Алгоритм Баума — Велша
 | Эта статья или раздел нуждается в переработке. |
Алгоритм Баума — Велша используется в информатике и статистике для нахождения неизвестных параметров скрытой марковской модели (HMM). Он использует алгоритм прямого-обратного хода и является частным случаем обобщённого EM-алгоритма.
Алгоритм Баума — Велша оценки скрытой модели Маркова
Скрытая модель Маркова — это вероятностная модель множества случайных переменных [math]\displaystyle{ \{Y_1,\;\ldots,\;Y_t,\;Q_1,\;\ldots,\;Q_t\} }[/math]. Переменные [math]\displaystyle{ Y_t }[/math] — известные дискретные наблюдения, а [math]\displaystyle{ Q_t }[/math] — «скрытые» дискретные величины. В рамках скрытой модели Маркова есть два независимых утверждения, обеспечивающих сходимость данного алгоритма:
- [math]\displaystyle{ t }[/math]-я скрытая переменная при известной [math]\displaystyle{ (t-1) }[/math]-ой переменной независима от всех предыдущих [math]\displaystyle{ (t-1) }[/math] переменных, то есть [math]\displaystyle{ P(Q_t\mid Q_{t-1},\;Y_{t-1},\;\ldots,\;Q_1,\;Y_1)=P(Q_t\mid Q_{t-1}) }[/math];
- [math]\displaystyle{ t }[/math]-е известное наблюдение зависит только от [math]\displaystyle{ t }[/math]-го состояния, то есть не зависит от времени, [math]\displaystyle{ P(Y_t\mid Q_t,\;Q_{t-1},\;Y_{t-1},\;\ldots,\;Q_1,\;Y_1)=P(Y_t\mid Q_t) }[/math].
Далее будет предложен алгоритм «предположений и максимизаций» для поиска максимальной вероятностной оценки параметров скрытой модели Маркова при заданном наборе наблюдений. Этот алгоритм также известен как алгоритм Баума — Велша.
[math]\displaystyle{ Q_t }[/math] — это дискретная случайная переменная, принимающая одно из [math]\displaystyle{ N }[/math] значений [math]\displaystyle{ (1\ldots N) }[/math]. Будем полагать, что данная модель Маркова, определённая как [math]\displaystyle{ P(Q_t\mid Q_{t-1}) }[/math], однородна по времени, то есть независима от [math]\displaystyle{ t }[/math]. Тогда можно задать [math]\displaystyle{ P(Q_t\mid Q_{t-1}) }[/math] как независящую от времени стохастическую матрицу перемещений [math]\displaystyle{ A=\{a_{ij}\}=p(Q_t=j\mid Q_{t-1}=i) }[/math]. Вероятности состояний в момент времени [math]\displaystyle{ t=1 }[/math] определяется начальным распределением [math]\displaystyle{ \pi_i=P(Q_1=i) }[/math].
Будем считать, что мы в состоянии [math]\displaystyle{ j }[/math] в момент времени [math]\displaystyle{ t }[/math], если [math]\displaystyle{ Q_t=j }[/math]. Последовательность состояний выражается как [math]\displaystyle{ q=(q_1,\;\ldots,\;q_T) }[/math], где [math]\displaystyle{ q_t\in\{1\ldots N\} }[/math] является состоянием в момент [math]\displaystyle{ t }[/math].
Наблюдение [math]\displaystyle{ Y_t }[/math] в момент времени [math]\displaystyle{ t }[/math] может иметь одно из [math]\displaystyle{ L }[/math] возможных значений, [math]\displaystyle{ y_t\in\{o_1,\;\ldots,\;o_L\} }[/math]. Вероятность заданного вектора наблюдений в момент времени [math]\displaystyle{ t }[/math] для состояния [math]\displaystyle{ j }[/math] определяется как [math]\displaystyle{ b_j(o_i)=P(Y_t=o_i\mid Q_t=j) }[/math] ([math]\displaystyle{ B=\{b_{ij}\} }[/math] — это матрица [math]\displaystyle{ L }[/math] на [math]\displaystyle{ N }[/math]). Последовательность наблюдений [math]\displaystyle{ y }[/math] выражается как [math]\displaystyle{ y=(y_1,\;\ldots,\;y_T) }[/math].
Следовательно, мы можем описать скрытую модель Маркова с помощью [math]\displaystyle{ \lambda=(A\;,B,\;\pi) }[/math]. При заданном векторе наблюдений [math]\displaystyle{ y }[/math] алгоритм Баума — Велша находит [math]\displaystyle{ \lambda^*=arg\max_\lambda P(y\mid\lambda) }[/math]. [math]\displaystyle{ \lambda^* }[/math] максимизирует вероятность наблюдений [math]\displaystyle{ y }[/math].
Алгоритм
Исходные данные: [math]\displaystyle{ \lambda=(A,\;B,\;\pi) }[/math] со случайными начальными условиями.
Алгоритм итеративно обновляет параметр [math]\displaystyle{ \lambda }[/math] до схождения в одной точке.
Прямая процедура
Обозначим через [math]\displaystyle{ \alpha_i(t)=p(Y_1=y_1,\;\ldots,\;Y_t=y_t,\;Q_t=i\mid\lambda) }[/math] вероятность появления заданной последовательности [math]\displaystyle{ y_1,\;\ldots,\;y_t }[/math] для состояния [math]\displaystyle{ i }[/math] в момент времени [math]\displaystyle{ t }[/math].
[math]\displaystyle{ \alpha_i(t) }[/math] можно вычислить рекурсивно:
- [math]\displaystyle{ \alpha_i(1)=\pi_i\cdot b_i(y_1); }[/math]
- [math]\displaystyle{ \alpha_j(t+1)=b_j(y_{t+1})\sum^N_{i=1}{\alpha_i(t)\cdot a_{ij}}. }[/math]
Обратная процедура
Данная процедура позволяет вычислить [math]\displaystyle{ \beta_i(t)=p(Y_{t+1}=y_{t+1},\ldots , Y_{T}=y_{T}\mid Q_{t}=i, \lambda ) }[/math] вероятность конечной заданной последовательности [math]\displaystyle{ y_{t+1},\;\ldots,\;y_T }[/math] при условии, что мы начали из исходного состояния [math]\displaystyle{ i }[/math], в момент времени [math]\displaystyle{ t }[/math].
Можно вычислить [math]\displaystyle{ \beta_i(t) }[/math]:
- [math]\displaystyle{ \beta_i(T)=p(Y_{T}=y_{T}\mid Q_{t}=i, \lambda) =1; }[/math]
- [math]\displaystyle{ \beta_i(t)=\sum^N_{j=1}{\beta_j(t+1)a_{ij}b_j(y_{t+1})}. }[/math]
Используя [math]\displaystyle{ \alpha }[/math] и [math]\displaystyle{ \beta }[/math] можно вычислить следующие значения:
- [math]\displaystyle{ \gamma_i(t)\equiv p(Q_t=i\mid y,\;\lambda)=\frac{\alpha_i(t)\beta_i(t)}{\displaystyle\sum^N_{j=1}\alpha_j(t)\beta_j(t)}, }[/math]
- [math]\displaystyle{ \xi_{ij}(t)\equiv p(Q_t=i,\;Q_{t+1}=j\mid y,\;\lambda)=\frac{\alpha_i(t)a_{ij}\beta_j(t+1)b_j(y_{t+1})}{\displaystyle\sum^N_{i=1}\displaystyle\sum^N_{j=1}\alpha_i(t)a_{ij}\beta_j(t+1)b_j(y_{t+1})}. }[/math]
Имея [math]\displaystyle{ \gamma }[/math] и [math]\displaystyle{ \xi }[/math], можно вычислить новые значения параметров модели:
- [math]\displaystyle{ \bar\pi_i=\gamma_i(1), }[/math]
- [math]\displaystyle{ \bar{a}_{ij}=\frac{\displaystyle\sum^{T-1}_{t=1}\xi_{ij}(t)}{\displaystyle\sum^{T-1}_{t=1}\gamma_i(t)}, }[/math]
- [math]\displaystyle{ \bar{b}_i(o_k)=\frac{\displaystyle\sum^T_{t=1}\delta_{y_t,\;o_k}\gamma_i(t)}{\displaystyle\sum^T_{t=1}\gamma_i(t)}. }[/math],
где
- [math]\displaystyle{ \delta_{y_t,\;o_k}= \begin{cases} 1 & \text{если } y_t=o_k,\\ 0 & \text{иначе} \end{cases} }[/math]
индикативная функция, и [math]\displaystyle{ b_i^*(o_k) }[/math] ожидаемое количество значений наблюдаемой величины, равных [math]\displaystyle{ o_k }[/math] в состоянии [math]\displaystyle{ i }[/math] к общему количеству состояний [math]\displaystyle{ i }[/math].
Используя новые значения [math]\displaystyle{ A }[/math], [math]\displaystyle{ B }[/math] и [math]\displaystyle{ \pi }[/math], итерации продолжаются до схождения.