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

История

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

Применение

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

Описание

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

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

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

Пусть задано пространство наблюдений [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*K[/math], матрица эмиссии В размера [math]K*N[/math], которая определяет вероятность наблюдения [math]o_j[/math] из состояния [math]s_i[/math], массив начальных вероятностей [math]\pi\,\![/math] размером [math]K[/math], показывающий вероятность того, что начальное состояние [math]s_i[/math]. Путь [math]Х =\{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]T_1[/math] и [math]T_2[/math] размером [math]K*T[/math]. Каждый элемент [math]T_1[i,j][/math] содержит вероятность того, что на [math]j[/math]-ом шаге мы находимся в состоянии [math]s_i[/math]. Каждый элемент [math]T_2[i,j][/math] содержит индекс наиболее вероятного состояния на [math]{j-1}[/math]-ом шаге.

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

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

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

Псевдокод

   //функция возвращает вектор [math]X[/math] - последовательность номеров наиболее вероятных состояний, которые привели к данным наблюдениям. 
   function viterbi [math](O,S,\pi\,\!,Y,A,B)[/math] 
       for [math]i=1..K[/math]
           [math]T_1[i,1]\longleftarrow\pi[i]\,\cdot B[i,Y[i]][/math]
           [math]T_2[i,1]\longleftarrow0[/math]
       for [math]i=2 .. T[/math]
           for [math]j=1..K[/math]
               [math]T_1[j,i]\longleftarrow \max_{1 \leqslant k\leqslant K} \limits {(T_1[k,i-1]\cdot A[k,j]\cdot B[j,Y[i]])}[/math] 
               [math]T_2[j,i]\longleftarrow\arg\max_{1 \leqslant k\leqslant K} \limits {(T_1[k,i-1]\cdot A[k,j]\cdot B[j,Y[i]])}[/math] 
               //функция arg max() ищет максимум выражения в скобках, возвращает аргумент (в нашем случае [math]k[/math]), при котором достигается этот максимум.
       [math]X[T]\longleftarrow\arg\max_{1 \leqslant k\leqslant K} \limits {(T_1[k,T])}[/math] 
       for [math]i=T...2[/math]
           [math]X[i-1]\longleftarrow T_2[X[i],i][/math]
       return [math]X[/math]

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

Ссылки

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