La búsqueda de haz es un algoritmo de búsqueda heurística utilizado en ciencias de la computación para explorar un grafo expandiendo el nodo más prometedor dentro de un conjunto limitado. Es una modificación de la búsqueda de mejor primero que reduce los requisitos de memoria al mantener solo un número predeterminado de mejores soluciones parciales como candidatas, lo que lo convierte en un algoritmo codicioso. El algoritmo se aplica ampliamente en tareas de decodificación de secuencias, como la traducción automática y el reconocimiento de voz, donde equilibra la calidad de la salida con la viabilidad computacional.
El núcleo de la búsqueda de haz consiste en mantener un conjunto de las soluciones parciales más prometedoras, llamado haz, y expandir solo esas en cada paso. Este enfoque contrasta con los métodos de búsqueda exhaustiva que consideran todas las rutas posibles, los cuales pueden ser computacionalmente prohibitivos para espacios de búsqueda grandes. Al podar los candidatos menos prometedores, la búsqueda de haz logra eficiencia a costa de sacrificar garantías de completitud y optimalidad.
Detalles algorítmicos
La búsqueda de haz opera utilizando una estrategia de búsqueda en anchura para construir su árbol de búsqueda. En cada nivel del árbol, genera todos los sucesores de los estados en el nivel actual y los ordena según su costo heurístico creciente. Sin embargo, solo almacena un número fijo de los mejores estados, denotado como β (el ancho del haz), en cada nivel. Solo esos estados se expanden a continuación, y el resto se descarta.
El ancho del haz β es un parámetro crítico que controla el equilibrio entre la calidad de la búsqueda y el uso de recursos. Un ancho de haz mayor retiene más estados, lo que reduce la probabilidad de podar soluciones óptimas y potencialmente mejora la calidad de la solución, pero también aumenta los requisitos de memoria y cálculo. Con un ancho de haz infinito, la búsqueda de haz se vuelve idéntica a la búsqueda de mejor primero. Por el contrario, con un ancho de haz de 1, se convierte en un algoritmo de escalada simple, que sigue codiciosamente solo la mejor ruta única.
El ancho del haz limita la memoria necesaria para realizar la búsqueda, lo que lo hace adecuado para sistemas con recursos limitados. Sin embargo, debido a esta poda, existe la posibilidad de que un estado objetivo sea descartado, lo que significa que la búsqueda de haz no garantiza encontrar una solución incluso si existe. Además, no es óptima, ya que no hay garantía de que la solución encontrada sea la mejor posible.
Desarrollo histórico
El primer uso de lo que se conocería como búsqueda de haz fue en el Sistema de Reconocimiento de Voz Harpy, presentado en una disertación de 1976. El procedimiento se denominó originalmente "modelo de locus de búsqueda", pero el término "búsqueda de haz" ya estaba en uso en 1977. Harpy se desarrolló en la Universidad Carnegie Mellon y representó un avance significativo en la tecnología de reconocimiento de voz, demostrando la utilidad práctica de la búsqueda heurística en aplicaciones del mundo real.
El desarrollo de la búsqueda de haz fue parte de una tendencia más amplia en la década de 1970 hacia algoritmos de búsqueda eficientes para sistemas de inteligencia artificial. Los investigadores reconocieron que los métodos de búsqueda exhaustiva eran a menudo poco prácticos para problemas complejos, lo que llevó al desarrollo de enfoques heurísticos que pudieran encontrar soluciones rápidamente. El éxito del sistema Harpy ayudó a establecer la búsqueda de haz como una técnica fundamental en el campo.
Aplicaciones en traducción automática
La búsqueda de haz se ha utilizado de manera prominente en sistemas de traducción automática, donde ayuda a seleccionar la mejor traducción entre muchos candidatos posibles. En la traducción automática estadística tradicional, cada parte de una oración se procesa y se generan muchas formas diferentes de traducir las palabras. La búsqueda de haz mantiene las mejores traducciones según sus estructuras de oración y descarta el resto, evaluando las traducciones restantes según un criterio dado para elegir la que mejor cumple los objetivos.
En la traducción automática neuronal moderna, que utiliza principalmente grandes modelos de lenguaje y arquitecturas transformer, la búsqueda de haz sigue siendo una estrategia de decodificación clave. Durante la generación, el modelo produce una distribución de probabilidad sobre los posibles siguientes tokens en cada paso. La búsqueda de haz mantiene múltiples secuencias parciales, expandiendo las más prometedoras según sus probabilidades acumuladas. Este enfoque produce traducciones de mayor calidad que la decodificación codiciosa, que selecciona solo el token más probable en cada paso.
La aplicación de la búsqueda de haz en la traducción automática ha sido ampliamente estudiada, con investigadores explorando diversas modificaciones para mejorar su rendimiento. Por ejemplo, la normalización de longitud se aplica a menudo para evitar un sesgo hacia secuencias más cortas, y se han desarrollado técnicas de búsqueda de haz diversa para fomentar la variedad entre las secuencias candidatas.
Variantes y extensiones
Se han desarrollado varias variantes de la búsqueda de haz para abordar sus limitaciones, particularmente su falta de completitud y optimalidad. Un enfoque combina la búsqueda de haz con la búsqueda en profundidad, dando lugar a la búsqueda de haz con pila y la búsqueda en profundidad con haz. Estos algoritmos son algoritmos en cualquier momento que encuentran soluciones subóptimas rápidamente, como la búsqueda de haz, y luego retroceden y continúan buscando hasta converger a una solución óptima.
Otra variante, la búsqueda de haz con discrepancia limitada, combina la búsqueda de haz con la búsqueda de discrepancia limitada. Este enfoque también produce algoritmos en cualquier momento que pueden mejorar las soluciones con el tiempo. En el contexto de la búsqueda local, la búsqueda de haz local es un algoritmo específico que comienza seleccionando β estados generados aleatoriamente y luego, para cada nivel del árbol de búsqueda, considera β nuevos estados entre todos los sucesores posibles de los estados actuales hasta alcanzar un objetivo.
Dado que la búsqueda de haz local a menudo termina en máximos locales, una solución común es elegir los siguientes β estados de manera aleatoria, con una probabilidad dependiente de la evaluación heurística de los estados. Este tipo de búsqueda se llama búsqueda de haz estocástica. Otras variantes incluyen la búsqueda de haz flexible y la búsqueda de haz con recuperación, que ajustan el ancho del haz dinámicamente o permiten la recuperación de malas decisiones de poda.
Papel en los sistemas modernos de IA
La búsqueda de haz desempeña un papel crucial en los sistemas modernos de inteligencia artificial, particularmente en aplicaciones de IA generativa. En los modelos de aprendizaje profundo, especialmente aquellos basados en la arquitectura transformer, la búsqueda de haz se utiliza durante la inferencia para generar secuencias como texto, código o voz. Empresas como OpenAI, Anthropic y Google DeepMind emplean la búsqueda de haz en sus modelos de lenguaje para producir salidas coherentes y contextualmente apropiadas.
La técnica también se utiliza en otras tareas de generación de secuencias, como el subtitulado de imágenes, el reconocimiento de voz y la predicción de estructuras de proteínas. En estas aplicaciones, la búsqueda de haz ayuda a equilibrar la calidad de la salida generada con los recursos computacionales requeridos. El ancho del haz se puede ajustar según los requisitos específicos de la tarea, donde anchos mayores proporcionan mejor calidad a costa de un mayor cálculo.
Propiedades teóricas
Las propiedades teóricas de la búsqueda de haz se han analizado en el contexto de la búsqueda heurística. Como algoritmo codicioso, toma decisiones localmente óptimas en cada paso, lo que puede conducir a soluciones globales subóptimas. El rendimiento del algoritmo depende en gran medida de la calidad de la función heurística utilizada para evaluar los estados. Una heurística bien diseñada puede guiar la búsqueda hacia buenas soluciones, mientras que una heurística deficiente puede hacer que el algoritmo pierda rutas óptimas.
El equilibrio entre el ancho del haz y la calidad de la solución es una consideración central en las aplicaciones prácticas. La investigación ha demostrado que aumentar el ancho del haz generalmente mejora la calidad de la solución, pero con rendimientos decrecientes. En algunos casos, un ancho de haz demasiado grande puede llevar a una generación excesiva y mayores costos computacionales sin mejoras significativas en la calidad. Por el contrario, un ancho de haz demasiado pequeño puede resultar en soluciones pobres debido a una poda excesiva.
Consideraciones computacionales
La complejidad computacional de la búsqueda de haz está determinada principalmente por el ancho del haz y el factor de ramificación del espacio de búsqueda. En cada nivel, el algoritmo genera sucesores para todos los estados en el haz, lo que requiere β × b operaciones, donde b es el factor de ramificación. La clasificación de estos sucesores añade un factor adicional de log(β × b) por nivel. Por lo tanto, la complejidad total es O(β × b × L × log(β × b)), donde L es la profundidad máxima de la búsqueda.
El uso de memoria está limitado por el ancho del haz, ya que solo se almacenan β estados en cada nivel. Esto hace que la búsqueda de haz sea particularmente atractiva para aplicaciones con recursos limitados, como sistemas integrados o procesamiento en tiempo real. La capacidad del algoritmo para equilibrar el uso de memoria y la calidad de la solución ha contribuido a su perdurable popularidad tanto en la investigación académica como en las aplicaciones industriales.
Comparación con otros métodos de búsqueda
La búsqueda de haz se compara a menudo con otros algoritmos de búsqueda, como la búsqueda codiciosa, la búsqueda de mejor primero y los métodos de decodificación basados en aprendizaje automático. La búsqueda codiciosa, que corresponde a la búsqueda de haz con un ancho de 1, es computacionalmente eficiente pero a menudo produce resultados de menor calidad. La búsqueda de mejor primero, que considera todas las soluciones parciales, puede encontrar soluciones óptimas pero requiere memoria proporcional a todo el espacio de búsqueda.
En el contexto de la generación de secuencias neuronales, la búsqueda de haz a veces se contrasta con métodos basados en muestreo, que seleccionan tokens aleatoriamente según sus distribuciones de probabilidad. El muestreo puede producir salidas más diversas pero puede sacrificar coherencia, mientras que la búsqueda de haz tiende a producir resultados más deterministas y de mayor calidad. Investigaciones recientes han explorado enfoques híbridos que combinan la búsqueda de haz con el muestreo para lograr un equilibrio entre calidad y diversidad.
Direcciones futuras
A principios de la década de 2020, la búsqueda de haz sigue siendo un área activa de investigación, particularmente en el contexto de los grandes modelos de lenguaje. Los investigadores están explorando estrategias de ancho de haz adaptativo que se ajustan según la confianza de las predicciones del modelo, así como métodos para incorporar restricciones externas en el proceso de búsqueda. El desarrollo de hardware más eficiente, como los aceleradores de IA especializados de empresas como NVIDIA y AMD, ha permitido anchos de haz mayores y estrategias de búsqueda más complejas en aplicaciones en tiempo real.
La integración de la búsqueda de haz con otras técnicas de IA, como el aprendizaje por refuerzo y las redes neuronales, también es un área de investigación en curso. Estos esfuerzos buscan mejorar la eficiencia y efectividad de la generación de secuencias en una amplia gama de aplicaciones, desde el procesamiento del lenguaje natural hasta el descubrimiento científico.