Скрытые марковские модели (HMM): Математика распознавания речи и текста

Классический пример для понимания HMM: представьте, что ваш друг живет в другом городе и каждый день звонит вам, рассказывая, чем он занимался (гулял, ходил в магазин, убирался дома). Вы не знаете, какая там погода (Скрытое состояние), но вы знаете вероятности: в солнечный день он гуляет с вероятностью 80%, а в дождливый день он убирается дома с вероятностью 60%. Задача алгоритма — по последовательности его действий (Наблюдаемые выбросы) с математической точностью угадать последовательность погоды.

Скрытая марковская модель полностью описывается тремя матрицами (вероятности начальных состояний, вероятности переходов между скрытыми состояниями и вероятности выбросов). Анализ HMM сводится к решению трех фундаментальных математических задач:

1. Задача оценки (Forward-Backward algorithm). По заданной модели рассчитать вероятность того, что мы увидим именно такую последовательность наблюдений. Применяется для фильтрации спама и детектирования аномалий в сети.
2. Задача декодирования (Алгоритм Витерби). Дана последовательность наблюдений. Нужно найти наиболее вероятную последовательность скрытых состояний, которая привела к этим наблюдениям. Алгоритм Витерби (Viterbi algorithm) — это метод динамического программирования, который находит оптимальный путь в решетке вероятностей (треллис) за линейное время, отбрасывая маловероятные ветви.
3. Задача обучения (Алгоритм Баума-Уэлша). Даны только наблюдения, а параметры самой модели неизвестны. Алгоритм, являющийся частным случаем EM-алгоритма (Expectation-Maximization), итеративно подбирает такие матрицы вероятностей, которые наилучшим образом объясняют увиденные данные.

До эпохи глубоких нейронных сетей (Deep Learning) Скрытые марковские модели были абсолютными монополистами в технологиях распознавания человеческой речи (где скрытые состояния — это фонемы или слова, а наблюдения — это частотные характеристики аудиосигнала). Сегодня HMM продолжают активно применяться в биоинформатике для поиска генов (где скрытые состояния — это кодирующие и некодирующие участки ДНК, а наблюдения — это нуклеотиды A, C, G, T), а также в задачах морфологической разметки текста (Part-of-Speech tagging) при создании поисковых систем.