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

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

Основные компоненты

Скрытая марковская модель формально определяется как кортеж из пяти элементов:

• Множество скрытых состояний \( S = \{s_1, s_2, \dots, s_N\} \) — конечный набор ненаблюдаемых состояний, в которых может находиться система в каждый момент времени.
• Множество наблюдаемых символов \( V = \{v_1, v_2, \dots, v_M\} \) — конечный набор возможных выходных данных (наблюдений), которые могут быть сгенерированы моделью.
• Матрица вероятностей переходов \( A = \{a_{ij}\} \), где \( a_{ij} = P(q_t = s_j \mid q_{t-1} = s_i) \) — вероятность перехода из состояния \( s_i \) в состояние \( s_j \) за один шаг времени.
• Матрица вероятностей эмиссии \( B = \{b_j(k)\} \), где \( b_j(k) = P(o_t = v_k \mid q_t = s_j) \) — вероятность наблюдения символа \( v_k \) в состоянии \( s_j \).
• Вектор начальных вероятностей \( \pi = \{\pi_i\} \), где \( \pi_i = P(q_1 = s_i) \) — вероятность того, что система в начальный момент времени находится в состоянии \( s_i \).

Модель предполагает выполнение марковского свойства первого порядка: вероятность перехода в следующее состояние зависит только от текущего состояния, а не от всей последовательности предыдущих состояний. Кроме того, предполагается, что наблюдения в момент времени \( t \) зависят только от состояния в этот же момент времени.

История

Идеи, лежащие в основе скрытых марковских моделей, восходят к работам Андрея Андреевича Маркова (старшего), который в начале XX века разработал теорию марковских цепей. Однако формальное введение СММ в современном виде произошло в 1960-х годах. В 1966 году Леонард Баум и его коллеги опубликовали серию статей, в которых были заложены основы теории скрытых марковских моделей, включая алгоритмы оценивания параметров (алгоритм Баума — Уэлча). В 1970-х годах Джеймс Бейкер и Фредерик Джелинек независимо друг от друга применили СММ к задаче распознавания речи, что стало ключевым прорывом в этой области. В 1980-х годах модели получили широкое распространение в биоинформатике, в частности для поиска генов и предсказания структуры белков.

Основные алгоритмы

Для работы со скрытыми марковскими моделями используются три фундаментальные задачи, каждая из которых решается своим алгоритмом:

Задача оценки (оценивание вероятности)

Дана модель \( \lambda = (A, B, \pi) \) и последовательность наблюдений \( O = (o_1, o_2, \dots, o_T) \). Требуется вычислить вероятность \( P(O \mid \lambda) \) того, что данная последовательность могла быть сгенерирована моделью. Эта задача решается с помощью прямого алгоритма (forward algorithm) или обратного алгоритма (backward algorithm), которые используют динамическое программирование для избежания экспоненциального перебора всех возможных последовательностей состояний.

Задача декодирования (нахождение оптимальной последовательности состояний)

Дана модель \( \lambda \) и последовательность наблюдений \( O \). Требуется найти наиболее вероятную последовательность скрытых состояний \( Q = (q_1, q_2, \dots, q_T) \), которая могла породить эту последовательность. Наиболее распространённым методом является алгоритм Витерби (Viterbi algorithm), который также основан на динамическом программировании и находит путь с максимальной вероятностью через решётку состояний.

Задача обучения (оценивание параметров модели)

Дана последовательность наблюдений \( O \) (или набор последовательностей). Требуется подобрать параметры модели \( \lambda = (A, B, \pi) \) так, чтобы максимизировать вероятность \( P(O \mid \lambda) \). Эта задача решается с помощью алгоритма Баума — Уэлча (Baum-Welch algorithm), который является частным случаем EM-алгоритма (Expectation-Maximization). Алгоритм итеративно пересчитывает параметры модели, сходясь к локальному максимуму функции правдоподобия.

Применение

Скрытые марковские модели нашли применение в самых разных областях науки и техники.

Распознавание речи

В системах автоматического распознавания речи СММ долгое время были доминирующим подходом. Каждое фонетическое состояние (например, начало, середина и конец фонемы) моделируется как скрытое состояние, а акустические признаки (спектрограммы, мел-кепстральные коэффициенты) — как наблюдаемые символы. Модель позволяет учитывать временную вариативность речи: разную длительность произнесения звуков разными дикторами.

Обработка естественного языка

В лингвистике СММ применяются для задач тегирования частей речи (part-of-speech tagging), сегментации текста, распознавания именованных сущностей и машинного перевода. Скрытыми состояниями в таких задачах часто являются грамматические категории, а наблюдаемыми — слова текста. Например, в задаче тегирования модель оценивает вероятность того, что данное слово является существительным, глаголом или прилагательным, исходя из контекста.

Биоинформатика

В биологии СММ используются для анализа последовательностей ДНК, РНК и белков. Модели помогают находить гены, предсказывать функциональные участки (экзоны, интроны, промоторы), выравнивать множественные последовательности и классифицировать белки по семействам. Например, профильные скрытые марковские модели (profile HMM) широко применяются в базах данных Pfam для аннотации белковых доменов.

Финансы и экономика

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

Робототехника и навигация

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

Разновидности и обобщения

Существует несколько модификаций классической скрытой марковской модели:

• СММ с непрерывными наблюдениями — вместо дискретного множества символов \( V \) используются непрерывные распределения (например, гауссовы смеси) для моделирования вероятностей эмиссии.
• СММ с авторегрессией — наблюдения в момент времени \( t \) зависят не только от текущего состояния, но и от предыдущих наблюдений.
• Скрытые полумарковские модели (HSMM) — обобщение, в котором время пребывания в каждом состоянии моделируется явно, а не через вероятности переходов, что позволяет учитывать разную длительность состояний.
• Иерархические скрытые марковские модели — модели, в которых скрытые состояния сами являются СММ, что позволяет описывать сложные структуры данных.

Преимущества и недостатки

Преимущества:

• Хорошая математическая основа с эффективными алгоритмами обучения и декодирования.
• Способность моделировать временные зависимости и последовательности переменной длины.
• Относительная простота реализации и интерпретации.

Недостатки:

• Предположение о марковском свойстве первого порядка часто является упрощением, не отражающим долгосрочные зависимости.
• Чувствительность к выбору начальных параметров (алгоритм Баума — Уэлча может сходиться к локальному оптимуму).
• Трудности при работе с большими наборами данных из-за вычислительной сложности (особенно для задач с большим числом состояний).

Сравнение с альтернативными методами

В конце 2010-х — начале 2020-х годов скрытые марковские модели во многих приложениях были вытеснены методами глубокого обучения, в частности рекуррентными нейронными сетями (LSTM, GRU) и трансформерами. Однако СММ сохраняют актуальность в задачах, где важна интерпретируемость модели, малый объём обучающих данных или необходимость работы с дискретными последовательностями. В некоторых областях, таких как биоинформатика, СММ остаются стандартным инструментом благодаря своей прозрачности и эффективности.

Источники

• Rabiner, L. R. (1989). «A tutorial on hidden Markov models and selected applications in speech recognition». Proceedings of the IEEE, 77(2), 257–286.
• Baum, L. E., Petrie, T. (1966). «Statistical inference for probabilistic functions of finite state Markov chains». The Annals of Mathematical Statistics, 37(6), 1554–1563.
• Durbin, R., Eddy, S., Krogh, A., Mitchison, G. (1998). Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press.
• Jelinek, F. (1997). Statistical Methods for Speech Recognition. MIT Press.
• Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer.