Trabalho HMM

Algoritmo: Conversão de HMM para DW-HMM

1 Faça um conjunto de super-estados que têm emissão única probabilidades, S = {S1, S2,. . . , SK}, a partir de um HMM. em Nesta etapa, o número de estados do HMM é reduzida quanto mostrado na Figura 1.

2 Se houver loops (auto-transições) no HMM, adicionar super-estados adicionais. Por exemplo, se SI um laço, um estado sj adicional é feita. Isso torna possível distinguir entre a auto-transições e não auto-transições.

3 Construir a DW-HMM associado ao HMM usando super-estados nas transições S. estaduais são feitas entre super-estados se existe uma transição de estado em o HMM, a partir do qual os super-estados são feitas. para exemplo, na Figura 1, o 4-estado DW-HMM tem um estado transição de s2 para s3 porque q2 pode fazer a transição para q5 no HMM 8-estado.

4 Faça uma estrutura de dados, Φ, para definir uma função de peso, ω (s1: t), a qual dá a probabilidade de transição do DW-HMM. Φ contém a estrutura de transição do HMM e armazena as probabilidades de transição em cada nó. Ao fazer Φ, auto-transições no HMM são alteradas como mostrado na Figura 3 A super-estado que tem um laço transições para um super-estado adicionais feitas a partir do passo 2 e transições de estados em que o estado original vai. A estrutura de Φ e a estrutura de transição de estado do HMMmay ser diferente devido à auto-transições.

5 Definir probabilidades de emissão de superestados do DW-HMM que são os mesmos que os correspondentes estados do HMM.

Abaixo a representação de auto-transições de HMMs em Φ.

2.2 Condições de equivalência

No processo de conversão, DW-HMM conserva transição e as probabilidades de emissão. No entanto, há uma diferença entre HMM e sua associada DW-HMM quando usamos algoritmo de Viterbi simples. A Figura 4 ilustra treliça de DW-HMM em t = 3 eo estado s1, o único caminho estado {s1, s2, s1} que pode se propagar ainda mais uma vez {s1, s3, s1} tem uma probabilidade menor que {s1, s2, s1}. Portanto, o caminho {S1, S3, s1} é descartado em um passo de purga do algoritmo de Viterbi. No entanto, no caso de HMM mostrado na Figura 5, em t = 3 eo estado q1, ambos os caminhos do Estado {Q1, Q2, Q1} e {q1, q3, q1} pode propagar para a próxima vez instante porque existem dois estados Q1. Para garantir que os resultados da DW-HMM e HMM são o mesmo, adaptamos N-melhor busca por DW-HMMs e escolhemos o melhor caminho no último instante de tempo em treliça. Figura 6 mostra que os dois-melhor pesquisa faz duas hipóteses em s1 e t = 3 Ambos os caminhos do estado {s1, s2, s1} e {s1, s3, s1} são mantido para propagar mais além.

Trellis para DW-HMM.

Trellis para HMM.

Trellis para dois melhor pesquisa.

3.1 Decodificação

O algoritmo de Viterbi simples é usado para encontrar o melhor sequência de estado, s1: T = {S1, S2,. . . , São}, para uma dada observação y1 sequência: L = {y1, y2,. . . , IL}. Aqui, T e L pode ser diferente devido às transições nulos. A precisão e velocidade são configuráveis para DW-HMMby usando o N-melhor pesquisa e o algoritmo de busca de feixe. Nbest Pesquisa torna possível melhorar a precisão em que vários super-estados são preservados na fase de decodificação. para nosso modelo, selecionar o melhor caminho, em vez de N mais provável caminhos no instante de tempo final em treliça. No entanto, ele aumenta a complexidade computacional, a um custo do melhorada precisão. A complexidade do algoritmo de Viterbi é O (K2T), em que K é o número de estados e T é a duração da entrada. Quando é usado o N-melhor pesquisa, a complexidade de tempo é O ((NK) 2T). Para resolver o problema da velocidade, a pesquisa feixe algoritmo é usado e que melhora a velocidade sem perder muito rigor. Embora LT-HMMs também são capazes de acelerar -se por meio do algoritmo de busca de feixe, o grande número de estados limita a velocidade, em certa medida. Em nosso experimento, quando usamos o algoritmo Viterbi, o taxa de processo foi de 246 caracteres / seg. Nós acelerar o deobfuscation processo, a uma taxa de 2,038 caracteres / segundo, com um largura de feixe de 10, usando o algoritmo de busca de feixe. Quando se trata da complexidade da função de ponderação, ω (s1: t), é praticamente insignificante uma vez que tem trie O (M) complexidade onde M é o comprimento máximo de palavras no léxico.

Learning 3.2 Parâmetro

O nosso modelo tem vários parâmetros,? Θ 3, que deve ser otimizada. Nós nos adaptamos busca hillclimbing ganancioso para obter locais maxima. Usando um conjunto de treinamento que consiste em ofuscado palavras e respectivas respostas, encontramos o conjunto de parâmetros que localmente maximizar a probabilidade de log. ? θ0 = argmax? θ

? log n (P (s1: t, y1: t) | θ), onde (s1: t, y1: t) é um par de observações escondido no dados de treinamento e seqüência de estados de resposta correspondente. ? θ0 representa o conjunto de parâmetros optimizados localmente e n é o número de linhas do conjunto de treino. η e determinar a probabilidade de a auto-transição e de transição