Sto cercando una spiegazione molto semplice possibile per Baum Welch e Viterbi per HMM con un esempio semplice e ben annotato. Quasi tutte le spiegazioni che trovo in rete saltano invariabilmente dallinizio in una spiegazione quasi completamente gergale / basata su simboli. Le poche volte che hanno un esempio di solito è spinto di lato o scarsamente annotato (cioè non è chiaro come i simboli e lesempio è correlato luno allaltro). Ho sentito cose come alcune fonti che affermano che Baum Welch si basa sullalgoritmo EM e altre che dicono che si basa sullalgoritmo in avanti allindietro e alcuni dicono entrambi, quindi “mi piacerebbe ottenere dettagli come è stato chiarito.
Il più vicino che ho trovato finora è un video di 1 ora pubblicato qui che la gente ha detto che era fantastico ma non è riproducibile perché il flash è vietato e una spiegazione su wikipedia che ha una nota accanto ad esso che dice che è sbagliato .
Risposta
Sto cercando una spiegazione molto semplice possibile per Baum Welch e Viterbi per HMM …
-
Dati i dati osservati, lalgoritmo di Baum-Welch trova i parametri che massimizzano la probabilità.
-
Dati i dati osservati e i parametri, il Lalgoritmo di Viterbi trova la sequenza più probabile di stati nascosti.
Ho sentito cose come alcune fonti che affermano che Baum Welch sia basato sullalgoritmo EM …
Lalgoritmo Baum-Welch è un caso speciale dellalgoritmo EM.
… e altri che dicono che si basa sullalgoritmo di andata e ritorno
La scomposizione avanti-indietro è il modo in cui si esegue il passaggio “E-” (utilizzando la terminologia EM). È specifico per i modelli di Markov nascosti.
Le poche volte che hanno un esempio di solito è spinto di lato o annotato male (cioè non è chiaro come i simboli e lesempio sono correlati tra loro)
Non so quali esempi stai guardando, ma posso dirti che lì sono molti buoni là fuori. Ricorda che questi metodi sono stati inventati molto tempo fa e sono ancora ampiamente utilizzati . Quello di Rabiner collegato sopra è probabilmente il più famoso, ma devi trovarne uno che ti piace su cui continuerai a lavorare. Ti consiglierei di trovarne uno con un esempio che contenga i dati che ti interessano e la notazione che sentire è apprendibile. Qualunque cosa trovi avrà molta notazione. Non cè modo di aggirarlo, quindi “devi solo trovare qualcosa in cui stabilirti.
Risposta
Ho la carta perfetta per te: http://www.stat.columbia.edu/~liam/teaching/neurostat-fall17/papers/hmm/rabiner.pdf
Tieni presente che esistono metodi BW più recenti.
Tentativo di spiegazione semplice per Viterbi: lobiettivo di Viterbi è trovare una sequenza ottimale di stati durante un periodo di tempo discreto.
Inizia con le probabilità iniziali di essere in uno stato $ s $ alla volta $ t = 0 $. Quindi aumenta $ t $ e per ogni stato in quel momento ($ t = 1 $), trova lo stato migliore $ s $ in $ t-1 $ (migliore come nella sequenza che dà la più alta probabilità ). Salva queste informazioni. Ciò significa che per ogni stato $ s $ a $ t = 1 $ salva qual è lo stato migliore $ s $ a $ t = 0 $. Salva anche la probabilità per quella sequenza (ottimale).
Quindi aumentare $ t $ a $ t = 2 $ e ripetere la procedura (con le probabilità per ogni stato $ s $ a $ t-1 $ che sono le migliori probabilità appena calcolate per quello stato). Il punto in cui raggiungerai $ t = T $ (ultimo punto nel tempo). Quindi scegli lo stato con la probabilità più alta e ricorda per ogni stato ogni volta che hai salvato lo stato migliore per $ t-1 $, quindi prendi lo stato migliore a $ t = T $ e poi procedi sempre a ritroso scegliendo quello stato ottimale salvato.
Per elaborare ciò che fa a un livello più generale: se hai un insieme di stati $ S $ che possono essere tutti selezionati per un certo periodo di tempo $ T $, un La soluzione ingenua per trovare la sequenza migliore sarebbe enumerare tutte le sequenze possibili e quindi calcolare la probabilità per ciascuna di esse (ciò significa calcolare il prodotto dello stato e le probabilità di transizione). Lerrore che si sta facendo qui è che molti calcoli sono duplicati, ad esempio potresti avere due sequenze $ p_1, p_2 $ ($ p $ è una sequenza di stati) dove lunica differenza è lo stato finale, ma con con questo approccio stai calcolando le probabilità degli stati condivisi sia per $ P (p_1) $ che per $ P (p_2) $.
Adottando lapproccio iterativo utilizzato a Viterbi, non ci sono calcoli duplicati, quindi ovviamente sarà molto più efficiente.
Commenti
- youtube.com/watch?v=6JVqutwtzmo Il video sopra spiega graficamente ciò che Nimitz14 ha spiegato (magnificamente).