Алгоритм Баума — Велша

Алгоритм Баума — Велша используется в информатике и статистике для нахождения неизвестных параметров скрытой марковской модели (HMM). Он использует алгоритм прямого-обратного хода и является частным случаем обобщённого EM-алгоритма.

Алгоритм Баума — Велша оценки скрытой модели Маркова править

Скрытая модель Маркова — это вероятностная модель множества случайных переменных  . Переменные   — известные дискретные наблюдения, а   — «скрытые» дискретные величины. В рамках скрытой модели Маркова есть два независимых утверждения, обеспечивающих сходимость данного алгоритма:

  1.  -я скрытая переменная при известной  -ой переменной независима от всех предыдущих   переменных, то есть  ;
  2.  -е известное наблюдение зависит только от  -го состояния, то есть не зависит от времени,  .

Далее будет предложен алгоритм «предположений и максимизаций» для поиска максимальной вероятностной оценки параметров скрытой модели Маркова при заданном наборе наблюдений. Этот алгоритм также известен как алгоритм Баума — Велша.

  — это дискретная случайная переменная, принимающая одно из   значений  . Будем полагать, что данная модель Маркова, определённая как  , однородна по времени, то есть независима от  . Тогда можно задать   как независящую от времени стохастическую матрицу перемещений  . Вероятности состояний в момент времени   определяется начальным распределением  .

Будем считать, что мы в состоянии   в момент времени  , если  . Последовательность состояний выражается как  , где   является состоянием в момент  .

Наблюдение   в момент времени   может иметь одно из   возможных значений,  . Вероятность заданного вектора наблюдений в момент времени   для состояния   определяется как   (  — это матрица   на  ). Последовательность наблюдений   выражается как  .

Следовательно, мы можем описать скрытую модель Маркова с помощью  . При заданном векторе наблюдений   алгоритм Баума — Велша находит  .   максимизирует вероятность наблюдений  .

Алгоритм править

Исходные данные:   со случайными начальными условиями.

Алгоритм итеративно обновляет параметр   до схождения в одной точке.

Прямая процедура править

Обозначим через   вероятность появления заданной последовательности   для состояния   в момент времени  .

  можно вычислить рекурсивно:

  1.  
  2.  

Обратная процедура править

Данная процедура позволяет вычислить   вероятность конечной заданной последовательности   при условии, что мы начали из исходного состояния  , в момент времени  .

Можно вычислить  :

  1.  
  2.  

Используя   и   можно вычислить следующие значения:

  •  
  •  

Имея   и  , можно вычислить новые значения параметров модели:

  •  
  •  
  •  ,

где

 

индикативная функция, и   ожидаемое количество значений наблюдаемой величины, равных   в состоянии   к общему количеству состояний  .

Используя новые значения  ,   и  , итерации продолжаются до схождения.

См. также править

Источники править