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

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

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

1. t-я скрытая переменная при известной (t − 1)-ой переменной, независима от всех предыдущих (t − 1) переменных, то есть ;

2. t-е известное наблюдение зависит только от t-го состояния, то есть не зависит от времени, .

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

Qt — это дискретная случайная переменная, принимающая одно из N значений . Будем полагать, что данная модель Маркова, определенная как , однородна по времени, то есть независима от t. Тогда можно задать  как независящую от времени стохастическую матрицу перемещений . Особый случай для времени t = 1 определяется начальным распределением πi = P(Q1 = i).

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

Наблюдение может иметь одно из L возможных значений, . Вероятность заданного вектора наблюдений в момент времени t для состояния j определяется как  (B = {bij} — это матрица L на N). Заданная последовательность наблюдений O выражается как .

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

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

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

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

αi(t) можно вычислить рекурсивно:

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

Можно вычислить βi(t):

1. βi(T) = 1;

2. 

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

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

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