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

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

Основные понятия и формальное определение

Скрытая марковская модель описывается набором параметров, которые определяют её структуру и поведение. Формально модель задаётся как λ = (A, B, π), где:

• Скрытые состояния (S): конечное множество N состояний, которые не наблюдаются напрямую. Состояния обозначаются как S = {s₁, s₂, ..., sₙ}. Система в каждый момент времени t находится в одном из этих состояний qₜ ∈ S.
• Наблюдаемые символы (V): конечное множество M возможных наблюдений, которые генерируются моделью. Наблюдения обозначаются как V = {v₁, v₂, ..., vₘ}. В момент времени t система генерирует наблюдение oₜ ∈ V.
• Матрица вероятностей переходов (A): квадратная матрица размера N×N, где каждый элемент aᵢⱼ = P(qₜ₊₁ = sⱼ | qₜ = sᵢ) представляет собой вероятность перехода из состояния sᵢ в состояние sⱼ за один шаг. Сумма вероятностей переходов из любого состояния равна 1: Σⱼ aᵢⱼ = 1.
• Матрица вероятностей наблюдений (B): матрица размера N×M, где каждый элемент bⱼ(k) = P(oₜ = vₖ | qₜ = sⱼ) представляет собой вероятность генерации символа vₖ в состоянии sⱼ. Сумма вероятностей для каждого состояния равна 1: Σₖ bⱼ(k) = 1.
• Вектор начальных вероятностей (π): вектор длины N, где πᵢ = P(q₁ = sᵢ) — вероятность того, что в начальный момент времени t=1 система находится в состоянии sᵢ. Сумма всех πᵢ равна 1.

Модель называется «скрытой», потому что наблюдатель видит только последовательность символов O = (o₁, o₂, ..., oₜ), но не знает, в каких состояниях Q = (q₁, q₂, ..., qₜ) находилась система при их генерации. Последовательность состояний является скрытой.

Основные предположения

Работа СММ основана на двух ключевых допущениях:

1. Марковское свойство (допущение о первом порядке): вероятность перехода в следующее состояние зависит только от текущего состояния, а не от всей предыдущей последовательности состояний. Формально: P(qₜ₊₁ | qₜ, qₜ₋₁, ..., q₁) = P(qₜ₊₁ | qₜ).
2. Допущение о независимости наблюдений: вероятность наблюдения в момент времени t зависит только от состояния в этот же момент времени и не зависит от других наблюдений или состояний. Формально: P(oₜ | qₜ, qₜ₋₁, ..., q₁, oₜ₋₁, ..., o₁) = P(oₜ | qₜ).

Три основные задачи СММ

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

Задача оценки (Evaluation)

Постановка: Дана модель λ = (A, B, π) и последовательность наблюдений O = (o₁, o₂, ..., oₜ). Требуется вычислить вероятность P(O | λ) того, что данная последовательность наблюдений была сгенерирована этой моделью. Решение: Для решения задачи оценки используется алгоритм «прямого-обратного хода» (Forward-Backward algorithm). Прямой алгоритм вычисляет вероятность нахождения в каждом состоянии на каждом шаге с учётом уже увиденных наблюдений. Обратный алгоритм — вероятность нахождения в состоянии с учётом будущих наблюдений. Комбинация этих вероятностей даёт P(O | λ). Применение: Эта задача позволяет выбрать модель, которая лучше всего объясняет наблюдаемые данные (например, распознавание речи: какая фонетическая модель с наибольшей вероятностью породила данный звуковой сигнал).

Задача декодирования (Decoding)

Постановка: Дана модель λ = (A, B, π) и последовательность наблюдений O = (o₁, o₂, ..., oₜ). Требуется найти наиболее вероятную последовательность скрытых состояний Q = (q₁, q₂, ..., qₜ), которая могла породить данную последовательность наблюдений. Решение: Для решения задачи декодирования используется алгоритм Витерби (Viterbi algorithm). Это алгоритм динамического программирования, который находит путь с максимальной вероятностью в графе состояний. Он рекурсивно вычисляет вероятность наиболее вероятного пути, заканчивающегося в каждом состоянии на каждом шаге, и запоминает, откуда этот путь пришёл. Применение: Эта задача используется для восстановления скрытой структуры, например, для определения последовательности фонем по звуковому сигналу (распознавание речи) или для определения наиболее вероятной последовательности состояний погоды по последовательности наблюдений (например, «мокрая трава», «сухо»).

Задача обучения (Learning)

Постановка: Дана последовательность наблюдений O = (o₁, o₂, ..., oₜ) (или несколько таких последовательностей). Требуется подобрать параметры модели λ = (A, B, π) так, чтобы максимизировать вероятность P(O | λ). Решение: Основным методом решения задачи обучения является алгоритм Баума-Уэлча (Baum-Welch algorithm), который является частным случаем EM-алгоритма (Expectation-Maximization). Алгоритм итеративно уточняет параметры модели:

1. E-шаг (Expectation): Используя текущие параметры модели, вычисляются ожидаемые значения скрытых переменных (вероятности нахождения в каждом состоянии в каждый момент времени и вероятности переходов между состояниями). Для этого применяется алгоритм прямого-обратного хода.
2. M-шаг (Maximization): На основе полученных ожидаемых значений пересчитываются параметры модели (A, B, π) таким образом, чтобы максимизировать правдоподобие данных.

Применение: Эта задача является ключевой для создания моделей на основе обучающих данных. Например, для обучения модели распознавания речи на большом корпусе звуковых записей с транскрипциями.

История развития

Основы теории скрытых марковских моделей были заложены в 1960-х годах. В 1966 году Леонард Баум и его коллеги опубликовали серию работ, в которых описали алгоритм, ныне известный как алгоритм Баума-Уэлча, для оценки параметров вероятностных функций от цепей Маркова. В 1967 году Эндрю Витерби разработал алгоритм декодирования, который позже был назван его именем.

Первоначально СММ использовались в основном в области распознавания речи. В 1970-х и 1980-х годах исследователи из IBM и других организаций (например, Фредерик Джелинек, Джеймс Бейкер) применили их для создания первых систем непрерывного распознавания речи. В 1980-х годах СММ стали доминирующим подходом в этой области, вытеснив более ранние методы, такие как динамическое программирование.

В 1990-х годах СММ нашли широкое применение в биоинформатике, в частности для поиска генов, предсказания белковых структур и выравнивания последовательностей. В 2000-х годах они активно использовались в обработке естественного языка (POS-теггинг, распознавание именованных сущностей) и компьютерном зрении (распознавание жестов, действий).

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

Применение

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

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

В классических системах распознавания речи СММ используются для моделирования фонем. Каждая фонема представляется как последовательность из нескольких состояний (обычно 3-5). Наблюдениями являются акустические признаки (например, MFCC-коэффициенты). Обученная модель позволяет по последовательности акустических признаков найти наиболее вероятную последовательность фонем, а затем и слов.

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

В биоинформатике СММ применяются для:

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

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

В NLP СММ применяются для:

• Частеречной разметки (POS-tagging): Скрытые состояния — это части речи (существительное, глагол, прилагательное), а наблюдения — слова. Модель позволяет определить наиболее вероятную часть речи для каждого слова в предложении.
• Распознавания именованных сущностей (NER): Скрытые состояния — это типы сущностей (имя, организация, место), а наблюдения — слова.

Компьютерное зрение

В компьютерном зрении СММ используются для:

• Распознавания жестов: Последовательность кадров видео анализируется, и модель определяет, какой жест был выполнен.
• Распознавания действий: Моделирование последовательности поз человека для определения действия (ходьба, бег, прыжок).
• Анализа текста: Моделирование последовательности штрихов при распознавании рукописного текста.

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

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

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

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

• СММ с непрерывными наблюдениями: Вместо дискретного множества символов используются непрерывные распределения (например, смеси гауссиан) для моделирования наблюдений.
• СММ с авторегрессией: Вероятность наблюдения зависит не только от текущего состояния, но и от предыдущих наблюдений.
• Иерархические СММ: Скрытые состояния могут быть вложенными, что позволяет моделировать сложные структуры.
• СММ с входными данными (Input-Output HMM): Модель, где переходы и наблюдения могут зависеть от внешних факторов.
• Максимально-энтропийные марковские модели (MEMM): Модель, в которой переходы между состояниями моделируются с помощью классификаторов на основе максимальной энтропии, что позволяет учитывать контекстные признаки.

Критика и ограничения

Несмотря на широкое применение, СММ имеют ряд ограничений:

1. Марковское свойство первого порядка: Предположение о том, что будущее зависит только от настоящего, часто является слишком сильным упрощением для реальных данных, где могут быть важны долгосрочные зависимости.
2. Независимость наблюдений: Допущение о независимости наблюдений при заданном состоянии также часто нарушается на практике.
3. Трудность моделирования сложных зависимостей: СММ не могут эффективно моделировать сложные нелинейные зависимости между наблюдениями, которые хорошо обрабатываются нейронными сетями.
4. Чувствительность к начальной инициализации: Алгоритм Баума-Уэлча может сходиться к локальному оптимуму, что требует тщательного выбора начальных параметров.
5. Проблема масштабирования: При большом количестве состояний и наблюдений обучение и декодирование становятся вычислительно затратными.

Источники

• Rabiner, L. R. (1989). A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2), 257-286.
• Durbin, R., Eddy, S. R., Krogh, A., & Mitchison, G. (1998). Biological sequence analysis: probabilistic models of proteins and nucleic acids. Cambridge University Press.
• Manning, C. D., & Schütze, H. (1999). Foundations of statistical natural language processing. MIT Press.
• Bishop, C. M. (2006). Pattern recognition and machine learning. Springer.
• Jelinek, F. (1997). Statistical methods for speech recognition. MIT Press.