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

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

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

Историја

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

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

Алгоритам

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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).
Сложеност овог алгоритма је ${\displaystyle 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), који је генерализација напред-назад алгоритма.

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

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

Псеудокод

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

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

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

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

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

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

УЛАЗ

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

ИЗЛАЗ

• највероватнија секвенца случаја је ${\displaystyle X=\{x_{1},x_{2},\ldots ,x_{T}\}}$

  function VITERBI( O, S, π, Y, A, B ) : X
     for each state si do
         T1[i,1] ← πi·Biy1
         T2[i,1] ← 0
     end for
     for i ← 2,3,...,T do
         for each state sj do
             ${\displaystyle T_{1}[j,i]\gets \max _{k}{(T_{1}[k,i-1]\cdot A_{kj}\cdot B_{jy_{i}})}}$
             ${\displaystyle T_{2}[j,i]\gets \arg \max _{k}{(T_{1}[k,i-1]\cdot A_{kj}\cdot B_{jy_{i}})}}$
         end for
     end for
     ${\displaystyle z_{T}\gets \arg \max _{k}{(T_{1}[k,T])}}$
     xT ← szT
     for i ← T,T-1,...,2 do
         zi-1 ← T2[zi,i]
         xi-1 ← szi-1
     end for
     return X
 end function

Види још

• Алгоритам очекивање-максимизација (ЕМ алгоритам)
• Skriveni Markovljev model