Algorithme de recherche en faisceau

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique, la recherche en faisceau est un algorithme de recherche heuristique qui explore un graphe en ne considérant qu'un ensemble limité de fils de chaque nœud. La recherche en faisceau est une optimisation de l'algorithme de parcours en largeur, en réduisant la mémoire nécessaire à son exécution. Contrairement à l'algorithme best-first où l'on explore tous les états candidats à la solution recherchée en partant du meilleur (estimé), la recherche en faisceau n'explore qu'un nombre limité de ces candidats[1].

La recherche en faisceau utilise l'algorithme de parcours en largeur pour explorer le graphe. À chaque niveau, elle génère tous les successeurs du nœud courant, en les classant selon leur coût heuristique[2]. Cependant, elle ne mémorise qu'un nombre prédéterminé de ces états à chaque niveau (nombre appelé la largeur du faisceau). Plus grande est la largeur, moins d'états sont ignorés. Avec une largeur infinie, tous les états sont considérés et l'algorithme devient identique au parcours en largeur. La largeur du faisceau limite la mémoire requise pour exécuter la recherche. Sachant qu'un état d'arrivée (but de la recherche) peut être ignoré par l'algorithme, la recherche en faisceau sacrifie la complétude (garantie que l'algorithme trouvera la solution si elle existe) et l'optimalité (garantie de trouver la meilleure solution possible).

La largeur du faisceau peut être fixe ou variable. Un exemple d'approche utilise une largeur minimale ; si aucune solution n'est trouvée, la procédure est répétée avec une largeur plus grande[3].

Nom[modifier | modifier le code]

Le terme de recherche en faisceau (beam search) est issu de Raj Reddy, de l'Université Carnegie-Mellon, en 1976.

Utilisations[modifier | modifier le code]

Une recherche en faisceau est le plus souvent utilisée pour étudier des systèmes trop complexes pour pouvoir stocker la totalité du graphe de recherche[4]. Par exemple, l'algorithme est utilisé dans de nombreux traducteurs automatiques[5]. Pour sélectionner la meilleure traduction, chaque partie de la phrase est traitée et de très nombreuses définitions du mot apparaissent. En considérant leur structure grammaticale, les meilleures sont conservées. Le programme évalue ensuite les traductions selon certains critères, choisissant celle qui semble la plus cohérente. La première utilisation d'une recherche en faisceau a été faite par le Harpy Speech Recognition System en 1976, à l'UCM[6].

Améliorations[modifier | modifier le code]

Le parcours en faisceau a été complété (de sorte à ce qu'elle termine avec une solution) en le combinant avec le parcours en profondeur, créant le Beam Stack Search[7] et le Depth-First Beam Search[4], ainsi qu'avec le parcours à écart limité, créant le Beam Search Using Limited Discrepancy Backtracking (BULB)[4]. Ces algorithmes peuvent retourner rapidement une solution valide (généralement sous-optimale) à n'importe quel moment, puis continuent à trouver des meilleures solutions (par retour sur trace) jusqu'à converger vers une solution optimale.

Références[modifier | modifier le code]

  1. (en) FOLDOC : Recherche en faisceau
  2. (en) British Museum Search
  3. (en) Norvig, Peter. Paradigms of Artificial Intelligence. http://books.google.com/books?id=X4mhySvjqUAC&pg=PA196&lpg=PA196&dq=beam+search+in+paradigms+of+artificial+intelligence+programming&source=web&ots=20BH2lB3sc&sig=udBIO2Qeg8awaySgwCu7gDEObY4&hl=en&sa=X&oi=book_result&resnum=1&ct=result#PPA196,M1 Programming
  4. a, b et c (en) Furcy, David. Koenig, Sven. "Limited Discrepancy Beam Search". 2005. http://www.ijcai.org/papers/0596.pdf
  5. (en) Tillmann, Christoph. Ney, Hermann. "Word Reordering and a Dynamic Programming Beam Search Algorithm for Statistical Machine Translation". http://acl.ldc.upenn.edu/J/J03/J03-1005.pdf
  6. (en) Lowerre, Bruce. "The Harpy Speech Recognition System", Ph.D. thesis, Carnegie Mellon University, 1976
  7. (en) Zhou, Rong. Hansen, Eric. "Beam-Stack Search: Integrating Backtracking with Beam Search". 2005. http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php