Изменения
→Пример
__TOC__
'''Алгоритм Баума-Велша''' (англ. ''Baum–Welch algorithm'') — алгоритм для нахождения неизвестных параметров [[Скрытые_Марковские_модели | скрытой Марковской модели]]. Использует [[Алгоритм_"Вперед-Назад" | алгоритм прямого-обратного хода]].
==История==
[[Скрытые_Марковские_модели | Скрытые Марковские модели]] (англ. ''Hidden Markov Models'', ''HMMs'') и алгоритм Баума-Велша впервые были описаны в заметках Леонарда Баума и его сверстников в конце <tex>1960</tex>годов. Одно из первых основных приложений на основе HMMs было использовано в области обработки речи. В <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>a_i(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>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>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>2</tex>
|-
! Состояние <tex>1 </tex>
|<tex>0.0598</tex> || <tex>0.0908</tex>
|-
! Состояние <tex>2 </tex>
|<tex>0.2179</tex> ||<tex> 0.9705</tex>
|}
|+Новая матрица (После изменения)
|-
! !! Состояние <tex>1 </tex> !! Состояние <tex>2</tex>
|-
! Состояние <tex>1 </tex>
|<tex>0.3973</tex> ||<tex> 0.6027</tex>
|-
! Состояние <tex>2 </tex>
|<tex>0.1833</tex> ||<tex> 0.8167</tex>
|}
{| class="wikitable"
|-
! Последовательности !! Наибольшая вероятность наблюдения <br/> Если допустимо, что E получено из <tex>S1S_1</tex> !! Наибольшая вероятность наблюдения
|-
| <tex>NE</tex> || <tex>0.1344\,</tex> <tex> S_2, </tex> <tex>S_1</tex> || <tex>0.1344\,</tex> <tex>S_2,</tex><tex> S_1</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.0876</tex> || <tex>0.8769</tex>
|-
! Состояние <tex>2 </tex>
|<tex>1.0000</tex> ||<tex> 0.7385</tex>
|}
! !! Яйца не отложены !! Яйца отложены
|-
! Состояние <tex>1 </tex>
|<tex>0.0908</tex> || <tex>0.9092</tex>
|-
! Состояние <tex>2 </tex>
|<tex>0.5752</tex> || <tex>0.4248</tex>
|}
