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

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

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

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

История

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

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

Алгоритм

Учитывая скрытую марковскую модель с набором скрытых состояний и последовательностью наблюдений , алгоритм Витерби находит наиболее вероятную последовательность состояний, которые могли бы произвести эти наблюдения. На каждом временном шаге алгоритм решает подзадачу, в которой рассматриваются только наблюдения до . ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle o_{0},o_{1},\dots ,o_{T-1}}$ ${\displaystyle t}$ ${\displaystyle o_{t}}$

Строятся две матрицы размера : ${\displaystyle T\times \left|{S}\right|}$

• ${\displaystyle P_{t,s}}$содержит максимальную вероятность оказаться в состоянии при наблюдении из всех возможных последовательностей состояний, ведущих к нему. ${\displaystyle s}$ ${\displaystyle t}$
• ${\displaystyle Q_{t,s}}$отслеживает предыдущее состояние, которое использовалось ранее в этой последовательности состояний максимальной вероятности. ${\displaystyle s}$

Пусть и будут начальной и переходной вероятностями соответственно, и пусть будет вероятностью наблюдения в состоянии . Тогда значения задаются рекуррентным соотношением ^[8] Формула для идентична для , за исключением того, что она заменена на , и . Путь Витерби можно найти, выбрав максимум на конечном временном шаге и следуя в обратном порядке. ${\displaystyle \pi _{s}}$ ${\displaystyle a_{r,s}}$ ${\displaystyle b_{s,o}}$ ${\displaystyle o}$ ${\displaystyle s}$ ${\displaystyle P}$ $${\displaystyle P_{t,s}={\begin{cases}\pi _{s}\cdot b_{s,o_{t}}&{\text{if }}t=0,\\\max _{r\in S}\left(P_{t-1,r}\cdot a_{r,s}\cdot b_{s,o_{t}}\right)&{\text{if }}t>0.\end{cases}}}$$ ${\displaystyle Q_{t,s}}$ ${\displaystyle t>0}$ ${\displaystyle \max }$ ${\displaystyle \arg \max }$ ${\displaystyle Q_{0,s}=0}$ ${\displaystyle P}$ ${\displaystyle Q}$

Псевдокод

Функция Viterbi(states, init, trans, emit, obs) — это  входные состояния: S скрытых состояний входные данные init: начальные вероятности каждого состояния входные данные trans: S × S матрица перехода входные данные emit: S × O матрица испускания входные данные obs: последовательность T наблюдений вероятность ← T × S матрица нулей предыдущая ← пустая матрица T × S для  каждого штата s в штатах делают prob[0][s] = init[s] * emit[s][obs[0]] для t = 1 до T - 1 включительно do  // t = 0 уже рассматривалось  для  каждого состояния s в states do  для  каждого состояния r в states do new_prob ← вероятность[t - 1][r] * транс[r][s] * испускание[s][наблюдение[t]] если new_prob > prob[t][s] тогда вероятность[t][s] ← новая_вероятность пред[т][с] ← г path ← пустой массив длины T path[T - 1] ← состояние s с максимальной вероятностью[T - 1][s] для t = T - 2 до 0 включительно сделать путь[t] ← предыдущий[t + 1][путь[t + 1]] конец обратного пути

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

Пример

Врач хочет определить, здоровы ли пациенты или у них лихорадка. Единственная информация, которую врач может получить, — это спросить пациентов, как они себя чувствуют. Пациенты могут сказать, что чувствуют себя нормально, испытывают головокружение или холод.

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

Наблюдения (нормально, холодно , головокружение) вместе со скрытыми состояниями (здорово, лихорадка) образуют скрытую марковскую модель (HMM). Из прошлого опыта вероятности этой модели были оценены как:

init = {"Здоров": 0.6, "Лихорадка": 0.4}транс = { "Здоров": {"Здоров": 0,7, "Лихорадка": 0,3}, "Лихорадка": {"Здоров": 0,4, "Лихорадка": 0,6},}испускать = { "Здоровый": {"нормальный": 0,5, "холодный": 0,4, "головокружение": 0,1}, "Лихорадка": {"нормальная": 0,1, "простуда": 0,3, "головокружение": 0,6},}

В этом коде initпредставляет убеждение врача о том, насколько вероятно, что пациент изначально будет здоров. Обратите внимание, что конкретное распределение вероятностей, используемое здесь, не является равновесным, которое {'Healthy': 0.57, 'Fever': 0.43}соответствовало бы вероятностям перехода. Вероятности перехода transпредставляют изменение состояния здоровья в базовой цепи Маркова. В этом примере пациент, который здоров сегодня, имеет только 30% шансов иметь лихорадку завтра. Вероятности выбросов emitпредставляют, насколько вероятно каждое возможное наблюдение (норма, простуда или головокружение) с учетом базового состояния (здоровье или лихорадка). Пациент, который здоров, имеет 50% шансов чувствовать себя нормально; пациент, у которого лихорадка, имеет 60% шансов почувствовать головокружение.

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

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

Во-первых, вычисляются вероятности быть здоровым или иметь лихорадку в первый день. Вероятность того, что пациент будет здоров в первый день и сообщит о нормальном самочувствии, составляет . Аналогично, вероятность того, что у пациента будет лихорадка в первый день и он сообщит о нормальном самочувствии, составляет . ${\displaystyle 0.6\times 0.5=0.3}$ ${\displaystyle 0.4\times 0.1=0.04}$

Вероятности для каждого из следующих дней можно рассчитать напрямую из предыдущего дня. Например, самая высокая вероятность быть здоровым на второй день и сообщить о простуде после сообщения о том, что он в норме в первый день, является максимальной из и . Это говорит о том, что более вероятно, что пациент был здоров в течение обоих этих дней, а не имел лихорадку и выздоравливал. ${\displaystyle 0.3\times 0.7\times 0.4=0.084}$ ${\displaystyle 0.04\times 0.4\times 0.4=0.0064}$

Остальные вероятности суммированы в следующей таблице:

Из таблицы видно, что у пациента, скорее всего, была лихорадка на третий день. Более того, существует последовательность состояний, заканчивающаяся на «лихорадка», вероятность получения которой равна 0,01512. Эта последовательность в точности (здоров, здоров, лихорадка), что можно обнаружить, прослеживая, какие состояния использовались при расчете максимумов (что является наилучшим предположением для каждого дня, но не всегда будет таковым). Другими словами, учитывая наблюдаемые действия, пациент, скорее всего, был здоров в первый день, а также во второй день (несмотря на то, что в тот день ему было холодно), и заболел лихорадкой только на третий день.

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

Расширения

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

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

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

Мягкий выходной алгоритм Витерби

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

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

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

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

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

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

Ссылки

1. Xavier Anguera et al., «Speaker Diarization: A Review of Recent Research» Архивировано 12 мая 2016 г. на Wayback Machine , получено 19 августа 2010 г., IEEE TASLP
2. 29 апреля 2005 г., Г. Дэвид Форни-младший: Алгоритм Витерби: личная история
3. Дэниел Джурафски; Джеймс Х. Мартин. Обработка речи и языка . Pearson Education International. стр. 246.
4. Шмид, Хельмут (2004). Эффективный синтаксический анализ крайне неоднозначных контекстно-свободных грамматик с битовыми векторами (PDF) . Труды 20-й Международной конференции по компьютерной лингвистике (COLING). doi : 10.3115/1220355.1220379 .
5. Кляйн, Дэн; Мэннинг, Кристофер Д. (2003). Анализ A*: быстрый точный выбор анализа Витерби (PDF) . Proc. 2003 Conf. Североамериканского отделения Ассоциации компьютерной лингвистики по технологиям человеческого языка (NAACL). стр. 40–47. doi : 10.3115/1073445.1073461 .
6. Станке, М.; Келлер, О.; Гюндуз, И.; Хейс, А.; Ваак, С.; Моргенштерн, Б. (2006). «AUGUSTUS: Ab initio predicting of alternative transcripts». Nucleic Acids Research . 34 (выпуск веб-сервера): W435–W439. doi :10.1093/nar/gkl200. PMC 1538822. PMID  16845043 . 
7. Quach, T.; Farooq, M. (1994). «Формирование траектории максимального правдоподобия с помощью алгоритма Витерби». Труды 33-й конференции IEEE по принятию решений и управлению . Том 1. С. 271–276. doi :10.1109/CDC.1994.410918.{{cite conference}}: CS1 maint: multiple names: authors list (link)
8. Син Э, слайд 11.
9. Ци Ван; Лэй Вэй; Родни А. Кеннеди (2002). «Итеративное декодирование Витерби, формирование решетки и многоуровневая структура для высокоскоростного конкатенированного четности TCM». Труды IEEE по коммуникациям . 50 : 48–55. doi :10.1109/26.975743.
10. Быстрый декодер максимального правдоподобия для сверточных кодов (PDF) . Конференция по транспортным технологиям. Декабрь 2002 г. С. 371–375. doi :10.1109/VETECF.2002.1040367.

Общие ссылки

• Viterbi AJ (апрель 1967 г.). «Границы ошибок для сверточных кодов и асимптотически оптимальный алгоритм декодирования». Труды IEEE по теории информации . 13 (2): 260–269. doi :10.1109/TIT.1967.1054010.(примечание: алгоритм декодирования Витерби описан в разделе IV.) Требуется подписка.
• Feldman J, Abou-Faycal I, Frigo M (2002). "Быстрый декодер максимального правдоподобия для сверточных кодов". Труды IEEE 56th Vehicular Technology Conference . Том 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. doi :10.1109/PROC.1973.9030.Требуется подписка.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Раздел 16.2. Декодирование Витерби". Numerical Recipes: The Art of Scientific Computing (3-е изд.). Нью-Йорк: Cambridge University Press. ISBN 978-0-521-88068-8. Архивировано из оригинала 2011-08-11 . Получено 2011-08-17 .
• Rabiner LR (февраль 1989). «Учебник по скрытым марковским моделям и избранным приложениям в распознавании речи». Труды IEEE . 77 (2): 257–286. CiteSeerX  10.1.1.381.3454 . doi :10.1109/5.18626. S2CID  13618539.(Описывает прямой алгоритм и алгоритм Витерби для HMM).
• Шингал, Р. и Годфрид Т. Туссен , «Эксперименты по распознаванию текста с помощью модифицированного алгоритма Витерби», Труды IEEE по анализу образов и машинному интеллекту , том PAMI-1, апрель 1979 г., стр. 184–193.
• Шингал, Р. и Годфрид Т. Туссен , «Чувствительность модифицированного алгоритма Витерби к исходной статистике», Труды IEEE по анализу шаблонов и машинному интеллекту , т. PAMI-2, март 1980 г., стр. 181–185.

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

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

Реализации

• В системе Mathematica реализована поддержка стохастических процессов
• Среда обработки сигналов Susa предоставляет реализацию C++ для кодов прямой коррекции ошибок и выравнивания каналов.
• С++
• С#
• Java Архивировано 2014-05-04 на Wayback Machine
• Ява 8
• Юлия (HMMBase.jl)
• Перл
• Пролог Архивировано 2012-05-02 на Wayback Machine
• Хаскелл
• Идти
• SFIHMM включает код для декодирования Витерби.