Viterbi algorithm | AI slovník

Odborná definice

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í

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

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

Zdroje a redakční stopa

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.