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

История

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

Описание

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

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

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

Пусть задано пространство наблюдений [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], начиная с последнего столбца, выдаем ответ.

Псевдокод

 //функция возвращает вектор X — последовательность номеров наиболее вероятных состояний, которые привели к данным наблюдениям. 
 viterbi(O, S, [math] \pi [/math], Y, A, B): 
     for i = 1..K
         TState[i, 1] = [math] \pi [/math][i] * B[i, Y[i]]
         TIndex[i, 1] = 0
     for i = 2..T
         for j = 1..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() ищет максимум выражения в скобках и возвращает аргумент (в нашем случае [math]k[/math]), при котором достигается этот максимум.
     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
• Презентация