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

2017-06-09T19:47:33Z

178.62.102.23: /* Псевдокод */

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

== Описание ==
Алгоритм Витерби позволяет сделать наилучшее предположение о последовательности состояний [[Скрытые Марковские модели|скрытой Марковской модели]] на основе последовательности наблюдений. Эта последовательность состояний называется путем Витерби.
{{Определение
|id=def1.
|definition='''Путь Витерби''' {{---}} наиболее правдоподобная последовательность скрытых состояний.
}}

Пусть задано пространство наблюдений <tex>O =\{o_1,o_2...o_N\}</tex>, пространство состояний <tex>S =\{s_1,s_2...s_K\}</tex>, последовательность наблюдений <tex>Y =\{y_1,y_2...y_T\}</tex>, матрица <tex>A</tex> переходов из <tex>i</tex>-того состояния в <tex>j</tex>-ое, размером <tex>K \times K</tex>, матрица эмиссии <tex> B </tex> размера <tex>K \times N</tex>, которая определяет вероятность наблюдения <tex>o_j</tex> из состояния <tex>s_i</tex>, массив начальных вероятностей <tex>\pi</tex> размером <tex>K</tex>, показывающий вероятность того, что начальное состояние <tex>s_i</tex>. Путь <tex>X =\{x_1,x_2...x_T\}</tex> {{---}} последовательность состояний, которые привели к последовательности наблюдений <tex>Y</tex>.

== Алгоритм ==
Создадим две матрицы <tex>TState</tex> и <tex>TIndex</tex> размером <tex>K \times T</tex>. Каждый элемент <tex>TState[i,j]</tex> содержит вероятность того, что на <tex>j</tex>-ом шаге мы находимся в состоянии <tex>s_i</tex>. Каждый элемент <tex>TIndex[i,j]</tex> содержит индекс наиболее вероятного состояния на <tex>{j-1}</tex>-ом шаге.

'''Шаг 1.''' Заполним первый столбец матриц <tex>TState</tex> на основании начального распределения, и <tex>TIndex</tex> нулями.

'''Шаг 2.''' Последовательно заполняем следующие столбцы матриц <tex>TState</tex> и <tex>TIndex</tex>, используя матрицы вероятностей эмиссий и переходов.

'''Шаг 3.''' Рассматривая максимальные значения в столбцах матрицы <tex>TIndex</tex>, начиная с последнего столбца, выдаем ответ.

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

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

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

== Ссылки ==
* [[wikipedia:Viterbi_algorithm|Wikipedia {{---}} Viterbi algorithm]]
* [http://www.cs.sfu.ca/~oschulte/teaching/726/spring11/slides/mychapter13b.pdf Презентация]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Марковские цепи]]
[[Категория: Динамическое программирование]]

Викиконспекты - Вклад участника [ru]

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