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

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

История

Алгоритм был предложен Эндрю Витерби, сотрудником корпорации Linkabit, в 1967 году в статье «Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm», опубликованной в журнале IEEE Transactions on Information Theory. Первоначально он предназначался для декодирования свёрточных кодов с максимальным правдоподобием в системах радиосвязи. В начале 1970-х годов алгоритм начали применять для решения задач распознавания речи и записи последовательностей ДНК. В 1978 году его впервые применили к скрытым марковским моделям для распознавания изолированных слов. С развитием вычислительной техники алгоритм Витерби стал базовым инструментом во многих областях машинного обучения и цифровой обработки сигналов.

Постановка задачи

Пусть задана скрытая марковская модель, определяемая:

• множеством состояний \( S = \{s_1, s_2, \dots, s_N\} \);
• последовательностью наблюдений \( O = o_1, o_2, \dots, o_T \);
• матрицей переходов между состояниями A, где \( a_{ij} = P(q_t = s_j | q_{t-1} = s_i) \);
• матрицей эмиссии B, где \( b_j(k) = P(o_t = v_k | q_t = s_j) \);
• начальным распределением вероятностей состояний \( \pi_i = P(q_1 = s_i) \).

Необходимо найти последовательность состояний \( Q^* = q_1, q_2, \dots, q_T \), которая максимизирует вероятность \( P(Q | O) \), то есть наиболее вероятную скрытую цепочку, породившую наблюдаемую последовательность.

Устройство и принцип работы

Алгоритм использует метод динамического программирования. Он строит решётку (треллис), где по оси времени отложены моменты \( t = 1, 2, \dots, T \), а по другой оси — возможные состояния. Для каждого момента времени и каждого состояния вычисляется два значения:

• вероятность наиболее вероятного пути, ведущего в данное состояние в данный момент времени;
• указатель (backpointer) на предыдущее состояние, которое обеспечило эту вероятность.

Рекурсивные соотношения

1. Инициализация (t = 1):

\[ v_1(i) = \pi_i \cdot b_i(o_1), \quad \text{ptr}_1(i) = 0. \]

1. Рекурсия (для t = 2, ..., T):

Для каждого состояния j: \[ v_t(j) = \max_{i} [ v_{t-1}(i) \cdot a_{ij} ] \cdot b_j(o_t), \text{ptr}_t(j) = \argmax_{i} [ v_{t-1}(i) \cdot a_{ij} ]. \]

1. Завершение (нахождение финального состояния):

\[ q_T^* = \argmax_i v_T(i). \]

1. Обратный проход (восстановление последовательности):

Для t = T-1, ..., 1: \[ q_t^ = \text{ptr}_{t+1}(q_{t+1}^). \]

В результате получается последовательность \( Q^ = q_1^, q_2^, \dots, q_T^ \), соответствующая максимальной вероятности.

Вычислительная сложность

В базовой реализации сложность алгоритма составляет \( O(T \cdot N^2) \), где T — длина последовательности, N — число состояний. При разреженных матрицах переходов (например, в лево-правых HMM) сложность может быть ниже. Память требуется \( O(T \cdot N) \) для хранения решётки и обратных указателей.

Применение

Декодирование свёрточных кодов

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

Распознавание речи

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

Обработка естественного языка

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

Биоинформатика

В анализе биологических последовательностей алгоритм Витерби используется для выравнивания последовательностей ДНК или белков по профилям HMM, поиска генов, предсказания вторичной структуры РНК и классификации семейств белков.

Голосовое управление и синтез речи

В современных голосовых помощниках (например, «Алиса» от Яндекса) алгоритм Витерби применяется на этапе акустического моделирования и распознавания команд. Он позволяет с вероятностной точки зрения выбрать наиболее подходящий вариант распознанного текста.

Другие области

• Оптический символьный распознавание (OCR): восстановление наиболее вероятной последовательности символов.
• Обработка геофизических сигналов (сейсмология, телеметрия).
• Финансовое моделирование: обнаружение режимов рынка по временным рядам.

Сравнение с другими методами

Алгоритм Витерби является разновидностью алгоритма максимального правдоподобия для HMM. В отличие от прямого перебора всех \( N^T \) возможных последовательностей (что практически нереализуемо при больших T), он даёт точное решение за полиномиальное время.

Алгоритм dynamic programming (DTW, динамическая трансформация временной шкалы) решает похожую задачу — выравнивание последовательностей — но без вероятностной модели. Алгоритм Витерби даёт более формальное вероятностное обоснование.

Существуют также приближённые методы, например, жадный поиск (beam search) — он сокращает пространство при помощи порогов вероятностей, но не гарантирует глобальный оптимум. Витерби даёт точное решение при условии правильности модели HMM.

Ограничения и критика

• Предположение о марковости первого порядка: в базовой модели алгоритм считает, что вероятность текущего состояния зависит только от предыдущего. Это упрощает вычисления, но может быть недостаточным для сложных реальных процессов.
• Чувствительность к параметрам модели: неточные оценки A, B, π приводят к ошибочным последовательностям. Оценки получают с помощью алгоритма Баума — Уэлча (частный случай EM-алгоритма), который также может сходиться к локальному экстремуму.
• Вычислительная нагрузка: на больших решётках (N > 1000, T > 10^6) память и время могут стать проблемой. Для таких случаев разрабатываются варианты с сокращением пространства (витерби с отсечением, витерби с разреженными матрицами).
• Отсутствие учёта долгосрочных зависимостей: алгоритм не способен моделировать контекст длиннее одного шага. В задачах машинного перевода или распознавания речи современные нейронные сети (LSTM, трансформеры) часто превосходят HMM с Витерби.

Связь с другими алгоритмами

• Алгоритм Баума — Уэлча (Baum-Welch) используется для обучения параметров HMM по наблюдаемым данным. Он является частным случаем EM-алгоритма.
• Прямая и обратная процедуры (Forward-Backward) вычисляют вероятности отдельных состояний в каждый момент времени, но не дают наиболее вероятную последовательность целиком.
• Алгоритм Витерби является «max-sum»-эквивалентом «суммирования» (Forward) — вместо суммы берётся максимум.

Интересные факты

• Эндрю Витерби стал миллиардером, основав компанию Qualcomm, разрабатывающую системы мобильной связи (CDMA). Алгоритм Витерби до сих пор используется в кодеках телефонов.
• Алгоритм Витерби — один из первых примеров применения динамического программирования в задаче декодирования. Он появился почти одновременно с алгоритмом Фано для декодирования.
• В 1991 году за вклад в теорию информации и разработку алгоритма Эндрю Витерби был удостоен премии Клода Шеннона.

Источники

• Viterbi, A. J. (1967). «Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm». IEEE Transactions on Information Theory, 13(2), 260–269.
• Rabiner, L. R. (1989). «A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition». Proceedings of the IEEE, 77(2), 257–286.
• Forney, G. D. (1973). «The Viterbi Algorithm». Proceedings of the IEEE, 61(3), 268–278.
• Дубков, А. А., Крейнделин, В. Б. (2010). «Скрытые марковские модели и их применение в анализе биологических последовательностей». Учебное пособие, МГУ.