En informática , la búsqueda por haz es un algoritmo de búsqueda heurístico que explora un gráfico al expandir el nodo más prometedor en un conjunto limitado. Beam search es una optimización de la mejor búsqueda que reduce los requisitos de memoria. La búsqueda mejor primero es una búsqueda gráfica que ordena todas las soluciones parciales (estados) de acuerdo con alguna heurística. Pero en la búsqueda de haces, solo un número predeterminado de mejores soluciones parciales se mantienen como candidatos. [1] Por tanto, es un algoritmo codicioso .
El término "búsqueda de rayos" fue acuñado por Raj Reddy de la Universidad Carnegie Mellon en 1977. [2]
Detalles
Beam search utiliza la búsqueda en amplitud para construir su árbol de búsqueda . En cada nivel del árbol, genera todos los sucesores de los estados en el nivel actual, clasificándolos en orden creciente de costo heurístico. [3] Sin embargo, solo almacena un número predeterminado,, de los mejores estados en cada nivel (llamado ancho de haz). Solo esos estados se expanden a continuación. Cuanto mayor sea el ancho de la viga, menos estados se podarán. Con un ancho de haz infinito, no se poda ningún estado y la búsqueda del haz es idéntica a la búsqueda en amplitud . El ancho del haz limita la memoria necesaria para realizar la búsqueda. Dado que un estado objetivo podría potencialmente podarse, la búsqueda de haces sacrifica la integridad (la garantía de que un algoritmo terminará con una solución, si existe). La búsqueda de haces no es óptima (es decir, no hay garantía de que encontrará la mejor solución).
En general, la búsqueda de haces devuelve la primera solución encontrada. La búsqueda de haces para traducción automática es un caso diferente: una vez que se alcanza la profundidad de búsqueda máxima configurada (es decir, la longitud de traducción), el algoritmo evaluará las soluciones encontradas durante la búsqueda a varias profundidades y devolverá la mejor (la que tiene la mayor probabilidad).
El ancho del haz puede ser fijo o variable. Un enfoque que utiliza un ancho de haz variable comienza con el ancho al mínimo. Si no se encuentra ninguna solución, se ensancha el haz y se repite el procedimiento. [4]
Usos
Una búsqueda de haz se usa con mayor frecuencia para mantener la capacidad de manejo en sistemas grandes con una cantidad de memoria insuficiente para almacenar todo el árbol de búsqueda. [5] Por ejemplo, se ha utilizado en muchos sistemas de traducción automática . [6] (El estado de la técnica ahora utiliza principalmente métodos basados en la traducción automática neuronal ). Para seleccionar la mejor traducción, se procesa cada parte y aparecen muchas formas diferentes de traducir las palabras. Se conservan las mejores traducciones según la estructura de las oraciones y el resto se descartan. A continuación, el traductor evalúa las traducciones según un criterio determinado, eligiendo la traducción que mejor se ajusta a los objetivos. El primer uso de una búsqueda por haz fue en el Harpy Speech Recognition System, CMU 1976. [7]
Variantes
La búsqueda de haces se ha completado combinándola con la búsqueda de profundidad primero , lo que resulta en una búsqueda de haz de haces [8] y una búsqueda de haz de profundidad primero , [5] y con una búsqueda de discrepancia limitada, [9] lo que da como resultado una búsqueda de haz con un retroceso de discrepancia limitado [5] (BOMBILLA). Los algoritmos de búsqueda resultantes son algoritmos en cualquier momento que encuentran soluciones buenas pero probablemente subóptimas rápidamente, como la búsqueda de haces, luego retroceden y continúan encontrando soluciones mejoradas hasta la convergencia a una solución óptima.
En el contexto de una búsqueda local , llamamos búsqueda de haz local a un algoritmo específico que comienza a seleccionar estados generados aleatoriamente y luego, para cada nivel del árbol de búsqueda, siempre considera nuevos estados entre todos los posibles sucesores de los actuales, hasta llegar a una meta. [10] [11]
Dado que la búsqueda de haz local a menudo termina en máximos locales, una solución común es elegir el siguiente estados de forma aleatoria, con una probabilidad dependiente de la evaluación heurística de los estados. Este tipo de búsqueda se denomina búsqueda de haz estocástico . [12]
Otras variantes son búsqueda de haz flexible y búsqueda de haz de recuperación . [11]
Referencias
- ^ "FOLDOC - Diccionario de computación" . foldoc.org . Consultado el 11 de abril de 2016 .
- ^ Reddy, D. Raj. "Sistemas de comprensión del habla: un resumen de los resultados del esfuerzo de investigación de cinco años. Departamento de Ciencias de la Computación", 1977.
- ^ "BÚSQUEDA DEL MUSEO BRITÁNICO" . bradley.bradley.edu . Consultado el 11 de abril de 2016 .
- ^ Norvig, Peter (1 de enero de 1992). Paradigmas de programación de inteligencia artificial: estudios de caso en LISP común . Morgan Kaufmann. ISBN 9781558601918.
- ^ a b c Furcy, David. Koenig, Sven. "Búsqueda de haz de discrepancia limitada". 2005. "Copia archivada" (PDF) . Archivado desde el original (PDF) el 16 de mayo de 2008 . Consultado el 22 de diciembre de 2007 .Mantenimiento de CS1: copia archivada como título ( enlace )
- ^ Tillmann, Christoph. Ney, Hermann. "Reordenamiento de palabras y un algoritmo de búsqueda de haces de programación dinámica para traducción automática estadística". "Copia archivada" (PDF) . Archivado desde el original (PDF) el 18 de junio de 2006 . Consultado el 22 de diciembre de 2007 .Mantenimiento de CS1: copia archivada como título ( enlace )
- ^ Lowerre, Bruce. "El Sistema de Reconocimiento de Voz Arpía", Ph.D. tesis, Universidad Carnegie Mellon, 1976
- ^ Zhou, Rong. Hansen, Eric. "Beam-Stack Search: integración de retroceso con Beam Search". 2005. http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php
- ^ CiteSeer x : 10.1.1.34.2426
- ^ Svetlana Lazebnik . "Algoritmos de búsqueda local" (PDF) . Universidad de Carolina del Norte en Chapel Hill, Departamento de Ciencias de la Computación. pag. 15. Archivado (PDF) desde el original el 5 de julio de 2011.
- ^ a b Pushpak Bhattacharyya. "Beam Search" . Instituto Indio de Tecnología de Bombay, Departamento de Ingeniería y Ciencias de la Computación (CSE). págs. 39–40. Archivado desde el original el 21 de noviembre de 2018.
- ^ James Parker (28 de septiembre de 2017). "Búsqueda local" (PDF) . Universidad de Minnesota. pag. 17. Archivado (PDF) desde el original el 13 de octubre de 2017 . Consultado el 21 de noviembre de 2018 .