Viterbi алгоритмі

The Viterbi алгоритмі Бұл динамикалық бағдарламалау алгоритм ең көп табу үшін мүмкін жасырын күйлер тізбегі - деп аталады Витерби жолы- бұл бақыланатын оқиғалардың дәйектілігіне әкеледі, әсіресе Марковтың ақпарат көздері және жасырын Марков модельдері (HMM).

Алгоритм декодтау кезінде әмбебап қолданбаны тапты конволюциялық кодтар екеуінде де қолданылады CDMA және GSM сандық ұялы байланыс, теру модемдер, спутниктік, терең ғарыштық байланыс және 802.11 сымсыз жергілікті желілер. Ол қазірде жиі қолданылады сөйлеуді тану, сөйлеу синтезі, диаризация,^[1] кілт сөзді анықтау, есептеу лингвистикасы, және биоинформатика. Мысалы, in сөзден мәтінге (сөйлеуді тану), акустикалық сигнал оқиғалардың бақыланатын дәйектілігі ретінде қарастырылады, ал мәтіндік жол акустикалық сигналдың «жасырын себебі» болып саналады. Viterbi алгоритмі дыбыстық сигнал берілген мәтіннің ең ықтимал жолын табады.

Тарих

Viterbi алгоритмі аталған Эндрю Витерби, оны 1967 жылы декодтау алгоритмі ретінде ұсынған конволюциялық кодтар шулы сандық байланыс сілтемелері арқылы.^[2] Алайда оның тарихы бар бірнеше өнертабыс, кем дегенде жеті тәуелсіз жаңалықпен, оның ішінде Витербидің ашқан жаңалықтары, Ине мен Вунш, және Вагнер мен Фишер.^[3] Ол таныстырылды Табиғи тілді өңдеу әдісі ретінде Сөйлеу бөлігін тегтеу 1987 жылдың өзінде.

«Viterbi жолы» және «Viterbi алгоритмі» ықтималдықтармен байланысты мәселелерді максимизациялау үшін динамикалық бағдарламалау алгоритмдерін қолданудың стандартты шарттары болды.^[3]Мысалы, in статистикалық талдау динамикалық бағдарламалау алгоритмін жолдың контекстсіз бірыңғай туындысын (синтаксисін) табу үшін пайдалануға болады, ол әдетте «Витерби талдауы» деп аталады.^[4]^[5]^[6] Тағы бір бағдарлама бар мақсатты бақылау, мұнда бақылаулар тізбегіне максималды ықтималдылықты беретін трек есептеледі.^[7]

Кеңейтімдер

Viterbi алгоритмін жалпылау максималды қосынды алгоритмі (немесе максималды өнім алгоритмі) барлығының немесе кейбір жиындарының ықтимал тағайындауын табу үшін қолданыла алады жасырын айнымалылар көп мөлшерде графикалық модельдер, мысалы. Байес желілері, Марков кездейсоқ өрістер және шартты кездейсоқ өрістер. Жасырын айнымалылар жалпы HMM-ге ұқсас жолмен, айнымалылар арасындағы шектеулі байланыстармен және айнымалылар арасындағы сызықтық құрылымның кейбір түрімен байланыстырылуы қажет. Жалпы алгоритмге жатады хабарлама жіберу және айтарлықтай ұқсас сенімнің таралуы алгоритм (бұл жалпылау болып табылады алға-артқа алгоритм ).

Шақырылған алгоритммен итеративті Витерби декодтау біреуіне сәйкес келетін (орта есеппен) бақылаудың дәйектілігін табуға болады жасырын Марков моделі. Бұл алгоритмді Ци Ванг және басқалар ұсынады. күресу турбо коды.^[8] Итеративті Витербиді декодтау модификацияланған Витерби алгоритмін қайталап шақыру арқылы жұмыс істейді, конвергенцияға дейін толтырғыштың бағасын қайта есептейді.

Баламалы алгоритм Lazy Viterbi алгоритмі, ұсынылды.^[9] Көптеген шуыл жағдайында практикалық қызығушылық тудыратын жалқау декодер (Lazy Viterbi алгоритмін қолдана отырып) түпнұсқаға қарағанда жылдамырақ Витерби декодері (Viterbi алгоритмін қолдану арқылы). Viterbi-дің түпнұсқа алгоритмі ықтимал нәтижелердің торабындағы барлық түйіндерді есептейтін болса, Lazy Viterbi алгоритмі ретімен бағалау үшін түйіндердің басымды тізімін сақтайды және қажет есептеулер саны кәдімгі Viterbi алгоритміне қарағанда азырақ (және ешқашан көп емес) сол нәтиже. Алайда, бұл оңай емес^{[түсіндіру қажет ]} жабдықта параллельдеу.

Псевдокод

Бұл алгоритм жол жасайды ${ displaystyle X = (x_ {1}, x_ {2}, ldots, x_ {T})}$ , бұл күйлер тізбегі болып табылады ${ displaystyle x_ {n} in S = {s_ {1}, s_ {2}, dots, s_ {K} }}$ бақылаулар тудырады ${ displaystyle Y = (y_ {1}, y_ {2}, ldots, y_ {T})}$ бірге ${ displaystyle y_ {n} in O = {o_ {1}, o_ {2}, dots, o_ {N} }}$ , қайда ${ displaystyle N}$ - бұл бақылау кеңістігінде мүмкін бақылаулар саны ${ displaystyle O}$ .

Екі өлшемді кесте ${ displaystyle K times T}$ салынған:

Әрбір элемент ${ displaystyle T_ {1} [i, j]}$ туралы ${ displaystyle T_ {1}}$ осы уақытқа дейінгі ықтимал жолдың ықтималдығын сақтайды ${ 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} [i, j]}$ туралы ${ displaystyle T_ {2}}$ дүкендер ${ displaystyle { hat {x}} _ {j-1}}$ осы уақытқа дейінгі ықтимал жолдың ${ displaystyle { hat {X}} = ({ hat {x}} _ {1}, { hat {x}} _ {2}, ldots, { hat {x}} _ {j- 1}, { hat {x}} _ {j} = s_ {i})}$ үшін ${ 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] = operatorname {argmax} _ {k} {(T_ {1} [k, j-1] cdot A_ {ki} cdot B_ {iy_ {j}} )}}

,

бірге ${ displaystyle A_ {ki}}$ және ${ displaystyle B_ {iy_ {j}}}$ төменде анықталғандай. Ескертіп қой ${ displaystyle B_ {iy_ {j}}}$ соңғы өрнекте пайда болудың қажеті жоқ, өйткені ол теріс емес және тәуелді емес ${ displaystyle k}$ және осылайша аргмаксқа әсер етпейді.

Кіріс

The бақылау кеңістігі ${ displaystyle O = {o_ {1}, o_ {2}, dots, o_ {N} }}$ ,
The мемлекеттік кеңістік ${ displaystyle S = {s_ {1}, s_ {2}, dots, s_ {K} }}$ ,
бастапқы ықтималдықтар жиыны ${ displaystyle Pi = ( pi _ {1}, pi _ {2}, нүктелер, pi _ {K})}$ осындай ${ displaystyle pi _ {i}}$ ықтималдығын сақтайды ${ displaystyle x_ {1} = s_ {i}}$ ,
бақылаулар тізбегі ${ displaystyle Y = (y_ {1}, y_ {2}, ldots, y_ {T})}$ осындай ${ displaystyle y_ {t} = i}$ егер байқау уақытында болса ${ displaystyle t}$ болып табылады ${ displaystyle o_ {i}}$ ,
өтпелі матрица ${ displaystyle A}$ өлшемі ${ displaystyle K times K}$ осындай ${ displaystyle A_ {ij}}$ сақтайды ауысу ықтималдығы мемлекеттен транзиттік қатынастар ${ displaystyle s_ {i}}$ мемлекетке ${ displaystyle s_ {j}}$ ,
шығарынды матрицасы ${ displaystyle B}$ өлшемі ${ displaystyle K times N}$ осындай ${ displaystyle B_ {ij}}$ сақтау ықтималдығын сақтайды ${ displaystyle o_ {j}}$ штаттан ${ displaystyle s_ {i}}$ .

Шығу

Ең ықтимал жасырын күй реттілігі ${ displaystyle X = (x_ {1}, x_ {2}, ldots, x_ {T})}$

 функциясы ВИТЕРБИ ${ displaystyle (O, S, Pi, Y, A, B): X}$      үшін әр штат  ${ displaystyle i = 1,2, lots, K}$  істеу          ${ displaystyle T_ {1} [i, 1] leftarrow pi _ {i} cdot B_ {iy_ {1}}}$           ${ displaystyle T_ {2} [i, 1] leftarrow 0}$      үшін аяқтау     үшін әрбір бақылау  ${ displaystyle j = 2,3, ldots, T}$  істеу         үшін әр штат  ${ displaystyle i = 1,2, ldots, K}$  істеу              ${ displaystyle T_ {1} [i, j] gets max _ {k} {(T_ {1} [k, j-1] cdot A_ {ki} cdot B_ {iy_ {j}})} }$               ${ displaystyle T_ {2} [i, j] gets arg max _ {k} {(T_ {1} [k, j-1] cdot A_ {ki} cdot B_ {iy_ {j}} )}}$          үшін аяқтау     үшін аяқтау      ${ displaystyle z_ {T} gets arg max _ {k} {(T_ {1} [k, T])}}$       ${ displaystyle x_ {T} leftarrow s_ {z_ {T}}}$      үшін  ${ displaystyle j = T, T-1, ldots, 2}$  істеу          ${ displaystyle z_ {j-1} сол жақ T_ {2} [z_ {j}, j]}$           ${ displaystyle x_ {j-1} leftarrow s_ {z_ {j-1}}}$      үшін аяқтау     қайту  ${ displaystyle X}$  соңғы функция

Питонға жақын қысқаша жазылған:

 # ықтималдық == б. Tm: өтпелі матрица. Эм: шығарынды матрицасы. функциясы viterbi (O, S, Π, Tm, Em): ең жақсы_жол торы ← матрица (ұзындық (S), ұзындық (O)) # б. ұстап тұру. әр бақылаудан өткен әр мемлекеттің. # Әрбір жасырылған күйді анықтаңыз. 0 уақытта ... үшін s диапазонында (ұзындық (S)): торлы тор [s, 0] ← Π [s] * Em [s, O [0]] #… және одан кейін әр күйдің ең ықтимал күйін қабылдай отырып, k. үшін o диапазонында (1, ұзындығы (O)): үшін s диапазонында (ұзындық (S)): к ← argmax (к торда [к, o-1] * Tm [к, s] * Em [s, o]) торлы тор [s, o] ← торлы тор [к, o-1] * Tm [к, s] * Em [s, o] best_path ← тізім () үшін o (-1, - (ұзындық (O) +1), -1) диапазонында: # Соңғы бақылаудан кері шегіну. к ← argmax (к торда [к, o]) # o best_path.insert (0, S [) күйінде болуы мүмкінк]) # қайтару үшін белгіленді. қайту ең жақсы_жол

Түсіндіру

Бізге а берілді делік жасырын Марков моделі (HMM) күй кеңістігі бар ${ 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}}$ бақылаулар тудыратын, қайталанатын қатынастармен беріледі^[10]

{ displaystyle { begin {aligned} 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 {aligned}}}

Мұнда ${ displaystyle V_ {t, k}}$ - бұл ең ықтимал күй реттілігінің ықтималдығы ${ displaystyle mathrm {P} { big (} x_ {1}, dots, x_ {t}, y_ {1}, dots, y_ {t} { big)}}$ біріншісіне жауап береді ${ displaystyle t}$ бар бақылаулар ${ displaystyle k}$ оның соңғы күйі ретінде. Viterbi жолын қай күйді еске сақтайтын көрсеткіштерді сақтау арқылы алуға болады ${ displaystyle x}$ екінші теңдеуде қолданылған. Келіңіздер ${ displaystyle mathrm {Ptr} (k, t)}$ мәнін қайтаратын функция болуы керек ${ displaystyle x}$ есептеу үшін қолданылады ${ displaystyle V_ {t, k}}$ егер ${ displaystyle t> 1}$ , немесе ${ displaystyle k}$ егер ${ displaystyle t = 1}$ . Содан кейін

{ displaystyle { begin {aligned} x_ {T} & = arg max _ {x in S} (V_ {T, x}), x_ {t-1} & = mathrm {Ptr} (x_ {t}, t). end {aligned}}}

Мұнда біз стандартты анықтамасын қолданамыз арг макс.

Бұл іске асырудың күрделілігі ${ displaystyle O (T times left | {S} right | ^ {2})}$ . Егер ішкі циклдегі максимум тек ағымдағы күйге тікелей байланысты күйлер бойынша қайталану арқылы табылса (мысалы, ${ displaystyle k}$ дейін ${ displaystyle j}$ ). Содан кейін пайдалану амортизациялық талдау күрделілігі бар екенін көрсетуге болады ${ displaystyle O (T times ( left | {S} right | + left | {E} right |))}$ , қайда ${ displaystyle E}$ - графиктегі жиектер саны.

Мысал

Барлық ауылдастарының денсаулығы жақсы немесе қызуы көтерілген ауылды қарастырайық, тек ауыл дәрігері әрқайсысының безгегі бар-жоғын анықтай алады. Дәрігер температураны науқастардан олардың сезімдерін сұрап анықтайды. Ауыл тұрғындары өздерін қалыпты, басы айналған немесе суық сезінеді деп жауап бере алады.

Дәрігер науқастардың денсаулығы дискретті түрде жұмыс істейді деп санайды Марков тізбегі. Екі мемлекет бар, олар «Дені сау» және «Қызба», бірақ дәрігер оларды тікелей бақылай алмайды; олар жасырын одан. Әр күн сайын пациент дәрігерге өзінің денсаулығына байланысты «қалыпты», «суық» немесе «басы айналған» деп айтуының белгілі бір мүмкіндігі бар.

The бақылаулар (қалыпты, суық, айналуы) бірге а жасырын күй (сау, қызба) жасырын Марков моделін құрайды (HMM), және келесі түрде ұсынылуы мүмкін Python бағдарламалау тілі:

обс = («қалыпты», «суық», «бас айналу»)мемлекеттер = («Дені сау», «Безгек»)бастау_б = {«Дені сау»: 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}. The өту_б Марков тізбегіндегі денсаулық жағдайының өзгеруін білдіреді. Бұл мысалда пациенттің бүгін дені сау болса, оның температурасы көтерілуінің 30% мүмкіндігі бар. The эмиссия_б қалыпты, суық немесе айналуы мүмкін кез-келген байқаудың олардың негізгі жағдайына, сау немесе қызбаға қаншалықты ықтимал екендігін көрсетеді. Егер пациент сау болса, оның қалыпты сезінуінің 50% мүмкіндігі бар; егер оның температурасы көтерілсе, оның айналуы мүмкін 60% ықтималдығы бар.

Берілген ХММ графикалық бейнесі

Науқас үш күн қатарынан барады және дәрігер бірінші күні өзін қалыпты сезінетінін, екінші күні салқындағанын, үшінші күні басы айналғанын анықтайды. Дәрігерде сұрақ туындайды: пациенттің денсаулық жағдайының қандай болуы мүмкін, бұл бақылауларды түсіндіреді? Бұған Viterbi алгоритмі жауап береді.

 1 деф витерби(обс, мемлекеттер, бастау_б, транс_п, шығару_б): 2     V = [{}] 3     үшін ст жылы мемлекеттер: 4         V[0][ст] = {«prob»: бастау_б[ст] * шығару_б[ст][обс[0]], «алдыңғы»: Жоқ} 5     T> 0 болғанда # Viterbi-ді іске қосыңыз 6     үшін т жылы ауқымы(1, лен(обс)): 7         V.қосу({}) 8         үшін ст жылы мемлекеттер: 9             max_tr_prob = V[т - 1][мемлекеттер[0]][«prob»] * транс_п[мемлекеттер[0]][ст]10             алдын-ала_таңдалды = мемлекеттер[0]11             үшін алдыңғы_ст жылы мемлекеттер[1:]:12                 tr_prob = V[т - 1][алдыңғы_ст][«prob»] * транс_п[алдыңғы_ст][ст]13                 егер tr_prob > max_tr_prob:14                     max_tr_prob = tr_prob15                     алдын-ала_таңдалды = алдыңғы_ст16 17             max_prob = max_tr_prob * шығару_б[ст][обс[т]]18             V[т][ст] = {«prob»: max_prob, «алдыңғы»: алдын-ала_таңдалды}19 20     үшін түзу жылы dptable(V):21         басып шығару(түзу)22 23     таңдау = []24     max_prob = 0.025     алдыңғы = Жоқ26     # Ең ықтимал күйді және оның кері бағытын алыңыз27     үшін ст, деректер жылы V[-1].заттар():28         егер деректер[«prob»] > max_prob:29             max_prob = деректер[«prob»]30             ең жақсы_ст = ст31     таңдау.қосу(ең жақсы_ст)32     алдыңғы = ең жақсы_ст33 34     # Бірінші бақылауға дейін артқы жолды ұстаныңыз35     үшін т жылы ауқымы(лен(V) - 2, -1, -1):36         таңдау.кірістіру(0, V[т + 1][алдыңғы][«алдыңғы»])37         алдыңғы = V[т + 1][алдыңғы][«алдыңғы»]38 39     басып шығару ('Мемлекеттердің қадамдары' + ' '.қосылу(таңдау) + 'ықтималдығы жоғары % s' % max_prob)40 41 деф dptable(V):42     # Сөздіктен қадамдар кестесін басып шығарыңыз43     Өткізіп жібер " ".қосылу(("% 12д" % мен) үшін мен жылы ауқымы(лен(V)))44     үшін мемлекет жылы V[0]:45         Өткізіп жібер "% .7с: " % мемлекет + " ".қосылу("% .7с" % ("% f" % v[мемлекет][«prob»]) үшін v жылы V)

Функция витерби келесі аргументтерді қолданады: обс бұл бақылаулар тізбегі, мысалы. ['қалыпты', 'суық', 'айналдыру']; мемлекеттер бұл жасырын күйлер жиынтығы; бастау_б басталу ықтималдығы; транс_п ауысу ықтималдығы; және шығару_б шығарындылардың ықтималдығы. Кодтың қарапайымдылығы үшін бақылау дәйектілігі деп есептейміз обс бос емес және солай trans_p [i] [j] және шығару_p [i] [j] барлық мемлекеттер үшін анықталған, i.

Іске асырылатын мысалда алға / Витерби алгоритмі келесідей қолданылады:

витерби(обс,        мемлекеттер,        бастау_б,        транс_п,        шығару_б)

Сценарийдің нәтижесі

$ python viterbi_example.py         0          1          2Дені сау: 0.30000 0.08400 0.00588Қызба: 0,04000 0,02700 0,01512Мемлекеттердің қадамдары - дені сау қызба, ең үлкен ықтималдығы 0,01512

Бұл бақылаулар екенін анықтайды ['қалыпты', 'суық', 'айналдыру'] мемлекеттер шығарған болуы мүмкін ['Дені сау', 'Дені сау', 'Қызба']. Басқаша айтқанда, байқалған іс-әрекеттерді ескере отырып, науқастың дені сау болуы мүмкін, бірінші күні ол өзін қалыпты сезінгенде де, екінші күні салқындаған кезде де, содан кейін ол үшінші күні безгекпен ауырды.

Витербидің алгоритмінің жұмысын a көмегімен бейнелеуге боладытордың диаграммасы. Витерби жолы - бұл торлы торап арқылы ең қысқа жол.

The Viterbi алгоритмі (СОВА) бұл классикалық Viterbi алгоритмінің нұсқасы.

SOVA классикалықтан ерекшеленеді Viterbi алгоритмі ескере отырып, модификацияланған жол көрсеткішін қолданады априорлық ықтималдықтар және енгізу атауын шығарады жұмсақ көрсететін шығыс сенімділік шешім.

SOVA-дағы алғашқы қадам - әр сәтте бірегей түйін арқылы өтетін тірі қалу жолын таңдау, т. Әр түйіннің бойында 2 тармақ жинақталғандықтан (форманы құру үшін бір тармақ таңдалады) Тірі қалған жол, ал екіншісі алынып тасталса), салалық көрсеткіштердегі айырмашылық (немесе құны) таңдалған және жойылған бұтақтар арасында қате мөлшері таңдауда.

Бұл құны бүкіл жылжымалы терезеде жинақталған (әдетте тең болады) шектен асқанда көрсету үшін, бес шектеу ұзындығы) жұмсақ шығу сенімділік өлшемі қатаң шешім туралы Витерби алгоритм.

Сондай-ақ қараңыз

Әдебиеттер тізімі

^ Xavier Anguera және басқалар, «Спикерлерді диаризациялау: соңғы зерттеулерге шолу», алынды 19. тамыз 2010, IEEE TASLP
^ 29 сәуір 2005 ж., Г.Дэвид Форни кіші: Витерби алгоритмі: жеке тарих
^ ^а ^б Даниэль Джурафский; Джеймс Х.Мартин. Сөйлеу және тілді өңдеу. Pearson Education International. б. 246.
^ Шмид, Гельмут (2004). Бит векторларымен екіұшты контекстсіз грамматиканы тиімді талдау (PDF). Proc. 20 Халықаралық Конф. Компьютерлік лингвистика (COLING) туралы. дои:10.3115/1220355.1220379.
^ Клейн, Дэн; Мэннинг, Кристофер Д. (2003). A * талдау: Viterbi талдауын жылдам дәл таңдау (PDF). Proc. 2003 ж. Компьютерлік лингвистика қауымдастығының адам тілінің технологиясы (NAACL) Солтүстік Америка тарауының. 40-47 бет. дои:10.3115/1073445.1073461.
^ Станке, М .; Келлер, О .; Гундуз, Мен .; Хейз, А .; Ваак С .; Моргенстерн, Б. (2006). «АВГУСТУС: балама транскрипттерді алдын-ала болжау». Нуклеин қышқылдарын зерттеу. 34 (Веб-сервер мәселесі): W435 – W439. дои:10.1093 / nar / gkl200. PMC 1538822. PMID 16845043.
^ Куач, Т .; Фарук, М. (1994). «Витерби алгоритмімен максималды ықтималдықты трек қалыптастыру». Шешімдер мен бақылау бойынша 33-ші IEEE конференциясының материалдары. 1. 271–276 бет. дои:10.1109 / CDC.1994.410918.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)
^ Ци Ванг; Лей Вэй; Родни А.Кеннеди (2002). «Жоғары деңгейлі паритетпен үйлескен ТКМ үшін итеративті Витербиді декодтау, треллерді қалыптастыру және көпдеңгейлі құрылым». Байланыс бойынша IEEE транзакциялары. 50: 48–55. дои:10.1109/26.975743.
^ Конволюциялық кодтар үшін жылдамдықты тез декодер (PDF). Көлік технологиялары конференциясы. Желтоқсан 2002. 371–375 бб. дои:10.1109 / VETECF.2002.1040367.
^ Xing E, слайд 11.

Жалпы сілтемелер

Viterbi AJ (сәуір, 1967). «Конволюциялық кодтардың және асимптотикалық оңтайлы декодтау алгоритмінің қателіктері». Ақпараттық теория бойынша IEEE транзакциялары. 13 (2): 260–269. дои:10.1109 / TIT.1967.1054010. (ескерту: Viterbi декодтау алгоритмі IV бөлімде сипатталған.) Жазылу қажет.
Фельдман Дж, Абу-Файкал I, Фриго М (2002). Конволюциялық кодтар үшін максималды ықтималдықты жылдам декодер. Көлік технологиялары конференциясы. 1. 371-375 бб. CiteSeerX 10.1.1.114.1314. дои:10.1109 / VETECF.2002.1040367. ISBN 978-0-7803-7467-6.
Форни Г.Д. (наурыз 1973). «Viterbi алгоритмі». IEEE материалдары. 61 (3): 268–278. дои:10.1109 / PROC.1973.9030. Жазылу қажет.
Press, WH; Теукольский, SA; Веттерлинг, ВТ; Flannery, BP (2007). «16.2 бөлім. Витерби декодтау». Сандық рецепттер: ғылыми есептеу өнері (3-ші басылым). Нью-Йорк: Кембридж университетінің баспасы. ISBN 978-0-521-88068-8.
Rabiner LR (ақпан 1989). «Марковтың жасырын модельдері және сөйлеуді танудағы таңдалған қосымшалар туралы оқу құралы» IEEE материалдары. 77 (2): 257–286. CiteSeerX 10.1.1.381.3454. дои:10.1109/5.18626. (НММ-ге бағытталған алгоритмді және Viterbi алгоритмін сипаттайды).
Шингхал, Р. және Годфрид Т., «Өзгертілген Viterbi алгоритмімен мәтінді тану тәжірибелері» Үлгіні талдау және машиналық интеллект бойынша IEEE транзакциялары, Т. PAMI-l, сәуір, 1979, 184–193 бб.
Шингхал, Р. және Годфрид Т., «Өзгертілген Viterbi алгоритмінің бастапқы статистикаға сезімталдығы» Үлгіні талдау және машиналық интеллект бойынша IEEE транзакциялары, т. PAMI-2, 1980 ж. Наурыз, 181–185 бб.

Іске асыру

Математика стохастикалық процестерді қолдау шеңберінде іске асыруға ие
Суса сигналдарды өңдеу құрылымы C ++ бағдарламасын ұсынады Қатені алға жіберу кодтар және арнаны теңестіру Мұнда.
C ++
C #
Java
Java 8
Перл
Пролог
Хаскелл
Барыңыз
SFIHMM Viterbi декодтау кодын қамтиды.

Сыртқы сілтемелер

Википедиядағы Java, F #, Clojure, C # бағдарламаларындағы ендірулер
Оқулық Чип Флемингтің көмегімен витерби декодтауымен конволюциялық кодтау туралы
Viterbi алгоритмінің сипаттамасын қамтитын жасырын Markov Model инструментіне арналған нұсқаулық (C тілінде енгізілген)
Viterbi алгоритмі Доктор Эндрю Дж. Витерби (scholarpedia.org).

[1] Xavier Anguera және басқалар, «Спикерлерді диаризациялау: соңғы зерттеулерге шолу», алынды 19. тамыз 2010, IEEE TASLP

[2] 29 сәуір 2005 ж., Г.Дэвид Форни кіші: Витерби алгоритмі: жеке тарих

[slp-3] а ^б Даниэль Джурафский; Джеймс Х.Мартин. Сөйлеу және тілді өңдеу. Pearson Education International. б. 246.

[4] Шмид, Гельмут (2004). Бит векторларымен екіұшты контекстсіз грамматиканы тиімді талдау (PDF). Proc. 20 Халықаралық Конф. Компьютерлік лингвистика (COLING) туралы. дои:10.3115/1220355.1220379.

[5] Клейн, Дэн; Мэннинг, Кристофер Д. (2003). A * талдау: Viterbi талдауын жылдам дәл таңдау (PDF). Proc. 2003 ж. Компьютерлік лингвистика қауымдастығының адам тілінің технологиясы (NAACL) Солтүстік Америка тарауының. 40-47 бет. дои:10.3115/1073445.1073461.

[6] Станке, М .; Келлер, О .; Гундуз, Мен .; Хейз, А .; Ваак С .; Моргенстерн, Б. (2006). «АВГУСТУС: балама транскрипттерді алдын-ала болжау». Нуклеин қышқылдарын зерттеу. 34 (Веб-сервер мәселесі): W435 – W439. дои:10.1093 / nar / gkl200. PMC 1538822. PMID 16845043.

[7] Куач, Т .; Фарук, М. (1994). «Витерби алгоритмімен максималды ықтималдықты трек қалыптастыру». Шешімдер мен бақылау бойынша 33-ші IEEE конференциясының материалдары. 1. 271–276 бет. дои:10.1109 / CDC.1994.410918.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)

[8] Ци Ванг; Лей Вэй; Родни А.Кеннеди (2002). «Жоғары деңгейлі паритетпен үйлескен ТКМ үшін итеративті Витербиді декодтау, треллерді қалыптастыру және көпдеңгейлі құрылым». Байланыс бойынша IEEE транзакциялары. 50: 48–55. дои:10.1109/26.975743.

[9] Конволюциялық кодтар үшін жылдамдықты тез декодер (PDF). Көлік технологиялары конференциясы. Желтоқсан 2002. 371–375 бб. дои:10.1109 / VETECF.2002.1040367.

[10] Xing E, слайд 11.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]