Изменения

''__TOC__'''Алгоритм Баума-Велша'''(англ. ''Baum–Welch algorithm'' ) — алгоритм для нахождения неизвестных параметров [[Скрытые_Марковские_модели | скрытой Марковской модели]]. Использует [[Алгоритм_"Вперед-Назад" | алгоритм прямого-обратного хода]].

[[Скрытые_Марковские_модели | Скрытые Марковские модели | Скрытые_Марковские_модели]](англ. ''Hidden Markov Models'', ''HMMs'') и алгоритм Баума-Велша впервые были описаны в заметках Леонарда Баума и его сверстников в конце 1960х<tex>1960</tex> годов. Одно из первых основных приложений на основе HMMs было использовано в области обработки речи. В 1980х <tex>1980</tex> годах HMMs стало стали эффективным инструментом в анализе биологических систем и информации, особенно в генном анализе.

Пусть <tex>Q_t</tex> - — это дискретная случайная переменная, принимающая одно из <tex>N</tex> значений <tex>(1..\ldots N)</tex>. Будем полагать, что данная модель Маркова, определенная как <tex>P(Q_t | \mid Q_{t - 1})</tex> однородна по времени, то есть независима от <tex>t</tex>. Тогда можно задать <tex>P(Q_t | \mid Q_{t - 1}) </tex> как независящую от времени стохастическую матрицу перемещений <tex>A = \{a_{ij}\} = p(Q_t = j | \mid 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..\ldots 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 | \mid 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>a_i(t) = p(O_1 = o_1, ..., \dots O_t = o_t, Q_t = _i | \lambdalambda_i )</tex>, что является вероятностью получения заданной последовательности <tex>\{ o_1, ..., \dots o_t\}</tex> для состояния <tex>i</tex> в момент времени <tex>t</tex>.

<tex>1.\,</tex> <tex>a_i(1) = \pi_i \cdot b_i(O_1) </tex>;

<tex>2.\,</tex> <tex>a_j(t + 1) = b_j(O_{t + 1})\displaystyle\sum^N_{i=1}a_i(t) \cdot a_{ij}</tex>.

Данная процедура позволяет вычислить вероятность конечной заданной последовательности <tex>\{ o_{t + 1}, ..., \dots o_T\}</tex> при условии, что мы начали из исходного состояния <tex>i</tex>, в момент времени <tex>t</tex>.

<tex>1.\,</tex> <tex>\beta_i(T) = 1</tex>;

<tex>2. \,</tex> <tex>\beta_i(t) = \displaystyle\sum^N_{j = 1}\beta_j(t + 1)a_{ij}b_j(O_{t + 1})</tex>.

<tex>\gamma_i(t) = p(Q_t=i\mid O,\;\lambda)=</tex> <tex dpi="160">\fracdfrac{\alpha_i(t)\beta_i(t)}{\displaystyle\sum^N_{j=1}\alpha_j(t)\beta_j(t)}</tex>

<tex>\xi_{ij}(t) = p(Q_t=i,\;Q_{t+1}=j\mid O,\;\lambda)=</tex> <tex dpi="160">\fracdfrac{\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})}</tex>.

<tex>\bar{a}_{ij}=\fracdfrac{\displaystyle\sum^{T-1}_{t=1}\xi_{ij}(t)}{\displaystyle\sum^{T-1}_{t=1}\gamma_i(t)}</tex>,

<tex>\bar{b}_i(k)=\fracdfrac{\displaystyle\sum^T_{t=1}\delta_{O_t,\;o_k}\gamma_i(t)}{\displaystyle\sum^T_{t=1}\gamma_i(t)}</tex>.

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

! !! Состояние <tex>1 </tex> !! Состояние <tex>2</tex>

! Состояние <tex>1 </tex> |<tex>0.5 </tex> || <tex>0.5</tex>

! Состояние <tex>2 </tex> |<tex>0.3 </tex> || <tex>0.7</tex>

! Состояние <tex>1 </tex>|<tex>0.3 </tex> || <tex>0.7</tex>

! Состояние <tex>2 </tex>|<tex>0.8 </tex> || <tex>0.2</tex>

! Состояние <tex>1 </tex> |<tex>0.2</tex>

! Состояние <tex>2 </tex> |<tex>0.8</tex>

Рассмотрим набор наблюдений (<tex>E - </tex> — яйца отложены, <tex>N - </tex> — яйца не отложены): <tex>NN, NN, NN, NN, NE, EE, EN, NN, NN</tex>.

! Последовательность !! Вероятность последовательности и состояний S1 и S2 !! Наибольшая вероятность наблюдения

| <tex>NN </tex> || <tex>0.024 </tex> || <tex>0.3584 S2\,S2</tex> <tex>S_2,</tex> <tex>S_2</tex>

| <tex>NN </tex> || <tex>0.024 </tex> || <tex>0.3584 S2\,S2</tex> <tex>S_2,</tex> <tex>S_2</tex>

| <tex>NN </tex> || <tex>0.024 </tex> || <tex>0.3584 S2\,S2</tex> <tex>S_2,</tex> <tex>S_2</tex>

| <tex>NN </tex> || <tex>0.024 </tex> || <tex>0.3584 S2\,S2</tex> <tex>S_2,</tex> <tex>S_2</tex>

| <tex>NE </tex> || <tex>0.006 </tex> || <tex>0.1344 S2\,S1</tex> <tex>S_2,</tex> <tex>S_1</tex>

| <tex>EE </tex> || <tex>0.014 </tex> || <tex>0.0490 S1\,S1</tex> <tex>S_1,</tex> <tex>S_1</tex>

| <tex>EN </tex> || <tex>0.056 </tex> || <tex>0.0896 S2\,S2</tex> <tex>S_2,</tex> <tex>S_2</tex>

| <tex>NN </tex> || <tex>0.024 </tex> || <tex>0.3584 S2\,S2</tex> <tex>S_2,</tex> <tex>S_2</tex>

| <tex>NN </tex> || <tex>0.024 </tex> || <tex>0.3584 S2\,S2</tex> <tex>S_2,</tex> <tex>S_2</tex>

! ИтогоИтог| <tex>0.22 </tex> || <tex>2.4234</tex>

<font color="green">// T — конечный момент времени</font> '''int'''[] DynamicOptionalStateSequance(<tex>\lambda</tex>, d): '''double''' <tex>\gamma</tex>[1, i] = Применение <tex>\pi</tex>[i] * b[i, d[1]] '''int''' <tex>\psi</tex>[1, i] =[] '''int''' ans[] '''for''' t =2 '''to''' T '''for''' i =1 '''to''' n '''if''' <tex>\gamma</tex>[t, j] < <tex>\gamma</tex>[t - 1, i] * a[i, j] * b[j, d[t]] <tex>\gamma</tex>[t, j] = Источники <tex>\gamma</tex>[t - 1, i] * a[i, j] * b[j, d[t]] <tex>\psi</tex>[t, j] = i ans[T] = 1 '''for''' i =2 '''to''' n '''if''' <tex>\gamma</tex>[T, i] > <tex>\gamma</tex>[T, i - 1] ans[T] =i '''for''' t = T - 1'''downto''' 1 ans[t] = <tex>\psi</tex>[t + 1, ans[t + 1]] '''return''' ans == См. также == *[[Скрытые Марковские модели]]*[[Алгоритм "Вперед-Назад"]]*[[Алгоритм Витерби]] == Источники информации==*[https://ru.wikipedia.org/wiki/Алгоритм_Баума_Алгоритм_Баума_—_Велша Википедия — Алгоритм Баума-_ВелшаВелша] *[http://logic.pdmi.ras.ru/~sergey/teaching/asr/notes-09-hmm.pdf Лекция "Скрытые Марковские Модели" Сергея Николенко]

2. *[http://logicen.pdmiwikipedia.ras.ruorg/~sergeywiki/teaching/asr/notes-09-hmm.pdfBaum%E2%80%93Welch_algorithm Wikipedia — Baum–Welch algorithm]

3. http[[Категория://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithmДискретная математика и алгоритмы]][[Категория: Марковские цепи]]