Алгоритм Баума

Толкование

Алгоритм Баума: Эта статья или раздел нуждается в переработке.
Пожалуйста, улучшите статью в соответствии с правилами написания статей.

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

Содержание

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

2 Алгоритм

2.1 Прямая процедура

2.2 Обратная процедура

3 Источники

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

Скрытая модель Маркова — это вероятностная модель множества случайных переменных $\{O_1,\;\ldots,\;O_t,\;Q_1,\;\ldots,\;Q_t\}$ . Переменные $O_t$ — известные дискретные наблюдения, а $Q_t$ — «скрытые» дискретные величины. В рамках скрытой модели Маркова есть два независимых утверждения, обеспечивающих сходимость данного алгоритма:

$t$ -я скрытая переменная при известной $(t-1)$ -ой переменной, независима от всех предыдущих $(t-1)$ переменных, то есть $P(Q_t\mid Q_{t-1},\;O_{t-1},\;\ldots,\;Q_1,\;O_1)=P(Q_t\mid Q_{t-1})$ ;

$t$ -е известное наблюдение зависит только от $t$ -го состояния, то есть не зависит от времени, $P(O_t\mid Q_t,\;Q_{t-1},\;O_{t-1},\;\ldots,\;Q_1,\;O_1)=P(O_t\mid Q_t)$ .

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

$Q_t$ — это дискретная случайная переменная, принимающая одно из $N$ значений $(1\ldots N)$ . Будем полагать, что данная модель Маркова, определенная как $P(Q_t\mid Q_{t-1})$ , однородна по времени, то есть независима от $t$ . Тогда можно задать $P(Q_t\mid Q_{t-1})$ как независящую от времени стохастическую матрицу перемещений $A=\{a_{ij}\}=p(Q_t=j\mid Q_{t-1}=i)$ . Особый случай для времени $t=1$ определяется начальным распределением $\pi_i=P(Q_1=i)$ .

Будем считать, что мы в состоянии $j$ в момент времени $t$ , если $Q_t=j$ . Последовательность заданных состояний определяется как $q=(q_1,\;\ldots,\;q_T)$ , где $q_t\in\{1\ldots N\}$ является состоянием в момент $t$ .

Наблюдение может иметь одно из $L$ возможных значений, $O_t\in\{o_1,\;\ldots,\;o_L\}$ . Вероятность заданного вектора наблюдений в момент времени $t$ для состояния $j$ определяется как $b_j(o_t)=P(O_t=o_t\mid Q_t=j)$ ( $B=\{b_{ij}\}$ — это матрица $L$ на $N$ ). Заданная последовательность наблюдений $O$ выражается как $O=(O_1=o_1,\;\ldots,\;O_T=o_T)$ .

Следовательно, мы можем описать скрытую модель Маркова с помощью $\lambda=(A\;,B,\;\pi)$ . При заданном векторе наблюдений $O$ алгоритм Баума — Велша находит $\lambda^*=\max_\lambda P(O\mid\lambda)$ . $\lambda$ максимизирует вероятность наблюдений $O$ .

Алгоритм

Исходные данные: $\lambda=(A,\;B,\;\pi)$ со случайными начальными условиями.

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

Прямая процедура

Определим $\alpha_i(t)=p(O_1=o_1,\;\ldots,\;O_t=o_t,\;Q_t=i\mid\lambda)$ , что является вероятностью получения заданной последовательности $o_1,\;\ldots,\;o_t$ для состояния $i$ в момент времени $t$ .

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

$\alpha_i(1)=\pi_i\cdot b_i(O_1);$

$\alpha_j(t+1)=b_j(O_{t+1})\sum^N_{i=1}{\alpha_i(t)\cdot a_{ij}}.$

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

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

Можно вычислить $\beta_i(t)$ :

$\beta_i(T)=1;$

$\beta_i(t)=\sum^N_{j=1}{\beta_j(t+1)a_{ij}b_j(O_{t+1})}.$

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

$\gamma_i(t)\equiv p(Q_t=i\mid O,\;\lambda)=\frac{\alpha_i(t)\beta_i(t)}{\displaystyle\sum^N_{j=1}\alpha_j(t)\beta_j(t)},$

$\xi_{ij}(t)\equiv p(Q_t=i,\;Q_{t+1}=j\mid O,\;\lambda)=\frac{\alpha_i(t)a_{ij}\beta_j(t+1)b_j(o_{t+1})}{\displaystyle\sum^N_{i=1}\displaystyle\sum^N_{j=1}\alpha_i(t)a_{ij}\beta_j(t+1)b_j(O_{t+1})}.$

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

$\bar\pi_i=\gamma_i(1),$

$\bar{a}_{ij}=\frac{\displaystyle\sum^{T-1}_{t=1}\xi_{ij}(t)}{\displaystyle\sum^{T-1}_{t=1}\xi_{ij}(t)},$

$\bar{b}_i(k)=\frac{\displaystyle\sum^T_{t=1}\delta_{O_t,\;o_k}\gamma_i(t)}{\displaystyle\sum^T_{t=1}\gamma_i(t)}.$

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

Источники

The Baum-Welch algorithm for estimating a Hidden Markov Model

Baum-Welch Algorithm

Лекции С.Николенко по скрытым марковским моделям

Категории:
Марковские процессы
Машинное обучение
Биоинформатика

Игры ⚽ Нужна курсовая?

Полезное

Смотреть что такое "Алгоритм Баума" в других словарях:

Алгоритм Баума — Велша — Алгоритм Баума Велша используется в информатике и статистике для нахождения неизвестных параметров скрытой марковской модели (HMM). Он использует алгоритм «вперёд назад» и является частным случаем обобщённого EM алгоритма. Содержание 1… … Википедия
Алгоритм Баума-Велша — … Википедия
Алгоритм Баума-Велха — … Википедия
Алгоритм вперёд-назад — Алгоритм «прямого обратного» хода алгоритм для вычисления апостериорных вероятностей последовательности состояний при наличии последовательности наблюдений. Иначе говоря, алгоритм, вычисляющий вероятность специфической последовательности… … Википедия
EM-алгоритм — (англ. Expectation maximization (EM) algorithm) алгоритм, используемый в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых… … Википедия
ЕМ-алгоритм — EM алгоритм (англ. expectation maximization) алгоритм, используемый в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных.… … Википедия
ЕМ алгоритм — EM алгоритм (англ. expectation maximization) алгоритм, используемый в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных.… … Википедия
Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия
Программируемые алгоритмы — Служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не устанавл … Википедия
ЕМ — EM алгоритм (англ. expectation maximization) алгоритм, используемый в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, в случае, когда модель зависит от некоторых скрытых переменных.… … Википедия

Словари и энциклопедии на Академике

Алгоритм Баума

Содержание

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

Алгоритм

Прямая процедура

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

Источники

Полезное

Смотреть что такое "Алгоритм Баума" в других словарях:

Поделиться ссылкой на выделенное

Словари и энциклопедии на Академике

Википедия

Алгоритм Баума

Содержание

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

Алгоритм

Прямая процедура

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

Источники

Полезное

Смотреть что такое "Алгоритм Баума" в других словарях:

Поделиться ссылкой на выделенное

Прямая ссылка: