Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Шаблон:Чистить

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

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

  1. ~t-ая скрытая переменная при известной (t-1)-ой переменной, независима от всех предыдущих ~(t-1) переменных, то есть ~P(O_t|Q_{t-1},O_{t-1},...,Q_1,O_1) = P(Q_t|Q_{t-1});
  2. ~t-ое известное наблюдение зависит только о ~i-го состояния, то есть не зависит от времени, ~P(O_t|Q_t,O_1,...,Q_1,O_1) = P(Q_t|Q_t).

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

~Q_t — это дискретная случайная переменная, принимающая одно из ~N значений ~(1..N). Будем полагать, что данная модель Маркова, определенная как ~P(Q_t|Q_{t-1}), однородна по времени, то есть независима от ~t. Тогда можно задать ~P(Q_t|Q_{t-1}) как независящую от времени стохастическую матрицу перемещений ~A = \{a_{ij}\} = p(Q_t=j|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_i(o_i)=p_j(O_t=o_t|Q_t=j). (~B=\{b_{ij}\} — это матрица L на N). Заданная последовательность наблюдений O выражается как ~O=(O_1=o1,...,O_T=o_T).

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

Алгоритм Править

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

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

Прямая процедура Править

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

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

  1. \alpha_i(t)=\pi_i \cdot b_i(O_i),
  2. \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):

  1. ~\beta_i(T)=1;
  2. ~\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|O,\lambda)=\frac{\alpha_i(t)\beta_i(t)}{\sum^{N}_{j=1}\alpha_j(t)\beta_j(t)},
  • ~\xi_{ij}(t)\equiv p(Q_t=i,Q_(t+1)=j|O,\lambda)=\frac{\alpha_i(t)a_{ij}\beta_j(t+1)b_j(o_{t+1})}{\sum^{N}_{i=1}{\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{\sum^{T-1}_{t=1}{\xi_{ij}(t)}}{\sum^{T-1}_{t=1} {\gamma_i(t)}},
  • ~\bar{b}_i(k)=\frac{\sum^{T}_{t=1}{\delta_{O_t,o_k}\gamma_i(t)}}{\sum^{T}_{t=1}{\gamma_i(t)}}.

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

Источники Править

  1. The Baum–Welch algorithm for estimating a Hidden Markov Model
  2. Baum-Welch Algorithm

Викия-сеть

Случайная вики