Цепи Маркова

До сих пор наши гарантии для выборок в основном предполагали независимые наблюдения. Многие случайные процессы устроены иначе, и их зависимость разворачивается во времени: завтрашняя погода зависит от сегодняшней, следующее слово — от предыдущих, следующая страница, которую откроет читатель, — от текущей, следующее состояние сэмплера — от текущего состояния. Цепь Маркова (Markov chain) — простейшая модель такой зависимости: будущее зависит от прошлого только через настоящее. Она достаточно проста, чтобы её можно было проанализировать полностью, и достаточно богата, чтобы описать n-граммные языковые модели, веб-поиск и сэмплеры из двух последних заметок курса.

Обозначения. $X_0, X_1, X_2, \dots$ принимают значения в конечном множестве состояний $\{1, \dots, K\}$. $P$ — матрица переходов (transition matrix) размера $K \times K$, $P_{ij} = P(X_{t+1} = j \mid X_t = i)$; сумма каждой строки равна 1. Распределение по состояниям — вектор-строка $\pi$.

Марковское свойство#

Последовательность называется цепью Маркова, если

$$P(X_{t+1} = j \mid X_t = i, X_{t-1}, \dots, X_0) = P(X_{t+1} = j \mid X_t = i) = P_{ij} .$$

Первое равенство — марковское свойство (Markov property): текущее состояние содержит всё о прошлом, что важно для будущего. Второе — отдельное предположение, однородность по времени (time homogeneity): правило перехода $P_{ij}$ одно и то же в любой момент $t$. Все цепи в этой заметке конечны и однородны по времени. Обратный процесс, порождающий сэмплы в диффузионной модели, марковский, но не однородный: его правило перехода меняется от шага к шагу (заметка о MCMC). Модель погоды с тремя состояниями, в которой за ясным днём в 70% случаев следует ясный, — это цепь Маркова с

$$P = \begin{pmatrix} 0.7 & 0.2 & 0.1 \\ 0.3 & 0.4 & 0.3 \\ 0.2 & 0.3 & 0.5 \end{pmatrix}$$

(строки и столбцы: ясно, облачно, дождь). По формуле полной вероятности распределение следующего состояния равно текущему распределению, умноженному на матрицу:

$$\pi_{t+1} = \pi_t P, \qquad \pi_t = \pi_0 P^t .$$

Элемент $(P^t)_{ij}$ — вероятность оказаться в $j$ через $t$ шагов, начав из $i$. Начнём с ясного дня:

Рисунок

Цепь Маркова для погоды

Стационарные распределения#

Распределение $\pi$, для которого

$$\pi P = \pi$$

называется стационарным (stationary): если цепь начинается в нём, она в нём и остаётся. Это левый собственный вектор $P$ с собственным значением 1, нормированный так, чтобы сумма компонент равнялась 1; его можно найти, решив линейную систему $\pi P = \pi$, $\sum_i \pi_i = 1$. Для цепи погоды $\pi = (21/46, 13/46, 12/46) = (0.457, 0.283, 0.261)$: в долгосрочной перспективе 46% дней ясные.

Рисунок подсказывает больше: если начать с ясного дня, распределение приближается к $\pi$ за десять дней. Это верно для любого начального распределения при двух условиях:

• Неприводимость (irreducibility): любое состояние достижимо из любого другого.
• Апериодичность (aperiodicity): цепь не движется по циклу с фиксированным периодом. Цепь, которая детерминированно чередует два состояния, имеет стационарное распределение $(1/2, 1/2)$, но из фиксированного начального состояния к нему никогда не приближается.

Для конечной неприводимой апериодической цепи $\pi_t \to \pi$ из любого начального распределения, а эргодическая теорема (ergodic theorem) — закон больших чисел для цепей Маркова — утверждает, что доля времени, которую цепь проводит в каждом состоянии, на одной длинной траектории сходится к $\pi$. Скорость задаёт второй по величине модуль собственных значений $P$: расстояние до $\pi$ убывает примерно как $\lvert \lambda_2 \rvert^t$, здесь как $0.473^t$, так что десять шагов уменьшают его примерно в 1800 раз. Число шагов, за которое цепь подходит близко к стационарному распределению, — это время перемешивания (mixing time), центральная величина для сэмплеров из заметки о MCMC.

Языковые модели как цепи Маркова#

Биграммная языковая модель — это цепь Маркова, состояния которой — слова: $P_{ij}$ — оценённая по числу вхождений вероятность того, что слово $j$ следует за словом $i$. Генерировать по ней текст — значит запускать цепь. Для биграммной цепи, оценённой по одному длинному тексту, стационарное распределение приближённо совпадает с униграммными частотами слов: за каждым словом следует слово и перед каждым стоит слово столько же раз, сколько оно встречается, кроме двух концов текста, так что униграммные частоты удовлетворяют уравнению стационарности с точностью до этих граничных слагаемых. Тексту из отдельных предложений нужен токен конца предложения, ведущий обратно в начальное состояние, иначе цепь останавливается. n-граммная модель при $n > 2$ — цепь Маркова, состояния которой — контексты из $n - 1$ слов; её стационарное распределение задано на контекстах, а униграммная частота — его маргинальное распределение для одной позиции контекста. Шеннон в статье 1948 года именно так порождал «английский текст» — цепями букв и слов возрастающего порядка, а заметка об n-граммных языковых моделях строит такие модели по данным.

Языковая модель на основе трансформера — тоже цепь Маркова, но с гораздо большим состоянием: всем контекстным окном. Марковское свойство — утверждение о том, что содержит состояние, и именно обогащая состояние, модели последовательностей получают более длинную память.

PageRank#

Читатель, который с каждой страницы переходит по случайной ссылке, совершает случайное блуждание (random walk) — цепь Маркова на страницах. Страницы, которые случайные блуждания посещают часто, важны; их важность — это стационарное распределение. Две поправки делают цепь корректно определённой, неприводимой и апериодической: с вероятностью $0.15$ читатель вместо перехода по ссылке прыгает на случайную страницу, а со страницы без ссылок прыгает всегда. Стационарное распределение такой цепи — это PageRank, сигнал ранжирования, на котором была основана ранняя поисковая система Google:

Рисунок

PageRank — стационарное распределение случайного блуждания

Пример показывает, чем PageRank отличается от подсчёта ссылок: страница важна, если на неё ссылаются важные страницы. У C больше всего входящих ссылок, но A, на которую ссылаются C и D, почти так же важна, потому что C передаёт весь свой вес странице A.

Вероятности достижения: задача о разорении игрока#

У некоторых цепей есть поглощающие (absorbing) состояния, из которых цепь никогда не выходит, и вопрос в том, какое из них будет достигнуто первым. Игрок с 3 монетами ставит по одной монете в честной игре и останавливается, когда у него остаётся 0 или набирается 10 монет. Пусть $h_a$ — вероятность дойти до 10, начав с $a$; разбор по исходу первой ставки даёт $h_a = \frac12 h_{a+1} + \frac12 h_{a-1}$ при $h_0 = 0$, $h_{10} = 1$, откуда $h_a = a/10$ и $h_3 = 0.3$. Ожидаемое число ставок равно $a(10 - a) = 21$. Слегка невыгодная игра, в которой каждая ставка выигрывается с вероятностью $0.49$, снижает этот шанс до $0.259$; при старте с 50 монет и цели 100 он равен всего $0.119$, а не половине: за долгую игру небольшое преимущество накапливается. Те же уравнения первого шага дают времена достижения (hitting times) и вероятности поглощения для любой цепи — от воронок продаж до ожидаемой длины случайного блуждания.

Что изменилось#

	Независимые наблюдения	Цепи Маркова
Зависимость	нет	следующее состояние зависит от текущего: $P_{ij}$
Распределение во времени	постоянно	$\pi_t = \pi_0 P^t$
В долгосрочной перспективе	закон больших чисел	стационарное $\pi = \pi P$; эргодическая теорема для средних по времени
Скорость	$1/\sqrt n$	ещё и время перемешивания, которое задаёт $\lvert \lambda_2 \rvert$
Примеры		n-граммные модели, PageRank, случайные блуждания, MCMC

Ограничения#

• Марковское свойство — модельное допущение. У реальных процессов память длиннее; расширение состояния (последние $n$ слов, весь контекст) восстанавливает свойство ценой гораздо большего пространства состояний.
• Сходимость может быть медленной. Цепи с узкими местами, например с двумя кластерами состояний, между которыми переходы редки, могут перемешиваться очень долго, и по одной траектории это может быть никак не заметно.
• Конечное множество состояний скрывает тонкости. Бесконечным или непрерывным пространствам состояний нужны условия (возвратность, положительная возвратность), которые в конечном случае выполняются автоматически.

Что нужно запомнить#

• Марковское свойство: будущее зависит от прошлого только через настоящее; $P_{ij} = P(X_{t+1} = j \mid X_t = i)$.
• Распределения эволюционируют по правилу $\pi_{t+1} = \pi_t P$; $(P^t)_{ij}$ — вероятность перехода за $t$ шагов.
• Стационарность: $\pi P = \pi$. Для конечных неприводимых апериодических цепей $\pi_t \to \pi$ из любого начального распределения, а средние по времени сходятся к $\pi$.
• Скорость задаёт второе по модулю собственное значение: расстояние до $\pi$ $\approx \lvert \lambda_2 \rvert^t$.
• n-граммные модели и PageRank — цепи Маркова; PageRank — стационарное распределение случайного пользователя (random surfer) с телепортацией.
• Вероятности поглощения и времена достижения находятся из уравнений первого шага; в честной задаче о разорении игрока с целью $N$ вероятность $h_a = a/N$.

Код#

Цепь погоды, её стационарное распределение и одна длинная траектория, PageRank и задача о разорении игрока:

import numpy as np

# the weather chain: distributions after 1, 2 and 10 days from a sunny start
P = np.array([[0.7, 0.2, 0.1], [0.3, 0.4, 0.3], [0.2, 0.3, 0.5]])
pi = np.array([1.0, 0.0, 0.0])
for t in range(11):
    if t in (1, 2, 10):
        print(t, pi.round(3))
    pi = pi @ P
# 1 [0.7 0.2 0.1] | 2 [0.57 0.25 0.18] | 10 [0.457 0.283 0.261]

# the stationary distribution solves pi P = pi with sum 1; the eigenvalues set the speed
A = np.vstack([P.T - np.eye(3), np.ones(3)])
stationary = np.linalg.lstsq(A, np.array([0, 0, 0, 1.0]), rcond=None)[0]
print(stationary.round(4), (np.array([21, 13, 12]) / 46).round(4))   # [0.4565 0.2826 0.2609] twice
print(np.sort(np.abs(np.linalg.eigvals(P))).round(3))                # [0.127 0.473 1.   ]

# the ergodic theorem: the share of days in each state along one long run
rng = np.random.default_rng(0)
x, counts = 0, np.zeros(3)
for _ in range(100_000):
    counts[x] += 1
    x = rng.choice(3, p=P[x])
print((counts / counts.sum()).round(3))                               # [0.459 0.281 0.259]

# PageRank of five pages by power iteration, damping 0.85
links = {0: [1, 2], 1: [2], 2: [0], 3: [0, 2], 4: [3, 2]}
M = np.zeros((5, 5))
for i, outs in links.items():
    M[i, outs] = 1 / len(outs)
G = 0.85 * M + 0.15 / 5
r = np.full(5, 0.2)
for _ in range(200):
    r = r @ G
print(r.round(3))                                                     # [0.367 0.186 0.375 0.043 0.03 ]

# gambler's ruin: the probability of reaching N before 0 from a, winning each bet with probability p
ruin = lambda p, a, N: a / N if p == 0.5 else (1 - ((1 - p) / p) ** a) / (1 - ((1 - p) / p) ** N)
print(ruin(0.5, 3, 10), round(ruin(0.49, 3, 10), 3), round(ruin(0.49, 50, 100), 3))   # 0.3 0.259 0.119

Дальше#

Эргодическая теорема говорит, что длинная траектория цепи сэмплирует её стационарное распределение. Если перевернуть это утверждение, получится способ сэмплировать из распределения, из которого нельзя сэмплировать напрямую: построить цепь, стационарное распределение которой и есть целевое. Прежде чем развивать эту идею, следующая заметка собирает прямые методы Монте-Карло — метод обратной функции, выборку с отклонением (rejection sampling) и выборку по значимости (importance sampling) — и разбирает дисперсию, от которой зависит, работают ли они.

Литература#

• J. R. Norris. Markov Chains. Cambridge University Press, 1997. Глава 1 (цепи с дискретным временем, вероятности достижения, стационарные распределения, сходимость, эргодическая теорема).
• D. A. Levin, Y. Peres, E. L. Wilmer. Markov Chains and Mixing Times, 2nd ed. American Mathematical Society, 2017. Главы 1, 4 и 12 (стационарные распределения, перемешивание, спектральная щель).
• C. E. Shannon. A Mathematical Theory of Communication. Bell System Technical Journal, 27(3), 1948. Марковские приближения к английскому языку.
• S. Brin, L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Computer Networks and ISDN Systems, 30, 1998.