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

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

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

История

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

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

Алгоритм

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

Две матрицы размера $T\times \left|{S}\right|$ построены:

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

Позволять $\pi _{s}$ и $a_{r,s}$ — начальная и переходная вероятности соответственно, и пусть $b_{s,o}$ быть вероятностью наблюдения $o$ в штате $s$ . Тогда значения $P$ задаются рекуррентным соотношением ^[8] $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}}$ Формула для $Q_{t,s}$ идентично, за исключением того, что $\max$ заменяется на $\arg \max$ .Путь Витерби можно найти, выбрав максимум из $P$ на последнем временном шаге и после $Q$ в обратном порядке.

Псевдокод

function Viterbi(states, init, trans, emit, obs) is    input states: S hidden states    input init: initial probabilities of each state    input trans: S × S transition matrix    input emit: S × O emission matrix    input obs: sequence of T observations    prob ← T × S matrix of zeroes    prev ← empty T × S matrix    for each state s in states do        prob[0][s] = init[s] * emit[s][obs[0]]    for t = 1 to T - 1 inclusive do // t = 0 has been dealt with already        for each state s in states do            for each state r in states do                new_prob ← prob[t - 1][r] * trans[r][s] * emit[s][obs[t]]                if new_prob > prob[t][s] then                    prob[t][s] ← new_prob                    prev[t][s] ← r    path ← empty array of length T    path[T - 1] ← the state s with maximum prob[T - 1][s]    for t = T - 2 to 0 inclusive do        path[t] ← prev[t + 1][path[t + 1]]    return pathend

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

Пример

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

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

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

init = {"Healthy": 0.6, "Fever": 0.4}trans = {    "Healthy": {"Healthy": 0.7, "Fever": 0.3},    "Fever": {"Healthy": 0.4, "Fever": 0.6},}emit = {    "Healthy": {"normal": 0.5, "cold": 0.4, "dizzy": 0.1},    "Fever": {"normal": 0.1, "cold": 0.3, "dizzy": 0.6},}

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

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

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

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

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

День	1	2	3
Наблюдение	Нормальный	Холодный	Испытывающий головокружение
Здоровый	0.3	0.084	0.00588
Высокая температура	0.04	0.027	0.01512

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

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

Расширения

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

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

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

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

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

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

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

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

См. также

Ссылки

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

Общие ссылки

Витерби А.Дж. (апрель 1967 г.). «Границы ошибок для сверточных кодов и асимптотически оптимальный алгоритм декодирования». Транзакции IEEE по теории информации . 13 (2): 260–269. дои : 10.1109/TIT.1967.1054010 . (примечание: алгоритм декодирования Витерби описан в разделе IV.) Требуется подписка.
Фельдман Дж., Абу-Файкаль И., Фриго М. (2002). «Быстрый декодер максимального правдоподобия для сверточных кодов». Материалы 56-й конференции IEEE по автомобильным технологиям . Том. 1. С. 371–375. CiteSeerX 10.1.1.114.1314 . дои : 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 . Архивировано из оригинала 11 августа 2011 г. Проверено 17 августа 2011 г.
Рабинер Л.Р. (февраль 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++ для кодов прямого исправления ошибок и выравнивания каналов здесь .
С++
С#
Java, заархивировано 4 мая 2014 г. на Wayback Machine.
Ява 8
Юлия (HMMBase.jl)
Перл
Пролог. Архивировано 2 мая 2012 г. на Wayback Machine.
Хаскелл
Идти
SFIHMM включает код для декодирования Витерби.

[1] Ксавье Ангера и др., «Диаризация говорящих: обзор недавних исследований». Архивировано 12 мая 2016 г. на Wayback Machine , получено 19 августа 2010 г., IEEE TASLP.

[2] 29 апреля 2005 г., Дж. Дэвид Форни-младший: Алгоритм Витерби: личная история

[slp-3] Jump up to: ^а ^б Дэниел Юрафски; Джеймс Х. Мартин. Речевая и языковая обработка . Пирсон Эдьюкейшн Интернэшнл. п. 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/нар/gkl200 . ПМЦ 1538822 . ПМИД 16845043 .

[7] Куах, Т.; Фарук, М. (1994). «Формирование трека максимального правдоподобия с помощью алгоритма Витерби». Материалы 33-й конференции IEEE по принятию решений и управлению . Том. 1. С. 271–276. дои : 10.1109/CDC.1994.410918 . {{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка )

[8] Син Э, слайд 11.

[9] Ци Ван; Лей Вэй; Родни А. Кеннеди (2002). «Итеративное декодирование Витерби, формирование решетки и многоуровневая структура для высокоскоростного TCM с конкатенированной четностью». Транзакции IEEE в области коммуникаций . 50 : 48–55. дои : 10.1109/26.975743 .

[10] Быстрый декодер максимального правдоподобия для сверточных кодов (PDF) . Конференция по автомобильным технологиям . Декабрь 2002 г., стр. 371–375. дои : 10.1109/VETECF.2002.1040367 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]