Computing with traceable tensor networks

Stellen Sie sich vor, Sie versuchen, ein Puzzle zu lösen, bei dem sich die Anzahl der möglichen Anordnungen des gesamten Ganzen jedes Mal explodiert, wenn Sie ein neues Teil hinzufügen. Dies ist der Albtraum „hochdimensionaler“ Probleme in Wissenschaft und Technik. Ob Sie modellieren, wie sich Wärme durch ein komplexes Material ausbreitet, die Bewegung von Teilchen in einer Flüssigkeit vorhersagen oder das Verhalten eines Quantensystems simulieren – die Mathematik wird schnell extrem kompliziert. Wenn ein Problem nur wenige Variablen hat, kann man es auf einem Laptop lösen. Aber wenn es zehn, zwanzig oder hundert Variablen hat, wächst die Menge der benötigten Daten so gewaltig an, dass selbst die größten Supercomputer der Welt an Speicherplatz ausgehen würden, bevor sie den ersten Schritt abgeschlossen hätten. Es ist, als versuche man, jede mögliche Route in einer Stadt zu kartieren, die ständig neue Straßen hinzufügt, schneller als man sie zeichnen kann.

Um dies anzugehen, nutzen Wissenschaftler einen cleveren Trick namens „Tensornetzwerke“. Stellen Sie sich einen Tensor als eine riesige, mehrdimensionale Tabelle vor. Anstatt zu versuchen, die gesamte Tabelle zu speichern, was unmöglich ist, zerlegen diese Methoden sie in kleinere, miteinander verbundene Stücke, wie ein Team von Arbeitern, die sich gegenseitig Notizen zuwerfen. Die bisher populärsten Teams waren in einer geraden Linie organisiert (ein sogenannter „Tensor-Train“) oder in einer Baumstruktur (genannt „Hierarchical Tucker“). Diese Teams sind großartig darin, die Daten klein zu halten, aber sie sind starr. Sie können nur in diesen spezifischen Formen arbeiten. Wenn das Problem, das Sie lösen wollen, von Natur aus zu einer anderen Form passt – wie einem Kreis, einer Schleife oder einem komplexen Netz – ist es, das Problem in eine gerade Linie oder einen Baum zu zwingen, als würde man versuchen, einen runden Steckpin in ein quadratisches Loch zu passen. Es funktioniert zwar, aber es verschwendet viel Platz und Energie.

Hier setzt eine neue Studie von Sarah Ellwein und Daniele Venturi von der University of California, Santa Cruz, an. Sie haben einen Weg erfunden, der es diesen Datenteams ermöglicht, in jeder beliebigen Form zu arbeiten, einschließlich Schleifen und komplexer Netze, ohne ihre Effizienz zu verlieren. Sie nennen ihre Methode „Graph Tensor Networks“ (GTN). In ihrer Arbeit zeigen sie, dass sie, indem sie die Daten in einem natürlicheren, kreisförmigen Muster fließen lassen, schwierige mathematische Probleme mit weit weniger Ressourcen lösen können als die alten Methoden. Sie testeten dies an einigen sehr kniffligen Gleichungen, darunter eine, die beschreibt, wie Teilchen sich bewegen und ausbreiten (die Fokker–Planck-Gleichung), und fanden heraus, dass ihr neuer „Graph“-Ansatz oft viel schneller war und deutlich weniger Speicher verbrauchte als die traditionellen linien- oder baumförmigen Ansätze, während er die Antworten ebenso genau lieferte.

Die Geschichte des formverändernden Puzzles

Stellen Sie sich vor, Sie versuchen, eine massive, komplizierte 3D-Skulptur aus Millionen kleiner Lego-Steine zu beschreiben. Wenn Sie versuchen, die Position jedes einzelnen Steins aufzulisten, wäre die Liste länger als das gesamte Internet. Das ist das Problem mit hochdimensionalen Daten. Um dies zu beheben, nutzen Wissenschaftler eine „Low-Rank“-Strategie: Anstatt jeden Stein einzeln aufzulisten, beschreiben sie die Skulptur als eine Reihe kleinerer, einfacherer Blöcke, die zusammenstecken.

Lange Zeit war die einzige Möglichkeit, diese Blöcke zusammenzustecken, eine gerade Linie (wie ein Zug) oder ein verzweigender Baum. Diese Formen sind leicht zu handhaben, aber sie sind nicht immer die beste Passform. Manchmal möchte die Datenstruktur eine Kreisform oder ein komplexes Netz bilden. Ein kreisförmiges Problem in eine gerade Linie zu zwingen, ist wie der Versuch, in einem Kreis zu gehen, während man eine lange, gerade Stange hält; man macht dadurch riesige, ineffiziente Schritte.

Ellwein und Venturi stellten eine einfache Frage: Was wäre, wenn wir die Blöcke in jeder beliebigen Form zusammenstecken könnten, solange wir eine Karte haben, wie sie verbunden sind?

Sie entwickelten einen neuen Algorithmus namens GTN-SVD. Betrachten Sie dies als einen universellen Übersetzer, der einen riesigen, unordentlichen Datenblock nehmen und ihn in ein Netzwerk kleinerer Teile zerlegen kann, die in einer von Ihnen gewählten Form angeordnet sind – sei es eine Linie, ein Ring, ein Stern oder ein seltsamer, wackeliger Klumpen. Der Schlüssel ist eine „Rang-Adjazenzmatrix“, was im Grunde nur eine Art Landkarte ist, die zeigt, welche Teile mit welchen verbunden sind. Wenn zwei Teile nicht verbunden sind, sagt die Karte „keine Verbindung“, und der Algorithmus weiß, dass er diese Verbindung ignorieren muss, was Platz spart.

Doch die Daten zu zerlegen, ist nur die halbe Miete. Um ein Problem zu lösen, das sich über die Zeit verändert (wie eine fließende Flüssigkeit), muss man ständig neue Informationen hinzufügen und dann das „Chaos aufräumen“, um die Daten klein zu halten. Hier wird die Arbeit der Autoren wirklich clever.

In den alten „gerade Linien“-Methoden war das Hinzufügen neuer Informationen einfach: Man steckte die neuen Blöcke einfach neben die alten. Aber in einem kreisförmigen oder netzartigen Netzwerk kann das Hinzufügen neuer Blöcke dazu führen, dass die Verbindungen sich verheddern und riesig werden, was das Ganze wieder in der Größe explodieren lässt. Die Autoren erkannten, dass, wenn das Netzwerk einen „rückverfolgbaren Pfad“ besitzt – eine Route, die jedes einzelne Stück genau einmal besucht, ohne in einer Schleife stecken zu bleiben –, sie das Netzwerk allein zum Zweck der „Aufräumphase“ wie einen Zug behandeln können.

Sie erfanden ein neues „Rounding“-Verfahren (Glättungsverfahren). Stellen Sie sich vor, Sie haben ein unordentliches Netz aus Schnüren. Wenn Sie an den Schnüren in einer bestimmten Reihenfolge ziehen (indem Sie dem rückverfolgbaren Pfad folgen), können Sie die Knoten festziehen und die losen Enden abschneiden, ohne das Netz zu zerstören. Ihre Methode macht genau das: Sie geht das Netzwerk ab, zieht die Verbindungen fest und schneidet die unnötigen Daten ab, wodurch die Größe klein und die Genauigkeit hoch bleibt.

Die Ergebnisse: Schlauer, schneller und schlanker

Um zu sehen, ob ihre Idee tatsächlich funktionierte, führten die Autoren Tests durch. Sie haben nicht nur geraten; sie simulierten reale Szenarien.

Zuerst versuchten sie, einige sehr komplexe, wackelige mathematische Funktionen zu approximieren. Sie verglichen ihre neue „Barbell“-Form (ein Graph, der wie zwei Kreise aussieht, die durch eine Brücke verbunden sind) mit den alten Linien- und Baummethoden. Die Ergebnisse waren beeindruckend. Um die gleiche Genauigkeit zu erreichen, benötigte die neue Graph-Methode 382-mal weniger „Freiheitsgrade“ (was nur eine schicke Bezeichnung für „Datenstücke“ ist) als die geradlinige Methode auf einem Genauigkeitsniveau und 498-mal weniger auf einem höheren Niveau. Auf gut Deutsch gesagt: Die neue Methode war hunderte Male effizienter darin, die gleiche Menge an Informationen zu speichern.

Als Nächstes widmeten sie sich einem berühmten Physikproblem: der Fokker–Planck-Gleichung. Diese Gleichung beschreibt, wie sich eine Wolke von Teilchen über die Zeit bewegt und ausbreitet, wie etwa Tinte, die in Wasser fällt. Sie simulierten dies in einem 4-dimensionalen Raum (was schwer zu visualisieren ist, aber denken Sie an eine hyperkomplexe Version eines Raumes).

Sie führten die Simulation über einen langen Zeitraum Schritt für Schritt durch.

• Im „Kein-Wind“-Szenario (wo Teilchen sich einfach zufällig bewegen/diffundieren), verbrauchte die neue Graph-Methode zu Beginn 166-mal weniger Speicher als die geradlinige Methode. Während die Simulation lief, blieb die Graph-Methode effizient, während die alte Methode zu kämpfen hatte. Die Graph-Methode schloss die gesamte Simulation in 1.460 Sekunden ab, während die geradlinige Methode 2.737 Sekunden benötigte. Das ist fast doppelt so schnell.
• Im „Windy“-Szenario (wo Teilchen durch einen komplexen Fluss gedrückt werden), verbrauchte die Graph-Methode immer noch mehr als 10-mal weniger Speicher als die geradlinige Methode. Der Zeitunterschied war sogar noch größer: Die Graph-Methode dauerte etwa 1,16 Sekunden pro Schritt, während die geradlinige Methode 13,6 Sekunden brauchte.

Die Autoren waren sorgfältig genug anzumerken, dass ihre Methode kein magisches Heilmittel ist, das alles perfekt löst. Im „Windy“-Test war die geradlinige Methode am Ende tatsächlich etwas genauer, obwohl sie viel langsamer war und wesentlich mehr Speicher verbrauchte. Die Autoren deuten an, dass die alten Methoden für manche Probleme immer noch besser sein könnten, aber für viele andere ist der neue Graph-Ansatz ein großer Gewinn.

Warum das wichtig ist

Die wichtigste Erkenntung ist, dass wir unsere Daten nicht mehr in eine gerade Linie zwingen müssen. Indem wir die Daten in Formen fließen lassen, die zum Problem passen (wie Schleifen oder Netze), können wir hochdimensionale Rätsel lösen, die zuvor zu teuer oder zu langsam zu bewältigen waren.

Die Autoren zeigen, dass wir durch die Nutzung dieser flexiblen Graphformen Antworten erhalten können, die genauso gut sind wie die der alten Methoden, aber mit einem Bruchteil der Computerleistung. Es ist, als würde man erkennen, dass man nicht immer eine lange, gewundene Straße bauen muss, um von Punkt A nach Punkt B zu gelangen; manchmal ist eine direkte Brücke oder ein kreisförmiger Pfad viel schneller und verbraucht weniger Asphalt. Dies eröffnet die Tür zur Simulation komplexerer Systeme in der Physik, Chemie und Technik, was potenziell helfen kann, alles zu verstehen – von der Bewegung von Medikamenten durch den Körper bis hin zur Entstehung von Sternen – ohne einen Supercomputer in der Größe einer Stadt zu benötigen.