Изменения

'''Алгоритм Витерби ''' (англ. ''Viterbi algorithm'') был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи.В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия, которая является популярным статистическим методом для создания статистической модели на основе данных и обеспечения оценки параметров модели (т.е. оценка неизвестного параметра максимизацией функции правдоподобия).{{Определение|id=def1. |definition= Применение =='''Сверточный код''' (англ. ''Convolutional code '') {{---}} это корректирующий ошибки код, в котором#На каждом такте работы кодера <tex>\mathtt{k}</tex> символов входной полубесконечной последовательности преобразуются в <tex>\mathtt{n} > \mathtt{k}</tex> символов выходнойАлгоритм используется #Также в CDMA и GSM цифровой связипреобразовании участвуют <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},π \mathtt {P} ,\mathtt {Y},\mathtt {A},\mathtt {B}) : X </tex> '''for each state ''' <tex>\mathtt{j} = 1</tex> '''to''' <tex>s_i\mathtt {K}</tex> do <tex>T_1\mathtt{TState}[i\mathtt{j},1]= \longleftarrowmathtt{P}[\mathtt{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 Презентация][[Категория: Дискретная математика и алгоритмы]][[Категория: Марковские цепи]][[Категория: Динамическое программирование]]