Мартингал

Материал из MachineLearning.

Версия от 11:33, 15 июля 2026; Oleg Aleksandrov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Статья написана с использованием LLM Qwen3.7-Max thinkingи проверена участником Oleg Aleksandrov 15:33, 15 июля 2026 (MSD)

Мартингал — фундаментальное понятие теории вероятностей и стохастических процессов, описывающее систему, в которой математическое ожидание следующего состояния при условии всей доступной на текущий момент информации в точности равно текущему состоянию. В контексте машинного обучения концепция мартингалов служит строгим математическим каркасом для анализа сходимости алгоритмов оптимизации, доказательства корректности методов, таких как Обучение с подкреплением (англ. Reinforcement Learning, RL), построения доверительных интервалов в задачах онлайн-обучения (англ. Online Learning) и изучения динамики диффузионных моделей (англ. Diffusion Models).

Интуитивно мартингал описывает концепцию «честной игры»: зная всю историю прошлых ходов, невозможно предсказать направление будущего изменения капитала. В машинном обучении сами данные или значения функции потерь (англ. loss function) редко образуют «честную игру» — при успешном обучении ошибка монотонно убывает, что соответствует свойству супермартингала. Однако шум, ошибки аппроксимации и стохастические градиенты в правильно настроенных алгоритмах формируют мартингальные структуры, что позволяет строго доказывать их сходимость.

Математический аппарат

Строгое определение

Пусть задано вероятностное пространство $(\Omega, \mathcal{F}, P)$ и фильтрация $\mathbb{F} = (\mathcal{F}_n)_{n \ge 0}$ — неубывающая последовательность $\sigma$ -алгебр ( $\mathcal{F}_0 \subseteq \mathcal{F}_1 \subseteq \dots \subseteq \mathcal{F}$ ), где $\mathcal{F}_n$ интерпретируется как информация, доступная на шаге $n$ (например, история всех мини-батчей до эпохи $n$ ).

Стохастический процесс $X = (X_n)_{n \ge 0}$ называется мартингалом относительно фильтрации $\mathbb{F}$ , если выполняются три условия:

Адаптированность: $X_n$ является $\mathcal{F}_n$ -измеримой случайной величиной для всех $n$ .
Интегрируемость: $\mathbb{E}[|X_n|] < \infty$ для всех $n$ .
Мартингальное свойство: для любого $n \ge 0$ выполняется:

$\mathbb{E}[X_{n+1} \mid \mathcal{F}_n] = X_n$

Если в третьем условии знак равенства заменяется на неравенство, процесс называют:

Субмартингалом, если $\mathbb{E}[X_{n+1} \mid \mathcal{F}_n] \ge X_n$ (процесс в среднем растет).
Супермартингалом, если $\mathbb{E}[X_{n+1} \mid \mathcal{F}_n] \le X_n$ (процесс в среднем убывает).

Последовательность мартингальных разностей

В алгоритмах машинного обучения чаще работают не с самими мартингалами, а с их приращениями. Последовательность случайных величин $\xi = (\xi_n)_{n \ge 1}$ называется последовательностью мартингальных разностей (англ. Martingale Difference Sequence, MDS) относительно $\mathbb{F}$ , если:

$\xi_n$ адаптирована к $\mathcal{F}_n$ .
$\mathbb{E}[|\xi_n|] < \infty$ .
$\mathbb{E}[\xi_{n+1} \mid \mathcal{F}_n] = 0$ .

Любой мартингал $X_n$ можно представить как сумму начального значения и последовательности мартингальных разностей: $X_n = X_0 + \sum_{i=1}^n \xi_i$ . Свойство MDS служит ключом к доказательству того, что шум в стохастическом градиенте не накапливается бесконечно, а взаимно уничтожается в долгосрочной перспективе.

Фундаментальные теоремы

Неравенство Азумы-Хёфдинга

Если $(\xi_n)$ — MDS, и разности ограничены почти наверное ( $|\xi_n| \le c_n$ ), то для суммы $S_n = \sum_{i=1}^n \xi_i$ справедлива экспоненциальная оценка концентрации:

$P(|S_n| \ge t) \le 2 \exp\left( - \frac{t^2}{2 \sum_{i=1}^n c_i^2} \right)$

Применяется для построения доверительных интервалов в условиях не-i.i.d. данных, например, в задачах многоруких бандитов (англ. Multi-Armed Bandits).

Теорема о сходимости мартингалов Дуба

Если $X_n$ — супермартингал, ограниченный снизу, то он сходится почти наверное к конечной случайной величине $X_\infty$ . Используется для доказательства сходимости алгоритмов оптимизации и функций Ляпунова.

Теорема Роббинса-Сигмунда

Обобщение теоремы Дуба, критически важное для стохастической аппроксимации (англ. stochastic approximation). Пусть $V_n, \alpha_n, \beta_n, \gamma_n$ — неотрицательные адаптированные последовательности, и выполняется:

$\mathbb{E}[V_{n+1} \mid \mathcal{F}_n] \le (1 + \alpha_n)V_n - \beta_n + \gamma_n$

Если $\sum \alpha_n < \infty$ и $\sum \gamma_n < \infty$ почти наверное, то $V_n$ сходится почти наверное к конечной случайной величине, и $\sum \beta_n < \infty$ . Служит стандартным инструментом доказательства сходимости стохастического градиентного спуска (англ. Stochastic Gradient Descent, SGD) и Q-learning.

Применение в машинном обучении и ИИ

Стохастический градиентный спуск

В задачах глубокого обучения минимизируется эмпирический риск $L(\theta) = \frac{1}{N} \sum_{i=1}^N l_i(\theta)$ . На каждом шаге $t$ происходит обновление весов:

$\theta_{t+1} = \theta_t - \alpha_t g_t$

где $g_t = \nabla l_{i_t}(\theta_t)$ — стохастический градиент по случайному батчу. Градиент раскладывается на истинный градиент и шум:

$g_t = \nabla L(\theta_t) + \xi_t$

Поскольку батч выбирается независимо от прошлого при условии текущих весов $\theta_t$ , математическое ожидание шума равно нулю: $\mathbb{E}[\xi_t \mid \mathcal{F}_t] = 0$ . Шум $\xi_t$ образует последовательность мартингальных разностей.

С помощью теоремы Роббинса-Сигмунда доказывается, что при условиях Роббинса-Монро на learning rate ( $\sum \alpha_t = \infty$ и $\sum \alpha_t^2 < \infty$ ) последовательность весов $\theta_t$ сходится к стационарной точке. Мартингальная природа шума объясняет способность SGD находить хорошие минимумы: шум не имеет систематического смещения (bias) и в среднем не уводит оптимизатор в неверном направлении.

В адаптивных оптимизаторах (Adam, RMSprop) learning rate $\alpha_t$ становится случайной величиной, зависящей от истории градиентов. Это нарушает независимость шага от текущего шума, и последовательность эффективных градиентов перестает быть классическим MDS, что усложняет теоретические доказательства сходимости и требует модификаций вроде AMSGrad.

Обучение с подкреплением

В RL концепция мартингалов лежит в основе доказательства сходимости алгоритмов Temporal Difference (TD), таких как Q-learning.

Процесс накопленной награды с учетом текущей оценки:

$M_t = \sum_{k=0}^{t-1} \gamma^k R_k + \gamma^t V^\pi(S_t)$

является мартингалом относительно истории траектории. Приращения этого мартингала равны дисконтированным TD-ошибкам:

$\delta_t = R_{t+1} + \gamma V^\pi(S_{t+1}) - V^\pi(S_t)$

Так как $M_t$ — мартингал, $\mathbb{E}[\delta_t \mid \mathcal{F}_t] = 0$ .

При обучении Q-learning агент обновляет Q-функцию, используя наблюдаемую TD-ошибку. Разница между фактическим обновлением и истинным оператором Беллмана формирует MDS. Применяя теорию стохастической аппроксимации (в частности, теорему Боркара о сходимости асинхронных стохастических аппроксимаций), исследователи доказывают сходимость Q-learning к оптимальной Q-функции $Q^*$ с вероятностью 1, несмотря на сильную коррелированность данных, генерируемых самой обучаемой моделью.

Многорукие бандиты и онлайн-обучение

В задачах онлайн-обучения (рекомендательные системы, A/B тесты) алгоритм сам выбирает, какие данные собирать (adaptive data collection). Это нарушает классическое предположение о независимости наблюдений, из-за чего стандартный закон больших чисел и неравенство Хёфдинга неприменимы напрямую.

Здесь применяется неравенство Азумы-Хёфдинга для мартингалов. В алгоритмах типа Upper Confidence Bound (UCB) оценка средней награды для «руки» (arm) $a$ после $T$ вытягиваний является суммой MDS. Это позволяет построить строгий доверительный интервал: с вероятностью $1-\delta$ истинное среднее лежит в пределах оценки плюс бонус за неопределенность, пропорциональный $\sqrt{\frac{\log(1/\delta)}{T}}$ . Математический аппарат мартингалов обеспечивает доказательство суб-линейного регрета (sublinear regret) в бандитах.

Ранняя остановка

В глубоком обучении повсеместно используется Ранняя остановка (англ. Early Stopping) — прерывание обучения, когда ошибка на валидационной выборке перестает уменьшаться, что помогает избежать переобучения (англ. overfitting). С точки зрения теории вероятностей, это связано с теоремой Дуба об опциональной остановке (Optional Stopping Theorem).

Если процесс валидационной ошибки $L_{val}(\theta_t)$ ведет себя как супермартингал, теорема об опциональной остановке утверждает, что математическое ожидание значения процесса в момент остановки $\tau$ (где $\tau$ — марковский момент, зависящий только от прошлого) равно начальному значению, при условии ограниченности времени или приращений. Корректный Early Stopping не вносит систематической ошибки в оценку обобщающей способности модели, если правило остановки адаптировано к фильтрации и не «заглядывает в будущее».

Диффузионные модели

В современных генеративных моделях процесс генерации описывается стохастическими дифференциальными уравнениями (SDE):

$dx = f(x, t)dt + g(t)dw$

где $w$ — винеровский процесс (броуновское движение, являющееся непрерывным мартингалом).

Для обращения этого процесса (reverse-time SDE) используется теорема Гирсанова и концепция эквивалентности мартингальных мер. Скоринговая функция (англ. score function) $\nabla_x \log p_t(x)$ , которую предсказывает нейросеть, тесно связана с производной Радона-Никодима и мартингальным представлением. Понимание мартингальных свойств винеровского процесса необходимо для вывода Evidence Lower Bound (ELBO) в непрерывном времени и доказательства того, что обратный SDE-процесс сэмплирует из целевого распределения данных.

Связанные концепции

Марковские цепи (англ. Markov chains): любой марковский процесс с постоянным математическим ожиданием является мартингалом. В RL среда моделируется как Марковский процесс принятия решений (англ. Markov Decision Process, MDP), что делает аппарат мартингалов применимым к траекториям агента.
Стохастическая аппроксимация (Роббинса-Монро): общий класс итеративных алгоритмов поиска корней функций, зашумленных мартингальным шумом. SGD и Q-learning служат частными случаями стохастической аппроксимации.
Функции Ляпунова: в теории управления и анализе сходимости нелинейных алгоритмов ИИ функции Ляпунова часто конструируются так, чтобы быть супермартингалами относительно стохастической динамики системы.

Литература

Sutton R. S., Barto A. G. Reinforcement Learning: An Introduction. — 2nd ed. — Cambridge, MA: MIT Press, 2018.
Borkar V. S. Stochastic Approximation: A Dynamical Systems Viewpoint. — Cambridge: Cambridge University Press, 2009.
Lattimore T., Szepesvári C. Bandit Algorithms. — Cambridge: Cambridge University Press, 2020.
Robbins H., Monro S. A Stochastic Approximation Method // The Annals of Mathematical Statistics. — 1951. — Т. 22. — № 3. — С. 400—407.
Robbins H., Siegmund D. A convergence theorem for nonnegative almost supermartingales and some applications // Optimizing Methods in Statistics. — Academic Press, 1971. — С. 233—257.
Azuma K. Weighted sums of certain dependent random variables // Tohoku Mathematical Journal. — 1967. — Т. 19. — № 3. — С. 357—367.
Song Y., Sohl-Dickstein J., Kingma D. P., Kumar A., Ermon S., Poole B. Score-Based Generative Modeling through Stochastic Differential Equations // International Conference on Learning Representations (ICLR). — 2021.

Источник — «http://recognition.su/wiki/index.php?title=%D0%9C%D0%B0%D1%80%D1%82%D0%B8%D0%BD%D0%B3%D0%B0%D0%BB»