Алгоритм Баума — Велша

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

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

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

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

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

• ${\displaystyle \gamma _{i}(t)\equiv p(Q_{t}=i\mid y,\;\lambda )={\frac {\alpha _{i}(t)\beta _{i}(t)}{\displaystyle \sum _{j=1}^{N}\alpha _{j}(t)\beta _{j}(t)}},}$
• ${\displaystyle \xi _{ij}(t)\equiv p(Q_{t}=i,\;Q_{t+1}=j\mid y,\;\lambda )={\frac {\alpha _{i}(t)a_{ij}\beta _{j}(t+1)b_{j}(y_{t+1})}{\displaystyle \sum _{i=1}^{N}\displaystyle \sum _{j=1}^{N}\alpha _{i}(t)a_{ij}\beta _{j}(t+1)b_{j}(y_{t+1})}}.}$

Имея ${\displaystyle \gamma }$ и ${\displaystyle \xi }$, можно вычислить новые значения параметров модели:

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

где

${\displaystyle \delta _{y_{t},\;o_{k}}={\begin{cases}1&{\text{если }}y_{t}=o_{k},\\0&{\text{иначе}}\end{cases}}}$

индикативная функция, и ${\displaystyle b_{i}^{*}(o_{k})}$ ожидаемое количество значений наблюдаемой величины, равных ${\displaystyle o_{k}}$ в состоянии ${\displaystyle i}$ к общему количеству состояний ${\displaystyle i}$.

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

Источники

• The Baum-Welch algorithm for estimating a Hidden Markov Model
• Baum-Welch Algorithm
• Лекции С.Николенко по скрытым марковским моделям