Изменения

'''Алгоритм Витерби ''' (англ. ''Viterbi algorithm'') был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия, которая является популярным статистическим методом для создания статистической модели на основе данных и обеспечения оценки параметров модели (т.е. оценка неизвестного параметра максимизацией функции правдоподобия).{{Определение|id=def1. |definition= Применение =='''Сверточный код''' (англ. ''Convolutional code '') {{---}} это корректирующий ошибки код, в которомАлгоритм используется #На каждом такте работы кодера <tex>\mathtt{k}</tex> символов входной полубесконечной последовательности преобразуются в CDMA и GSM цифровой связи, <tex>\mathtt{n} > \mathtt{k}</tex> символов выходной#Также в модемах и космических коммуникациях. Он нашел применение в распознавании речи и письмапреобразовании участвуют <tex>\mathtt{m}</tex> предыдущих символов#Выполняется свойство линейности (если <tex>\mathtt{x}</tex> соответствует <tex>\mathtt{X}</tex>, компьютерной лингвистике и биоинформатикеа <tex>\mathtt{y}</tex> соответствует <tex>\mathtt{Y}</tex>, а также в алгоритме свёрточного декодирования Витербито <tex>\mathtt{ax} + \mathtt{by}</tex> соответствует <tex>\mathtt{aX} + \mathtt{bY}</tex>).}} 

Алгоритм Витерби позволяет сделать наилучшее наиболее вероятное предположение о последовательности состояний [[Скрытые Марковские модели|скрытой Марковской модели ]] на основе последовательности наблюдений. Эта последовательность состояний называется путем Витерби.

|definition='''Путь Витерби — ''' (англ. ''Viterbi path'') {{---}} наиболее правдоподобная (наиболее вероятная) последовательность скрытых состояний.

Пусть задано пространство наблюдений <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*K</tex>, матрица эмиссии В размера <tex>K*N</tex>, которая определяет вероятность наблюдения <tex>o_j</tex> из состояния <tex>s_i</tex>, массив начальных вероятностей <tex>\pi\,\!</tex> размером <tex>K</tex>, показывающий вероятность того, что начальное состояние <tex>s_i</tex>. Путь <tex>Х =\{x_1,x_2...x_T\}</tex> — последовательность состояний, которые привели к последовательности наблюдений <tex>Y</tex>.'''Входные данные:'''

'''Пример скрытой марковской модели<tex>\mathtt{X} =\{\mathtt{x_1},\mathtt{x_2} \ldots \mathtt{x_T}\}</tex> {{---}} последовательность состояний, которые привели к последовательности наблюдений <tex>\mathtt{Y}</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_1\mathtt{TState}</tex> и <tex>T_2\mathtt{TIndex}</tex> размером <tex>\mathtt{K*} \times \mathtt{T}</tex>. Каждый элемент <tex>T_1\mathtt{TState}[\mathtt{i},\mathtt{j}]</tex> содержит вероятность того, что на <tex>\mathtt{j}</tex>-ом шаге мы находимся в состоянии <tex>\mathtt{s_i}</tex>. Каждый элемент <tex>T_2\mathtt{TIndex}[\mathtt{i},\mathtt{j}]</tex> содержит индекс наиболее вероятного состояния на <tex>\mathtt{j} -1}</tex>-ом шаге.

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

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

'''Шаг 3.''' Рассматривая максимальные значения в столбцах матрицы <tex>T_2\mathtt{TIndex}</tex>, начиная с последнего столбца, выдаем ответ. '''Доказательство корректности:''' Наиболее вероятная последовательность скрытых состояний получается следующими реккурентными соотношениями:*<tex>\mathtt{V_{1,k}} = \mathrm{P}(\mathtt{y_1} \mid \mathtt{k}) \cdot \pi_k</tex>*<tex>\mathtt{V_{t,k}} = \max\limits_{\mathtt{x} \in \mathtt{S}}\left(\mathrm{P}(\mathtt{y_t} \mid \mathtt{k}) \cdot \mathtt{A_{x,k}} \cdot \mathtt{V_{t-1,x}}\right)</tex>Где <tex>\mathtt{V_{t,k}}</tex> это вероятность наиболее вероятной последовательности, которая ответственна за первые <tex>\mathtt{t}</tex> наблюдений, у которых <tex>\mathtt{k}</tex> является завершающим состоянием. Путь Витерби может быть получен сохранением обратных указателей, которые помнят какое состояние было использовано во втором равенстве. Пусть <tex>\mathrm{Ptr}(\mathtt{k},\mathtt{t})</tex> {{---}} функция, которая возвращает значение <tex>\mathtt{x}</tex>, использованное для подсчета <tex>\mathtt{V_{t,k}}</tex> если <tex>\mathtt{t} > 1</tex>, или <tex>\mathtt{k}</tex> если <tex>\mathtt{t}=1</tex>. Тогда:*<tex>\mathtt{x_T} = \mathtt{x} \in \mathtt{S} : \mathtt{V_{T,x}} \leadsto \max</tex>*<tex>\mathtt{x_{t-1}} = \mathrm{Ptr}(\mathtt{x_t},\mathtt{t})</tex>

Функция возвращает вектор <tex>\mathtt{X}</tex> : последовательность номеров наиболее вероятных состояний, которые привели к данным наблюдениям. function viterbi <tex>\mathrm{Viterbi}(\mathtt {O},\mathtt {S}, \pi\mathtt {P} ,\!,mathtt {Y},\mathtt {A},\mathtt {B})</tex> //функция возвращает вектор X - последовательность номеров наиболее вероятных состояний, которые привели к данным наблюдениям. '''for each state ''' <tex>s_i\mathtt{j} = 1</tex> '''to''' <tex>\mathtt {K}</tex> do <tex>T_1\mathtt{TState}[i\mathtt{j},1]= \mathtt{P}[\longleftarrowmathtt{j}] * \pimathtt{B}[i]\mathtt{j},\cdot Bmathtt{Y}[i,y_i1]]</tex> <tex>T_2\mathtt{TIndex}[i\mathtt{j},1]\longleftarrow0= 0</tex> '''for ''' <tex>\mathtt{i} =2 .. </tex> '''to''' <tex>\mathtt {T}</tex> do '''for each state ''' <tex>\mathtt{j} = 1</tex>s_j'''to''' <tex>\mathtt {K}</tex> do <tex>T_1\mathtt{TIndex}[\mathtt{j},\mathtt{i}]= \longleftarrow\max_mathtt{k}\in \mathtt{K} : (T_1\mathtt{TState}[\mathtt{k},\mathtt{i} -1]* \cdot mathtt{A}[\mathtt{k},\mathtt{j}]* \cdot mathtt{B}[\mathtt{j},y_i\mathtt{Y}[\mathtt{i}]])}\leadsto \max</tex> <tex>T_2\mathtt{TState}[\mathtt{j},\mathtt{i}]= \longleftarrowmathtt{TState}[\argmathtt{TIndex}[\max_mathtt{kj}, \mathtt{(T_1[ki}],\mathtt{i} -1]* \cdot mathtt{A}[\mathtt{k},\mathtt{j}]* \cdot mathtt{B}[\mathtt{j},y_i\mathtt{Y}[\mathtt{i}]])}</tex> <tex>x_T\longleftarrowmathtt{X}[\mathtt{T}] = \arg\max_{1 \leqslant \mathtt{k}\leqslant \mathtt{K}} \limits (T_1\mathtt{TState}[\mathtt{k},\mathtt{T}])}</tex> '''for ''' <tex>\mathtt{i} =\mathtt{T...}</tex> '''downto''' <tex>2</tex> do <tex>x_\mathtt{X}[\mathtt{i} -1] = \mathtt{TIndex}[\longleftarrow T_2mathtt{X}[x_i\mathtt{i}],\mathtt{i}]</tex> '''return ''' <tex>\mathtt{X}</tex>Таким образом, алгоритму требуется <tex>\mathrm{O}(\mathtt{T}\times\left|{\mathtt{K}}\right|^2)</tex>времени. == Применение ==Алгоритм используется в <tex>\mathrm{CDMA}</tex> и <tex>\mathrm{GSM}</tex> цифровой связи, в модемах и космических коммуникациях. Он нашел применение в распознавании речи и письма, компьютерной лингвистике и биоинформатике, а также в алгоритме свёрточного декодирования Витерби.

Таким образом, алгоритму требуется <tex> O(T\times\left== Источники информации ==* [[wikipedia:Viterbi_algorithm|Wikipedia {S{---}}\right|^2)<Viterbi algorithm]]* [http://www.cs.sfu.ca/~oschulte/teaching/726/spring11/slides/tex> времениmychapter13b.pdf Презентация]

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