Изменения

[[Скрытые_Марковские_модели | Скрытые Марковские модели]] (англ. ''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>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>\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>.

| <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>

Таким образом получаем новую оценку перехода из <tex>S1S_1</tex> в <tex>S2S_2</tex>, которая составляет <tex dpi="160">\fracdfrac{0.22}{2.4234}</tex><tex> = 0.0908</tex>. После этого можно подсчитать вероятность переходов из <tex>S2S_2</tex> в <tex>S1S_1</tex>, <tex>S2S_2</tex> в <tex>S2S_2</tex>, <tex>S1S_1</tex> в <tex>S1S_1</tex> и изменим их так, чтобы в суммы вероятностей давали <tex>1</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>

! Последовательности !! Наибольшая вероятность наблюдения <br/> Если допустимо, что E получено из <tex>S1S_1</tex> !! Наибольшая вероятность наблюдения

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

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

| <tex>EN </tex> || <tex>0.0560 S1\,S2 </tex> <tex> S_1, </tex> <tex>S_2</tex> || <tex>0.0896 S1\,</tex> <tex>S_1,S2</tex> <tex>S_2</tex>

| <tex>0.2394 </tex> || <tex>0.2730</tex>

Новая оценка для <tex>E</tex>, полученная из <tex>S1S_1</tex>, составляет <tex dpi="160">\fracdfrac{0.2394}{0.2730}</tex> <tex> = 0.8769</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>

Для оценки начальной вероятности, мы предполагаем, что все последовательности начаты со скрытого состояния <tex>S1S_1</tex> и рассчитаны с высокой вероятностью, а затем повторяем для <tex>S2S_2</tex>. После нормализации получаем обновленный исходный вектор.