Odborná definice
Význam a odborné vymezení pojmu
Viterbi algorithm je dynamický programovací postup na nájdení najpravdepodobnejšej sekvence skrytých stavů v modeli s Markovovou strukturou, zejména v hidden Marků modelech. V každém časovém kroku uchovává nejlépe skóre pro každý stav a backpointer na předchozí rozhodnutí, místo enumerace všech možných ciest. Časová složitost je přibližně lineární v dlžke sekvence a kvadratická v počtu stavů při plných prechodoch. Algoritmus vrací jednu MAP cestu, ne marginálne pravděpodobnosti jednotlivých stavů.
Srozumitelné vysvětlení
Jak se pojem používá v praxi
Představte si větu, při které má každé slovo více možných gramatických značiek. Počet všech kombinací roste obrovsky. Viterbiho algoritmus postupuje zlava doprava a pro každou značku si ponechá pouze najlepšiu cestu, která k ní vede. Na konci vybere najúspešnejší posledný stav a pomocí uložených ukazovatelů se vrátí zpět k celé sekvenci. Stejný princip se používal při rozpoznávání řeči, tagování a dekódování komunikačných kanálů, když je třeba najít najpravdepodobnejší průběh.
Časté otázky
Otázky, které upřesňují význam
Jaký problém Viterbiho algoritmus řeší?
Najde jednu nejpravděpodobnější globálnu cestu skrytých stavů podle prechodových a emisných pravděpodobností, bez skúšání všech kombinací.
Jak se liší od forward algoritmu?
Forward sumarizuje pravděpodobnost všech ciest vedúcich k stavu. Viterbi používá maximum a uchovává pouze najlepšieho predchodcu pro finálnu MAP sekvenci.
Co jsou backpointers?
Pro každý čas a stav ukladají, ze kterého předchozího stavu prišlo nejlépe skóre. Po ukončení umožnia zrekonštruovat optimální cestu.
Používá se Viterbi i v neuronových modelech?
Ano například při CRF dekódování nad neurónovými príznakmi nebo v hybridných ASR systémech. Moderní generativní modely však často používají jiné dekódování.
Co pokud chceme více než jednu najlepšiu sekvenci?
Použije se k-best Viterbi, beam search nebo sampling podle modelu. Základní algoritmus uchovává pouze jednu najlepšiu cestu pro každý stav.
Související pojmy
Významové a tematické souvislosti
Zdroje a redakční stopa
Použitá východiska a odborná revize
- The Viterbi Algorithm, Proceedings of the IEEE Speech and Language Processing, Hidden Markov Models
Definícia je autorská odborná syntéza. Pri právnych a regulačných rozhodnutiach má prednosť aktuálne oficiálne znenie predpisu a posúdenie konkrétneho prípadu.