Bellman-Ford pousse les réseaux neuronaux cinq fois plus loin

Des algorithmes classiques Les algorithmes de tri, de recherche de plus court chemin et de programmation dynamique possèdent des propriétés difficiles à reproduire avec les réseaux neuronaux profonds. Ils peuvent être prouvés corrects dans certaines conditions. Ils offrent souvent des garanties sur le temps ou la mémoire nécessaires. Ils généralisent aussi à des entrées plus grandes ou différentes des exemples observés. Leur pseudo-code facilite enfin l’interprétation et la recomposition par sous-programmes. Ces caractéristiques répondent à plusieurs limites des réseaux neuronaux. Ces modèles garantissent rarement leur précision. Ils peuvent échouer sur des données hors distribution. Leurs boîtes noires compliquent également l’analyse des erreurs composées.

Un benchmark pour le raisonnement L’exécution d’algorithmes fournit un cadre mesurable pour étudier les capacités algorithmiques des réseaux. Les chercheurs peuvent générer une quantité arbitraire d’entrées. Les tâches imposent aussi des manipulations complexes de données. Leur fonction cible reste clairement définie, ce qui facilite l’analyse de l’interprétabilité. Des travaux menés à partir de 2019 ont étudié cette question avec des réseaux neuronaux graphiques, ou GNN. Une équipe du MIT a ensuite relié l’alignement algorithmique à la complexité d’échantillonnage. Selon son théorème principal, un meilleur alignement algorithmique favorise une meilleure généralisation.

Les GNN suivent Bellman-Ford

Le chemin le plus court Bellman-Ford illustre la manière dont un GNN peut suivre la structure d’un algorithme classique. L’algorithme conserve une distance estimée pour chaque nœud du graphe. À chaque étape, il propose une mise à jour pour chaque voisin. Cette proposition combine la distance connue et le poids de l’arête parcourue. L’algorithme conserve ensuite la meilleure proposition. Dans un GNN, les distances correspondent aux caractéristiques des nœuds. Le calcul du message ajoute le poids de l’arête à une distance. L’agrégation sélectionne ensuite une valeur optimale parmi les voisins. Cette décomposition rapproche le réseau du flux de données algorithmique.

La programmation dynamique Bellman-Ford appartient à la famille de la programmation dynamique. Cette méthode divise un problème en sous-problèmes, puis recombine leurs solutions. Les GNN présentent une affinité algorithmique avec cette structure relationnelle. Des travaux du MIT ont évalué cette hypothèse sur plusieurs benchmarks d’exécution de programmes dynamiques. Les modèles relationnels, comme les GNN, ont dépassé des architectures dotées de biais inductifs plus faibles. Une analyse empirique consacrée à l’exécution d’algorithmes de graphes a toutefois montré qu’un GNN expressif ne suffisait pas. Le modèle pouvait encore mémoriser les caractéristiques des données d’entraînement et éviter la procédure visée.

Trois choix renforcent la généralisation

Un processeur partagé Les architectures traditionnelles empilent des couches dont les paramètres diffèrent. Cette organisation limite le nombre d’étapes disponibles lorsque la taille des entrées augmente. Les chercheurs ont donc utilisé un schéma encodeur-processeur-décodeur. Un processeur GNN partagé est itéré pendant un nombre variable d’étapes. Ce nombre peut changer pendant l’entraînement et l’inférence. Cette conception correspond à la structure de nombreux algorithmes itératifs. Les chercheurs ont également utilisé une agrégation par maximum. Ce choix reflète l’optimisation locale des algorithmes de plus court chemin. Les modèles ainsi conçus ont généralisé à des entrées cinq fois plus grandes pendant les tests.

Une supervision étape par étape Les chercheurs ont ajouté des signaux d’apprentissage intermédiaires afin d’aligner le réseau avec les invariants de l’algorithme. Pour Bellman-Ford, après k itérations, le modèle doit retrouver les plus courts chemins couvrant au plus k arêtes. Cette contrainte fournit une cible à chaque étape du calcul. Elle complète l’objectif habituel, qui consiste seulement à produire une sortie finale. Les auteurs relient cette approche à des travaux récents sur la conception de grands modèles de langage. Leur programme couvre aussi les algorithmes de séquence, les structures de données à pointeurs et la mémoire auxiliaire persistante.

Une théorie en évolution Les machines de Turing neuronales et les ordinateurs neuronaux différentiables avaient déjà tenté d’intégrer des composants informatiques dans des réseaux. La machine de Turing neuronale a notamment introduit une forme précoce d’attention fondée sur le contenu, trois ans avant les Transformers. Ces architectures ont toutefois été peu utilisées en pratique, selon l’analyse présentée. Leur conception combinait plusieurs composants différentiables et rendait le débogage difficile. Les travaux récents cherchent plutôt à tester chaque bloc séparément. La théorie de l’alignement algorithmique s’est ensuite affinée avec l’alignement algorithmique linéaire. Des recherches explorent aussi la causalité, la théorie des catégories et le calcul asynchrone. Lire l’article complet sur The Gradient. Les travaux associés sont regroupés sur la plateforme AlgoReasoning et dans le dépôt CLRS de DeepMind.