Busca em Feixe

O que é beam search?

Beam search é um algoritmo de busca heurística que expande o nó mais promissor em um conjunto limitado para explorar um grafo. Esta técnica usa um algoritmo de busca em largura para construir uma estrutura de dados em árvore e gerar sucessores do estado atual de cada nível.

Aplicações de software de processamento de linguagem natural (NLP) e modelos de reconhecimento de fala usam beam search como uma camada de tomada de decisão. O objetivo aqui é escolher a melhor saída para variáveis-alvo como o próximo caractere de saída ou a probabilidade máxima.

O algoritmo beam search seleciona tokens para uma posição específica em uma sequência com base na probabilidade condicional. Ele ajusta a largura do feixe (β) para escolher várias alternativas de hiperparâmetro n.

Diferente da busca gulosa, beam search amplia a busca para explorar possíveis encaixes para palavras em uma sequência. Beam search recebe esse nome pela forma como o algoritmo lança um feixe de busca amplo. 

Tipos de beam search

Beam search tem diferentes variantes, dependendo do algoritmo em uso, como busca em profundidade (DFS), busca de discrepância limitada e busca baseada em memória.

1. Busca em pilha de feixe é um algoritmo de busca que usa pilha de feixe como uma estrutura de dados para combinar busca em profundidade ou retrocesso cronológico com beam search. Os usuários também podem conectá-lo com um algoritmo de dividir e conquistar — uma técnica que quebra recursivamente um problema em dois ou mais subproblemas — para criar uma busca em pilha de feixe de dividir e conquistar.
2. Busca em profundidade com feixe usa um algoritmo de busca em profundidade para buscar estruturas de dados em grafo. Ele usa memória adicional ou uma pilha para rastrear nós explorados ao longo de um ramo específico e retroceder no grafo. 
3. Busca local com feixe rastreia ou mantém até k estados gerados aleatoriamente ou números de atribuições em vez de um. Ele escolhe k melhores vizinhos dos indivíduos atuais em cada estágio. O algoritmo relata sucesso apenas após encontrar uma atribuição satisfatória. Em caso de empates, ele escolherá valores aleatórios.
4. Busca estocástica com feixe seleciona k dos indivíduos aleatoriamente em vez dos melhores k indivíduos. Esta variação de beam search usa a probabilidade de ser escolhido como uma função da função de avaliação. Quanto melhor a avaliação, maiores as chances de ser escolhido.
5. Busca com feixe usando retrocesso de discrepância limitada (BULB) é um método de busca baseado em memória que resolve problemas de busca maiores dentro de um tempo de execução razoável. As buscas BULB fazem isso usando larguras de feixe maiores e encontrando caminhos mais curtos sem perder memória.
6. Busca com feixe flexível aumenta temporariamente a largura do feixe para incluir todos os nós filhos com o mesmo valor heurístico. 

Componentes do beam search

Beam search tem três componentes:

1. Um problema que pode ser um grafo ou pode conter um conjunto de nós representando um objetivo.
2. Regras heurísticas referem-se às diretrizes específicas do domínio do problema usadas para remover nós desfavoráveis da memória e focar no domínio do problema.
3. Memória que armazena o feixe, mas tem capacidade disponível limitada. Quando a memória está cheia, o algoritmo automaticamente exclui o nó mais custoso para evitar exceder o limite de memória. 

Benefícios de usar beam search 

Beam search tenta encontrar o complexo ótimo de forma heurística. Os benefícios de usar beam search para resolver problemas de otimização são:

• Redução de computação: Beam search usa um número limitado de nós ou recursos por vez. Como resultado, ele precisa de menos computação e consumo de memória em comparação com outros métodos de busca. Desenvolver regras heurísticas eficazes para poda é crucial para realizar essa vantagem, o que pode ser desafiador sem conhecimento de domínio.
• Melhoria em escolhas subótimas: A busca gulosa considera cada posição isoladamente. Ao contrário, beam search considera mais de uma opção por vez e melhora escolhas subótimas. 

Desvantagens de usar beam search 

A principal desvantagem de usar beam search é que os usuários podem não alcançar um objetivo ótimo no final. A maioria dos algoritmos de beam search termina em dois cenários: ou o usuário ainda não alcançou um nó objetivo e não há mais nós a serem explorados, ou alcançou o nó objetivo necessário. 

Além disso, beam search pode ser incompleto devido à sua natureza probabilística. Apesar dessas desvantagens, algoritmos de beam search têm tido sucesso em reconhecimento de fala, visão, planejamento e aprendizado de máquina. 

Usos do beam search

Beam search tem múltiplos usos em sistemas de tradução automática, NLP e reconhecimento de fala. Grandes sistemas com memória insuficiente para armazenar toda a árvore de busca frequentemente recorrem ao beam search para se manterem gerenciáveis.

Sistemas de tradução automática neural (NMT) usam beam search para escolher a melhor tradução e processar cada parte. Eles mantêm as melhores traduções com as estruturas de frase corretas e descartam o restante. O tradutor então verifica as traduções e escolhe a melhor que atende aos objetivos. Em 1976, o Sistema de Reconhecimento de Fala Harpy da Universidade Carnegie-Mellon foi o primeiro a usar um beam search. 

Beam search vs. busca gulosa vs. busca melhor-primeiro

Uma busca gulosa segue a heurística de resolução de problemas para construir uma solução gradualmente, um passo de cada vez. O sistema prioriza a seleção da próxima peça que oferece vantagens claras e imediatas. Algoritmos gulosos funcionam melhor para problemas onde é importante escolher soluções localmente ótimas.

Beam search otimiza a busca melhor-primeiro para reduzir os requisitos de memória.

Tanto buscas gulosas quanto beam search usam modelos de sequência para sequência para gerar saídas de sequência ou tokens de uma rede neural. No entanto, o primeiro avalia cada posição de forma independente, e o segundo considera mais de uma por vez.

Busca melhor-primeiro é uma técnica de busca em grafo que classifica e ordena soluções parciais com base em heurísticas. No entanto, beam search considera um número predeterminado de melhores soluções parciais como candidatas. É por isso que beam search é tratado como um algoritmo guloso. 

Procurando interpretar dados de maneira digerível? Explore o melhor software de geração de linguagem natural (NLG) para processar conjuntos de dados.