Скрытые Марковские модели — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример)
Строка 12: Строка 12:
 
Рассмотрим пример скрытой марковской модели. У Деда Мороза есть три мешка с подарками в разноцветной упаковке: красной, синей, зеленой и фиолетовой. Ночью Дед Мороз  пробирается в квартиру и тайком  выкладывает подарки под елкой в ряд, доставая по одному подарку из мешка. Наутро мы обнаруживаем упорядоченную последовательность из пяти подарков и хотим сделать наилучшее предположение о последовательности мешков, из которых он доставал эти подарки.  
 
Рассмотрим пример скрытой марковской модели. У Деда Мороза есть три мешка с подарками в разноцветной упаковке: красной, синей, зеленой и фиолетовой. Ночью Дед Мороз  пробирается в квартиру и тайком  выкладывает подарки под елкой в ряд, доставая по одному подарку из мешка. Наутро мы обнаруживаем упорядоченную последовательность из пяти подарков и хотим сделать наилучшее предположение о последовательности мешков, из которых он доставал эти подарки.  
 
Дед Мороз с мешками {{---}} скрытая марковская модель. При этом 4 цвета {{---}} пространство из <tex>M</tex> возможных событий, 3 мешка {{---}} количество состояний <tex>N</tex>, 5 подарков {{---}} наши <tex>K</tex> наблюдений, каждое из которых представлено цифрой {{---}} номером цвета {{---}} от 1 до 5. Мы знаем, каковы вероятности того, что Дед Мороз начнет доставать подарки из мешка с номером <tex>i</tex> {{---}} вектор <tex>\pi[i]</tex>. Мы также знаем матрицу переходов <tex>A</tex>, какова вероятность того, что от мешка с номером <tex>i</tex> Дед Мороз переходит к мешку с номером <tex>j</tex>. Мешки Деда Мороза бесконечны, но мы точно знаем, каково соотношение цветов подарков в каждом мешке ему загрузили на заводе в Великом Устюге. Это матрица вероятностей эмиссии <tex>B</tex>.
 
Дед Мороз с мешками {{---}} скрытая марковская модель. При этом 4 цвета {{---}} пространство из <tex>M</tex> возможных событий, 3 мешка {{---}} количество состояний <tex>N</tex>, 5 подарков {{---}} наши <tex>K</tex> наблюдений, каждое из которых представлено цифрой {{---}} номером цвета {{---}} от 1 до 5. Мы знаем, каковы вероятности того, что Дед Мороз начнет доставать подарки из мешка с номером <tex>i</tex> {{---}} вектор <tex>\pi[i]</tex>. Мы также знаем матрицу переходов <tex>A</tex>, какова вероятность того, что от мешка с номером <tex>i</tex> Дед Мороз переходит к мешку с номером <tex>j</tex>. Мешки Деда Мороза бесконечны, но мы точно знаем, каково соотношение цветов подарков в каждом мешке ему загрузили на заводе в Великом Устюге. Это матрица вероятностей эмиссии <tex>B</tex>.
 +
 +
== Алгоритмы на СММ ==
 +
* [[Алгоритм Витерби]] {{---}} делает наилучшее предположение о последовательности состояний скрытой модели на основе последовательности наблюдений.
 +
* [[Алгоритм "Вперед-Назад"]] {{---}} находит вероятность попадания в состояние <tex>s_n</tex> на <tex>t</tex>-ом шаге.
 +
* [http://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm Алгоритм Баума-Вэлша] {{---}} меняет <tex>a_{ij}</tex>, максимизируя вероятность наблюдения последовательности событий <tex>O</tex>.

Версия 14:45, 14 января 2013

Определение:
Скрытая Марковская модель — модель процесса, в которой процесс считается Марковским, причем неизвестно, в каком состоянии [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].