notizia

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

Rapporto sul cuore della macchina

Editore: Jiaqi

La matrice è difficile da comprendere, ma potrebbe essere diversa se la si guarda da un’altra prospettiva.

Quando impariamo la matematica, spesso siamo frustrati dalla difficoltà e dall'astrattezza delle conoscenze che apprendiamo, ma a volte, solo cambiando la prospettiva, possiamo trovare una soluzione semplice e intuitiva al problema; Ad esempio, quando da bambini imparavamo la formula della somma dei quadrati (a+b)², forse non capivamo perché è uguale a a²+2ab+b². Sappiamo solo che è scritta così nella libro e l'insegnante ci ha chiesto di ricordarlo così finché un giorno non vediamo Ho ottenuto questa immagine animata:

All'improvviso ci è venuto in mente che possiamo capirlo da una prospettiva geometrica!

Ora, questo senso di illuminazione si ripresenta: una matrice non negativa può essere convertita in modo equivalente nel corrispondente grafo orientato!

Come mostrato nella figura seguente, la matrice 3×3 a sinistra può effettivamente essere rappresentata in modo equivalente come un grafo diretto contenente tre nodi a destra, e questa rappresentazione è molto utile sia per la teoria delle matrici che per quella dei grafi.

Questo esempio viene dal matematico Tivadar Danka, che si impegna a rendere la matematica accessibile a tutti. L’autoproclamato matematico “caotico buono” ha introdotto vividamente questa equivalenza tra matrici e grafici e i loro usi in una serie di tweet e post sul blog. Finora questi tweet sono stati letti più di 2 milioni di volte, hanno ricevuto più di 3.200 retweet e 9.100 preferiti.

Valenza di matrici e grafi orientati

Come mostrato nell'esempio sopra, se trattiamo ogni riga come un nodo, ogni elemento può essere rappresentato come un bordo orientato e ponderato. Naturalmente, 0 elementi possono essere ignorati. Se l'elemento si trova nella riga i e nella colonna j, corrisponde al bordo dal nodo i al nodo j.

A prima vista può sembrare complicato, ma possiamo iniziare osservando uno dei nodi.

Come mostrato nella figura, per questa matrice 3×3, la riga 1 corrisponde al nodo più in alto (qui lo chiamiamo nodo 1), che contiene 3 elementi ma uno di essi è 0, quindi il nodo si estende su due lati. Il bordo giallo rappresenta l'elemento 0,5 in (1,1), quindi è un bordo diretto che punta a se stesso con un peso di 0,5. Allo stesso modo, il bordo blu è il bordo che punta al nodo 2 e ha peso 1.

In questo modo, possiamo analizzare che la i-esima colonna della matrice corrisponde a tutti gli archi che puntano all'i-node.

A cosa serve questa rappresentazione equivalente?

Questa equivalenza tra matrici non negative e grafici orientati non solo può aiutarci a comprendere meglio le matrici e le loro operazioni, ma anche a semplificare alcuni processi di calcolo, e a sua volta può anche aiutarci a comprendere i grafici da una nuova prospettiva.

Ad esempio, le potenze di una matrice corrispondono alle passeggiate nel grafico.

Come mostrato nella figura sopra, per la k-esima potenza della matrice quadrata n×n A, il processo di somma di ciascun elemento includerà tutte le possibili passeggiate in k-passi.

Ad esempio, supponiamo di voler elevare al quadrato la matrice 3×3 sopra.

Se utilizziamo la moltiplicazione di matrici, dobbiamo calcolarla in questo modo:

Per il primo elemento del risultato dell'operazione, possiamo ottenere il risultato = 0,5×0,5+1×0,2+0×1,8 = 0,45. Infine, possiamo ottenere il risultato completo come:

Tuttavia, se si utilizza il metodo di visualizzazione del grafico riportato sopra, è possibile ottenere i risultati percorrendo il percorso. Allo stesso modo, per il primo elemento della matrice dei risultati, è necessario sommare tutti i percorsi pedonali in 2 passi conformi a a_{1,l}→a_{l,1}.

Tuttavia, se questo grafico orientato rappresenta lo stato di una catena di Markov, il quadrato della sua matrice di probabilità di transizione rappresenta essenzialmente la probabilità che la catena raggiunga un certo stato dopo 2 passaggi.

Non solo, rappresentare le matrici come un grafico può anche darci informazioni sulla struttura delle matrici non negative. Per fare questo, secondo Danka, dobbiamo prima comprendere il concetto di “componenti fortemente connessi”.

Componente fortemente connesso

Cos'è una componente fortemente connessa? Per un grafo orientato, se ogni altro nodo del grafo può essere raggiunto da ogni nodo, diciamo che il grafo è fortemente connesso. Come mostrato di seguito.

La componente fortemente connessa si riferisce alla parte/sottografo nel grafico diretto che può raggiungere una forte connettività. Come mostrato nella figura seguente, a sinistra e a destra c'è una componente fortemente connessa, mentre il bordo bianco al centro non appartiene ad alcuna componente fortemente connessa.

La figura seguente mostra un altro esempio, dove la parte gialla è la componente fortemente connessa:

La matrice corrispondente ad un grafo fortemente connesso è una matrice irriducibile, mentre tutte le altre matrici nella matrice non negativa sono matrici riducibili.

Danka spiega con un esempio. (Per semplicità di spiegazione, tutti i pesi nell'esempio sono pesi unitari, ma in pratica questi valori di peso possono essere qualsiasi valore non negativo.)

Successivamente, questo grafo, che contiene componenti fortemente connesse ma non è esso stesso fortemente connesso, viene trasformato nella corrispondente forma matriciale:

E questa matrice è una matrice riducibile.

Si può vedere che le due sottomatrici sulla diagonale principale rappresentano rispettivamente due componenti fortemente connesse, mentre la sottomatrice in alto a destra rappresenta il confine dalla prima componente fortemente connessa alla seconda componente fortemente connessa, e quella in basso a sinistra rappresenta Rappresenta il bordo dal 2° componente fortemente connesso al 1° componente fortemente connesso (poiché non esiste tale bordo, è tutto 0).

Questa forma di scrittura di una matrice a blocchi è chiamata forma normale di Frobenius.

Quindi, ci chiediamo naturalmente: possiamo convertire qualsiasi matrice non negativa in una matrice canonica di Frobenius?

Utilizzando un grafo diretto per rappresentare una matrice non negativa, possiamo facilmente vedere che la risposta è sì, poiché qualsiasi grafo diretto che rappresenta una matrice non negativa può essere rappresentato come componenti fortemente connessi tra loro. Il processo è molto semplice:

1. Costruire grafici diretti corrispondenti per matrici non negative;
2. Trova i componenti fortemente connessi;
3. Trova un modo migliore per etichettare ciascun nodo.

E il gioco è fatto!

Utilizza i grafici per ottenere la forma standard di Frobenius

Allora, qual è il modo migliore?

Sulla base dell'esempio sopra, diamo un'occhiata al processo.

Innanzitutto, i singoli componenti fortemente connessi vengono fusi in un unico oggetto, come mostrato nella figura seguente. Al momento possiamo trattare ogni componente fortemente connesso come una scatola nera: non ci interessa la sua struttura interna, ma solo le sue connessioni esterne.

Quindi, in questo nuovo grafico, dobbiamo trovare le componenti che hanno solo archi uscenti ma non archi entranti. Ce n'è solo uno in questo esempio specifico, che etichettiamo con il numero 0:

Il passo successivo è più problematico: numerare ciascun componente in modo che il numero di ciascun componente sia la distanza massima dal numero 0. L’esempio seguente illustra questo punto più chiaramente:

Si può vedere che ci sono due percorsi dal numero 0 al componente centrale, quindi scegli il percorso più lontano da 0 per numerarlo. Alla fine ho ottenuto:

In effetti, questo definisce l'ordine dei componenti. Successivamente contrassegnare i nodi interni di ciascun componente:

Se il grafico stesso proviene da una matrice, tale processo di rietichettatura risulta in una matrice canonica di Frobenius!

In effetti, questo processo di rietichettatura consiste nell'utilizzare una matrice di permutazione P per trasformare la matrice originale, e la matrice di permutazione è composta dal prodotto di più matrici trasposte.

Quella che segue è la forma completa del teorema:

Naturalmente, l'uso dei grafici per rappresentare le matrici va ben oltre. Ad esempio, possiamo anche utilizzare gli autovalori della matrice per definire gli autovalori del grafico. In effetti, questa linea di pensiero ha dato origine al campo di ricerca della teoria dei grafi spettrali.

Conclusione

Ovviamente, questa relazione di equivalenza tra matrici e grafici non è solo utile per la ricerca sulla teoria dei grafi, ma fornisce anche una nuova prospettiva per il calcolo e l'analisi dell'algebra lineare. Ha anche alcuni importanti usi pratici. Ad esempio, i dati sul DNA sono spesso rappresentati sotto forma di matrice o grafico.

Inoltre, sappiamo tutti l’importanza delle operazioni sulle matrici per l’attuale intelligenza artificiale di grandi dimensioni e i grafici rappresentati dai grafici della conoscenza stanno diventando un importante motore dell’attuale intelligenza artificiale attraverso tecnologie come la ricerca potenziata dal recupero. Il collegamento dei due potrebbe portare ad alcune nuove scoperte nell’interpretabilità dell’IA e nell’intelligenza artificiale dei grafici. Per lo meno, questo ci aiuta a imparare meglio l’algebra lineare.

In effetti, il contenuto di cui sopra è estratto dal libro "Matematica dell'apprendimento automatico" che Tivadar Danka sta scrivendo. Questo libro introdurrà le conoscenze matematiche relative all'apprendimento automatico da un livello semplice a quello profondo, consentendo ai lettori di comprendere veramente di cosa si tratta e perché viene fatto. Danka dichiara con sicurezza che questa sarà "la migliore risorsa per l'apprendimento dell'apprendimento automatico". Al momento, ha pubblicato online le anteprime di due capitoli. I lettori interessati possono visitare: https://tivadardanka.com/mathematics-of-machine-learning-preview/.