Алгоритм Баума-Велша — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример)
(Пример)
 
(не показаны 53 промежуточные версии 6 участников)
Строка 1: Строка 1:
'''''Алгоритм Баума-Велша''''' — алгоритм для нахождения неизвестных параметров [[Скрытые_Марковские_модели | скрытой Марковской модели]]. Использует [[Алгоритм_"Вперед-Назад" | алгоритм прямого-обратного хода]].
+
__TOC__
 +
'''Алгоритм Баума-Велша''' (англ. ''Baum–Welch algorithm'') — алгоритм для нахождения неизвестных параметров [[Скрытые_Марковские_модели | скрытой Марковской модели]]. Использует [[Алгоритм_"Вперед-Назад" | алгоритм прямого-обратного хода]].
 
==История==
 
==История==
[[Скрытые Марковские модели | Скрытые_Марковские_модели]](HMMs) и алгоритм Баума-Велша впервые были описаны в заметках Леонарда Баума и его сверстников в конце 1960х. Одно из первых основных приложений на основе HMMs было использовано в области обработки речи. В 1980х HMMs стало эффективным инструментом в анализе биологических систем и информации, особенно в генном анализе.
+
[[Скрытые_Марковские_модели | Скрытые Марковские модели]] (англ. ''Hidden Markov Models'', ''HMMs'') и алгоритм Баума-Велша впервые были описаны в заметках Леонарда Баума и его сверстников в конце <tex>1960</tex> годов. Одно из первых основных приложений на основе HMMs было использовано в области обработки речи. В <tex>1980</tex> годах HMMs стали эффективным инструментом в анализе биологических систем и информации, особенно в генном анализе.
  
 
== Описание алгоритма==
 
== Описание алгоритма==
Пусть <tex>Q_t</tex> - это дискретная случайная переменная, принимающая одно из <tex>N</tex> значений <tex>(1..N)</tex>. Будем полагать, что данная модель Маркова, определенная как <tex>P(Q_t | Q_{t - 1})</tex> однородна по времени, то есть независима от <tex>t</tex>. Тогда можно задать <tex>P(Q_t | Q_{t - 1}) </tex> как независящую от времени стохастическую матрицу перемещений <tex>A = \{a_{ij}\} = p(Q_t = j | Q_{t - 1} = i)</tex>. Особый случай для времени <tex>t = 1</tex> определяется начальным распределением <tex>\pi_i = P(Q_1 = i)</tex>.
+
Пусть <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, ..., q_T)</tex>, где <tex>q_t \in \{ 1..N\}</tex> является состоянием в момент времени <tex>t</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, ..., o_L\}</tex>. Вероятность заданного вектора наблюдений в момент времени <tex>t</tex> для состояния <tex>j</tex> определяется как <tex>b_j(o_t) = P(O_t = o_t | Q_t = j)( B = \{ b_{ij}\}</tex> - это матрица <tex>L</tex> на <tex>N)</tex>. Заданная последовательность наблюдений <tex>O</tex> выражается как <tex> O = (O_1 = o_1, ..., O_T = o_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> \lambda = (A, B, \pi)</tex>. При заданном векторе наблюдений <tex>O</tex> алгоритм Баума-Велша находит <tex> \lambda^*=\max_\lambda P(O\mid\lambda)</tex>. <tex>\lambda</tex> максимизирует вероятность наблюдений <tex>O</tex>.
 
Следовательно, мы можем описать скрытую модель Маркова с помощью <tex> \lambda = (A, B, \pi)</tex>. При заданном векторе наблюдений <tex>O</tex> алгоритм Баума-Велша находит <tex> \lambda^*=\max_\lambda P(O\mid\lambda)</tex>. <tex>\lambda</tex> максимизирует вероятность наблюдений <tex>O</tex>.
Строка 21: Строка 22:
 
=== Прямая процедура ===
 
=== Прямая процедура ===
  
<tex>a_i(t) = p(O_1 = o_1, ..., O_t = o_t, Q_t = _i | \lambda</tex>, что является вероятностью получения заданной последовательности <tex>\{ o_1, ..., o_t\}</tex> для состояния <tex>i</tex> в момент времени <tex>t</tex>.
+
<tex>a_i(t) = p(O_1 = o_1 \dots O_t = o_t, Q_t = \lambda_i )</tex>, что является вероятностью получения заданной последовательности <tex>\{ o_1 \dots o_t \}</tex> для состояния <tex>i</tex> в момент времени <tex>t</tex>.
  
 
<tex>a_i(t)</tex> можно вычислить рекурсивно:
 
<tex>a_i(t)</tex> можно вычислить рекурсивно:
  
1.<tex>a_i(1) = \pi_i \cdot b_i(O_1) </tex>;
+
<tex>1.\,</tex> <tex>a_i(1) = \pi_i \cdot b_i(O_1) </tex>;
  
2.<tex>a_j(t + 1) = b_j(O_{t + 1})\displaystyle\sum^N_{i=1}a_i(t) \cdot a_{ij}</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}, ..., o_T</tex> при условии, что мы начали из исходного состояния <tex>i</tex>, в момент времени <tex>t</tex>.
+
Данная процедура позволяет вычислить вероятность конечной заданной последовательности <tex>\{ o_{t + 1} \dots o_T \}</tex> при условии, что мы начали из исходного состояния <tex>i</tex>, в момент времени <tex>t</tex>.
  
 
<tex>\beta_i(t)</tex> можно вычислить рекурсивно:
 
<tex>\beta_i(t)</tex> можно вычислить рекурсивно:
  
1.<tex>\beta_i(T) = 1</tex>;
+
<tex>1.\,</tex> <tex>\beta_i(T) = 1</tex>;
  
2. <tex>\beta_i(t) = \displaystyle\sum^N_{j = 1}\beta_j(t + 1)a_{ij}b_j(O_{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>.
  
 
=== Обновление переменных ===
 
=== Обновление переменных ===
Строка 43: Строка 44:
 
Определим временные переменные:
 
Определим временные переменные:
  
<tex>\gamma_i(t) = 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)}</tex>
+
<tex>\gamma_i(t) = p(Q_t=i\mid O,\;\lambda)=</tex> <tex dpi="160">\dfrac{\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)=\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})}</tex>.
+
<tex>\xi_{ij}(t) = p(Q_t=i,\;Q_{t+1}=j\mid O,\;\lambda)=</tex> <tex dpi="160">\dfrac{\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>\gamma</tex> и <tex>\xi</tex>, можно определить:
 
Имея <tex>\gamma</tex> и <tex>\xi</tex>, можно определить:
Строка 51: Строка 52:
 
<tex>\bar\pi_i=\gamma_i(1)</tex>,
 
<tex>\bar\pi_i=\gamma_i(1)</tex>,
  
<tex>\bar{a}_{ij}=\frac{\displaystyle\sum^{T-1}_{t=1}\xi_{ij}(t)}{\displaystyle\sum^{T-1}_{t=1}\gamma_i(t)}</tex>,
+
<tex>\bar{a}_{ij}=\dfrac{\displaystyle\sum^{T-1}_{t=1}\xi_{ij}(t)}{\displaystyle\sum^{T-1}_{t=1}\gamma_i(t)}</tex>,
  
<tex>\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)}</tex>.
+
<tex>\bar{b}_i(k)=\dfrac{\displaystyle\sum^T_{t=1}\delta_{O_t,\;o_k}\gamma_i(t)}{\displaystyle\sum^T_{t=1}\gamma_i(t)}</tex>.
  
 
Используя новые переменные <tex> A, B, \pi</tex> итерации продолжаются до схождения.
 
Используя новые переменные <tex> A, B, \pi</tex> итерации продолжаются до схождения.
  
 
== Пример ==
 
== Пример ==
Предположим, у нас есть курица, с которой мы собираем яйца. Куриные ли это яйца - зависит от некоторых неизвестных факторов. Для простоты предположим, что существуют лишь два состояния, которые определяют куриные ли это яйца. В начальный момент нам неизвестно текущее состояние, также нам неизвестна вероятность перехода из одного состояния в другое. Для начала возьмем произвольные матрицы переходов и состояний.
+
Предположим, у нас есть курица, с которой мы собираем яйца. Снесла ли курица яйца зависит от некоторых неизвестных факторов. Для простоты предположим, что существуют лишь два состояния, которые определяют есть ли яйца. В начальный момент нам неизвестно текущее состояние, также нам неизвестна вероятность перехода из одного состояния в другое. Для начала возьмем произвольные матрицы переходов и состояний.
  
 
<center>
 
<center>
Строка 67: Строка 68:
 
|+Переходы
 
|+Переходы
 
|-
 
|-
! !! Состояние 1 !! Состояние 2
+
! !! Состояние <tex>1</tex> !! Состояние <tex>2</tex>
 
|-
 
|-
! Состояние 1  
+
! Состояние <tex>1</tex>
|0.5 || 0.5
+
|<tex>0.5</tex> || <tex>0.5</tex>
 
|-
 
|-
! Состояние 2
+
! Состояние <tex>2</tex>
|0.3 || 0.7
+
|<tex>0.3</tex> || <tex>0.7</tex>
 
|}
 
|}
 
||
 
||
Строка 81: Строка 82:
 
! !! Яйца не отложены !! Яйца отложены
 
! !! Яйца не отложены !! Яйца отложены
 
|-
 
|-
! Состояние 1  
+
! Состояние <tex>1</tex>
|0.3 || 0.7
+
|<tex>0.3</tex> || <tex>0.7</tex>
 
|-
 
|-
! Состояние 2
+
! Состояние <tex>2</tex>
|0.8 || 0.2
+
|<tex>0.8</tex> || <tex>0.2</tex>
 
|}
 
|}
 
||
 
||
Строка 91: Строка 92:
 
|+ Начальное состояние
 
|+ Начальное состояние
 
|-
 
|-
! Состояние 1  
+
! Состояние <tex>1</tex>
|0.2
+
|<tex>0.2</tex>
 
|-
 
|-
! Состояние 2
+
! Состояние <tex>2</tex>
|0.8
+
|<tex>0.8</tex>
 
|}
 
|}
 
|}
 
|}
 
</center><br />
 
</center><br />
  
Рассмотрим набор наблюдений (E - яйца отложены, N - яйца не отложены):  NN, NN, NN, NN, NE, EE, EN, NN, NN.
+
Рассмотрим набор наблюдений (<tex>E</tex> — яйца отложены, <tex>N</tex> — яйца не отложены):  <tex>NN, NN, NN, NN, NE, EE, EN, NN, NN</tex>.
  
 
Следующим шагом оценим новую матрицу переходов:
 
Следующим шагом оценим новую матрицу переходов:
Строка 107: Строка 108:
 
{| class="wikitable"
 
{| class="wikitable"
 
|-
 
|-
! Последовательность !! Вероятность последовательности и состояний S1 и S2 !! Наибольшая вероятность наблюдения
+
! Последовательность !! Вероятность последовательности и состояний !! Наибольшая вероятность наблюдения
 
|-
 
|-
| NN || 0.024 || 0.3584 S2,S2
+
| <tex>NN</tex> || <tex>0.024</tex> || <tex>0.3584\,</tex>  <tex>S_2,</tex>  <tex>S_2</tex>
 
|-
 
|-
| NN || 0.024 || 0.3584 S2,S2
+
| <tex>NN</tex> || <tex>0.024</tex> || <tex>0.3584\,</tex>  <tex>S_2,</tex>  <tex>S_2</tex>
 
|-
 
|-
| NN || 0.024 || 0.3584 S2,S2
+
| <tex>NN</tex> || <tex>0.024</tex> || <tex>0.3584\,</tex>  <tex>S_2,</tex>  <tex>S_2</tex>
 
|-
 
|-
| NN || 0.024 || 0.3584 S2,S2
+
| <tex>NN</tex> || <tex>0.024</tex> || <tex>0.3584\,</tex>  <tex>S_2,</tex>  <tex>S_2</tex>
 
|-
 
|-
| NE || 0.006 || 0.1344 S2,S1
+
| <tex>NE</tex> || <tex>0.006</tex> || <tex>0.1344\,</tex>  <tex>S_2,</tex>  <tex>S_1</tex>
 
|-
 
|-
| EE || 0.014 || 0.0490 S1,S1
+
| <tex>EE</tex> || <tex>0.014</tex> || <tex>0.0490\,</tex>  <tex>S_1,</tex>  <tex>S_1</tex>
 
|-
 
|-
| EN || 0.056 || 0.0896 S2,S2
+
| <tex>EN</tex> || <tex>0.056</tex> || <tex>0.0896\,</tex>  <tex>S_2,</tex>  <tex>S_2</tex>
 
|-
 
|-
| NN || 0.024 || 0.3584 S2,S2
+
| <tex>NN</tex> || <tex>0.024</tex> || <tex>0.3584\,</tex>  <tex>S_2,</tex>  <tex>S_2</tex>
 
|-
 
|-
| NN || 0.024 || 0.3584 S2,S2
+
| <tex>NN</tex> || <tex>0.024</tex> || <tex>0.3584\,</tex>  <tex>S_2,</tex> <tex>S_2</tex>
 
|-
 
|-
! Итого
+
! Итог
| 0.22 || 2.4234
+
| <tex>0.22</tex> || <tex>2.4234</tex>
 
|}
 
|}
 
</center><br />
 
</center><br />
 +
 +
Таким образом получаем новую оценку перехода из <tex>S_1</tex> в <tex>S_2</tex>, которая составляет <tex dpi="160">\dfrac{0.22}{2.4234}</tex><tex> = 0.0908</tex>. После этого можно подсчитать вероятность переходов из <tex>S_2</tex> в <tex>S_1</tex>, <tex>S_2</tex> в <tex>S_2</tex>, <tex>S_1</tex> в <tex>S_1</tex> и изменим их так, чтобы в суммы вероятностей давали <tex>1</tex>. В итоге получаем новую матрицу переходов:
 +
 +
<center>
 +
{| border="0" style="background:transparent;"
 +
|-
 +
|
 +
{| class="wikitable"
 +
|+Старая матрица                             
 +
|-
 +
! !! Состояние <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>
 +
|}
 +
||
 +
{| class="wikitable"
 +
|+Новая матрица (Псевдовероятности)
 +
|-
 +
! !! Состояние <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>
 +
|}
 +
||
 +
{| class="wikitable"
 +
|+Новая матрица (После изменения)
 +
|-
 +
! !! Состояние <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>
 +
|}
 +
|}
 +
</center>
 +
 +
Далее оценим новую матрицу состояний:
 +
 +
<center>
 +
{| class="wikitable"
 +
|-
 +
! Последовательности !! Наибольшая вероятность наблюдения <br/> Если допустимо, что E получено из <tex>S_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>EE</tex> || <tex>0.0490\,</tex>  <tex> S_1, </tex> <tex>S_1</tex> || <tex>0.0490\,</tex>  <tex>S_1,</tex><tex> S_1</tex>
 +
|-
 +
| <tex>EN</tex> || <tex>0.0560\,</tex>  <tex> S_1, </tex> <tex>S_2</tex> || <tex>0.0896\,</tex>  <tex>S_1,</tex> <tex>S_2</tex>
 +
|-
 +
! Итог
 +
| <tex>0.2394</tex> || <tex>0.2730</tex>
 +
|}
 +
</center><br />
 +
 +
Новая оценка для <tex>E</tex>, полученная из <tex>S_1</tex>, составляет <tex dpi="160">\dfrac{0.2394}{0.2730}</tex> <tex> = 0.8769</tex>.
 +
 +
Благодаря этому, возможно рассчитать матрицу состояний:
 +
 +
<center>
 +
{| border="0" style="background:transparent;"
 +
|-
 +
|
 +
{| class="wikitable"
 +
|+Старая матрица                             
 +
|-
 +
! !! Яйца не отложены  !! Яйца отложены
 +
|-
 +
! Состояние <tex>1</tex>
 +
|<tex>0.3</tex> || <tex>0.7</tex>
 +
|-
 +
! Состояние <tex>2</tex> 
 +
|<tex>0.8</tex> || <tex>0.2</tex>
 +
|}
 +
||
 +
{| class="wikitable"
 +
|+Новая матрица (Оценка)
 +
|-
 +
! !! Яйца не отложены  !! Яйца отложены
 +
|-
 +
! Состояние <tex>1</tex>
 +
|<tex>0.0876</tex> || <tex>0.8769</tex>
 +
|-
 +
! Состояние <tex>2</tex>
 +
|<tex>1.0000</tex> ||<tex> 0.7385</tex>
 +
|}
 +
||
 +
{| class="wikitable"
 +
|+Новая матрица (После изменения)
 +
|-
 +
! !! Яйца не отложены  !! Яйца отложены
 +
|-
 +
! Состояние <tex>1</tex>
 +
|<tex>0.0908</tex> || <tex>0.9092</tex>
 +
|-
 +
! Состояние <tex>2</tex>
 +
|<tex>0.5752</tex> || <tex>0.4248</tex>
 +
|}
 +
|}
 +
</center>
 +
 +
Для оценки начальной вероятности, мы предполагаем, что все последовательности начаты со скрытого состояния <tex>S_1</tex> и рассчитаны с высокой вероятностью, а затем повторяем для <tex>S_2</tex>. После нормализации получаем обновленный исходный вектор.
 +
 +
Повторяем эти шаги до тех пор, пока вероятности не сойдутся.
  
 
== Псевдокод ==
 
== Псевдокод ==
== Применение ==
+
  <font color="green">// T — конечный момент времени</font>
== Источники ==
+
  '''int'''[] DynamicOptionalStateSequance(<tex>\lambda</tex>, d):
1. https://ru.wikipedia.org/wiki/Алгоритм_Баума_-_Велша
+
      '''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://logic.pdmi.ras.ru/~sergey/teaching/asr/notes-09-hmm.pdf
+
*[http://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm Wikipedia — Baum–Welch algorithm]
  
3. http://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm
+
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Марковские цепи]]

Текущая версия на 10:16, 15 марта 2018

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

История[править]

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

Описание алгоритма[править]

Пусть [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 \dots q_T \}[/math], где [math]q_t \in \{ 1\ldots N\}[/math] является состоянием в момент времени [math]t[/math].

Наблюдение может иметь одно из [math]L[/math] возможных значений, [math]Q_t \in \{o_1 \dots o_L\}[/math]. Вероятность заданного вектора наблюдений в момент времени [math]t[/math] для состояния [math]j[/math] определяется как [math]b_j(o_t) = P(O_t = o_t \mid Q_t = j)\ ( B = \{ b_{ij}\}[/math] — это матрица [math]L[/math] на [math]N)[/math]. Заданная последовательность наблюдений [math]O[/math] выражается как [math] O = (O_1 = o_1, \dots ,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]a_i(t) = p(O_1 = o_1 \dots O_t = o_t, Q_t = \lambda_i )[/math], что является вероятностью получения заданной последовательности [math]\{ o_1 \dots o_t \}[/math] для состояния [math]i[/math] в момент времени [math]t[/math].

[math]a_i(t)[/math] можно вычислить рекурсивно:

[math]1.\,[/math] [math]a_i(1) = \pi_i \cdot b_i(O_1) [/math];

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

Обратная процедура[править]

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

[math]\beta_i(t)[/math] можно вычислить рекурсивно:

[math]1.\,[/math] [math]\beta_i(T) = 1[/math];

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

Обновление переменных[править]

Определим временные переменные:

[math]\gamma_i(t) = p(Q_t=i\mid O,\;\lambda)=[/math] [math]\dfrac{\alpha_i(t)\beta_i(t)}{\displaystyle\sum^N_{j=1}\alpha_j(t)\beta_j(t)}[/math]

[math]\xi_{ij}(t) = p(Q_t=i,\;Q_{t+1}=j\mid O,\;\lambda)=[/math] [math]\dfrac{\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}=\dfrac{\displaystyle\sum^{T-1}_{t=1}\xi_{ij}(t)}{\displaystyle\sum^{T-1}_{t=1}\gamma_i(t)}[/math],

[math]\bar{b}_i(k)=\dfrac{\displaystyle\sum^T_{t=1}\delta_{O_t,\;o_k}\gamma_i(t)}{\displaystyle\sum^T_{t=1}\gamma_i(t)}[/math].

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

Пример[править]

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

Переходы
Состояние [math]1[/math] Состояние [math]2[/math]
Состояние [math]1[/math] [math]0.5[/math] [math]0.5[/math]
Состояние [math]2[/math] [math]0.3[/math] [math]0.7[/math]
Состояния
Яйца не отложены Яйца отложены
Состояние [math]1[/math] [math]0.3[/math] [math]0.7[/math]
Состояние [math]2[/math] [math]0.8[/math] [math]0.2[/math]
Начальное состояние
Состояние [math]1[/math] [math]0.2[/math]
Состояние [math]2[/math] [math]0.8[/math]

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

Следующим шагом оценим новую матрицу переходов:

Последовательность Вероятность последовательности и состояний Наибольшая вероятность наблюдения
[math]NN[/math] [math]0.024[/math] [math]0.3584\,[/math] [math]S_2,[/math] [math]S_2[/math]
[math]NN[/math] [math]0.024[/math] [math]0.3584\,[/math] [math]S_2,[/math] [math]S_2[/math]
[math]NN[/math] [math]0.024[/math] [math]0.3584\,[/math] [math]S_2,[/math] [math]S_2[/math]
[math]NN[/math] [math]0.024[/math] [math]0.3584\,[/math] [math]S_2,[/math] [math]S_2[/math]
[math]NE[/math] [math]0.006[/math] [math]0.1344\,[/math] [math]S_2,[/math] [math]S_1[/math]
[math]EE[/math] [math]0.014[/math] [math]0.0490\,[/math] [math]S_1,[/math] [math]S_1[/math]
[math]EN[/math] [math]0.056[/math] [math]0.0896\,[/math] [math]S_2,[/math] [math]S_2[/math]
[math]NN[/math] [math]0.024[/math] [math]0.3584\,[/math] [math]S_2,[/math] [math]S_2[/math]
[math]NN[/math] [math]0.024[/math] [math]0.3584\,[/math] [math]S_2,[/math] [math]S_2[/math]
Итог [math]0.22[/math] [math]2.4234[/math]

Таким образом получаем новую оценку перехода из [math]S_1[/math] в [math]S_2[/math], которая составляет [math]\dfrac{0.22}{2.4234}[/math][math] = 0.0908[/math]. После этого можно подсчитать вероятность переходов из [math]S_2[/math] в [math]S_1[/math], [math]S_2[/math] в [math]S_2[/math], [math]S_1[/math] в [math]S_1[/math] и изменим их так, чтобы в суммы вероятностей давали [math]1[/math]. В итоге получаем новую матрицу переходов:

Старая матрица
Состояние [math]1[/math] Состояние [math]2[/math]
Состояние [math]1[/math] [math]0.5[/math] [math] 0.5[/math]
Состояние [math]2[/math] [math]0.3 [/math] [math]0.7[/math]
Новая матрица (Псевдовероятности)
Состояние [math]1[/math] Состояние [math]2[/math]
Состояние [math]1[/math] [math]0.0598[/math] [math]0.0908[/math]
Состояние [math]2[/math] [math]0.2179[/math] [math] 0.9705[/math]
Новая матрица (После изменения)
Состояние [math]1[/math] Состояние [math]2[/math]
Состояние [math]1[/math] [math]0.3973[/math] [math] 0.6027[/math]
Состояние [math]2[/math] [math]0.1833[/math] [math] 0.8167[/math]

Далее оценим новую матрицу состояний:

Последовательности Наибольшая вероятность наблюдения
Если допустимо, что E получено из [math]S_1[/math]
Наибольшая вероятность наблюдения
[math]NE[/math] [math]0.1344\,[/math] [math] S_2, [/math] [math]S_1[/math] [math]0.1344\,[/math] [math]S_2,[/math][math] S_1[/math]
[math]EE[/math] [math]0.0490\,[/math] [math] S_1, [/math] [math]S_1[/math] [math]0.0490\,[/math] [math]S_1,[/math][math] S_1[/math]
[math]EN[/math] [math]0.0560\,[/math] [math] S_1, [/math] [math]S_2[/math] [math]0.0896\,[/math] [math]S_1,[/math] [math]S_2[/math]
Итог [math]0.2394[/math] [math]0.2730[/math]

Новая оценка для [math]E[/math], полученная из [math]S_1[/math], составляет [math]\dfrac{0.2394}{0.2730}[/math] [math] = 0.8769[/math].

Благодаря этому, возможно рассчитать матрицу состояний:

Старая матрица
Яйца не отложены Яйца отложены
Состояние [math]1[/math] [math]0.3[/math] [math]0.7[/math]
Состояние [math]2[/math] [math]0.8[/math] [math]0.2[/math]
Новая матрица (Оценка)
Яйца не отложены Яйца отложены
Состояние [math]1[/math] [math]0.0876[/math] [math]0.8769[/math]
Состояние [math]2[/math] [math]1.0000[/math] [math] 0.7385[/math]
Новая матрица (После изменения)
Яйца не отложены Яйца отложены
Состояние [math]1[/math] [math]0.0908[/math] [math]0.9092[/math]
Состояние [math]2[/math] [math]0.5752[/math] [math]0.4248[/math]

Для оценки начальной вероятности, мы предполагаем, что все последовательности начаты со скрытого состояния [math]S_1[/math] и рассчитаны с высокой вероятностью, а затем повторяем для [math]S_2[/math]. После нормализации получаем обновленный исходный вектор.

Повторяем эти шаги до тех пор, пока вероятности не сойдутся.

Псевдокод[править]

 // T — конечный момент времени
 int[] DynamicOptionalStateSequance([math]\lambda[/math], d):
     double [math]\gamma[/math][1, i] = [math]\pi[/math][i] * b[i, d[1]]
     int [math]\psi[/math][1, i] = []
     int ans[]
     for t = 2 to T
         for i = 1 to n
             if [math]\gamma[/math][t, j] < [math]\gamma[/math][t - 1, i] * a[i, j] * b[j, d[t]]
                 [math]\gamma[/math][t, j] = [math]\gamma[/math][t - 1, i] * a[i, j] * b[j, d[t]]
                 [math]\psi[/math][t, j] = i
     ans[T] = 1 
     for i = 2 to n
         if [math]\gamma[/math][T, i] > [math]\gamma[/math][T, i - 1]
             ans[T] = i    
     for t = T - 1 downto 1
         ans[t] = [math]\psi[/math][t + 1, ans[t + 1]]
 return ans

См. также[править]

Источники информации[править]