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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
Строка 1: Строка 1:
 
== История ==
 
== История ==
Алгоритм Витерби был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия.
+
Алгоритм Витерби(англ. Viterbi algorithm) был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия.
  
 
== Описание ==
 
== Описание ==
Алгоритм Витерби позволяет сделать наилучшее предположение о последовательности состояний [[Скрытые Марковские модели|скрытой Марковской модели]] на основе последовательности наблюдений. Эта последовательность состояний называется путем Витерби.
+
Алгоритм Витерби позволяет сделать наилучшее предположение о последовательности состояний [[Скрытые Марковские модели|скрытой Марковской модели]] на основе последовательности наблюдений. Эта последовательность состояний называется путем Витерби(англ. Viterbi path).
 
{{Определение
 
{{Определение
 
|id=def1.  
 
|id=def1.  
Строка 43: Строка 43:
 
Алгоритм используется в CDMA и GSM цифровой связи, в модемах и космических коммуникациях. Он нашел применение в распознавании речи и письма, компьютерной лингвистике и биоинформатике, а также в алгоритме свёрточного декодирования Витерби.
 
Алгоритм используется в CDMA и GSM цифровой связи, в модемах и космических коммуникациях. Он нашел применение в распознавании речи и письма, компьютерной лингвистике и биоинформатике, а также в алгоритме свёрточного декодирования Витерби.
  
== Ссылки ==
+
== Источники информации ==
 
* [[wikipedia:Viterbi_algorithm|Wikipedia {{---}} Viterbi algorithm]]
 
* [[wikipedia:Viterbi_algorithm|Wikipedia {{---}} Viterbi algorithm]]
 
* [http://www.cs.sfu.ca/~oschulte/teaching/726/spring11/slides/mychapter13b.pdf Презентация]
 
* [http://www.cs.sfu.ca/~oschulte/teaching/726/spring11/slides/mychapter13b.pdf Презентация]

Версия 18:23, 30 марта 2018

История

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

Описание

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

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


Пусть задано пространство наблюдений [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[1]]
         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 цифровой связи, в модемах и космических коммуникациях. Он нашел применение в распознавании речи и письма, компьютерной лингвистике и биоинформатике, а также в алгоритме свёрточного декодирования Витерби.

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