Изменения

Перейти к: навигация, поиск

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

14 байт добавлено, 14:17, 2 июня 2017
м
Описание алгоритма
Пусть <tex>Q_t</tex> — это дискретная случайная переменная, принимающая одно из <tex>N</tex> значений <tex>(1..N)</tex>. Будем полагать, что данная модель Маркова, определенная как <tex>P(Q_t | Q_{t - 1})</tex> однородна по времени, то есть независима от <tex>t</tex>. Тогда можно задать <tex>P(Q_t | Q_{t - 1}) </tex> как независящую от времени стохастическую матрицу перемещений <tex>A = \{a_{ij}\} = p(Q_t = j | Q_{t - 1} = i)</tex>. Особый случай для времени <tex>t = 1</tex> определяется начальным распределением <tex>\pi_i = P(Q_1 = i)</tex>.
Будем считать, что мы в состоянии <tex>j</tex> в момент времени <tex>t</tex>, если <tex>Q_t = j</tex>. Последовательность заданных состояний определяется как <tex>q = (\{q_1, ..., \dots q_T)\}</tex>, где <tex>q_t \in \{ 1..N\}</tex> является состоянием в момент времени <tex>t</tex>.
Наблюдение может иметь одно из <tex>L</tex> возможных значений, <tex>Q_t \in \{o_1, ..., \dots o_L\}</tex>. Вероятность заданного вектора наблюдений в момент времени <tex>t</tex> для состояния <tex>j</tex> определяется как <tex>b_j(o_t) = P(O_t = o_t | Q_t = j)\ ( B = \{ b_{ij}\}</tex> — это матрица <tex>L</tex> на <tex>N)</tex>. Заданная последовательность наблюдений <tex>O</tex> выражается как <tex> O = (O_1 = o_1, ...\dots , O_T = o_T)</tex>.
Следовательно, мы можем описать скрытую модель Маркова с помощью <tex> \lambda = (A, B, \pi)</tex>. При заданном векторе наблюдений <tex>O</tex> алгоритм Баума-Велша находит <tex> \lambda^*=\max_\lambda P(O\mid\lambda)</tex>. <tex>\lambda</tex> максимизирует вероятность наблюдений <tex>O</tex>.
=== Прямая процедура ===
<tex>a_i(t) = p(O_1 = o_1, ..., \dots O_t = o_t, Q_t = _i | \lambda</tex>, что является вероятностью получения заданной последовательности <tex>\{ o_1, ..., \dots o_t\}</tex> для состояния <tex>i</tex> в момент времени <tex>t</tex>.
<tex>a_i(t)</tex> можно вычислить рекурсивно:
=== Обратная процедура ===
Данная процедура позволяет вычислить вероятность конечной заданной последовательности <tex>\{ o_{t + 1}, ..., \dots o_T\}</tex> при условии, что мы начали из исходного состояния <tex>i</tex>, в момент времени <tex>t</tex>.
<tex>\beta_i(t)</tex> можно вычислить рекурсивно:
96
правок

Навигация