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

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

в обратном порядке.

Псевдокод [ править ]

функция  Витерби (состояния, инициализация, транс, эмиссия, obs)  — это 
     входные  состояния: S скрытые состояния 
      ввод  init: начальные вероятности каждого состояния 
      входной  транс: матрица перехода S × S 
      входное  излучение: матрица выбросов S × O 
      входные  данные: последовательность T наблюдений 

      проб ← T × S матрица нулей 
      предыдущая ← пустая матрица T × S 
      для   каждого  штата s  в  штатах  делают 
          проб[0][s] = инициализация[s] * испускание[s][obs[0]] 

      для  t = 1  до  T - 1  включительно do   // t = 0 уже рассмотрено 
         для   каждого  состояния s  в  состояниях  do 
             для   каждого  состояния r  в  состояниях  do 
                  new_prob ← prob[t - 1][r] * trans[r][s] * испускать[s][obs[t]] 
                  если  new_prob > проб[t][s]  , то 
                      проб[t][s] ← new_prob 
                      предыдущая[t][s] ← r 

      путь ← пустой массив длины T 
      path[T - 1] ← состояние s с максимальной вероятностью[T - 1][s] 
      для  t = T - от 2  до  0  включительно делаем 
          путь[t] ← предыдущая[t + 1][путь[t + 1]] 

      Обратный  путь 
  конец

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

Пример [ править ]

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

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

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

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%.

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

Сначала рассчитывается вероятность того, что вы будете здоровы или у вас поднимется температура в первый день. Учитывая, что пациент сообщает, что чувствует себя нормально, вероятность того, что он на самом деле был здоров, равна $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 сходящиеся в нем ветви (при этом одна ветвь выбирается для формирования Пути Оставшегося в живых , а другая отбрасывается), разница в метриках ветвей (или стоимости ) между выбранной и отброшенной ветвями указывает на величину ошибки в выбор.

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

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

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

^ Ксавьер Ангера и др., «Диаризация говорящих: обзор недавних исследований» , получено 19 августа 2010 г., IEEE TASLP.
^ 29 апреля 2005 г., Дж. Дэвид Форни-младший: Алгоритм Витерби: личная история
^ Перейти обратно: ^а ^б Дэниел Юрафски; Джеймс Х. Мартин. Речевая и языковая обработка . Пирсон Эдьюкейшн Интернэшнл. п. 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 .
Рабинер Л.Р. (февраль 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 включает код для декодирования Витерби.

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

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

[slp-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/нар/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]