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

История

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

Описание

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

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

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

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

1. Скрытые и наблюдаемые события должны быть последовательностью, которая чаще всего упорядочена по времени.
2. Каждое скрытое событие должно соответствовать только одному наблюдаемому.
3. Вычисление наиболее вероятной скрытой последовательности до момента [math]t[/math] зависит только от наблюдаемого события в этот момент времени и наиболее вероятной последовательности до момента [math]t − 1[/math] (динамическое программирование).

Алгоритм

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

Пусть задано пространство наблюдений [math]O =\{o_1,o_2 \ldots o_N\}[/math], пространство состояний [math]S =\{s_1,s_2 \ldots s_K\}[/math], последовательность наблюдений [math]Y =\{y_1,y_2 \ldots y_T\}[/math], матрица [math]A[/math] переходов из [math]i[/math]-того состояния в [math]j[/math]-ое, размером [math]K \times K[/math], матрица эмиссии [math] B [/math] размера [math]K \times N[/math], которая определяет вероятность наблюдения [math]o_j[/math] из состояния [math]s_i[/math], массив начальных вероятностей [math]\pi[/math] размером [math]K[/math], показывающий вероятность того, что начальное состояние [math]s_i[/math]. Путь [math]X =\{x_1,x_2 \ldots x_T\}[/math] — последовательность состояний, которые привели к последовательности наблюдений [math]Y[/math].

Алгоритм:

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

Шаг 1. Заполним первый столбец матриц [math]TState[/math] на основании начального распределения, и [math]TIndex[/math] нулями.

Шаг 2. Последовательно заполняем следующие столбцы матриц [math]TState[/math] и [math]TIndex[/math], используя матрицы вероятностей эмиссий и переходов.

Шаг 3. Рассматривая максимальные значения в столбцах матрицы [math]TIndex[/math], начиная с последнего столбца, выдаем ответ.

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

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

• [math]V_{1,k} = \mathrm{P}(y_1 \mid k) \cdot \pi_k[/math]
• [math]V_{t,k} = \max_{x \in S} \left( \mathrm{P}( y_t \mid k) \cdot A_{x,k} \cdot V_{t-1,x}\right)[/math]

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

• [math]x_T = \arg\max_{x \in S} (V_{T,x})[/math]
• [math]x_{t-1} = \mathrm{Ptr}(x_t,t)[/math]

Псевдокод

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

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

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

Применение

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

См. также

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

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

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