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

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

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

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

1. <math>t</math>-я скрытая переменная при известной <math>(t-1)</math>-ой переменной независима от всех предыдущих <math>(t-1)</math> переменных, то есть <math>P(Q_t\mid Q_{t-1},\;O_{t-1},\;\ldots,\;Q_1,\;O_1)=P(Q_t\mid Q_{t-1})</math>;
2. <math>t</math>-е известное наблюдение зависит только от <math>t</math>-го состояния, то есть не зависит от времени, <math>P(O_t\mid Q_t,\;Q_{t-1},\;O_{t-1},\;\ldots,\;Q_1,\;O_1)=P(O_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>L</math> возможных значений, <math>O_t\in\{o_1,\;\ldots,\;o_L\}</math>. Вероятность заданного вектора наблюдений в момент времени <math>t</math> для состояния <math>j</math> определяется как <math>b_j(o_t)=P(O_t=o_t\mid Q_t=j)</math> (<math>B=\{b_{ij}\}</math> — это матрица <math>L</math> на <math>N</math>). Заданная последовательность наблюдений <math>O</math> выражается как <math>O=(O_1=o_1,\;\ldots,\;O_T=o_T)</math>.

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

Алгоритм

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

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

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

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

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

1. <math>\alpha_i(1)=\pi_i\cdot b_i(O_1);</math>
2. <math>\alpha_j(t+1)=b_j(O_{t+1})\sum^N_{i=1}{\alpha_i(t)\cdot a_{ij}}.</math>

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

Данная процедура позволяет вычислить <math>\beta_i(t)=p(O_{t+1}=o_{t+1},\ldots , O_{T}=o_{T}\mid Q_{t}=i, \lambda )</math> вероятность конечной заданной последовательности <math>o_{t+1},\;\ldots,\;o_T</math> при условии, что мы начали из исходного состояния <math>i</math>, в момент времени <math>t</math>.

Можно вычислить <math>\beta_i(t)</math>:

1. <math>\beta_i(T)=p(\mid Q_{t}=i, \lambda) =1;</math>
2. <math>\beta_i(t)=\sum^N_{j=1}{\beta_j(t+1)a_{ij}b_j(O_{t+1})}.</math>

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

• <math>\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)},</math>
• <math>\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})}.</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(k)=\frac{\displaystyle\sum^T_{t=1}\delta_{O_t,\;o_k}\gamma_i(t)}{\displaystyle\sum^T_{t=1}\gamma_i(t)}.</math>

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

Источники

• [www.ph.biu.ac.il/faculty/kanter/BW.pdf The Baum-Welch algorithm for estimating a Hidden Markov Model]
• [jedlik.phy.bme.hu/~gerjanos/HMM/node11.html Baum-Welch Algorithm]
• [logic.pdmi.ras.ru/~sergey/teaching/asr/notes-09-hmm.pdf Лекции С.Николенко по скрытым марковским моделям]

Отрывок, характеризующий Алгоритм Баума — Велша

Княгиня покраснела и отчаянно взмахнула руками.
– Non, Andre, je dis que vous avez tellement, tellement change… [Нет, Андрей, я говорю: ты так, так переменился…]
– Твой доктор велит тебе раньше ложиться, – сказал князь Андрей. – Ты бы шла спать.
Княгиня ничего не сказала, и вдруг короткая с усиками губка задрожала; князь Андрей, встав и пожав плечами, прошел по комнате.
Пьер удивленно и наивно смотрел через очки то на него, то на княгиню и зашевелился, как будто он тоже хотел встать, но опять раздумывал.
– Что мне за дело, что тут мсье Пьер, – вдруг сказала маленькая княгиня, и хорошенькое лицо ее вдруг распустилось в слезливую гримасу. – Я тебе давно хотела сказать, Andre: за что ты ко мне так переменился? Что я тебе сделала? Ты едешь в армию, ты меня не жалеешь. За что?
– Lise! – только сказал князь Андрей; но в этом слове были и просьба, и угроза, и, главное, уверение в том, что она сама раскается в своих словах; но она торопливо продолжала:
– Ты обращаешься со мной, как с больною или с ребенком. Я всё вижу. Разве ты такой был полгода назад?
– Lise, я прошу вас перестать, – сказал князь Андрей еще выразительнее.
Пьер, всё более и более приходивший в волнение во время этого разговора, встал и подошел к княгине. Он, казалось, не мог переносить вида слез и сам готов был заплакать.
– Успокойтесь, княгиня. Вам это так кажется, потому что я вас уверяю, я сам испытал… отчего… потому что… Нет, извините, чужой тут лишний… Нет, успокойтесь… Прощайте…
Князь Андрей остановил его за руку.
– Нет, постой, Пьер. Княгиня так добра, что не захочет лишить меня удовольствия провести с тобою вечер.
– Нет, он только о себе думает, – проговорила княгиня, не удерживая сердитых слез.
– Lise, – сказал сухо князь Андрей, поднимая тон на ту степень, которая показывает, что терпение истощено.
Вдруг сердитое беличье выражение красивого личика княгини заменилось привлекательным и возбуждающим сострадание выражением страха; она исподлобья взглянула своими прекрасными глазками на мужа, и на лице ее показалось то робкое и признающееся выражение, какое бывает у собаки, быстро, но слабо помахивающей опущенным хвостом.
– Mon Dieu, mon Dieu! [Боже мой, Боже мой!] – проговорила княгиня и, подобрав одною рукой складку платья, подошла к мужу и поцеловала его в лоб.
– Bonsoir, Lise, [Доброй ночи, Лиза,] – сказал князь Андрей, вставая и учтиво, как у посторонней, целуя руку.


Друзья молчали. Ни тот, ни другой не начинал говорить. Пьер поглядывал на князя Андрея, князь Андрей потирал себе лоб своею маленькою рукой.
– Пойдем ужинать, – сказал он со вздохом, вставая и направляясь к двери.
Они вошли в изящно, заново, богато отделанную столовую. Всё, от салфеток до серебра, фаянса и хрусталя, носило на себе тот особенный отпечаток новизны, который бывает в хозяйстве молодых супругов. В середине ужина князь Андрей облокотился и, как человек, давно имеющий что нибудь на сердце и вдруг решающийся высказаться, с выражением нервного раздражения, в каком Пьер никогда еще не видал своего приятеля, начал говорить:
– Никогда, никогда не женись, мой друг; вот тебе мой совет: не женись до тех пор, пока ты не скажешь себе, что ты сделал всё, что мог, и до тех пор, пока ты не перестанешь любить ту женщину, какую ты выбрал, пока ты не увидишь ее ясно; а то ты ошибешься жестоко и непоправимо. Женись стариком, никуда негодным… А то пропадет всё, что в тебе есть хорошего и высокого. Всё истратится по мелочам. Да, да, да! Не смотри на меня с таким удивлением. Ежели ты ждешь от себя чего нибудь впереди, то на каждом шагу ты будешь чувствовать, что для тебя всё кончено, всё закрыто, кроме гостиной, где ты будешь стоять на одной доске с придворным лакеем и идиотом… Да что!…
Он энергически махнул рукой.
Пьер снял очки, отчего лицо его изменилось, еще более выказывая доброту, и удивленно глядел на друга.
– Моя жена, – продолжал князь Андрей, – прекрасная женщина. Это одна из тех редких женщин, с которою можно быть покойным за свою честь; но, Боже мой, чего бы я не дал теперь, чтобы не быть женатым! Это я тебе одному и первому говорю, потому что я люблю тебя.