Скрытые марковские модели (HMM): распознавание образов и алгоритм Витерби

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

В теории HMM выделяют три фундаментальные аналитические задачи. Первая задача (задача оценки) заключается в вычислении вероятности того, что заданная последовательность наблюдений вообще могла быть сгенерирована конкретной моделью. Прямой комбинаторный перебор всех возможных траекторий скрытых состояний требует экспоненциального времени, что делает его невыполнимым даже для коротких последовательностей. Эта проблема элегантно решается с помощью алгоритма прямого хода (Forward Algorithm), который использует динамическое программирование для рекурсивного накопления вероятностей на каждом шаге, снижая вычислительную сложность с экспоненциальной до полиномиальной, что позволяет процессорам обрабатывать данные в режиме реального времени.

Вторая и самая знаменитая задача HMM — это задача декодирования. Суть ее сводится к поиску наиболее вероятной последовательности скрытых состояний, которая привела к появлению данных наблюдений. Именно эта задача решается всемирно известным алгоритмом Витерби (Viterbi Algorithm), созданным Эндрю Витерби в 1967 году. Алгоритм Витерби строит в памяти компьютера решетку (Trellis) и на каждом временном шаге вычисляет максимальную вероятность достижения каждого состояния, запоминая при этом наилучший путь (обратную ссылку), который привел к этому максимуму. Когда алгоритм доходит до конца последовательности, он просто разматывает клубок обратных ссылок, безошибочно реконструируя скрытую траекторию. В распознавании речи именно этот алгоритм превращает набор звуковых частот в осмысленный текст, догадываясь о скрытых произнесенных фонемах.

Третья задача HMM — задача обучения (или настройки параметров). Если у нас есть гигабайты исторических данных (наблюдений), но мы не знаем ни вероятностей переходов, ни вероятностей эмиссий, как построить саму модель? Для этого используется алгоритм Баума-Велша (частный случай EM-алгоритма: Expectation-Maximization). Это итерационный процесс, который начинает со случайных параметров модели. На шаге E (ожидание) алгоритм вычисляет ожидаемое количество переходов между состояниями на основе текущих данных. На шаге M (максимизация) алгоритм обновляет матрицы вероятностей так, чтобы они лучше соответствовали этим ожиданиям. Процесс повторяется до сходимости, автоматически подстраивая HMM под структуру данных. Этот самообучающийся механизм позволил биологам успешно использовать HMM для поиска генов в структурах ДНК, а финансистам — для выявления скрытых режимов волатильности на фондовых рынках.