Витербијев алгоритам

Витербијев алгоритам представља алгоритам динамичког програмирања који служи за проналажење највероватније секвенце скривених стања, такозваног Витербијевог пута, која произилази из секвенце посматраних догађаја, посебно у контексту Марковљевих извора информација и Марковљевих скривених модела.

Алгоритам је нашао универзалну примену у декодирању конвулционих кодова, који се користе у ЦДМА и ГСМ дигиталним мобилним телефонима, дајл-ап модемима, сателитима, комуникацији у дубоком свемиру, и 802.11 бежичном ЛАН-у. Такође је опште коришћен у препознавању говора, синтези говора, диаризацији,^[1] рачунарској лингвистици и биоинформатици. На пример, код препознавања говора звучни сигнал се третира као посматрана секвенца догађаја, а ниска текста се сматра "скривеним узроком" звучног сигнала. Витербијев алгоритам проналази највероватнију ниску текста за дати звучни сигнал.

Историја

Витербијев алгоритам је добио име по Ендруу Витербију, који га је предложио 1967. као декодирајући алгоритам конвулционих кодова за исправљање шума у дигиталној комуникацији.^[2] Међутим, до независног открића алгоритма дошло је чак седам научника, међу којима и Нидлман и Ванш, као и Вагнер и Фишер.^[3]

"Витербијев (пут, алгоритам)" је постао стандардни израз за примену алгоритама динамичког програмирања ради максимизације проблема који укључују вероватноћу.^[3] На пример, у статичкој синтаксној анализи алгоритам динамичког програмирања може да се искористи за откривање једног највероватнијег контекстно слободног члана ниске, који се назива „Витербијев члан“.^[4]^[5]^[6]

Алгоритам

Претпоставимо да нам је дат скривени Марковљев модел са следећим вредностима: стање простора $S$ , иницијална вероватноћа $\pi _{i}$ да је у стању $i$ и транзициона вероватноћа $a_{i,j}$ преласка из стања $i$ у стање $j$ . Рецимо да посматрамо излаз $y_{1},\dots ,y_{T}$ , највероватнија секвенца стања $x_{1},\dots ,x_{T}$ која производи опажање је дата рекурентним релацијама:^[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}}

Овде је $V_{t,k}$ вероватноћа највероватније секвенце стања $\mathrm {P} {\big (}x_{1},\dots ,x_{T},y_{1},\dots ,y_{T}{\big )}$ одговорне за првих $t$ опсервација које имају $k$ за своје коначно стање. Витербијев пут се може реконструисати чувањем показивача који памте које стање $x$ је коришћено у другој једначини. Нека је $\mathrm {Ptr} (k,t)$ функција која враћа вредност $x$ коришћену да се израчуна $V_{t,k}$ ако је $t>1$ , или $k$ ако је $t=1$ . Онда:

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

Овде користимо стандардну дефиницију аргумента максимума (arg max).
Сложеност овог алгоритма је $O(T\times \left|{S}\right|^{2})$ .

Пример

Посматрајмо село где су сви сељани или здрави или имају грозницу и једино сеоски лекар може да утврди ко има грозницу. Доктор дијагностикује грозницу тако што пита пацијенте како се осећају. Сељани само могу да одговоре да се осећају нормално, ошамућено или да им је хладно.

Доктор верује да се здравствено стање његових пацијената понаша као дискретан Марковљев ланац. Постоје два стања, "здрав" и "грозница", али доктор не може да их посматра директно, она су скривена од њега. Сваког дана постоји извесна могућност да ће пацијент рећи доктору да се осећа "нормално", "ошамућено" или да му је "хладно" у зависности од свог здравственог стања.

Опсервације (нормално, ошамућено, хладно) уз скривено стање (здрав, грозница) формирају скривени Марковљев модел и могу се представити у програмерском језику Пајтон на следећи начин:

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

У овом одломку кода почетна_вероватноћа представља лекарево уверење о томе у коме је стању скривеног Марковљевог модела био пацијент када га је први пут посетио (све што зна је да је пацијент иначе здрав). Конкретна дистрибуција вероватноће која се овде користи није еквилибријумска, која је (за дате вероватноће преласка) приближно {'Здрав': 0.57, 'Грозница': 0.43}. вероватноћа_преласка представља промену здравственог стања у Марковљевом ланцу. У овом примеру постоји само 30% шансе да ће пацијент сутра имати грозницу ако је данас здрав. вероватноћа_емисије представља вероватноћу како ће се пацијент осећати сваког дана. Ако је здрав, постоји 50% вероватноће да ће се осећати нормално, ако има грозницу постоји 60% вероватноће да се осећа ошамућено.

Пацијент долази на преглед три дана за редом и доктор открива да се он првог дана осећао нормално, да му је другог дана хладно и да је трећег дана ошамућен. Доктор има питање: која је највероватнија секвенца здравствених стања пацијента која би објаснила ове опсервације? Одговор на то питање даје Витербијев алгоритам.

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)

Функција viterbi има следеће аргументе: obs је секвенца запажања нпр ['нормално', 'хладно', 'ошамућено']; states је скуп скривених стања; start_p је почетна вероватноћа; trans_p су вероватноће преласка; и emit_p су вероватноће емисије.

Ради једноставности кода претпоставимо да је секвенца запажања obs непразна и да су trans_p[i][j] и emit_p[i][j] дефинисани за сва стања i,j.

У текућем примеру Витербијев алгоритам се користи на следећи начин:

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

Излаз је:

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

Ово открива да су запажања ['нормално', 'хладно', 'ошамућено'] највероватније генерисана од стања ['Здрав', 'Здрав', 'Грозница']. Другим речима, с обзиром на уочене активности највероватније је да је пацијент био здрав и првог дана када се осећао нормално као и другог дана када се осећао хладно, а онда је трећег дана добио грозницу.

Рад Витербијевог алгоритма се може видети помоћу трелис дијаграма. Витербијев алгоритам је у суштини најкраћи пут кроз трелис дијаграм. Клинички пример за трелис дијаграм је показан на слици испод где је назначен одговарајући Витербијев пут.

Анимација trellis дијаграма за Витербијев алгоритам. После три дана највероватнији могући пут је `['Здрав', 'Здрав', 'Грозница']`

Приликом примене Витербијевог алгоритма треба напоменути да многи језици користе аритметику у покретном зарезу -као нпр. p је мало, што може довести до поткорачења у резултатима. Уобичајена техника да се ово избегне је коришћење алгоритма вероватноће током обрачуна, истом техником која се користи у логаритамском бројчаном систему. Када се алгоритам заустави, прецизна вредност се може добити извођењем одговарајућег степеновања.

Екстензије

Генерализација Витербијевог алгоритма, названа алгоритмом max-sum (алгоритам максималног производа) може се користити да се пронађу највероватнији подаци свих или неких подскупова латентних варијабли у великом броју графичких модела, нпр Бајесове мреже, Марковљева случајна поља и условна случајна поља. Латентне варијабле треба да буду повезане на начин донекле сличан са скривеним Марковљевим моделом, са ограниченим бројем веза између варијабли и неке врсте линеарних структура између варијабли. Општи алгоритам обухвата прослеђивање порука и суштински је сличан алгоритму ширења поверења (belief propagation algorithm), који је генерализација напред-назад алгоритма.

Алгоритам који се зове итеративно Витербијево декодирање може наћи подниз опажања који најбоље одговара (у просеку) датом скривеном Марковљевом моделу. Користи се за рад са турбо кодом. Итеративно Витербијево декодирање ради помоћу итеративног позивања модификованог Витербијевог алгоритма, поново процењујући резултат датотеке до конвергенције.

Алтернативни алгоритам лењи Витербијев алгоритам, предложен је недавно. За многе кодексе практичног интереса, под разумним потешкоћама, лењи декодер (користећу лењи Витербијев алгоритам) је много бржи од оригиналног Витербијевог декодера (који користи Витербијев алгоритам). Овај алгоритам ради тако што не шири никакве чворове док заиста не буде потребно и обично успева да избегне пуно посла (у софтверу) од обичног Витербијевог алгоритма за исти резултат -међутим није могуће то рећи и за хардвер.

Псеудокод

С обзиром на простор за запажање $O=\{o_{1},o_{2},\dots ,o_{N}\}$ , простор за могућа стања $S=\{s_{1},s_{2},\dots ,s_{K}\}$ , секвенца запажања $Y=\{y_{1},y_{2},\ldots ,y_{T}\}$ , транзициона матрица $A$ величине $K\cdot K$ тако да $A_{ij}$ чува транзициону вероватноћу стања $s_{i}$ у стање $s_{j}$ , емисиона матрица $B$ велицине $K\cdot N$ тако да $B_{ij}$ чува вероватноћу запажања $o_{j}$ стања $s_{i}$ , низ иницијалних вероватноћа $\pi$ величине $K$ тако да $\pi _{i}$ чува вероватноћу $x_{1}==s_{i}$ . Ми кажемо да је пут $X=\{x_{1},x_{2},\ldots ,x_{T}\}$ секвенца случаја који генеришу запажања $Y=\{y_{1},y_{2},\ldots ,y_{T}\}$ .

У овом динамичком програмирању проблем смо конструисали у две дводимензионалне табеле $T_{1},T_{2}$ величине $K\cdot T$ . Сваки елемент од $T_{1}$ , $T_{1}[i,j]$ , чува вероватноћу највероватнијег пута до сада ${\hat {X}}=\{{\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j}\}$ са ${\hat {x}}_{j}=s_{i}$ који генерише $Y=\{y_{1},y_{2},\ldots ,y_{j}\}$ . Сваки елемент из $T_{2}$ , $T_{2}[i,j]$ чува ${\hat {x}}_{j-1}$ , највероватнији пут до сада ${\hat {X}}=\{{\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j-1},{\hat {x}}_{j}\}$ , за $\forall j,2\leq j\leq T$ .

Пунимо уносе две табеле $T_{1}[i,j],T_{2}[i,j]$ по растућем редоследу $K\cdot j+i$ .

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

, и

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

Треба напоменути да $B_{iy_{j}}$ не треба да се појави у другим изразима, јер је константа са $i$ и $j$ , и не утиче на argmax.

УЛАЗ

простор запажања $O=\{o_{1},o_{2},\dots ,o_{N}\}$ ,
простор могућих стања $S=\{s_{1},s_{2},\dots ,s_{K}\}$ ,
секвенца запажања $Y=\{y_{1},y_{2},\ldots ,y_{T}\}$ тако да $y_{t}==i$ за тренутно запажање $t$ је $o_{i}$ ,
транзициона матрица $A$ величине $K\cdot K$ тако да $A_{ij}$ чува трануициону вероватноћу стања $s_{i}$ у стање $s_{j}$ ,
емисиона матрица $B$ величине $K\cdot N$ тако да $B_{ij}$ чува вероватноћу запажања $o_{j}$ стања $s_{i}$ ,
низ иницијалних вероватноћа $\pi$ величине $K$ тако да $\pi _{i}$ чува вероватноћу $x_{1}==s_{i}$

ИЗЛАЗ

највероватнија секвенца случаја је $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

Види још

Референце

^ Xavier Anguera et Al, "Speaker Diarization: A Review of Recent Research" Архивирано на сајту Wayback Machine (12. мај 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 .
^ ^а ^б Jurafsky, Daniel; Martin, James H. (2014). Speech and Language Processing. Pearson Education International. стр. 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). стр. 40—47. doi:10.3115/1073445.1073461. Архивирано из оригинала (PDF) 05. 03. 2016. г. Приступљено 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

Литература

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

Литература

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. стр. 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 изд.). New York: Cambridge University Press. ISBN 978-0-521-88068-8. Архивирано из оригинала 11. 08. 2011. г. Приступљено 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 .

Имплементације

Спољашње везе

[1] Xavier Anguera et Al, "Speaker Diarization: A Review of Recent Research" Архивирано на сајту Wayback Machine (12. мај 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. стр. 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). стр. 40—47. doi:10.3115/1073445.1073461. Архивирано из оригинала (PDF) 05. 03. 2016. г. Приступљено 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]