50
правок
Изменения
м
Грамматика
'''''Алгоритм Баума-Велша(Baum–Welch algorithm)''''' — алгоритм для нахождения неизвестных параметров [[Скрытые_Марковские_модели | скрытой Марковской модели]]. Использует [[Алгоритм_"Вперед-Назад" | алгоритм прямого-обратного хода]].
==История==
[[Скрытые_Марковские_модели | Скрытые Марковские модели]](HMMs) и алгоритм Баума-Велша впервые были описаны в заметках Леонарда Баума и его сверстников в конце 1960х. Одно из первых основных приложений на основе HMMs было использовано в области обработки речи. В 1980х 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>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>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> \lambda = (A, B, \pi)</tex>. При заданном векторе наблюдений <tex>O</tex> алгоритм Баума-Велша находит <tex> \lambda^*=\max_\lambda P(O\mid\lambda)</tex>. <tex>\lambda</tex> максимизирует вероятность наблюдений <tex>O</tex>.
== Пример ==
Предположим, у нас есть курица, с которой мы собираем яйца. Куриные Снесла ли это курица яйца - — зависит от некоторых неизвестных факторов. Для простоты предположим, что существуют лишь два состояния, которые определяют куриные ли это яйца. В начальный момент нам неизвестно текущее состояние, также нам неизвестна вероятность перехода из одного состояния в другое. Для начала возьмем произвольные матрицы переходов и состояний.
<center>
</center><br />
Рассмотрим набор наблюдений (E - яйца отложены, N - — яйца не отложены): NN, NN, NN, NN, NE, EE, EN, NN, NN.
Следующим шагом оценим новую матрицу переходов:
