Bellman-Ford pousse les GNN cinq fois plus loin

Réseaux neuronaux Depuis 2019, des chercheurs étudient la capacité des réseaux neuronaux à exécuter des algorithmes classiques. Ces travaux portent notamment sur la recherche de plus courts chemins, le tri et la programmation dynamique. L’objectif consiste à reproduire, avec des réseaux profonds, des calculs habituellement enseignés en informatique. Les algorithmes classiques présentent plusieurs propriétés recherchées en IA. Ils peuvent être prouvés corrects et fournir des garanties sur le temps ou la mémoire nécessaires. Ils généralisent aussi à des entrées plus grandes ou différentes. Leur code reste interprétable et composable. Ces caractéristiques répondent directement aux limites fréquemment observées dans les réseaux neuronaux profonds.

Exécution algorithmique L’exécution d’algorithmes fournit un banc d’essai contrôlé pour les modèles d’apprentissage. Les chercheurs peuvent générer une quantité arbitraire d’entrées. Les tâches imposent aussi des manipulations complexes de données et disposent d’une fonction cible clairement définie. Une équipe du MIT a étudié ce qui rend une architecture meilleure pour certaines tâches algorithmiques. Son travail relie l’alignement algorithmique à la complexité d’échantillonnage, soit le nombre d’exemples nécessaires pour réduire l’erreur de validation sous un seuil donné. Cette théorie indique qu’une architecture plus proche de la structure d’un algorithme peut mieux généraliser. Les réseaux de neurones graphiques occupent une place centrale dans cette approche.

Les GNN suivent Bellman-Ford

Chemins les plus courts Bellman-Ford sert à illustrer cette correspondance entre algorithme et réseau graphique. L’algorithme conserve une estimation de la distance entre chaque nœud et une source. À chaque étape, il propose une nouvelle distance pour chaque voisin. Cette proposition additionne la distance connue et le poids de l’arête traversée. Le réseau neuronal graphique peut reproduire ce flux de données. Les distances deviennent des caractéristiques de nœuds. L’ajout du poids d’une arête correspond à la fonction de message. La sélection de la meilleure proposition correspond à une agrégation insensible à l’ordre des voisins. Bellman-Ford relève de la programmation dynamique, qui décompose un problème en sous-problèmes recombinés.

Généralisation mesurée Les expériences montrent toutefois qu’un réseau graphique expressif ne suffit pas automatiquement. Le modèle peut mémoriser les caractéristiques des entrées d’entraînement et contourner la procédure algorithmique visée. Pour limiter ce comportement, les chercheurs ont retenu trois choix d’architecture et d’apprentissage. Le premier utilise un processeur graphique partagé, répété pendant un nombre variable d’étapes. Le deuxième privilégie une agrégation par maximum, adaptée à l’optimisation locale des problèmes de chemins. Le troisième fournit une supervision à chaque étape. Dans Bellman-Ford, après k itérations, le modèle doit retrouver les plus courts chemins comportant au plus k arêtes. Ces choix ont permis de tester des entrées jusqu’à cinq fois plus grandes.

Trois choix renforcent l’alignement

Mémoire différentiable L’alignement algorithmique s’inscrit dans une histoire plus longue. Les Neural Turing Machines et les Differentiable Neural Computers cherchaient déjà à intégrer des composants de calcul différentiables. La Neural Turing Machine a notamment introduit une forme précoce d’attention fondée sur le contenu, trois ans avant les Transformers. Ces architectures sont toutefois rarement utilisées en pratique selon l’analyse présentée. Leur conception pouvait réunir trop de composants différentiables sans méthode claire pour les composer. Elle rendait aussi le débogage difficile lorsqu’une nouvelle tâche produisait peu de signal utile. Les travaux récents reprennent cette ambition avec une construction plus progressive, en évaluant séparément les blocs adaptés à chaque algorithme.

Familles spécialisées Cette démarche a produit des réseaux spécialisés pour plusieurs types de calcul. Les travaux cités couvrent des algorithmes séquentiels linéarithmiques, des algorithmes itératifs, des structures de données fondées sur des pointeurs et une mémoire auxiliaire persistante. La théorie a également évolué après les résultats de Neural Execution of Graph Algorithms. Le concept d’alignement algorithmique linéaire apporte une justification théorique à l’agrégation par maximum. D’autres recherches relient désormais son étude au raisonnement causal, à la théorie des catégories et au calcul asynchrone. Les travaux et jeux de données associés sont accessibles via The Gradient, CLRS de DeepMind et le site Algorithmic Reasoning.