Odborná definícia
Význam a odborné vymedzenie pojmu
Viterbi algorithm je dynamický programovací postup na nájdenie najpravdepodobnejšej sekvencie skrytých stavov v modeli s Markovovou štruktúrou, najmä v hidden Markov modeloch. V každom časovom kroku uchováva najlepšie skóre pre každý stav a backpointer na predchádzajúce rozhodnutie, namiesto enumerácie všetkých možných ciest. Časová zložitosť je približne lineárna v dĺžke sekvencie a kvadratická v počte stavov pri plných prechodoch. Algoritmus vracia jednu MAP cestu, nie marginálne pravdepodobnosti jednotlivých stavov.
Zrozumiteľné vysvetlenie
Ako sa pojem používa v praxi
Predstavte si vetu, pri ktorej má každé slovo viac možných gramatických značiek. Počet všetkých kombinácií rastie obrovsky. Viterbiho algoritmus postupuje zľava doprava a pre každú značku si ponechá iba najlepšiu cestu, ktorá k nej vedie. Na konci vyberie najúspešnejší posledný stav a pomocou uložených ukazovateľov sa vráti späť k celej sekvencii. Rovnaký princíp sa používal pri rozpoznávaní reči, tagovaní a dekódovaní komunikačných kanálov, keď treba nájsť najpravdepodobnejší priebeh.
Časté otázky
Otázky, ktoré spresňujú význam
Aký problém Viterbiho algoritmus rieši?
Nájde jednu najpravdepodobnejšiu globálnu cestu skrytých stavov podľa prechodových a emisných pravdepodobností, bez skúšania všetkých kombinácií.
Ako sa líši od forward algoritmu?
Forward sumarizuje pravdepodobnosť všetkých ciest vedúcich k stavu. Viterbi používa maximum a uchováva iba najlepšieho predchodcu pre finálnu MAP sekvenciu.
Čo sú backpointers?
Pre každý čas a stav ukladajú, z ktorého predchádzajúceho stavu prišlo najlepšie skóre. Po ukončení umožnia zrekonštruovať optimálnu cestu.
Používa sa Viterbi aj v neurónových modeloch?
Áno napríklad pri CRF dekódovaní nad neurónovými príznakmi alebo v hybridných ASR systémoch. Moderné generatívne modely však často používajú iné dekódovanie.
Čo ak chceme viac než jednu najlepšiu sekvenciu?
Použije sa k-best Viterbi, beam search alebo sampling podľa modelu. Základný algoritmus uchováva iba jednu najlepšiu cestu pre každý stav.
Súvisiace pojmy
Významové a tematické súvislosti
Pojem v rozhodovaní
Odborné články, ktoré tento pojem používajú v praxi
Zdroje a redakčná stopa
Použité východiská a odborná revízia
- 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.