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

История

Алгоритм Витерби (англ. Viterbi algorithm) был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия, которая является популярным статистическим методом для создания статистической модели на основе данных и обеспечения оценки параметров модели (т.е. оценка неизвестного параметра максимизацией функции правдоподобия).

Определение:

Сверточный код (англ. Convolutional code ) — это корректирующий ошибки код, в котором На каждом такте работы кодера $\mathtt{k}$ символов входной полубесконечной последовательности преобразуются в $\mathtt{n} \gt \mathtt{k}$ символов выходной Также в преобразовании участвуют $\mathtt{m}$ предыдущих символов Выполняется свойство линейности (если $\mathtt{x}$ соответствует $\mathtt{X}$, а $\mathtt{y}$ соответствует $\mathtt{Y}$, то $\mathtt{ax} + \mathtt{by}$ соответствует $\mathtt{aX} + \mathtt{bY}$).

Описание

Алгоритм Витерби позволяет сделать наиболее вероятное предположение о последовательности состояний скрытой Марковской модели на основе последовательности наблюдений.

Определение:

Путь Витерби (англ. Viterbi path) — наиболее правдоподобная (наиболее вероятная) последовательность скрытых состояний.

Предположения, которые делает алгоритм:

1. Скрытые и наблюдаемые события должны быть последовательностью, которая упорядочена по времени.
2. Каждое скрытое событие должно соответствовать только одному наблюдаемому.
3. Вычисление наиболее вероятной скрытой последовательности до момента $\mathtt{t}$ зависит только от наблюдаемого события в этот момент времени и наиболее вероятной последовательности до момента $\mathtt{t} - 1$ (динамическое программирование).

Алгоритм

Входные данные:

1. Пространство наблюдений $\mathtt{O} =\{\mathtt{o_1},\mathtt{o_2} \ldots \mathtt{o_N}\}$
2. Пространство состояний $\mathtt{S} =\{\mathtt{s_1},\mathtt{s_2} \ldots \mathtt{s_K}\}$
3. Последовательность наблюдений $\mathtt{Y} =\{\mathtt{y_1},\mathtt{y_2} \ldots \mathtt{y_T}\}$
4. Матрица $\mathtt{A}$ переходов из $\mathtt{i}$-того состояния в $\mathtt{j}$-ое, размером $\mathtt{K} \times \mathtt{K}$
5. Матрица эмиссии $\mathtt{B}$ размера $\mathtt{K} \times \mathtt{N}$, которая определяет вероятность наблюдения $\mathtt{o_j}$ из состояния $\mathtt{s_i}$
6. Массив начальных вероятностей $\mathtt{\pi}$ размером $\mathtt{K}$, показывающий вероятность того, что начальное состояние $\mathtt{s_i}$

Выходные данные:

$\mathtt{X} =\{\mathtt{x_1},\mathtt{x_2} \ldots \mathtt{x_T}\}$ — последовательность состояний, которые привели к последовательности наблюдений $\mathtt{Y}$.

Алгоритм:

Создадим две матрицы $\mathtt{TState}$ и $\mathtt{TIndex}$ размером $\mathtt{K} \times \mathtt{T}$. Каждый элемент $\mathtt{TState}[\mathtt{i},\mathtt{j}]$ содержит вероятность того, что на $\mathtt{j}$-ом шаге мы находимся в состоянии $\mathtt{s_i}$. Каждый элемент $\mathtt{TIndex}[\mathtt{i},\mathtt{j}]$ содержит индекс наиболее вероятного состояния на $\mathtt{j} - 1$-ом шаге.

Шаг 1. Заполним первый столбец матриц $\mathtt{TState}$ на основании начального распределения, и $\mathtt{TIndex}$ нулями.

Шаг 2. Последовательно заполняем следующие столбцы матриц $\mathtt{TState}$ и $\mathtt{TIndex}$, используя матрицы вероятностей эмиссий и переходов.

Шаг 3. Рассматривая максимальные значения в столбцах матрицы $\mathtt{TIndex}$, начиная с последнего столбца, выдаем ответ.

Доказательство корректности:

Наиболее вероятная последовательность скрытых состояний получается следующими реккурентными соотношениями:

• $\mathtt{V_{1,k}} = \mathrm{P}(\mathtt{y_1} \mid \mathtt{k}) \cdot \pi_k$
• $\mathtt{V_{t,k}} = \max\limits_{\mathtt{x} \in \mathtt{S}}\left(\mathrm{P}(\mathtt{y_t} \mid \mathtt{k}) \cdot \mathtt{A_{x,k}} \cdot \mathtt{V_{t-1,x}}\right)$

Где $\mathtt{V_{t,k}}$ это вероятность наиболее вероятной последовательности, которая ответственна за первые $\mathtt{t}$ наблюдений, у которых $\mathtt{k}$ является завершающим состоянием. Путь Витерби может быть получен сохранением обратных указателей, которые помнят какое состояние было использовано во втором равенстве. Пусть $\mathrm{Ptr}(\mathtt{k},\mathtt{t})$ — функция, которая возвращает значение $\mathtt{x}$, использованное для подсчета $\mathtt{V_{t,k}}$ если $\mathtt{t} \gt 1$, или $\mathtt{k}$ если $\mathtt{t}=1$. Тогда:

• $\mathtt{x_T} = \mathtt{x} \in \mathtt{S} : \mathtt{V_{T,x}} \leadsto \max$
• $\mathtt{x_{t-1}} = \mathrm{Ptr}(\mathtt{x_t},\mathtt{t})$

Псевдокод

Функция возвращает вектор $\mathtt{X}$ : последовательность номеров наиболее вероятных состояний, которые привели к данным наблюдениям.

   $\mathrm{Viterbi}(\mathtt {O}, \mathtt {S},  \mathtt {P} , \mathtt {Y}, \mathtt {A}, \mathtt {B})$
       for $\mathtt{j} = 1$ to $\mathtt {K}$
           $\mathtt{TState}[\mathtt{i}, 1] = \mathtt{P}[\mathtt{i}] * \mathtt{B}[\mathtt{i}, \mathtt{Y}[1]]$
           $\mathtt{TIndex}[\mathtt{i}, 1] = 0$
       for $\mathtt{i} = 2$ to $\mathtt {T}$
           for $\mathtt{j} = 1$ to $\mathtt {K}$
               $\mathtt{TIndex}[\mathtt{j}, \mathtt{i}] = \arg\max_{1 \leqslant \mathtt{k}\leqslant \mathtt{K}} \limits (\mathtt{TState}[\mathtt{k}, \mathtt{i} - 1] * \mathtt{A}[\mathtt{k}, \mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[\mathtt{i}]])$ 
               // функция arg max() возвращает аргумент(в нашем случае $\mathtt{k}$), при котором достигается этот максимум
               $\mathtt{TState}[\mathtt{j}, \mathtt{i}] = \mathtt{TState}[\mathtt{TIndex}[\mathtt{j}, \mathtt{i}], \mathtt{i} - 1] * \mathtt{A}[\mathtt{k}, \mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[\mathtt{i}]]$  
       $\mathtt{X}[\mathtt{T}] = \arg\max_{1 \leqslant \mathtt{k}\leqslant \mathtt{K}} \limits (\mathtt{TState}[\mathtt{k}, \mathtt{T}])$ 
       for $\mathtt{i} = \mathtt{T}$ downto $2$
           $\mathtt{X}[\mathtt{i} - 1] = \mathtt{TIndex}[\mathtt{X}[\mathtt{i}], \mathtt{i}]$
       return $\mathtt{X}$

Таким образом, алгоритму требуется $\mathrm{O}(\mathtt{T}\times\left|{\mathtt{K}}\right|^2)$ времени.

Применение

Алгоритм используется в $\mathrm{CDMA}$ и $\mathrm{GSM}$ цифровой связи, в модемах и космических коммуникациях. Он нашел применение в распознавании речи и письма, компьютерной лингвистике и биоинформатике, а также в алгоритме свёрточного декодирования Витерби.

См. также

• Скрытые Марковские модели
• Алгоритм "Вперед-Назад"
• Алгоритм Баума-Велша

Источники информации

• Wikipedia — Viterbi algorithm
• Презентация