Computing with traceable tensor networks

Imaginez que vous essayez de résoudre un puzzle où, chaque fois que vous ajoutez une nouvelle pièce, le nombre de façons possibles d'organiser l'ensemble explose. C'est le cauchemar des problèmes à « haute dimensionnalité » en science et en ingénierie. Que vous modélisiez la façon dont la chaleur se propage à travers un matériau complexe, que vous prédisiez le mouvement de particules dans un fluide ou que vous simuliez le comportement d'un système quantique, les mathématiques deviennent vite complexes. Si un problème n'a que quelques variables, on peut le résoudre sur un ordinateur portable. Mais s'il en possède dix, vingt ou cent, la quantité de données que vous devez stocker devient si énorme que même les plus gros supercalculateurs du monde tomberaient à court de mémoire avant même d'avoir terminé la première étape. C'est comme essayer de cartographier tous les itinéraires possibles dans une ville qui ajoute de nouvelles rues plus vite que vous ne pouvez les dessiner.

Pour surmonter cela, les scientifiques utilisent une astuce ingénieuse appelée « réseaux de tenseurs ». Considérez un tenseur comme un immense tableur multidimensionnel. Au lieu d'essayer de stocker l'intégralité du tableur, ce qui est impossible, ces méthodes le décomposent en morceaux plus petits et interconnectés, comme une équipe de travailleurs qui se passent des notes. Les équipes les plus populaires jusqu'à présent ont été organisées en ligne droite (appelées « Tensor Train » ou train de tenseurs) ou en forme d'arbre (appelées « Hierarchical Tucker »). Ces équipes sont excellentes pour garder les données compactes, mais elles sont rigides. Elles ne peuvent travailler que dans ces formes spécifiques. Si le problème que vous essayez de résoudre correspond naturellement à une autre forme — comme un cercle, une boucle ou une toile complexe — forcer ce dernier dans une ligne droite ou un arbre revient à essayer de faire entrer une cheville ronde dans un trou carré. Cela fonctionne, mais cela gaspille beaucoup d'espace et d'énergie.

C'est ici qu'intervient une nouvelle étude de Sarah Ellwein et Daniele Venturi de l'Université de Californie à Santa Cruz. Ils ont inventé une façon de permettre à ces équipes de données de travailler dans n'importe quelle forme, y compris des boucles et des toiles complexes, sans perdre leur efficacité. Ils appellent leur méthode les « Réseaux de Tenseurs sur Graphes » (Graph Tensor Networks ou GTN). Dans leur article, ils montrent qu'en permettant aux données de circuler selon un schéma plus naturel, circulaire, ils peuvent résoudre des problèmes mathématiques difficiles avec beaucoup moins de ressources que les anciennes méthodes. Ils ont testé cela sur des équations très complexes, notamment une qui décrit comment les particules se déplacent et se propagent (l'équation de Fokker–Planck), et ont constaté que leur nouvelle approche par « graphe » était souvent beaucoup plus rapide et utilisait nettement moins de mémoire que les approches traditionnelles en ligne droite ou en arbre, tout en conservant la même précision.

L'histoire du puzzle changeur de forme

Imaginez que vous essayiez de décrire une sculpture 3D massive et complexe faite de millions de petites briques Lego. Si vous essayez de lister la position de chaque brique, la liste serait plus longue que l'internet entier. C'est le problème des données de haute dimensionnalité. Pour y remédier, les scientifiques utilisent une stratégie de « bas rang » : au lieu de lister chaque brique, ils décrivent la sculpture comme un ensemble de blocs plus petits et plus simples qui s'emboîtent.

Pendant longtemps, la seule façon d'emboîter ces blocs était en ligne droite (comme un train) ou en arbre ramifié. Ces formes sont faciles à gérer, mais elles ne sont pas toujours les mieux adaptées. Parfois, les données veulent former un cercle ou une toile complexe. Forcer un problème circulaire dans une ligne droite, c'est comme essayer de marcher en cercle en tenant un long poteau droit ; on finit par faire des pas énormes et inefficaces.

Ellwein et Venturi ont posé une question simple : Et si nous pouvions laisser les blocs s'emboîter dans n'importe quelle forme, tant que nous avons une carte de leurs connexions ?

Ils ont développé un nouvel algorithme appelé GTN-SVD. Voyez cela comme un traducteur universel capable de prendre un bloc de données géant et désordonné et de le décomposer en un réseau de pièces plus petites disposées selon la forme de votre choix — que ce soit une ligne, un anneau, une étoile ou une forme étrange et ondulante. La clé est une « matrice d'adjacence de rang », qui est simplement une façon sophistiquée de dessiner une carte indiquant quels morceaux sont connectés à quels autres. Si deux pièces ne sont pas connectées, la carte indique « pas de lien », et l'algorithme sait qu'il doit ignorer cette connexion, économisant ainsi de l'espace.

Mais décomposer les données n'est que la moitié de la bataille. Pour résoudre un problème qui évolue dans le temps (comme un fluide qui coule), il faut constamment ajouter de nouvelles informations, puis « nettoyer » le désordre pour garder les données compactes. C'est là que l'article devient vraiment ingénieux.

Dans les anciennes méthodes en « ligne droite », ajouter de nouvelles informations était facile : il suffisait de coller les nouveaux blocs à côté des anciens. Mais dans un réseau circulaire ou en forme de toile, ajouter de nouveaux blocs peut provoquer un enchevêtrement des connexions, les rendant gigantesques et faisant exploser la taille de l'ensemble. Les auteurs ont réalisé que si le réseau possède un « chemin traçable » — un itinéraire qui visite chaque bloc exactement une fois sans rester bloqué dans une boucle — ils pouvaient traiter le réseau comme un train juste pour le but de nettoyage.

Ils ont inventé une nouvelle procédure de « lissage » (rounding). Imaginez que vous avez un réseau de cordes désordonné. Si vous tirez sur les cordes dans un ordre spécifique (en suivant ce chemin traçable), vous pouvez resserrer les nœuds et couper les extrémités lâches sans briser la toile. Leur méthode fait exactement cela : elle parcourt le réseau, resserre les connexions et coupe les données inutiles, maintenant la taille réduite et la précision élevée.

Les résultats : Plus intelligent, plus rapide et plus léger

Pour voir si leur idée fonctionnait réellement, les auteurs ont effectué des tests. Ils n'ont pas seulement deviné ; ils ont simulé des scénarios réels.

D'abord, ils ont tenté d'approximer des fonctions mathématiques très complexes et sinueuses. Ils ont comparé leur nouvelle forme « Barbell » (un graphe qui ressemble à deux boucles reliées par un pont) par rapport aux anciennes méthodes en ligne droite et en arbre. Les résultats sont frappants. Pour obtenir le même niveau de précision, la nouvelle méthode de graphe avait besoin de 382 fois moins de « degrés de liberté » (ce qui est une façon élégante de dire « morceaux de données ») que la méthode en ligne droite à un certain niveau de précision, et 498 fois moins à un niveau de précision supérieur. En langage clair : la nouvelle méthode était des centaines de fois plus efficace pour stocker la même quantité d'informations.

Ensuite, ils se sont attaqués à un célèbre problème de physique : l'équation de Fokker–Planck. Cette équation décrit comment un nuage de particules se déplace et se propage au fil du temps, comme de l'encre tombant dans l'eau. Ils ont simulé cela dans un espace à 4 dimensions (ce qui est difficile à visualiser, mais imaginez une version hyper-complexe d'une pièce).

Ils ont lancé la simulation sur une longue période, étape par étape.

• Dans le scénario « sans vent » (où les particules diffusent de manière aléatoire), la nouvelle méthode de graphe utilisait 166 fois moins de mémoire que la méthode en ligne droite au début. À mesure que la simulation progressait, la méthode de graphe restait efficace, tandis que l'ancienne méthode peinait. La méthode de graphe a terminé toute la simulation en 1 460 secondes, alors que la méthode en ligne droite a pris 2 737 secondes. C'est presque deux fois plus rapide.
• Dans le scénario « venteux » (où les particules sont poussées par un flux complexe), la méthode de graphe utilisait toujours plus de 10 fois moins de mémoire que la méthode en ligne droite. La différence de temps était encore plus grande : la méthode de graphe prenait environ 1,16 seconde par étape, tandis que la méthode en ligne droite prenait 13,6 secondes.

Les auteurs ont pris soin de noter que leur méthode n'est pas un remède miracle qui résout tout parfaitement. Dans le test « venteux », la méthode en ligne droite était en fait légèrement plus précise à la fin, bien qu'elle soit beaucoup plus lente et utilise beaucoup plus de mémoire. Les auteurs suggèrent que pour certains problèmes, les anciennes méthodes pourraient encore être meilleures, mais pour beaucoup d'autres, la nouvelle approche par graphe est une victoire majeure.

Pourquoi cela importe

L'idée principale est que nous n'avons plus besoin de forcer nos données dans une ligne droite. En laissant les données circuler dans des formes qui correspondent au problème — comme des boucles ou des toiles — nous pouvons résoudre des puzzles de haute dimension qui étaient auparavant trop coûteux ou trop lents à traiter.

Les auteurs démontrent qu'en utilisant ces formes de graphes flexibles, nous pouvons obtenir des réponses aussi bonnes que les anciennes méthodes, mais avec une fraction de la puissance informatique. C'est comme réaliser que vous n'avez pas besoin de construire une route longue et sinueuse pour aller d'un point A à un point B ; parfois, un pont direct ou un chemin circulaire est beaucoup plus rapide et utilise moins d'asphalte. Cela ouvre la porte à la simulation de systèmes plus complexes en physique, en chimie et en ingénierie, aidant potentiellement à comprendre tout, de la façon dont les médicaments circulent dans le corps à la naissance des étoiles, sans avoir besoin d'un supercalculateur de la taille d'une ville.