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