Скрытая марковская модель

• Разделы:
  • Структура скрытой марковской модели
  • Базовые алгоритмы
  • Примечания
  • Ссылки

Скрытая марковская модель (СММ) — статистическая модель, имитирующая работу процесса, похожего на марковский процесс с неизвестными параметрами, и задачей ставится разгадывание неизвестных параметров на основе наблюдаемых. Полученные параметры могут быть использованы в дальнейшем анализе, например, для распознавания образов. СММ может быть рассмотрена как простейшая Байесовская сеть доверия.

Диаграмма переходов в скрытой марковской модели (пример)
x — скрытые состояния
y — наблюдаемые результаты
a — вероятности переходов
b — вероятность результата

Основное применение СММ получили в области распознавания речи, письма, движений и биоинформатике. Кроме того, СММ применяются в криптоанализе, машинном переводе.

Содержание

• 1 Конкретный пример
• 2 Структура скрытой марковской модели
• 3 Базовые алгоритмы
• 4 Примечания
• 5 Ссылки

Конкретный пример

Представим двух друзей, обсуждающих каждый вечер по телефону, что они сегодня делали днём. Ваш друг может делать лишь три вещи: гулять в парке, ходить за покупками или убираться в комнате. Его выбор основывается лишь на погоде, которая была в момент принятия решения. Вы ничего не знаете о погоде в том регионе, где живёт ваш друг, но вы можете, основываясь на его решениях, попытаться предугадать, какая погода была.

Погода представима в виде марковской цепи, она имеет два состояния: солнечно или дождливо, но вы не можете сами увидеть её, поэтому она скрыта от вас. Каждый день ваш друг принимает одно из трёх возможных решений: прогулка, покупки или уборка. Вы можете узнать о решении вашего друга, поэтому это наблюдаемое значение. В целом мы получаем СММ.

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

В обычной Марковской модели состояние видимо наблюдателю, поэтому вероятности переходов — единственный параметр. В скрытой марковской модели мы можем следить лишь за переменными, на которые оказывает влияние данное состояние. Каждое состояние имеет вероятностное распределение среди всех возможных выходных значений. Поэтому последовательность символов, сгенерированная СММ, даёт и
нформацию о последовательности состояний.

Диаграмма, представленная ниже, показывает общую структуру СММ. Овалы представляют собой переменные со случайным значением. Случайная переменная x(t){displaystyle x(t)}

  представляет собой значение скрытой переменной в момент времени t{displaystyle t} . Случайная переменная y(t){displaystyle y(t)}  — это значение наблюдаемой переменной в момент времени t{displaystyle t} . Стрелки на диаграмме символизируют условные зависимости.

Из диаграммы становится ясно, что значение скрытой переменной x(t){displaystyle x(t)}

  (в момент времени t{displaystyle t} ) зависит только от значения скрытой переменной x(t−1){displaystyle x(t-1)}  (в момент t−1{displaystyle t-1} ). Это называется свойством Маркова. Хотя в то же время значение наблюдаемой переменной y(t){displaystyle y(t)}  зависит только от значения скрытой переменной x(t){displaystyle x(t)}  (обе в момент времени t{displaystyle t} ). 

Вероятность увидеть последовательность Y=y(0),y(1),…,y(L−1){displaystyle Y=y(0),y(1),dots ,y(L-1)}

  длины L{displaystyle L}  равна

P(Y)=∑XP(Y∣X)P(X),{displaystyle P(Y)=sum _{X}P(Ymid X)P(X),} 

здесь сумма пробегает по всем возможным последовательностям скрытых узлов X=x(0),x(1),…,x(L−1).{displaystyle X=x(0),x(1),dots ,x(L-1).,}

  Метод подсчёта полным перебором значений P(Y){displaystyle P(Y)}  — очень трудоёмкий для многих задач из реальной жизни в силу того, что количество возможных последовательностей скрытых узлов очень велико. Но применение процедуры вперёд-назад [1] позволяет существенно увеличить скорость вычислений.

Базовые алгоритмы

Существуют три основных задачи, связанные с СММ:

• даны параметры модели и последовательность, требуется вычислить вероятность появления данной последовательности (задача решается с помощью алгоритма вперёд-назад),
• даны параметры модели, требуется определить наиболее подходящую последовательность скрытых узлов, наиболее точно описывающую данную модель (алгоритм Витерби помогает при решении данной задачи),
• дана выходная последовательность (или несколько), требуется
  «потренировать» СММ на данном выходе (в этом помогает алгоритм Баума-Уэлша).

Примечания

1. ↑ Rabiner, p. 262

Ссылки

• Скрытые Марковские Модели
• Сергей Николенко. Лекции № 6 и № 7 (слайды), посвящённые скрытым марковским моделям, из курса «Вероятностное обучение»