Computing with traceable tensor networks

Stel je voor dat je probeert een puzzel op te lossen waarbij elke keer dat je een nieuw stukje toevoegt, het aantal manieren om het geheel te rangschikken explodeert. Dit is de nachtmerrie van "hoogdimensionale" problemen in wetenschap en techniek. Of je nu modelleert hoe warmte zich door een complex materiaal verspreidt, de beweging van deeltjes in een vloeistof voorspelt, of het gedrag van een kwantumsysteem simuleert, de wiskunde wordt snel een puinhoop. Als een probleem slechts een paar variabelen heeft, kun je het op een laptop oplossen. Maar als het tien, twintig of een honderd variabelen heeft, wordt de hoeveelheid data die je moet opslaan zo groot dat zelfs de grootste supercomputers ter wereld zonder geheugen zouden komen zitten voordat ze de eerste stap hebben voltooid. Het is alsoast proberen elke mogelijke route in een stad in kaart te brengen die sneller nieuwe straten toevoegt dan jij ze kunt tekenen.

Om dit aan te pakken, gebruiken wetenschappers een slimme truc genaamd "tensornetwerken". Denk aan een tensor als een gigantische, meerdimensionale spreadsheet. In plaats van te proberen de hele spreadsheet op te slaan, wat onmogelijk is, breken deze methoden het af in kleinere, onderling verbonden brokken, zoals een team van werkers die elkaar briefjes doorgeven. De populairste teams tot nu toe waren georganiseerd in een rechte lijn (een "Tensor Train") of in een boomstructuur (de "Hierarchical Tucker"). Deze teams zijn goed in het klein houden van de data, maar ze zijn rigide. Ze kunnen alleen in die specifieke vormen werken. Als het probleem dat je probeert op te lossen van nature een andere vorm heeft—zoals een cirkel, een lus of een complex web—dan is het dwingen ervan in een rechte lijn of een boomvorm alsof je een rond gat probeert te passen in een vierkant gat. Het werkt wel, maar het verspilt veel ruimte en energie.

Dit is waar een nieuwe studie van Sarah Ellwein en Daniele Venturi van de University of California, Santa Cruz, om de hoek komt kijken. Zij hebben een manier uitgevonden waarmee deze datateams in elke vorm kunnen werken, inclusief lussen en complexe webben, zonder hun efficiëntie te verliezen. Ze noemen hun methode "Graph Tensor Networks" (GTN). In hun paper laten ze zien dat door de data in een natuurlijker, circulair patroon te laten stromen, ze moeilijke wiskundige problemen met veel minder middelen kunnen oplossen dan de oude methoden. Ze testten dit op enkele zeer lastige vergelijkingen, waaronder één die beschrijft hoe deeltjes bewegen en zich verspreiden (de Fokker–Planck-vergelijking), en ontdekten dat hun nieuwe "grafiek"-aanpak vaak veel sneller was en aanzienlijk minder geheugen gebruikte dan de traditionele rechte lijn- of boomvormige benaderingen, terwijl de antwoorden net zo nauwkeurig bleven.

Het Verhaal van de Vormveranderende Puzzel

Stel je voor dat je een enorme, ingewikkelde 3D-sculptuur probeert te beschrijven die gemaakt is van miljoenen kleine Lego-steentjes. Als je probeert de positie van elk afzonderlijk steentje op te sommen, zou de lijst langer zijn dan het hele internet. Dat is het probleem met hoogdimensionale data. Om dit op te lossen, gebruiken wetenschappers een "low-rank" strategie: in plaats van elk steentje op te sommen, beschrijven ze de sculptuur als een reeks kleinere, eenvoudigere blokken die in elkaar klikken.

Een lange tijd was de enige manier om deze blokken aan elkaar te klikken in een rechte lijn (zoals een trein) of een vertakkende boom. Deze vormen zijn gemakkelijk te beheren, maar ze zijn niet altijd de beste pasvorm. Soms wil de data een cirkel of een complex web vormen. Een circulair probleem in een rechte lijn dwingen is als proberen in een cirkel te lopen terwijl je een lange, rechte paal vasthoudt; je eindigt met enorme, inefficiënte stappen te zetten.

Ellwein en Venturi stelden een eenvoudige vraag: Wat als we de blokken in elke gewenste vorm kunnen laten vastklikken, zolang we maar een kaart hebben van hoe ze verbonden zijn?

Ze ontwikkelden een nieuw algoritme genaamd GTN-SVD. Zie dit als een universele vertaler die een gigantisch, rommelig blok data kan nemen en het kan afbreken in een netwerk van kleinere stukjes, gerangschikt in een vorm naar keuze—of dat nu een lijn, een ring, een ster of een vreemd, golvend klodder is. De sleutel is een "rank adjacency matrix", wat gewoon een chique manier is om een kaart te tekenen van welke stukken met welke verbonden zijn. Als twee stukken niet verbonden zijn, zegt de kaart "geen link", en weet het algoritme dat deze verbinding te negeren, wat ruimte bespaart.

Maar het afbreken van de data is slechts de helft van de strijd. Om een probleem op te lossen dat in de loop van de tijd verandert (zoals een stromende vloeistof), moet je voortdurend nieuwe informatie toevoegen en vervolgens de "rommel opruimen" om de data klein te houden. Dit is waar het paper echt slim wordt.

In de oude "rechte lijn"-methoden was het toevoegen van nieuwe informatie gemakkelijk: je plakte de nieuwe blokken gewoon naast de oude. Maar in een circulair of webachtig netwerk kan het toevoegen van nieuwe blokken ervoor zorgen dat de verbindingen verstrikt raken en enorm worden, waardoor het geheel weer in omvang explodeert. De auteurs realiseerden zich dat als het netwerk een "traceerbaar pad" heeft—een route die elk enkel blok precies één keer bezoekt zonder in een lus te blijven hangen—ze het netwerk als een trein kunnen behanden specifiek voor het doel van het opruimen.

Ze hebben een nieuwe "rounding"-procedure uitgevonden. Stel je voor dat je een rommelig web van touwen hebt. Als je aan de touwen trekt in een specifieke volgorde (volgens dat traceerbare pad), kun je de knopen strak trekken en de losse uiteinden afknippen zonder het web te verbreken. Hun methode doet precies dit: het scant door het netwerk, trekt de verbindingen strak en snijdt de overbodige data af, waardoor de omvang klein blijft en de nauwkeurigheid hoog.

De Resultaten: Slimmer, Sneller en Slanker

Om te zien of hun idee daadwerkelijk werkte, hebben de auteurs tests uitgevoerd. Ze hebben niet alleen geraden; ze hebben realistische scenario's gesimuleerd.

Eerst probeerden ze enkele zeer complexe, golvende wiskundige functies te benaderen. Ze vergeleken hun nieuwe "Barbell"-vorm (een graaf die eruitziet als twee lussen die verbonden zijn door een brug) met de oude rechte lijn- en boommethoden. De resultaten waren opmerkelijk. Om dezelfde nauwkeurigheid te bereiken, had de nieuwe grafiekmethode 382 keer minder "degrees of freedom" (wat gewoon een chique manier is om te zeggen: "stukjes data") nodig dan de rechte lijnmethode bij één precisieniveau, en 498 keer minder bij een hoger precisieniveau. In gewone mensentaal: de nieuwe methode was honderden keren efficiënter in het opslaan van dezelfde hoeveelheid informatie.

Vervolgens pakten ze een beroemd natuurkundig probleem aan: de Fokker–Planck-vergelijking. Deze vergelijking beschrijft hoe een wolk van deeltjes beweegt en zich in de loop van de tijd verspreidt, zoals inkt die in water valt. Ze simuleerden dit in een 4-dimensionale ruimte (wat moeilijk te visualiseren is, maar denk aan een hypercomplexe versie van een kamer).

Ze draaiden de simulatie gedurende een lange tijd, stap voor stap.

• In het scenario "zonder wind" (waarbij deeltjes willekeurig diffunderen), gebruikte de nieuwe grafiekmethode 166 keer minder geheugen dan de rechte lijnmethode aan het begin. Terwijl de simulatie liep, bleef de grafiekmethode efficiënt, terwijl de oude methode moeite kreeg. De grafiekmethode voltooide de hele simulatie in 1.460 seconden, terwijl de rechte lijnmethode 2.737 seconden duurde. Dat is bijna twee keer zo snel.
• In het "windige" scenario (waarbij deeltjes worden geduwd door een complexe stroming), gebruikte de grafiekmethode nog steeds meer dan 10 keer minder geheugen dan de rechte lijnmethode. Het tijdsverschil was nog groter: de grafiekmethode deed er ongeveer 1,16 seconde per stap over, terwijl de rechte lijnmethode 13,6 seconden nodig had.

De auteurs merkten er zorgvuldig bij op dat hun methode geen wondermiddel is dat alles perfect oplost. In de "windy" test was de rechte lijnmethode uiteindelijk iets nauwkeuriger, hoewel deze veel langzamer was en veel meer geheugen gebruikte. De auteurs suggereren dat voor sommige problemen de oude methoden nog steeds beter kunnen zijn, maar voor veel andere problemen is de nieuwe grafiek-aanpak een enorme winst.

Waarom Dit Belangrijk Is

De belangrijkste les is dat we onze data niet langer gedwongen in een rechte lijn hoeven te persen. Door de data te laten stromen in vormen die passen bij het probleem—zoals lussen of webben—kunnen we hoogdimensionale puzzels oplossen die voorheen te duur of te traag waren om te verwerken.

De auteurs laten zien dat we door deze flexibele grafiekvormen te gebruiken, antwoorden kunnen krijgen die net zo goed zijn als de oude methoden, maar met een fractie van de computerkracht. Het is alsof je beseft dat je geen lange, kronkelende weg hoeft aan te leggen om van punt A naar punt B te komen; soms is een directe brug of een cirkelvormig pad veel sneller en gebruikt het veel minder asfalt. Dit opent de deur naar het simuleren van complexere systemen in de natuurkunde, chemie en techniek, wat ons potentieel kan helpen om alles te begrijpen van hoe medicijnen door het lichaam bewegen tot hoe sterren worden geboren, zonder dat we een supercomputer nodig hebben ter grootte van een stad.