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

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

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

История [ править ]

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

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

Расширения [ править ]

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

С помощью алгоритма, называемого итеративным декодированием Витерби, можно найти подпоследовательность наблюдения, которая наилучшим образом (в среднем) соответствует заданной скрытой марковской модели . Этот алгоритм предложен Qi Wang et al. разобраться с турбо-кодом . ^[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} [я, 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}=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,\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 :

# вероятность == p. Tm: матрица перехода. Em: матрица излучения.функция viterbi (O, S, Π, Tm, Em): best_path решетка ← матрица (длина (S), длина (O)) # Удерживать п. каждого государства с учетом каждого наблюдения. # Определить каждое скрытое состояние p. в момент времени 0… для s в диапазоне (длина (S)): решетка [s, 0] ← Π [s] * Em [s, O [0]]  #… А затем, предполагая наиболее вероятное предшествующее состояние каждого состояния, k. для o в диапазоне (1, длина (O)): для s в диапазоне (длина (S)): k ← argmax ( k в решетке [ k , o-1] * Tm [ k , s] * Em [s, о]) решетка [s, o] ← решетка [ k , o-1] * Tm [ k , s] * Em [s, o] лучший_путь ← список () for o in range (-1, - (length (O) +1), -1): # Возврат к последнему наблюдению. k ← argmax ( k in trellis [ k , o]) # Скорее всего, состояние в o best_path.insert (0, S [ k ]) # отмечен для возврата. вернуть best_path

Объяснение

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

Вот вероятность наиболее вероятной последовательности состояний, ответственной за первые наблюдения, которые имеют в качестве своего конечного состояния. Путь Витерби можно получить, сохранив обратные указатели, которые запоминают, какое состояние использовалось во втором уравнении. Позвольте быть функцией, которая возвращает значение, используемое для вычисления 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 :

набл  =  ( "нормальный" ,  "холодный" ,  "головокружение" ) состояния  =  ( "Здоровый" ,  "Лихорадка" ) 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}. transition_pПредставляет собой изменение состояния здоровья в базовой цепи Маркова. В этом примере вероятность того, что завтра у пациента поднимется температура, составляет всего 30%, если он здоров сегодня. Символ emit_pпоказывает, насколько вероятно каждое возможное наблюдение, нормальное состояние, простуда или головокружение, с учетом их основного состояния, здоровья или лихорадки. Если пациент здоров, вероятность того, что он чувствует себя нормально, составляет 50%; если у него высокая температура, вероятность головокружения составляет 60%.

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

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

В текущем примере алгоритм прямого / Витерби используется следующим образом:

Витерби ( набл ,  состояния ,  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 ветви (одна ветвь выбирается для формирования Survivor Path , а другая отбрасывается), разница в показателях ветвления (или стоимости ) между выбранными и отброшенными ветвями указывает на величину ошибки в выбор.

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

См. Также [ править ]

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

Ссылки [ править ]

Общие ссылки [ править ]

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

Реализации [ править ]

• В Mathematica есть реализация как часть поддержки случайных процессов.
• Суз основа обработки сигналов обеспечивает реализацию C ++ для прямого исправления ошибок кодов и выравнивания каналов здесь .
• C ++
• C #
• Ява
• Java 8
• Perl
• Пролог
• Haskell
• Идти
• SFIHMM включает код для декодирования Витерби.

Внешние ссылки [ править ]

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