La recherche en faisceau est un algorithme de recherche heuristique utilisé en informatique pour explorer un graphe en développant le nœud le plus prometteur dans un ensemble limité. Il s'agit d'une modification de la recherche meilleur d'abord qui réduit les besoins en mémoire en ne conservant qu'un nombre prédéterminé de meilleures solutions partielles comme candidats, ce qui en fait un algorithme glouton. L'algorithme est largement appliqué dans les tâches de décodage de séquences, telles que la traduction automatique et la reconnaissance vocale, où il équilibre la qualité de sortie avec la tractabilité computationnelle.
L'idée centrale de la recherche en faisceau est de maintenir un ensemble des solutions partielles les plus prometteuses, appelé le faisceau, et de ne développer que celles-ci à chaque étape. Cette approche contraste avec les méthodes de recherche exhaustive qui considèrent tous les chemins possibles, ce qui peut être computationnellement prohibitif pour de grands espaces de recherche. En élaguant les candidats moins prometteurs, la recherche en faisceau atteint une efficacité tout en sacrifiant les garanties de complétude et d'optimalité.
Détails Algorithmiques
La recherche en faisceau opère en utilisant une stratégie de recherche en largeur pour construire son arbre de recherche. À chaque niveau de l'arbre, elle génère tous les successeurs des états au niveau actuel et les trie par ordre croissant de coût heuristique. Cependant, elle ne stocke qu'un nombre prédéterminé, noté β (la largeur du faisceau), des meilleurs états à chaque niveau. Seuls ces états sont développés ensuite, et les autres sont écartés.
La largeur du faisceau β est un paramètre critique qui contrôle le compromis entre la qualité de recherche et l'utilisation des ressources. Une largeur de faisceau plus grande conserve plus d'états, réduisant le nombre de candidats élagués et améliorant potentiellement la qualité de la solution, mais elle augmente également les exigences en mémoire et en calcul. Avec une largeur de faisceau infinie, aucun état n'est élagué, et la recherche en faisceau devient identique à la recherche meilleur d'abord. Inversement, une largeur de faisceau de 1 correspond à un algorithme de montée de colline, qui suit de manière gloutonne uniquement le meilleur chemin unique.
La largeur du faisceau borne la mémoire nécessaire pour effectuer la recherche, ce qui la rend adaptée aux grands systèmes avec une mémoire limitée. Cependant, comme un état but pourrait potentiellement être élagué, la recherche en faisceau sacrifie la complétude - la garantie qu'un algorithme se terminera avec une solution si une existe. De plus, la recherche en faisceau n'est pas optimale, ce qui signifie qu'il n'y a aucune garantie qu'elle trouvera la meilleure solution possible.
Développement Historique
La première utilisation de ce qui deviendrait la recherche en faisceau était dans le système de reconnaissance vocale Harpy, introduit dans une thèse de 1976. La procédure était initialement appelée le « modèle de locus de recherche », mais le terme « recherche en faisceau » était déjà utilisé en 1977. Harpy a été développé à Carnegie Mellon University et représentait une avancée significative dans la technologie de reconnaissance vocale, démontrant l'utilité pratique de la recherche heuristique dans des applications réelles.
Le développement de la recherche en faisceau faisait partie d'une tendance plus large dans les années 1970 vers des algorithmes de recherche efficaces pour les systèmes d'intelligence artificielle. Les chercheurs ont reconnu que les méthodes de recherche exhaustive étaient souvent impraticables pour des problèmes complexes, ce qui a conduit au développement d'approches heuristiques capables de trouver de bonnes solutions rapidement. Le succès du système Harpy a aidé à établir la recherche en faisceau comme une technique fondamentale dans le domaine.
Applications en Traduction Automatique
La recherche en faisceau a été le plus prominent utilisée dans les systèmes de traduction automatique, où elle aide à sélectionner la meilleure traduction parmi de nombreux candidats possibles. Dans la traduction automatique statistique traditionnelle, chaque partie d'une phrase est traitée, et de nombreuses façons différentes de traduire les mots sont générées. La recherche en faisceau garde les meilleures traductions selon leurs structures de phrases et écarte le reste, puis évalue les traductions restantes selon un critère donné pour choisir celle qui répond le mieux aux objectifs.
Dans la traduction automatique neuronale moderne, qui utilise principalement des grands modèles de langage et des architectures transformeur, la recherche en faisceau reste une stratégie de décodage clé. Pendant la génération, le modèle produit une distribution de probabilité sur les prochains jetons possibles à chaque étape. La recherche en faisceau maintient plusieurs séquences partielles, développant les plus prometteuses en fonction de leurs probabilités cumulatives. Cette approche produit des traductions de meilleure qualité que le décodage glouton, qui sélectionne uniquement le jeton le plus probable à chaque étape.
L'application de la recherche en faisceau dans la traduction automatique a été largement étudiée, avec des chercheurs explorant diverses modifications pour améliorer les performances. Par exemple, la normalisation de longueur est souvent appliquée pour éviter un biais vers des séquences plus courtes, et des techniques de recherche en faisceau diversifiée ont été développées pour encourager la variété parmi les séquences candidates.
Variantes et Extensions
Plusieurs variantes de la recherche en faisceau ont été développées pour remédier à ses limitations, en particulier son manque de complétude et d'optimalité. Une approche combine la recherche en faisceau avec la recherche en profondeur, résultant en la recherche en faisceau par pile et la recherche en faisceau en profondeur. Ces algorithmes sont des algorithmes anytime qui trouvent de bonnes solutions mais probablement sous-optimales rapidement, comme la recherche en faisceau, puis reviennent en arrière et continuent à trouver des solutions améliorées jusqu'à convergence vers une solution optimale.
Une autre variante, la recherche en faisceau avec retour arrière à divergence limitée (BULB), combine la recherche en faisceau avec la recherche à divergence limitée. Cette approche produit également des algorithmes anytime qui peuvent améliorer les solutions au fil du temps. Dans le contexte de la recherche locale, la recherche en faisceau locale est un algorithme spécifique qui commence par sélectionner β états générés aléatoirement et ensuite, pour chaque niveau de l'arbre de recherche, considère β nouveaux états parmi tous les successeurs possibles des états actuels jusqu'à atteindre un but.
Comme la recherche en faisceau locale se termine souvent sur des maxima locaux, une solution courante est de choisir les β états suivants de manière aléatoire, avec une probabilité dépendant de l'évaluation heuristique des états. Ce type de recherche est appelé recherche en faisceau stochastique. D'autres variantes incluent la recherche en faisceau flexible et la recherche en faisceau avec récupération, qui ajustent dynamiquement la largeur du faisceau ou permettent une récupération après de mauvaises décisions d'élagage.
Rôle dans les Systèmes d'IA Modernes
La recherche en faisceau joue un rôle crucial dans les systèmes modernes d'intelligence artificielle, en particulier dans les applications d'IA générative. Dans les modèles de apprentissage profond, en particulier ceux basés sur l'architecture transformeur, la recherche en faisceau est utilisée pendant l'inférence pour générer des séquences telles que du texte, du code ou de la parole. Des entreprises comme OpenAI, Anthropic et Google DeepMind emploient la recherche en faisceau dans leurs modèles de langage pour produire des sorties cohérentes et contextuellement appropriées.
La technique est également utilisée dans d'autres tâches de génération de séquences, telles que la légende d'images, la reconnaissance vocale et la prédiction de structure de protéines. Dans ces applications, la recherche en faisceau aide à équilibrer la qualité de la sortie générée avec les ressources computationnelles requises. La largeur du faisceau peut être ajustée en fonction des exigences spécifiques de la tâche, avec des largeurs plus grandes fournissant une meilleure qualité au prix d'un calcul accru.
Propriétés Théoriques
Les propriétés théoriques de la recherche en faisceau ont été analysées dans le contexte de la recherche heuristique. En tant qu'algorithme glouton, elle fait des choix localement optimaux à chaque étape, ce qui peut conduire à des solutions globales sous-optimales. La performance de l'algorithme dépend fortement de la qualité de la fonction heuristique utilisée pour évaluer les états. Une heuristique bien conçue peut guider la recherche vers de bonnes solutions, tandis qu'une mauvaise heuristique peut faire manquer à l'algorithme des chemins optimaux.
Le compromis entre la largeur du faisceau et la qualité de la solution est une considération centrale dans les applications pratiques. La recherche a montré que l'augmentation de la largeur du faisceau améliore généralement la qualité de la solution, mais avec des rendements décroissants. Dans certains cas, une largeur de faisceau trop grande peut conduire à une sur-génération et à des coûts computationnels accrus sans améliorations significatives de la qualité. Inversement, une largeur de faisceau trop petite peut entraîner de mauvaises solutions en raison d'un élagage excessif.
Considérations Computationnelles
La complexité computationnelle de la recherche en faisceau est principalement déterminée par la largeur du faisceau et le facteur de branchement de l'espace de recherche. À chaque niveau, l'algorithme génère des successeurs pour tous les états du faisceau, ce qui nécessite β × b opérations, où b est le facteur de branchement. Le tri de ces successeurs ajoute un facteur supplémentaire de log(β × b) par niveau. La complexité totale est donc O(β × b × L × log(β × b)), où L est la profondeur maximale de la recherche.
L'utilisation de la mémoire est bornée par la largeur du faisceau, car seuls β états sont stockés à chaque niveau. Cela rend la recherche en faisceau particulièrement attrayante pour les applications avec une mémoire limitée, telles que les systèmes embarqués ou le traitement en temps réel. La capacité de l'algorithme à équilibrer l'utilisation de la mémoire et la qualité de la solution a contribué à sa popularité durable dans la recherche académique et les applications industrielles.
Comparaison avec d'Autres Méthodes de Recherche
La recherche en faisceau est souvent comparée à d'autres algorithmes de recherche, tels que la recherche gloutonne, la recherche meilleur d'abord et les méthodes de décodage basées sur le apprentissage automatique. La recherche gloutonne, qui correspond à la recherche en faisceau avec une largeur de faisceau de 1, est computationnellement efficace mais produit souvent des résultats de qualité inférieure. La recherche meilleur d'abord, qui considère toutes les solutions partielles, peut trouver des solutions optimales mais nécessite une mémoire proportionnelle à tout l'espace de recherche.
Dans le contexte de la génération de séquences neuronales, la recherche en faisceau est parfois contrastée avec les méthodes basées sur l'échantillonnage, qui sélectionnent aléatoirement des jetons en fonction de leurs distributions de probabilité. L'échantillonnage peut produire des sorties plus diverses mais peut sacrifier la cohérence, tandis que la recherche en faisceau tend à produire des résultats plus déterministes et de meilleure qualité. Des recherches récentes ont exploré des approches hybrides qui combinent la recherche en faisceau avec l'échantillonnage pour atteindre un équilibre entre qualité et diversité.
Directions Futures
Au début des années 2020, la recherche en faisceau continue d'être un domaine de recherche actif, en particulier dans le contexte des grands modèles de langage. Les chercheurs explorent des stratégies adaptatives de largeur de faisceau qui s'ajustent en fonction de la confiance des prédictions du modèle, ainsi que des méthodes pour incorporer des contraintes externes dans le processus de recherche en faisceau. Le développement de matériel plus efficace, tel que les accélérateurs d'IA spécialisés de sociétés comme NVIDIA et AMD, a permis des largeurs de faisceau plus grandes et des stratégies de recherche plus complexes dans des applications en temps réel.
L'intégration de la recherche en faisceau avec d'autres techniques d'IA, telles que l'apprentissage par renforcement et les réseaux neuronaux, est également un domaine d'investigation en cours. Ces efforts visent à améliorer l'efficacité et l'efficacité de la génération de séquences dans une large gamme d'applications, du traitement du langage naturel à la découverte scientifique.