Na engenharia elétrica, computação estatística e bioinformática, o algoritmo de Baum–Welch é um caso especial do algoritmo de maximização da expectativa (EM) usado para encontrar os parâmetros desconhecidos de um modelo oculto de Markov (HMM). Ele faz uso do algoritmo forward-backward para calcular as estatísticas para a etapa de expectativa. O algoritmo de Baum–Welch, o método principal para inferência em modelos ocultos de Markov, é numericamente instável devido ao seu cálculo recursivo de probabilidades conjuntas. À medida que o número de variáveis cresce, essas probabilidades conjuntas tornam-se cada vez menores, levando as recursões forward a se aproximarem rapidamente de valores abaixo da precisão da máquina.

História O algoritmo de Baum–Welch recebeu esse nome em homenagem aos seus inventores Leonard E. Baum e Lloyd R. Welch. O algoritmo e os Modelos Ocultos de Markov foram descritos pela primeira vez em uma série de artigos por Baum e seus colegas no Centro de Pesquisa em Comunicações do IDA, Princeton no final dos anos 1960 e início dos anos 1970. Uma das primeiras grandes aplicações dos HMMs foi no campo do processamento de fala. Na década de 1980, os HMMs estavam surgindo como uma ferramenta útil na análise de sistemas biológicos e informações, e em particular informação genética. Desde então, eles se tornaram uma ferramenta importante na modelagem probabilística de sequências genômicas.

Descrição Um modelo oculto de Markov descreve a probabilidade conjunta de uma coleção de variáveis aleatórias discretas "ocultas" e observadas. Ele se baseia na suposição de que a i-ésima variável oculta dada a (i − 1)-ésima variável oculta é independente das variáveis ocultas anteriores, e as variáveis de observação atuais dependem apenas do estado oculto atual.

O algoritmo de Baum–Welch usa o conhecido algoritmo EM para encontrar a estimativa de máxima verossimilhança dos parâmetros de um modelo oculto de Markov, dado um conjunto de vetores de características observados.

Seja uma variável aleatória discreta oculta com valores possíveis (ou seja, assumimos que existem estados no total). Assumimos que o é independente do tempo , o que leva à definição da matriz de transição estocástica independente do tempo

A distribuição de estado inicial (ou seja, quando ) é dada por

As variáveis de observação podem assumir um dos valores possíveis. Também assumimos que a observação dada o estado "oculto" é independente do tempo. A probabilidade de uma certa observação no tempo para o estado é dada por

Levando em conta todos os valores possíveis de e , obtemos a matriz onde pertence a todos os estados possíveis e pertence a todas as observações.

Uma sequência de observação é dada por .

Assim, podemos descrever uma cadeia de Markov oculta por . O algoritmo de Baum–Welch encontra um máximo local para (ou seja, os parâmetros do HMM que maximizam a probabilidade da observação).

Algoritmo Defina com condições iniciais aleatórias. Elas também podem ser definidas usando informações prévias sobre os parâmetros, se disponíveis; isso pode acelerar o algoritmo e também direcioná-lo para o máximo local desejado.

Procedimento Forward (Avançar) Seja , a probabilidade de ver as observações e estar no estado no tempo . Isso é encontrado recursivamente:

Como esta série converge exponencialmente para zero, o algoritmo sofrerá underflow numérico para sequências mais longas. No entanto, isso pode ser evitado em um algoritmo ligeiramente modificado escalando no procedimento forward e no procedimento backward abaixo.

Procedimento Backward (Retroceder) Seja que é a probabilidade do final da sequência parcial dado o estado inicial no tempo . Calculamos como:

Atualização Podemos agora calcular as variáveis temporárias, de acordo com o Teorema de Bayes:

que é a probabilidade de estar no estado no tempo dada a sequência observada e os parâmetros

que é a probabilidade de estar no estado e nos tempos e respectivamente dada a sequência observada e os parâmetros .

Os denominadores de e são os mesmos; eles representam a probabilidade de fazer a observação dados os parâmetros .

Os parâmetros do modelo oculto de Markov podem agora ser atualizados:

que é a frequência esperada gasta no estado no tempo .

que é o número esperado de transições do estado i para o estado j comparado ao número total esperado de transições começando no estado i, incluindo do estado i para ele mesmo. O número de transições começando no estado i é equivalente ao número de vezes que o estado i é observado na sequência de t = 1 a t = T − 1.

onde

é uma função indicadora, e é o número esperado de vezes que as observações de saída foram iguais a enquanto no estado sobre o número total esperado de vezes no estado .

Essas etapas são agora repetidas iterativamente até um nível desejado de convergência.

Nota: É possível ocorrer o sobreajuste (over-fit) em um conjunto de dados específico. Ou seja, . O algoritmo também não garante um máximo global.

Múltiplas sequências

O algoritmo descrito até agora assume uma única sequência observada . No entanto, em muitas situações, existem várias sequências observadas: . Neste caso, as informações de todas as sequências observadas devem ser usadas na atualização dos parâmetros , e . Assumindo que você calculou e para cada sequência , os parâmetros podem agora ser atualizados:

onde

é uma função indicadora

Exemplo Suponha que temos uma galinha da qual coletamos ovos ao meio-dia todos os dias. Agora, se a galinha botou ovos para coleta ou não, depende de alguns fatores desconhecidos que estão ocultos. Podemos, no entanto (por simplicidade) assumir que a galinha está sempre em um de dois estados que influenciam se a galinha bota ovos, e que este estado depende apenas do estado no dia anterior. Agora, não sabemos o estado no ponto de partida inicial, não sabemos as probabilidades de transição entre os dois estados e não sabemos a probabilidade de a galinha botar um ovo dado um estado específico. Para começar, primeiro deduzimos as matrizes de transição e emissão.

+Transição Estado 1 Estado 2 Estado 10.5 0.5 Estado 20.3 0.7+ Emissão Sem Ovos Ovos Estado 10.3 0.7 Estado 20.8 0.2+ Inicial Estado 10.2 Estado 20.8 Então, pegamos um conjunto de observações (E = ovos, N = sem ovos): N, N, N, N, N, E, E, N, N, N

Isso nos dá um conjunto de transições observadas entre os dias: NN, NN, NN, NN, NE, EE, EN, NN, NN

O próximo passo é estimar uma nova matriz de transição. Por exemplo, a probabilidade da sequência NN e do estado ser e depois é dada pelo seguinte:

Sequência observada Probabilidade mais alta de observar essa sequência se o estado for e depois Probabilidade mais alta de observar essa sequência NN 0.024 = 0.2 × 0.3 × 0.5 × 0.8 0.3584 , NN 0.024 = 0.2 × 0.3 × 0.5 × 0.8 0.3584 , NN 0.024 = 0.2 × 0.3 × 0.5 × 0.8 0.3584 , NN 0.024 = 0.2 × 0.3 × 0.5 × 0.8 0.3584 , NE 0.006 = 0.2 × 0.3 × 0.5 × 0.2 0.1344 , EE 0.014 = 0.2 × 0.7 × 0.5 × 0.2 0.0490 , EN 0.056 = 0.2 × 0.7 × 0.5 × 0.8 0.0896 , NN 0.024 = 0.2 × 0.3 × 0.5 × 0.8 0.3584 , NN 0.024 = 0.2 × 0.3 × 0.5 × 0.8 0.3584 , Total 0.22 2.4234

Assim, a nova estimativa para a transição de para é agora (referida como "Pseudo probabilidades" nas tabelas a seguir). Em seguida, calculamos as probabilidades de transição de para , de para e de para e normalizamos cada linha da matriz de transição para que as probabilidades de transições de um determinado estado inicial somem 1. Isso nos dá a matriz de transição atualizada:

+Matriz de Transição Antiga Estado 1 Estado 2 Estado 10.5 0.5 Estado 20.3 0.7+Nova Matriz de Transição (Pseudo Probabilidades) Estado 1 Estado 2 Estado 10.0598 0.0908 Estado 20.2179 0.9705+Nova Matriz de Transição (Após Normalização) Estado 1 Estado 2 Estado 10.3973 0.6027 Estado 20.1833 0.8167

Em seguida, queremos estimar uma nova matriz de emissão, Sequência Observada Probabilidade mais alta de observar essa sequência se for assumido que E vem de Probabilidade mais alta de observar essa sequência NE 0.1344 , 0.1344 , EE 0.0490 , 0.0490 , EN 0.0560 , 0.0896 , Total 0.2394 0.2730

A nova estimativa para a emissão de E vindo de agora é .

Isso nos permite calcular a matriz de emissão conforme descrito acima no algoritmo, somando as probabilidades para as respectivas sequências observadas. Em seguida, repetimos se N veio de e para se N e E vieram de e normalizamos.

+Matriz de Emissão Antiga Sem Ovos Ovos Estado 10.3 0.7 Estado 20.8 0.2+Nova Matriz de Emissão (Estimativas) Sem Ovos Ovos Estado 10.0404 0.8769 Estado 21.0000 0.7385+Nova Matriz de Emissão (Após Normalização) Sem Ovos Ovos Estado 10.0441 0.9559 Estado 20.5752 0.4248

Para estimar as probabilidades iniciais, assumimos que todas as sequências começam com o estado oculto e calculamos a probabilidade mais alta e depois repetimos para . Novamente, em seguida, normalizamos para fornecer um vetor inicial atualizado.

Finalmente repetimos esses passos até que as probabilidades resultantes convirjam satisfatoriamente.

Aplicações

Reconhecimento de fala Modelos Ocultos de Markov foram aplicados pela primeira vez ao reconhecimento de fala por James K. Baker em 1975. O reconhecimento de fala contínua ocorre pelos seguintes passos, modelados por um HMM. A análise de características é inicialmente realizada em características temporais e/ou espectrais do sinal de fala. Isso produz um vetor de observação. A característica é então comparada a todas as sequências das unidades de reconhecimento de fala. Essas unidades podem ser fonemas, sílabas ou unidades de palavras inteiras. Um sistema de decodificação de léxico é aplicado para restringir os caminhos investigados, de modo que apenas palavras no léxico (dicionário de palavras) do sistema sejam investigadas. Semelhante à decodificação do léxico, o caminho do sistema é ainda mais restrito pelas regras de gramática e sintaxe. Finalmente, a análise semântica é aplicada e o sistema emite o enunciado reconhecido. Uma limitação de muitas aplicações de HMM ao reconhecimento de fala é que o estado atual depende apenas do estado no passo de tempo anterior, o que não é realista para a fala, pois as dependências geralmente têm vários passos de tempo em duração. O algoritmo de Baum-Welch também tem extensas aplicações na resolução de HMMs usados no campo da síntese de fala.

Criptanálise O algoritmo de Baum-Welch é frequentemente usado para estimar os parâmetros de HMMs na decifração de informações ocultas ou com ruído e, consequentemente, é frequentemente usado em criptanálise. Na segurança de dados, um observador gostaria de extrair informações de um fluxo de dados sem conhecer todos os parâmetros da transmissão. Isso pode envolver engenharia reversa de um codificador de canal. HMMs e, como consequência, o algoritmo de Baum-Welch também foram usados para identificar frases faladas em chamadas VoIP criptografadas. Além disso, a criptanálise HMM é uma ferramenta importante para investigações automatizadas de dados de tempo de cache. Ela permite a descoberta automática do estado crítico do algoritmo, por exemplo, valores de chave.

Aplicações em bioinformática

Encontrando genes

Procariotos O software GLIMMER (Gene Locator and Interpolated Markov ModelER) foi um programa inicial de localização de genes usado para a identificação de regiões codificantes em DNA procarioto. O GLIMMER usa Modelos de Markov Interpolados (IMMs) para identificar as regiões codificantes e distingui-las do DNA não-codificante. A versão mais recente (GLIMMER3) demonstrou ter maior especificidade e precisão em comparação com os seus antecessores no que diz respeito à previsão dos locais de início da tradução, demonstrando uma precisão média de 99% na localização de pontos 3' em comparação com genes confirmados em procariotos.

Eucariotos