Beam search

Beam search
Classe	Algoritmo di ricerca
Struttura dati	Albero
Caso peggiore temporalmente	${\displaystyle b^{m}}$
Caso peggiore spazialmente	${\displaystyle \beta }$
Ottimale	no
Completo	no

In informatica, la beam search è un algoritmo di ricerca basato su euristiche che esplora un grafo espandendo il nodo più promettente in un insieme limitato di nodi.

La beam search è un caso particolare di best-first search che mira a ridurre i requisiti di memoria. Best-first search è una ricerca su grafi che ordina tutte le soluzioni parziali (stati) in base ad una certa euristica. Nella beam search è tenuto in considerazione solo un numero predefinito di migliori soluzioni parziali.[1] Di conseguenza, è considerato un algoritmo greedy.

Il nome "beam search" venne introdotto da Raj Reddy dell'Università Carnegie Mellon, nel 1977.[2]

Dettagli

L'algoritmo beam search utilizza una ricerca in ampiezza per costruire il suo albero di ricerca. Ad ogni livello di profondità dell'albero, l'algoritmo genera tutti i successori dei nodi correnti, dispondendoli in modo che i valori della funzione euristica abbiano un ordine crescente.[3] Tuttavia, a differenza della best-first search, salva solo fino un numero predefinito, ${\displaystyle \beta }$, di stati "migliori" per ogni livello. Questo numero ${\displaystyle \beta }$ è chiamato "beam width" (lett. "ampiezza del fascio"). Più grande è l'ampiezza predefinita, minore sarà il numero di stati esclusi dalla ricerca. Logicamente, per ${\displaystyle \beta =\infty }$ non verrà escluso nessuno stato e il comportamento dell'algoritmo sarà identico ad una best-first search. L'ampiezza massima predefinita limita i requisiti di memoria per eseguire questa ricerca. L'algoritmo non fornisce garanzie sulla completezza, né sull'ottimalità della soluzione.

L'ampiezza ${\displaystyle \beta }$ può anche essere resa variabile. Un possibile approccio con ampiezza variabile prevede di eseguire inizialmente l'algoritmo con ${\displaystyle \beta }$ impostato al valore minimo e, se nessuna soluzione viene trovata, di aumentarne il valore ad ogni nuova esecuzione.[4]

Utilizzi

La beam search viene usata in grandi sistemi aventi memoria insufficiente per memorizzare l'intero albero di ricerca.[5] Ad esempio, è usata in vari sistemi di traduzione automatica.[6] Per selezionare la traduzione migliore, di ogni parola vengono generate diverse possibili traduzioni, ciascuna delle quali dipende dalla parola e dal contesto sintattico-semantico in cui è inserita.[7] Per ogni parola viene dunque salvata una porzione limitata delle traduzioni disponibili, in modo da risparmiare spazio, e viene scartato il resto.

Varianti

La beam search può essere resa completa combinandola con la ricerca in profondità. Fra le varianti di questo tipo, troviamo la beam stack search[8] e depth-first beam search[5].

Nel contesto di una ricerca locale, la local beam search è un particolare algoritmo che inizia selezionando ${\displaystyle \beta }$ stati generati casualmente e poi, per ogni livello dell'albero di ricerca, considera sempre ${\displaystyle \beta }$ nuovi stati fra i possibili successori di quelli correnti, fino a quando l'obiettivo non viene raggiunto.[9][10]

Dato che la local beam search è solita terminare su massimi locali (soluzioni sotto-ottimali), una soluzione adottata solitamente è quella di scegliere i nuovi ${\displaystyle \beta }$ stati in maniera casuale, con una probabilità dipendente dalla valutazione euristica di ciascuno stato. Questo tipo di ricerca è nota come stochastic beam search.[11]

Altre varianti sono flexible beam search e recovery beam search.[10]

Note

1. (EN) FOLDOC - Computing Dictionary, su foldoc.org. URL consultato l'11 aprile 2016 (archiviato dall'url originale il 25 gennaio 2020).
2. (EN) D. Raj. Reddy, Speech Understanding Systems: A Summary of Results of the Five-Year Research Effort, Università Carnegie Mellon - Dipartimento di Informatica, 1977.
3. (EN) BRITISH MUSEUM SEARCH, su bradley.bradley.edu. URL consultato l'11 aprile 2016 (archiviato il 6 maggio 2018).
4. (EN) Peter Norvig, Paradigms of Artificial Intelligence Programming: Case Studies in Common LISP, Morgan Kaufmann, 1º gennaio 1992, ISBN 978-1-55860-191-8.
5. (EN) David Furcy, Sven Koenig, Limited Discrepancy Beam Search (PDF), 2005. URL consultato il 22 dicembre 2007 (archiviato dall'url originale il 16 maggio 2008).
6. (EN) Christoph Tillmann, Hermann Ney, Word Reordering and a Dynamic Programming Beam Search Algorithm for Statistical Machine Translation (PDF). URL consultato il 22 dicembre 2007 (archiviato dall'url originale il 18 giugno 2006).
7. Nella versione più semplice, tale contesto è costituito dalle parole già tradotte all'interno della stessa frase all'interno del ramo corrente dell'albero di ricerca.
8. (EN) Zhou, Rong. Hansen, Eric, Beam-Stack Search: Integrating Backtracking with Beam Search, 2005. URL consultato il 29 aprile 2019 (archiviato dall'url originale il 16 novembre 2019).
9. (EN) Svetlana Lazebnik, Local search algorithms (PDF), su cs.unc.edu, University of North Carolina at Chapel Hill, Department of Computer Science, p. 15. URL consultato il 21 novembre 2018 (archiviato dall'url originale il 5 luglio 2011).
10. (EN) Pushpak Bhattacharyya, Beam Search (PPTX), su cse.iitb.ac.in, Indian Institute of Technology Bombay, Department of Computer Science and Engineering (CSE), pp. 39-40. URL consultato il 21 novembre 2018 (archiviato il 21 novembre 2018).
11. (EN) James Parker, Local Search (PDF), su www-users.cselabs.umn.edu, University of Minnesota, 28 settembre 2017, p. 17. URL consultato il 21 novembre 2018 (archiviato il 13 ottobre 2017).