Ik ben op zoek naar een zeer eenvoudige mogelijke verklaring voor Baum Welch en Viterbi voor HMMs met een rechttoe rechtaan goed geannoteerd voorbeeld. Bijna alle uitleg die ik op het net vind, springt steevast vanaf het begin in een bijna volledig op jargon / symbool gebaseerde uitleg. De paar keer dat ze een voorbeeld hebben, wordt het meestal opzij geschoven of slecht geannoteerd (dwz het is onduidelijk hoe de symbolen en voorbeelden zijn aan elkaar gerelateerd). Ik heb dingen gehoord zoals sommige bronnen beweren dat Baum Welch is gebaseerd op het EM-algoritme en anderen zeggen dat het gebaseerd is op het algoritme voor vooruit achteruit en sommigen zeggen beide, dus ik zou graag details willen krijgen zoals dat is verholpen.
Het beste wat ik tot nu toe heb gevonden, is een video van 1 uur die hier is gepost en waarvan mensen zeiden dat deze geweldig was, maar die niet kan worden afgespeeld omdat Flash is verboden en een uitleg op Wikipedia met een opmerking ernaast dat het fout is .
Antwoord
Ik “ben op zoek naar een zo eenvoudig mogelijke verklaring voor Baum Welch en Viterbi voor HMMs …
-
Gezien de waargenomen gegevens, vindt het Baum-Welch-algoritme de waarschijnlijkheidsmaximaliserende parameters.
-
Gezien de waargenomen gegevens en de parameters, Het Viterbi-algoritme vindt de meest waarschijnlijke reeks verborgen toestanden.
Ik heb dingen gehoord zoals sommige bronnen die beweren dat Baum Welch dat is gebaseerd op het EM-algoritme …
Het Baum-Welch-algoritme is een speciaal geval van het EM-algoritme.
… en anderen zeggen dat het gebaseerd is op het algoritme voor vooruit achteruit.
De voorwaartse-achterwaartse decompositie is hoe je de “E-” -stap uitvoert (met behulp van de EM-terminologie). Het is specifiek voor verborgen Markov-modellen.
De paar keer dat ze een voorbeeld hebben, wordt het meestal opzij geschoven of slecht geannoteerd (dwz het is onduidelijk hoe de symbolen en het voorbeeld zijn aan elkaar gerelateerd)
Ik weet niet naar welke voorbeelden je kijkt, maar ik kan je vertellen dat er zijn veel goede die er zijn. Onthoud dat deze methoden al heel lang geleden zijn uitgevonden en dat ze nog steeds veel worden gebruikt . De Rabiner-koppeling waarnaar hierboven wordt verwezen, is waarschijnlijk de meest bekende, maar je moet er een vinden die je leuk vindt en die je zult blijven doorwerken. Ik zou je aanraden er een te zoeken met een voorbeeld met gegevens waarin je geïnteresseerd bent, en een notatie die je gevoel is leerbaar. Wat je ook vindt, het zal veel notatie hebben. Daar is geen ontkomen aan, dus je moet gewoon iets vinden waar je je in kunt vestigen.
Antwoord
Ik heb het perfecte papier voor jou: http://www.stat.columbia.edu/~liam/teaching/neurostat-fall17/papers/hmm/rabiner.pdf
Merk op dat er nieuwere BW-methoden zijn.
Poging tot eenvoudige verklaring voor Viterbi: het doel van viterbi is om een optimale opeenvolging van toestanden te vinden gedurende een bepaalde discrete tijdsperiode.
Begin met de initiële waarschijnlijkheid dat je in een toestand $ s $ op dat moment bent $ t = 0 $. Verhoog vervolgens $ t $ en zoek voor elke staat op dat moment ($ t = 1 $) de beste staat $ s $ op $ t-1 $ (het beste zoals in de reeks die de hoogste waarschijnlijkheid geeft ). Sla deze informatie op. Dat betekent dat voor elke staat $ s $ at $ t = 1 $ moet worden opgeslagen wat de beste staat $ s $ op $ t = 0 $ is. Bewaar ook de waarschijnlijkheid voor die (optimale) reeks.
Verhoog vervolgens $ t $ tot $ t = 2 $, en herhaal de procedure (waarbij de kansen voor elke staat $ s $ op $ t-1 $ de zojuist berekende beste kansen zijn voor die staat). Op het punt kom je op $ t = T $ (laatste punt in de tijd). Dan kies je gewoon de staat met de hoogste waarschijnlijkheid, en onthoudt voor elke staat telkens dat je de beste staat hebt opgeslagen voor $ t-1 $, dus neem de beste staat op $ t = T $ en werk dan altijd achteruit het kiezen van die opgeslagen optimale staat.
Om uit te werken wat het doet op een algemener niveau: Als je een set staten $ S $ hebt die allemaal kunnen worden gekozen gedurende een bepaalde tijd $ T $, een naïeve oplossing om de beste reeks te vinden, zou zijn om alle mogelijke reeksen op te sommen en vervolgens de waarschijnlijkheid voor elk ervan te berekenen (dat betekent dat het product van de toestand en de overgangskansen wordt berekend). De fout die men hier doet, is dat veel van de berekeningen worden gedupliceerd, u kunt bijvoorbeeld twee reeksen $ p_1, p_2 $ ($ p $ is een reeks toestanden) hebben, waarbij het enige verschil de eindtoestand is, maar met deze benadering berekent u de waarschijnlijkheden van de gedeelde toestanden voor zowel $ P (p_1) $ als $ P (p_2) $.
Door de iteratieve benadering te gebruiken die in viterbi wordt gebruikt, zijn er geen dubbele berekeningen, dus het zal duidelijk zijn veel efficiënter.
Reacties
- youtube.com/watch?v=6JVqutwtzmo Bovenstaande video legt grafisch uit wat Nimitz14 heeft uitgelegd (prachtig).