Qual è la differenza tra lalgoritmo avanti-indietro e quello di Viterbi?

Prima un po di background forse chiarisce le cose un po .

Quando si parla di HMM (Hidden Markov Models) ci sono generalmente 3 problemi da considerare:

1. Problema di valutazione

   • Il problema di valutazione risponde alla domanda: qual è la probabilità che una particolare sequenza di simboli sia prodotta da un particolare modello?
   • Per la valutazione utilizziamo due algoritmi: l algoritmo in avanti o algoritmo allindietro (NON confonderli con lalgoritmo in avanti-indietro).

2. Problema di decodifica

   • Il problema di decodifica risponde alla domanda: data una sequenza di simboli (le tue osservazioni) e un modello, qual è la sequenza di stati più probabile che ha prodotto la sequenza.
   • Per la decodifica utilizziamo l algoritmo di Viterbi .

3. Problema di addestramento

   • Il problema di addestramento risponde alla domanda: data una struttura del modello e un insieme di sequenze, trova il modello che meglio si adatta ai dati .
   • Per questo problema possiamo utilizzare i seguenti 3 algoritmi:
     1. MLE (stima di massima verosimiglianza)
     2. Formazione di Viterbi (NON confondere con la decodifica di Viterbi)
     3. Baum Welch = algoritmo avanti-indietro

Per riassumere, si utilizza lalgoritmo di Viterbi per problema di decodifica e Baum Welch / Forward-backward quando si addestra il modello su una serie di sequenze.

Baum Welch funziona nel modo seguente.

Per ogni sequenza nel set di sequenze di addestramento.

1. Calcola le probabilità in avanti con lalgoritmo in avanti
2. Calcola le probabilità a ritroso con lalgoritmo a ritroso
3. Calcola i contributi della sequenza corrente alle transizioni del modello, calcola i contributi della sequenza corrente alle probabilità di emissione del modello.
4. Calcola i nuovi parametri del modello (probabilità di inizio, probabilità di transizione, probabilità di emissione )
5. Calcola il nuova probabilità di log del modello
6. Interrompi quando la modifica della probabilità di log è inferiore a una determinata soglia o quando viene superato un numero massimo di iterazioni.

Se necessario una descrizione completa delle equazioni per la decodifica di Viterbi e lalgoritmo di addestramento fammelo sapere e posso indicarti la giusta direzione.

Commenti

• Ciao . Se salviamo il percorso, durante la valutazione utilizzando lalgoritmo di inoltro, rende ridondante luso dellalgoritmo di Viterbi nella decodifica?

Trovo che queste due diapositive seguenti da {2} siano davvero utili per situare il futuro -backward e algoritmi di Viterbi tra tutti gli altri algoritmi tipici utilizzati con HMM:

Note :

• $ x $ sono le emissioni osservate, $ \ pi $ sono i parametri dellHMM.
• percorso = una sequenza di emissioni
• decodifica = inferenza
• apprendimento = addestramento = stima dei parametri
• Alcuni documenti (ad esempio, {1}) affermano che Baum – Welch è lo stesso algoritmo avanti-indietro, ma Io agr ee con Masterfool e Wikipedia: Baum – Welch è un algoritmo di massimizzazione delle aspettative che utilizza lalgoritmo avanti-indietro. Le due illustrazioni distinguono anche Baum – Welch dallalgoritmo avanti – indietro.

Riferimenti:

• {1} Lember, Jüri e Alexey Koloydenko. “Lallenamento Viterbi adattato per i modelli Markov nascosti”. Bernoulli 14, n. 1 (2008): 180-206.
• {2} 6.047 / 6.878 Computational Biology: Genomes, Networks, Evolution (Fall 2012) Lecture 07 – HMMs II (2012-09-29) http://stellar.mit.edu/S/course/6/fa12/6.047/courseMaterial/topics/topic2/lectureNotes/Lecture07_HMMsIIb_6up/Lecture07_HMMsIIb_6up.pdf (Manolis Kellis):

La risposta di Morat è falsa su un punto: Baum -Welch è un algoritmo di massimizzazione delle aspettative, utilizzato per addestrare i parametri di un HMM. utilizza lalgoritmo avanti-indietro durante ogni iterazione. Lalgoritmo avanti-indietro è in realtà solo una combinazione degli algoritmi avanti e indietro: un passaggio in avanti, un passaggio allindietro. Da solo, lalgoritmo avanti-indietro non viene utilizzato per addestrare i parametri di un HMM, ma solo per smussare: calcolare le probabilità marginali di una sequenza di stati.

https://en.wikipedia.org/wiki/Forward%E2%80%93backward_algorithm

https://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm

@Yaroslav Bulatov aveva una risposta precisa. Vorrei aggiungere un esempio per dire al differenze tra gli algoritmi forward-backward e di Viterbi.

Supponiamo di avere un this HMM (dalla pagina HMM di Wikipedia). Nota, il modello è già fornito, quindi non cè attività di apprendimento dai dati qui.

Supponiamo che i nostri dati siano una sequenza di lunghezza 4. (Walk, Shop, Walk, Clean). Due algoritmi daranno cose diverse.

• Lalgoritmo in avanti allindietro darà il probabi lità di ogni stato nascosto . Ecco un esempio. Tieni presente che ogni colonna della tabella ammonta a $ 1 $.

• Lalgoritmo di Viterbi fornirà la sequenza più probabile di stati nascosti . Ecco un esempio. Nota, cè anche una probabilità associata a questa sequenza di stati nascosti. Questa sequenza ha max prob. su tutte le altre sequenze (ad esempio, $ 2 ^ 4 = 16 $ sequenze da tutte le Sunny a tutte le Rainy).

Eccone alcune R codice per la demo

library(HMM) # in education setting, # hidden state: Rainy and Sunny # observation: Walk, Shop, Clean # state transition P <- as.matrix(rbind(c(0.7,0.3), c(0.4,0.6))) # emission prob R <- as.matrix(rbind(c(0.1, 0.4, 0.5), c(0.6,0.3, 0.1))) hmm = initHMM(States=c("Rainy","Sunny"), Symbols=c("Walk","Shop", "Clean"), startProbs=c(0.6,0.4), transProbs=P, emissionProbs=R) hmm obs=c("Walk","Shop","Walk", "Clean") print(posterior(hmm,obs)) print(viterbi(hmm, obs))