Изменения

'''Алгоритм Витерби''' (англ. ''Viterbi algorithm'') был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия, которая является популярным статистическим методом для создания статистической модели на основе данных и обеспечения оценки параметров модели (т.е. оценка неизвестного параметра максимизацией функции правдоподобия).{{Определение|id=def1. |definition='''Сверточный код''' (англ. ''Convolutional code '') {{---}} это корректирующий ошибки код, в котором#На каждом такте работы кодера <tex>\mathtt{k}</tex> символов входной полубесконечной последовательности преобразуются в <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>).}}

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

Пусть задано пространство #Пространство наблюдений <tex>\mathtt{O } =\{\mathtt{o_1},\mathtt{o_2 } \ldots \mathtt{o_N}\}</tex>, пространство #Пространство состояний <tex>\mathtt{S } =\{\mathtt{s_1},\mathtt{s_2 } \ldots \mathtt{s_K}\}</tex>, последовательность #Последовательность наблюдений <tex>\mathtt{Y } =\{\mathtt{y_1},\mathtt{y_2 } \ldots \mathtt{y_T}\}</tex>, матрица #Матрица <tex>\mathtt{A}</tex> переходов из <tex>\mathtt{i}</tex>-того состояния в <tex>\mathtt{j}</tex>-ое, размером <tex>\mathtt{K } \times \mathtt{K}</tex>, матрица #Матрица эмиссии <tex> \mathtt{B }</tex> размера <tex>\mathtt{K } \times \mathtt{N}</tex>, которая определяет вероятность наблюдения <tex>\mathtt{o_j}</tex> из состояния <tex>\mathtt{s_i}</tex>, массив #Массив начальных вероятностей <tex>\mathtt{\pi}</tex> размером <tex>\mathtt{K}</tex>, показывающий вероятность того, что начальное состояние <tex>s_i</tex>. Путь <tex>X =\mathtt{x_1,x_2 \ldots x_T\s_i}</tex> {{---}} последовательность состояний, которые привели к последовательности наблюдений <tex>Y</tex>.

'''Выходные данные''':  <tex>\mathtt{X} == \{\mathtt{x_1},\mathtt{x_2} \ldots \mathtt{x_T}\}</tex> {{---}} последовательность состояний, которые привели к последовательности наблюдений <tex>\mathtt{Y}</tex>. '''Алгоритм ==:''' Создадим две матрицы <tex>\mathtt{TState}</tex> и <tex>\mathtt{TIndex}</tex> размером <tex>\mathtt{K } \times \mathtt{T}</tex>. Каждый элемент <tex>\mathtt{TState}[\mathtt{i},\mathtt{j}]</tex> содержит вероятность того, что на <tex>\mathtt{j}</tex>-ом шаге мы находимся в состоянии <tex>\mathtt{s_i}</tex>. Каждый элемент <tex>\mathtt{TIndex}[\mathtt{i},\mathtt{j}]</tex> содержит индекс наиболее вероятного состояния на <tex>\mathtt{j} -1}</tex>-ом шаге.

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

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

'''Шаг 3Наиболее вероятная последовательность скрытых состояний получается следующими реккурентными соотношениями:*<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>TIndex\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> : последовательность номеров наиболее вероятных состояний, которые привели к данным наблюдениям. '''viterbi'''(<tex>\mathrm{Viterbi}(\mathtt {O}, \mathtt {S}, \mathtt {P} , \mathtt {Y}, \mathtt {A}, \mathtt {B})</tex>) '''for''' <tex>\mathtt{j} = 1</tex> '''to''' <tex>\mathtt {K}</tex> <tex>\mathtt{TState}[i\mathtt{j}, 1]} = \mathtt {P}[i\mathtt{j}] * \mathtt{B}[i\mathtt{j}, \mathtt{Y}[1]]}</tex> <tex>\mathtt{TIndex}[i\mathtt{j}, 1]} = 0</tex> '''for''' <tex>\mathtt{i} = 2</tex> '''to''' <tex>\mathtt {T}</tex> '''for''' <tex>\mathtt{j} = 1</tex> '''to''' <tex>\mathtt {K}</tex> <tex>\mathtt{TStateTIndex}[\mathtt{j}, \mathtt{i}]} = \max_mathtt{1 k} \leqslant kin \leqslant mathtt{K} \limits : (\mathtt{TState}[\mathtt{k}, \mathtt{i } - 1] * \mathtt{A}[\mathtt{k}, \mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[\mathtt{i}]]})\leadsto \max</tex> <tex>\mathtt{TIndexTState}[\mathtt{j}, \mathtt{i}]} = \argmathtt{TState}[\max_mathtt{1 TIndex}[\leqslant kmathtt{j}, \leqslant Kmathtt{i} \limits (], \mathtt{TState[k, i } - 1] * \mathtt{A}[\mathtt{k}, \mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[\mathtt{i}]]})</tex> ''<font color=green>// функция arg max() ищет максимум выражения в скобках и возвращает аргумент // (в нашем случае <tex>\mathtt{kX}</tex>), при котором достигается этот максимум</font>'' <tex>[\mathtt{X[T}]} = \arg\max_{1 \leqslant \mathtt{k}\leqslant \mathtt{K}} \limits (\mathtt{TState}[\mathtt{k}, \mathtt{T}]})</tex>

<tex>\mathtt{X}[\mathtt{i } - 1]} = \mathtt{TIndex}[\mathtt{X}[\mathtt{i}], \mathtt{i}]}</tex>

Таким образом, алгоритму требуется <tex> \mathrm{O}(\mathtt{T}\times\left|{\mathtt{K}}\right|^2)</tex> времени.

Алгоритм используется в <tex>\mathrm{CDMA }</tex> и <tex>\mathrm{GSM }</tex> цифровой связи, в модемах и космических коммуникациях. Он нашел применение в распознавании речи и письма, компьютерной лингвистике и биоинформатике, а также в алгоритме свёрточного декодирования Витерби.