- Les transformers et les LLM excellent dans la conversation, la compréhension d’images et l’autocomplétion de code, mais ont du mal à offrir des performances stables sur la planification multi-étapes et le raisonnement de haut niveau
- Cet article convertit les tâches de planification et leurs solutions optimales en séquences de tokens, et intègre aussi dans les données d’entraînement la trace d’exécution montrant comment A* résout le problème
- Searchformer commence par imiter le processus de recherche d’A*, puis est affiné pour produire des séquences de recherche plus courtes tout en conservant le plan optimal
- Dans les expériences sur Sokoban, les modèles de la famille Searchformer ont résolu 93,7 % des tâches de test, en utilisant en moyenne 26,8 % de étapes de recherche en moins qu’une implémentation de référence d’A*
- Les traces d’exécution alourdissent les séquences générées d’un facteur 10× à 100×, mais permettent malgré tout de générer plus souvent des plans optimaux sur des tâches inédites avec moins de séquences d’entraînement qu’un modèle plus grand entraîné uniquement sur les solutions
Ce que les transformers font bien, et les limites des tâches de planification
- Les architectures basées sur les transformers affichent de hautes performances sur de nombreuses tâches
- conversation de niveau humain
- compréhension d’images de haute qualité
- génération vidéo
- génération multimodale
- autocomplétion de code
- Des modèles comme les LLM, entraînés sur des données à l’échelle d’Internet, peuvent bien se généraliser à des cas d’usage réels
- Mais des limites subsistent encore sur les tâches de planification et de raisonnement
- les LLM montrent des lacunes sur les tâches de planification multi-étapes
- ils rencontrent aussi des difficultés sur le raisonnement de haut niveau
Les limites des prompts de raisonnement étape par étape
- Des approches récentes cherchent à améliorer les performances en poussant les transformers à générer des “pensées” intermédiaires avant de répondre
- Le prompt Chain-of-Thought (CoT) et Tree-of-thoughts (ToT) encouragent le modèle à “penser” par étapes
- Ces techniques sont souvent efficaces, mais peuvent aussi dégrader les performances pour des raisons comme le caractère self-enforcing
- Une méthode efficace sur un dataset peut échouer sur un autre
- c’est par exemple le cas lorsque le type de raisonnement requis change, comme entre raisonnement spatial et raisonnement mathématique
- La question de savoir comment amener les transformers et les LLM à planifier, décider en plusieurs étapes et raisonner de manière fiable reste un sujet de recherche très actif
Intégrer la dynamique de recherche d’A* dans les données d’entraînement
- Cette approche se concentre sur l’entraînement de transformers capables de résoudre plus robustement des tâches de planification complexes
- Le modèle est entraîné, comme un LLM, à prédire le mot suivant à partir d’une séquence de mots donnée
- Les expériences sont menées sur des datasets génératifs synthétiques utilisant un langage synthétique et un vocabulaire synthétique
- Les tâches de planification et leurs plans de solution optimaux sont représentés comme des séquences de mots appelées tokens
- Le processus de calcul exécuté par A* est enregistré sous forme de séquence de tokens de trace d’exécution
- la trace d’exécution constitue un dataset séquentiel contenant la dynamique de recherche d’A*
- à travers ces séquences enrichies par la recherche, le transformer est entraîné à générer des séquences de tokens encodant à la fois la dynamique de recherche d’A* et le plan optimal
Procédure d’entraînement de Searchformer
- Le modèle final, Searchformer, est construit en deux étapes
- d’abord, le transformer est entraîné à imiter le processus de recherche d’A*
- ensuite, il est affiné pour trouver un plan avec moins d’étapes de recherche tout en produisant le plan optimal
- Ce processus est appelé search dynamics bootstrapping
- L’objectif est d’obtenir un transformer capable de résoudre des tâches de planification complexes avec moins d’étapes de recherche que l’implémentation de référence d’A*
Expériences sur Sokoban et performances de généralisation
- Sur les puzzles Sokoban, les modèles de la famille Searchformer résolvent 93,7 % de l’ensemble des tâches de test
- Le nombre moyen d’étapes de recherche est inférieur de 26,8 % à celui de l’implémentation de référence d’A*
- Des expériences contrôlant la complexité des tâches, la taille du dataset et la taille du modèle confirment l’effet de l’ajout des traces d’exécution
- L’ajout de traces d’exécution dans les données d’entraînement augmente la longueur des séquences générées d’un facteur 10× à 100×
- Malgré cela, les performances augmentent sur un ensemble indépendant de tâches de test
- Les modèles search-augmented génèrent plus souvent des plans optimaux sur des tâches inédites, même avec 10 fois moins de séquences d’entraînement que des modèles solution-only plus grands
- les modèles search-augmented sont entraînés sur des données incluant la description de la tâche, la solution et la trace d’exécution
- les modèles solution-only sont entraînés sur des séquences ne contenant que la description de la tâche et sa solution
- Ce résultat montre que l’intégration de la dynamique de recherche d’A* dans l’entraînement des transformers peut améliorer les performances sur les tâches de planification
1 commentaires
Réactions sur Hacker News
Il y a aussi eu des recherches plus intéressantes sur l’usage de transformeurs pour la planification de mouvement robotique 0
Le problème consistant à déplacer un bras robotique d’un point A à un point B en évitant les collisions est très difficile, car il est de haute dimension et continu, et les méthodes de planification classiques demandent beaucoup de calcul pour des performances souvent médiocres
C’est aussi l’une des raisons pour lesquelles les mouvements des robots paraissent « peu naturels » et qu’ils peinent à accomplir correctement diverses tâches qu’on leur demande ; cette approche semble capable de planifier plus vite des trajectoires quasi optimales et paraît assez compétitive face aux autres méthodes
Avant d’aller vers cette direction de recherche, je me demande s’ils ont essayé l’algorithme J modifié*, une optimisation d’A* pour les graphes de jeu / la recherche de chemin
Pour les curieux, c’est dans Game AI Pro 2 0
Cet article teste à quel point les transformeurs prédisent bien les traces d’exécution, par exemple dans le cas d’un compilateur JIT, et si cela peut aider à améliorer les heuristiques dans des domaines comme la recherche de chemin
Cela dit, les transformeurs sont lents, donc je reste prudent
Les problèmes de planification sont déjà bien traités par des approches établies comme la recherche sur graphe, les solveurs SAT, la recherche opérationnelle ou Prolog
Le cœur du sujet consiste généralement à optimiser entre plusieurs alternatives possibles, et je ne suis pas certain que les transformeurs soient adaptés à cela
Le rôle des méthodes de type LLM semble plutôt être de traduire des descriptions en langage naturel en programmes exécutables, mais Prolog en est déjà assez proche, puisqu’il a été conçu à l’origine pour le traitement classique du langage naturel
La traduction automatique nécessitait autrefois un décodage grammatical complexe reposant sur la recherche, mais aujourd’hui on utilise des transformeurs avec un décodage bien plus simple et pratiquement sans recherche
On peut peut-être maintenant aller jusqu’à une structure pleinement récursive
L’idée serait d’utiliser les meilleurs modèles prédictifs actuels pour apprendre des heuristiques de neural architecture search (NAS) et trouver de nouveaux blocs de réseau neuronal meilleurs que transformer ou mamba
La singularité approche…
Si les jeux de type Sokoban vous intéressent, vous pouvez aussi regarder https://thinky.gg
Il y a Sokopath, une variante de Sokoban amusante, et une autre variante NP-difficile appelée Pathology, dont l’objectif est d’aller du point A au point B en un nombre minimal de pas
La communauté a essayé de créer plusieurs solveurs, mais dès que la grille dépasse 5x5 cela devient très difficile, et la communauté thinky a aussi trouvé, avec du simulated annealing, des niveaux intéressants avec un nombre maximal de pas très élevé
« 26,8 % d’étapes de recherche en moins que la recherche A* standard »
Donc, pour Sokoban, c’est juste un peu mieux qu’un A* loin de l’état de l’art (https://festival-solver.site/)
Je ne vois pas ce qu’il y a d’impressionnant dans cet article, ni pourquoi il est sur Hacker News
En revanche, s’il existe d’autres contraintes exploitables dans le domaine exploré, on peut faire mieux qu’A*
Par exemple, Jump Point Search exploite les propriétés de la recherche sur grille quand les déplacements sont limités à certaines formes
S’il était possible de créer un algorithme de recherche général qui exploite efficacement ces propriétés particulières du domaine sous-jacent de manière « automatique », sans analyse manuelle par un humain, ce serait utile
A* est proche d’une solution de base « naïve », et eux n’ont pas directement réfléchi à la conception algorithmique
Le fait qu’un simple transformeur encodeur-décodeur puisse faire ça est assez impressionnant
« Transformers have enabled tremendous progress in various application settings, such architectures still lag behind traditional symbolic planners for solving complex decision making tasks. In this work, we demonstrate how to train Transformers to solve complex planning tasks ... »
Cet article est intéressant comme exemple d’usage des transformeurs pour la prise de décision, et le fait qu’ils soient au niveau d’A* ou non ne m’intéresse pas particulièrement pour l’instant
Bien sûr, il existe une version forte et une version faible de cette hypothèse, et la version forte n’est sans doute pas vraie, mais cela reste une nouvelle importante si l’on a l’impression qu’on se rapproche de « l’unique vraie manière » dont la nature apprend à faire les choses
Si les transformeurs peuvent planifier, cela pourrait vouloir dire qu’il ne manque à l’intelligence artificielle générale qu’une meilleure éducation
Il faut aussi de l’apprentissage en ligne, et plusieurs autres couches encore
Pour les personnes qui apprennent mieux à l’oral, il existe un résumé de cet article au format audiobook
https://player.oration.app/09fefe41-f2a7-4257-a25e-30e479b30d6f
Je suis très optimiste sur l’usage d’heuristiques apprises pour des algorithmes discrets comme A*, Focal search ou diverses familles de programmation linéaire en nombres entiers
Dans la plupart des bibliothèques modernes d’optimisation discrète comme CPLEX, la différence de performance s’explique en grande partie par les heuristiques et le tuning
Remplacer une routine de recherche optimale bien comprise par une approche end-to-end apprise me convainc moins, mais c’est peut-être une inquiétude inutile
Cela dit, les auteurs semblent avoir laissé passer cette opportunité
Je devrais peut-être essayer de résoudre le morpion avec un transformeur et aller demander de l’argent à des VC
Dans quelques années, tout le monde écrira peut-être sur à quel point le vrai code est plus efficace que l’IA ;)
Apprendre des heuristiques admissibles permet de conserver les performances dans le pire des cas, et cela a toujours été le critère de référence pour ce type d’algorithmes
Il n’est pas rare du tout de chercher des solutions plus rapides en moyenne ou sur les cas p99, mais qui ne fournissent pas de garantie dans le pire des cas
Je me demande si quelqu’un tient une liste des algorithmes classiques ou des problèmes NP-complets qui sont mieux traités grâce au deep learning