Алгоритм Витерби является динамическое программирование алгоритма для получения максимальной апостериорной вероятности оценки в наиболее вероятной последовательности скрытых состояний, называется путь Витерби -Вот приводит к последовательности наблюдаемых событий, особенно в контексте информационных источников Маркова и скрытые марковские модели (HMM).
Алгоритм нашел универсальное применение при декодировании сверточных кодов, используемых как в цифровой сотовой связи CDMA, так и в GSM , модемах с коммутируемым доступом, спутниковой связи, связи в дальнем космосе и беспроводных локальных сетях стандарта 802.11 . В настоящее время также широко используется в распознавании речи , синтеза речи , diarization , [1] ключевое слово пятнистость , компутационное и биоинформатики . Например, при преобразовании речи в текст(распознавание речи) акустический сигнал рассматривается как наблюдаемая последовательность событий, а строка текста считается «скрытой причиной» акустического сигнала. Алгоритм Витерби находит наиболее вероятную строку текста с учетом акустического сигнала.
История
Алгоритм Витерби назван в честь Эндрю Витерби , который предложил его в 1967 году в качестве алгоритма декодирования сверточных кодов по зашумленным цифровым каналам связи. [2] Тем не менее, он имеет историю множественных изобретений , по крайней мере, с семью независимыми открытиями, в том числе открытиями Витерби, Нидлмана и Вунша , Вагнера и Фишера . [3] Он был введен в обработку естественного языка как метод тегирования частей речи еще в 1987 году.
«Путь Витерби» и «алгоритм Витерби» стали стандартными терминами для применения алгоритмов динамического программирования к задачам максимизации, связанным с вероятностями. [3] Например, при статистическом синтаксическом анализе алгоритм динамического программирования может использоваться для обнаружения единственного наиболее вероятного контекстно-свободного вывода (синтаксического анализа) строки, который обычно называется "синтаксическим анализом Витерби". [4] [5] [6] Другое приложение - отслеживание цели , где вычисляется трек, который присваивает максимальную вероятность последовательности наблюдений. [7]
Расширения
Обобщение алгоритма Витерби, называемое алгоритмом максимальной суммы (или алгоритмом максимального произведения ), может использоваться для поиска наиболее вероятного присвоения всех или некоторого подмножества скрытых переменных в большом количестве графических моделей , например, байесовских сетей , Марковских сетей. случайные поля и условные случайные поля . Скрытые переменные, как правило, должны быть связаны способом, подобным HMM, с ограниченным количеством связей между переменными и некоторой линейной структурой между переменными. Общий алгоритм включает передачу сообщений и по существу аналогичен алгоритму распространения убеждений (который является обобщением алгоритма вперед-назад ).
С помощью алгоритма, называемого итеративным декодированием Витерби, можно найти подпоследовательность наблюдения, которая наилучшим образом (в среднем) соответствует заданной скрытой марковской модели . Этот алгоритм предложен Qi Wang et al. разобраться с турбо-кодом . [8] Итеративное декодирование Витерби работает путем итеративного вызова модифицированного алгоритма Витерби, переоценивающего оценку заполнителя до сходимости.
Был предложен альтернативный алгоритм - алгоритм Ленивого Витерби . [9] Для многих приложений, представляющих практический интерес, в условиях разумного шума ленивый декодер (использующий алгоритм Ленивого Витерби) намного быстрее, чем исходный декодер Витерби (использующий алгоритм Витерби). В то время как исходный алгоритм Витерби вычисляет каждый узел в решетке возможных результатов, алгоритм Ленивого Витерби поддерживает список узлов с приоритетами для оценки по порядку, а количество требуемых вычислений обычно меньше (и никогда не больше), чем обычный алгоритм Витерби для тот же результат. Однако аппаратное распараллеливание [ требуется пояснение ] не так-то просто .
Псевдокод
Этот алгоритм генерирует путь , которая представляет собой последовательность состояний которые генерируют наблюдения с участием , где это количество возможных наблюдений в пространстве наблюдения .
Две двухмерные таблицы размеров построены:
- Каждый элемент из хранит вероятность наиболее вероятного пути на данный момент с участием что порождает .
- Каждый элемент из магазины наиболее вероятного пути на данный момент
Записи в таблице заполняются в порядке возрастания :
- ,
- ,
с участием а также как определено ниже. Обратите внимание, что не обязательно должно присутствовать в последнем выражении, поскольку оно неотрицательно и не зависит от и, таким образом, не влияет на argmax.
- Вход
- Наблюдение пространства ,
- пространство состояний ,
- массив начальных вероятностей такой, что хранит вероятность того, что ,
- последовательность наблюдений такой, что если наблюдение во время является ,
- матрица перехода размера такой, что хранит вероятность перехода из состояния заявить ,
- матрица выбросов размера такой, что хранит вероятность наблюдения от государства .
- Выход
- Наиболее вероятная последовательность скрытых состояний
функция ВИТЕРБИ для каждого государства делать конец для каждого наблюдения сделать для каждого штата делать конец за конец для для делать конец для возвращения конечная функция
Переформулировано в сжатой форме, близкой к 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]
Здесь вероятность наиболее вероятной последовательности состояний отвечает за первый наблюдения, которые имеют как его окончательное состояние. Путь Витерби можно получить, сохранив обратные указатели, которые запоминают, какое состояниеиспользовался во втором уравнении. Позволять быть функцией, которая возвращает значение используется для вычисления если , или же если . потом
Здесь мы используем стандартное определение arg max .
Сложность этой реализации составляет . Более точная оценка существует, если вместо этого максимум во внутреннем цикле найден путем итерации только по состояниям, которые напрямую связаны с текущим состоянием (т. Е. Есть край от к ). Тогда, используя амортизированный анализ, можно показать, что сложность, где количество ребер в графе.
Пример
Рассмотрим деревню, в которой все жители либо здоровы, либо у них температура, и только деревенский врач может определить, есть ли у них температура. Врач диагностирует лихорадку, спрашивая пациентов, как они себя чувствуют. Жители могут только ответить, что чувствуют себя нормально, головокружение или холод.
Врач считает, что состояние здоровья его пациентов работает как дискретная цепь Маркова . Есть два состояния: «Здоровое» и «Лихорадка», но врач не может наблюдать за ними напрямую; они скрыты от него. Каждый день есть определенный шанс, что пациент скажет врачу, что он «нормальный», «холодный» или «головокружительный», в зависимости от состояния его здоровья.
В наблюдения (нормальный, холод, головокружение) вместе с скрытом состоянии (здоровый, лихорадка) образуют скрытые модели Маркова (СММ), и может быть представлена следующим образом в языке программирования Python :
набл = ( "нормальный" , "холодный" , "головокружение" ) состояния = ( "Здоровый" , "Лихорадка" ) start_p = { "Здоровый" : 0.6 , "Лихорадка" : 0,4 } trans_p = { "Здоровый" : { " Здоровый » : 0,7 , « Лихорадка » : 0,3 }, « Лихорадка » : { « Здоровый » : 0,4 , « Лихорадочный » : 0,6 }, } emit_p = { « Здоровый » : { « нормальный » : 0,5 , « холодный » : 0,4 , "dizzy" : 0,1 }, "Fever" : { "normal" : 0,1 , "холодный" : 0,3 , "dizzy" : 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 ): # Распечатать таблицу шагов из словаря yield "" * 5 + "" . join (( " % 3d " % i ) для i в диапазоне ( len ( V ))) для состояния в V [ 0 ]: yield " % .7s :" % state + "" . join ( " % .7s " % ( " % lf " % 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 . Поскольку каждый узел имеет две сходящиеся к нему ветви (одна ветвь выбирается для формирования Survivor Path , а другая отбрасывается), разница в показателях ветвления (или стоимости ) между выбранными и отброшенными ветвями указывает на величину ошибки в выбор.
Эта стоимость накапливается в течение всего скользящего окна ( как правило , равна , по меньшей мере пяти длин ограничений), чтобы указать мягкую выходную меру надежности жесткого битового решения по Витерби алгоритма.
Смотрите также
- Алгоритм ожидания – максимизации
- Алгоритм Баума – Велча
- Вперед-назад алгоритм
- Прямой алгоритм
- Код исправления ошибок
- Декодер Витерби
- Скрытая марковская модель
- Пометка части речи
- Алгоритм поиска A *
Рекомендации
- ^ Xavier Angueraдр. «Диаризация: Обзор последних исследований» , получен 19 августа 2010, IEEE TASLP
- ^ 29 апреля 2005 г., Дж. Дэвид Форни-младший: Алгоритм Витерби: личная история
- ^ a b Даниэль Джурафски; Джеймс Х. Мартин. Обработка речи и языка . Pearson Education International. п. 246.
- ^ Шмид, Гельмут (2004). Эффективный синтаксический анализ весьма неоднозначных контекстно-свободных грамматик с помощью битовых векторов (PDF) . Proc. 20-я Международная конф. по компьютерной лингвистике (COLING). DOI : 10.3115 / 1220355.1220379 .
- ^ Кляйн, Дэн; Мэннинг, Кристофер Д. (2003). A * parsing: быстрый и точный выбор синтаксического анализа Витерби (PDF) . Proc. Конференция 2003 г. Североамериканского отделения Ассоциации компьютерной лингвистики по технологиям человеческого языка (NAACL). С. 40–47. DOI : 10.3115 / 1073445.1073461 .
- ^ Станке, М .; Keller, O .; Gunduz, I .; Hayes, A .; Waack, S .; Моргенштерн, Б. (2006). «АВГУСТ: Ab initio предсказание альтернативных транскриптов» . Исследования нуклеиновых кислот . 34 (выпуск веб-сервера): W435 – W439. DOI : 10.1093 / NAR / gkl200 . PMC 1538822 . PMID 16845043 .
- ^ Quach, T .; Фарук, М. (1994). «Формирование трека максимального правдоподобия с помощью алгоритма Витерби». Труды 33-й конференции IEEE по решениям и контролю . 1 . С. 271–276. DOI : 10.1109 / CDC.1994.410918 .CS1 maint: несколько имен: список авторов ( ссылка )
- ^ Ци Ван; Лэй Вэй; Родни А. Кеннеди (2002). «Итеративное декодирование Витерби, формирование решетчатой диаграммы и многоуровневая структура для высокоскоростной сцепленной с проверкой четности TCM». Транзакции IEEE по коммуникациям . 50 : 48–55. DOI : 10.1109 / 26.975743 .
- ^ Быстрый декодер максимального правдоподобия для сверточных кодов (PDF) . Конференция по автомобильной технике . Декабрь 2002. С. 371–375. DOI : 10,1109 / VETECF.2002.1040367 .
- ^ Xing E, слайд 11.
Общие ссылки
- Витерби 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).