Изменения

|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>.

Дед Мороз с мешками — {{---}} скрытая марковская модель. При этом 4 цвета {{-- -}} пространство из <tex>N</tex> наблюдений, 3 мешка — {{---}} количество состояний <tex>K</tex>, 5 подарков — {{---}} наши <tex>T</tex> наблюдений, каждое из которых представлено цифрой — {{---}} номером цвета — {{---}} от 1 до 5. Мы знаем, каковы вероятности того, что Дед Мороз начнет доставать подарки из мешка с номером <tex>i</tex> – {{---}} вектор <tex>\pi[i]\,\!</tex>. Мы также знаем матрицу переходов <tex>A</tex>, какова вероятность того, что от мешка с номером <tex>i</tex> Дед Мороз переходит к мешку с номером <tex>j</tex>. Мешки Деда Мороза бесконечны, но мы точно знаем, каково соотношение цветов подарков в кажом мешке ему загрузили на заводе в Великом Устюге. Это матрица вероятностей эмиссии <tex>B</tex>.

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

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

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

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

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

Таким образом== Применение ==Алгоритм используется в CDMA и GSM цифровой связи, алгоритму требуется <tex> O(T\times\left|{S}\right|^2)</tex> временив модемах и космических коммуникациях. Он нашел применение в распознавании речи и письма, компьютерной лингвистике и биоинформатике, а также в алгоритме свёрточного декодирования Витерби.

*[http[wikipedia://en.wikipedia.org/wiki/Viterbi_algorithm |Wikipedia{{---}} Viterbi algorithm]]*[http://www.cs.sfu.ca/~oschulte/teaching/726/spring11/slides/mychapter13b.pdf Презентация] [[Категория: Дискретная математика и алгоритмы]][[Категория: Марковские цепи]][[Категория: Динамическое программирование]]