Скрытые Марковские модели

Определение:

Скрытая Марковская модель — модель процесса, в которой процесс считается Марковским, причем неизвестно, в каком состоянии [math]s_i[/math] находится система (состояния скрыты), но каждое состояние [math]s_i[/math] может с некоторой вероятностью [math]b_{io_j}[/math] произвести событие [math]o_j[/math], которое можно наблюдать.

Модель представляет из себя марковскую цепь, для которой нам известны начальная вероятность и матрица вероятностей переходов. Скрытой она называется потому, что мы не имеем информации о ее текущем состоянии. Мы получаем информацию на основе некоторого наблюдения, в рассмотренном ниже алгоритме мы будем использовать просто натуральное число от 1 до [math]N[/math], как индекс наблюдаемого события. Для каждого состояния скрытой марковской модели задан вектор вероятности эмиссии, который характеризует вероятность наблюдения каждого события, когда модель находится в этом состоянии. Совокупность таких векторов образует матрицу эмиссии.

Марковская модель [math]\lambda[/math] задается как [math]\lambda = \{S, \Omega, \Pi, A, B\}[/math], где [math]S = \{s_1, ..., s_n\}[/math] — состояния, [math]\Omega = \{\omega_1, ..., \omega_m\}[/math] — возможные события, [math]\Pi = \{\pi_1, ..., \pi_n\}[/math] — начальные вероятности, [math]A = \{a_{ij}\}[/math] — матрица переходов, а [math]B = \{b_{i\omega_k}\}[/math] — вероятность наблюдения события [math]\omega_k[/math] после перехода в состояние [math]s_i[/math].

Пример

Пример СММ

Рассмотрим пример скрытой марковской модели. У Деда Мороза есть три мешка с подарками в разноцветной упаковке: красной, синей, зеленой и фиолетовой. Ночью Дед Мороз пробирается в квартиру и тайком выкладывает подарки под елкой в ряд, доставая по одному подарку из мешка. Наутро мы обнаруживаем упорядоченную последовательность из пяти подарков и хотим сделать наилучшее предположение о последовательности мешков, из которых он доставал эти подарки. Дед Мороз с мешками — скрытая марковская модель. При этом 4 цвета — пространство из [math]M[/math] возможных событий, 3 мешка — количество состояний [math]N[/math], 5 подарков — наши [math]K[/math] наблюдений, каждое из которых представлено цифрой — номером цвета — от 1 до 5. Мы знаем, каковы вероятности того, что Дед Мороз начнет доставать подарки из мешка с номером [math]i[/math] — вектор [math]\pi[i][/math]. Мы также знаем матрицу переходов [math]A[/math], какова вероятность того, что от мешка с номером [math]i[/math] Дед Мороз переходит к мешку с номером [math]j[/math]. Мешки Деда Мороза бесконечны, но мы точно знаем, каково соотношение цветов подарков в каждом мешке ему загрузили на заводе в Великом Устюге. Это матрица вероятностей эмиссии [math]B[/math].

Алгоритмы на СММ

• Алгоритм Витерби — делает наилучшее предположение о последовательности состояний скрытой модели на основе последовательности наблюдений.
• Алгоритм "Вперед-Назад" — находит вероятность попадания в состояние [math]s_n[/math] на [math]t[/math]-ом шаге.
• Алгоритм Баума-Вэлша — меняет [math]a_{ij}[/math], максимизируя вероятность наблюдения последовательности событий [math]O[/math].

Ссылки

• Wikipedia - Hidden Markov model
• Introduction in Hidden Markov models
• A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition