Viterbialgoritme

Viterbialgoritmen er en dynamisk programmeringsalgoritme som brukes til å finne den mest sannsynlige tilstandssekvensen i et system som kan modelleres som et Markov-kjede eller et skjult Markov-modell (HMM). Den egner seg for å konvertere en observerbar sekvens til den mest sannsynlige opprinnelsen, og den er særlig viktig i dekoding av konvolusjonskoder i digitale kommunikasjonslenker.

Algoritmen opererer på et trellisdiagram og beregner for hvert tidspunkt og hver tilstand en path metric som representerer den høyest sannsynlige stien som ender i tilstanden. Rekursjonen velger kontinuerlig den forrige tilstanden som gir den største akkumulerte metrikk. Ved hvert steg lagres en backpointer slik at den mest sannsynlige sekvensen kan rekonstrueres etter siste tidsenhet. Relevante implementasjoner bruker log-sannsynligheter for å forbedre numerisk stabilitet. Vanlig kompleksitet er O(T · S²), hvor T er antall tidssteg og S antall tilstander; minnebruken er ofte O(S) hvis bare forrige lag bevares.

Historie og anvendelser: Viterbialgoritmen ble introdusert av Andrew J. Viterbi i 1967 som en metode for optimal dekoding av konvolusjonskoder i digitale kommunikasjonskanaler. Den har siden blitt en standard i trådløse og kablede systemer, og den brukes også innen talegjenkjenning og i bioinformatiske applikasjoner som modellering av sekvenser med skjulte Markov-modeller.

Begrensninger og variasjoner: Algoritmen gir optimal løsning for riktig modell, men avhenger av korrekte overgangs- og emisjons sannsynligheter. Den kan være beregningskrevende for mange tilstander. For store modeller brukes ofte skalerings-, pruning- eller tilnærmingsvarianter, og noen systemer kombinerer Viterbi med andre metoder som Forward-Backward.