Viterbijev algoritam

Viterbijev algoritam predstavlja algoritam dinamičkog programiranja koji služi za pronalaženje najverovatnije sekvence skrivenih stanja, takozvanog Viterbijevog puta, koja proizilazi iz sekvence posmatranih događaja, posebno u kontekstu Markovljevih izvora informacija i Markovljevih skrivenih modela.

Algoritam je našao univerzalnu primenu u dekodiranju konvulcionih kodova, koji se koriste u CDMA i GSM digitalnim mobilnim telefonima, dajl-ap modemima, satelitima, komunikaciji u dubokom svemiru, i 802.11 bežičnom LAN-u. Takođe je opšte korišćen u prepoznavanju govora, sintezi govora, diarizaciji,^[1] računarskoj lingvistici i bioinformatici. Na primer, kod prepoznavanja govora zvučni signal se tretira kao posmatrana sekvenca događaja, a niska teksta se smatra "skrivenim uzrokom" zvučnog signala. Viterbijev algoritam pronalazi najverovatniju nisku teksta za dati zvučni signal.

Istorija

Viterbijev algoritam je dobio ime po Endruu Viterbiju, koji ga je predložio 1967. kao dekodirajući algoritam konvulcionih kodova za ispravljanje šuma u digitalnoj komunikaciji.^[2] Međutim, do nezavisnog otkrića algoritma došlo je čak sedam naučnika, među kojima i Nidlman i Vanš, kao i Vagner i Fišer.^[3]

"Viterbijev (put, algoritam)" je postao standardni izraz za primenu algoritama dinamičkog programiranja radi maksimizacije problema koji uključuju verovatnoću.^[3] Na primer, u statičkoj sintaksnoj analizi algoritam dinamičkog programiranja može da se iskoristi za otkrivanje jednog najverovatnijeg kontekstno slobodnog člana niske, koji se naziva „Viterbijev član“.^[4]^[5]^[6]

Algoritam

Pretpostavimo da nam je dat skriveni Markovljev model sa sledećim vrednostima: stanje prostora $S$ , inicijalna verovatnoća $\pi _{i}$ da je u stanju $i$ i tranziciona verovatnoća $a_{i,j}$ prelaska iz stanja $i$ u stanje $j$ . Recimo da posmatramo izlaz $y_{1},\dots ,y_{T}$ , najverovatnija sekvenca stanja $x_{1},\dots ,x_{T}$ koja proizvodi opažanje je data rekurentnim relacijama:^[7]

{\begin{array}{rcl}V_{1,k}&=&\mathrm {P} {\big (}y_{1}\ |\ k{\big )}\cdot \pi _{k}\\V_{t,k}&=&\max _{x\in S}\left(\mathrm {P} {\big (}y_{t}\ |\ k{\big )}\cdot a_{x,k}\cdot V_{t-1,x}\right)\end{array}}

Ovde je $V_{t,k}$ verovatnoća najverovatnije sekvence stanja $\mathrm {P} {\big (}x_{1},\dots ,x_{T},y_{1},\dots ,y_{T}{\big )}$ odgovorne za prvih $t$ opservacija koje imaju $k$ za svoje konačno stanje. Viterbijev put se može rekonstruisati čuvanjem pokazivača koji pamte koje stanje $x$ je korišćeno u drugoj jednačini. Neka je $\mathrm {Ptr} (k,t)$ funkcija koja vraća vrednost $x$ korišćenu da se izračuna $V_{t,k}$ ako je $t>1$ , ili $k$ ako je $t=1$ . Onda:

{\begin{array}{rcl}x_{T}&=&\arg \max _{x\in S}(V_{T,x})\\x_{t-1}&=&\mathrm {Ptr} (x_{t},t)\end{array}}

Ovde koristimo standardnu definiciju argumenta maksimuma (arg max).
Složenost ovog algoritma je $O(T\times \left|{S}\right|^{2})$ .

Primer

Posmatrajmo selo gde su svi seljani ili zdravi ili imaju groznicu i jedino seoski lekar može da utvrdi ko ima groznicu. Doktor dijagnostikuje groznicu tako što pita pacijente kako se osećaju. Seljani samo mogu da odgovore da se osećaju normalno, ošamućeno ili da im je hladno.

Doktor veruje da se zdravstveno stanje njegovih pacijenata ponaša kao diskretan Markovljev lanac. Postoje dva stanja, "zdrav" i "groznica", ali doktor ne može da ih posmatra direktno, ona su skrivena od njega. Svakog dana postoji izvesna mogućnost da će pacijent reći doktoru da se oseća "normalno", "ošamućeno" ili da mu je "hladno" u zavisnosti od svog zdravstvenog stanja.

Opservacije (normalno, ošamućeno, hladno) uz skriveno stanje (zdrav, groznica) formiraju skriveni Markovljev model i mogu se predstaviti u programerskom jeziku Pajton na sledeći način:

стања = ('Здрав', 'Грозница')
запажања = ('нормалано', 'хладно', 'ошамућено')
почетна_вероватноћа = {'Здрав': 0.6, 'Грозница': 0.4}
вероватноћа_преласка = {
   'Здрав' : {'Здрав': 0.7, 'Грозница': 0.3},
   'Грозница' : {'Здрав': 0.4, 'Грозница': 0.6}
   }
вероватноћа_емисије = {
   'Здрав' : {'нормално': 0.5, 'хладно': 0.4, 'ошамућено': 0.1},
   'Грозница' : {'нормално': 0.1, 'хладно': 0.3, 'ошамућено': 0.6}
   }

U ovom odlomku koda почетна_вероватноћа predstavlja lekarevo uverenje o tome u kome je stanju skrivenog Markovljevog modela bio pacijent kada ga je prvi put posetio (sve što zna je da je pacijent inače zdrav). Konkretna distribucija verovatnoće koja se ovde koristi nije ekvilibrijumska, koja je (za date verovatnoće prelaska) približno {'Здрав': 0.57, 'Грозница': 0.43}. вероватноћа_преласка predstavlja promenu zdravstvenog stanja u Markovljevom lancu. U ovom primeru postoji samo 30% šanse da će pacijent sutra imati groznicu ako je danas zdrav. вероватноћа_емисије predstavlja verovatnoću kako će se pacijent osećati svakog dana. Ako je zdrav, postoji 50% verovatnoće da će se osećati normalno, ako ima groznicu postoji 60% verovatnoće da se oseća ošamućeno.

Grafički prikaz datog skrivenog Markovljevog modela

Pacijent dolazi na pregled tri dana za redom i doktor otkriva da se on prvog dana osećao normalno, da mu je drugog dana hladno i da je trećeg dana ošamućen. Doktor ima pitanje: koja je najverovatnija sekvenca zdravstvenih stanja pacijenta koja bi objasnila ove opservacije? Odgovor na to pitanje daje Viterbijev algoritam.

def viterbi(obs, states, start_p, trans_p, emit_p):
    V = [{}]
    for st in states:
        V[0][st] = {"prob": start_p[st] * emit_p[st][obs[0]], "prev": None}
    # Позови Viterbi када је t > 0
    for t in range(1, len(obs)):
        V.append({})
        for st in states:
            max_tr_prob = max(V[t-1][prev_st]["prob"]*trans_p[prev_st][st] for prev_st in states)
            for prev_st in states:
                if V[t-1][prev_st]["prob"] * trans_p[prev_st][st] == max_tr_prob:
                    max_prob = max_tr_prob * emit_p[st][obs[t]]
                    V[t][st] = {"prob": max_prob, "prev": prev_st}
                    break
    for line in dptable(V):
        print line
    opt = []
    # Највећа вероватноћа
    max_prob = max(value["prob"] for value in V[-1].values())
    previous = None
    # Узми највероватније стање и његове прошле кораке
    for st, data in V[-1].items():
        if data["prob"] == max_prob:
            opt.append(st)
            previous = st
            break
    # Прати претходне кораке све до првог запажања
    for t in range(len(V) - 2, -1, -1):
        opt.insert(0, V[t + 1][previous]["prev"])
        previous = V[t][previous]["prev"]

    print 'Редослед стања је ' + ' '.join(opt) + ' са највећом вероватноћом од %s' % max_prob

def dptable(V):
    # Испиши талицу корака из речника 
    yield " ".join(("%12d" % i) for i in range(len(V)))
    for state in V[0]:
        yield "%.7s: " % state + " ".join("%.7s" % ("%f" % v[state]["prob"]) for v in V)

Funkcija viterbi ima sledeće argumente: obs je sekvenca zapažanja npr ['нормално', 'хладно', 'ошамућено']; states je skup skrivenih stanja; start_p je početna verovatnoća; trans_p su verovatnoće prelaska; i emit_p su verovatnoće emisije.

Radi jednostavnosti koda pretpostavimo da je sekvenca zapažanja obs neprazna i da su trans_p[i][j] i emit_p[i][j] definisani za sva stanja i,j.

U tekućem primeru Viterbijev algoritam se koristi na sledeći način:

витерби (запажања,
                   стања,
                   почетна_вероватноћа,
                   вероватноћа_преласка,
                   вероватноћа_емисије)

Izlaz je:

$ python витерби_пример.py
         0          1          2
Здрав: 0.30000 0.08400 0.00588
Грозница: 0.04000 0.02700 0.01512
Редослед стања је Здрав Здрав Грозница са највећом вероватноћом од 0.01512

Ovo otkriva da su zapažanja ['нормално', 'хладно', 'ошамућено'] najverovatnije generisana od stanja ['Здрав', 'Здрав', 'Грозница']. Drugim rečima, s obzirom na uočene aktivnosti najverovatnije je da je pacijent bio zdrav i prvog dana kada se osećao normalno kao i drugog dana kada se osećao hladno, a onda je trećeg dana dobio groznicu.

Rad Viterbijevog algoritma se može videti pomoću trelis dijagrama. Viterbijev algoritam je u suštini najkraći put kroz trelis dijagram. Klinički primer za trelis dijagram je pokazan na slici ispod gde je naznačen odgovarajući Viterbijev put.

Animacija trellis dijagrama za Viterbijev algoritam. Posle tri dana najverovatniji mogući put je ['Здрав', 'Здрав', 'Грозница']

Prilikom primene Viterbijevog algoritma treba napomenuti da mnogi jezici koriste aritmetiku u pokretnom zarezu -kao npr. p je malo, što može dovesti do potkoračenja u rezultatima. Uobičajena tehnika da se ovo izbegne je korišćenje algoritma verovatnoće tokom obračuna, istom tehnikom koja se koristi u logaritamskom brojčanom sistemu. Kada se algoritam zaustavi, precizna vrednost se može dobiti izvođenjem odgovarajućeg stepenovanja.

Ekstenzije

Generalizacija Viterbijevog algoritma, nazvana algoritmom max-sum (algoritam maksimalnog proizvoda) može se koristiti da se pronađu najverovatniji podaci svih ili nekih podskupova latentnih varijabli u velikom broju grafičkih modela, npr Bajesove mreže, Markovljeva slučajna polja i uslovna slučajna polja. Latentne varijable treba da budu povezane na način donekle sličan sa skrivenim Markovljevim modelom, sa ograničenim brojem veza između varijabli i neke vrste linearnih struktura između varijabli. Opšti algoritam obuhvata prosleđivanje poruka i suštinski je sličan algoritmu širenja poverenja (belief propagation algorithm), koji je generalizacija napred-nazad algoritma.

Algoritam koji se zove iterativno Viterbijevo dekodiranje može naći podniz opažanja koji najbolje odgovara (u proseku) datom skrivenom Markovljevom modelu. Koristi se za rad sa turbo kodom. Iterativno Viterbijevo dekodiranje radi pomoću iterativnog pozivanja modifikovanog Viterbijevog algoritma, ponovo procenjujući rezultat datoteke do konvergencije.

Alternativni algoritam lenji Viterbijev algoritam, predložen je nedavno. Za mnoge kodekse praktičnog interesa, pod razumnim poteškoćama, lenji dekoder (koristeću lenji Viterbijev algoritam) je mnogo brži od originalnog Viterbijevog dekodera (koji koristi Viterbijev algoritam). Ovaj algoritam radi tako što ne širi nikakve čvorove dok zaista ne bude potrebno i obično uspeva da izbegne puno posla (u softveru) od običnog Viterbijevog algoritma za isti rezultat -međutim nije moguće to reći i za hardver.

Pseudokod

S obzirom na prostor za zapažanje $O=\{o_{1},o_{2},\dots ,o_{N}\}$ , prostor za moguća stanja $S=\{s_{1},s_{2},\dots ,s_{K}\}$ , sekvenca zapažanja $Y=\{y_{1},y_{2},\ldots ,y_{T}\}$ , tranziciona matrica $A$ veličine $K\cdot K$ tako da $A_{ij}$ čuva tranzicionu verovatnoću stanja $s_{i}$ u stanje $s_{j}$ , emisiona matrica $B$ velicine $K\cdot N$ tako da $B_{ij}$ čuva verovatnoću zapažanja $o_{j}$ stanja $s_{i}$ , niz inicijalnih verovatnoća $\pi$ veličine $K$ tako da $\pi _{i}$ čuva verovatnoću $x_{1}==s_{i}$ . Mi kažemo da je put $X=\{x_{1},x_{2},\ldots ,x_{T}\}$ sekvenca slučaja koji generišu zapažanja $Y=\{y_{1},y_{2},\ldots ,y_{T}\}$ .

U ovom dinamičkom programiranju problem smo konstruisali u dve dvodimenzionalne tabele $T_{1},T_{2}$ veličine $K\cdot T$ . Svaki element od $T_{1}$ , $T_{1}[i,j]$ , čuva verovatnoću najverovatnijeg puta do sada ${\hat {X}}=\{{\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j}\}$ sa ${\hat {x}}_{j}=s_{i}$ koji generiše $Y=\{y_{1},y_{2},\ldots ,y_{j}\}$ . Svaki element iz $T_{2}$ , $T_{2}[i,j]$ čuva ${\hat {x}}_{j-1}$ , najverovatniji put do sada ${\hat {X}}=\{{\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j-1},{\hat {x}}_{j}\}$ , za $\forall j,2\leq j\leq T$ .

Punimo unose dve tabele $T_{1}[i,j],T_{2}[i,j]$ po rastućem redosledu $K\cdot j+i$ .

T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

, i

T_{2}[i,j]=\arg \max _{k}{(T_{1}[k,j-1]\cdot A_{ki}\cdot B_{iy_{j}})}

Treba napomenuti da $B_{iy_{j}}$ ne treba da se pojavi u drugim izrazima, jer je konstanta sa $i$ i $j$ , i ne utiče na argmax.

ULAZ

prostor zapažanja $O=\{o_{1},o_{2},\dots ,o_{N}\}$ ,
prostor mogućih stanja $S=\{s_{1},s_{2},\dots ,s_{K}\}$ ,
sekvenca zapažanja $Y=\{y_{1},y_{2},\ldots ,y_{T}\}$ tako da $y_{t}==i$ za trenutno zapažanje $t$ je $o_{i}$ ,
tranziciona matrica $A$ veličine $K\cdot K$ tako da $A_{ij}$ čuva tranuicionu verovatnoću stanja $s_{i}$ u stanje $s_{j}$ ,
emisiona matrica $B$ veličine $K\cdot N$ tako da $B_{ij}$ čuva verovatnoću zapažanja $o_{j}$ stanja $s_{i}$ ,
niz inicijalnih verovatnoća $\pi$ veličine $K$ tako da $\pi _{i}$ čuva verovatnoću $x_{1}==s_{i}$

IZLAZ

najverovatnija sekvenca slučaja je $X=\{x_{1},x_{2},\ldots ,x_{T}\}$

  function VITERBI(  $O, S, π, Y, A, B$  ) :  $X$ 
     for each state  $s i$  do
          $T 1 [i,1] \leftarrow π i \cdot B iy 1$ 
          $T 2 [i,1] \leftarrow 0$ 
     end for
     for  $i \leftarrow 2, 3,..., T$  do
         for each state  $s j$  do
              $T_{1}[j,i]\gets \max _{k}{(T_{1}[k,i-1]\cdot A_{kj}\cdot B_{jy_{i}})}$ 
              $T_{2}[j,i]\gets \arg \max _{k}{(T_{1}[k,i-1]\cdot A_{kj}\cdot B_{jy_{i}})}$ 
         end for
     end for
      $z_{T}\gets \arg \max _{k}{(T_{1}[k,T])}$ 
      $x T \leftarrow s z T$ 
     for  $i \leftarrow T, T-1,..., 2$  do
          $z i-1 \leftarrow T 2 [z i,i]$ 
          $x i-1 \leftarrow s z i-1$ 
     end for
     return  $X$ 
 end function

Vidi još

Reference

^ Xavier Anguera et Al, "Speaker Diarization: A Review of Recent Research" Arhivirano na sajtu Wayback Machine (12. maj 2016), retrieved 19. August 2010, IEEE TASLP
^ Forney, David (2005). „29 Apr 2005, G. David Forney Jr: The Viterbi Algorithm: A Personal History”. arXiv:cs/0504020v2  .
^ ^a ^b Jurafsky, Daniel; Martin, James H. (2014). Speech and Language Processing. Pearson Education International. str. 246.
^ Schmid, Helmut (2004). Efficient parsing of highly ambiguous context-free grammars with bit vectors (PDF). Proc. 20th Int'l Conf. on Computational Linguistics (COLING). doi:10.3115/1220355.1220379.
^ Klein, Dan; Manning, Christopher D. (2003). A* parsing: fast exact Viterbi parse selection (PDF). Proc. 2003 Conf. of the North American Chapter of the Association for Computational Linguistics on Human Language Technology (NAACL). str. 40—47. doi:10.3115/1073445.1073461. Arhivirano iz originala (PDF) 05. 03. 2016. g. Pristupljeno 19. 05. 2016.
^ Stanke, M.; Keller, O.; Gunduz, I.; Hayes, A.; Waack, S.; Morgenstern, B. (2006). „AUGUSTUS: Ab initio prediction of alternative transcripts”. Nucleic Acids Research. 34 (Web Server issue): W435—W439. PMC 1538822  . PMID 16845043. doi:10.1093/nar/gkl200.
^ Xing E, slide 11

Literatura

Jurafsky, Daniel; Martin, James H. (2014). Speech and Language Processing. Pearson Education International. str. 246.

Literatura

Viterbi, AJ (1967). „Error bounds for convolutional codes and an asymptotically optimum decoding algorithm”. IEEE Transactions on Information Theory. 13 (2): 260—269. S2CID 15843983. doi:10.1109/TIT.1967.1054010. (note: the Viterbi decoding algorithm is described in section IV.) Subscription required.
Feldman J, Abou-Faycal I, Frigo M (2002). „A fast maximum-likelihood decoder for convolutional codes”. Proceedings IEEE 56th Vehicular Technology Conference. 1. str. 371—375. ISBN 0-7803-7467-3. S2CID 9783963. doi:10.1109/VETECF.2002.1040367.
Forney, GD (1973). „The Viterbi algorithm”. Proceedings of the IEEE. 61 (3): 268—278. doi:10.1109/PROC.1973.9030. Subscription required.
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). „Section 16.2. Viterbi Decoding”. Numerical Recipes: The Art of Scientific Computing (3rd izd.). New York: Cambridge University Press. ISBN 978-0-521-88068-8. Arhivirano iz originala 11. 08. 2011. g. Pristupljeno 19. 05. 2016.
Rabiner, LR (1989). „A tutorial on hidden Markov models and selected applications in speech recognition”. Proceedings of the IEEE. 77 (2): 257—286. S2CID 13618539. doi:10.1109/5.18626. (Describes the forward algorithm and Viterbi algorithm for HMMs)
Forney, David (2005). „The Viterbi Algorithm: A Personal History”. Bibcode:2005cs........4020F. arXiv:cs/0504020v2  .

Implementacije

Spoljašnje veze

[1] Xavier Anguera et Al, "Speaker Diarization: A Review of Recent Research" Arhivirano na sajtu Wayback Machine (12. maj 2016), retrieved 19. August 2010, IEEE TASLP

[2] Forney, David (2005). „29 Apr 2005, G. David Forney Jr: The Viterbi Algorithm: A Personal History”. arXiv:cs/0504020v2  .

[slp-3] Jurafsky, Daniel; Martin, James H. (2014). Speech and Language Processing. Pearson Education International. str. 246.

[4] Schmid, Helmut (2004). Efficient parsing of highly ambiguous context-free grammars with bit vectors (PDF). Proc. 20th Int'l Conf. on Computational Linguistics (COLING). doi:10.3115/1220355.1220379.

[5] Klein, Dan; Manning, Christopher D. (2003). A* parsing: fast exact Viterbi parse selection (PDF). Proc. 2003 Conf. of the North American Chapter of the Association for Computational Linguistics on Human Language Technology (NAACL). str. 40—47. doi:10.3115/1073445.1073461. Arhivirano iz originala (PDF) 05. 03. 2016. g. Pristupljeno 19. 05. 2016.

[6] Stanke, M.; Keller, O.; Gunduz, I.; Hayes, A.; Waack, S.; Morgenstern, B. (2006). „AUGUSTUS: Ab initio prediction of alternative transcripts”. Nucleic Acids Research. 34 (Web Server issue): W435—W439. PMC 1538822  . PMID 16845043. doi:10.1093/nar/gkl200.

[7] Xing E, slide 11

[1]

[2]

[3]

[4]

[5]

[6]

[7]