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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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

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

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

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

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

Алгоритм[править | править вики-текст]

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

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

Прямая процедура[править | править вики-текст]

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

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

Обратная процедура[править | править вики-текст]

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

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

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

Имея и , можно определить:

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

Источники[править | править вики-текст]