Búsqueda en haz

¿Qué es la búsqueda en haz?

La búsqueda en haz es un algoritmo de búsqueda heurística que expande el nodo más prometedor en un conjunto limitado para explorar un grafo. Esta técnica utiliza un algoritmo de búsqueda en anchura para construir una estructura de datos en forma de árbol y generar sucesores del estado actual de cada nivel.

Las aplicaciones de procesamiento de lenguaje natural (NLP) y los modelos de reconocimiento de voz utilizan la búsqueda en haz como una capa de toma de decisiones. El objetivo aquí es elegir la mejor salida para variables objetivo como el siguiente carácter de salida o la máxima probabilidad.

El algoritmo de búsqueda en haz selecciona tokens para una posición particular en una secuencia basándose en la probabilidad condicional. Ajusta el ancho del haz (β) para elegir varias alternativas de hiperparámetro n.

A diferencia de la búsqueda codiciosa, la búsqueda en haz amplía la búsqueda para explorar posibles ajustes para palabras en una secuencia. La búsqueda en haz recibe su nombre de cómo el algoritmo lanza un haz de búsqueda amplio. 

Tipos de búsqueda en haz

La búsqueda en haz tiene diferentes variantes, dependiendo del algoritmo en uso, como la búsqueda en profundidad (DFS), la búsqueda de discrepancia limitada y la búsqueda basada en memoria.

1. Búsqueda en pila de haz es un algoritmo de búsqueda que utiliza una pila de haz como estructura de datos para combinar la búsqueda en profundidad o el retroceso cronológico con la búsqueda en haz. Los usuarios también pueden conectarlo con un algoritmo de divide y vencerás —una técnica que descompone recursivamente un problema en dos o más subproblemas— para crear una búsqueda en pila de haz de divide y vencerás.
2. Búsqueda en haz en profundidad utiliza un algoritmo de búsqueda en profundidad para buscar estructuras de datos de grafos. Utiliza memoria adicional o una pila para rastrear los nodos explorados a lo largo de una rama específica y retroceder en el grafo. 
3. Búsqueda en haz local rastrea o mantiene hasta k estados generados aleatoriamente o números de asignaciones en lugar de uno. Elige los k mejores vecinos de los individuos actuales en cada etapa. El algoritmo informa de éxito solo después de encontrar una asignación satisfactoria. En caso de empates, elegirá valores aleatorios.
4. Búsqueda en haz estocástica selecciona k de los individuos aleatoriamente en lugar de los mejores k individuos. Esta variación de búsqueda en haz utiliza la probabilidad de ser elegido como una función de la función de evaluación. Cuanto mejor sea la evaluación, mayores serán las posibilidades de ser elegido.
5. Búsqueda en haz utilizando retroceso de discrepancia limitada (BULB) es un método de búsqueda basado en memoria que resuelve problemas de búsqueda más grandes dentro de un tiempo de ejecución razonable. Las búsquedas BULB lo hacen utilizando anchos de haz más grandes y encontrando caminos más cortos sin perder memoria.
6. Búsqueda en haz flexible aumenta temporalmente el ancho del haz para incluir todos los nodos hijos con el mismo valor heurístico. 

Componentes de la búsqueda en haz

La búsqueda en haz tiene tres componentes:

1. Un problema que puede ser un grafo o puede contener un conjunto de nodos que representan un objetivo.
2. Reglas heurísticas se refieren a las pautas específicas del dominio del problema utilizadas para eliminar nodos desfavorables de la memoria y centrarse en el dominio del problema.
3. Memoria que almacena el haz pero tiene capacidad disponible limitada. Cuando la memoria está llena, el algoritmo elimina automáticamente el nodo más costoso para evitar exceder el límite de memoria. 

Beneficios de usar la búsqueda en haz 

La búsqueda en haz intenta encontrar el complejo óptimo de manera heurística. Los beneficios de usar la búsqueda en haz para resolver problemas de optimización son:

• Reducción de la computación: La búsqueda en haz utiliza un número limitado de nodos o recursos a la vez. Como resultado, necesita menos computación y consumo de memoria en comparación con otros métodos de búsqueda. Desarrollar reglas heurísticas efectivas para la poda es crucial para realizar esta ventaja, lo cual puede ser un desafío sin conocimiento del dominio.
• Mejora de elecciones subóptimas: La búsqueda codiciosa considera cada posición de forma aislada. Por el contrario, la búsqueda en haz considera más de una opción a la vez y mejora las elecciones subóptimas. 

Desventajas de usar la búsqueda en haz 

La principal desventaja de usar una búsqueda en haz es que los usuarios pueden no alcanzar un objetivo óptimo al final. La mayoría de los algoritmos de búsqueda en haz terminan en dos escenarios: o el usuario aún no ha alcanzado un nodo objetivo y no queda ningún nodo por explorar, o ha alcanzado el nodo objetivo requerido. 

Además, la búsqueda en haz puede ser incompleta debido a su naturaleza probabilística. A pesar de estas desventajas, los algoritmos de búsqueda en haz han tenido éxito en reconocimiento de voz, visión, planificación y aprendizaje automático. 

Usos de la búsqueda en haz

La búsqueda en haz tiene múltiples usos en sistemas de traducción automática, NLP y reconocimiento de voz. Los sistemas grandes con memoria insuficiente para almacenar todo el árbol de búsqueda recurren frecuentemente a la búsqueda en haz para mantenerse manejables.

Los sistemas de traducción automática neuronal (NMT) utilizan la búsqueda en haz para elegir la mejor traducción y procesar cada parte. Mantienen las mejores traducciones con las estructuras de oración correctas y descartan el resto. El traductor luego verifica las traducciones y elige la mejor que cumpla con los objetivos. En 1976, el Sistema de Reconocimiento de Voz Harpy de la Universidad Carnegie-Mellon fue el primero en usar una búsqueda en haz. 

Búsqueda en haz vs. búsqueda codiciosa vs. búsqueda del mejor primero

Una búsqueda codiciosa sigue la heurística de resolución de problemas para construir una solución gradualmente, un paso a la vez. El sistema prioriza seleccionar la siguiente pieza que proporcione ventajas claras e inmediatas. Los algoritmos codiciosos funcionan mejor para problemas donde es importante elegir soluciones localmente óptimas.

La búsqueda en haz optimiza la búsqueda del mejor primero para reducir los requisitos de memoria.

Tanto las búsquedas codiciosas como las búsquedas en haz utilizan modelos de secuencia a secuencia para generar salidas de secuencia o tokens de una red neuronal. Sin embargo, la primera evalúa cada posición de manera independiente, y la segunda considera más de una a la vez.

La búsqueda del mejor primero es una técnica de búsqueda de grafos que ordena y clasifica soluciones parciales basadas en heurísticas. Sin embargo, la búsqueda en haz considera un número predeterminado de mejores soluciones parciales como candidatas. Por eso, la búsqueda en haz se trata como un algoritmo codicioso. 

¿Buscas interpretar datos de manera comprensible? Explora el mejor software de generación de lenguaje natural (NLG) para procesar conjuntos de datos.