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

История

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

Описание

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

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

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

Пусть задано пространство наблюдений [math]O =\{o_1,o_2...o_N\}[/math], пространство состояний [math]S =\{s_1,s_2...s_K\}[/math], последовательность наблюдений [math]Y =\{y_1,y_2...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...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]{X}[/math] : последовательность номеров наиболее вероятных состояний, которые привели к данным наблюдениям.

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

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

Применение

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

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

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