Recherche par faisceau

Qu'est-ce que la recherche par faisceau ?

La recherche par faisceau est un algorithme de recherche heuristique qui développe le nœud le plus prometteur dans un ensemble limité pour explorer un graphe. Cette technique utilise un algorithme de recherche en largeur pour construire une structure de données en arbre et générer des successeurs de l'état actuel de chaque niveau.

Les applications de traitement du langage naturel (NLP) et les modèles de reconnaissance vocale utilisent la recherche par faisceau comme couche de prise de décision. L'objectif ici est de choisir la meilleure sortie pour des variables cibles comme le prochain caractère de sortie ou la probabilité maximale.

L'algorithme de recherche par faisceau sélectionne des tokens pour une position particulière dans une séquence en fonction de la probabilité conditionnelle. Il ajuste la largeur du faisceau (β) pour choisir diverses alternatives d'hyperparamètre n.

Contrairement à la recherche gloutonne, la recherche par faisceau élargit la recherche pour explorer les ajustements possibles pour les mots dans une séquence. La recherche par faisceau tire son nom de la manière dont l'algorithme projette un large faisceau de recherche. 

Types de recherche par faisceau

La recherche par faisceau a différentes variantes, selon l'algorithme utilisé, telles que la recherche en profondeur (DFS), la recherche à divergence limitée et la recherche basée sur la mémoire.

1. Recherche par pile de faisceaux est un algorithme de recherche qui utilise une pile de faisceaux comme structure de données pour combiner la recherche en profondeur ou le retour en arrière chronologique avec la recherche par faisceau. Les utilisateurs peuvent également la connecter avec un algorithme de diviser pour régner — une technique qui décompose récursivement un problème en deux ou plusieurs sous-problèmes — pour créer une recherche par pile de faisceaux de diviser pour régner.
2. Recherche par faisceau en profondeur utilise un algorithme de recherche en profondeur pour explorer les structures de données en graphe. Elle utilise une mémoire supplémentaire ou une pile pour suivre les nœuds explorés le long d'une branche spécifique et revenir en arrière dans le graphe. 
3. Recherche par faisceau local suit ou maintient jusqu'à k états générés aléatoirement ou nombres d'assignations au lieu d'un seul. Elle choisit les k meilleurs voisins des individus actuels à chaque étape. L'algorithme rapporte le succès uniquement après avoir trouvé une assignation satisfaisante. En cas d'égalité, il choisira des valeurs aléatoires.
4. Recherche par faisceau stochastique sélectionne k des individus aléatoirement au lieu des k meilleurs individus. Cette variation de la recherche par faisceau utilise la probabilité d'être choisi comme fonction de la fonction d'évaluation. Plus l'évaluation est bonne, plus les chances d'être choisi sont élevées.
5. Recherche par faisceau utilisant le retour en arrière à divergence limitée (BULB) est une méthode de recherche basée sur la mémoire qui résout des problèmes de recherche plus importants dans un temps d'exécution raisonnable. Les recherches BULB le font en utilisant des largeurs de faisceau plus grandes et en trouvant des chemins plus courts sans perdre de mémoire.
6. Recherche par faisceau flexible augmente temporairement la largeur du faisceau pour inclure tous les nœuds enfants ayant la même valeur heuristique. 

Composants de la recherche par faisceau

La recherche par faisceau a trois composants :

1. Un problème qui peut être un graphe ou contenir un ensemble de nœuds représentant un objectif.
2. Règles heuristiques se réfèrent aux directives spécifiques au domaine du problème utilisées pour supprimer les nœuds défavorables de la mémoire et se concentrer sur le domaine du problème.
3. Mémoire qui stocke le faisceau mais a une capacité disponible limitée. Lorsque la mémoire est pleine, l'algorithme supprime automatiquement le nœud le plus coûteux pour éviter de dépasser la limite de mémoire. 

Avantages de l'utilisation de la recherche par faisceau 

La recherche par faisceau tente de trouver l'optimal complexe de manière heuristique. Les avantages de l'utilisation de la recherche par faisceau pour résoudre des problèmes d'optimisation sont :

• Réduction des calculs : La recherche par faisceau utilise un nombre limité de nœuds ou de ressources à la fois. En conséquence, elle nécessite moins de calculs et de consommation de mémoire par rapport à d'autres méthodes de recherche. Développer des règles heuristiques efficaces pour l'élagage est crucial pour réaliser cet avantage, ce qui peut être difficile sans connaissances du domaine.
• Amélioration des choix sous-optimaux : La recherche gloutonne considère chaque position isolément. Au contraire, la recherche par faisceau considère plus d'une option à la fois et améliore les choix sous-optimaux. 

Inconvénients de l'utilisation de la recherche par faisceau 

Le principal inconvénient de l'utilisation d'une recherche par faisceau est que les utilisateurs peuvent ne pas atteindre un objectif optimal à la fin. La plupart des algorithmes de recherche par faisceau se terminent dans deux scénarios : soit l'utilisateur n'a pas encore atteint un nœud objectif et il n'y a plus de nœud à explorer, soit il a atteint le nœud objectif requis. 

De plus, la recherche par faisceau peut être incomplète en raison de sa nature probabiliste. Malgré ces inconvénients, les algorithmes de recherche par faisceau ont connu du succès dans la reconnaissance vocale, la vision, la planification et l'apprentissage automatique. 

Utilisations de la recherche par faisceau

La recherche par faisceau a de multiples utilisations dans les systèmes de traduction automatique, le NLP et la reconnaissance vocale. Les grands systèmes avec une mémoire insuffisante pour stocker l'arbre de recherche entier se tournent fréquemment vers la recherche par faisceau pour rester gérables.

Les systèmes de traduction automatique neuronale (NMT) utilisent la recherche par faisceau pour choisir la meilleure traduction et traiter chaque partie. Ils conservent les meilleures traductions avec les bonnes structures de phrases et écartent le reste. Le traducteur vérifie ensuite les traductions et choisit la meilleure qui répond aux objectifs. En 1976, le système de reconnaissance vocale Harpy de l'Université Carnegie-Mellon a été le premier à utiliser une recherche par faisceau. 

Recherche par faisceau vs. recherche gloutonne vs. recherche du meilleur d'abord

Une recherche gloutonne suit l'heuristique de résolution de problème pour construire une solution progressivement, une étape à la fois. Le système privilégie la sélection de la prochaine pièce qui offre des avantages clairs et immédiats. Les algorithmes gloutons fonctionnent mieux pour les problèmes où il est important de choisir des solutions localement optimales.

La recherche par faisceau optimise la recherche du meilleur d'abord pour réduire les besoins en mémoire.

Les recherches gloutonne et par faisceau utilisent toutes deux des modèles séquence-à-séquence pour générer des sorties de séquence ou des tokens à partir d'un réseau neuronal. Cependant, la première évalue chaque position indépendamment, et la seconde en considère plus d'une à la fois.

La recherche du meilleur d'abord est une technique de recherche de graphe qui trie et ordonne les solutions partielles en fonction des heuristiques. Cependant, la recherche par faisceau considère un nombre prédéterminé des meilleures solutions partielles comme candidates. C'est pourquoi la recherche par faisceau est considérée comme un algorithme glouton. 

Vous cherchez à interpréter des données de manière digeste ? Explorez les meilleurs logiciels de génération de langage naturel (NLG) pour traiter des ensembles de données.