Цепи Маркова

Цели урока

• Понимать марковское свойство и отличие от детерминированного FSM
• Читать и строить матрицу переходов для цепи Маркова
• Вычислять эволюцию распределения через умножение pi * P
• Знать стационарное распределение и его связь с PageRank
• Видеть связь цепей Маркова с языковыми моделями и Stable Diffusion

Предварительные знания

• Конечные автоматы (FSM) - предыдущий урок aut-01-fsm
• Базовые вероятности: P(A) - вероятность события, сумма вероятностей = 1
• Умножение матрицы на вектор - желательно, объясним в примерах

Google PageRank. Spotify Discover Weekly. DeepMind AlphaGo. Stable Diffusion. Все четыре - цепи Маркова. Один и тот же математический объект, открытый Андреем Марковым в 1906 году при анализе 20 000 букв Евгения Онегина. Марков не знал ни про Google, ни про нейросети. Он спорил о свободе воли.

• **Google PageRank (1998)** - вся индексация 2 триллионов страниц через стационарное распределение цепи Маркова; без этой математики поисковик не работал бы
• **Stable Diffusion / DDPM** - обратный диффузионный процесс это цепь Маркова от чистого гауссового шума к изображению; 1000 шагов денойзинга
• **DeepMind AlphaGo** - MCTS строит дерево игры как цепь Маркова; стационарное распределение посещений определяет лучший ход
• **Spotify Discover Weekly** - коллаборативная фильтрация через random walks на графе пользователей и треков; тот же степенной метод что и PageRank
• **MCMC в байесовском ML** - PyMC3, Stan, NumPyro используют цепи Маркова для сэмплирования из апостериорного распределения

Марков против Некрасова - спор о свободе воли

Русский математик Андрей Марков создал свои цепи в полемике с религиозным философом Некрасовым. Тот утверждал: закон больших чисел применим только к независимым событиям - а значит 'доказывает' свободу воли и ответственность за грехи. Марков опроверг его математически, показав что даже зависимые события подчиняются статистике. Для демонстрации взял 20 000 букв Евгения Онегина и вручную построил матрицу переходов гласных и согласных - первую цепь Маркова в истории. Спор о теологии породил инструмент, на котором стоит Google.

Марковское свойство и FSM с вероятностями

**Google PageRank. Spotify Discover Weekly. DeepMind AlphaGo. Stable Diffusion.** Все четыре построены на одном математическом объекте, открытом Андреем Марковым в 1906 году при анализе русской поэзии. FSM детерминирован: один вход - один исход. Цепь Маркова добавляет вероятность к каждому переходу. Этого простого расширения оказалось достаточно, чтобы описать PageRank, генерацию текста и диффузионные модели.

**Цепь Маркова** - это FSM, где каждый переход имеет вероятность. Формально: из состояния i система переходит в состояние j с вероятностью p_ij. Ключевое свойство (марковское): P(X_{t+1} = j | X_t = i, X_{t-1} = k, ...) = P(X_{t+1} = j | X_t = i). Будущее зависит только от настоящего - не от того, как система сюда попала.

Пример: модель погоды с двумя состояниями. Если сегодня солнечно - завтра снова солнечно с вероятностью 0.8, дождь с 0.2. Если дождь - снова дождь с 0.6, солнце с 0.4. Никакого входного алфавита нет - переход происходит автоматически на каждом шаге. Stable Diffusion работает ровно так же: состояния - уровни шума, переходы - обратный диффузионный процесс.

Матрица переходов и эволюция распределения

**Все вероятности переходов цепи записываются в матрицу P, где p_ij - вероятность перехода из i в j.** Главное свойство: сумма каждой строки равна 1 - из любого состояния система куда-то переходит с вероятностью 100%. Такая матрица называется стохастической. Умножение вектора-распределения на P - это один шаг эволюции цепи.

Матрица переходов для модели погоды (строки: откуда, столбцы: куда): строка Sunny [0.8, 0.2], строка Rainy [0.4, 0.6]. Проверка: 0.8 + 0.2 = 1, 0.4 + 0.6 = 1. Для вычисления распределения на следующий шаг: pi^(t+1) = pi^(t) * P.

Не все цепи Маркова сходятся к единственному стационарному распределению. Требуется: 1. неприводимость - из любого состояния можно достичь любого другого 2. апериодичность - система не застревает в цикличном поведении. При нарушении любого условия - гарантии сходимости нет.

Стационарное распределение и PageRank

**Google PageRank, 1998: Брин и Пейдж превращают весь интернет в одну гигантскую цепь Маркова.** Модель - случайный сёрфер переходит по ссылкам страниц. Стационарное распределение этой цепи - это и есть ранг каждой страницы. 2 триллиона страниц. Одна собственная задача линейной алгебры.

Стационарное распределение pi - вектор, не изменяющийся при умножении на P: pi * P = pi. Для погодной модели: pi = [2/3, 1/3]. Проверка: [0.667, 0.333] * [[0.8,0.2],[0.4,0.6]] = [0.667, 0.333]. Сходится! Теорема Перрона-Фробениуса гарантирует существование и единственность для неприводимых апериодических цепей.

Стационарное распределение для этого графа: A=0.333, B=0.167, C=0.167, D=0.333. Страницы A и D имеют наивысший ранг - не потому что на них много ссылок, а потому что случайный сёрфер проводит там больше времени. AlphaGo использует тот же принцип в MCTS: стационарное распределение посещений узлов дерева.

Стационарное распределение - это левый собственный вектор матрицы P с собственным значением 1 (теорема Перрона-Фробениуса). Именно поэтому PageRank вычисляется через степенной метод - многократное умножение на P. Тот же алгоритм, который используется для вычисления собственных векторов в PCA.

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

**GPT-2 (2019, OpenAI) генерирует связные статьи. Но его прямые предшественники - буквальные цепи Маркова.** Состояния = слова, переходы = вероятности того, какое слово следует за каким, обученные на корпусе. Марков делал то же самое с буквами в 1906 году - вручную, на 20 000 символах Евгения Онегина. Разница - только в масштабе и механизме внимания.

Проблема цепей первого порядка: модель не видит контекст дальше одного слова. Текст получается бессвязным. Цепи 2-го порядка (биграммы) лучше, 3-го (триграммы) - ещё лучше. Трансформеры (GPT-3, GPT-4) - это цепи с 'бесконечным' контекстом через механизм внимания с квадратичной сложностью O(n^2).

Цепи Маркова применяются не только в тексте: **MCMC (Markov Chain Monte Carlo)** - стандарт байесовского вывода в PyMC3, Stan; **Stable Diffusion** - обратный диффузионный процесс как цепь Маркова от шума к изображению; **AlphaGo MCTS** - стационарное распределение посещений узлов; **биоинформатика** - модели мутаций ДНК и Hidden Markov Models для выравнивания последовательностей.

Ключевые идеи

• **Марковское свойство**: P(X_{t+1} | X_t, X_{t-1}, ...) = P(X_{t+1} | X_t) - будущее зависит только от настоящего
• **Матрица переходов P**: p_ij - вероятность перехода i->j; сумма каждой строки = 1 (стохастическая матрица)
• **Эволюция**: pi^(t+1) = pi^(t) * P; распределение через k шагов = pi * P^k
• **Стационарное распределение pi**: pi * P = pi; существует и единственно для неприводимых апериодических цепей
• **PageRank** - стационарное распределение случайного сёрфера по гиперссылкам; вычисляется степенным методом
• **GPT vs Markov**: трансформеры - цепи с полным контекстом через attention; Марков 1-го порядка видит только последний токен

Связанные темы

Цепи Маркова связывают вероятность, автоматы и современные ML-системы:

• Конечные автоматы (FSM) — FSM - детерминированный частный случай цепи Маркова без вероятностей
• Скрытые марковские модели (HMM) — HMM добавляет скрытые состояния и применяется в распознавании речи
• Марковские процессы принятия решений (MDP) — MDP - цепь Маркова с управлением, основа Reinforcement Learning

Вопросы для размышления

• Если моделировать поведение пользователя на e-commerce сайте как цепь Маркова - состояния: главная, категория, товар, корзина, оплата, уход. Как выглядит матрица переходов? Что стационарное распределение говорит о конверсии? Как изменение одного перехода (например, упрощение оплаты) сдвинет стационарное распределение?

Связанные уроки

• aut-01-fsm — FSM - детерминированный предшественник цепи Маркова
• aut-03-hmm — HMM - цепь Маркова со скрытыми состояниями, следующий шаг
• ml-09-gradient-descent — MCMC использует цепи Маркова для байесовского вывода
• aut-04-mdp — MDP - цепь Маркова с управлением, основа RL
• prob-05-independence