Um mergulho profundo na marcação de parte da fala usando o algoritmo Viterbi

por Sachin Malhotra e Divya Godayal

Fonte: https://www.vocal.com/echo-cancellation/viterbi-algorithm-in-speech-enhancement-and-hmm/

Bem-vindo de volta, zelador!

Caso você tenha esquecido o problema que estávamos tentando resolver no artigo anterior, vamos revisá-lo para você.

Então tem esse garoto travesso, Peter, e ele vai incomodar seu novo zelador, você!

Como zelador, uma das tarefas mais importantes para você é colocar Peter na cama e ter certeza de que ele está dormindo. Uma vez que você o tenha metido, você quer ter certeza de que ele está realmente dormindo e não fazendo algum mal.

Você não pode, no entanto, entrar na sala novamente, pois isso certamente acordaria Peter. Tudo o que você pode ouvir são os ruídos que podem vir do quarto.

O quarto é tranquilo ou há barulho vindo do quarto. Estes são seus estados.

Tudo o que você tem como cuidador são:

  • um conjunto de observações, que é basicamente uma sequência contendo ruído ou calma ao longo do tempo, e
  • Um diagrama de estado fornecido pela mãe de Peter – que por acaso é um cientista neurológico – contém todos os diferentes conjuntos de probabilidades que você pode usar para resolver o problema definido abaixo.

O problema

Dado o diagrama de estados e uma sequência de N observações ao longo do tempo, precisamos informar o estado do bebê no momento atual. Matematicamente, temos observações N ao longo dos tempos t0, t1, t2 .... tN . Queremos descobrir se Pedro estaria acordado ou dormindo, ou melhor, qual estado é mais provável no tempo tN+1 .

Caso isso pareça grego para você, leia o artigo anterior para revisar o Modelo de Cadeia de Markov, Modelos de Markov Ocultos e Parte da Marcação de Fala.

O diagrama de estado que a mãe de Peter lhe deu antes de sair.

Nesse artigo anterior , modelamos brevemente o problema da marcação de parte da fala usando o modelo de Markov oculto.

O problema de Peter estar dormindo ou não é apenas um problema exemplar para uma melhor compreensão de alguns dos principais conceitos envolvidos nesses dois artigos. No núcleo, os artigos lidam com a solução do problema da marcação da parte da fala usando os modelos ocultos de Markov.

Portanto, antes de passar para o Algoritmo Viterbi , vamos primeiro examinar uma explicação muito mais detalhada de como o problema de marcação pode ser modelado usando HMMs.

Modelos gerativos e o modelo de canal barulhento

Muitos problemas no Processamento de Linguagem Natural são resolvidos usando uma abordagem de aprendizado supervisionado.

Problemas supervisionados no aprendizado de máquina são definidos da seguinte maneira. Nós assumimos exemplos de treinamento (x(1), y(1)) . . . (x(m) , y(m)) , onde cada exemplo consiste de uma entrada x (i) emparelhada com um rótulo y (i). Usamos X para nos referirmos ao conjunto de possíveis entradas e Y para nos referirmos ao conjunto de possíveis rótulos. Nossa tarefa é aprender uma função f: X ? Y que mapeia qualquer entrada x para um rótulo f (x).

Nos problemas de marcação, cada x (i) seria uma sequência de palavras X1 X2 X3 …. Xn(i) , e cada y (i) seria uma sequência de tags Y1 Y2 Y3 … Yn(i) (usamos n (i) para nos referirmos ao comprimento do i´th exemplo de treinamento). X se referiria ao conjunto de todas as seqüências x1. . . xn e Y seriam o conjunto de todas as sequências de tags y1. . . yn Nossa tarefa seria aprender uma função f: X ? Y que mapeia sentenças para seqüências de tags.

Uma abordagem intuitiva para obter uma estimativa para esse problema é usar probabilidades condicionais. p(y | x) que é a probabilidade da saída y dada uma entrada x. Os parâmetros do modelo seriam estimados usando as amostras de treinamento. Finalmente, dada uma entrada desconhecida x , gostaríamos de encontrar

f(x) = arg max(p(y | x)) ?y ? Y

Este aqui é o modelo condicional para resolver este problema genérico, dados os dados de treinamento. Outra abordagem que é adotada principalmente no aprendizado de máquina e processamento de linguagem natural é usar um modelo generativo .

Em vez de estimar diretamente a distribuição condicional p(y|x) , em modelos generativos, modelamos a probabilidade conjunta p(x, y) sobre todos os pares (x, y).

Podemos ainda decompor a probabilidade conjunta em valores mais simples usando a regra de Bayes:

  • p(y) é a probabilidade anterior de qualquer entrada pertencente ao rótulo y.
  • p(x | y) é a probabilidade condicional de entrada x dada a etiqueta y.

Podemos usar essa decomposição e a regra de Bayes para determinar a probabilidade condicional.

Lembre-se, queríamos estimar a função

 f (x) = arg max (p (y | x)) ?y ? Y 
 f (x) = arg max (p (y) * p (x | y)) 

A razão pela qual pulamos o denominador aqui é porque a probabilidade p(x) permanece a mesma, independente do rótulo de saída que está sendo considerado. E assim, de uma perspectiva computacional, ela é tratada como uma constante de normalização e é normalmente ignorada.

Modelos que decompõem uma probabilidade conjunta em termos de p(y) e p(x|y) são freqüentemente chamados de modelos de canal barulhento . Intuitivamente, quando vemos um exemplo de teste x, supomos que ele tenha sido gerado em duas etapas:

  1. primeiro, um rótulo y foi escolhido com probabilidade p (y)
  2. segundo, o exemplo x foi gerado a partir da distribuição p (x | y). O modelo p (x | y) pode ser interpretado como um “canal” que toma um rótulo y como sua entrada, e o corrompe para produzir x como sua saída.

Parte geradora do modelo de marcação de fala

Vamos supor um conjunto finito de palavras V e uma seqüência finita de tags K. Então o conjunto S será o conjunto de todas as seqüências, pares de tags <x1, x2, x3 ... xn, y1, y2, y3, ..., yn> tal que n> 0 ?x ? V e ?y ? K

Um modelo de tagging generativo é aquele em que

2

Dado um modelo generativo de marcação, a função sobre a qual falamos anteriormente, da entrada à saída, torna-se

Assim, para qualquer seqüência de entrada de palavras, a saída é a sequência de tag de maior probabilidade do modelo. Tendo definido o modelo generativo, precisamos descobrir três coisas diferentes:

  1. Como exatamente definimos a probabilidade do modelo generativo p(<x1, x2, x3 ... xn, y1, y2, y3, ..., yn>)
  2. Como estimamos os parâmetros do modelo e
  3. Como calculamos eficientemente

Vejamos como podemos responder a essas três perguntas lado a lado, uma vez para nosso problema de exemplo e, em seguida, para o problema real em questão: parte da marcação de fala.

Definindo o Modelo Gerativo

Vamos primeiro olhar como podemos estimar a probabilidade p(x1 .. xn, y1 .. yn) usando o HMM.

Podemos ter qualquer NMg HMM que considere eventos na janela anterior de tamanho N.

As fórmulas fornecidas a seguir correspondem a um modelo Trigram Hidden Markov.

Trigrama escondido Markov modelo

Um trigrama O modelo de Markov oculto pode ser definido usando

  • Um conjunto finito de estados.
  • Uma seqüência de observações.
  • q (s | u, v)
    Probabilidade de transição definida como a probabilidade de um estado “s” aparecer logo após observar “u” e “v” na sequência de observações.
  • e (x | s)
    Probabilidade de emissão definida como a probabilidade de fazer uma observação x, dado que o estado era s.

Então, a probabilidade do modelo generativo seria estimada como

Quanto ao problema do sono do bebê que estamos considerando, teremos apenas dois estados possíveis: que o bebê esteja acordado ou que esteja dormindo. O zelador pode fazer apenas duas observações ao longo do tempo. Ou há barulho vindo do quarto ou o quarto é absolutamente tranqüila. A sequência de observações e estados pode ser representada da seguinte forma:

Observações e estados ao longo do tempo para o problema do sono do bebê

Chegando à parte do problema de marcação de fala, os estados seriam representados pelas tags reais atribuídas às palavras. As palavras seriam nossas observações. A razão pela qual dizemos que as tags são nossos estados é porque, em um Modelo de Markov Oculta, os estados estão sempre ocultos e tudo o que temos são o conjunto de observações que são visíveis para nós. Ao longo de linhas similares, a sequência de estados e observações para a parte do problema de marcação de fala seria

Observações e estados ao longo do tempo para o problema de marcação de PDV

Estimando os parâmetros do modelo

Vamos supor que temos acesso a alguns dados de treinamento. Os dados de treinamento consistem em um conjunto de exemplos em que cada exemplo é uma seqüência que consiste nas observações, sendo cada observação associada a um estado. Dados esses dados, como estimamos os parâmetros do modelo?

A estimativa dos parâmetros do modelo é feita pela leitura de várias contagens fora do corpus de treinamento que temos e, em seguida, pelo cálculo das estimativas de máxima verossimilhança:

Probabilidade de Transição e Probabilidade de Emissão para um Trigrama HMM

Já sabemos que o primeiro termo representa a probabilidade de transição e o segundo termo representa a probabilidade de emissão. Vamos ver o que as quatro contagens diferentes significam nos termos acima.

  1. c (u, v, s) representa a contagem de trigramas dos estados u, v e s. Significa que representa o número de vezes que os três estados u, ve s ocorreram juntos nessa ordem no corpo de treinamento.
  2. c (u, v) seguindo linhas similares àquelas da contagem de trigramas, esta é a contagem de bigramas dos estados uev dada ao corpus de treinamento.
  3. c (s ? x) é o número de vezes no conjunto de treinamento que o estado e a observação x estão emparelhados entre si. E finalmente,
  4. c (s) é a probabilidade anterior de uma observação ser rotulada como estado s.

Vamos olhar primeiro para um conjunto de treinamento de amostra para o problema do brinquedo e ver os cálculos das probabilidades de transição e emissão usando o mesmo.

As marcações AZUL representam a probabilidade de transição, e RED é para cálculos de probabilidade de emissão.

Observe que, como o problema do exemplo tem apenas dois estados distintos e duas observações distintas, e dado que o conjunto de treinamento é muito pequeno, os cálculos mostrados abaixo para o problema de exemplo estão usando um bigrama. HMM em vez de um trigrama HMM.

A mãe de Peter mantinha um registro de observações e estados. E, assim, ela até lhe forneceu um corpus de treinamento para ajudá-lo a obter as probabilidades de transição e emissão.

Exemplo de Probabilidade de Transição:

Corpus de treinamentoCálculo para a Despertaça após a Despertai

Exemplo de Probabilidade de Emissão:

Cálculo de treinamentoCálculo para observar "Quiet" quando o estado está "Awake"

Isso foi bem simples, já que o conjunto de treinamento era muito pequeno. Vejamos um conjunto de treinamento de amostra para nosso problema real de marcação de parte da fala. Aqui podemos considerar um trigrama HMM e mostraremos os cálculos de acordo.

Usaremos as seguintes sentenças como um corpus de dados de treinamento (a palavra de notação / TAG significa palavra marcada com uma tag de parte da fala específica).

O conjunto de treinamento que temos é um conjunto de frases marcadas. Cada sentença consiste em palavras marcadas com sua parte correspondente de tags de fala. Por exemplo: – eat / VB significa que a palavra é “eat” e a parte da tag de fala nesta frase neste mesmo contexto é “VB”, isto é, Verb Phrase. Vejamos um cálculo de amostra para probabilidade de transição e probabilidade de emissão, assim como vimos para o problema do sono do bebê.

Probabilidade de Transição

Digamos que queremos calcular a probabilidade de transição q (IN | VB, NN). Para isso, vemos quantas vezes vemos um trigrama (VB, NN, IN) no corpus de treinamento nessa ordem específica. Em seguida, dividimos pelo número total de vezes que vemos o bigrama (VB, NN) no corpus.

Probabilidade de Emissão

Digamos que queremos descobrir a probabilidade de emissão e (an | DT). Para isso, vemos quantas vezes a palavra “an” é marcada como “DT” no corpus e dividimos pelo número total de vezes que vemos a tag “DT” no corpus.

Então, se você observar esses cálculos, isso mostra que calcular os parâmetros do modelo não é computacionalmente caro. Ou seja, não precisamos fazer várias passagens pelos dados de treinamento para calcular esses parâmetros. Tudo o que precisamos é de um monte de contagens diferentes, e uma única passagem sobre o corpus de treinamento deve nos fornecer isso.

Vamos seguir em frente e olhar para o passo final que precisamos examinar dado um modelo generativo. Esse passo é calcular eficientemente

Nós estaremos olhando para o famoso Algoritmo Viterbi para este cálculo.

Encontrando a seqüência mais provável – Algoritmo Viterbi

Finalmente, vamos resolver o problema de encontrar a sequência mais provável de rótulos, dado um conjunto de observações x1… xn. Ou seja, devemos descobrir

A probabilidade aqui é expressa em termos das probabilidades de transição e emissão que aprendemos a calcular na seção anterior do artigo. Só para lembrá-lo, a fórmula para a probabilidade de uma seqüência de rótulos dada uma sequência de observações sobre “n” intervalos de tempo é

Antes de olhar para um algoritmo otimizado para resolver este problema, vamos primeiro olhar para uma abordagem de força bruta simples para este problema. Basicamente, precisamos descobrir a sequência de rótulos mais provável, dado um conjunto de observações a partir de um conjunto finito de possíveis seqüências de rótulos. Vejamos o número total possível de sequências para um pequeno exemplo para nosso problema de exemplo e também para uma parte do problema de marcação de fala.

Digamos que tenhamos o seguinte conjunto de observações para o problema do exemplo.

 Ruído Silencioso 

Temos dois rótulos possíveis {Sleep and Awake}. Algumas das seqüências possíveis de rótulos para as observações acima são:

 Desperta Desperta Desperta Despertai 
 Despertai acordado Adormecido 
 Awake Awake Awake 
 Acordado adormecido 

No total, podemos ter ²³ = 8 seqüências possíveis. Isso pode não parecer muito, mas se aumentarmos o número de observações ao longo do tempo, o número de sequências aumentará exponencialmente. Este é o caso quando só tivemos duas etiquetas possíveis. E se tivermos mais? Como é o caso com parte da marcação de voz.

Por exemplo, considere a sentença

 o cachorro late 

e assumindo que o conjunto de tags possíveis é {D, N, V}, vamos ver algumas das possíveis seqüências de tags:

 DDD 
DDN
DDV
DND
DNN
DNV ... etc

Aqui, teríamos ³ = 27 sequências de tags possíveis. E como você pode ver, a frase foi extremamente curta e o número de tags não era muito grande. Na prática, podemos ter sentenças que podem ser muito maiores que apenas três palavras. Em seguida, o número de rótulos exclusivos à nossa disposição também seria alto demais para seguir essa abordagem de enumeração e encontrar a melhor sequência possível de tags dessa maneira.

Portanto, o crescimento exponencial no número de sequências implica que, para qualquer sentença de duração razoável, a abordagem da força bruta não funcionaria, já que levaria muito tempo para ser executada.

Em vez dessa abordagem de força bruta, veremos que podemos encontrar a sequência de tag mais provável usando um algoritmo de programação dinâmica conhecido como algoritmo de Viterbi.

Vamos primeiro definir alguns termos que seriam úteis na definição do próprio algoritmo. Nós já sabemos que a probabilidade de uma sequência de rótulos dada uma série de observações pode ser definida em termos da probabilidade de transição e da probabilidade de emissão. Matematicamente, é

Vamos olhar para uma versão truncada deste que é

e vamos chamar isso de custo de uma sequência de comprimento k.

Portanto, a definição de “r” é simplesmente considerar os primeiros k termos da definição de probabilidade em que k ? {1..n} e para qualquer sequência de rótulo y1… yk.

Em seguida, temos o conjunto S (k, u, v) que é basicamente o conjunto de todas as seqüências de rótulo de comprimento k que terminam com o bigrama (u, v), ou seja

Finalmente, definimos o termo ? (k, u, v) que é basicamente a sequência com o custo máximo.

A idéia principal por trás do Algoritmo de Viterbi é que podemos calcular os valores do termo ? (k, u, v) eficientemente de uma forma recursiva e memoizada. Para definir o algoritmo recursivamente, vamos examinar os casos básicos para a recursão.

 ? (0, *, *) = 1 
 ? (0, u, v) = 0 

Como estamos considerando um trigrama HMM, estaríamos considerando todos os trigramas como parte da execução do algoritmo de Viterbi.

Agora, podemos começar a primeira janela do trigrama a partir das três primeiras palavras da sentença, mas então o modelo perderia os trigramas onde a primeira palavra ou as duas primeiras palavras ocorreram independentemente. Por essa razão, consideramos dois símbolos especiais de início como * e, assim, nossa sentença se torna

 * * x1 x2 x3 ...... xn 

E o primeiro trigrama que consideramos então seria (*, *, x1) e o segundo seria (*, x1, x2).

Agora que temos todos os nossos termos em vigor, podemos finalmente olhar para a definição recursiva do algoritmo que é basicamente o coração do algoritmo.

Esta definição é claramente recursiva, porque estamos tentando calcular um termo ? e estamos usando outro com um valor menor de k na relação de recorrência para ele.

Cada sequência terminaria com um símbolo STOP especial. Para o modelo de trigramas, também teríamos dois símbolos de início especiais “*” no começo.

Dê uma olhada no pseudo-código para todo o algoritmo.

O algoritmo preenche primeiro os valores de ? (k, u, v) ao usar o método recursivo.
definição. Em seguida, ele usa a identidade descrita anteriormente para calcular a probabilidade mais alta de qualquer sequência.

O tempo de execução para o algoritmo é O (n | K | ³), portanto, é linear no comprimento da seqüência e cúbico no número de tags.

OBSERVAÇÃO: Estaríamos mostrando cálculos para o problema do sono do bebê e a parte do problema de marcação de fala baseada apenas em um bigram HMM. Os cálculos para o trigrama são deixados ao leitor para fazerem eles mesmos. Mas o código anexado ao final deste artigo é baseado em um trigrama HMM. É só que os cálculos são mais fáceis de explicar e retratar para o algoritmo Viterbi ao considerar um bigrama HMM em vez de um trigrama HMM.

Portanto, antes de mostrar os cálculos para o Algoritmo de Viterbi, vamos olhar para a fórmula recursiva baseada em um bigram HMM.

Este é extremamente semelhante ao que vimos antes para o modelo de trigramas, exceto que agora estamos apenas nos preocupando com o rótulo atual e o anterior, em vez de dois antes. A complexidade do algoritmo agora se torna O (n | K | ²).

Cálculos para o problema do sono do bebê

Agora que temos a fórmula recursiva pronta para o Algoritmo de Viterbi, vamos ver um exemplo de cálculo do mesmo primeiro para o problema de exemplo que tivemos, isto é, o problema do sono do bebê, e depois para a parte da versão de marcação de fala.

Note que quando estamos nesta etapa, ou seja, nos cálculos do algoritmo de Viterbi para encontrar a sequência de tags mais provável, dado um conjunto de observações ao longo de uma série de etapas de tempo, assumimos que as probabilidades de transição e de emissão já foram calculadas a partir do dado corpus. Vamos dar uma olhada em uma amostra de probabilidades de transição e emissão para o problema do sono do bebê que usaríamos em nossos cálculos do algoritmo.

O bebê começa por estar acordado e permanece no quarto por três momentos, t1. . . t3 (três iterações da cadeia de Markov). As observações são: silencioso, silencioso, ruído. Dê uma olhada no diagrama a seguir que mostra os cálculos para até duas etapas de tempo. O diagrama completo com todo o conjunto final de valores será mostrado posteriormente.

Nós não mostramos os cálculos para o estado de “adormecido” em k = 2 e os cálculos para k = 3 no diagrama acima para manter as coisas simples.

Agora que temos todos esses cálculos no lugar, queremos calcular a seqüência mais provável de estados em que o bebê pode estar ao longo das diferentes etapas de tempo dadas. Assim, para k = 2 e o estado de Awake, queremos saber o estado mais provável em k = 1 que passou para Awake em k = 2. (k = 2 representa uma sequência de estados de comprimento 3 começando de 0 e t = 2 significaria o estado no passo de tempo 2. Nos é dado o estado em t = 0 ie Despertai).

Claramente, se o estado na etapa de tempo 2 for AWAKE, então o estado na etapa de tempo 1 também teria sido AWAKE, conforme os cálculos apontam. Assim, o algoritmo de Viterbi não apenas nos ajuda a encontrar os valores de ? (k), ou seja, os valores de custo para todas as sequências usando o conceito de programação dinâmica, mas também nos ajuda a encontrar a sequência de tags mais provável uma seqüência de observações. O algoritmo, juntamente com o pseudo-código para armazenar os ponteiros é dado abaixo.

Cálculos para a parte do problema de marcação de fala

Vejamos um corpus um pouco maior para a parte da marcação de fala e o gráfico correspondente de Viterbi mostrando os cálculos e os back-pointers para o algoritmo de Viterbi.

Aqui está o corpus que vamos considerar:

Agora, dê uma olhada nas probabilidades de transição calculadas a partir desse corpus.

Aqui, q0 ? VB representa a probabilidade de uma sentença começar com a tag VB, que é a primeira palavra de uma sentença sendo marcada como VB. Da mesma forma, q0 ? NN representa a probabilidade de uma sentença começando com a tag NN. Observe que de 10 sentenças no corpus, 8 começam com NN e 2 com VB e, portanto, as probabilidades de transição correspondentes.

Quanto às probabilidades de emissão, idealmente devemos estar olhando para todas as combinações de tags e palavras no corpus. Como isso seria demais, consideraremos apenas probabilidades de emissão para a sentença que seria usada nos cálculos do Algoritmo de Viterbi.

 O tempo voa como uma flecha 

As probabilidades de emissão da sentença acima são:

Finalmente, estamos prontos para ver os cálculos para a sentença dada, probabilidades de transição, probabilidades de emissão e o corpus dado.

Então, isso é tudo que existe para o Algoritmo Viterbi?

Dê uma olhada no exemplo abaixo.

O balde abaixo de cada palavra é preenchido com as tags possíveis vistas ao lado da palavra no corpus de treinamento. A sentença dada pode ter as combinações de tags dependendo do caminho que tomamos. Mas há um porém. Você pode descobrir o que é isso?

Todas as combinações de caminhos de sequência

Você conseguiu descobrir?

Não??

Deixe-me dizer o que é.

Pode haver algum caminho no gráfico de computação para o qual não temos uma probabilidade de transição. Portanto, nosso algoritmo pode simplesmente descartar esse caminho e pegar o outro caminho.

No diagrama acima, descartamos o caminho marcado em vermelho, pois não temos q (VB | VB). O corpus de treinamento nunca tem um VB seguido por VB . Então, nos cálculos de Viterbi, acabamos pegando q (VB | VB) = 0. E se você estiver acompanhando o algoritmo de perto, você verá que um único 0 nos cálculos faria com que toda a probabilidade ou o custo máximo para uma sequência de tags / labels como 0.

Isto, no entanto, significa que estamos ignorando as combinações que não são vistas no corpus de treinamento.

É esse o caminho certo para abordar os exemplos do mundo real?

Considere um pequeno ajuste na frase acima.

O tempo voa como seta take

Nesta sentença não temos nenhum caminho alternativo. Mesmo se tivermos a probabilidade de Viterbi até alcançarmos a palavra “gostar”, não podemos prosseguir. Já que ambos q (VB | VB) = 0 e q (VB | IN) = 0. O que fazemos agora?

O corpus que consideramos aqui era muito pequeno. Considere qualquer corpus de tamanho razoável com muitas palavras e temos um grande problema de escassez de dados. Dê uma olhada abaixo.

Fonte: http://www.cs.pomona.edu/~kim/CSC181S08/lectures/Lec6/Lec6.pdf

Isso significa que podemos ter um potencial de 68 bilhões de bigramas, mas o número de palavras no corpus é de pouco menos de um bilhão. Esse é um grande número de probabilidades de transição zero para preencher. O problema da escassez de dados é ainda mais elaborado no caso de estarmos considerando os trigramas.

Para resolver esse problema de dispersão de dados, recorremos a uma solução chamada Suavização.

Suavização

A ideia por trás do Smoothing é justamente esta:

  1. Desconto – os valores de probabilidade existentes são um pouco e
  2. Realocar – esta probabilidade para os zeros

Dessa forma, redistribuimos os valores de probabilidade não zero para compensar as combinações de transição não vistas. Vamos considerar um tipo muito simples de técnica de suavização conhecida como Laplace Smoothing.

O alisamento de Laplace também é conhecido como suavização de uma contagem. Você vai entender exatamente por que ele passa por esse nome em um momento. Vamos revisar como os parâmetros para um modelo HMM trigrama são calculados, dado um corpus de treinamento.

Os possíveis valores que podem dar errado aqui são

  1. c(u, v, s) é 0
  2. c(u, v) é 0
  3. Recebemos uma palavra desconhecida na frase de teste e não temos tags de treinamento associadas a ela.

Tudo isso pode ser resolvido por meio de suavização. Então as contagens de alisamento de Laplace se tornariam

Aqui V é o número total de tags em nosso corpus e ? é basicamente um valor real entre 0 e 1. Ele age como um fator de desconto. Um valor ? = 1 nos daria muita redistribuição de valores de probabilidades. Por exemplo:

Demasiado peso é dado a trigramas invisíveis para ? = 1 e é por isso que a versão modificada do Laplace Smoothing acima mencionada é considerada para todas as aplicações práticas. O valor do fator de desconto deve ser variado de um aplicativo para outro.

Note que ? = 1 só criaria um problema se o tamanho do vocabulário for muito grande. Para um corpus menor, ? = 1 nos daria um bom desempenho para começar.

Uma coisa a notar sobre o Laplace Smoothing é que é uma redistribuição uniforme, ou seja, todos os trigramas que antes eram invisíveis teriam probabilidades iguais. Então, suponha que nos sejam dados alguns dados e observamos que

  • Freqüência do trigrama <deu, o, coisa> é zero
  • Freqüência do trigrama <deu, o, acha> também é zero
  • Distribuição uniforme sobre eventos invisíveis significa:
    P (coisa | deu, o) = P (pense | deu, o)

Isso reflete nosso conhecimento sobre o uso do inglês?
P (coisa | deu, o)> P (pense | deu, o) idealmente, mas distribuição uniforme usando alisamento de Laplace não considerará isto.

Isso significa que milhões de trigramas invisíveis em um enorme corpus teriam probabilidades iguais quando estão sendo considerados em nossos cálculos. Isso provavelmente não é a coisa certa a fazer. No entanto, é melhor do que considerar as probabilidades 0 que levariam a esses trigramas e, eventualmente, a alguns caminhos no gráfico de Viterbi serem completamente ignorados. Mas isso ainda precisa ser trabalhado e melhor.

Existem, no entanto, muitos tipos diferentes de técnicas de suavização que melhoram a técnica básica de suavização de Laplace e ajudam a superar esse problema de distribuição uniforme de probabilidades. Algumas dessas técnicas são:

  • Estimativa de Good-Turing
  • Alisamento de Jelinek-Mercer (interpolação)
  • Katz suavizando (backoff)
  • Alisamento de Witten-Bell
  • Desconto absoluto
  • Suavização de Kneser-Ney

Para ler mais sobre esses diferentes tipos de técnicas de suavização em mais detalhes, consulte este tutorial. Qual técnica de suavização escolher depende muito do tipo de aplicativo em questão, do tipo de dados que está sendo considerado e também do tamanho do conjunto de dados.

Se você tem acompanhado este longo artigo, então devo dizer

Fonte: https://sebreg.deviantart.com/art/You-re-Kind-of-Awesome-289166787

Vamos seguir em frente e observar uma pequena otimização que podemos fazer com o algoritmo Viterbi que pode reduzir o número de cálculos e que também faz sentido para muitos conjuntos de dados lá fora.

Antes disso, no entanto, observe o pseudo-código do algoritmo novamente.

Se olharmos de perto, podemos ver que, para cada trigrama de palavras, estamos considerando todos os possíveis conjuntos de tags. Isto é, se o número de tags for V, então estamos considerando o número de combinações para cada trigrama da sentença de teste.

Ignore o trigrama por enquanto e considere apenas uma única palavra. Nós estaríamos considerando todas as tags únicas para uma determinada palavra no algoritmo mencionado acima. Considere um corpus em que temos a palavra “kick”, que é associada a apenas duas tags, digamos {NN, VB} e o número total de tags exclusivas no corpus de treinamento é de cerca de 500 (é um enorme corpus).

Agora o problema aqui é aparente. Podemos acabar atribuindo uma tag que não faz sentido com a palavra em questão, simplesmente porque a probabilidade de transição do trigrama que termina na tag era muito alta, como no exemplo mostrado acima. Além disso, seria computacionalmente ineficiente considerar todas as 500 tags para a palavra “kick” se ela ocorrer apenas com duas tags exclusivas no corpo inteiro.

Assim, a otimização que fazemos é que, para cada palavra, em vez de considerar todas as tags exclusivas no corpus, apenas consideramos as tags com as quais ocorreu no corpus .

Isso funcionaria porque, para um corpus razoavelmente grande, uma determinada palavra ocorreria idealmente com todos os vários conjuntos de tags com os quais ela pode ocorrer (a maioria deles no mínimo). Então seria razoável simplesmente considerar apenas aquelas tags para o algoritmo Viterbi.

No que diz respeito ao algoritmo de decodificação de Viterbi, a complexidade ainda permanece a mesma porque estamos sempre preocupados com a complexidade do pior caso. No pior dos casos, cada palavra ocorre com cada tag única no corpus, e assim a complexidade permanece em O (n | V | ³) para o modelo de trigramas e O (n | V | ²) para o modelo de bigrama.

Para a implementação recursiva do código, por favor consulte

DivyaGodayal / HMM-POS-Tagger
HMM-POS-Tagger – Uma parte da implementação do Speech Tagger baseada em HMM usando o Laplace Smoothing e o Trigram HMMs github.com

A implementação recursiva é feita junto com o Laplace Smoothing.

Para a implementação iterativa, consulte

edorado93 / HMM-Part-of-Speech-Tagger
HMM-Part-of-Speech-Tagger – Uma parte do Speech Tagger baseado em HMM github.com

Essa implementação é feita com a técnica One-Count Smoothing, que leva a uma melhor precisão em comparação com o Laplace Smoothing.

Um monte de instantâneos de fórmulas e cálculos nos dois artigos são derivados daqui .

Deixe-nos saber como este blog ajudou você, e aponte os erros se você encontrar algum ao ler o artigo na seção de comentários abaixo. Além disso, por favor, recomende (batendo palmas) e espalhe o amor o máximo possível por este post se você acha que isso pode ser útil para alguém.

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *