Случайные процессы
Stochastic в ML и Systems
SGD, который обучает каждую нейронную сеть - это стохастический процесс. Stable Diffusion и DALL-E - это СДУ. Серверная инфраструктура под вашими ML-моделями описывается теорией массового обслуживания. Стохастические процессы - не абстрактная математика, а рабочий инструмент ML-инженера.
- **Обучение нейронных сетей** - SGD как Langevin динамика; условия Роббинса-Монро для выбора learning rate schedule
- **Генеративные модели (DDPM, Stable Diffusion)** - форвардный и обратный SDE; score matching как задача аппроксимации score функции
- **ML-инфраструктура** - batching inference через теорию очередей; tail latency через M/G/1 с тяжёлым хвостом
Предварительные знания
Сходимость SGD как стохастический процесс
Стохастический градиентный спуск (SGD) - это случайный процесс: каждый шаг зависит от случайной подвыборки данных. Траектория θ_0, θ_1, θ_2, ... в пространстве параметров - это марковская цепь (следующее состояние зависит только от предыдущего). Анализ сходимости SGD через теорию мартингалов и стохастических процессов объясняет, почему уменьшение learning rate необходимо и достаточно для сходимости.
**SGD как стохастический процесс:** θ_{t+1} = θ_t - η_t · ∇̃L(θ_t) где ∇̃L(θ_t) = ∇L(θ_t) + ξ_t - стохастический градиент (истинный + шум). **Условия Роббинса-Монро для сходимости:** ∑ η_t = ∞ (шаги достаточно большие, чтобы добраться до оптимума) ∑ η_t² < ∞ (шаги достаточно малые, чтобы не «прыгать» навсегда) Типичный выбор: η_t = η₀ / t (полиномиальное убывание) или η_t = η₀ / √t.
**Связь с броуновским движением:** при малом η_t и большом числе шагов траектория SGD приближается к **Langevin SDE**: dθ = -∇L(θ)dt + √(2T) dB, где T - «температура» (масштаб шума). Это позволяет анализировать SGD инструментами теории СДУ и даёт теоретическое обоснование для SGD как MCMC (Langevin Monte Carlo - сэмплирование из апостериора весов нейронной сети).
| Режим SGD | Условие η_t | Поведение вблизи оптимума | Применение |
|---|---|---|---|
| Убывающий η | ∑η_t=∞, ∑η_t²<∞ | Сходится п.н. к оптимуму | Классическая оптимизация |
| Постоянный η | η_t = const | Флуктуирует, E[‖θ-θ*‖²] ~ η·σ² | Онлайн-обучение, SGLD |
| Циклический (cosine) | η_t = cosine decay | Эффект «переохлаждения» | Обучение трансформеров |
| Warmup + decay | η_t = warmup·schedule | Стабилизация в начале | BERT, GPT обучение |
Роббинс и Монро, 1951
Условия Роббинса-Монро были сформулированы в 1951 году для стохастической аппроксимации - нахождения нуля функции через зашумлённые наблюдения. Оказалось, что те же условия управляют сходимостью SGD в машинном обучении. В 2011 году Уэллинг и Те предложили SGLD (Stochastic Gradient Langevin Dynamics) - добавление гауссовского шума с правильным масштабом превращает SGD в MCMC-сэмплер.
SGD - это просто GD с шумом, и теория для них одинакова
SGD - это марковская цепь в пространстве параметров. Его сходимость требует специальных условий (Роббинс-Монро), а поведение вблизи оптимума описывается СДУ Ланжевена. Теория GD в детерминированном случае здесь неприменима напрямую
Градиент в GD - детерминированный, поэтому достаточен постоянный rate. В SGD каждый шаг случаен: суммарная дисперсия должна быть конечной (∑η_t² < ∞), иначе θ_t не сходится к точке, а флуктуирует в окрестности
SGD с η_t = 0.01 / t (убывающий) обучается медленнее, чем с η = 0.01 (постоянный). Почему всё равно предпочтителен убывающий rate для теоретических гарантий сходимости?
Случайные графы и распространение информации
Социальные сети, транспортные маршруты, нейронные связи - все это графы, построенные случайно. **Модель Эрдёша-Реньи G(n, p)** - n вершин, каждое ребро существует независимо с вероятностью p - простейшая модель случайного графа. Через неё можно анализировать распространение информации, вирусов, слухов. Ключевой вопрос: при каком p граф становится связным?
**Модель Эрдёша-Реньи G(n, p):** - Число рёбер: Bin(n(n-1)/2, p), в среднем p·n(n-1)/2 - Ожидаемая степень: (n-1)p **Пороговые явления:** - p < 1/n: граф состоит из малых компонент, крупнейшая ~ log n - p = 1/n: пороговое значение - появляется гигантская компонента - p > (1+ε)/n: гигантская компонента охватывает долю Θ(1) вершин - p > log(n)/n: граф связен п.н. **Распространение по графу** - марковский процесс на состояниях вершин.
**Пороговые явления в графах** - это фазовые переходы: небольшое изменение p меняет структуру графа качественно. Аналогичные пороговые явления встречаются в распределённых системах: **epidemic gossip protocols** (как Cassandra распространяет изменения схемы), **consensus algorithms** (кворум - это граф связности при отказах), **percolation** (связность кластера серверов при частичных отказах).
| Пороговое значение p | Структура графа | Аналог в системах |
|---|---|---|
| p < 1/n | Только маленькие компоненты | Сеть «распалась» на изолированные кластеры |
| p ≈ 1/n | Гигантская компонента возникает | Пороговая связность при gossip |
| p > log(n)/n | Полная связность | Broadcast достигает всех узлов |
| p = c/n (c>1) | Гигантская компонента ~ βn вершин | β зависит от c нелинейно |
В случайном графе G(n, p) при p > 0 все вершины связны с ненулевой вероятностью
При p < log(n)/n с высокой вероятностью существуют изолированные вершины (степень 0). Порог связности - именно p = log(n)/n: только выше него граф связен п.н.
Изолированная вершина имеет вероятность (1-p)^{n-1} ≈ e^{-pn}. При p = log(n)/n: P(изолированная) ≈ 1/n. Ожидаемое число изолированных ≈ 1. Это критическая точка: ниже порога изолированные вершины есть, выше - нет
В G(1000, p) при каком p граф становится связным с высокой вероятностью?
Очереди в распределённых системах
В реальных системах задача сложнее M/M/1: GPU кластер обрабатывает batch-запросы к LLM, несколько реплик балансируют нагрузку, inference занимает переменное время. Применение теории очередей к ML-инфраструктуре - прямая практическая ценность стохастических процессов для ML-инженера.
**Ключевые модели для ML-систем:** **M/M/c (c серверов):** Ожидаемое время = (C(c, ρ) / (c·μ·(1-ρ/c))) + 1/μ где C(c, ρ) - формула Эрланга-C, ρ = λ/(cμ) **Batching (группировка запросов):** При батч-обработке B запросов вместе время обработки τ(B) растёт субпропорционально B (GPU эффективен). Оптимальный батч: minimize E[wait] + E[processing] по B. **Incast проблема:** Одновременные ответы N микросервисов на один запрос - пуассоновский поток с лавиной. P(хотя бы один > T) → 1 при N → ∞.
**Проблема хвостовых задержек (tail latency)** особенно важна в ML-системах: P99 latency может быть в 10× выше медианы из-за garbage collection, cold start контейнеров, или вариабельности inference. Модель M/G/1 с формулой Поллачека-Хинчина показывает: снижение CV (коэффициента вариации) времени обработки - главный рычаг. Hedging запросов (отправить запрос нескольким репликам, взять первый ответ) снижает CV хвоста.
| Паттерн системы | Модель очереди | Ключевая метрика | Оптимизация |
|---|---|---|---|
| LLM inference (single) | M/G/1 | W = E[S]/(1-ρ) · (1+CV²)/2 | Снизить CV через batching |
| Load balancer + N реплик | M/M/N | Формула Эрланга-C | Горизонтальное масштабирование |
| Batch inference | M[X]/G/1 (bulk) | Компромисс wait vs throughput | Оптимальный batch size |
| Streaming (autoregressive) | Цепочка M/M/1 | Суммарная задержка цепи | Сети Джексона |
Линейное масштабирование: N серверов = N-кратное улучшение latency
Улучшение при добавлении серверов нелинейно. При низкой нагрузке (ρ≪1) второй сервер почти не помогает. При высокой нагрузке (ρ→1) второй сервер снижает ожидание экспоненциально. Это формула Эрланга-C
Очередь нелинейно зависит от загрузки: L = ρ/(1-ρ). При ρ=0.9 → L=9; при ρ=0.45 (два сервера, та же λ) → L=0.82. Снижение в 11 раз от удвоения числа серверов. Это именно нелинейность теории массового обслуживания
LLM inference сервис: λ=10 req/s, μ=12 req/s (экспоненциальное). При добавлении второй реплики (M/M/2) как изменится среднее время ожидания в очереди?
Диффузионные генеративные модели
Stable Diffusion, DALL-E 3, Sora - за всеми этими моделями стоит одна идея: постепенно добавить гауссовский шум к изображению (форвардный процесс) и научить нейронную сеть обратному - убирать шум (обратный процесс). Форвардный процесс - это СДУ Ито; обратный - тоже СДУ, связанное с форвардным через score function ∇ₓ log p(x).
**DDPM (Denoising Diffusion Probabilistic Models):** Форвардный процесс (добавление шума): dxₜ = -½β(t)xₜ dt + √β(t) dBₜ Это СДУ Орнштейна-Уленбека: начальное изображение x₀ постепенно превращается в N(0,I). Обратный процесс (генерация изображения): dxₜ = [-½β(t)xₜ - β(t)·∇ₓ log p_t(xₜ)] dt + √β(t) dB̃ₜ где ∇ₓ log p_t(x) - score function: нейронная сеть s_θ(x, t) обучается её аппроксимировать.
**Score matching:** нейронная сеть s_θ(x, t) аппроксимирует ∇ₓ log p_t(x) - градиент логарифма плотности по x. Это позволяет написать обратный SDE без знания нормировочной константы. Эквивалентно DDPM: предсказывать добавленный шум ε тождественно предсказыванию score (с точностью до масштаба). Это элегантная связь теории стохастических процессов и современной генеративной AI.
| Модель | Форвардный SDE | Обратный SDE | Самплер |
|---|---|---|---|
| DDPM | dX = -X/2 dt + dB (OU) | Обратный OU со score | DDPM (1000 шагов) |
| DDIM | Тот же форвард | Детерминированный ODE | DDIM (50 шагов) |
| Score SDE (VP) | dX = -β(t)/2 X dt + √β(t) dB | Обратный с score | Euler-Maruyama |
| Flow Matching | ODE: dX = v_θ(X,t)dt | Прямое v_θ | Euler ODE (10-20 шагов) |
DDPM учит нейросеть «рисовать изображения»
DDPM учит нейросеть оценивать score function ∇ₓ log p_t(x) - градиент логарифма плотности, или эквивалентно - предсказывать добавленный шум ε. Это позволяет обратить форвардный SDE и сэмплировать из p(x₀)
Нейросеть не хранит изображения и не «знает» как они выглядят. Она учится на парах (x_t, ε) предсказывать шум, добавленный на шаге t. Через score функцию это эквивалентно описанию геометрии пространства данных
Форвардный процесс DDPM - это СДУ Орнштейна-Уленбека. Что происходит с исходным изображением x₀ при t → ∞?
Ключевые идеи
- **SGD** - марковская цепь в пространстве параметров; сходимость требует условий Роббинса-Монро; связь с Langevin SDE
- **Случайные графы** G(n,p) - пороговые явления при p = 1/n (гигантская компонента) и log(n)/n (связность); применение в gossip-протоколах
- **Очереди в ML-системах** - M/M/c для реплик, M/G/1 для inference с вариабельным CV; оптимальный batching через компромисс задержки и пропускной способности
- **Диффузионные модели** - форвардный OU-SDE стирает информацию; обратный SDE с score function генерирует; DDPM = предсказание шума ≡ предсказание score
Связанные темы
Stochastic в ML объединяет весь курс в практических приложениях:
- MCMC и сэмплирование — SGD с шумом (SGLD) - это MCMC; диффузионные модели генерируют через обратный SDE аналогично Langevin MCMC
- Стохастические дифференциальные уравнения — DDPM форвардный/обратный процесс - это конкретные СДУ; численное решение через Эйлер-Маруяма = DDPM inference
- Теория массового обслуживания — M/G/1, сети Джексона - основа анализа latency и throughput ML-сервисов
Вопросы для размышления
- SGLD добавляет гауссовский шум к каждому шагу SGD. При каких условиях это превращается в корректный MCMC-сэмплер апостериорного распределения весов?
- В DDPM score функция ∇ₓ log p_t(x) нужна для обратного процесса. Что физически означает этот вектор для промежуточного зашумлённого изображения x_t?
- P99 latency inference сервиса в 10× выше медианы. Применяя формулу P-K для M/G/1: что нужно изменить в дизайне сервиса чтобы снизить P99?