Стохастические процессы

Случайность со структурой. Математика, лежащая в основе случайных блужданий, цепей Маркова и диффузионных моделей.

Тип: Изучение Язык: Python Предварительные требования: Фаза 1, уроки 06–07 (вероятность, Байес) Время: ~75 минут

Цели обучения

• Смоделировать одномерные и двумерные случайные блуждания и проверить масштабирование смещения как sqrt(n)
• Построить симулятор цепи Маркова и вычислить её стационарное распределение через разложение по собственным значениям
• Реализовать MCMC Метрополиса—Хастингса и динамику Ланжевена для выборки из целевых распределений
• Связать прямой процесс диффузии с броуновским движением и объяснить, как обратный процесс генерирует данные

Проблема

Во многих AI-системах присутствует случайность, которая развивается во времени. Это не статическая случайность, а структурированная последовательная случайность, где каждый шаг зависит от предшествующего.

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

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

Агенты обучения с подкреплением предпринимают действия в среде. Каждое действие с некоторой вероятностью ведёт к новому состоянию. Агент следует случайной политике в случайном мире. Вся эта конструкция является марковским процессом принятия решений.

Выборка MCMC — основа байесовского вывода — строит цепь Маркова, стационарным распределением которой является апостериорное распределение, из которого вы хотите делать выборки.

Всё это опирается на четыре фундаментальные идеи:

1. Случайные блуждания — простейший стохастический процесс
2. Цепи Маркова — структурированная случайность с матрицей переходов
3. Динамика Ланжевена — градиентный спуск с шумом
4. Метрополис—Хастингс — выборка из любого распределения

Концепция

Случайные блуждания

Начните в позиции 0. На каждом шаге бросайте честную монету. Орёл: сдвиньтесь вправо (+1). Решка: сдвиньтесь влево (-1).

После n шагов ваша позиция равна сумме n случайных значений +/-1. Ожидаемая позиция равна 0 (блуждание несмещённое). Но ожидаемое расстояние от начала координат растёт как sqrt(n).

Это противоречит интуиции. Блуждание честное — нет дрейфа ни в одну сторону. Однако со временем оно уходит всё дальше и дальше от точки старта. Стандартное отклонение после n шагов равно sqrt(n).

Шаг 0:      Позиция = 0
Шаг 1:      Позиция = +1 или -1
Шаг 2:      Позиция = +2, 0 или -2
...
Шаг 100:    Ожидаемое расстояние от начала ~ 10 (sqrt(100))
Шаг 10000:  Ожидаемое расстояние от начала ~ 100 (sqrt(10000))

В 2D блуждание с равной вероятностью перемещается вверх, вниз, влево или вправо. То же масштабирование sqrt(n) применимо к расстоянию от начала координат. Траектория рисует узор, похожий на фрактал.

Почему sqrt(n)? Каждый шаг равен +1 или -1 с одинаковой вероятностью. После n шагов позиция S_n = X_1 + X_2 + … + X_n, где каждый X_i равен +/-1. Дисперсия каждого шага равна 1, а шаги независимы, поэтому Var(S_n) = n. Стандартное отклонение = sqrt(n). По центральной предельной теореме S_n / sqrt(n) сходится к стандартному нормальному распределению.

Это масштабирование sqrt(n) встречается в ML повсюду. Шум SGD масштабируется как 1/sqrt(batch_size). Размерности эмбеддингов масштабируются как sqrt(d). Квадратный корень — признак независимых случайных сложений.

Связь с броуновским движением. Возьмите случайное блуждание с размером шага 1/sqrt(n) и n шагами на единицу времени. При стремлении n к бесконечности блуждание сходится к броуновскому движению B(t) — непрерывному во времени процессу, в котором B(t) нормально распределена со средним 0 и дисперсией t.

Броуновское движение — математический фундамент диффузии. Оно моделирует случайное дрожание частиц в жидкости, колебания цен акций и — что особенно важно — процесс шума в диффузионных моделях.

Разорение игрока. Случайный блуждатель начинает в позиции k; поглощающие барьеры расположены в 0 и N. Какова вероятность достичь N раньше 0? Для честного блуждания: P(reach N) = k/N. Это удивительно простое и изящное выражение. Оно связывается с теорией мартингалов: честное случайное блуждание является мартингалом (ожидаемое будущее значение равно текущему значению).

Цепи Маркова

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

P(X_{t+1} = j | X_t = i, X_{t-1} = ...) = P(X_{t+1} = j | X_t = i)

Это марковское свойство. Оно означает, что всю динамику можно описать матрицей переходов P:

P[i][j] = вероятность перехода из состояния i в состояние j

Сумма элементов каждой строки P равна 1 (вы обязательно куда-то перейдёте).

Пример — погода:

Состояния: солнечно (0), дождливо (1), облачно (2)

P = [[0.7, 0.1, 0.2],    (если солнечно: 70% солнечно, 10% дождливо, 20% облачно)
     [0.3, 0.4, 0.3],    (если дождливо: 30% солнечно, 40% дождливо, 30% облачно)
     [0.4, 0.2, 0.4]]    (если облачно: 40% солнечно, 20% дождливо, 40% облачно)

Начните с любого состояния. После многих переходов распределение состояний сходится к стационарному распределению pi, где pi * P = pi. Это левый собственный вектор P с собственным значением 1.

Для цепи погоды стационарное распределение может быть равно [0.53, 0.18, 0.29]: в долгосрочной перспективе солнечно 53% времени независимо от начального состояния.

Вычисление стационарного распределения. Есть два подхода:

1. Степенной метод: многократно умножайте любое начальное распределение на P. После достаточного числа итераций оно сойдётся.
2. Метод собственных значений: найдите левый собственный вектор P с собственным значением 1. Это собственный вектор P^T с собственным значением 1.

Оба подхода требуют, чтобы цепь удовлетворяла условиям сходимости.

Условия сходимости. Цепь Маркова сходится к единственному стационарному распределению, если она:

• Неразложима (irreducible): каждое состояние достижимо из любого другого
• Апериодична (aperiodic): цепь не зацикливается с фиксированным периодом

Большинство цепей, встречающихся в ML, удовлетворяет обоим условиям.

Поглощающие состояния. Состояние поглощающее, если, попав в него, вы уже никогда его не покинете (P[i][i] = 1). Поглощающие цепи Маркова моделируют процессы с терминальными состояниями: заканчивающуюся игру, клиента, который ушёл, последовательность токенов, достигшую токена конца текста.

Время смешивания. Сколько шагов нужно, чтобы цепь стала «близка» к стационарному распределению? Формально это число шагов до того момента, когда расстояние полной вариации от стационарности опустится ниже некоторого порога. Быстрое смешивание = требуется мало шагов. Спектральная щель P (единица минус второе по величине собственное значение) определяет время смешивания. Чем больше щель, тем быстрее смешивание.

Связь с языковыми моделями

Генерация токенов в языковой модели приблизительно является марковским процессом. Получив текущий контекст, модель выдаёт распределение по следующему токену. Температура управляет его остротой:

P(token_i) = exp(logit_i / temperature) / sum(exp(logit_j / temperature))

• Температура = 1.0: стандартное распределение
• Температура < 1.0: острее (более детерминированное)
• Температура > 1.0: более плоское (более случайное)
• Температура -> 0: argmax (жадный выбор)

Выборка top-k отбрасывает все токены, кроме k с наибольшей вероятностью. Выборка top-p (nucleus) оставляет наименьшее множество токенов, совокупная вероятность которого превышает p. Обе модифицируют вероятности переходов марковского процесса.

Броуновское движение

Непрерывный во времени предел случайного блуждания. Позиция B(t) обладает тремя свойствами:

1. B(0) = 0
2. B(t) - B(s) нормально распределена со средним 0 и дисперсией t - s (для t > s)
3. Приращения на неперекрывающихся интервалах независимы

Броуновское движение непрерывно, но нигде не дифференцируемо: оно колеблется на каждом масштабе. Траектория имеет фрактальную размерность 2 на плоскости.

В дискретной симуляции броуновское движение приближают так:

B(t + dt) = B(t) + sqrt(dt) * z,    где z ~ N(0, 1)

Масштабирование sqrt(dt) важно. Оно следует из центральной предельной теоремы, применённой к случайным блужданиям.

Динамика Ланжевена

Градиентный спуск находит минимум функции. Динамика Ланжевена находит распределение вероятностей, пропорциональное exp(-U(x)/T), где U — функция энергии, а T — температура.

x_{t+1} = x_t - dt * gradient(U(x_t)) + sqrt(2 * T * dt) * z_t

На частицу действуют две силы:

1. Градиентная сила (-dt * gradient(U)): толкает к низкой энергии (как градиентный спуск)
2. Случайная сила (sqrt(2Tdt) * z): толкает в случайных направлениях (исследование)

При температуре T = 0 это чистый градиентный спуск. При высокой температуре это почти случайное блуждание. При подходящей температуре частица исследует энергетический ландшафт и проводит больше времени в областях низкой энергии.

Связь с диффузионными моделями. Прямой процесс диффузионной модели таков:

x_t = sqrt(alpha_t) * x_{t-1} + sqrt(1 - alpha_t) * noise

Это цепь Маркова, которая постепенно смешивает данные с шумом. После достаточного числа шагов x_T становится чистым гауссовским шумом.

Обратный процесс — переход от шума обратно к данным — тоже является цепью Маркова, но её вероятности перехода обучает нейронная сеть. Сеть учится предсказывать шум, добавленный на каждом шаге, а затем вычитать его.

MCMC: метод Монте-Карло на цепях Маркова

Иногда нужно делать выборки из распределения p(x), которое можно вычислить (с точностью до константы), но из которого нельзя делать выборки напрямую. Байесовские апостериорные распределения — классический пример: вы знаете произведение правдоподобия и априорного распределения, но нормирующую константу трудно вычислить.

Метрополис—Хастингс строит цепь Маркова, стационарным распределением которой является p(x):

1. Начните с некоторой позиции x
2. Предложите новую позицию x’ из распределения предложений Q(x’|x)
3. Вычислите отношение принятия: a = p(x’) * Q(x|x’) / (p(x) * Q(x’|x))
4. Примите x’ с вероятностью min(1, a). В противном случае останьтесь в x.
5. Повторяйте.

Если Q симметрично (например, Q(x’|x) = Q(x|x’) = N(x, sigma^2)), отношение упрощается до a = p(x’) / p(x). Нужна только пропорция вероятностей: нормирующая константа сокращается.

При мягких условиях цепь гарантированно сходится к p(x). Но сходимость может быть медленной, если предложение слишком мало (случайное блуждание) или слишком велико (много отказов). Настройка предложения — искусство MCMC.

Почему это работает. Отношение принятия обеспечивает детальный баланс: вероятность находиться в x и перейти в x’ равна вероятности находиться в x’ и перейти в x. Детальный баланс означает, что p(x) является стационарным распределением цепи. Поэтому после достаточного числа шагов выборки происходят из p(x).

Практические соображения:

• Разогрев (burn-in): отбросьте первые N выборок. Цепи нужно время, чтобы достичь стационарного распределения из начальной точки.
• Прореживание (thinning): сохраняйте каждую k-ю выборку, чтобы уменьшить автокорреляцию.
• Несколько цепей: запустите несколько цепей из разных начальных точек. Если они сходятся к одному распределению, у вас есть свидетельство сходимости.
• Доля принятия: для гауссовских предложений в d измерениях оптимальная доля принятия составляет около 23% (Roberts & Rosenthal, 2001). Слишком высокая означает, что цепь почти не движется. Слишком низкая означает, что она всё отвергает.

Стохастические процессы в AI

Процесс	Применение в AI
Случайное блуждание	Исследование в RL, эмбеддинги Node2Vec
Цепь Маркова	Генерация текста, выборка MCMC
Броуновское движение	Диффузионные модели (прямой процесс)
Динамика Ланжевена	Генеративные модели на основе score, SGLD
Марковский процесс принятия решений	Обучение с подкреплением
Метрополис—Хастингс	Байесовский вывод, выборка из апостериорного распределения

random-walk-diffusion

Соберите это

Шаг 1: симулятор случайного блуждания

import numpy as np

def random_walk_1d(n_steps, seed=None):
    rng = np.random.RandomState(seed)
    steps = rng.choice([-1, 1], size=n_steps)
    positions = np.concatenate([[0], np.cumsum(steps)])
    return positions


def random_walk_2d(n_steps, seed=None):
    rng = np.random.RandomState(seed)
    directions = rng.choice(4, size=n_steps)
    dx = np.zeros(n_steps)
    dy = np.zeros(n_steps)
    dx[directions == 0] = 1   # right
    dx[directions == 1] = -1  # left
    dy[directions == 2] = 1   # up
    dy[directions == 3] = -1  # down
    x = np.concatenate([[0], np.cumsum(dx)])
    y = np.concatenate([[0], np.cumsum(dy)])
    return x, y

Одномерное блуждание хранит накопленные суммы. Каждый шаг равен +1 или -1. После n шагов позиция равна сумме. Дисперсия растёт линейно с n, поэтому стандартное отклонение растёт как sqrt(n).

Шаг 2: цепь Маркова

class MarkovChain:
    def __init__(self, transition_matrix, state_names=None):
        self.P = np.array(transition_matrix, dtype=float)
        self.n_states = len(self.P)
        self.state_names = state_names or [str(i) for i in range(self.n_states)]

    def step(self, current_state, rng=None):
        if rng is None:
            rng = np.random.RandomState()
        probs = self.P[current_state]
        return rng.choice(self.n_states, p=probs)

    def simulate(self, start_state, n_steps, seed=None):
        rng = np.random.RandomState(seed)
        states = [start_state]
        current = start_state
        for _ in range(n_steps):
            current = self.step(current, rng)
            states.append(current)
        return states

    def stationary_distribution(self):
        eigenvalues, eigenvectors = np.linalg.eig(self.P.T)
        idx = np.argmin(np.abs(eigenvalues - 1.0))
        stationary = np.real(eigenvectors[:, idx])
        stationary = stationary / stationary.sum()
        return np.abs(stationary)

Стационарное распределение — левый собственный вектор P с собственным значением 1. Мы находим его, вычисляя собственные векторы P^T (транспонирование превращает левые собственные векторы в правые).

Шаг 3: динамика Ланжевена

def langevin_dynamics(grad_U, x0, dt, temperature, n_steps, seed=None):
    rng = np.random.RandomState(seed)
    x = np.array(x0, dtype=float)
    trajectory = [x.copy()]
    for _ in range(n_steps):
        noise = rng.randn(*x.shape)
        x = x - dt * grad_U(x) + np.sqrt(2 * temperature * dt) * noise
        trajectory.append(x.copy())
    return np.array(trajectory)

Градиент толкает x к низкой энергии. Шум не даёт ему застрять. В равновесии распределение выборок пропорционально exp(-U(x)/temperature).

Шаг 4: Метрополис—Хастингс

def metropolis_hastings(target_log_prob, proposal_std, x0, n_samples, seed=None):
    rng = np.random.RandomState(seed)
    x = np.array(x0, dtype=float)
    samples = [x.copy()]
    accepted = 0
    for _ in range(n_samples - 1):
        x_proposed = x + rng.randn(*x.shape) * proposal_std
        log_ratio = target_log_prob(x_proposed) - target_log_prob(x)
        if np.log(rng.rand()) < log_ratio:
            x = x_proposed
            accepted += 1
        samples.append(x.copy())
    acceptance_rate = accepted / (n_samples - 1)
    return np.array(samples), acceptance_rate

Алгоритм предлагает новую точку, проверяет, обладает ли она более высокой вероятностью (либо принимает её с вероятностью, пропорциональной отношению), и повторяет процедуру. Для хорошего смешивания доля принятия должна быть около 23–50%.

Используйте это

На практике для этих алгоритмов используют устоявшиеся библиотеки. Однако понимание механики важно для отладки и настройки.

import numpy as np

rng = np.random.RandomState(42)
walk = np.cumsum(rng.choice([-1, 1], size=10000))
print(f"Final position: {walk[-1]}")
print(f"Expected distance: {np.sqrt(10000):.1f}")
print(f"Actual distance: {abs(walk[-1])}")

numpy для матриц переходов

import numpy as np

P = np.array([[0.7, 0.1, 0.2],
              [0.3, 0.4, 0.3],
              [0.4, 0.2, 0.4]])

distribution = np.array([1.0, 0.0, 0.0])
for _ in range(100):
    distribution = distribution @ P

print(f"Stationary distribution: {np.round(distribution, 4)}")

Многократно умножайте начальное распределение на P. После достаточного числа итераций оно сойдётся к стационарному распределению независимо от того, откуда вы начали. Это степенной метод нахождения доминирующего левого собственного вектора.

Связи с реальными фреймворками

• Диффузия PyTorch: DDPMScheduler в Hugging Face diffusers реализует прямую и обратную цепи Маркова
• NumPyro / PyMC: используйте MCMC (сэмплер NUTS, улучшающий Метрополиса—Хастингса) для байесовского вывода
• Gymnasium (RL): функция шага среды определяет марковский процесс принятия решений

Проверка сходимости цепи Маркова

import numpy as np

P = np.array([[0.9, 0.1], [0.3, 0.7]])

eigenvalues = np.linalg.eigvals(P)
spectral_gap = 1 - sorted(np.abs(eigenvalues))[-2]
print(f"Eigenvalues: {eigenvalues}")
print(f"Spectral gap: {spectral_gap:.4f}")
print(f"Approximate mixing time: {1/spectral_gap:.1f} steps")

Спектральная щель показывает, как быстро цепь забывает своё начальное состояние. Щель 0.2 означает примерно 5 шагов до смешивания. Щель 0.01 означает примерно 100 шагов. Всегда проверяйте это перед долгими симуляциями: медленно смешивающаяся цепь тратит вычислительные ресурсы впустую.

Выпустите это

Этот урок создаёт:

• outputs/prompt-stochastic-process-advisor.md — промпт, помогающий определить, какой фреймворк стохастических процессов применим к данной задаче

Связи

Концепция	Где встречается
Случайное блуждание	Графовые эмбеддинги Node2Vec, исследование в RL
Цепь Маркова	Генерация токенов в LLM, выборка MCMC
Броуновское движение	Прямой процесс диффузии в DDPM, модели на основе SDE
Динамика Ланжевена	Генеративные модели на основе score, стохастическая градиентная динамика Ланжевена (SGLD)
Стационарное распределение	Цель сходимости MCMC, PageRank
Метрополис—Хастингс	Выборка из байесовского апостериорного распределения, имитация отжига
Температура	Выборка LLM, больцмановское исследование в RL, имитация отжига
Время смешивания	Скорость сходимости MCMC, анализ спектральной щели
Поглощающее состояние	Токен конца последовательности, терминальные состояния в RL
Детальный баланс	Гарантия корректности MCMC-сэмплеров

Диффузионные модели заслуживают особого внимания. DDPM (Ho et al., 2020) задаёт прямую цепь Маркова:

q(x_t | x_{t-1}) = N(x_t; sqrt(1-beta_t) * x_{t-1}, beta_t * I)

где beta_t — расписание шума. После T шагов x_T приблизительно равно N(0, I). Обратный процесс параметризуется нейронной сетью, которая предсказывает шум:

p_theta(x_{t-1} | x_t) = N(x_{t-1}; mu_theta(x_t, t), sigma_t^2 * I)

Каждый шаг генерации — это шаг обученной цепи Маркова. Понимать цепи Маркова означает понимать, как и почему диффузионные модели генерируют данные.

SGLD (стохастическая градиентная динамика Ланжевена) объединяет градиентный спуск по мини-батчам с шумом Ланжевена. Вместо вычисления полного градиента вы используете стохастическую оценку и добавляете калиброванный шум. По мере уменьшения скорости обучения SGLD переходит от оптимизации к выборке: вы почти бесплатно получаете приближённые выборки из байесовского апостериорного распределения. Это один из простейших способов получить оценки неопределённости от нейронной сети.

Ключевая идея всех этих связей: стохастические процессы — не просто теоретические инструменты. Это вычислительные механизмы внутри современных AI-систем. Настраивая температуру LLM, вы регулируете цепь Маркова. Обучая диффузионную модель, вы учитесь обращать процесс, похожий на броуновское движение. Выполняя байесовский вывод, вы строите цепь, сходящуюся к апостериорному распределению.

Упражнения

1. Смоделируйте 1000 случайных блужданий по 10000 шагов. Постройте распределение конечных позиций. Убедитесь, что оно приблизительно гауссовское со средним 0 и стандартным отклонением sqrt(10000) = 100.

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

3. Реализуйте имитацию отжига с помощью Метрополиса—Хастингса. Начните с высокой температуры (принимайте почти всё) и постепенно охлаждайте систему (принимайте только улучшения). Используйте её, чтобы найти минимум функции с множеством локальных минимумов.

4. Сравните динамику Ланжевена при разных температурах. Делайте выборки из потенциала с двумя ямами U(x) = (x^2 - 1)^2. При низкой температуре выборки группируются в одной яме. При высокой они распределяются по обеим. Найдите критическую температуру, при которой цепь смешивается между ямами.

5. Реализуйте прямой процесс диффузии. Начните с одномерного сигнала (например, синусоиды). Постепенно добавляйте шум на протяжении 100 шагов с линейным расписанием шума. Покажите, как сигнал деградирует до чистого шума. Затем реализуйте простой денойзер, обращающий процесс (даже наивный, который просто вычитает оценённый шум).

Ключевые термины

Термин	Как обычно говорят	Что это на самом деле означает
Случайное блуждание	«Движение по броскам монеты»	Процесс, в котором позиция меняется случайными приращениями на каждом шаге
Марковское свойство	«Без памяти»	Будущее зависит только от текущего состояния, а не от истории
Матрица переходов	«Таблица вероятностей»	P[i][j] = вероятность перейти из состояния i в состояние j
Стационарное распределение	«Долгосрочное среднее»	Распределение pi, где pi*P = pi, — равновесие цепи
Броуновское движение	«Случайное дрожание»	Непрерывный во времени предел случайного блуждания, B(t) ~ N(0, t)
Динамика Ланжевена	«Градиентный спуск с шумом»	Правило обновления, объединяющее детерминированный градиент и случайное возмущение
MCMC	«Движение к цели»	Построение цепи Маркова, стационарное распределение которой — нужное вам
Метрополис—Хастингс	«Предложить и принять/отклонить»	Алгоритм MCMC, использующий отношения принятия для обеспечения сходимости
Температура	«Регулятор случайности»	Параметр, управляющий компромиссом между исследованием и использованием
Диффузионный процесс	«Шум на входе, шум на выходе»	Прямой: постепенно добавляет шум. Обратный: постепенно удаляет его. Генерирует данные.

Дополнительное чтение

• Ho, Jain, Abbeel (2020) — «Denoising Diffusion Probabilistic Models». Статья о DDPM, начавшая революцию диффузионных моделей. Даёт ясный вывод прямой и обратной цепей Маркова.
• Song & Ermon (2019) — «Generative Modeling by Estimating Gradients of the Data Distribution». Подход на основе score, использующий динамику Ланжевена для выборки.
• Roberts & Rosenthal (2004) — «General state space Markov chains and MCMC algorithms». Теория того, когда и почему MCMC работает.
• Norris (1997) — «Markov Chains». Стандартный учебник. Рассматривает сходимость, стационарные распределения и времена достижения.
• Welling & Teh (2011) — «Bayesian Learning via Stochastic Gradient Langevin Dynamics». Объединяет SGD с динамикой Ланжевена для масштабируемого байесовского вывода.

---

Источник: Stochastic Processes Навигация: ← 01.21 — Теория графов для машинного обучения · ↑ Фаза 1 — Математические основы · Полный каталог · → 02.01 — Что такое машинное обучение