Hidden Markov Model (HMM)

Скрытая марковская модель (HMM) — это вероятностная модель последовательности, в которой система переходит между состояниями, которые нельзя наблюдать напрямую, причем каждое скрытое состояние порождает наблюдаемое событие. По последовательности наблюдений, например аудиокадрам или буквам ДНК, HMM вычисляет вероятность каждой последовательности скрытых состояний — например, фонем, соответствующих аудио, или участков генов, соответствующих буквам. «Марковская» указывает на ключевое предположение модели: следующее состояние зависит только от текущего. Леонард Баум и его коллеги разработали эту теорию в конце 1960-х годов; затем HMM десятилетиями лежали в основе распознавания речи. Полностью основанные на явных вероятностях, сегодня они остаются стандартным инструментом анализа временных рядов и биоинформатики и классическим примером статистического ИИ.

Компоненты HMM#

HMM с N скрытыми состояниями задается тремя наборами вероятностей:

• Начальные вероятности (π): Вероятность начать в каждом скрытом состоянии.
• Вероятности переходов (A): Матрица N × N, элемент A[i, j] которой задает вероятность перехода из состояния i в состояние j за один шаг; таким образом, скрытые состояния образуют марковскую цепь.
• Вероятности эмиссии (B): Вероятность каждого наблюдения при текущем состоянии. Для дискретных наблюдений используется таблица, а для непрерывных, например акустических признаков, — распределения, такие как гауссовы смеси.

Два предположения делают модель вычислительно удобной: каждое состояние зависит только от предыдущего, а каждое наблюдение — только от текущего состояния. Развернутая во времени модель представляет собой цепочку скрытых состояний, каждое из которых порождает одно наблюдение:

Три классические задачи HMM#

В широко цитируемом учебном пособии Лоуренса Рабинера 1989 года применение HMM описано через три вопроса. Для каждого существует решение с помощью динамического программирования, вычислительная сложность которого растет как N² × T для T наблюдений, а не как число Nᵀ возможных последовательностей состояний:

• Оценивание: Насколько вероятна последовательность наблюдений для заданной модели? Алгоритм прямого прохода суммирует вероятности по всем скрытым путям; так система распознавания выбирает модель слова, лучше всего объясняющую произнесенную фразу.
• Декодирование: Какая последовательность скрытых состояний лучше всего объясняет наблюдения? Алгоритм Витерби, опубликованный Эндрю Витерби в 1967 году для декодирования сверточных кодов, находит наиболее вероятный путь, а алгоритм прямого и обратного прохода вычисляет вероятность каждого состояния на каждом временном шаге.
• Обучение: Какие параметры лучше всего соответствуют набору последовательностей наблюдений? Алгоритм Баума — Уэлча, представляющий собой вариант алгоритма максимизации ожидания, оценивает π, A и B по неразмеченным последовательностям. Если последовательности состояний размечены, достаточно подсчитать переходы и эмиссии.

Декодирование Витерби можно реализовать всего в несколько строк NumPy. В этой модели скрыта активность человека — ходьба или бег, трекер сообщает одно значение скорости для каждого кадра, а активность обычно сохраняется от кадра к кадру:

import numpy as np

states = ["walk", "run"]
start = np.array([0.8, 0.2])  # начальные вероятности состояний
trans = np.array([[0.9, 0.1], [0.1, 0.9]])  # активность обычно сохраняется между кадрами
emit = np.array([[0.7, 0.25, 0.05], [0.1, 0.3, 0.6]])  # P(скорость | состояние) для низкой, средней и высокой скорости
obs = [0, 0, 2, 0, 0, 1, 2, 2, 1, 2]  # значения скорости для каждого кадра

# Витерби: наилучшая логарифмическая вероятность достижения каждого состояния и указатели на предыдущие состояния
logp = np.log(start) + np.log(emit[:, obs[0]])
back = []
for o in obs[1:]:
    scores = logp[:, None] + np.log(trans)  # строки: предыдущее состояние, столбцы: следующее состояние
    back.append(scores.argmax(axis=0))
    logp = scores.max(axis=0) + np.log(emit[:, o])

# Восстановить наиболее вероятную последовательность состояний в обратном порядке, начиная с наилучшего конечного состояния
path = [int(logp.argmax())]
for pointers in reversed(back):
    path.insert(0, int(pointers[path[0]]))
print("Speeds: ", " ".join(["slow", "medium", "fast"][o] for o in obs))
print("Decoded:", " ".join(states[s] for s in path))

Алгоритм декодирует walk walk walk walk walk run run run run run. Высокое значение скорости в кадре 3 остается помеченным как «ходьба», поскольку переход к бегу и обратно потребовал бы двух маловероятных переходов; средние значения в кадрах 6 и 9 становятся «бегом» из-за окружающих их кадров с высокой скоростью. Классификатор для отдельных кадров, не учитывающий переходы, пометил бы кадр 3 как бег.

HMM и родственные модели#

• Фильтр Калмана: Выполняет ту же рекурсивную процедуру предсказания и обновления для непрерывных состояний с линейной динамикой и гауссовским шумом. Алгоритм прямого прохода HMM — его аналог для дискретных состояний.
• Байесовские сети: HMM — это простейшая динамическая байесовская сеть с одной скрытой и одной наблюдаемой переменной на временной шаг.
• Марковский процесс принятия решений (MDP): Дополняет марковскую цепь с наблюдаемыми состояниями действиями и вознаграждениями; эта схема лежит в основе обучения с подкреплением.
• Рекуррентные нейронные сети и трансформеры: Обучаются выявлять долгосрочные нелинейные зависимости на больших наборах данных и вытеснили HMM в большинстве задач распознавания речи и обработки языка. HMM требуют гораздо меньше данных, а все их вероятности можно прочитать напрямую.
• Модели пространства состояний (SSM): Слои глубокого обучения, такие как Mamba, используют идею пространства состояний из теории управления и обновляют непрерывный скрытый вектор с помощью обучаемой детерминированной динамики.

Примеры применения в реальных условиях#

• Распознавание речи: С 1980-х до начала 2010-х годов большинство систем распознавания моделировали каждую фонему небольшой HMM с гауссовыми смесями в качестве эмиссий. Затем в гибридных системах модель эмиссий заменили глубокие нейронные сети, а позднее сквозные модели полностью заменили HMM.
• Биоинформатика: Профильные HMM описывают семейства родственных белковых последовательностей или последовательностей ДНК. HMMER использует их для поиска отдаленных родственников в базах последовательностей и лежит в основе базы данных семейств белков Pfam; кроме того, с помощью HMM программы поиска генов помечают участки генома как кодирующие или некодирующие.
• Разметка частей речи: В ранней статистической обработке естественного языка слова размечали как существительные, глаголы и другие части речи, применяя декодирование Витерби к последовательностям меток.
• Распознавание активности: Последовательности поз тела или показаний носимых датчиков декодируются в такие действия, как стояние, ходьба или падение. Решение Ultralytics для мониторинга тренировок отслеживает такую последовательность из двух состояний: для каждого человека определяется положение «вверху» или «внизу» по углу сустава, вычисленному по ключевым точкам оценки позы YOLO26; по умолчанию используется локоть, переход в «вверху» происходит при угле больше 145°, а в «внизу» — при угле меньше 90°. Повторение засчитывается при каждом переходе из положения «вверху» в «внизу».