Nachricht

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

Maschinenherzbericht

Herausgeber: Jiaqi

Die Matrix ist schwer zu verstehen, kann aber anders ausfallen, wenn man sie aus einer anderen Perspektive betrachtet.

Wenn wir Mathematik lernen, sind wir oft frustriert über die Schwierigkeit und Abstraktheit des gelernten Wissens, aber manchmal können wir einfach durch einen Perspektivenwechsel eine einfache und intuitive Lösung für das Problem finden. Als wir zum Beispiel als Kinder die Formel der Quadratsumme (a+b)² lernten, verstehen wir vielleicht nicht, warum sie gleich a²+2ab+b² ist. Wir wissen nur, dass sie in der Formel so geschrieben ist Buch und der Lehrer bat uns, es uns so zu merken, bis wir eines Tages dieses animierte Bild sahen:

Uns wurde plötzlich klar, dass wir es aus einer geometrischen Perspektive verstehen können!

Jetzt tritt dieses Gefühl der Erleuchtung erneut auf: Eine nichtnegative Matrix kann äquivalent in den entsprechenden gerichteten Graphen umgewandelt werden!

Wie in der Abbildung unten gezeigt, kann die 3×3-Matrix auf der linken Seite tatsächlich äquivalent als gerichteter Graph dargestellt werden, der rechts drei Knoten enthält, und diese Darstellung ist sowohl für die Matrix- als auch für die Graphentheorie sehr hilfreich.

Dieses Beispiel stammt vom Mathematiker Tivadar Danka, der sich dafür einsetzt, Mathematik für jedermann zugänglich zu machen. Der selbsternannte „chaotisch gute“ Mathematiker stellte diese Äquivalenz von Matrizen und Graphen und deren Verwendung in einer Reihe von Tweets und Blogbeiträgen anschaulich vor. Bisher wurden diese Tweets mehr als 2 Millionen Mal gelesen, erhielten mehr als 3.200 Retweets und 9.100 Favoriten.

Valenz von Matrizen und gerichteten Graphen

Wie im obigen Beispiel gezeigt, kann jedes Element als gerichtete und gewichtete Kante dargestellt werden, wenn wir jede Zeile als Knoten behandeln. Natürlich können 0 Elemente ignoriert werden. Befindet sich das Element in Zeile i und Spalte j, entspricht es der Kante vom Knoten i zum Knoten j.

Auf den ersten Blick mag dies kompliziert erscheinen, aber wir können damit beginnen, einen der Knoten zu betrachten.

Wie in der Abbildung gezeigt, entspricht Zeile 1 für diese 3 × 3-Matrix dem obersten Knoten (wir nennen ihn hier Knoten 1), der 3 Elemente enthält, von denen jedoch eines 0 ist, sodass sich der Knoten über zwei Seiten erstreckt. Die gelbe Kante stellt das Element 0,5 bei (1,1) dar, es handelt sich also um eine gerichtete Kante, die auf sich selbst zeigt, mit einem Gewicht von 0,5. Ebenso ist die blaue Kante die Kante, die auf Knoten 2 zeigt und ein Gewicht von 1 hat.

Auf diese Weise können wir analysieren, dass die i-te Spalte der Matrix allen Kanten entspricht, die auf den i-Knoten zeigen.

Welchen Nutzen hat diese äquivalente Darstellung?

Diese Äquivalenz zwischen nichtnegativen Matrizen und gerichteten Graphen kann uns nicht nur helfen, Matrizen und ihre Operationen besser zu verstehen, sondern auch dazu beitragen, einige Berechnungsprozesse zu vereinfachen. Dies kann uns auch dabei helfen, Graphen aus einer neuen Perspektive zu verstehen.

Beispielsweise entsprechen die Potenzen einer Matrix den Spaziergängen im Diagramm.

Wie in der Abbildung oben gezeigt, umfasst der Summierungsprozess jedes Elements für die k-te Potenz der n×n-Quadratmatrix A alle möglichen k-Schritt-Spaziergänge.

Nehmen wir zum Beispiel an, wir möchten die obige 3×3-Matrix quadrieren.

Wenn wir eine Matrixmultiplikation verwenden, müssen wir sie wie folgt berechnen:

Für das erste Element des Operationsergebnisses können wir das Ergebnis = 0,5×0,5+1×0,2+0×1,8 = 0,45 erhalten. Schließlich können wir das vollständige Ergebnis erhalten als:

Wenn Sie jedoch die oben beschriebene Graph-Walking-Methode verwenden, können Sie die Ergebnisse erhalten, indem Sie den Pfad ablaufen. Ebenso ist es für das erste Element der Ergebnismatrix erforderlich, alle zweistufigen Gehwege aufzusummieren, die a_{1,l}→a_{l,1} entsprechen.

Wenn dieser gerichtete Graph jedoch den Zustand einer Markov-Kette darstellt, stellt das Quadrat seiner Übergangswahrscheinlichkeitsmatrix im Wesentlichen die Wahrscheinlichkeit dar, mit der die Kette nach zwei Schritten einen bestimmten Zustand erreicht.

Darüber hinaus kann uns die Darstellung von Matrizen als Diagramm Einblicke in die Struktur nichtnegativer Matrizen geben. Um dies zu erreichen, müssen wir laut Danka zunächst das Konzept der „stark verbundenen Komponenten“ verstehen.

Stark verbundene Komponente

Was ist eine stark zusammenhängende Komponente? Wenn bei einem gerichteten Graphen jeder andere Knoten im Graphen von jedem Knoten aus erreichbar ist, sagen wir, dass der Graph stark zusammenhängend ist. Wie unten gezeigt.

Die stark verbundene Komponente bezieht sich auf den Teil/Untergraphen im gerichteten Graphen, der eine starke Konnektivität erreichen kann. Wie in der Abbildung unten gezeigt, gibt es links und rechts eine stark verbundene Komponente, während der weiße Rand in der Mitte zu keiner stark verbundenen Komponente gehört.

Die folgende Abbildung zeigt ein weiteres Beispiel, bei dem der gelbe Teil die stark verbundene Komponente ist:

Die einem stark zusammenhängenden Graphen entsprechende Matrix ist eine irreduzible Matrix, während alle anderen Matrizen in der nichtnegativen Matrix reduzierbare Matrizen sind.

Danka erklärt es anhand eines Beispiels. (Der Einfachheit halber sind alle Gewichte im Beispiel Einheitsgewichte, in der Praxis können diese Gewichtswerte jedoch beliebige nicht negative Werte sein.)

Als nächstes wird dieser Graph, der stark zusammenhängende Komponenten enthält, aber selbst nicht stark zusammenhängend ist, in die entsprechende Matrixform umgewandelt:

Und diese Matrix ist eine reduzierbare Matrix.

Es ist ersichtlich, dass die beiden Untermatrizen auf der Hauptdiagonale jeweils zwei stark verbundene Komponenten darstellen, während die Untermatrix oben rechts die Kante von der ersten stark verbundenen Komponente zur zweiten stark verbundenen Komponente darstellt und die Untermatrix unten links die Kante darstellt Stellt die Kante von der zweiten stark verbundenen Komponente zur ersten stark verbundenen Komponente dar (da es keine solche Kante gibt, ist alles 0).

Diese Form des Schreibens einer Blockmatrix wird als Frobenius-Normalform bezeichnet.

Daher fragen wir uns natürlich: Können wir jede nichtnegative Matrix in eine kanonische Frobenius-Matrix umwandeln?

Wenn wir einen gerichteten Graphen zur Darstellung einer nicht negativen Matrix verwenden, können wir leicht erkennen, dass die Antwort „Ja“ lautet, da jeder gerichtete Graph, der eine nicht negative Matrix darstellt, als stark verbundene Komponenten dargestellt werden kann, die miteinander verbunden sind. Der Vorgang ist ganz einfach:

1. Konstruieren Sie entsprechende gerichtete Graphen für nichtnegative Matrizen;
2. Finden Sie die stark zusammenhängenden Komponenten;
3. Finden Sie eine bessere Möglichkeit, jeden Knoten zu beschriften.

Und schon sind Sie fertig!

Verwenden Sie Diagramme, um die Frobenius-Standardform zu erhalten

Was ist also dieser bessere Weg?

Schauen wir uns anhand des obigen Beispiels den Prozess an.

Zunächst werden die einzelnen stark verbundenen Komponenten zu einem einzigen Objekt verschmolzen, wie in der folgenden Abbildung dargestellt. Zu diesem Zeitpunkt können wir jede stark verbundene Komponente als Black Box behandeln – wir kümmern uns nicht um ihre interne Struktur, sondern nur um ihre externen Verbindungen.

Dann müssen wir in diesem neuen Diagramm die Komponenten finden, die nur ausgehende Kanten, aber keine eingehenden Kanten haben. In diesem konkreten Beispiel gibt es nur eines, das wir mit der Nummer 0 bezeichnen:

Der nächste Schritt ist schwieriger: Nummerieren Sie jede Komponente so, dass die Nummer jeder Komponente am weitesten von der Nummer 0 entfernt ist. Das folgende Beispiel verdeutlicht diesen Punkt noch deutlicher:

Es ist ersichtlich, dass es zwei Pfade von der Nummer 0 zur mittleren Komponente gibt. Wählen Sie daher den Pfad, der am weitesten von 0 entfernt ist, um ihn zu nummerieren. Endlich habe ich:

Dies definiert faktisch die Reihenfolge der Komponenten. Markieren Sie als Nächstes die internen Knoten jeder Komponente:

Wenn der Graph selbst aus einer Matrix stammt, führt ein solcher Umbenennungsprozess zu einer kanonischen Frobenius-Matrix!

Tatsächlich besteht dieser Neumarkierungsprozess darin, eine Permutationsmatrix P zu verwenden, um die ursprüngliche Matrix zu transformieren, und die Permutationsmatrix besteht aus dem Produkt mehrerer transponierter Matrizen.

Das Folgende ist die vollständige Form des Satzes:

Natürlich geht die Verwendung von Diagrammen zur Darstellung von Matrizen weit darüber hinaus. Beispielsweise können wir auch die Eigenwerte der Matrix verwenden, um die Eigenwerte des Diagramms zu definieren. Tatsächlich entstand aus dieser Denkrichtung das Forschungsgebiet der Spektralgraphentheorie.

Abschluss

Offensichtlich ist diese Äquivalenzbeziehung zwischen Matrizen und Graphen nicht nur hilfreich für die Forschung zur Graphentheorie, sondern bietet auch eine neue Perspektive für die Berechnung und Analyse der linearen Algebra. Es hat auch einige wichtige praktische Verwendungsmöglichkeiten. Beispielsweise werden DNA-Daten häufig in Form einer Matrix oder eines Diagramms dargestellt.

Darüber hinaus wissen wir alle, wie wichtig Matrixoperationen für die aktuelle KI mit großen Modellen sind, und durch Wissensgraphen dargestellte Diagramme werden durch Technologien wie die abrufgestützte Suche zu einem wichtigen Treiber der aktuellen KI. Die Verknüpfung beider könnte zu neuen Durchbrüchen in der Interpretierbarkeit von KI und der grafischen künstlichen Intelligenz führen. Zumindest hilft uns dies, die lineare Algebra besser zu lernen.

Tatsächlich stammt der obige Inhalt aus dem Buch „Mathematik des maschinellen Lernens“, das Tivadar Danka schreibt. In diesem Buch werden die mathematischen Kenntnisse im Zusammenhang mit maschinellem Lernen von einer einfachen bis hin zu einer tiefgreifenden Ebene vermittelt, sodass die Leser wirklich verstehen können, was es ist und warum es durchgeführt wird. Danka erklärt zuversichtlich, dass dies „die beste Ressource für das Erlernen maschinellen Lernens“ sein wird. Derzeit hat er zwei Kapitelvorschauen online veröffentlicht: https://tivadardanka.com/mathematics-of-machine-learning-preview/.