Beam search é um algoritmo de busca heurística usado em ciência da computação para explorar um grafo expandindo o nó mais promissor em um conjunto limitado. É uma modificação da busca pelo melhor primeiro que reduz os requisitos de memória mantendo apenas um número predeterminado das melhores soluções parciais como candidatas, tornando-o um algoritmo guloso. O algoritmo é amplamente aplicado em tarefas de decodificação de sequências, como tradução automática e reconhecimento de fala, onde equilibra a qualidade da saída com a tratabilidade computacional.
A ideia central do beam search é manter um conjunto das soluções parciais mais promissoras, chamado de feixe, e expandir apenas aquelas em cada etapa. Essa abordagem contrasta com métodos de busca exaustiva que consideram todos os caminhos possíveis, o que pode ser computacionalmente proibitivo para grandes espaços de busca. Ao podar candidatos menos promissores, o beam search alcança eficiência enquanto sacrifica garantias de completude e otimalidade.
Detalhes Algorítmicos
O beam search opera usando uma estratégia de busca em largura para construir sua árvore de busca. Em cada nível da árvore, ele gera todos os sucessores dos estados no nível atual e os ordena em ordem crescente de custo heurístico. No entanto, ele armazena apenas um número predeterminado, denotado como β (a largura do feixe), dos melhores estados em cada nível. Apenas esses estados são expandidos em seguida, e o restante é descartado.
A largura do feixe β é um parâmetro crítico que controla o trade-off entre qualidade da busca e uso de recursos. Uma largura de feixe maior retém mais estados, reduzindo o número de candidatos podados e potencialmente melhorando a qualidade da solução, mas também aumenta os requisitos de memória e computação. Com uma largura de feixe infinita, nenhum estado é podado, e o beam search torna-se idêntico à busca pelo melhor primeiro. Por outro lado, uma largura de feixe de 1 corresponde a um algoritmo de hill-climbing, que segue guloso apenas o único melhor caminho.
A largura do feixe limita a memória necessária para realizar a busca, tornando-o adequado para sistemas grandes com memória limitada. No entanto, como um estado objetivo pode potencialmente ser podado, o beam search sacrifica a completude - a garantia de que um algoritmo terminará com uma solução se uma existir. Além disso, o beam search não é ótimo, o que significa que não há garantia de que encontrará a melhor solução possível.
Desenvolvimento Histórico
O primeiro uso do que viria a ser conhecido como beam search foi no Sistema de Reconhecimento de Fala Harpy, introduzido em uma dissertação de 1976. O procedimento foi originalmente referido como "modelo de locus de busca", mas o termo "beam search" já estava em uso em 1977. O Harpy foi desenvolvido na Universidade Carnegie Mellon e representou um avanço significativo na tecnologia de reconhecimento de fala, demonstrando a utilidade prática da busca heurística em aplicações do mundo real.
O desenvolvimento do beam search fez parte de uma tendência mais ampla na década de 1970 em direção a algoritmos de busca eficientes para sistemas de inteligência artificial. Pesquisadores reconheceram que métodos de busca exaustiva eram frequentemente impraticáveis para problemas complexos, levando ao desenvolvimento de abordagens heurísticas que pudessem encontrar boas soluções rapidamente. O sucesso do sistema Harpy ajudou a estabelecer o beam search como uma técnica fundamental no campo.
Aplicações em Tradução Automática
O beam search tem sido mais proeminentemente usado em sistemas de tradução automática, onde ajuda a selecionar a melhor tradução entre muitos candidatos possíveis. Na tradução automática estatística tradicional, cada parte de uma frase é processada, e muitas maneiras diferentes de traduzir as palavras são geradas. O beam search mantém as melhores traduções de acordo com suas estruturas de frase e descarta o restante, então avalia as traduções restantes de acordo com um critério dado para escolher aquela que melhor atende aos objetivos.
Na tradução automática neural moderna, que usa principalmente modelos de linguagem de grande escala e arquiteturas transformer, o beam search continua sendo uma estratégia de decodificação chave. Durante a geração, o modelo produz uma distribuição de probabilidade sobre os possíveis próximos tokens em cada etapa. O beam search mantém múltiplas sequências parciais, expandindo as mais promissoras com base em suas probabilidades cumulativas. Essa abordagem produz traduções de maior qualidade do que a decodificação gulosa, que seleciona apenas o token único mais provável em cada etapa.
A aplicação do beam search em tradução automática tem sido extensivamente estudada, com pesquisadores explorando várias modificações para melhorar o desempenho. Por exemplo, a normalização de comprimento é frequentemente aplicada para evitar viés em direção a sequências mais curtas, e técnicas de beam search diverso foram desenvolvidas para incentivar variedade entre as sequências candidatas.
Variantes e Extensões
Várias variantes do beam search foram desenvolvidas para abordar suas limitações, particularmente sua falta de completude e otimalidade. Uma abordagem combina beam search com busca em profundidade, resultando em beam stack search e busca em profundidade com feixe. Esses algoritmos são algoritmos anytime que encontram boas soluções, mas provavelmente sub-ótimas, rapidamente, como o beam search, então retrocedem e continuam a encontrar soluções melhoradas até a convergência para uma solução ótima.
Outra variante, beam search usando retrocesso com discrepância limitada (BULB), combina beam search com busca de discrepância limitada. Essa abordagem também produz algoritmos anytime que podem melhorar soluções ao longo do tempo. No contexto de busca local, o beam search local é um algoritmo específico que começa selecionando β estados gerados aleatoriamente e então, para cada nível da árvore de busca, considera β novos estados entre todos os sucessores possíveis dos atuais até alcançar um objetivo.
Como o beam search local frequentemente termina em máximos locais, uma solução comum é escolher os próximos β estados de maneira aleatória, com uma probabilidade dependente da avaliação heurística dos estados. Esse tipo de busca é chamado de beam search estocástico. Outras variantes incluem beam search flexível e beam search com recuperação, que ajustam a largura do feixe dinamicamente ou permitem recuperação de decisões de poda ruins.
Papel em Sistemas Modernos de IA
O beam search desempenha um papel crucial em sistemas modernos de inteligência artificial, particularmente em aplicações de IA generativa. Em modelos de aprendizado profundo, especialmente aqueles baseados na arquitetura transformer, o beam search é usado durante a inferência para gerar sequências como texto, código ou fala. Empresas como OpenAI, Anthropic e Google DeepMind empregam beam search em seus modelos de linguagem para produzir saídas coerentes e contextualmente apropriadas.
A técnica também é usada em outras tarefas de geração de sequências, como legendagem de imagens, reconhecimento de fala e predição de estrutura de proteínas. Nessas aplicações, o beam search ajuda a equilibrar a qualidade da saída gerada com os recursos computacionais necessários. A largura do feixe pode ser ajustada com base nos requisitos específicos da tarefa, com larguras maiores fornecendo melhor qualidade ao custo de maior computação.
Propriedades Teóricas
As propriedades teóricas do beam search foram analisadas no contexto da busca heurística. Como um algoritmo guloso, ele faz escolhas localmente ótimas em cada etapa, o que pode levar a soluções globais sub-ótimas. O desempenho do algoritmo depende fortemente da qualidade da função heurística usada para avaliar estados. Uma heurística bem projetada pode guiar a busca em direção a boas soluções, enquanto uma heurística pobre pode fazer com que o algoritmo perca caminhos ótimos.
O trade-off entre largura do feixe e qualidade da solução é uma consideração central em aplicações práticas. Pesquisas mostraram que aumentar a largura do feixe geralmente melhora a qualidade da solução, mas com retornos decrescentes. Em alguns casos, uma largura de feixe muito grande pode levar a supergeração e custos computacionais aumentados sem melhorias significativas de qualidade. Por outro lado, uma largura de feixe muito pequena pode resultar em soluções pobres devido à poda excessiva.
Considerações Computacionais
A complexidade computacional do beam search é principalmente determinada pela largura do feixe e pelo fator de ramificação do espaço de busca. Em cada nível, o algoritmo gera sucessores para todos os estados no feixe, o que requer β × b operações, onde b é o fator de ramificação. A ordenação desses sucessores adiciona um fator extra de log(β × b) por nível. A complexidade total é, portanto, O(β × b × L × log(β × b)), onde L é a profundidade máxima da busca.
O uso de memória é limitado pela largura do feixe, pois apenas β estados são armazenados em cada nível. Isso torna o beam search particularmente atraente para aplicações com memória limitada, como sistemas embarcados ou processamento em tempo real. A capacidade do algoritmo de equilibrar uso de memória e qualidade da solução contribuiu para sua popularidade duradoura tanto em pesquisa acadêmica quanto em aplicações industriais.
Comparação com Outros Métodos de Busca
O beam search é frequentemente comparado com outros algoritmos de busca, como busca gulosa, busca pelo melhor primeiro e métodos de decodificação baseados em aprendizado de máquina. A busca gulosa, que corresponde ao beam search com largura de feixe de 1, é computacionalmente eficiente, mas frequentemente produz resultados de menor qualidade. A busca pelo melhor primeiro, que considera todas as soluções parciais, pode encontrar soluções ótimas, mas requer memória proporcional a todo o espaço de busca.
No contexto de geração de sequências neurais, o beam search é às vezes contrastado com métodos baseados em amostragem, que selecionam tokens aleatoriamente com base em suas distribuições de probabilidade. A amostragem pode produzir saídas mais diversas, mas pode sacrificar coerência, enquanto o beam search tende a produzir resultados mais determinísticos e de maior qualidade. Pesquisas recentes exploraram abordagens híbridas que combinam beam search com amostragem para alcançar um equilíbrio entre qualidade e diversidade.
Direções Futuras
A partir do início dos anos 2020, o beam search continua sendo uma área ativa de pesquisa, particularmente no contexto de modelos de linguagem de grande escala. Pesquisadores estão explorando estratégias de largura de feixe adaptativa que se ajustam com base na confiança das predições do modelo, bem como métodos para incorporar restrições externas no processo de beam search. O desenvolvimento de hardware mais eficiente, como aceleradores de IA especializados de empresas como NVIDIA e AMD, permitiu larguras de feixe maiores e estratégias de busca mais complexas em aplicações em tempo real.
A integração do beam search com outras técnicas de IA, como aprendizado por reforço e redes neurais, também é uma área de investigação contínua. Esses esforços visam melhorar a eficiência e eficácia da geração de sequências em uma ampla gama de aplicações, desde processamento de linguagem natural até descoberta científica.