История
Алгоритм Витерби (англ. Viterbi algorithm) был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия, которая является популярным статистическим методом для создания статистической модели на основе данных и обеспечения оценки параметров модели (т.е. оценка неизвестного параметра максимизацией функции правдоподобия).
| Определение: |
Сверточный код (англ. Convolutional code ) — это корректирующий ошибки код, в котором
- На каждом такте работы кодера [math]\mathtt{k}[/math] символов входной полубесконечной последовательности преобразуются в [math]\mathtt{n} \gt \mathtt{k}[/math] символов выходной
- Также в преобразовании участвуют [math]\mathtt{m}[/math] предыдущих символов
- Выполняется свойство линейности (если [math]\mathtt{x}[/math] соответствует [math]\mathtt{X}[/math], а [math]\mathtt{y}[/math] соответствует [math]\mathtt{Y}[/math], то [math]\mathtt{ax} + \mathtt{by}[/math] соответствует [math]\mathtt{aX} + \mathtt{bY}[/math]).
|
Описание
Алгоритм Витерби позволяет сделать наиболее вероятное предположение о последовательности состояний скрытой Марковской модели на основе последовательности наблюдений.
| Определение: |
| Путь Витерби (англ. Viterbi path) — наиболее правдоподобная (наиболее вероятная) последовательность скрытых состояний. |
Предположения, которые делает алгоритм:
- Скрытые и наблюдаемые события должны быть последовательностью, которая упорядочена по времени.
- Каждое скрытое событие должно соответствовать только одному наблюдаемому.
- Вычисление наиболее вероятной скрытой последовательности до момента [math]\mathtt{t}[/math] зависит только от наблюдаемого события в этот момент времени и наиболее вероятной последовательности до момента [math]\mathtt{t} - 1[/math] (динамическое программирование).
Алгоритм
Входные данные:
- Пространство наблюдений [math]\mathtt{O} =\{\mathtt{o_1},\mathtt{o_2} \ldots \mathtt{o_N}\}[/math]
- Пространство состояний [math]\mathtt{S} =\{\mathtt{s_1},\mathtt{s_2} \ldots \mathtt{s_K}\}[/math]
- Последовательность наблюдений [math]\mathtt{Y} =\{\mathtt{y_1},\mathtt{y_2} \ldots \mathtt{y_T}\}[/math]
- Матрица [math]\mathtt{A}[/math] переходов из [math]\mathtt{i}[/math]-того состояния в [math]\mathtt{j}[/math]-ое, размером [math]\mathtt{K} \times \mathtt{K}[/math]
- Матрица эмиссии [math]\mathtt{B}[/math] размера [math]\mathtt{K} \times \mathtt{N}[/math], которая определяет вероятность наблюдения [math]\mathtt{o_j}[/math] из состояния [math]\mathtt{s_i}[/math]
- Массив начальных вероятностей [math]\mathtt{\pi}[/math] размером [math]\mathtt{K}[/math], показывающий вероятность того, что начальное состояние [math]\mathtt{s_i}[/math]
Выходные данные:
[math]\mathtt{X} =\{\mathtt{x_1},\mathtt{x_2} \ldots \mathtt{x_T}\}[/math] — последовательность состояний, которые привели к последовательности наблюдений [math]\mathtt{Y}[/math].
Алгоритм:
Создадим две матрицы [math]\mathtt{TState}[/math] и [math]\mathtt{TIndex}[/math] размером [math]\mathtt{K} \times \mathtt{T}[/math]. Каждый элемент [math]\mathtt{TState}[\mathtt{i},\mathtt{j}][/math] содержит вероятность того, что на [math]\mathtt{j}[/math]-ом шаге мы находимся в состоянии [math]\mathtt{s_i}[/math]. Каждый элемент [math]\mathtt{TIndex}[\mathtt{i},\mathtt{j}][/math] содержит индекс наиболее вероятного состояния на [math]\mathtt{j} - 1[/math]-ом шаге.
Шаг 1. Заполним первый столбец матриц [math]\mathtt{TState}[/math] на основании начального распределения, и [math]\mathtt{TIndex}[/math] нулями.
Шаг 2. Последовательно заполняем следующие столбцы матриц [math]\mathtt{TState}[/math] и [math]\mathtt{TIndex}[/math], используя матрицы вероятностей эмиссий и переходов.
Шаг 3. Рассматривая максимальные значения в столбцах матрицы [math]\mathtt{TIndex}[/math], начиная с последнего столбца, выдаем ответ.
Доказательство корректности:
Наиболее вероятная последовательность скрытых состояний получается следующими реккурентными соотношениями:
- [math]\mathtt{V_{1,k}} = \mathrm{P}(\mathtt{y_1} \mid \mathtt{k}) \cdot \pi_k[/math]
- [math]\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)[/math]
Где [math]\mathtt{V_{t,k}}[/math] это вероятность наиболее вероятной последовательности, которая ответственна за первые [math]\mathtt{t}[/math] наблюдений, у которых [math]\mathtt{k}[/math] является завершающим состоянием. Путь Витерби может быть получен сохранением обратных указателей, которые помнят какое состояние было использовано во втором равенстве. Пусть [math]\mathrm{Ptr}(\mathtt{k},\mathtt{t})[/math] — функция, которая возвращает значение [math]\mathtt{x}[/math], использованное для подсчета [math]\mathtt{V_{t,k}}[/math] если [math]\mathtt{t} \gt 1[/math], или [math]\mathtt{k}[/math] если [math]\mathtt{t}=1[/math]. Тогда:
- [math]\mathtt{x_T} = \mathtt{x} \in \mathtt{S} : \mathtt{V_{T,x}} \leadsto \max[/math]
- [math]\mathtt{x_{t-1}} = \mathrm{Ptr}(\mathtt{x_t},\mathtt{t})[/math]
Псевдокод
Функция возвращает вектор [math]\mathtt{X}[/math] : последовательность номеров наиболее вероятных состояний, которые привели к данным наблюдениям.
[math]\mathrm{Viterbi}(\mathtt {O}, \mathtt {S}, \mathtt {P} , \mathtt {Y}, \mathtt {A}, \mathtt {B})[/math]
for [math]\mathtt{i} = 1[/math] to [math]\mathtt {K}[/math]
[math]\mathtt{TState}[\mathtt{i}, 1] = \mathtt{P}[\mathtt{i}] * \mathtt{B}[\mathtt{i}, \mathtt{Y}[1]][/math]
[math]\mathtt{TIndex}[\mathtt{i}, 1] = 0[/math]
for [math]\mathtt{i} = 2[/math] to [math]\mathtt {T}[/math]
for [math]\mathtt{j} = 1[/math] to [math]\mathtt {K}[/math]
[math]\mathtt{TIndex}[\mathtt{j}, \mathtt{i}] = \mathtt{k} \in \mathtt{K} : (\mathtt{TState}[\mathtt{k}, \mathtt{i} - 1] * \mathtt{A}[\mathtt{k}, \mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[\mathtt{i}]]) \leadsto \max[/math]
[math]\mathtt{TState}[\mathtt{j}, \mathtt{i}] = \mathtt{TState}[\mathtt{TIndex}[\mathtt{j}, \mathtt{i}], \mathtt{i} - 1] * \mathtt{A}[\mathtt{k}, \mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[\mathtt{i}]][/math]
[math]\mathtt{X}[\mathtt{T}] = \arg\max_{1 \leqslant \mathtt{k}\leqslant \mathtt{K}} \limits (\mathtt{TState}[\mathtt{k}, \mathtt{T}])[/math]
for [math]\mathtt{i} = \mathtt{T}[/math] downto [math]2[/math]
[math]\mathtt{X}[\mathtt{i} - 1] = \mathtt{TIndex}[\mathtt{X}[\mathtt{i}], \mathtt{i}][/math]
return [math]\mathtt{X}[/math]
Таким образом, алгоритму требуется [math]\mathrm{O}(\mathtt{T}\times\left|{\mathtt{K}}\right|^2)[/math] времени.
Применение
Алгоритм используется в [math]\mathrm{CDMA}[/math] и [math]\mathrm{GSM}[/math] цифровой связи, в модемах и космических коммуникациях. Он нашел применение в распознавании речи и письма, компьютерной лингвистике и биоинформатике, а также в алгоритме свёрточного декодирования Витерби.
См. также
Источники информации
