Алгоритм Баума — Велша используется в информатике и статистике для нахождения неизвестных параметров скрытой марковской модели (HMM). Он использует алгоритм прямого-обратного хода и является частным случаем обобщённого EM-алгоритма.
Алгоритм Баума — Велша оценки скрытой модели Маркова Скрытая модель Маркова — это вероятностная модель множества случайных переменных . Переменные — известные дискретные наблюдения, а — «скрытые» дискретные величины. В рамках скрытой модели Маркова есть два независимых утверждения, обеспечивающих сходимость данного алгоритма: -я скрытая переменная при известной -ой переменной независима от всех предыдущих переменных, то есть ; -е известное наблюдение зависит только от -го состояния, то есть не зависит от времени, . Далее будет предложен алгоритм «предположений и максимизаций» для поиска максимальной вероятностной оценки параметров скрытой модели Маркова при заданном наборе наблюдений. Этот алгоритм также известен как алгоритм Баума — Велша.
— это дискретная случайная переменная, принимающая одно из значений . Будем полагать, что данная модель Маркова, определённая как , однородна по времени, то есть независима от . Тогда можно задать как независящую от времени стохастическую матрицу перемещений . Вероятности состояний в момент времени определяется начальным распределением .
Будем считать, что мы в состоянии в момент времени , если . Последовательность состояний выражается как , где является состоянием в момент .
Наблюдение в момент времени может иметь одно из возможных значений, . Вероятность заданного вектора наблюдений в момент времени для состояния определяется как ( — это матрица на ). Последовательность наблюдений выражается как .
Следовательно, мы можем описать скрытую модель Маркова с помощью . При заданном векторе наблюдений алгоритм Баума — Велша находит . максимизирует вероятность наблюдений .
Алгоритм Исходные данные: со случайными начальными условиями.
Алгоритм итеративно обновляет параметр до схождения в одной точке.
Прямая процедура Обозначим через вероятность появления заданной последовательности для состояния в момент времени .
можно вычислить рекурсивно:
Обратная процедура Данная процедура позволяет вычислить вероятность конечной заданной последовательности при условии, что мы начали из исходного состояния , в момент времени .
Можно вычислить :
Используя и можно вычислить следующие значения:
Имея и , можно вычислить новые значения параметров модели:
, где
индикативная функция, и ожидаемое количество значений наблюдаемой величины, равных в состоянии к общему количеству состояний .
Используя новые значения , и , итерации продолжаются до схождения. См. также Алгоритм Витерби
Источники The Baum-Welch algorithm for estimating a Hidden Markov Model Baum-Welch Algorithm Лекции С.Николенко по скрытым марковским моделям
Категория:Марковские процессы Категория:Машинное обучение Категория:Биоинформатика