50
правок
Изменения
Новая страница: «'''''Алгоритм Баума-Велша''''' — алгоритм для нахождения неизвестных параметров [[Скрытые_М...»
'''''Алгоритм Баума-Велша''''' — алгоритм для нахождения неизвестных параметров [[Скрытые_Марковские_модели | скрытой Марковской модели]]. Использует [[Алгоритм_"Вперед-Назад" | алгоритм прямого-обратного хода]].
== Описание алгоритма==
Пусть <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>.
'''Исходные данные: '''<tex> \lambda = (A, B, \pi)</tex> со случайными начальными условиями.
Алгоритм итеративно обновляет параметр <tex>\lambda</tex> до схождения в одной точке.
'''Прямая процедура'''
<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)</tex> можно вычислить рекурсивно:
1.<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>.
== Псевдокод ==
== Применение ==
== Источники ==
1. https://ru.wikipedia.org/wiki/Алгоритм_Баума_-_Велша
2. http://logic.pdmi.ras.ru/~sergey/teaching/asr/notes-09-hmm.pdf
== Описание алгоритма==
Пусть <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>.
'''Исходные данные: '''<tex> \lambda = (A, B, \pi)</tex> со случайными начальными условиями.
Алгоритм итеративно обновляет параметр <tex>\lambda</tex> до схождения в одной точке.
'''Прямая процедура'''
<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)</tex> можно вычислить рекурсивно:
1.<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>.
== Псевдокод ==
== Применение ==
== Источники ==
1. https://ru.wikipedia.org/wiki/Алгоритм_Баума_-_Велша
2. http://logic.pdmi.ras.ru/~sergey/teaching/asr/notes-09-hmm.pdf
