Estou procurando uma explicação o mais simples possível para Baum Welch e Viterbi para HMMs com um exemplo direto e bem anotado. Quase todas as explicações que encontro na rede invariavelmente saltam do início para uma explicação quase completamente baseada em jargão / símbolo. Nas poucas vezes que eles têm um exemplo, ele geralmente é colocado de lado ou mal anotado (ou seja, não está claro como os símbolos e os exemplos estão relacionados entre si). Eu ouvi coisas como algumas fontes alegando que Baum Welch é baseado no algoritmo EM e outras dizendo que é baseado no algoritmo de avanço para trás e alguns dizem que ambos, então eu gostaria de obter detalhes como isso esclareceu.
O mais próximo que encontrei até agora é um vídeo de 1 hora postado aqui que as pessoas disseram que era ótimo, mas não pode ser reproduzido porque o flash está banido e uma explicação na wikipedia que tem uma nota ao lado dizendo que está errado .
Resposta
Estou procurando uma explicação o mais simples possível para Baum Welch e Viterbi para HMMs …
-
Dados os dados observados, o algoritmo Baum-Welch encontra os parâmetros de maximização da probabilidade.
-
Dados os dados observados e os parâmetros, O algoritmo de Viterbi encontra a sequência mais provável de estados ocultos.
Eu ouvi coisas como algumas fontes alegando que Baum Welch é baseado no algoritmo EM …
O algoritmo Baum-Welch é um caso especial do algoritmo EM.
… e outros dizendo que é baseado no algoritmo de avanço para trás
A decomposição para frente e para trás é como você executa a etapa “E-” (usando a terminologia EM). É específico para modelos de Markov ocultos.
As poucas vezes em que eles têm um exemplo, ele é geralmente colocado de lado ou mal anotado (ou seja, não está claro como os símbolos e os exemplos estão relacionados entre si)
Não sei quais exemplos você está vendo, mas posso dizer que há são muitos bons por aí. Lembre-se de que esses métodos foram inventados há muito tempo e ainda são amplamente usados . O Rabiner vinculado acima é provavelmente o mais famoso, mas você tem que encontrar um de que goste para continuar trabalhando. Eu recomendo que você encontre um com um exemplo que tenha dados nos quais você está interessado e uma anotação de que você sinto que pode ser aprendido. O que quer que você encontre terá muita notação. Não há como contornar isso, então você só precisa encontrar algo em que possa se acomodar.
Resposta
Eu tenho o papel perfeito para você: http://www.stat.columbia.edu/~liam/teaching/neurostat-fall17/papers/hmm/rabiner.pdf
Observe que existem métodos de BW mais recentes.
Tentativa de explicação simples para Viterbi: o objetivo de viterbi é encontrar uma sequência ótima de estados durante algum período discreto de tempo.
Comece com as probabilidades iniciais de estar em um estado $ s $ no momento $ t = 0 $. Em seguida, aumente $ t $ e para cada estado naquele momento ($ t = 1 $), encontre o melhor estado $ s $ em $ t-1 $ (melhor como na sequência que dá a maior probabilidade ). Salve essas informações. Isso significa que, para cada estado $ s $ em $ t = 1 $, salve qual é o melhor estado $ s $ em $ t = 0 $. Salve também a probabilidade dessa sequência (ótima). Em seguida, aumente $ t $ para $ t = 2 $ e repita o procedimento (com as probabilidades para cada estado $ s $ em $ t-1 $ sendo as melhores probabilidades calculadas para esse estado). e ponto você alcançará $ t = T $ (último ponto no tempo). Então, você apenas escolhe o estado com a maior probabilidade e lembra para cada estado em cada vez que você salvou o melhor estado para $ t-1 $, então pegue o melhor estado em $ t = T $ e então trabalhe para trás sempre escolhendo aquele estado ótimo salvo.
Para elaborar sobre o que ele faz em um nível mais geral: Se você tiver um conjunto de estados $ S $ que podem ser todos selecionados ao longo de algum período de tempo $ T $, a A solução ingênua para encontrar a melhor sequência seria enumerar todas as sequências possíveis e então calcular a probabilidade de cada uma delas (isso significa calcular o produto do estado e as probabilidades de transição). O erro que se comete aqui é que muitos dos cálculos são duplicados, por exemplo, você poderia ter duas sequências $ p_1, p_2 $ ($ p $ é uma sequência de estados) onde a única diferença é o estado final, mas com Com esta abordagem, você está calculando as probabilidades dos estados compartilhados para $ P (p_1) $ e $ P (p_2) $.
Ao tomar a abordagem iterativa usada em viterbi, não há cálculos duplicados, então obviamente será muito mais eficiente.
Comentários
- youtube.com/watch?v=6JVqutwtzmo O vídeo acima explica graficamente o que Nimitz14 explicou (lindamente).