Алгоритм Витерби — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 31: Строка 31:
  
 
Наиболее вероятная последовательность скрытых состояний получается следующими реккурентными соотношениями:
 
Наиболее вероятная последовательность скрытых состояний получается следующими реккурентными соотношениями:
 
+
#<tex>V_{1,k} = \mathrm{P}(y_1 \mid k) \cdot \pi_k</tex>
<tex>
+
#<tex>V_{t,k} = \max_{x \in S} \left(  \mathrm{P}( y_t \mid k) \cdot a_{x,k} \cdot V_{t-1,x}\right)</tex>
V_{1,k} = \mathrm{P}(y_1 \mid k) \cdot \pi_k \\
+
#<tex>x_T = \arg\max_{x \in S} (V_{T,x})</tex>
V_{t,k} = \max_{x \in S} \left(  \mathrm{P}( y_t \mid k) \cdot a_{x,k} \cdot V_{t-1,x}\right) \\
+
#<tex>x_{t-1} = \mathrm{Ptr}(x_t,t)</tex>
x_T = \arg\max_{x \in S} (V_{T,x}) \\
 
x_{t-1} = \mathrm{Ptr}(x_t,t)
 
</tex>
 
 
Где <tex>V_{t,k}</tex> это вероятность наиболее вероятной последовательностельности, которая ответственна за первые <tex>t</tex> наблюдений, у которых <tex>k</tex> является завершающим состоянием.
 
Где <tex>V_{t,k}</tex> это вероятность наиболее вероятной последовательностельности, которая ответственна за первые <tex>t</tex> наблюдений, у которых <tex>k</tex> является завершающим состоянием.
  

Версия 15:24, 2 апреля 2018

История

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

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

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

  1. [math]V_{1,k} = \mathrm{P}(y_1 \mid k) \cdot \pi_k[/math]
  2. [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]
  3. [math]x_T = \arg\max_{x \in S} (V_{T,x})[/math]
  4. [math]x_{t-1} = \mathrm{Ptr}(x_t,t)[/math]

Где [math]V_{t,k}[/math] это вероятность наиболее вероятной последовательностельности, которая ответственна за первые [math]t[/math] наблюдений, у которых [math]k[/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 цифровой связи, в модемах и космических коммуникациях. Он нашел применение в распознавании речи и письма, компьютерной лингвистике и биоинформатике, а также в алгоритме свёрточного декодирования Витерби.

См. также

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