Алгоритм Витерби — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 63 промежуточные версии 8 участников) | |||
Строка 1: | Строка 1: | ||
== История == | == История == | ||
− | Алгоритм Витерби был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия. | + | '''Алгоритм Витерби''' (англ. ''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>). | ||
+ | }} | ||
+ | |||
== Описание == | == Описание == | ||
− | Алгоритм Витерби позволяет сделать | + | Алгоритм Витерби позволяет сделать наиболее вероятное предположение о последовательности состояний [[Скрытые Марковские модели|скрытой Марковской модели]] на основе последовательности наблюдений. |
{{Определение | {{Определение | ||
|id=def1. | |id=def1. | ||
− | |definition=Путь Витерби | + | |definition='''Путь Витерби''' (англ. ''Viterbi path'') {{---}} наиболее правдоподобная (наиболее вероятная) последовательность скрытых состояний. |
}} | }} | ||
+ | '''Предположения, которые делает алгоритм:''' | ||
+ | #Скрытые и наблюдаемые события должны быть последовательностью, которая упорядочена по времени. | ||
+ | #Каждое скрытое событие должно соответствовать только одному наблюдаемому. | ||
+ | #Вычисление наиболее вероятной скрытой последовательности до момента <tex>\mathtt{t}</tex> зависит только от наблюдаемого события в этот момент времени и наиболее вероятной последовательности до момента <tex>\mathtt{t} - 1</tex> (динамическое программирование). | ||
− | + | == Алгоритм == | |
+ | '''Входные данные:''' | ||
− | + | #Пространство наблюдений <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>\mathtt{s_i}</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>-ом шаге. | |
− | Создадим две матрицы <tex> | ||
− | '''Шаг 1.''' Заполним первый столбец матриц <tex> | + | '''Шаг 1.''' Заполним первый столбец матриц <tex>\mathtt{TState}</tex> на основании начального распределения, и <tex>\mathtt{TIndex}</tex> нулями. |
− | '''Шаг 2.''' Последовательно заполняем следующие столбцы матриц <tex> | + | '''Шаг 2.''' Последовательно заполняем следующие столбцы матриц <tex>\mathtt{TState}</tex> и <tex>\mathtt{TIndex}</tex>, используя матрицы вероятностей эмиссий и переходов. |
− | '''Шаг 3.''' Рассматривая максимальные значения в столбцах матрицы <tex> | + | '''Шаг 3.''' Рассматривая максимальные значения в столбцах матрицы <tex>\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> : последовательность номеров наиболее вероятных состояний, которые привели к данным наблюдениям. | |
− | + | <tex>\mathrm{Viterbi}(\mathtt {O}, \mathtt {S}, \mathtt {P} , \mathtt {Y}, \mathtt {A}, \mathtt {B})</tex> | |
− | for <tex> | + | '''for''' <tex>\mathtt{j} = 1</tex> '''to''' <tex>\mathtt {K}</tex> |
− | <tex> | + | <tex>\mathtt{TState}[\mathtt{j}, 1] = \mathtt{P}[\mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[1]]</tex> |
− | <tex> | + | <tex>\mathtt{TIndex}[\mathtt{j}, 1] = 0</tex> |
− | for <tex>i=2 | + | '''for''' <tex>\mathtt{i} = 2</tex> '''to''' <tex>\mathtt {T}</tex> |
− | for <tex>j=1 | + | '''for''' <tex>\mathtt{j} = 1</tex> '''to''' <tex>\mathtt {K}</tex> |
− | <tex> | + | <tex>\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</tex> |
− | <tex> | + | <tex>\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}]]</tex> |
− | + | <tex>\mathtt{X}[\mathtt{T}] = \arg\max_{1 \leqslant \mathtt{k}\leqslant \mathtt{K}} \limits (\mathtt{TState}[\mathtt{k}, \mathtt{T}])</tex> | |
− | <tex>X[T] | + | '''for''' <tex>\mathtt{i} = \mathtt{T}</tex> '''downto''' <tex>2</tex> |
− | for <tex>i=T | + | <tex>\mathtt{X}[\mathtt{i} - 1] = \mathtt{TIndex}[\mathtt{X}[\mathtt{i}], \mathtt{i}]</tex> |
− | <tex>X[i-1]\ | + | '''return''' <tex>\mathtt{X}</tex> |
− | return <tex>X</tex> | + | Таким образом, алгоритму требуется <tex>\mathrm{O}(\mathtt{T}\times\left|{\mathtt{K}}\right|^2)</tex> времени. |
+ | |||
+ | == Применение == | ||
+ | Алгоритм используется в <tex>\mathrm{CDMA}</tex> и <tex>\mathrm{GSM}</tex> цифровой связи, в модемах и космических коммуникациях. Он нашел применение в распознавании речи и письма, компьютерной лингвистике и биоинформатике, а также в алгоритме свёрточного декодирования Витерби. | ||
+ | == См. также == | ||
+ | *[[Скрытые Марковские модели]] | ||
+ | *[[Алгоритм "Вперед-Назад"]] | ||
+ | *[[Алгоритм Баума-Велша]] | ||
− | + | == Источники информации == | |
+ | * [[wikipedia:Viterbi_algorithm|Wikipedia {{---}} Viterbi algorithm]] | ||
+ | * [http://www.cs.sfu.ca/~oschulte/teaching/726/spring11/slides/mychapter13b.pdf Презентация] | ||
− | + | [[Категория: Дискретная математика и алгоритмы]] | |
− | + | [[Категория: Марковские цепи]] | |
− | + | [[Категория: Динамическое программирование]] | |
− | [[Категория: Дискретная математика и алгоритмы]][[Категория: Марковские цепи]] |
Текущая версия на 19:17, 4 сентября 2022
История
Алгоритм Витерби (англ. Viterbi algorithm) был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия, которая является популярным статистическим методом для создания статистической модели на основе данных и обеспечения оценки параметров модели (т.е. оценка неизвестного параметра максимизацией функции правдоподобия).
Определение: |
Сверточный код (англ. Convolutional code ) — это корректирующий ошибки код, в котором
|
Описание
Алгоритм Витерби позволяет сделать наиболее вероятное предположение о последовательности состояний скрытой Марковской модели на основе последовательности наблюдений.
Определение: |
Путь Витерби (англ. Viterbi path) — наиболее правдоподобная (наиболее вероятная) последовательность скрытых состояний. |
Предположения, которые делает алгоритм:
- Скрытые и наблюдаемые события должны быть последовательностью, которая упорядочена по времени.
- Каждое скрытое событие должно соответствовать только одному наблюдаемому.
- Вычисление наиболее вероятной скрытой последовательности до момента зависит только от наблюдаемого события в этот момент времени и наиболее вероятной последовательности до момента (динамическое программирование).
Алгоритм
Входные данные:
- Пространство наблюдений
- Пространство состояний
- Последовательность наблюдений
- Матрица переходов из -того состояния в -ое, размером
- Матрица эмиссии размера , которая определяет вероятность наблюдения из состояния
- Массив начальных вероятностей размером , показывающий вероятность того, что начальное состояние
Выходные данные:
— последовательность состояний, которые привели к последовательности наблюдений .
Алгоритм:
Создадим две матрицы
и размером . Каждый элемент содержит вероятность того, что на -ом шаге мы находимся в состоянии . Каждый элемент содержит индекс наиболее вероятного состояния на -ом шаге.Шаг 1. Заполним первый столбец матриц
на основании начального распределения, и нулями.Шаг 2. Последовательно заполняем следующие столбцы матриц
и , используя матрицы вероятностей эмиссий и переходов.Шаг 3. Рассматривая максимальные значения в столбцах матрицы
, начиная с последнего столбца, выдаем ответ.Доказательство корректности:
Наиболее вероятная последовательность скрытых состояний получается следующими реккурентными соотношениями:
Где
это вероятность наиболее вероятной последовательности, которая ответственна за первые наблюдений, у которых является завершающим состоянием. Путь Витерби может быть получен сохранением обратных указателей, которые помнят какое состояние было использовано во втором равенстве. Пусть — функция, которая возвращает значение , использованное для подсчета если , или если . Тогда:Псевдокод
Функция возвращает вектор
: последовательность номеров наиболее вероятных состояний, которые привели к данным наблюдениям.for to for to for to for downto return
Таким образом, алгоритму требуется
времени.Применение
Алгоритм используется в
и цифровой связи, в модемах и космических коммуникациях. Он нашел применение в распознавании речи и письма, компьютерной лингвистике и биоинформатике, а также в алгоритме свёрточного декодирования Витерби.