Алгоритм Витерби

Находит вероятную последовательность скрытых состояний

Алгоритм Витерби — это алгоритм динамического программирования для получения максимальной апостериорной оценки вероятности наиболее вероятной последовательности скрытых состояний, называемой путем Витерби , которая приводит к последовательности наблюдаемых событий. Это делается особенно в контексте источников марковской информации и скрытых марковских моделей (HMM).

Алгоритм нашел универсальное применение при декодировании сверточных кодов , используемых в цифровой сотовой связи CDMA и GSM , модемах коммутируемого доступа , спутниковой связи, связи в дальнем космосе и беспроводных локальных сетях 802.11 . В настоящее время он также широко используется в распознавании речи , синтезе речи , дневникизации , ^[1] обнаружении ключевых слов , компьютерной лингвистике и биоинформатике . Например, при преобразовании речи в текст (распознавании речи) акустический сигнал рассматривается как наблюдаемая последовательность событий, а строка текста считается «скрытой причиной» акустического сигнала. Алгоритм Витерби находит наиболее вероятную текстовую строку по акустическому сигналу.

История

Алгоритм Витерби назван в честь Эндрю Витерби , который предложил его в 1967 году в качестве алгоритма декодирования сверточных кодов по зашумленным цифровым каналам связи. ^[2] Тем не менее, он имеет историю многочисленных изобретений , по крайней мере, семи независимых открытий, в том числе Витерби, Нидлмана и Вунша , а также Вагнера и Фишера . ^[3] Он был представлен в обработке естественного языка как метод маркировки частей речи еще в 1987 году.

Путь Витерби и алгоритм Витерби стали стандартными терминами для применения алгоритмов динамического программирования к задачам максимизации, связанным с вероятностями. ^[3] Например, при статистическом анализе алгоритм динамического программирования может использоваться для обнаружения единственного наиболее вероятного контекстно-свободного вывода (анализа) строки, который обычно называют «анализом Витерби». ^{[4] [5] [6]} Другое применение — отслеживание целей , где вычисляется путь, который присваивает максимальную вероятность последовательности наблюдений. ^[7]

Расширения

Обобщение алгоритма Витерби, называемое алгоритмом максимальной суммы (или алгоритмом максимального произведения ), может использоваться для поиска наиболее вероятного назначения всех или некоторого подмножества скрытых переменных в большом количестве графических моделей , например, байесовских сетей , марковских сетей . случайные поля и условно случайные поля . Скрытые переменные, как правило, должны быть связаны способом, похожим на скрытую модель Маркова (СММ), с ограниченным количеством связей между переменными и некоторым типом линейной структуры среди переменных. Общий алгоритм включает передачу сообщений и по существу аналогичен алгоритму распространения доверия (который является обобщением алгоритма вперед-назад ).

С помощью алгоритма, называемого итеративным декодированием Витерби, можно найти подпоследовательность наблюдения, которая лучше всего (в среднем) соответствует заданной скрытой марковской модели. Этот алгоритм предложен Ци Ваном и др. разобраться с турбокодом . ^[8] Итеративное декодирование Витерби работает путем итеративного вызова модифицированного алгоритма Витерби, переоценивая оценку заполнителя до достижения сходимости.

Был предложен альтернативный алгоритм — алгоритм Ленивого Витерби. ^[9] Для многих приложений, представляющих практический интерес, при разумных условиях шума ленивый декодер (с использованием ленивого алгоритма Витерби) работает намного быстрее, чем исходный декодер Витерби (с использованием алгоритма Витерби). В то время как исходный алгоритм Витерби вычисляет каждый узел в решетке возможных результатов, алгоритм Ленивого Витерби поддерживает приоритетный список узлов для оценки по порядку, а количество необходимых вычислений обычно меньше (и никогда больше), чем обычный алгоритм Витерби для тот же результат. Однако распараллелить аппаратно не так-то просто ^{[ нужны пояснения ] .}

Псевдокод

Этот алгоритм генерирует путь , который представляет собой последовательность состояний , которые генерируют наблюдения с где – количество возможных наблюдений в пространстве наблюдения . ${\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}})}}$,

с и как определено ниже. Обратите внимание, что это значение не обязательно должно присутствовать в последнем выражении, поскольку оно неотрицательно, независимо от и, следовательно, не влияет на argmax. ${\displaystyle A_{ki}}$ ${\displaystyle B_{iy_{j}}}$ ${\displaystyle B_{iy_{j}}}$ ${\displaystyle k}$

Вход

• Наблюдательное пространство , ${\displaystyle O=\{o_{1},o_{2},\dots ,o_{N}\}}$
• государственное пространство , ${\displaystyle S=\{s_{1},s_{2},\dots ,s_{K}\}}$
• массив начальных вероятностей , в котором хранится вероятность того, что , ${\displaystyle \Pi =(\pi _{1},\pi _{2},\dots ,\pi _{K})}$ ${\displaystyle \pi _{i}}$ ${\displaystyle x_{1}=s_{i}}$
• последовательность наблюдений такая, что если наблюдение в момент времени , ${\displaystyle Y=(y_{1},y_{2},\ldots ,y_{T})}$ ${\displaystyle y_{t}=o_{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})}$

функция  VITERBI для каждого состояния do end для каждого наблюдения do для каждого состояния do end for end for for do end for return end function ${\displaystyle (O,S,\Pi ,Y,A,B):X}$  ${\displaystyle i=1,2,\ldots ,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}\leftarrow T_{2}[z_{j},j]}$  ${\displaystyle x_{j-1}\leftarrow s_{z_{j-1}}}$    ${\displaystyle X}$

Переформулировано в краткой форме, близкой к Python :

функция  viterbi Tm: матрица переходов Em: матрица выбросов Хранить вероятность каждого состояния с учетом каждого наблюдения Удерживать обратный указатель на лучшее предшествующее состояние для s in : Определить вероятность каждого скрытого состояния в момент времени 0… для o in : … и после, отслеживая каждое состояние наиболее вероятное предыдущее состояние, k для s in : Найти k наилучшего конечного состояния для o in : Возврат от последнего наблюдения Вставить предыдущее состояние на наиболее вероятный путь. Использовать обратный указатель для поиска наилучшего возврата предыдущего состояния. ${\displaystyle (O,S,\Pi ,Tm,Em):best\_path}$ ${\displaystyle trellis\leftarrow matrix(length(S),length(O))}$ ${\displaystyle pointers\leftarrow matrix(length(S),length(O))}$  ${\displaystyle range(length(S))}$ ${\displaystyle trellis[s,0]\leftarrow \Pi [s]\cdot Em[s,O[0]]}$   ${\displaystyle range(1,length(O))}$  ${\displaystyle range(length(S))}$ ${\displaystyle k\leftarrow \arg \max(trellis[k,o-1]\cdot Tm[k,s]\cdot Em[s,o]\ {\mathsf {for}}\ k\ {\mathsf {in}}\ range(length(S)))}$  ${\displaystyle trellis[s,o]\leftarrow trellis[k,o-1]\cdot Tm[k,s]\cdot Em[s,o]}$  ${\displaystyle pointers[s,o]\leftarrow k}$  ${\displaystyle best\_path\leftarrow list()}$  ${\displaystyle k\leftarrow \arg \max(trellis[k,length(O)-1]\ {\mathsf {for}}\ k\ {\mathsf {in}}\ range(length(S)))}$  ${\displaystyle range(length(O)-1,-1,-1)}$ ${\displaystyle best\_path.insert(0,S[k])}$ ${\displaystyle k\leftarrow pointers[k,o]}$  ${\displaystyle best\_path}$

Объяснение

Предположим, нам дана скрытая марковская модель (СММ) с пространством состояний , начальными вероятностями нахождения в скрытом состоянии и переходными вероятностями перехода из состояния в состояние . Допустим, мы наблюдаем результаты . Наиболее вероятная последовательность состояний , которая производит наблюдения, задается рекуррентными соотношениями ^[10] ${\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}}$

${\displaystyle {\begin{aligned}V_{1,k}&=\mathrm {P} {\big (}y_{1}\ |\pi _{k}{\big )}\cdot \pi _{k},\\V_{t,k}&=\max _{x\in S}\left(\mathrm {P} {\big (}y_{t}\ |\pi _{k}{\big )}\cdot a_{x,k}\cdot V_{t-1,x}\right).\end{aligned}}}$

Вот вероятность наиболее вероятной последовательности состояний, ответственной за первые наблюдения, которые имеют свое конечное состояние. Путь Витерби можно получить, сохранив обратные указатели, которые запоминают, какое состояние использовалось во втором уравнении. Позвольте быть функцией, которая возвращает значение, используемое для вычисления if или if . Затем ${\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{aligned}x_{T}&=\arg \max _{x\in S}(V_{T,x}),\\x_{t-1}&=\mathrm {Ptr} (x_{t},t).\end{aligned}}}$

Здесь мы используем стандартное определение arg max .

Сложность этой реализации . Лучшая оценка существует, если вместо этого максимум во внутреннем цикле находится путем итерации только по состояниям, которые напрямую связаны с текущим состоянием (т. е. существует край от до ). Затем, используя амортизированный анализ, можно показать, что сложность равна , где – количество ребер в графе. ${\displaystyle O(T\times \left|{S}\right|^{2})}$ ${\displaystyle k}$ ${\displaystyle j}$ ${\displaystyle O(T\times (\left|{S}\right|+\left|{E}\right|))}$ ${\displaystyle E}$

Пример

Рассмотрим деревню, в которой все жители либо здоровы, либо имеют жар, и только деревенский врач может определить, есть ли у каждого из них жар. Врач диагностирует лихорадку, спрашивая пациентов, как они себя чувствуют. Жители деревни могут только ответить, что чувствуют себя нормально, кружится голова или холодно.

Врач считает, что состояние здоровья пациентов действует как дискретная цепь Маркова . Есть два состояния: «Здоровье» и «Лихорадка», но врач не может наблюдать их непосредственно; они скрыты от врача. Каждый день существует определенная вероятность того, что пациент скажет врачу: «Я чувствую себя нормально», «Мне холодно» или «У меня кружится голова», в зависимости от состояния здоровья пациента.

Наблюдения (норма, простуда, головокружение) вместе со скрытым состоянием (здоров, лихорадка) образуют скрытую марковскую модель (СММ) и могут быть представлены на языке программирования Python следующим образом :

obs  =  ( «нормальный» ,  «простуда» ,  «головокружение» ) States  =  ( «Здоровый» ,  «Лихорадка» ) start_p  =  { «Здоровый» :  0,6 ,  «Лихорадка» :  0,4 } trans_p  =  {  «Здоровый» :  { " Здоровый" :  0,7 ,  "Лихорадка" :  0,3 },  "Лихорадка" :  { "Здоровый" :  0,4 ,  "Лихорадка" :  0,6 }, } emit_p  =  {  "Здоровый" :  { "нормальный" :  0,5 ,  "простуда" :  0,4 ,  «головокружение» :  0,1 },  «лихорадка» :  { «нормальный» :  0,1 ,  «простуда» :  0,3 ,  «головокружение» :  0,6 }, }

В этом фрагменте кода start_pпредставляет мнение врача о том, в каком состоянии находится HMM при первом посещении пациента (все, что знает врач, это то, что пациент, как правило, здоров). Используемое здесь конкретное распределение вероятностей не является равновесным, которое (с учетом вероятностей перехода) составляет примерно {'Healthy': 0.57, 'Fever': 0.43}. Это trans_pпредставляет собой изменение состояния здоровья в основной цепи Маркова. В этом примере у пациента, который сегодня здоров, есть только 30% вероятность того, что завтра у него поднимется температура. Показывает emit_p, насколько вероятно каждое возможное наблюдение (нормальное, холодное или головокружение) с учетом основного состояния (здорового или лихорадочного). Здоровый пациент имеет 50%-ную вероятность чувствовать себя нормально; у того, у кого жар, вероятность головокружения составляет 60%.

Графическое представление данного HMM

Пациент приходит на прием три дня подряд, и врач обнаруживает, что в первый день пациент чувствует себя нормально, на второй день холодно, на третий день кружится голова. У врача возникает вопрос: какова наиболее вероятная последовательность состояний здоровья пациента, которая могла бы объяснить эти наблюдения? На этот вопрос отвечает алгоритм Витерби.

Def  Viterbi ( obs ,  States ,  start_p ,  trans_p ,  emite_p ): В  =  [{}] для  ул.  в  штатах : V [ 0 ]  [ st ]  =  { "prob" :  start_p [ st ]  *  emit_p [ st ]  [ obs [ 0 ]],  "prev" :  None } # Запускаем Витерби, когда t > 0 для  t  в  диапазоне ( 1 ,  len ( obs )): В. _ добавить ({}) для  ул.  в  штатах : max_tr_prob  =  V [ t  -  1 ]  [ states [ 0 ]]  [ "prob" ]  *  trans_p [ states [ 0 ]]  [ st ]  *  emit_p [ st ]  [ obs [ t ]] prev_st_selected  =  состояния [ 0 ] для  prev_st  в  состояниях [ 1 :]: tr_prob  =  V [ t  -  1 ]  [ prev_st ]  [ "prob" ]  *  trans_p [ prev_st ]  [ st ]  *  emit_p [ st ]  [ obs [ t ]] если  tr_prob  >  max_tr_prob : max_tr_prob  =  tr_prob prev_st_selected  =  prev_st max_prob  =  max_tr_prob V [ t ]  [ st ]  =  { "prob" :  max_prob ,  "prev" :  prev_st_selected } для  строки  в  dptable ( V ): печать ( строка ) выбор  =  [] макс_проб  =  0,0 best_st  =  Нет # Получить наиболее вероятное состояние и его возврат для  st данные  в V [ -1 ] . _  _ предметы ():  если  данные [ "prob" ]  >  max_prob : max_prob  =  данные [ "проб" ] best_st  =  ул опт . добавить ( best_st ) предыдущий  =  best_st # Следуем обратному пути до первого наблюдения для  t  в  диапазоне ( len ( V )  -  2 ,  - 1 ,  - 1 ): опт . вставить ( 0 ,  V [ t  +  1 ]  [ предыдущая ]  [ "предыдущая" ]) предыдущий  =  V [ t  +  1 ]  [ предыдущий ]  [ "предыдущий" ] print  ( "Шаги состояний: "  +  " " . join ( opt )  +  " с наибольшей вероятностью %s "  %  max_prob )защита  dptable ( V ): # Распечатываем таблицу шагов из словаря выход  " "  *  5  +  " " . join (( " %3d "  %  i )  для  i  в  диапазоне ( len ( V ))) для  состояния  в  V [ 0 ]: доходность  " %.7s : "  %  состояние  +  " " . join ( " %.7s "  %  ( " %lf "  %  v [ state ]  [ "prob" ])  for  v  в  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 ( obs ,  states ,  start_p ,  trans_p ,  emit_p )

Результат работы скрипта

$ python  viterbi_example.py  0 1 2 Здоровый: 0,30000 0,08400 0,00588 Лихорадка: 0,04000 0,02700 0,01512 Шаги состояний: Здоровый Здоровый Лихорадка с наибольшей вероятностью 0,01512

Это показывает, что наблюдения, ['normal', 'cold', 'dizzy']скорее всего, были инициированы государствами ['Healthy', 'Healthy', 'Fever']. Другими словами, учитывая наблюдаемую активность, пациент, скорее всего, был здоров в первый день, а также на второй день (несмотря на то, что в этот день он чувствовал холод), и только на третий день у него поднялась температура.

Работу алгоритма Витерби можно визуализировать с помощью решетчатой ​​диаграммы . Путь Витерби, по сути, является кратчайшим путем через эту решетку.

Алгоритм Витерби с мягким выводом

Алгоритм Витерби с мягким выходом ( SOVA ) — это вариант классического алгоритма Витерби.

SOVA отличается от классического алгоритма Витерби тем, что он использует модифицированную метрику пути, которая учитывает априорные вероятности входных символов и выдает мягкий вывод, указывающий на надежность решения.

Первым шагом в SOVA является выбор оставшегося пути, проходящего через один уникальный узел в каждый момент времени t . Поскольку каждый узел имеет 2 сходящиеся в нем ветви (при этом одна ветвь выбирается для формирования Пути Оставшегося в живых , а другая отбрасывается), разница в метриках ветвей (или стоимости ) между выбранной и отброшенной ветвями указывает на величину ошибки в выбор.

Эта стоимость накапливается по всему скользящему окну (обычно равна не менее пяти длинам ограничений), чтобы указать мягкую выходную меру надежности жесткого битового решения алгоритма Витерби.

Смотрите также

• Алгоритм ожидания-максимизации
• Алгоритм Баума – Уэлча
• Алгоритм вперед-назад
• Прямой алгоритм
• Код, исправляющий ошибки
• декодер Витерби
• Скрытая модель Маркова
• Маркировка частей речи
• Алгоритм поиска A*

Рекомендации

1. Ксавьер Ангера и др., «Диаризация говорящих: обзор недавних исследований», получено 19 августа 2010 г., IEEE TASLP.
2. 29 апреля 2005 г., Дж. Дэвид Форни-младший: Алгоритм Витерби: личная история
3. Дэниел Юрафски; Джеймс Х. Мартин. Речевая и языковая обработка . Пирсон Эдьюкейшн Интернэшнл. п. 246.
4. Шмид, Хельмут (2004). Эффективный анализ весьма неоднозначных контекстно-свободных грамматик с помощью битовых векторов (PDF) . Учеб. 20-я Международная конференция. по компьютерной лингвистике (COLING). дои : 10.3115/1220355.1220379 .
5. Кляйн, Дэн; Мэннинг, Кристофер Д. (2003). Синтаксический анализ A*: быстрый и точный выбор анализа Витерби (PDF) . Учеб. 2003 Конф. член Североамериканского отделения Ассоциации компьютерной лингвистики по технологиям человеческого языка (NAACL). стр. 40–47. дои : 10.3115/1073445.1073461 .
6. Станке, М.; Келлер, О.; Гундуз, И.; Хейс, А.; Ваак, С.; Моргенштерн, Б. (2006). «АВГУСТ: Ab initio предсказание альтернативных транскриптов». Исследования нуклеиновых кислот . 34 (проблема с веб-сервером): W435–W439. дои : 10.1093/nar/gkl200. ПМЦ 1538822 . ПМИД  16845043. 
7. Куах, Т.; Фарук, М. (1994). «Формирование трека максимального правдоподобия с помощью алгоритма Витерби». Материалы 33-й конференции IEEE по принятию решений и управлению . Том. 1. С. 271–276. дои : 10.1109/CDC.1994.410918.{{cite conference}}: CS1 maint: multiple names: authors list (link)
8. Ци Ван; Лей Вэй; Родни А. Кеннеди (2002). «Итеративное декодирование Витерби, формирование решетки и многоуровневая структура для высокоскоростного TCM с конкатенированной четностью». Транзакции IEEE в области коммуникаций . 50 : 48–55. дои : 10.1109/26.975743.
9. Быстрый декодер максимального правдоподобия для сверточных кодов (PDF) . Конференция по автомобильным технологиям. Декабрь 2002 г., стр. 371–375. doi :10.1109/VETECF.2002.1040367.
10. Син Э, слайд 11.

Общие ссылки

• Витерби А.Дж. (апрель 1967 г.). «Границы ошибок для сверточных кодов и асимптотически оптимальный алгоритм декодирования». Транзакции IEEE по теории информации . 13 (2): 260–269. дои : 10.1109/TIT.1967.1054010.(примечание: алгоритм декодирования Витерби описан в разделе IV.) Требуется подписка.
• Фельдман Дж., Абу-Файкаль И., Фриго М. (2002). «Быстрый декодер максимального правдоподобия для сверточных кодов». Материалы 56-й конференции IEEE по автомобильным технологиям . Том. 1. С. 371–375. CiteSeerX  10.1.1.114.1314 . doi :10.1109/VETECF.2002.1040367. ISBN 978-0-7803-7467-6. S2CID  9783963.
• Форни Г.Д. (март 1973 г.). «Алгоритм Витерби». Труды IEEE . 61 (3): 268–278. дои : 10.1109/PROC.1973.9030.Требуется подписка.
• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007). «Раздел 16.2. Декодирование Витерби». Численные рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8.
• Рабинер Л.Р. (февраль 1989 г.). «Учебное пособие по скрытым моделям Маркова и избранным приложениям для распознавания речи». Труды IEEE . 77 (2): 257–286. CiteSeerX  10.1.1.381.3454 . дои : 10.1109/5.18626. S2CID  13618539.(Описывает прямой алгоритм и алгоритм Витерби для HMM).
• Шингхал Р. и Годфрид Т. Туссен , «Эксперименты по распознаванию текста с помощью модифицированного алгоритма Витерби», Транзакции IEEE по анализу шаблонов и машинному интеллекту , Vol. ПАМИ-1, апрель 1979 г., стр. 184–193.
• Шингхал Р. и Годфрид Т. Туссен , «Чувствительность модифицированного алгоритма Витерби к исходной статистике», IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. ПАМИ-2, март 1980 г., стр. 181–185.

Внешние ссылки

• Реализации на Java, F#, Clojure, C# в Wikibooks
• Учебник по сверточному кодированию с декодированием Витерби, Чип Флеминг
• Учебное пособие по набору инструментов скрытой марковской модели (реализованному на C), содержащему описание алгоритма Витерби.
• Алгоритм Витерби доктора Эндрю Дж. Витерби (scholarpedia.org).

Реализации

• В Mathematica есть реализация как часть поддержки случайных процессов.
• Платформа обработки сигналов Susa предоставляет здесь реализацию C++ для кодов прямого исправления ошибок и выравнивания каналов.
• С++
• С#
• Джава
• Ява 8
• Юлия (HMMBase.jl)
• Перл
• Пролог
• Хаскелл
• Идти
• SFIHMM включает код для декодирования Витерби.