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

История

Алгоритм Витерби был представлен в 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].

Скрытая марковская модель.

Модель представляет из себя марковскую цепь, для которой нам известны начальная вероятность и матрица вероятностей переходов. Скрытой она называется потому, что мы не имеем информации о ее текущем состоянии. Мы получаем информацию на основе некоторого наблюдения, в рассмотренном ниже алгоритме мы будем использовать просто натуральное число от 1 до [math]N[/math], как индекс наблюдаемого события. Для каждого состояния скрытой марковской модели задан вектор вероятности эмиссии, который характеризует вероятность наблюдени каждого события, когда модель находится в этом состоянии. Совокупность таких векторов образует матрицу эмиссии.

Пример скрытой марковской модели.

Рассмотрим пример скрытой марковской модели. У Деда Мороза есть три мешка с подарками в разноцветной упаковке: красной, синей, зеленой и фиолетовой. Ночью Дед Мороз пробирается в квартиру и тайком выкладывает подарки под елкой в ряд, доставая по одному подарку из мешка. Наутро мы обнаруживаем упорядоченную последовательность из пяти подарков и хотим сделать наилучшее предположение о последовательности мешков, из которых он доставал эти подарки. Дед Мороз с мешками — скрытая марковская модель. При этом 4 цвета — пространство из [math]N[/math] наблюдений, 3 мешка — количество состояний [math]K[/math], 5 подарков — наши [math]T[/math] наблюдений, каждое из которых представлено цифрой — номером цвета — от 1 до 5. Мы знаем, каковы вероятности того, что Дед Мороз начнет доставать подарки из мешка с номером [math]i[/math] — вектор [math]\pi[i][/math]. Мы также знаем матрицу переходов [math]A[/math], какова вероятность того, что от мешка с номером [math]i[/math] Дед Мороз переходит к мешку с номером [math]j[/math]. Мешки Деда Мороза бесконечны, но мы точно знаем, каково соотношение цветов подарков в каждом мешке ему загрузили на заводе в Великом Устюге. Это матрица вероятностей эмиссии [math]B[/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...2
         X[i - 1] = TIndex[X[i], i]
     return X

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

Применение

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

Ссылки

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