Алгоритм Баума-Велша — различия между версиями
(→Обратная процедура) |
м (rollbackEdits.php mass rollback) |
||
(не показано 9 промежуточных версий 5 участников) | |||
Строка 1: | Строка 1: | ||
+ | __TOC__ | ||
'''Алгоритм Баума-Велша''' (англ. ''Baum–Welch algorithm'') — алгоритм для нахождения неизвестных параметров [[Скрытые_Марковские_модели | скрытой Марковской модели]]. Использует [[Алгоритм_"Вперед-Назад" | алгоритм прямого-обратного хода]]. | '''Алгоритм Баума-Велша''' (англ. ''Baum–Welch algorithm'') — алгоритм для нахождения неизвестных параметров [[Скрытые_Марковские_модели | скрытой Марковской модели]]. Использует [[Алгоритм_"Вперед-Назад" | алгоритм прямого-обратного хода]]. | ||
==История== | ==История== | ||
− | [[Скрытые_Марковские_модели | Скрытые Марковские модели]] (HMMs) и алгоритм Баума-Велша впервые были описаны в заметках Леонарда Баума и его сверстников в конце <tex>1960</tex>. Одно из первых основных приложений на основе HMMs было использовано в области обработки речи. В <tex>1980</tex> HMMs стали эффективным инструментом в анализе биологических систем и информации, особенно в генном анализе. | + | [[Скрытые_Марковские_модели | Скрытые Марковские модели]] (англ. ''Hidden Markov Models'', ''HMMs'') и алгоритм Баума-Велша впервые были описаны в заметках Леонарда Баума и его сверстников в конце <tex>1960</tex> годов. Одно из первых основных приложений на основе HMMs было использовано в области обработки речи. В <tex>1980</tex> годах HMMs стали эффективным инструментом в анализе биологических систем и информации, особенно в генном анализе. |
== Описание алгоритма== | == Описание алгоритма== | ||
− | Пусть <tex>Q_t</tex> — это дискретная случайная переменная, принимающая одно из <tex>N</tex> значений <tex>(1 | + | Пусть <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>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>. | ||
Строка 25: | Строка 26: | ||
<tex>a_i(t)</tex> можно вычислить рекурсивно: | <tex>a_i(t)</tex> можно вычислить рекурсивно: | ||
− | <tex>1.\,</tex><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>; |
− | <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>2.\,</tex> <tex>a_j(t + 1) = b_j(O_{t + 1})\displaystyle\sum^N_{i=1}a_i(t) \cdot a_{ij}</tex>. |
=== Обратная процедура === | === Обратная процедура === | ||
Строка 67: | Строка 68: | ||
|+Переходы | |+Переходы | ||
|- | |- | ||
− | ! !! Состояние 1 !! Состояние | + | ! !! Состояние <tex>1</tex> !! Состояние <tex>2</tex> |
|- | |- | ||
− | ! Состояние 1 | + | ! Состояние <tex>1</tex> |
|<tex>0.5</tex> || <tex>0.5</tex> | |<tex>0.5</tex> || <tex>0.5</tex> | ||
|- | |- | ||
− | ! Состояние 2 | + | ! Состояние <tex>2</tex> |
|<tex>0.3</tex> || <tex>0.7</tex> | |<tex>0.3</tex> || <tex>0.7</tex> | ||
|} | |} | ||
Строка 81: | Строка 82: | ||
! !! Яйца не отложены !! Яйца отложены | ! !! Яйца не отложены !! Яйца отложены | ||
|- | |- | ||
− | ! Состояние 1 | + | ! Состояние <tex>1</tex> |
|<tex>0.3</tex> || <tex>0.7</tex> | |<tex>0.3</tex> || <tex>0.7</tex> | ||
|- | |- | ||
− | ! Состояние 2 | + | ! Состояние <tex>2</tex> |
|<tex>0.8</tex> || <tex>0.2</tex> | |<tex>0.8</tex> || <tex>0.2</tex> | ||
|} | |} | ||
Строка 91: | Строка 92: | ||
|+ Начальное состояние | |+ Начальное состояние | ||
|- | |- | ||
− | ! Состояние 1 | + | ! Состояние <tex>1</tex> |
|<tex>0.2</tex> | |<tex>0.2</tex> | ||
|- | |- | ||
− | ! Состояние 2 | + | ! Состояние <tex>2</tex> |
|<tex>0.8</tex> | |<tex>0.8</tex> | ||
|} | |} | ||
Строка 141: | Строка 142: | ||
|+Старая матрица | |+Старая матрица | ||
|- | |- | ||
− | ! !! Состояние 1 !! Состояние 2 | + | ! !! Состояние <tex>1</tex> !! Состояние <tex>2</tex> |
|- | |- | ||
− | ! Состояние 1 | + | ! Состояние <tex>1</tex> |
|<tex>0.5</tex> ||<tex> 0.5</tex> | |<tex>0.5</tex> ||<tex> 0.5</tex> | ||
|- | |- | ||
− | ! Состояние 2 | + | ! Состояние <tex>2</tex> |
|<tex>0.3 </tex>|| <tex>0.7</tex> | |<tex>0.3 </tex>|| <tex>0.7</tex> | ||
|} | |} | ||
Строка 153: | Строка 154: | ||
|+Новая матрица (Псевдовероятности) | |+Новая матрица (Псевдовероятности) | ||
|- | |- | ||
− | ! !! Состояние 1 !! Состояние 2 | + | ! !! Состояние <tex>1</tex> !! Состояние <tex>2</tex> |
|- | |- | ||
− | ! Состояние 1 | + | ! Состояние <tex>1</tex> |
|<tex>0.0598</tex> || <tex>0.0908</tex> | |<tex>0.0598</tex> || <tex>0.0908</tex> | ||
|- | |- | ||
− | ! Состояние 2 | + | ! Состояние <tex>2</tex> |
|<tex>0.2179</tex> ||<tex> 0.9705</tex> | |<tex>0.2179</tex> ||<tex> 0.9705</tex> | ||
|} | |} | ||
Строка 165: | Строка 166: | ||
|+Новая матрица (После изменения) | |+Новая матрица (После изменения) | ||
|- | |- | ||
− | ! !! Состояние 1 !! Состояние 2 | + | ! !! Состояние <tex>1</tex> !! Состояние <tex>2</tex> |
|- | |- | ||
− | ! Состояние 1 | + | ! Состояние <tex>1</tex> |
|<tex>0.3973</tex> ||<tex> 0.6027</tex> | |<tex>0.3973</tex> ||<tex> 0.6027</tex> | ||
|- | |- | ||
− | ! Состояние 2 | + | ! Состояние <tex>2</tex> |
|<tex>0.1833</tex> ||<tex> 0.8167</tex> | |<tex>0.1833</tex> ||<tex> 0.8167</tex> | ||
|} | |} | ||
Строка 181: | Строка 182: | ||
{| class="wikitable" | {| class="wikitable" | ||
|- | |- | ||
− | ! Последовательности !! Наибольшая вероятность наблюдения <br/> Если допустимо, что E получено из <tex> | + | ! Последовательности !! Наибольшая вероятность наблюдения <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>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> | ||
Строка 207: | Строка 208: | ||
! !! Яйца не отложены !! Яйца отложены | ! !! Яйца не отложены !! Яйца отложены | ||
|- | |- | ||
− | ! Состояние 1 | + | ! Состояние <tex>1</tex> |
|<tex>0.3</tex> || <tex>0.7</tex> | |<tex>0.3</tex> || <tex>0.7</tex> | ||
|- | |- | ||
− | ! Состояние 2 | + | ! Состояние <tex>2</tex> |
|<tex>0.8</tex> || <tex>0.2</tex> | |<tex>0.8</tex> || <tex>0.2</tex> | ||
|} | |} | ||
Строка 219: | Строка 220: | ||
! !! Яйца не отложены !! Яйца отложены | ! !! Яйца не отложены !! Яйца отложены | ||
|- | |- | ||
− | ! Состояние 1 | + | ! Состояние <tex>1</tex> |
|<tex>0.0876</tex> || <tex>0.8769</tex> | |<tex>0.0876</tex> || <tex>0.8769</tex> | ||
|- | |- | ||
− | ! Состояние 2 | + | ! Состояние <tex>2</tex> |
|<tex>1.0000</tex> ||<tex> 0.7385</tex> | |<tex>1.0000</tex> ||<tex> 0.7385</tex> | ||
|} | |} | ||
Строка 231: | Строка 232: | ||
! !! Яйца не отложены !! Яйца отложены | ! !! Яйца не отложены !! Яйца отложены | ||
|- | |- | ||
− | ! Состояние 1 | + | ! Состояние <tex>1</tex> |
|<tex>0.0908</tex> || <tex>0.9092</tex> | |<tex>0.0908</tex> || <tex>0.9092</tex> | ||
|- | |- | ||
− | ! Состояние 2 | + | ! Состояние <tex>2</tex> |
|<tex>0.5752</tex> || <tex>0.4248</tex> | |<tex>0.5752</tex> || <tex>0.4248</tex> | ||
|} | |} |
Текущая версия на 19:31, 4 сентября 2022
Алгоритм Баума-Велша (англ. Baum–Welch algorithm) — алгоритм для нахождения неизвестных параметров скрытой Марковской модели. Использует алгоритм прямого-обратного хода.
История
Скрытые Марковские модели (англ. Hidden Markov Models, HMMs) и алгоритм Баума-Велша впервые были описаны в заметках Леонарда Баума и его сверстников в конце годов. Одно из первых основных приложений на основе HMMs было использовано в области обработки речи. В годах HMMs стали эффективным инструментом в анализе биологических систем и информации, особенно в генном анализе.
Описание алгоритма
Пусть
— это дискретная случайная переменная, принимающая одно из значений . Будем полагать, что данная модель Маркова, определенная как однородна по времени, то есть независима от . Тогда можно задать как независящую от времени стохастическую матрицу перемещений . Особый случай для времени определяется начальным распределением .Будем считать, что мы в состоянии
в момент времени , если . Последовательность заданных состояний определяется как , где является состоянием в момент времени .Наблюдение может иметь одно из
возможных значений, . Вероятность заданного вектора наблюдений в момент времени для состояния определяется как — это матрица на . Заданная последовательность наблюдений выражается как .Следовательно, мы можем описать скрытую модель Маркова с помощью
. При заданном векторе наблюдений алгоритм Баума-Велша находит . максимизирует вероятность наблюдений .
Исходные данные:
со случайными начальными условиями. Алгоритм итеративно обновляет параметр до схождения в одной точке.
Прямая процедура
, что является вероятностью получения заданной последовательности для состояния в момент времени .
можно вычислить рекурсивно:
;
.
Обратная процедура
Данная процедура позволяет вычислить вероятность конечной заданной последовательности
при условии, что мы начали из исходного состояния , в момент времени .можно вычислить рекурсивно:
;
.
Обновление переменных
Определим временные переменные:
.
Имея
и , можно определить:,
,
.
Используя новые переменные
итерации продолжаются до схождения.Пример
Предположим, у нас есть курица, с которой мы собираем яйца. Снесла ли курица яйца — зависит от некоторых неизвестных факторов. Для простоты предположим, что существуют лишь два состояния, которые определяют есть ли яйца. В начальный момент нам неизвестно текущее состояние, также нам неизвестна вероятность перехода из одного состояния в другое. Для начала возьмем произвольные матрицы переходов и состояний.
|
|
|
Рассмотрим набор наблюдений (
— яйца отложены, — яйца не отложены): .Следующим шагом оценим новую матрицу переходов:
Последовательность | Вероятность последовательности и состояний | Наибольшая вероятность наблюдения |
---|---|---|
Итог |
Таким образом получаем новую оценку перехода из
в , которая составляет . После этого можно подсчитать вероятность переходов из в , в , в и изменим их так, чтобы в суммы вероятностей давали . В итоге получаем новую матрицу переходов:
|
|
|
Далее оценим новую матрицу состояний:
Последовательности | Наибольшая вероятность наблюдения Если допустимо, что E получено из |
Наибольшая вероятность наблюдения |
---|---|---|
Итог |
Новая оценка для
, полученная из , составляет .Благодаря этому, возможно рассчитать матрицу состояний:
|
|
|
Для оценки начальной вероятности, мы предполагаем, что все последовательности начаты со скрытого состояния
и рассчитаны с высокой вероятностью, а затем повторяем для . После нормализации получаем обновленный исходный вектор.Повторяем эти шаги до тех пор, пока вероятности не сойдутся.
Псевдокод
// T — конечный момент времени int[] DynamicOptionalStateSequance(, d): double [1, i] = [i] * b[i, d[1]] int [1, i] = [] int ans[] for t = 2 to T for i = 1 to n if [t, j] < [t - 1, i] * a[i, j] * b[j, d[t]] [t, j] = [t - 1, i] * a[i, j] * b[j, d[t]] [t, j] = i ans[T] = 1 for i = 2 to n if [T, i] > [T, i - 1] ans[T] = i for t = T - 1 downto 1 ans[t] = [t + 1, ans[t + 1]] return ans