Изменения
Нет описания правки
Рассмотрим пример скрытой марковской модели. У Деда Мороза есть три мешка с подарками в разноцветной упаковке: красной, синей, зеленой и фиолетовой. Ночью Дед Мороз пробирается в квартиру и тайком выкладывает подарки под елкой в ряд, доставая по одному подарку из мешка. Наутро мы обнаруживаем упорядоченную последовательность из пяти подарков и хотим сделать наилучшее предположение о последовательности мешков, из которых он доставал эти подарки.
Дед Мороз с мешками — скрытая марковская модель. При этом 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>X</tex> - последовательность номеров наиболее вероятных состояний, которые привели к данным наблюдениям.
function viterbi <tex>(O,S,\pi\,\!,Y,A,B)</tex>
for each state <tex>s_ii=1..K</tex> do
<tex>T_1[i,1]\longleftarrow\pi[i]\,\cdot B[i,y_i]</tex>
<tex>T_2[i,1]\longleftarrow0</tex>
for <tex>i=2 .. T</tex> do for each state <tex>s_jj=1..K</tex> do
<tex>T_1[j,i]\longleftarrow\max_{k}{(T_1[k,i-1]\cdot A[k,j]\cdot B[j,y_i])}</tex>
<tex>T_2[j,i]\longleftarrow\arg\max_{k}{(T_1[k,i-1]\cdot A[k,j]\cdot B[j,y_i])}</tex>
<tex>x_T\longleftarrow\arg\max_{k}{(T_1[k,T])}</tex>
for <tex>i=T...2</tex> do
<tex>x_{i-1}\longleftarrow T_2[x_i,i]</tex>
return <tex>X</tex>
