Алгоритм Витерби — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(История)
(Алгоритм)
Строка 23: Строка 23:
 
'''Входные данные:'''
 
'''Входные данные:'''
  
#Пространство наблюдений <tex>\mathtt{O =\{o_1,o_2 \ldots o_N\}}</tex>
+
#Пространство наблюдений <tex>\mathtt{O} =\{\mathtt{o_1},\mathtt{o_2} \ldots \mathtt{o_N}\}</tex>
#Пространство состояний <tex>\mathtt{S =\{s_1,s_2 \ldots s_K\}}</tex>
+
#Пространство состояний <tex>\mathtt{S} =\{\mathtt{s_1},\mathtt{s_2} \ldots \mathtt{s_K}}\}</tex>
#Последовательность наблюдений <tex>\mathtt{Y =\{y_1,y_2 \ldots y_T\}}</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 K}</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 N}</tex>, которая определяет вероятность наблюдения <tex>\mathtt{o_j}</tex> из состояния <tex>\mathtt{s_i}</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{\pi}</tex> размером <tex>\mathtt{K}</tex>, показывающий вероятность того, что начальное состояние <tex>\mathtt{s_i}</tex>
  
 
'''Выходные данные''':  
 
'''Выходные данные''':  
  
<tex>\mathtt{X =\{x_1,x_2 \ldots x_T\}}</tex> {{---}} последовательность состояний, которые привели к последовательности наблюдений <tex>\mathtt{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 T}</tex>. Каждый элемент <tex>\mathtt{TState}[\mathtt{i,j}]</tex> содержит вероятность того, что на <tex>\mathtt{j}</tex>-ом шаге мы находимся в состоянии <tex>\mathtt{s_i}</tex>. Каждый элемент <tex>\mathtt{TIndex}[\mathtt{i,j}]</tex> содержит индекс наиболее вероятного состояния на <tex>{\mathtt{j-1}}</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> нулями.
 
'''Шаг 1.''' Заполним первый столбец матриц <tex>\mathtt{TState}</tex> на основании начального распределения, и <tex>\mathtt{TIndex}</tex> нулями.

Версия 23:32, 17 мая 2018

История

Алгоритм Витерби (англ. Viterbi algorithm) был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия, которая является популярным статистическим методом для создания статистической модели на основе данных и обеспечения оценки параметров модели (т.е. оценка неизвестного параметра максимизацией функции правдоподобия).

Определение:
Сверточный код (англ. Convolutional code ) — это корректирующий ошибки код, в котором
  1. На каждом такте работы кодера [math]\mathtt{k}[/math] символов входной полубесконечной последовательности преобразуются в [math]\mathtt{n} \gt \mathtt{k}[/math] символов выходной
  2. Также в преобразовании участвуют [math]\mathtt{m}[/math] предыдущих символов
  3. Выполняется свойство линейности (если [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) — наиболее правдоподобная (наиболее вероятная) последовательность скрытых состояний.

Предположения, которые делает алгоритм:

  1. Скрытые и наблюдаемые события должны быть последовательностью, которая упорядочена по времени.
  2. Каждое скрытое событие должно соответствовать только одному наблюдаемому.
  3. Вычисление наиболее вероятной скрытой последовательности до момента [math]\mathtt{t}[/math] зависит только от наблюдаемого события в этот момент времени и наиболее вероятной последовательности до момента [math]\mathtt{t - 1}[/math] (динамическое программирование).

Алгоритм

Входные данные:

  1. Пространство наблюдений [math]\mathtt{O} =\{\mathtt{o_1},\mathtt{o_2} \ldots \mathtt{o_N}\}[/math]
  2. Пространство состояний [math]\mathtt{S} =\{\mathtt{s_1},\mathtt{s_2} \ldots \mathtt{s_K}}\}[/math]
  3. Последовательность наблюдений [math]\mathtt{Y} =\{\mathtt{y_1},\mathtt{y_2} \ldots \mathtt{y_T}}\}[/math]
  4. Матрица [math]\mathtt{A}[/math] переходов из [math]\mathtt{i}[/math]-того состояния в [math]\mathtt{j}[/math]-ое, размером [math]\mathtt{K} \times \mathtt{K}[/math]
  5. Матрица эмиссии [math]\mathtt{B}[/math] размера [math]\mathtt{K} \times \mathtt{N}[/math], которая определяет вероятность наблюдения [math]\mathtt{o_j}[/math] из состояния [math]\mathtt{s_i}[/math]
  6. Массив начальных вероятностей [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 k}) \cdot \pi_k}[/math]
  • [math]\mathtt{V_{t,k} = \max\limits_{x \in S}\left(\mathrm{P}(\mathtt{y_t \mid k}) \cdot A_{x,k} \cdot 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,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 = \arg\max\limits_{x \in S}(V_{T,x})}[/math]
  • [math]\mathtt{x_{t-1} = \mathrm{Ptr}(x_t,t)}[/math]

Псевдокод

Функция возвращает вектор [math]\mathtt{X}[/math] : последовательность номеров наиболее вероятных состояний, которые привели к данным наблюдениям.

   Viterbi([math]\mathtt {O}, \mathtt {S},  \mathtt {P} , \mathtt {Y}, \mathtt {A}, \mathtt {B}[/math])
       for [math]\mathtt{j} = 1[/math] to [math]\mathtt K[/math]
           [math]\mathtt{TState}[\mathtt{i, 1}] = \mathtt{P}[\mathtt{i}] * \mathtt{B}[\mathtt{i,} \mathtt{Y}[\mathtt{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{TState[j, i]} = \max_{1 \leqslant \mathtt{k}\leqslant \mathtt{K}} \limits (\mathtt{TState[k, i - 1] * A[k, j] * B[j, Y[i]]})[/math] 
               [math]\mathtt{TIndex[j, i]} = \arg\max_{1 \leqslant \mathtt{k}\leqslant \mathtt{K}} \limits (\mathtt{TState[k, i - 1] * A[k, j] * B[j, Y[i]]})[/math] 
               // функция arg max() ищет максимум выражения в скобках и возвращает аргумент(в нашем случае [math]\mathtt{k}[/math]), при котором достигается этот максимум
       [math]\mathtt{X}[\mathtt{T}] = \arg\max_{1 \leqslant \mathtt{k}\leqslant \mathtt{K}} \limits (\mathtt{TState}[\mathtt{k, 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]O(\mathtt{T\times\left|{K}\right|^2})[/math] времени.

Применение

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

См. также

Источники информации