O algoritmo de Baum-Welch é um caso especial do algoritmo de maximização de expectativa (EM) usado para encontrar os parâmetros desconhecidos de um modelo oculto de Markov (HMM). É o método principal para inferência em HMMs, utilizando o algoritmo forward-backward para calcular as estatísticas para a etapa de expectativa. O algoritmo recebeu o nome de Leonard E. Baum e Lloyd R. Welch, que o desenvolveram com colegas no IDA Center for Communications Research em Princeton durante o final dos anos 1960 e início dos anos 1970.
Um modelo oculto de Markov descreve a probabilidade conjunta de uma coleção de variáveis aleatórias discretas ocultas e observadas. Ele depende da suposição de que a i-ésima variável oculta, dado 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 algoritmo EM para encontrar a estimativa de máxima verossimilhança dos parâmetros de um HMM dado um conjunto de vetores de características observados.
Descrição Formal
Seja \(X_t\) uma variável aleatória oculta discreta com \(N\) valores possíveis, representando \(N\) estados no total. As probabilidades de transição são assumidas como independentes do tempo, levando à definição da matriz de transição estocástica \(A = \{a_{ij}\} = P(X_t = j \mid X_{t-1} = i)\). A distribuição do estado inicial é dada por \(\pi_i = P(X_1 = i)\).
As variáveis de observação \(Y_t\) podem assumir um de \(K\) valores possíveis. A probabilidade de uma certa observação \(y_i\) no tempo \(t\) para o estado \(X_t = j\) é dada por \(b_j(y_i) = P(Y_t = y_i \mid X_t = j)\). Isso resulta na matriz \(N \times K\) \(B = \{b_j(y_i)\}\). Uma sequência de observações é dada por \(Y = (Y_1 = y_1, Y_2 = y_2, \ldots, Y_T = y_T)\). Assim, uma cadeia oculta de Markov pode ser descrita por \(\theta = (A, B, \pi)\). O algoritmo de Baum-Welch encontra um máximo local para \(\theta^* = \arg\max_\theta P(Y \mid \theta)\).
Etapas do Algoritmo
O algoritmo refina iterativamente as estimativas dos parâmetros. Na etapa de expectativa, ele calcula as probabilidades forward \(\alpha_t(i) = P(Y_1, \ldots, Y_t, X_t = i \mid \theta)\) e as probabilidades backward \(\beta_t(i) = P(Y_{t+1}, \ldots, Y_T \mid X_t = i, \theta)\) usando o algoritmo forward-backward. Essas são usadas para calcular as estatísticas suficientes esperadas, como a probabilidade de estar no estado \(i\) no tempo \(t\) e a probabilidade de transitar do estado \(i\) para o estado \(j\) entre os tempos \(t\) e \(t+1\).
Na etapa de maximização, o algoritmo atualiza os parâmetros \(A\), \(B\) e \(\pi\) para maximizar a log-verossimilhança esperada. As probabilidades de transição atualizadas são calculadas como a razão entre as contagens esperadas de transições do estado \(i\) para o estado \(j\) e as contagens esperadas de estar no estado \(i\). Da mesma forma, as probabilidades de emissão são atualizadas com base nas contagens esperadas de observações em cada estado. A distribuição do estado inicial é atualizada com base na probabilidade esperada de estar em cada estado no tempo 1.
O algoritmo continua iterando até a convergência, tipicamente quando a mudança na log-verossimilhança cai abaixo de um limiar. É garantido que ele converge para um máximo local da função de verossimilhança, embora não necessariamente o máximo global.
Estabilidade Numérica
O algoritmo de Baum-Welch é numericamente instável devido ao seu cálculo recursivo de probabilidades conjuntas. À medida que o número de variáveis cresce, essas probabilidades conjuntas se tornam cada vez menores, levando as recursões forward a rapidamente se aproximarem de valores abaixo da precisão da máquina. Isso pode causar underflow em implementações práticas, especialmente para sequências de observação longas. Para mitigar isso, as implementações frequentemente usam técnicas de escalonamento, como normalizar as variáveis forward e backward em cada passo de tempo, ou trabalhar no domínio logarítmico.
Aplicações
Uma das primeiras grandes aplicações de HMMs foi no campo do processamento de fala. Na década de 1980, os HMMs emergiram como uma ferramenta útil na análise de sistemas biológicos e informações, particularmente informações genéticas. Desde então, eles se tornaram uma ferramenta importante na modelagem probabilística de sequências genômicas. O algoritmo de Baum-Welch também é usado no processamento de linguagem natural, como etiquetagem de partes do discurso e reconhecimento de entidades nomeadas, bem como em biologia computacional para descoberta de genes e predição de estrutura de proteínas.
Conceitos Relacionados
O algoritmo de Baum-Welch está intimamente relacionado a outras técnicas de estimativa de parâmetros em aprendizado de máquina. É uma instância específica do algoritmo de maximização de expectativa, que é amplamente usado para modelos com variáveis latentes. O algoritmo forward-backward, que é um componente chave, também é usado em outras tarefas de inferência em HMMs, como o algoritmo de Viterbi para decodificação. No aprendizado profundo moderno, princípios semelhantes aparecem no treinamento de modelos com variáveis latentes, embora redes neurais frequentemente usem métodos baseados em gradiente como otimizador Adam e variantes de SGD em vez de EM. A conexão do algoritmo com aprendizado de máquina e inteligência artificial é fundamental, pois forneceu um quadro inicial para aprender a partir de dados sequenciais.