νέα

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Αναφορά Machine Heart

Επιμέλεια: Jiaqi

Η μήτρα είναι δύσκολο να κατανοηθεί, αλλά μπορεί να είναι διαφορετική αν την δεις από άλλη οπτική γωνία.

Όταν μαθαίνουμε μαθηματικά, είμαστε συχνά απογοητευμένοι από τη δυσκολία και την αφηρημένη γνώση που μαθαίνουμε, αλλά μερικές φορές, απλώς αλλάζοντας την προοπτική, μπορούμε να βρούμε μια απλή και διαισθητική λύση στο πρόβλημα. Για παράδειγμα, όταν μαθαίναμε τον τύπο του αθροίσματος των τετραγώνων (a+b)² όταν ήμασταν παιδιά, μπορεί να μην καταλαβαίνουμε γιατί ισούται με a²+2ab+b². Ξέρουμε μόνο ότι γράφεται έτσι στο το βιβλίο και ο δάσκαλος μας ζήτησε να το θυμηθούμε έτσι, μέχρι να δούμε μια μέρα με αυτή την κινούμενη εικόνα:

Ξαφνικά μας ξημέρωσε ότι μπορούμε να το καταλάβουμε από γεωμετρική προοπτική!

Τώρα, αυτή η αίσθηση της φώτισης εμφανίζεται ξανά: ένας μη αρνητικός πίνακας μπορεί να μετατραπεί ισοδύναμα στο αντίστοιχο κατευθυνόμενο γράφημα!

Όπως φαίνεται στο παρακάτω σχήμα, ο πίνακας 3×3 στα αριστερά μπορεί στην πραγματικότητα να αναπαρασταθεί ισοδύναμα ως ένα κατευθυνόμενο γράφημα που περιέχει τρεις κόμβους στα δεξιά, και αυτή η αναπαράσταση είναι πολύ χρήσιμη τόσο για τη θεωρία πινάκων όσο και για τη θεωρία γραφημάτων.

Αυτό το παράδειγμα προέρχεται από τον μαθηματικό Tivadar Danka, ο οποίος έχει δεσμευτεί να κάνει τα μαθηματικά προσβάσιμα σε όλους. Ο αυτοαποκαλούμενος «χαοτικός καλός» μαθηματικός εισήγαγε ζωντανά αυτήν την ισοδυναμία πινάκων και γραφημάτων και τις χρήσεις τους σε μια σειρά από tweets και αναρτήσεις ιστολογίου. Μέχρι στιγμής, αυτά τα tweets έχουν διαβαστεί περισσότερες από 2 εκατομμύρια φορές, έχουν λάβει περισσότερα από 3.200 retweets και 9.100 αγαπημένα.

Σθένος πινάκων και κατευθυνόμενων γραφημάτων

Όπως φαίνεται στο παραπάνω παράδειγμα, αν αντιμετωπίσουμε κάθε σειρά ως κόμβο, κάθε στοιχείο μπορεί να αναπαρασταθεί ως κατευθυνόμενη και σταθμισμένη ακμή. Φυσικά, 0 στοιχεία μπορούν να αγνοηθούν. Εάν το στοιχείο βρίσκεται στη σειρά i και στη στήλη j, αντιστοιχεί στην άκρη από τον κόμβο i στον κόμβο j.

Με την πρώτη ματιά, αυτό μπορεί να φαίνεται περίπλοκο, αλλά μπορούμε να ξεκινήσουμε κοιτάζοντας έναν από τους κόμβους.

Όπως φαίνεται στο σχήμα, για αυτόν τον πίνακα 3×3, η σειρά 1 αντιστοιχεί στον κορυφαίο κόμβο (εδώ τον ονομάζουμε κόμβο 1), ο οποίος περιέχει 3 στοιχεία αλλά το ένα από αυτά είναι 0, οπότε ο κόμβος εκτείνεται σε δύο πλευρές. Η κίτρινη άκρη αντιπροσωπεύει το στοιχείο 0,5 στο (1,1), επομένως είναι μια κατευθυνόμενη άκρη που δείχνει προς τον εαυτό της με βάρος 0,5. Με τον ίδιο τρόπο, το μπλε άκρο είναι το άκρο που δείχνει στον κόμβο 2 και έχει βάρος 1.

Με αυτόν τον τρόπο, μπορούμε να αναλύσουμε ότι η i-η στήλη του πίνακα αντιστοιχεί σε όλες τις ακμές που δείχνουν προς τον κόμβο i.

Ποια είναι η χρήση αυτής της ισοδύναμης αναπαράστασης;

Αυτή η ισοδυναμία μεταξύ μη αρνητικών πινάκων και κατευθυνόμενων γραφημάτων μπορεί όχι μόνο να μας βοηθήσει να κατανοήσουμε καλύτερα τους πίνακες και τις λειτουργίες τους, αλλά και να απλοποιήσουμε ορισμένες διαδικασίες υπολογισμού με τη σειρά του, αυτό μπορεί επίσης να μας βοηθήσει να κατανοήσουμε τα γραφήματα από μια νέα προοπτική.

Για παράδειγμα, οι δυνάμεις ενός πίνακα αντιστοιχούν σε περιπάτους στο γράφημα.

Όπως φαίνεται στο παραπάνω σχήμα, για την k-η ισχύ του n×n τετραγωνικού πίνακα A, η διαδικασία άθροισης κάθε στοιχείου θα περιλαμβάνει όλα τα πιθανά βήματα k-βημάτων.

Για παράδειγμα, ας υποθέσουμε ότι θέλουμε να τετραγωνίσουμε τον πίνακα 3×3 παραπάνω.

Εάν χρησιμοποιούμε πολλαπλασιασμό πίνακα, πρέπει να τον υπολογίσουμε ως εξής:

Για το πρώτο στοιχείο του αποτελέσματος της πράξης, μπορούμε να πάρουμε το αποτέλεσμα = 0,5×0,5+1×0,2+0×1,8 = 0,45. Τέλος, μπορούμε να πάρουμε το πλήρες αποτέλεσμα ως εξής:

Ωστόσο, εάν χρησιμοποιήσετε την παραπάνω μέθοδο βάδισης γραφήματος, μπορείτε να πάρετε τα αποτελέσματα περπατώντας το μονοπάτι. Ομοίως, για το πρώτο στοιχείο του πίνακα αποτελεσμάτων, είναι απαραίτητο να συνοψιστούν όλα τα μονοπάτια πεζοπορίας 2 βημάτων που συμμορφώνονται με το a_{1,l}→a_{l,1}.

Ωστόσο, εάν αυτό το κατευθυνόμενο γράφημα αντιπροσωπεύει την κατάσταση μιας αλυσίδας Markov, το τετράγωνο του πίνακα πιθανοτήτων μετάβασης ουσιαστικά αντιπροσωπεύει την πιθανότητα η αλυσίδα να φτάσει σε μια συγκεκριμένη κατάσταση μετά από 2 βήματα.

Όχι μόνο αυτό, η αναπαράσταση πινάκων ως γράφημα μπορεί επίσης να μας δώσει πληροφορίες για τη δομή των μη αρνητικών πινάκων. Για να γίνει αυτό, ο Danka είπε ότι πρέπει πρώτα να κατανοήσουμε την έννοια των "δυνατά συνδεδεμένων εξαρτημάτων".

Ισχυρά συνδεδεμένο εξάρτημα

Τι είναι ένα ισχυρά συνδεδεμένο στοιχείο; Για ένα κατευθυνόμενο γράφημα, εάν κάθε άλλος κόμβος στο γράφημα μπορεί να επιτευχθεί από κάθε κόμβο, λέμε ότι το γράφημα είναι ισχυρά συνδεδεμένο. Όπως φαίνεται παρακάτω.

Το ισχυρά συνδεδεμένο στοιχείο αναφέρεται στο τμήμα/υπογράφημα στο κατευθυνόμενο γράφημα που μπορεί να επιτύχει ισχυρή συνδεσιμότητα. Όπως φαίνεται στο παρακάτω σχήμα, υπάρχει ένα ισχυρά συνδεδεμένο εξάρτημα στα αριστερά και στα δεξιά, ενώ η λευκή άκρη στη μέση δεν ανήκει σε κανένα εξάρτημα με ισχυρή σύνδεση.

Το παρακάτω σχήμα δείχνει ένα άλλο παράδειγμα, όπου το κίτρινο τμήμα είναι το ισχυρά συνδεδεμένο στοιχείο:

Ο πίνακας που αντιστοιχεί σε ένα ισχυρά συνδεδεμένο γράφημα είναι ένας μη αναγώγιμος πίνακας, ενώ όλοι οι άλλοι πίνακες στον μη αρνητικό πίνακα είναι αναγώγιμοι πίνακες.

Η Danka εξηγεί με ένα παράδειγμα. (Για την απλότητα της εξήγησης, όλα τα βάρη στο παράδειγμα είναι μοναδιαία βάρη, αλλά στην πράξη αυτές οι τιμές βάρους μπορεί να είναι οποιεσδήποτε μη αρνητικές τιμές.)

Στη συνέχεια, αυτό το γράφημα, το οποίο περιέχει ισχυρά συνδεδεμένα στοιχεία αλλά δεν είναι ισχυρά συνδεδεμένο το ίδιο, μετατρέπεται στην αντίστοιχη μορφή μήτρας:

Και αυτός ο πίνακας είναι ένας αναγόμενος πίνακας.

Μπορεί να φανεί ότι οι δύο υπομήτρες στην κύρια διαγώνιο αντιπροσωπεύουν δύο ισχυρά συνδεδεμένες συνιστώσες αντίστοιχα, ενώ η υπομήτρα επάνω δεξιά αντιπροσωπεύει την άκρη από το πρώτο ισχυρά συνδεδεμένο στοιχείο στο δεύτερο ισχυρά συνδεδεμένο στοιχείο, και αυτό στο κάτω αριστερό αντιπροσωπεύει Αντιπροσωπεύει την άκρη από το 2ο ισχυρά συνδεδεμένο στοιχείο στο 1ο ισχυρά συνδεδεμένο στοιχείο (επειδή δεν υπάρχει τέτοια ακμή, είναι όλα 0).

Αυτή η μορφή γραφής μπλοκ μήτρας ονομάζεται κανονική μορφή Frobenius.

Λοιπόν, αναρωτιόμαστε φυσικά: Μπορούμε να μετατρέψουμε οποιονδήποτε μη αρνητικό πίνακα σε κανονικό πίνακα Frobenius;

Χρησιμοποιώντας ένα κατευθυνόμενο γράφημα για την αναπαράσταση ενός μη αρνητικού πίνακα, μπορούμε εύκολα να δούμε ότι η απάντηση είναι ναι, καθώς κάθε κατευθυνόμενο γράφημα που αντιπροσωπεύει έναν μη αρνητικό πίνακα μπορεί να αναπαρασταθεί ως ισχυρά συνδεδεμένα στοιχεία που συνδέονται μεταξύ τους. Η διαδικασία είναι πολύ απλή:

1. Κατασκευάστε τα αντίστοιχα κατευθυνόμενα γραφήματα για μη αρνητικούς πίνακες.
2. Βρείτε τα ισχυρά συνδεδεμένα στοιχεία.
3. Βρείτε έναν καλύτερο τρόπο να επισημάνετε κάθε κόμβο.

Και τελειώσατε!

Χρησιμοποιήστε γραφήματα για να λάβετε την τυπική φόρμα Frobenius

Λοιπόν, ποιος είναι αυτός ο καλύτερος τρόπος;

Με βάση το παραπάνω παράδειγμα, ας ρίξουμε μια ματιά στη διαδικασία.

Πρώτον, τα μεμονωμένα ισχυρά συνδεδεμένα εξαρτήματα συγχωνεύονται σε ένα ενιαίο αντικείμενο, όπως φαίνεται στο παρακάτω σχήμα. Αυτή τη στιγμή, μπορούμε να αντιμετωπίσουμε κάθε ισχυρά συνδεδεμένο στοιχείο ως ένα μαύρο κουτί - δεν μας ενδιαφέρει η εσωτερική του δομή, παρά μόνο οι εξωτερικές του συνδέσεις.

Στη συνέχεια, σε αυτό το νέο γράφημα, πρέπει να βρούμε τα στοιχεία που έχουν μόνο εξερχόμενες άκρες αλλά όχι εισερχόμενες άκρες. Υπάρχει μόνο ένα σε αυτό το συγκεκριμένο παράδειγμα, το οποίο ονομάζουμε αριθμό 0:

Το επόμενο βήμα είναι πιο ενοχλητικό: αριθμήστε κάθε στοιχείο έτσι ώστε ο αριθμός κάθε στοιχείου να είναι η πιο απομακρυσμένη από τον αριθμό 0. Το ακόλουθο παράδειγμα απεικονίζει αυτό το σημείο πιο ξεκάθαρα:

Μπορεί να φανεί ότι υπάρχουν δύο μονοπάτια από τον αριθμό 0 έως το μεσαίο στοιχείο, οπότε επιλέξτε το μονοπάτι που βρίσκεται πιο μακριά από το 0 για να το αριθμήσετε. Τελικά πήρα:

Στην πραγματικότητα, αυτό καθορίζει τη σειρά των εξαρτημάτων. Στη συνέχεια, σημειώστε τους εσωτερικούς κόμβους κάθε στοιχείου:

Εάν το ίδιο το γράφημα προέρχεται από έναν πίνακα, μια τέτοια διαδικασία επανασήμανσης καταλήγει σε έναν κανονικό πίνακα Frobenius!

Στην πραγματικότητα, αυτή η διαδικασία επανασήμανσης είναι να χρησιμοποιηθεί ένας πίνακας μετάθεσης P για να μετασχηματίσει τον αρχικό πίνακα και ο πίνακας μετάθεσης αποτελείται από το γινόμενο πολλαπλών μετατιθέμενων πινάκων.

Ακολουθεί η πλήρης μορφή του θεωρήματος:

Φυσικά, η χρήση γραφημάτων για την αναπαράσταση πινάκων υπερβαίνει αυτό, για παράδειγμα, μπορούμε επίσης να χρησιμοποιήσουμε τις ιδιοτιμές του πίνακα για να ορίσουμε τις ιδιοτιμές του γραφήματος. Στην πραγματικότητα, αυτή η γραμμή σκέψης έδωσε αφορμή για το ερευνητικό πεδίο της θεωρίας φασματικών γραφημάτων.

Σύναψη

Προφανώς, αυτή η σχέση ισοδυναμίας μεταξύ πινάκων και γραφημάτων δεν είναι μόνο χρήσιμη για την έρευνα της θεωρίας γραφημάτων, αλλά παρέχει επίσης μια νέα προοπτική για τον υπολογισμό και την ανάλυση της γραμμικής άλγεβρας. Έχει επίσης κάποιες σημαντικές πρακτικές χρήσεις. Για παράδειγμα, τα δεδομένα DNA αναπαρίστανται συχνά με τη μορφή μήτρας ή γραφήματος.

Επιπλέον, όλοι γνωρίζουμε τη σημασία των λειτουργιών μήτρας για την τρέχουσα τεχνητή νοημοσύνη μεγάλου μοντέλου και τα γραφήματα που αντιπροσωπεύονται από γραφήματα γνώσης γίνονται σημαντικός μοχλός της τρέχουσας τεχνητής νοημοσύνης μέσω τεχνολογιών όπως η βελτιωμένη αναζήτηση με ανάκτηση. Η σύνδεση των δύο μπορεί να φέρει μερικές νέες ανακαλύψεις στην ερμηνευτικότητα της τεχνητής νοημοσύνης και στη γραφική παράσταση της τεχνητής νοημοσύνης. Τουλάχιστον, αυτό μας βοηθά να μάθουμε καλύτερα τη γραμμική άλγεβρα.

Μάλιστα, το παραπάνω περιεχόμενο εξάγεται από το βιβλίο «Mathematics of Machine Learning» που γράφει ο Tivadar Danka. Αυτό το βιβλίο θα εισαγάγει τις μαθηματικές γνώσεις που σχετίζονται με τη μηχανική μάθηση από ένα απλό σε ένα βαθύ επίπεδο, επιτρέποντας στους αναγνώστες να κατανοήσουν πραγματικά τι είναι και γιατί η Danka δηλώνει με σιγουριά ότι αυτή θα είναι «η καλύτερη πηγή για την εκμάθηση μηχανών». Προς το παρόν, έχει κυκλοφορήσει δύο προεπισκοπήσεις κεφαλαίων Οι ενδιαφερόμενοι αναγνώστες μπορούν να επισκεφθούν: https://tivadardanka.com/mathematics-of-machine-learning-preview/.