Скрытая марковская модель: устройство и три задачи

Скрытая марковская модель (HMM, hidden Markov model) описывает ситуацию, знакомую любому исследователю: интересующий нас процесс напрямую не виден, а видны лишь его следы. Погода за окном чужого города скрыта, но известно, чем человек занимался; фонема скрыта, а измерен спектр звука; состояние рынка скрыто, а наблюдается доходность. Модель предполагает, что скрытый процесс марковский (следующее состояние зависит только от текущего), а каждое состояние с известными вероятностями порождает наблюдение. Ниже разберём параметры модели, три классические задачи и оба ключевых алгоритма на сквозном числовом примере. Калькулятор под этим абзацем считает тот же пример: подвигайте вероятности и посмотрите, как меняются правдоподобие и восстановленная цепочка состояний.

Что скрыто и что наблюдается

В обычной цепи Маркова состояния видны напрямую. В скрытой марковской модели появляется второй слой: последовательность состояний $q_1, q_2, \dots, q_T$ существует, но недоступна наблюдателю, и вместо неё фиксируется последовательность наблюдений $O = o_1, o_2, \dots, o_T$. Связь между слоями вероятностная: находясь в состоянии $i$, модель выдаёт символ $k$ с вероятностью $b_i(k)$.

Отсюда два независимых предположения, на которых держится вся конструкция:

$$P(q_{t+1} \mid q_t, q_{t-1}, \dots, q_1) = P(q_{t+1} \mid q_t), \qquad P(o_t \mid q_1^T, o_1^{t-1}) = P(o_t \mid q_t)$$

Первое - марковское свойство скрытого слоя, второе - условная независимость наблюдения от всего, кроме текущего состояния. В сквозном примере скрытые состояния это «Солнечно» и «Дождливо», а наблюдения - занятия человека: прогулка, магазин, уборка.

Параметры модели: начальное распределение, A и B

Модель полностью задаётся тройкой $\lambda = (\pi, A, B)$:

• $\pi_i = P(q_1 = i)$ - начальное распределение по состояниям;
• $a_{ij} = P(q_{t+1} = j \mid q_t = i)$ - матрица переходов между скрытыми состояниями;
• $b_i(k) = P(o_t = k \mid q_t = i)$ - матрица эмиссий (наблюдений).

Строки всех трёх объектов нормированы: сумма по $j$ в каждой строке $A$ равна единице, сумма по $k$ в каждой строке $B$ - тоже. Наш пример:

Читается так: солнечный день с вероятностью 0,6 сменится солнечным, а человек в солнечный день с вероятностью 0,6 пойдёт гулять и лишь с вероятностью 0,1 возьмётся за уборку. Если добавить к этому набору действия агента и награды, получится марковский процесс принятия решений - другая надстройка над той же цепью Маркова, где состояния как раз наблюдаемы, а неизвестна оптимальная политика.

Полезно сразу оценить, сколько в модели свободных параметров: при $N$ состояниях и $M$ символах наблюдений их $N(N-1)$ в матрице переходов, $N(M-1)$ в матрице эмиссий и $N-1$ в начальном распределении, потому что каждая строка теряет одну степень свободы из-за нормировки. Для нашей модели это 2, 4 и 1, итого семь чисел. Чем длиннее наблюдаемая последовательность по сравнению с этим количеством, тем устойчивее будет оценка параметров.

Три задачи, которые решают для HMM

Практически всё, что делают со скрытой марковской моделью, сводится к трём задачам Рабинера. Они отличаются тем, что дано и что ищется.

Рассчитать для своей задачи

1. Оценка. Даны параметры $\lambda$ и наблюдения $O$; найти $P(O \mid \lambda)$. Это мера того, насколько модель правдоподобно объясняет данные, и именно по ней выбирают между несколькими обученными моделями (например, между HMM разных слов при распознавании речи).
2. Декодирование. Даны $\lambda$ и $O$; найти последовательность скрытых состояний $Q^*$, максимизирующую $P(Q \mid O, \lambda)$. Ответ на вопрос «что там на самом деле происходило».
3. Обучение. Даны только наблюдения; подобрать параметры $\lambda$, при которых $P(O \mid \lambda)$ максимально.

Лобовой перебор в первых двух задачах невозможен: путей длины $T$ по $N$ состояниям ровно $N^T$, при 10 состояниях и 100 шагах это $10^{100}$ вариантов. Спасает динамическое программирование - то же, что и в задачах на последовательные решения: вместо путей хранят значения в узлах.

Алгоритм forward: правдоподобие наблюдений

Прямая переменная $\alpha_t(i)$ - это вероятность увидеть первые $t$ наблюдений и оказаться в состоянии $i$:

$$\alpha_t(i) = P(o_1, \dots, o_t,\ q_t = i \mid \lambda)$$

Её считают по шагам. Инициализация $\alpha_1(i) = \pi_i \, b_i(o_1)$, дальше рекуррентно:

$$\alpha_{t+1}(j) = \left[\sum_{i=1}^{N} \alpha_t(i)\, a_{ij}\right] b_j(o_{t+1}), \qquad P(O \mid \lambda) = \sum_{i=1}^{N} \alpha_T(i)$$

Ключевое слово здесь - сумма: все пути, ведущие в узел, складываются, потому что нас интересует вероятность наблюдений при любой скрытой траектории. Сложность падает с $N^T$ до $N^2 T$.

Рассчитать для своей задачи

Для нашей последовательности «прогулка, магазин, уборка» первый столбец равен $0{,}2400$ и $0{,}0600$, второй - $0{,}0486$ и $0{,}0552$, третий - $0{,}0046$ и $0{,}0290$. Сумма последнего столбца даёт $P(O \mid \lambda) = 0{,}0336$. Само по себе число маленькое, и это нормально: вероятность конкретной тройки наблюдений и должна быть малой. Сравнивают такие числа только между моделями на одних и тех же данных, как апостериорные вероятности гипотез.

Алгоритм Витерби: лучший путь по решётке

Декодирование отличается от forward одной заменой: вместо суммы по предшественникам берётся максимум, а вместе со значением запоминается указатель на победителя.

$$\delta_{t+1}(j) = \max_{i} \left[\delta_t(i)\, a_{ij}\right] b_j(o_{t+1}), \qquad \psi_{t+1}(j) = \arg\max_{i} \left[\delta_t(i)\, a_{ij}\right]$$

В конце берут узел с наибольшим $\delta_T$ и идут по указателям $\psi$ назад, восстанавливая путь от конца к началу.

Рассчитать для своей задачи

Витерби максимизирует вероятность последовательности целиком, а не выбирает самое вероятное состояние на каждом шаге по отдельности. В нашем примере оба подхода дают один и тот же ответ, но в общем случае они расходятся: цепочка из поштучных максимумов может оказаться вовсе невозможной, если между какими-то состояниями стоит нулевая вероятность перехода. Ровно поэтому алгоритм хранит указатели $\psi$ и делает обратный ход, а не читает таблицу по столбцам. Вес найденного пути $0{,}0134$ составляет около 40 % правдоподобия $0{,}0336$: одна траектория из восьми возможных объясняет две пятых вероятности наблюдений.

Баум-Велч: обучение без разметки

Третья задача самая тяжёлая: параметры надо оценить, ни разу не увидев скрытых состояний. Алгоритм Баума-Велча - это частный случай EM-алгоритма, и работает он итерациями.

На шаге E при текущих параметрах считают апостериорные величины: $\gamma_t(i)$ - вероятность быть в состоянии $i$ в момент $t$, и $\xi_t(i, j)$ - вероятность перехода $i \to j$ между моментами $t$ и $t+1$. Обе выражаются через прямые $\alpha$ и обратные $\beta$ переменные. На шаге M параметры пересчитывают как «ожидаемые частоты»:

$$\hat{a}_{ij} = \frac{\sum_{t=1}^{T-1} \xi_t(i, j)}{\sum_{t=1}^{T-1} \gamma_t(i)}, \qquad \hat{b}_j(k) = \frac{\sum_{t:\, o_t = k} \gamma_t(j)}{\sum_{t=1}^{T} \gamma_t(j)}$$

Смысл пересчёта прозрачен: если бы скрытые состояния были известны, вероятность перехода оценивалась бы простой частотой «сколько раз из $i$ попали в $j$, делённое на то, сколько раз были в $i$». Состояния неизвестны, поэтому вместо счётчиков подставляют их ожидаемые значения при текущей модели, и процедура повторяется до сходимости.

Каждая итерация не уменьшает правдоподобие, но гарантирует лишь локальный максимум: из разных начальных приближений Баум-Велч приходит к разным моделям. Отсюда практика нескольких запусков со случайной инициализацией и выбора лучшего результата.

Где применяются скрытые марковские модели

Исторически HMM выросла на распознавании речи, где скрытый слой - последовательность фонем, а наблюдения - кадры спектра. Дальше она разошлась по областям, где данные упорядочены во времени или вдоль цепочки:

• разметка частей речи и распознавание именованных сущностей в NLP;
• поиск генов и выравнивание последовательностей в биоинформатике (профильные HMM);
• распознавание рукописного текста и жестов;
• определение режимов рынка в финансах (regime switching);
• диагностика состояния оборудования по косвенным измерениям.

Нейросетевые модели потеснили HMM в распознавании речи, но там, где данных мало, а структура процесса известна заранее, скрытая марковская модель остаётся рабочим инструментом: её параметры интерпретируемы, а обучение не требует размеченного скрытого слоя.

Частые ошибки

• Путают forward и Витерби. Формулы отличаются одним символом: сумма против максимума. Если в задаче на декодирование сложить веса вместо взятия максимума, получится правдоподобие, а не путь.
• Забывают умножить на вероятность эмиссии. Типичная потеря множителя $b_j(o_{t+1})$ на шаге рекурсии: числа остаются похожими на правильные, но ответ неверен.
• Собирают путь по поштучным максимумам. Последовательность самых вероятных состояний в каждый момент может оказаться вовсе невозможной, если между ними нулевой переход.
• Не нормируют строки матриц. Сумма по строке $A$ и по строке $B$ обязана равняться единице, иначе модель не задаёт распределения вероятностей.
• Считают длинные последовательности без масштабирования. Значения $\alpha_t$ убывают экспоненциально и при $T$ порядка сотен обнуляются машинно; на практике переходят к логарифмам или нормируют $\alpha$ на каждом шаге.

FAQ

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

Сколько скрытых состояний брать? Число состояний - гиперпараметр, он не определяется алгоритмом обучения. Его выбирают из предметного смысла (число фонем, число режимов рынка) или по информационным критериям AIC и BIC на отложенной выборке: рост числа состояний всегда повышает правдоподобие на обучающих данных и рано или поздно приводит к переобучению.

Можно ли работать с непрерывными наблюдениями? Да. Тогда дискретная матрица эмиссий заменяется плотностью, чаще всего смесью гауссиан для каждого состояния. Структура алгоритмов не меняется: в рекурсиях forward и Витерби вместо $b_j(o_t)$ подставляется значение плотности в точке наблюдения.

Коротко

Скрытая марковская модель задаётся тройкой $\lambda = (\pi, A, B)$ и описывает два слоя: марковскую цепь скрытых состояний и порождаемые ею наблюдения. С ней решают три задачи: правдоподобие $P(O \mid \lambda)$ считают алгоритмом forward, суммируя веса всех путей в решётке; наиболее вероятную цепочку состояний находят алгоритмом Витерби, где сумма заменяется максимумом и добавляются обратные указатели; параметры по неразмеченным данным подбирает Баум-Велч, итеративно повышая правдоподобие до локального максимума. Оба алгоритма стоят на динамическом программировании и работают за $N^2 T$ вместо экспоненциального перебора.