Viterbiho algoritmus

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Viterbiho algoritmus je algoritmus dynamického programování pro hledání/nalezení nejpravděpodobnější posloupnosti skrytých stavů – nazývané Viterbiho cesta – jehož výsledkem je posloupnost pozorovaných událostí, především v kontextu Markovových informačních zdrojů a skrytých Markovových modelů.

Pojmy „Viterbiho cesta“ a „Viterbiho algoritmus“ se používají i pro další podobné algoritmy dynamického programování, které hledají nejpravděpodobnější vysvětlení určitého pozorování. Například algoritmus dynamického programování pro statistické parsování lze použít na hledání nejpravděpodobnějšího bezkontextového odvození (parse) řetězce, který se někdy nazývá „Viterbiho odvození“.

Algoritmus navrhl Andrew Viterbi v roce 1967 pro dekódování konvolučních kódů na digitálních komunikačních linkách se šumem[1]. Od té doby se používá při dekódování konvolučních kódů používaných v mobilních sítích CDMA a GSM i v běžných telefonních modemech, pro komunikaci se satelity a kosmickými sondami do vzdáleného vesmíru, i v bezdrátových sítích podle standardu 802.11. Často se používá i při rozpoznávání a syntéze řeči, v počítačové lingvistice, pro vyhledávání klíčových slov a v bioinformatice. Například při rozpoznávání řeči se zvukový signál považuje za pozorovanou posloupnost událostí, a textový řetězec za „skrytou příčinu“ zvukového signálu. Viterbiho algoritmus hledá nejpravděpodobnější řetězec textu k danému zvukovému signálu.

Algoritmus[editovat | editovat zdroj]

Předpokládejme, že je dán skrytý Markovův model (HMM) se stavovým prostorem S, pravděpodobnostmi \pi_i začátku ve stavu i (počáteční pravděpodobnosti), pravděpodobnostmi a_{i, j} pro přechod ze stavu i do stavu j (přechodové pravděpodobnosti). Pokud pozorujeme výstupní posloupnost y_1, \dots, y_T, pak nejpravděpodobnější posloupnost stavů x_1, \dots, x_T, která produkuje pozorovaný výstup, je dána rekurentními vztahy:[2]


\begin{array}{rcl}
V_{1,k} &=& \mathrm{P}\big( y_1 \ | \ k \big) \cdot \pi_k \\
V_{t,k} &=& \mathrm{P}\big( y_t \ | \ k \big) \cdot \max_{x \in S} \left( a_{x,k} \cdot V_{t-1,x}\right)
\end{array}

kde V_{t,k} je pravděpodobnost nejpravděpodobnější posloupnosti stavů odpovědné za prvních t pozorování, jejíž koncový stav je k. Pro získání Viterbiho cestu lze používat zpětné ukazatele, které zachycují, jaký stav x byl použit ve druhé rovnici. Nechť \mathrm{Ptr}(k,t) je funkce, která vrací hodnotu x použitou pro výpočet V_{t,k} pokud t > 1, nebo k pokud t=1. Pak:


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

(používáme standardní definici arg max).

Složitost tohoto algoritmu je O(T\times\left|{S}\right|^2).

Pseudokód[editovat | editovat zdroj]

Pokud je dán prostor pozorování  O=\{o_1,o_2,\dots,o_N\}, stavový prostor  S=\{s_1,s_2,\dots,s_K\} , posloupnost pozorování  Y=\{y_1,y_2,\ldots, y_T\} , matice přechodů  A velikosti  K\times K tak, že  A_{ij} obsahuje přechodovou pravděpodobnost přechodu ze stavu s_i do stavu s_j, výstupní matice  B velikosti  K\times N taková, že  B_{ij} obsahuje pravděpodobnosti pozorování o_j ze stavu s_i, pole počátečních pravděpodobností \pi velikosti K takové, že \pi_i obsahuje pravděpodobnost, že  x_1 ==  s_i . Nechť posloupnost  X=\{x_1,x_2,\ldots,x_T\} je cestou, která generuje pozorování  Y=\{y_1,y_2,\ldots, y_T\} .

V tomto problému dynamického programování vytváříme dvě dvourozměrné tabulky T_1, T_2 velikosti K\times T. Každý prvek T_1, T_1[i,j], obsahuje pravděpodobnost zatím nejpravděpodobnější cesty  \hat{X}=\{\hat{x}_1,\hat{x}_2,\ldots,\hat{x}_j\} s \hat{x}_j=s_i , která generuje  Y=\{y_1,y_2,\ldots, y_j\}. Každý prvek T_2 , T_2[i,j] , obsahuje \hat{x}_{j-1} zatím nejpravděpodobnější cesty  \hat{X}=\{\hat{x}_1,\hat{x}_2,\ldots,\hat{x}_{j-1},\hat{x}_j\} pro každé j, 2\leq j \leq T

Naplníme položky dvou tabulek  T_1[i,j],T_2[i,j] rostoucí posloupností K\cdot j+i .

T_1[i,j]=\max_{k}{(T_1[k,j-1]\cdot A_{ki}\cdot B_{iy_j})} , a
 T_2[i,j]=\arg\max_{k}{(T_1[k,j-1]\cdot A_{ki}\cdot B_{iy_j})}
   VSTUP:  Prostor pozorování  O=\{o_1,o_2,\dots,o_N\}, 
           stavový prostor  S=\{s_1,s_2,\dots,s_K\} , 
           posloupnost pozorování   Y=\{y_1,y_2,\ldots, y_T\}  taková, že  y_t==i  pokud 
             pozorování v čase  t  je  o_i ,
           matice přechodů  A  velikosti  K\cdot K  tak, že  A_{ij}  obsahuje přechodovou
             pravděpodobnost přechodu ze stavu  s_i  do stavu  s_j ,
           emission matrix  B  velikosti  K\cdot N  tak, že  B_{ij}  obsahuje pravděpodobnost
             pozorování  o_j  ze stavu  s_i , 
           pole počátečních pravděpodobností  \pi  velikosti  K  takové, že  \pi_i  obsahuje pravděpodobnost, že
              x_1 ==  s_i 
   VÝSTUP: Nejpravděpodobnější skrytá posloupnost stavů  X=\{x_1,x_2,\ldots,x_T\} 
A01 function VITERBI(O, S, π, Y, A, B): X
A02     for each state si do
A03         T1[i,1]πi\cdotBiy_1
A04         T2[i,1]←0
A05     end for
A06     for i2,3,...,T do
A07         for each state sj do
A08             T1[j,i]\max_{k}{(T_1[k,i-1]\cdot A_{kj}\cdot B_{jy_i})} 
A09             T2[j,i]\arg\max_{k}{(T_1[k,i-1]\cdot A_{kj}\cdot B_{jy_i})} 
A10         end for
A11     end for
A12     zT\arg\max_{k}{(T_1[k,T])} 
A13     xT←szT
A14     for iT,T-1,...,2 do
A15         zi-1←T2[zi,i]
A16         xi-1szi-1
A17     end for
A18     return X
A19 end function

Příklad[editovat | editovat zdroj]

Uvažujme malé zdravotní středisko ve vesnici. Lidé ve vesnici jsou buď zdraví nebo nemocní. Zda jsou nemocní, mohou zjistit tak, že se zeptají lékaře na středisku. Moudrý lékař stanovuje diagnózu tím, že se ptá pacientů, jak se cítí. Vesničané jenom odpovídají, že se cítí normálně, slabě (dizzy) nebo nastydlý (cold).

Předpokládejme, že určitý pacient dochází každý den na zdravotní středisko a sděluje lékaři, jak se cítí. Lékař se domnívá, že zdravotní stav tohoto pacienta se chová jako diskrétní Markovův řetězec. Zdraví pacienta   stavy, „Zdravý“ a „Nemocný“ nemůže lékař přímo pozorovat (jsou před ním skryté). Každý den je jistá pravděpodobnost, že pacient řekne lékaři, jak se cítí, což závisí na jeho zdravotním stavu: „normálně“, „nastydle (cold)“, nebo „špatně“. To jsou pozorování. Celý systém lze popsat jako skrytý Markovův model (HMM).

Lékař zná obecný stav zdraví vesničanů, a na jaké problémy si pacienti v průměru stěžují s nemocí nebo bez nemoci. Jinak řečeno parametry HMM jsou známé. Mohou být reprezentovány následujícím programem v jazyce Python:

states = ('Zdravý', 'Nemocný')
 
observations = ('normálně', 'nastydle', 'špatně')
 
start_probability = {'Zdravý': 0.6, 'Nemocný': 0.4}
 
transition_probability = {
   'Zdravý' : {'Zdravý': 0.7, 'Nemocný': 0.3},
   'Nemocný' : {'Zdravý': 0.4, 'Nemocný': 0.6},
   }
 
emission_probability = {
   'Zdravý' : {'normální': 0.5, 'nastydlý': 0.4, 'špatně': 0.1},
   'Nemocný' : {'normální': 0.1, 'nastydlý': 0.3, 'špatně': 0.6},
   }

V tomto kusu kódu start_probability reprezentuje lékařovo přesvědčení, v jakém stavu je HMM, když jej pacient navštívil poprvé (jediné, co ví, je, že pacient je obvykle zdravý). Určité rozložení pravděpodobnosti zde použité není vyrovnané, což je (dané přechodovou pravděpodobností) přibližně {'Zdravý': 0.57, 'Nemocný': 0.43}. transition_probability reprezentuje změnu zdravotních podmínek ve skrytém Markovově řetězci. V tomto příkladě je jenom 30% pravděpodobnost, že zítra bude pacient nemocný, když je dnes zdravý. emission_probability reprezentuje s jakou pravděpodobností se pacient cítí každý den. Pokud je zdravý, je 50% pravděpodobnost, že se cítí normálně; pokud je nemocný, je 60% pravděpodobnost, že se cítí špatně (dizzy).

Grafická reprezentace zadaného HMM

Pacient navštívil lékaře tři dny po sobě a lékař zjistil, že první den se pacient cítil normálně, druhý den se cítí nastydle (cold), třetí den se cítí špatně (dizzy). Lékař má otázku: jaká je nejpravděpodobnější posloupnost zdravotních stavů pacienta, které by vysvětlily tato pozorování? Odpověď dá Viterbiho algoritmus.

# Vizualizace Viterbiho algoritmu.
def print_dptable(V):
    print "    ",
    for i in range(len(V)): print "%7d" % i,
    print
 
    for y in V[0].keys():
        print "%.5s: " % y,
        for t in range(len(V)):
            print "%.7s" % ("%f" % V[t][y]),
        print
 
def viterbi(obs, states, start_p, trans_p, emit_p):
    V = [{}]
    path = {}
 
    # Initialize base cases (t == 0)
    for y in states:
        V[0][y] = start_p[y] * emit_p[y][obs[0]]
        path[y] = [y]
 
    # Run Viterbi for t > 0
    for t in range(1,len(obs)):
        V.append({})
        newpath = {}
 
        for y in states:
            (prob, state) = max([(V[t-1][y0] * trans_p[y0][y] * emit_p[y][obs[t]], y0) for y0 in states])
            V[t][y] = prob
            newpath[y] = path[state] + [y]
 
        # Don't need to remember the old paths
        path = newpath
 
    print_dptable(V)
    (prob, state) = max([(V[len(obs) - 1][y], y) for y in states])
    return (prob, path[state])

Funkce viterbi má následující argumenty: obs je posloupnost pozorování, např. ['normal', 'cold', 'dizzy']; states je množina skrytých stavů; start_p je start pravděpodobnost; trans_p jsou přechodové pravděpodobnosti; a emit_p jsou výstupní pravděpodobnosti. Pro jednoduchost kódu předpokládáme, že posloupnost pozorování obs je neprázdná a že trans_p[i][j] a emit_p[i][j] jsou definované pro všechny stavy i,j.

V našem příkladě se dopředný Viterbiho algoritmus používá takto:

def example():
    return viterbi(observations,
                   states,
                   start_probability,
                   transition_probability,
                   emission_probability)
print example()

To ukazuje, že pozorování ['normálně', 'nastydle', 'špatně'] byly s největší pravděpodobností generovány posloupností stavů ['Zdravý', 'Zdravý', 'Nemocný']. Jinými slovy, na základě pozorovaných aktivit, byl pacient s největší pravděpodobností první a druhý den zdravý (kdy se cítil normálně a nastydlý (cold) a třetí den nemocný.

Funkci Viterbiho algoritmu lze vizualizovat pomocí trellis diagramu. Viterbiho cesta je v zásadě nejkratší cesta tímto trellisem. Trellis pro příklad se zdravotním střediskem je níže; odpovídající Viterbiho cesta je tučně:

Animace trellis diagramu Viterbiho algoritmu. Po dni 3 je nejpravděpodobnější cesta ['Zdravý', 'Zdravý', 'Nemocný']

Při implementaci Viterbiho algoritmu je nutné zmínit, že mnoho jazyků používá aritmetiku s pohyblivou řádovou čárkou – pokud jsou hodnoty pravděpodobností malé, může dojít k podtečení výsledku. Obvyklá technika, jak se tomu vyhnout, je používat během celého výpočtu logaritmus pravděpodobnosti, tatáž technika použitá v Logarithmic Number System. Po skončení algoritmu lze získat správnou hodnotu pomocí exponenciální funkce.

Rozšíření[editovat | editovat zdroj]

Zobecnění Viterbiho algoritmu nazývané max-sum algoritmus (nebo max-product algoritmus) lze použít pro nalezení nejpravděpodobnějšího přiřazení všech nebo určitých podmnožinách skrytých proměnných ve velkém množství grafických modelů, např. Bayesovské sítě, Markov náhodná pole a podmíněná náhodná pole. Skryté proměnné musí být obecně propojeny nějakým způsobem na HMM, s omezeným počtem spojení mezi proměnnými a určitým typem lineární struktury mezi proměnnými. Obecný algoritmus využívá mechanismus předávání zpráv a v zásadě se podobá algoritmu belief propagation (který je zobecněním forward-backward algoritmu).

Pomocí algoritmu nazývaného iterativní Viterbiho dekódování lze najít podposloupnost pozorování, která vyhovuje nejlépe (v průměru) dané HMM. Tento algoritmus navrhl Qi Wang, etc.[3] pro zpracování turbo kódů. Iterativní Viterbi dekódování pracuje iterativně vyvoláním modifikovaného Viterbiho algoritmu, znovu odhadnutím skóre pro výplňku při konvergenci.

Nedávno byl navržen alternativní algoritmus, líný Viterbiho algoritmus[4]. Pro mnoho kódů používaných v praxi, při rozumném šumu, je dekodér používající líný Viterbiho algoritmus mnohem rychlejší než tradiční Viterbiho dekodér[5]. Líný Viterbiho algoritmus neexpanduje uzly, dokud to není opravdu nutné, a obvykle vyžaduje mnohem méně výpočtů, aby došel ke stejnému výsledku jako normální Viterbiho algoritmus – není ho však snadné hardwarově paralelizovat.

Existuje rozšíření Viterbiho algoritmu, aby pracoval s deterministickým konečným automatem pro zlepšení rychlosti při stochastické konverzi písmen na fonémy[6].

Související články[editovat | editovat zdroj]

Literatura[editovat | editovat zdroj]

  • Viterbi AJ(April 1967)."Error bounds for convolutional codes a an asymptotically optimum decoding algorithm". IEEE Transactions on Information Theory13(2): 260–269. doi:10.1109/TIT.1967.1054010.  (note: the Viterbi decoding algoritmus je described in section IV.) Subscription required.
  • Feldman J, Abou-Faycal I, Frigo M(2002)."A Fast Maximum-Likelihood Decoder for Convolutional Codes". Vehicular Technology Conference1: 371–375. doi:10.1109/VETECF.2002.1040367. 
  • Forney GD(March 1973)."The Viterbi algorithm". Proceedings of the IEEE61(3): 268–278. doi:10.1109/PROC.1973.9030.  Subscription required.
  • (2007)"Section 16.2. Viterbi Decoding", Numerical Recipes: The Art of Scientific Computing, 3rd,Cambridge University Press. ISBN 978-0-521-88068-8. 
  • Rabiner LR(February 1989)."A tutorial on hidden Markov models and selected applications in speech recognition". Proceedings of the IEEE77(2): 257–286. doi:10.1109/5.18626.  (Describes the forward algoritmus and Viterbi algorithm for HMMs).
  • Shinghal, R. a Godfried T. Toussaint, "Experiments in text recognition with the modified Viterbi algoritmus," IEEE Transactions on Pattern Analysis a Machine Intelligence, Vol. PAMI-l, April 1979, pp. 184–193.
  • Shinghal, R. a Godfried T. Toussaint, "The sensitivity of the modified Viterbi algoritmus to the source statistics," IEEE Transactions on Pattern Analysis a Machine Intelligence, vol. PAMI-2, March 1980, pp. 181–185.

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Viterbi algorithm na anglické Wikipedii.

  1. 29 Apr 2005, G. David Forney Jr: The Viterbi Algorithm: A Personal History
  2. Xing E, slide 11
  3. Qi Wang; Lei Wei; Rodney A. Kennedy(2002)."Iterative Viterbi Decoding, Trellis Shaping,a Multilevel Structure for High-Rate Parity-Concatenated TCM". IEEE TRANSACTIONS ON COMMUNICATIONS50: 48–55. 
  4. (December 2002) "A fast maximum-likelihood decoder for convolutional codes" (PDF) in Vehicular Technology Conference.: 371–375. doi:10.1109/VETECF.2002.1040367. 
  5. (December 2002) "A fast maximum-likelihood decoder for convolutional codes" (PDF) in Vehicular Technology Conference.. doi:10.1109/VETECF.2002.1040367. 
  6. Luk, R.W.P.; R.I. Damper(1998)."Computational complexity of a fast Viterbi decoding algoritmus for stochastic letter-phoneme transduction". IEEE Trans. Speech a Audio Processing6(3): 217–225. doi:10.1109/89.668816. 

Implementace[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]