Изменения
Новая страница: «== История == Алгоритм Витерби был представлен в 1967 году для декодирования сверточных код...»
== История ==
Алгоритм Витерби был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи.
== Применение ==
Алгоритм используется в CDMA и GSM цифровой связи, в модемах и космических коммуникациях. Он нашел применение в распознавании речи и письма, компьютерной лингвистике и биоинформатике.
== Описание ==
Алгоритм Витерби позволяет сделать наилучшее предположение о последовательности состояний скрытой модели на основе последовательности наблюдений. Эта последовательность состояний называется путем Витерби.
{{Определение
|id=def1.
|definition=Путь Витерби — наиболее правдоподобная последовательность скрытых состояний.
}}
Пусть задано пространство наблюдений <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>i</tex>-того состояния в <tex>j</tex>-ое, размером <tex>К*К</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>.
'''Скрытая марковская модель.'''<br>
Модель представляет из себя марковскую цепь, для которой нам известны начальная вероятность и матрица вероятностей переходов. Скрытой она называется потому, что мы не имеем информации о ее текущем состоянии. Мы получаем информацию на основе некоторого наблюдения, в рассмотренном ниже алгоритме мы будем использовать просто натуральное число от 1 до <tex>N</tex>, как индекс наблюдаемого события. Для каждого состояния скрытой марковской модели задан вектор вероятности эмиссии, который характеризует вероятность наблюдени каждого события, когда модель находится в этом состоянии. Совокупность таких векторов образует матрицу эмиссии.
'''Пример скрытой марковской модели.'''<br>
Рассмотрим пример скрытой марковской модели. У Деда Мороза есть три мешка с подарками в разноцветной упаковке: красной, синей, зеленой и фиолетовой. Ночью Дед Мороз пробирается в квартиру и тайком выкладывает подарки под елкой в ряд, доставая по одному подарку из мешка. Наутро мы обнаруживаем упорядоченную последовательность из пяти подарков и хотим сделать наилучшее предположение о последовательности мешков, из которых он доставал эти подарки.
Дед Мороз с мешками — скрытая марковская модель. При этом 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</tex> и <tex>T_2</tex> размером <tex>K*T</tex>. Каждый элемент <tex>T_1[i,j]</tex> содержит вероятность того, что на <tex>j</tex>-ом шаге мы находимся в состоянии <tex>s_i</tex>. Каждый элемент <tex>T_2[i,j]</tex> содержит индекс наиболее вероятного состояния на <tex>{j-1}</tex>-ом шаге.
'''Шаг 1.''' Заполним первый столбец матриц <tex>T_1</tex> на основании начального распределения, и <tex>T_2</tex> нулями.<br>
'''Шаг 2.''' Последовательно заполняем следующие столбцы матриц <tex>T_1</tex> и <tex>T_2</tex>, используя матрицы вероятностей эмиссий и переходов.<br>
'''Шаг 3.''' Рассматривая максимальные значения в столбцах матрицы <tex>T_2</tex>, начиная с последнего столбца, выдаем ответ.<br>
== Псевдокод ==
function viterbi <tex>(O,S,π,Y,A,B) : X </tex>
for each state <tex>s_i</tex> do
<tex>T_1[i,1]\longleftarrow\pi[i]\,\cdot B[i,y_i]</tex>
<tex>T_2[i,1]\longleftarrow0</tex>
for <tex>i=2 .. T</tex> do
for each state <tex>s_j</tex> do
<tex>T_1[j,i]\longleftarrow\max_{k}{(T_1[k,i-1]\cdot A[k,j]\cdot B[j,y_i])}</tex>
<tex>T_2[j,i]\longleftarrow\arg\max_{k}{(T_1[k,i-1]\cdot A[k,j]\cdot B[j,y_i])}</tex>
<tex>x_T\longleftarrow\arg\max_{k}{(T_1[k,T])}</tex>
for <tex>i=T...2</tex> do
<tex>x_{i-1}\longleftarrow T_2[x_i,i]</tex>
return <tex>X</tex>
Таким образом, алгоритму требуется <tex> O(T\times\left|{S}\right|^2)</tex> времени.
== Ссылки ==
*[http://en.wikipedia.org/wiki/Viterbi_algorithm Статья из английской Википедии]
*[http://www.cs.sfu.ca/~oschulte/teaching/726/spring11/slides/mychapter13b.pdf Презентация]
Алгоритм Витерби был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи.
== Применение ==
Алгоритм используется в CDMA и GSM цифровой связи, в модемах и космических коммуникациях. Он нашел применение в распознавании речи и письма, компьютерной лингвистике и биоинформатике.
== Описание ==
Алгоритм Витерби позволяет сделать наилучшее предположение о последовательности состояний скрытой модели на основе последовательности наблюдений. Эта последовательность состояний называется путем Витерби.
{{Определение
|id=def1.
|definition=Путь Витерби — наиболее правдоподобная последовательность скрытых состояний.
}}
Пусть задано пространство наблюдений <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>i</tex>-того состояния в <tex>j</tex>-ое, размером <tex>К*К</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>.
'''Скрытая марковская модель.'''<br>
Модель представляет из себя марковскую цепь, для которой нам известны начальная вероятность и матрица вероятностей переходов. Скрытой она называется потому, что мы не имеем информации о ее текущем состоянии. Мы получаем информацию на основе некоторого наблюдения, в рассмотренном ниже алгоритме мы будем использовать просто натуральное число от 1 до <tex>N</tex>, как индекс наблюдаемого события. Для каждого состояния скрытой марковской модели задан вектор вероятности эмиссии, который характеризует вероятность наблюдени каждого события, когда модель находится в этом состоянии. Совокупность таких векторов образует матрицу эмиссии.
'''Пример скрытой марковской модели.'''<br>
Рассмотрим пример скрытой марковской модели. У Деда Мороза есть три мешка с подарками в разноцветной упаковке: красной, синей, зеленой и фиолетовой. Ночью Дед Мороз пробирается в квартиру и тайком выкладывает подарки под елкой в ряд, доставая по одному подарку из мешка. Наутро мы обнаруживаем упорядоченную последовательность из пяти подарков и хотим сделать наилучшее предположение о последовательности мешков, из которых он доставал эти подарки.
Дед Мороз с мешками — скрытая марковская модель. При этом 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</tex> и <tex>T_2</tex> размером <tex>K*T</tex>. Каждый элемент <tex>T_1[i,j]</tex> содержит вероятность того, что на <tex>j</tex>-ом шаге мы находимся в состоянии <tex>s_i</tex>. Каждый элемент <tex>T_2[i,j]</tex> содержит индекс наиболее вероятного состояния на <tex>{j-1}</tex>-ом шаге.
'''Шаг 1.''' Заполним первый столбец матриц <tex>T_1</tex> на основании начального распределения, и <tex>T_2</tex> нулями.<br>
'''Шаг 2.''' Последовательно заполняем следующие столбцы матриц <tex>T_1</tex> и <tex>T_2</tex>, используя матрицы вероятностей эмиссий и переходов.<br>
'''Шаг 3.''' Рассматривая максимальные значения в столбцах матрицы <tex>T_2</tex>, начиная с последнего столбца, выдаем ответ.<br>
== Псевдокод ==
function viterbi <tex>(O,S,π,Y,A,B) : X </tex>
for each state <tex>s_i</tex> do
<tex>T_1[i,1]\longleftarrow\pi[i]\,\cdot B[i,y_i]</tex>
<tex>T_2[i,1]\longleftarrow0</tex>
for <tex>i=2 .. T</tex> do
for each state <tex>s_j</tex> do
<tex>T_1[j,i]\longleftarrow\max_{k}{(T_1[k,i-1]\cdot A[k,j]\cdot B[j,y_i])}</tex>
<tex>T_2[j,i]\longleftarrow\arg\max_{k}{(T_1[k,i-1]\cdot A[k,j]\cdot B[j,y_i])}</tex>
<tex>x_T\longleftarrow\arg\max_{k}{(T_1[k,T])}</tex>
for <tex>i=T...2</tex> do
<tex>x_{i-1}\longleftarrow T_2[x_i,i]</tex>
return <tex>X</tex>
Таким образом, алгоритму требуется <tex> O(T\times\left|{S}\right|^2)</tex> времени.
== Ссылки ==
*[http://en.wikipedia.org/wiki/Viterbi_algorithm Статья из английской Википедии]
*[http://www.cs.sfu.ca/~oschulte/teaching/726/spring11/slides/mychapter13b.pdf Презентация]
