Recherche de faisceau - Beam search

En informatique , la recherche de faisceau est un algorithme de recherche heuristique qui explore un graphe en développant le nœud le plus prometteur dans un ensemble limité. La recherche par faisceau est une optimisation de la recherche best-first qui réduit ses besoins en mémoire. La recherche Best-first est une recherche de graphe qui ordonne toutes les solutions partielles (états) selon une heuristique. Mais dans la recherche de faisceau, seul un nombre prédéterminé de meilleures solutions partielles sont conservés comme candidats. C'est donc un algorithme glouton .

Le terme « recherche par faisceau » a été inventé par Raj Reddy de l'Université Carnegie Mellon en 1977.

Des détails

La recherche par faisceau utilise la recherche en largeur d'abord pour créer son arbre de recherche . A chaque niveau de l'arbre, il génère tous les successeurs des états au niveau courant, en les triant par ordre croissant de coût heuristique. Cependant, il ne stocke qu'un nombre prédéterminé, , des meilleurs états à chaque niveau (appelé largeur de faisceau). Seuls ces états sont étendus ensuite. Plus la largeur du faisceau est grande, moins les états sont élagués. Avec une largeur de faisceau infinie, aucun état n'est élagué et la recherche de faisceau est identique à la recherche en largeur d'abord . La largeur du faisceau délimite la mémoire requise pour effectuer la recherche. Puisqu'un état cible pourrait potentiellement être élagué, la recherche de faisceau sacrifie l'exhaustivité (la garantie qu'un algorithme se terminera avec une solution, s'il en existe une). La recherche de faisceau n'est pas optimale (c'est-à-dire qu'il n'y a aucune garantie qu'elle trouvera la meilleure solution). . ${\displaystyle \beta }$

Les usages

Une recherche de faisceau est le plus souvent utilisée pour maintenir la traçabilité dans les grands systèmes avec une quantité de mémoire insuffisante pour stocker l'intégralité de l'arbre de recherche. Par exemple, il a été utilisé dans de nombreux systèmes de traduction automatique. (L'état de l'art utilise maintenant principalement des méthodes basées sur la traduction automatique neuronale .) Pour sélectionner la meilleure traduction, chaque partie est traitée et de nombreuses façons différentes de traduire les mots apparaissent. Les meilleures traductions en fonction de leurs structures de phrases sont conservées et les autres sont rejetées. Le traducteur évalue ensuite les traductions selon un critère donné, en choisissant la traduction qui respecte le mieux les objectifs. La première utilisation d'une recherche par faisceau était dans le système de reconnaissance vocale Harpy, CMU 1976.

Variantes

La recherche de faisceau a été complétée en la combinant avec la recherche en profondeur d'abord , résultant en une recherche de pile de faisceau et une recherche de faisceau en profondeur d'abord , et avec une recherche de discordance limitée, résultant en une recherche de faisceau utilisant le backtracking de discordance limitée (BULB). Les algorithmes de recherche résultants sont des algorithmes à tout moment qui trouvent rapidement des solutions bonnes mais probablement sous-optimales, comme la recherche de faisceau, puis reviennent en arrière et continuent à trouver des solutions améliorées jusqu'à convergence vers une solution optimale.

Dans le contexte d'une recherche locale , nous appelons recherche de faisceau local un algorithme spécifique qui commence à sélectionner des états générés aléatoirement puis, pour chaque niveau de l'arbre de recherche, il considère toujours de nouveaux états parmi tous les successeurs possibles des actuels, jusqu'à ce qu'il atteint un but. ${\displaystyle \beta }$${\displaystyle \beta }$

Étant donné que la recherche de faisceaux locaux aboutit souvent à des maxima locaux, une solution courante consiste à choisir les états suivants de manière aléatoire, avec une probabilité dépendante de l'évaluation heuristique des états. Ce type de recherche est appelé recherche de faisceau stochastique . ${\displaystyle \beta }$

D'autres variantes sont la recherche de faisceau flexible et la recherche de faisceau de récupération .

Les références