nouvelles

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

Rapport sur le cœur de la machine

Editeur : Jiaqi

La matrice est difficile à comprendre, mais elle peut être différente si vous la regardez sous un autre angle.

Lorsque nous apprenons les mathématiques, nous sommes souvent frustrés par la difficulté et le caractère abstrait des connaissances que nous apprenons, mais parfois, en changeant simplement de perspective, nous pouvons trouver une solution simple et intuitive au problème. Par exemple, lorsque nous apprenions la formule de la somme des carrés (a+b)² lorsque nous étions enfants, nous ne comprenons peut-être pas pourquoi elle est égale à a²+2ab+b². Nous savons seulement qu'elle est écrite ainsi dans le. livre et le professeur nous a demandé de nous en souvenir comme ceci jusqu'au jour où nous voyons J'ai cette image animée :

Il nous est soudain apparu que nous pouvions le comprendre d’un point de vue géométrique !

Maintenant, ce sentiment d’illumination se reproduit : une matrice non négative peut être convertie de manière équivalente en le graphe orienté correspondant !

Comme le montre la figure ci-dessous, la matrice 3×3 à gauche peut en fait être représentée de manière équivalente sous la forme d'un graphe orienté contenant trois nœuds à droite, et cette représentation est très utile pour la théorie des matrices et des graphes.

Cet exemple vient du mathématicien Tivadar Danka, qui s'engage à rendre les mathématiques accessibles à tous. Le mathématicien autoproclamé « bon chaotique » a présenté de manière vivante cette équivalence des matrices et des graphiques ainsi que leurs utilisations dans une série de tweets et d'articles de blog. Jusqu’à présent, ces tweets ont été lus plus de 2 millions de fois, ont reçu plus de 3 200 retweets et 9 100 favoris.

Valence des matrices et des graphes orientés

Comme le montre l'exemple ci-dessus, si nous traitons chaque ligne comme un nœud, chaque élément peut être représenté comme une arête dirigée et pondérée. Bien entendu, 0 élément peut être ignoré. Si l'élément est situé dans la ligne i et la colonne j, il correspond au bord du nœud i au nœud j.

À première vue, cela peut paraître compliqué, mais on peut commencer par s’intéresser à l’un des nœuds.

Comme le montre la figure, pour cette matrice 3×3, la ligne 1 correspond au nœud le plus haut (nous l'appelons ici nœud 1), qui contient 3 éléments mais l'un d'eux est 0, donc le nœud s'étend sur deux côtés. Le bord jaune représente l'élément 0,5 en (1,1), c'est donc un bord dirigé pointant vers lui-même avec un poids de 0,5. De la même manière, le bord bleu est le bord qui pointe vers le nœud 2 et a un poids de 1.

De cette façon, nous pouvons analyser que la i-ème colonne de la matrice correspond à toutes les arêtes pointant vers le i-nœud.

A quoi sert cette représentation équivalente ?

Cette équivalence entre les matrices non négatives et les graphiques orientés peut non seulement nous aider à mieux comprendre les matrices et leurs opérations, mais également à simplifier certains processus de calcul, ce qui peut également nous aider à comprendre les graphiques sous un nouvel angle.

Par exemple, les puissances d'une matrice correspondent à des parcours dans le graphe.

Comme le montre la figure ci-dessus, pour la k-ième puissance de la matrice carrée n×n A, le processus de sommation de chaque élément inclura toutes les marches possibles en k étapes.

Par exemple, disons que nous voulons mettre au carré la matrice 3×3 ci-dessus.

Si nous utilisons la multiplication matricielle, nous devons la calculer comme ceci :

Pour le premier élément du résultat de l’opération, on peut obtenir le résultat = 0,5×0,5+1×0,2+0×1,8 = 0,45. Finalement, nous pouvons obtenir le résultat complet comme suit :

Cependant, si vous utilisez la méthode de marche graphique ci-dessus, vous pouvez obtenir les résultats via des sentiers de marche. De même, pour le premier élément de la matrice de résultats, il est nécessaire de résumer tous les parcours de marche en 2 étapes conformes à a_{1,l}→a_{l,1}.

Cependant, si ce graphe orienté représente l'état d'une chaîne de Markov, le carré de sa matrice de probabilité de transition représente essentiellement la probabilité que la chaîne atteigne un certain état après 2 étapes.

De plus, représenter les matrices sous forme de graphique peut également nous donner un aperçu de la structure des matrices non négatives. Pour ce faire, Danka a déclaré que nous devons d'abord comprendre le concept de « composants fortement connectés ».

Composants fortement connectés

Qu'est-ce qu'un composant fortement connecté ? Pour un graphe orienté, si tous les autres nœuds du graphe peuvent être atteints à partir de chaque nœud, nous disons que le graphe est fortement connecté. Comme indiqué ci-dessous.

Le composant fortement connecté fait référence à la partie/sous-graphe du graphe orienté qui peut atteindre une forte connectivité. Comme le montre la figure ci-dessous, il y a un composant fortement connecté à gauche et à droite, tandis que le bord blanc au milieu n'appartient à aucun composant fortement connecté.

La figure ci-dessous montre un autre exemple, où la partie jaune est le composant fortement connecté :

La matrice correspondant à un graphe fortement connexe est une matrice irréductible, tandis que toutes les autres matrices de la matrice non négative sont des matrices réductibles.

Danka explique avec un exemple. (Pour simplifier l'explication, tous les poids dans l'exemple sont des poids unitaires, mais en pratique, ces valeurs de poids peuvent être n'importe quelle valeur non négative.)

Ensuite, ce graphe, qui contient des composantes fortement connectées mais qui n'est pas lui-même fortement connecté, est transformé sous la forme matricielle correspondante :

Et cette matrice est une matrice réductible.

On peut voir que les deux sous-matrices sur la diagonale principale représentent respectivement deux composants fortement connectés, tandis que la sous-matrice en haut à droite représente le bord du premier composant fortement connecté au deuxième composant fortement connecté, et celle en bas à gauche représente Représente le bord du 2ème composant fortement connecté au 1er composant fortement connecté (car il n'y a pas un tel bord, tout est 0).

Cette forme d'écriture d'une matrice de blocs est appelée forme normale de Frobenius.

Nous nous demandons donc naturellement : pouvons-nous convertir n’importe quelle matrice non négative en une matrice canonique de Frobenius ?

En utilisant un graphe orienté pour représenter une matrice non négative, nous pouvons facilement voir que la réponse est oui, puisque tout graphe orienté représentant une matrice non négative peut être représenté comme des composants fortement connectés les uns aux autres. Le processus est très simple :

1. Construire des graphiques orientés correspondants pour des matrices non négatives ;
2. Trouvez les composants fortement connectés ;
3. Trouvez une meilleure façon d’étiqueter chaque nœud.

Et c'est fini !

Utilisez des graphiques pour obtenir le formulaire standard Frobenius

Alors, quelle est cette meilleure façon ?

Sur la base de l'exemple ci-dessus, examinons le processus.

Tout d’abord, les composants individuels fortement connectés sont fusionnés en un seul objet, comme le montre la figure ci-dessous. À l’heure actuelle, nous pouvons traiter chaque composant fortement connecté comme une boîte noire : nous ne nous soucions pas de sa structure interne, seulement de ses connexions externes.

Ensuite, dans ce nouveau graphe, nous devons trouver les composants qui n’ont que des arêtes sortantes mais pas d’arêtes entrantes. Il n’y en a qu’un dans cet exemple spécifique, que nous étiquetons numéro 0 :

L'étape suivante est plus compliquée : numéroter chaque composant de manière à ce que le numéro de chaque composant soit le plus éloigné du numéro 0. L’exemple suivant illustre ce point plus clairement :

On peut voir qu'il existe deux chemins du numéro 0 au composant du milieu, choisissez donc le chemin le plus éloigné de 0 pour le numéroter. J'ai finalement obtenu :

En effet, cela définit l’ordre des composants. Marquez ensuite les nœuds internes de chaque composant :

Si le graphe lui-même provient d'une matrice, un tel processus de réétiquetage aboutit à une matrice canonique de Frobenius !

En fait, ce processus de réétiquetage consiste à utiliser une matrice de permutation P pour transformer la matrice d'origine, et la matrice de permutation est composée du produit de plusieurs matrices transposées.

Voici la forme complète du théorème :

Bien entendu, l'utilisation de graphiques pour représenter des matrices va bien au-delà. Par exemple, on peut également utiliser les valeurs propres de la matrice pour définir les valeurs propres du graphe. En fait, cette ligne de pensée a donné naissance au domaine de recherche de la théorie des graphes spectraux.

Conclusion

De toute évidence, cette relation d’équivalence entre matrices et graphiques est non seulement utile pour la recherche en théorie des graphes, mais offre également une nouvelle perspective pour le calcul et l’analyse de l’algèbre linéaire. Il a également des utilisations pratiques importantes. Par exemple, les données ADN sont souvent représentées sous la forme d’une matrice ou d’un graphique.

De plus, nous connaissons tous l’importance des opérations matricielles pour l’IA actuelle à grands modèles, et les graphiques représentés par des graphes de connaissances deviennent un moteur important de l’IA actuelle grâce à des technologies telles que la recherche améliorée par récupération. Relier les deux pourrait apporter de nouvelles avancées en matière d’interprétabilité de l’IA et d’intelligence artificielle graphique. À tout le moins, cela nous aide à mieux apprendre l’algèbre linéaire.

En fait, le contenu ci-dessus est extrait du livre « Mathematics of Machine Learning » qu'écrit Tivadar Danka. Ce livre présentera les connaissances mathématiques liées à l'apprentissage automatique du niveau simple au niveau approfondi, afin que les lecteurs puissent vraiment comprendre de quoi il s'agit et pourquoi cela est fait, et Danka déclare avec confiance que ce sera « la meilleure ressource pour l'apprentissage de l'apprentissage automatique ». ". À l'heure actuelle, il a publié deux aperçus de chapitres en ligne. Les lecteurs intéressés peuvent visiter : https://tivadardanka.com/mathematics-of-machine-learning-preview/.