Como implementar um decodificador de Beam Search para processamento de linguagem natural

Como implementar um decodificador de Beam Search para processamento de linguagem natural

Tarefas de processamento de linguagem natural, como geração de legenda e tradução automática, envolvem a geração de sequências de palavras.

Os modelos desenvolvidos para esses problemas geralmente operam gerando distribuições de probabilidade no vocabulário de palavras de saída e cabe aos algoritmos de decodificação amostrar as distribuições de probabilidade para gerar as sequências de palavras mais prováveis.

Neste tutorial, você descobrirá a pesquisa gananciosa e os algoritmos de decodificação da pesquisa de feixe que podem ser usados ​​em problemas de geração de texto.

Depois de concluir este tutorial, você saberá:

  • O problema da decodificação em problemas de geração de texto.
  • O algoritmo de decodificador de pesquisa ganancioso e como implementá-lo em Python.
  • O algoritmo do decodificador de pesquisa de feixe e como implementá-lo em Python.

Comece seu projeto com meu novo livro Deep Learning for Natural Language Processing, incluindo tutoriais passo a passo e a Código-fonte Python arquivos para todos os exemplos.

Vamos começar.

  • Atualização maio / 2020: Corrigido bug na implementação de pesquisa de feixe (obrigado a todos que apontaram isso, e Constantin Weisser por sua correção limpa)
Como implementar o decodificador de Beam Search para processamento de linguagem natural

Como implementar o decodificador de Beam Search para processamento de linguagem natural
Foto de See1, Do1, Teach1, alguns direitos reservados.

Decodificador para Geração de Texto

Em tarefas de processamento de linguagem natural, como geração de legenda, resumo de texto e tradução automática, a previsão necessária é uma sequência de palavras.

É comum que os modelos desenvolvidos para esses tipos de problemas gerem uma distribuição de probabilidade sobre cada palavra no vocabulário para cada palavra na seqüência de saída. É então deixado para um processo de decodificação para transformar as probabilidades em uma seqüência final de palavras.

É provável que você encontre isso ao trabalhar com redes neurais recorrentes em tarefas de processamento de linguagem natural onde o texto é gerado como uma saída. A camada final no modelo de rede neural tem um neurônio para cada palavra no vocabulário de saída e uma função de ativação softmax é usada para produzir uma probabilidade de cada palavra no vocabulário ser a próxima palavra na sequência.

A decodificação da sequência de saída mais provável envolve pesquisar todas as sequências de saída possíveis com base em sua probabilidade. O tamanho do vocabulário costuma ser dezenas ou centenas de milhares de palavras, ou mesmo milhões de palavras. Portanto, o problema de pesquisa é exponencial no comprimento da sequência de saída e é intratável (NP-completo) para pesquisar completamente.

Na prática, os métodos de pesquisa heurística são usados ​​para retornar uma ou mais sequências de saída decodificadas "boas o suficiente" para uma determinada previsão.

Como o tamanho do gráfico de pesquisa é exponencial no comprimento da frase de origem, temos que usar aproximações para encontrar uma solução de forma eficiente.

- Página 272, Manual de Processamento de Linguagem Natural e Tradução Automática, 2011.

As sequências de palavras candidatas são pontuadas com base em sua probabilidade. É comum usar uma pesquisa gananciosa ou uma pesquisa de feixe para localizar sequências de texto candidatas. Veremos esses dois algoritmos de decodificação neste artigo.

Cada predição individual tem uma pontuação associada (ou probabilidade) e estamos interessados ​​na sequência de saída com pontuação máxima (ou probabilidade máxima) […] Uma técnica aproximada popular é usar predição gananciosa, pegando o item de maior pontuação em cada estágio. Embora essa abordagem seja frequentemente eficaz, obviamente não é a ideal. Na verdade, usar a pesquisa de feixe como uma pesquisa aproximada geralmente funciona muito melhor do que a abordagem gananciosa.

- Página 227, Métodos de redes neurais em processamento de linguagem natural, 2017.

Precisa de ajuda com Deep Learning for Text Data?

Faça meu curso intensivo de e-mail gratuito de 7 dias agora (com código).

Clique para se inscrever e também obter uma versão gratuita do Ebook em PDF do curso.

Comece Seu Crash-Course GRÁTIS Agora

Decodificador Greedy Search

Uma aproximação simples é usar uma pesquisa gananciosa que seleciona a palavra mais provável em cada etapa da sequência de saída.

Essa abordagem tem a vantagem de ser muito rápida, mas a qualidade das sequências de saída final pode estar longe de ser ideal.

Podemos demonstrar a abordagem de busca gananciosa para decodificar com um pequeno exemplo inventado em Python.

Podemos começar com um problema de previsão que envolve uma sequência de 10 palavras. Cada palavra é prevista como uma distribuição de probabilidade em um vocabulário de 5 palavras.

Assumiremos que as palavras foram codificadas por inteiro, de forma que o índice da coluna pode ser usado para pesquisar a palavra associada no vocabulário. Portanto, a tarefa de decodificação torna-se a tarefa de selecionar uma sequência de inteiros a partir das distribuições de probabilidade.

A função matemática argmax () pode ser usada para selecionar o índice de uma matriz que possui o maior valor. Podemos usar essa função para selecionar o índice de palavras mais provável em cada etapa da sequência. Esta função é fornecida diretamente no numpy.

O greedy_decoder () A função abaixo implementa essa estratégia de decodificador usando a função argmax.

Juntando tudo isso, o exemplo completo que demonstra o decodificador ganancioso está listado abaixo.

A execução do exemplo gera uma sequência de inteiros que podem ser mapeados de volta para palavras no vocabulário.

Decodificador de Beam Search

Outra heurística popular é a pesquisa de feixe que expande a pesquisa gananciosa e retorna uma lista das sequências de saída mais prováveis.

Em vez de escolher avidamente a próxima etapa mais provável à medida que a sequência é construída, a pesquisa de feixe expande todas as próximas etapas possíveis e mantém o k muito provavelmente, onde k é um parâmetro especificado pelo usuário e controla o número de feixes ou pesquisas paralelas por meio da sequência de probabilidades.

O algoritmo de busca de feixe local mantém o controle de k estados em vez de apenas um. Ele começa com k estados gerados aleatoriamente. Em cada etapa, todos os sucessores de todos os k estados são gerados. Se qualquer um for um objetivo, o algoritmo é interrompido. Caso contrário, ele seleciona os k melhores sucessores da lista completa e repete.

- Páginas 125-126, Artificial Intelligence: A Modern Approach (3ª edição), 2009.

Não precisamos começar com estados aleatórios; em vez disso, começamos com o k palavras mais prováveis ​​como o primeiro passo na sequência.

Os valores de largura de feixe comuns são 1 para uma pesquisa gananciosa e valores de 5 ou 10 para problemas de benchmark comuns em tradução automática. Larguras de feixe maiores resultam em melhor desempenho de um modelo, pois as várias sequências candidatas aumentam a probabilidade de corresponder melhor a uma sequência de destino. Este aumento de desempenho resulta em uma diminuição na velocidade de decodificação.

No NMT, novas sentenças são traduzidas por um decodificador de busca de feixe simples que encontra uma tradução que maximiza aproximadamente a probabilidade condicional de um modelo NMT treinado. A estratégia de busca de feixe gera a tradução palavra por palavra da esquerda para a direita, enquanto mantém um número fixo (feixe) de candidatos ativos em cada etapa de tempo. Ao aumentar o tamanho do feixe, o desempenho da tradução pode aumentar às custas da redução significativa da velocidade do decodificador.

- Estratégias de pesquisa de feixe para tradução automática neural, 2017.

O processo de pesquisa pode ser interrompido para cada candidato separadamente atingindo um comprimento máximo, atingindo um token de fim de sequência ou atingindo um limite de probabilidade.

Vamos tornar isso concreto com um exemplo.

Podemos definir uma função para realizar a busca do feixe para uma dada sequência de probabilidades e parâmetro de largura do feixe k. Em cada etapa, cada sequência candidata é expandida com todas as próximas etapas possíveis. Cada etapa do candidato é pontuada multiplicando-se as probabilidades. O k sequências com as probabilidades mais prováveis ​​são selecionadas e todos os outros candidatos são removidos. O processo então se repete até o final da sequência.

As probabilidades são números pequenos e a multiplicação de pequenos números cria números muito pequenos. Para evitar o estouro dos números de ponto flutuante, o logaritmo natural das probabilidades são somados, o que mantém os números maiores e gerenciáveis. Além disso, também é comum realizar a pesquisa minimizando a pontuação. Esse ajuste final significa que podemos classificar todas as sequências candidatas em ordem crescente por sua pontuação e selecionar o primeiro k como as sequências candidatas mais prováveis.

O beam_search_decoder () A função abaixo implementa o decodificador de pesquisa de feixe.

Você também pode estar interessado em