Trabalho IA

2.1 Algoritmo conversão

Para converter um HMM para DW-HMM, devemos fazer um conjunto de super-estados, S, dos estados do HMM que representam probabilidades de emissão únicos. Quando S consiste um pequeno número de super-estados eo original do HMM estrutura de transição de estado é grande, a DW-HMM é mais eficientes do que os HMMs. Por exemplo, uma LT-HMM é uma boa candidato para converter em um DW-HMM, porque só tem um poucos estados com probabilidades de emissão única e contém grande dicionário trie. O seguinte explica o algoritmo de conversão de um HMM para DW-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 nulo, respectivamente [Lee e

Ng, 2005]. Começamos a otimizar parâmetros,? Θ, a partir de valores iniciais que são definidas de acordo com suas características. Por exemplo, 2Leet é definida como a modificação de texto escrito, ver (en.wikipedia.org/wiki/Leet) website. 3? Θ = {η,?, Ρ1, ρ2, ρ3, σ1, σ2, ψ1, ψ2, ψ3}. o parâmetro para a auto-transição deve ser significativamente menor do que o parâmetro de não-auto-transição, porque a inserção de caracteres é menos freqüente do que escrito corretamente letras. A partir do ponto de partida, nós otimizamos cada valor em? θ e obter? θ0 que é maximizada localmente em torno do primeiro Os valores dos parâmetros.

4 Os resultados experimentais

Em nossa experiência, podemos definir probabilidades de transição, P (qt | qt-1), e fazer Φ usando um dicionário Inglês (83552 palavras) e grandes volumes de dados de e-mail contra spam corpus. 4 Parâmetros do nosso modelo são otimizados com e-mails de spam contendo reais 65 linhas e 447 palavras. Realizamos um experimento com e-mails spam reais, que contêm 313 linhas e 2.131 palavras, incluindo a inserção, substituição, eliminação, segmentação e os tipos mistos de ofuscação. Quase todas as palavras são incluídos no léxico que usamos. A Tabela 2 apresenta alguns exemplos de vários tipos de ofuscação.

Tabela 2: Alguns exemplos de vários tipos de spam ofuscação.

As experiências são realizadas usando uma variedade de descodificação métodos. Usamos a um melhor e dois melhores pesquisas com vários largura de feixe e avaliar os resultados em termos de precisão e velocidade. A Tabela 3 mostra a precisão dos resultados da Spam deobfuscation quando dois melhor procurar com uma largura de feixe de cinco é usado. Representa que o nosso modelo funciona bem para a inserção, a substituição, de segmentação, e os tipos mistos de ofuscação. No entanto, considerando que o tipo de exclusão de ofuscação é rara em e-mails de spam real, nosso modelo não tem treinado bem.

Tabela 3: Precisão da DW-HMM com dois de busca e um melhor largura de feixe de cinco.

5 Conclusões

Nós apresentamos dinamicamente ponderada oculto de Markov modelo (DW-HMM) que reduziu drasticamente o número de estados quando alguns conjuntos de estados tinham probabilidades de emissão distintos. Os estados que partilham as mesmas probabilidades de emissão foram agrupadas em super-estados em DW-HMM. A transição de estado probabilidades em DW-HMM foram determinadas por um peso função que reflete as transições de estado originais mantidos na estrutura de dados Φ, em vez de uma grande transição matriz de probabilidade. Mostramos como um HMM é convertido em seu associado DW-HMM, mantendo um número pouco de super-sates. Temos aplicado DW-HMM para a tarefa de deobfuscation de spam, onde os LT-HMMwas substituído pelo DW-HMM. Os resultados experimentais mostraram que melhora a velocidade de 10 caracteres / s para 207 caracteres / s quando um algoritmo de Viterbi simples é aplicada. DW-HMM pode ser aplicada a diversas áreas onde um HMM altamente estruturado é usada com algumas probabilidades de emissão distintos. Por exemplo, nas áreas de fala e reconhecimento de escrita, o nosso modelo pode ser utilizado para tratar os grandes problemas de vocabulário. Podemos também usar DW-HMM, onde a estrutura de transição de estado muda freqüentemente, uma vez que é fácil de manter tais mudanças para DW-HMM.