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

Des réseaux graphiques apprennent à exécuter des algorithmes classiques, selon un article consacré au raisonnement algorithmique neuronal. L’étude porte notamment sur la recherche de plus courts chemins, le tri et la programmation dynamique. Elle examine aussi comment des réseaux de neurones profonds peuvent reproduire ces opérations. Les algorithmes classiques offrent plusieurs propriétés recherchées en IA. Ils peuvent être prouvés corrects et leurs besoins en temps ou en mémoire peuvent être encadrés. Ils généralisent également à des entrées plus grandes ou différentes. Leur représentation en pseudo-code facilite enfin l’interprétation et la recomposition par sous-programmes. Ces caractéristiques contrastent avec les faiblesses souvent observées dans les réseaux neuronaux profonds.

Le raisonnement algorithmique est étudié comme un moyen de mieux généraliser hors distribution. L’article relie cette piste aux systèmes capables d’expliquer ou d’enseigner une notion. Il pose une question centrale : un réseau peut-il apprendre à exécuter un algorithme classique ? Cette tâche constitue un banc d’essai contrôlé. Les chercheurs peuvent générer autant d’entrées que nécessaire. La fonction cible est clairement définie, ce qui facilite l’analyse de l’interprétabilité. Les opérations demandent aussi des manipulations complexes de données. En 2019, l’auteur et ses collaborateurs considéraient cette approche comme un banc d’essai particulièrement propre. Le sujet est ensuite devenu un domaine de recherche actif.

Les GNN suivent Bellman-Ford

Le modèle de graphe s’aligne sur la structure de Bellman-Ford pour rechercher un plus court chemin. Cet algorithme conserve une distance estimée pour chaque nœud. À chaque étape, chaque voisin propose une nouvelle distance. Le réseau de neurones graphique peut représenter ces distances dans les caractéristiques des nœuds. Sa fonction de message correspond à l’ajout du poids d’une arête. Son agrégation sélectionne ensuite la meilleure proposition parmi les voisins. Cette correspondance illustre l’alignement algorithmique. Une équipe du MIT a établi un cadre mathématique reliant cet alignement à la complexité d’échantillonnage. Des bancs d’essai de programmation dynamique ont ensuite favorisé les modèles relationnels, notamment les GNN.

Les résultats expérimentaux montrent toutefois que l’alignement ne suffit pas à garantir une bonne généralisation. Un GNN expressif peut encore mémoriser les caractéristiques des données d’entraînement. Il peut alors employer des raccourcis plutôt que reproduire la procédure visée. L’approche décrite introduit trois choix de conception. Un processeur GNN partagé est répété pendant un nombre variable d’étapes. Cette organisation encode, traite et décode les données. L’agrégation maximale est utilisée pour les problèmes de plus courts chemins. Enfin, une supervision est fournie à chaque étape. Pour Bellman-Ford, le modèle doit alors récupérer les chemins de longueur maximale donnée après chaque nombre d’itérations. Ces choix permettent de tester des entrées jusqu’à cinq fois plus grandes.

Trois choix renforcent l’alignement

La méthode s’inscrit dans une histoire plus longue de conception inspirée par l’informatique. Les machines de Turing neuronales et les ordinateurs neuronaux différentiables avaient déjà introduit des composants différentiables liés à la mémoire. L’article estime toutefois que ces architectures étaient difficiles à composer et à déboguer. L’alignement algorithmique propose plutôt d’étudier chaque bloc séparément. Les travaux cités couvrent des algorithmes séquentiels en temps quasi linéaire, des algorithmes itératifs, des structures de données à pointeurs et une mémoire auxiliaire persistante. La théorie évolue également. Des recherches récentes relient l’alignement au raisonnement causal, à la théorie des catégories et à l’analyse du calcul asynchrone. Lire l’article original. Voir les tâches CLRS de DeepMind.