Автоматы и сознание
Скрытые марковские модели
Цели урока
- Понимать разницу между скрытыми состояниями и наблюдениями в HMM
- Знать формальное определение H = (S, O, A, B, pi)
- Понимать три задачи: Evaluation (Forward), Decoding (Viterbi), Learning (Baum-Welch)
- Читать и понимать реализации Forward и Viterbi на TypeScript
- Видеть применения HMM в речи, NLP, биоинформатике
Предварительные знания
- Цепи Маркова - матрица переходов, стационарное распределение
- Условная вероятность P(A|B)
- Динамическое программирование (базовое понимание)
- Теорема Байеса (желательно)
AT&T Bell Labs, 1975. Команда Фреда Джелинека: первая реальная система распознавания речи на 1000 слов. Не правила, не эвристики - статистическая модель, обученная на данных. Идея Джелинека: «каждый раз, когда я увольняю лингвиста, качество распознавания растёт». HMM дал индустрии речи 40 лет - до появления трансформеров в 2017. Та же математика сегодня в каждом смарт-спикере на планете.
- **Apple Siri (2011)** - первый массовый голосовой ассистент на HMM, 100 млн устройств в первый год
- **Биоинформатика** - поиск CpG-островков в ДНК через HMM открыл регуляторные регионы генома
- **Google HTK** - Hidden Toolkit использовался в Google Voice Search с 2007 по 2015
- **Финансы** - HMM для определения рыночных режимов (bull/bear) в quant trading фондах
- **Медицина** - анализ ЭКГ через HMM для выявления аномальных ритмов сердца
Леонард Баум и криптоанализ холодной войны
В 1966 году Леонард Баум из Institute for Defense Analyses разработал HMM для криптоанализа советских шифрограмм. Перехваченный зашифрованный текст - наблюдения. Оригинальное сообщение - скрытые состояния. Алгоритм Баума-Велша (1970) позволял обучать модель без знания истинных состояний. Работа была засекречена до 1972 года. После рассекречивания HMM революционизировали распознавание речи - первые системы AT&T Bell Labs (1975) были полностью на HMM.
Скрытая реальность: от FSM к HMM
**Apple Speech Recognition, 2011. Первый день Siri. Сервер получает акустические векторы - не слова, не буквы, а числа: [0.12, 0.87, 0.03...]. За 150 мс нужно восстановить фразу.** Под капотом - Hidden Markov Model с тысячами скрытых состояний (фонем), обученная на 10 000 часах речи. Та же математика сегодня работает в Google Assistant, Amazon Alexa и ChatGPT Voice.
**Ключевое отличие HMM от обычной цепи Маркова:** в цепи Маркова состояния видны напрямую. В HMM - истинные состояния системы скрыты, наблюдаются только их «симптомы» (эмиссии). Задача: по наблюдениям восстановить скрытый путь.
| Домен | Скрытые состояния | Наблюдения |
|---|---|---|
| Распознавание речи | Фонемы, слова | Акустические векторы (MFCC) |
| Биоинформатика | Функции генов (экзон/интрон) | Последовательность ATCG |
| NLP (POS tagging) | Часть речи (N/V/Adj) | Слова текста |
| Финансы | Режим рынка (бычий/медвежий) | Цены активов |
| Медицина | Диагноз (болезнь) | Симптомы, анализы |
Разница между цепью Маркова и HMM - как разница между прозрачным аквариумом и непрозрачным ящиком с рыбами. В цепи Маркова видно рыб. В HMM слышны лишь всплески воды - и по ним надо угадать, сколько рыб и где они.
HMM - это просто цепь Маркова с шумом
HMM - это двухуровневая модель: скрытый марковский процесс + вероятностный генератор наблюдений
Шум - это случайные помехи поверх видимого процесса. В HMM же сам процесс (скрытые состояния) невидим. Из состояния «фонема /k/» с разной вероятностью генерируются разные акустические векторы - это эмиссии, не шум.
Чем HMM принципиально отличается от обычной цепи Маркова?
Формальное определение HMM
**HMM формально задаётся пятёркой** H = (S, O, A, B, pi), где каждый элемент играет конкретную роль в модели.
| Символ | Название | Роль |
|---|---|---|
| S | Скрытые состояния | Множество состояний, недоступных наблюдателю |
| O | Наблюдения | Множество того, что реально видно |
| A | Матрица переходов | A[i][j] = P(S_j | S_i) - вероятность перехода между скрытыми |
| B | Матрица эмиссий | B[s][o] = P(o | s) - вероятность наблюдения o из состояния s |
| pi | Начальное распределение | pi[i] = P(S_i в момент t=0) |
Конкретный HMM: определение настроения по постам
Скрытые состояния S = {Happy, Sad}. Наблюдения O = {Positive, Neutral, Negative}. Матрица переходов A: Happy -> Happy: 0.7, Happy -> Sad: 0.3 Sad -> Happy: 0.4, Sad -> Sad: 0.6 Матрица эмиссий B: Happy: Positive=0.6, Neutral=0.3, Negative=0.1 Sad: Positive=0.1, Neutral=0.3, Negative=0.6 Начальное распределение pi = (0.6, 0.4) Задача: наблюдаем [Positive, Negative, Negative, Positive]. Каким было настроение?
Строки матрицы A и B должны суммироваться в 1 (это вероятностные распределения). Проверка: A[i].reduce((a,b)=>a+b) === 1 для каждого i, аналогично для B.
Что хранит матрица эмиссий B[s][o]?
Три задачи HMM: Evaluation, Decoding, Learning
**Любая работа с HMM сводится к трём фундаментальным задачам.** Рабочая лошадь ML - знать все три наизусть, понимать алгоритмы и сложность.
| Задача | Вопрос | Алгоритм | Сложность |
|---|---|---|---|
| Evaluation | P(O | модель) - какова вероятность этих наблюдений? | Forward | O(T * N^2) |
| Decoding | Наиболее вероятная последовательность скрытых состояний? | Viterbi | O(T * N^2) |
| Learning | Найти A, B, pi максимизирующие P(O | модель) | Baum-Welch (EM) | O(iter * T * N^2) |
Evaluation: алгоритм Forward
Наивный перебор всех путей даёт O(N^T) - при 50 состояниях и 100 шагах это 50^100 операций. Forward-алгоритм использует динамическое программирование: alpha[t][i] = P(O1..Ot, St=i). Сложность падает до O(T * N^2).
Decoding: алгоритм Витерби
Forward суммирует по всем путям. Витерби ищет максимум - наиболее вероятный путь скрытых состояний. Структура та же (DP), но sum заменяется на max, добавляется трекбэк psi для восстановления пути.
Learning: алгоритм Баума-Велша
Идея EM в HMM
E-step: при текущих A, B, pi - вычислить мягкие вероятности (gamma, xi): с какой вероятностью в момент t система была в состоянии s? M-step: обновить A, B, pi чтобы максимизировать ожидаемое правдоподобие. Повторять до сходимости. Каждая итерация гарантированно не уменьшает log P(O | модель). Это специализация EM-алгоритма для HMM.
Baum-Welch сходится к локальному максимуму, не глобальному. На практике запускают несколько раз с разными начальными параметрами и берут лучший результат.
HMM всегда находит истинные скрытые состояния
HMM находит наиболее вероятные состояния при данной модели - и не более
Если модель неверна (мало состояний, неверные эмиссии), декодирование тоже будет неверным. HMM не знает истинную структуру мира - он оптимизирует правдоподобие под заданную архитектуру. Именно поэтому выбор числа скрытых состояний - критически важный гиперпараметр.
В чём принципиальная разница между Forward и Viterbi?
HMM в реальных системах
**Google, 1998. PageRank - первый алгоритм ранжирования Google.** Под капотом - марковская цепь над графом веб-страниц. HMM появился в каждой системе обработки языка и сигналов следующие 20 лет - до прихода трансформеров.
| Система | Скрытые состояния | Алгоритм HMM | Замена сегодня |
|---|---|---|---|
| Распознавание речи (HTK, 1990s) | Фонемы (~40 для EN) | Viterbi декодирование | Wav2Vec 2.0 (трансформер) |
| POS тэггинг в NLP | Часть речи | Viterbi | BERT fine-tuning |
| Биоинформатика (CpG островки) | CpG/не-CpG регион | Forward / Viterbi | DeepVariant (CNN) |
| Распознавание рукописного текста | Символы | Viterbi | CTC + LSTM |
| Финансовые режимы | Bull/Bear рынок | Baum-Welch + Viterbi | Гибрид HMM+NN |
Трансформеры (2017) вытеснили HMM из многих задач NLP и речи. Но HMM остаётся незаменимым там, где нужна интерпретируемость: биоинформатика, медицина, финансы. Также HMM - математическая основа для понимания POMDP (следующий урок).
Задача нечестного казино (классика)
Казино использует два кубика: честный (P(k)=1/6) и нечестный (P(6)=0.5, P(k)=0.1 для k!=6). Казино тайно меняет кубики. Скрытые состояния: {Fair, Loaded}. Наблюдения: {1,2,3,4,5,6}. Переходы: P(Fair->Fair)=0.95, P(Fair->Loaded)=0.05, P(Loaded->Fair)=0.1, P(Loaded->Loaded)=0.9. При последовательности [6,6,3,6,6,6] Viterbi декодирует: [Loaded,Loaded,Fair,Loaded,Loaded,Loaded]. Эта задача - стандартный тест любой реализации HMM.
Связи с другими темами
HMM - ключевая модель в цепочке от Маркова до RL:
- Цепи Маркова — HMM = марковская цепь + скрытые состояния + эмиссии
- POMDP — HMM + действия агента = POMDP (частично наблюдаемый MDP)
- EM-алгоритм — Baum-Welch - частный случай EM для скрытых переменных
- MDP — MDP добавляет к HMM управляющего агента с функцией наград
В задаче POS-тэггинга (определение частей речи) что является скрытыми состояниями в HMM?
Ключевые идеи
- **HMM vs цепь Маркова** - в HMM истинные состояния скрыты, наблюдаются только их эмиссии; цепь Маркова прозрачна
- **Пятёрка (S, O, A, B, pi)** - скрытые состояния, наблюдения, матрица переходов, матрица эмиссий, начальное распределение
- **Evaluation (Forward)** - P(O | модель) за O(T * N^2) вместо O(N^T) через динамическое программирование
- **Decoding (Viterbi)** - та же DP, но sum заменяется на max; находит наиболее вероятный путь скрытых состояний
- **Learning (Baum-Welch)** - EM для HMM: E-step считает soft posteriors, M-step обновляет A, B, pi; сходится к локальному максимуму
- **Применения** - распознавание речи (фонемы), POS-тэггинг (части речи), биоинформатика (CpG-островки), финансовые режимы
- **Границы HMM** - трансформеры вытеснили HMM в NLP и речи, но HMM незаменим там где нужна интерпретируемость
Вопросы для размышления
- Какие системы вокруг работают с неполной информацией - видят симптомы, не видят причины? Как HMM мог бы моделировать поведение пользователя в мобильном приложении, где скрыто его намерение, а видны только клики?
Связанные уроки
- aut-02-markov-chains — Матрица переходов и стационарное распределение - база HMM
- aut-04-mdp — MDP = HMM + действия агента, следующий шаг в иерархии
- aut-05-pomdp — POMDP = HMM + частичная наблюдаемость + управление
- prob-01-intro — Условная вероятность P(A|B) и теорема Байеса - язык HMM
- nlp-01 — POS tagging, NER - классические применения HMM в NLP
- ml-03 — EM-алгоритм: Baum-Welch - это специализация EM для скрытых переменных
- alg-05 — Forward и Viterbi - это динамическое программирование на цепочке
- prob-04-bayes