WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

Алгоритм Баума — Велша используется в информатике и статистике для нахождения неизвестных параметров скрытой марковской модели (HMM). Он использует алгоритм прямого-обратного хода и является частным случаем обобщённого EM-алгоритма.

Алгоритм Баума — Велша оценки скрытой модели Маркова

Скрытая модель Маркова — это вероятностная модель множества случайных переменных $\{O_{1},\;\ldots ,\;O_{t},\;Q_{1},\;\ldots ,\;Q_{t}\}$ . Переменные $O_{t}$ — известные дискретные наблюдения, а $Q_{t}$ — «скрытые» дискретные величины. В рамках скрытой модели Маркова есть два независимых утверждения, обеспечивающих сходимость данного алгоритма:

$t$ -я скрытая переменная при известной $(t-1)$ -ой переменной независима от всех предыдущих $(t-1)$ переменных, то есть $P(Q_{t}\mid Q_{t-1},\;O_{t-1},\;\ldots ,\;Q_{1},\;O_{1})=P(Q_{t}\mid Q_{t-1})$ ;
$t$ -е известное наблюдение зависит только от $t$ -го состояния, то есть не зависит от времени, $P(O_{t}\mid Q_{t},\;Q_{t-1},\;O_{t-1},\;\ldots ,\;Q_{1},\;O_{1})=P(O_{t}\mid Q_{t})$ .

Далее будет предложен алгоритм «предположений и максимизаций» для поиска максимальной вероятностной оценки параметров скрытой модели Маркова при заданном наборе наблюдений. Этот алгоритм также известен как алгоритм Баума — Велша.

$Q_{t}$ — это дискретная случайная переменная, принимающая одно из $N$ значений $(1\ldots N)$ . Будем полагать, что данная модель Маркова, определённая как $P(Q_{t}\mid Q_{t-1})$ , однородна по времени, то есть независима от $t$ . Тогда можно задать $P(Q_{t}\mid Q_{t-1})$ как независящую от времени стохастическую матрицу перемещений $A=\{a_{ij}\}=p(Q_{t}=j\mid Q_{t-1}=i)$ . Особый случай для времени $t=1$ определяется начальным распределением $\pi _{i}=P(Q_{1}=i)$ .

Будем считать, что мы в состоянии $j$ в момент времени $t$ , если $Q_{t}=j$ . Последовательность заданных состояний определяется как $q=(q_{1},\;\ldots ,\;q_{T})$ , где $q_{t}\in \{1\ldots N\}$ является состоянием в момент $t$ .

Наблюдение может иметь одно из $L$ возможных значений, $O_{t}\in \{o_{1},\;\ldots ,\;o_{L}\}$ . Вероятность заданного вектора наблюдений в момент времени $t$ для состояния $j$ определяется как $b_{j}(o_{t})=P(O_{t}=o_{t}\mid Q_{t}=j)$ ( $B=\{b_{ij}\}$ — это матрица $L$ на $N$ ). Заданная последовательность наблюдений $O$ выражается как $O=(O_{1}=o_{1},\;\ldots ,\;O_{T}=o_{T})$ .

Следовательно, мы можем описать скрытую модель Маркова с помощью $\lambda =(A\;,B,\;\pi )$ . При заданном векторе наблюдений $O$ алгоритм Баума — Велша находит $\lambda ^{*}=\max _{\lambda }P(O\mid \lambda )$ . $\lambda$ максимизирует вероятность наблюдений $O$ .

Алгоритм

Исходные данные: $\lambda =(A,\;B,\;\pi )$ со случайными начальными условиями.

Алгоритм итеративно обновляет параметр $\lambda$ до схождения в одной точке.

Прямая процедура

Определим $\alpha _{i}(t)=p(O_{1}=o_{1},\;\ldots ,\;O_{t}=o_{t},\;Q_{t}=i\mid \lambda )$ , что является вероятностью получения заданной последовательности $o_{1},\;\ldots ,\;o_{t}$ для состояния $i$ в момент времени $t$ .

$\alpha _{i}(t)$ можно вычислить рекурсивно:

$\alpha _{i}(1)=\pi _{i}\cdot b_{i}(O_{1});$
$\alpha _{j}(t+1)=b_{j}(O_{t+1})\sum _{i=1}^{N}{\alpha _{i}(t)\cdot a_{ij}}.$

Обратная процедура

Данная процедура позволяет вычислить $\beta _{i}(t)=p(O_{t+1}=o_{t+1},\ldots ,O_{T}=o_{T}\mid Q_{t}=i,\lambda )$ вероятность конечной заданной последовательности $o_{t+1},\;\ldots ,\;o_{T}$ при условии, что мы начали из исходного состояния $i$ , в момент времени $t$ .

Можно вычислить $\beta _{i}(t)$ :

$\beta _{i}(T)=p(\mid Q_{t}=i,\lambda )=1;$
$\beta _{i}(t)=\sum _{j=1}^{N}{\beta _{j}(t+1)a_{ij}b_{j}(O_{t+1})}.$

Используя $\alpha$ и $\beta$ можно вычислить следующие значения:

$\gamma _{i}(t)\equiv p(Q_{t}=i\mid O,\;\lambda )={\frac {\alpha _{i}(t)\beta _{i}(t)}{\displaystyle \sum _{j=1}^{N}\alpha _{j}(t)\beta _{j}(t)}},$
$\xi _{ij}(t)\equiv 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 _{i=1}^{N}\displaystyle \sum _{j=1}^{N}\alpha _{i}(t)a_{ij}\beta _{j}(t+1)b_{j}(O_{t+1})}}.$

Имея $\gamma$ и $\xi$ , можно определить:

${\bar {\pi }}_{i}=\gamma _{i}(1),$
${\bar {a}}_{ij}={\frac {\displaystyle \sum _{t=1}^{T-1}\xi _{ij}(t)}{\displaystyle \sum _{t=1}^{T-1}\gamma _{i}(t)}},$
${\bar {b}}_{i}(k)={\frac {\displaystyle \sum _{t=1}^{T}\delta _{O_{t},\;o_{k}}\gamma _{i}(t)}{\displaystyle \sum _{t=1}^{T}\gamma _{i}(t)}}.$

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

Источники

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .

Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии