Корисник:MiaSandra/песак

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

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

Историја

Витербијев алгоритам је добио име по Eндру Витербију, који га је предложио 1967 као декодирајући алгоритам конвулционих кодова за исправљање шума у дигиталној комуникацији. Mеђутим, до независног открића алгоритма дошло је чак седам научника, међу којима и Нидлман и Ванш,и Вагнер и Фишер.

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

Алгоритам

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

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

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

Пример

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

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

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

states = ('Healthy', 'Fever')
observations = ('normal', 'cold', 'dizzy')
start_probability = {'Healthy': 0.6, 'Fever': 0.4}
transition_probability = {
   'Healthy' : {'Healthy': 0.7, 'Fever': 0.3},
   'Fever' : {'Healthy': 0.4, 'Fever': 0.6}
   }
emission_probability = {
   'Healthy' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
   'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6}
   }

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

Graphical representation of the given HMM

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

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}
    # Run Viterbi when 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 = []
    # The highest probability
    max_prob = max(value["prob"] for value in V[-1].values())
    previous = None
    # Get most probable state and its backtrack
    for st, data in V[-1].items():
        if data["prob"] == max_prob:
            opt.append(st)
            previous = st
            break
    # Follow the backtrack till the first observation
    for t in range(len(V) - 2, -1, -1):
        opt.insert(0, V[t + 1][previous]["prev"])
        previous = V[t][previous]["prev"]

    print 'The steps of states are ' + ' '.join(opt) + ' with highest probability of %s' % max_prob

def dptable(V):
    # Print a table of steps from dictionary
    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 је секвенца опсервација нпр ['normal', 'cold', 'dizzy']; states је скуп скривених стања; start_p је почетна вероватноћа; trans_p су вероватноће преласка; и emit_p су вероватноће емисије.

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

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

viterbi(observations,
                   states,
                   start_probability,
                   transition_probability,
                   emission_probability)

Излаз је:

$ python viterbi_example.py
         0          1          2
Healthy: 0.30000 0.08400 0.00588
Fever: 0.04000 0.02700 0.01512
The steps of states are Healthy Healthy Fever with highest probability of 0.01512

Ово открива да су запажања ['normal', 'cold', 'dizzy'] највероватније генерисана од стања ['Healthy', 'Healthy', 'Fever']. Другим речима, с обзиром на уочене активности највероватније је да је пацијенткиња била здрава и првог дана када се осећала normal као и другог дана када се осећала cold, а онда је трећег дана добила грозницу, dizzy.

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

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

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

Екстензије

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

Алгоритам који се зове итеративно Витербијево декодирање може наћи секвенцу са запажањем која одговара најбоље (у просеку) датом HMM. Овај алгоритам је предложен од стране Qi Wang et al. да би се решило са турбо кодом. Итеративно Витербијево декодирање ради помоћу итеративног позивања модификованог Витербијевог алгоритма, поново процењујући резултат filer до конвергенције.

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

Псеудокод

С обзиром на простор за запажање $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}\}$.

У овом динамичком програмирању проблем смо конструисали у 2-димензионе табеле $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.

INPUT

• простор запажања $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}$

OUTPUT

• Највероватнија секвенца случаја је $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
             $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])}$
     xT ← szT
     for i ← T,T-1,...,2 do
         zi-1 ← T2[zi,i]
         xi-1 ← szi-1
     end for
     return ${X}$
 end function