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

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

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

Первые заметки о скрытых марковских моделях опубликовал Баум в 1960-х, и уже в 70-х их впервые применили при распознавании речи. С середины 1980-х СММ применяются при анализе биологических последовательностей, в частности ДНК.

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

Пример

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

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

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

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

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

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

Temporal evolution of a hidden Markov model

Вероятность увидеть последовательность $Y=y(0),y(1),\dots ,y(L-1)$ длины $L$ равна

$P(Y)=\sum _{X}P(Y\mid X)P(X),$

здесь сумма пробегает по всем возможным последовательностям скрытых узлов $X=x(0),x(1),\dots ,x(L-1).$ Метод подсчёта полным перебором значений $P(Y)$ — очень трудоёмкий для многих задач из реальной жизни в силу того, что количество возможных последовательностей скрытых узлов очень велико. Но применение процедуры прямого-обратного хода позволяет существенно увеличить скорость вычислений.

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

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

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

См. также

• Теорема Марелье

Ссылки

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