Мартингал

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

(Различия между версиями)

Текущая версия

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

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

Интуиция

Концепция «честной игры»

В классической теории вероятностей мартингал формализует понятие честной игры (англ. fair game). Представьте себе игрока в казино, чей капитал в момент времени $t$ равен $X_t$ . Если игра абсолютно честная, то, зная всю историю прошлых ставок и выпадений шарика (информацию $\mathcal{F}_t$ ), игрок не может придумать стратегию, которая гарантированно увеличит его капитал. Математическое ожидание его богатства на следующем шаге в точности равно его текущему богатству: $\mathbb{E}[X_{t+1} \mid \mathcal{F}_t] = X_t$ . Будущее изменение капитала полностью непредсказуемо и симметрично: вероятность выиграть ровно равна вероятности проиграть.

В терминах случайных блужданий мартингал — это блуждание без дрейфа (англ. drift). Частица может двигаться хаотично, но у неё нет систематического смещения ни в одну из сторон.

Мартингалы и супермартингалы в оптимизации

В машинном обучении мы, напротив, не хотим, чтобы процесс обучения был честной игрой. Наша цель — минимизировать функцию потерь (англ. loss function) $L(\theta_t)$ . Если алгоритм работает корректно, то ошибка на каждом шаге в среднем должна уменьшаться. Следовательно, последовательность значений функции потерь должна быть супермартингалом:

$\mathbb{E}[L(\theta_{t+1}) \mid \mathcal{F}_t] \le L(\theta_t)$

Алгоритм оптимизации (например, SGD) намеренно «подкручивает» игру в нашу пользу, добавляя отрицательный дрейф (сигнал истинного градиента), который тянет систему вниз, к минимуму.

Где же тогда сам мартингал?

Если функция потерь — это супермартингал (сигнал + шум), то чистым мартингалом (или, точнее, последовательностью мартингальных разностей, MDS) выступает именно шум.

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

Информационная фильтрация

Ключевым элементом интуиции является понятие фильтрации $\mathbb{F} = (\mathcal{F}_t)$ — формализации «памяти» или «контекста» системы. В глубоком обучении $\mathcal{F}_t$ — это вся история весов, градиентов и состояний оптимизатора (например, скользящих средних в Adam) к шагу $t$ .

Утверждение « $X$ — мартингал» всегда по умолчанию предполагает ответ на вопрос: «Мартингал относительно чего?». Процесс может быть мартингалом относительно своей собственной истории, но перестать быть им, если мы добавим в фильтрацию какую-то скрытую переменную из будущего или из внешней среды. Понимание того, какая именно информация доступна модели в момент принятия решения, критически важно для корректного применения теорем о сходимости в RL и онлайн-обучении, где агент активно влияет на генерацию будущих данных.

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

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

Пусть задано вероятностное пространство $(\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-процесс сэмплирует из целевого распределения данных.

См. также

Литература

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»

@@ Строка 2: / Строка 2: @@
-'''Мартингал''' — фундаментальное понятие теории вероятностей и стохастических процессов, описывающее систему, в которой математическое ожидание следующего состояния при условии всей доступной на текущий момент информации в точности равно текущему состоянию. В контексте машинного обучения концепция мартингалов служит строгим математическим каркасом для анализа сходимости алгоритмов оптимизации, доказательства корректности методов, таких как [[Обучение с подкреплением]] (англ. Reinforcement Learning, RL), построения доверительных интервалов в задачах [[Онлайн-обучение|онлайн-обучения]] (англ. Online Learning) и изучения динамики [[Диффузионные модели|диффузионных моделей]] (англ. Diffusion Models).
+'''Мартингал''' — фундаментальное понятие теории вероятностей и стохастических процессов, описывающее систему, в которой математическое ожидание следующего состояния при условии всей доступной на текущий момент информации в точности равно текущему состоянию. В контексте [[машинное обучение|машинного обучения]] концепция мартингалов служит строгим математическим каркасом для анализа сходимости алгоритмов оптимизации, доказательства корректности методов, таких как [[Обучение с подкреплением]] (англ. Reinforcement Learning, RL), построения доверительных интервалов в задачах [[Онлайн-обучение|онлайн-обучения]] (англ. Online Learning) и изучения динамики [[Диффузионные модели|диффузионных моделей]] (англ. Diffusion Models).
+== Интуиция ==
+=== Концепция «честной игры» ===
+В классической теории вероятностей мартингал формализует понятие ''честной игры'' (англ. fair game). Представьте себе игрока в казино, чей капитал в момент времени <tex>t</tex> равен <tex>X_t</tex>. Если игра абсолютно честная, то, зная всю историю прошлых ставок и выпадений шарика (информацию <tex>\mathcal{F}_t</tex>), игрок не может придумать стратегию, которая гарантированно увеличит его капитал. Математическое ожидание его богатства на следующем шаге в точности равно его текущему богатству: <tex>\mathbb{E}[X_{t+1} \mid \mathcal{F}_t] = X_t</tex>. Будущее изменение капитала полностью непредсказуемо и симметрично: вероятность выиграть ровно равна вероятности проиграть.
+В терминах случайных блужданий мартингал — это блуждание без ''дрейфа'' (англ. drift). Частица может двигаться хаотично, но у неё нет систематического смещения ни в одну из сторон.
+=== Мартингалы и супермартингалы в оптимизации ===
+В машинном обучении мы, напротив, '''не хотим''', чтобы процесс обучения был честной игрой. Наша цель — минимизировать [[Функция потерь|функцию потерь]] (англ. loss function) <tex>L(\theta_t)</tex>. Если алгоритм работает корректно, то ошибка на каждом шаге в среднем должна уменьшаться. Следовательно, последовательность значений функции потерь должна быть '''супермартингалом''':
+::<tex>\mathbb{E}[L(\theta_{t+1}) \mid \mathcal{F}_t] \le L(\theta_t)</tex>
+Алгоритм оптимизации (например, [[Стохастический градиентный спуск|SGD]]) намеренно «подкручивает» игру в нашу пользу, добавляя отрицательный дрейф (сигнал истинного градиента), который тянет систему вниз, к минимуму.
+=== Где же тогда сам мартингал? ===
+Если функция потерь — это супермартингал (сигнал + шум), то '''чистым мартингалом''' (или, точнее, последовательностью мартингальных разностей, MDS) выступает именно '''шум'''.
+* В SGD стохастический градиент по мини-батчу отличается от истинного градиента на некоторую величину <tex>\xi_t</tex>.
+* Поскольку батч выбирается случайно и независимо от прошлых шагов, этот шум не имеет предпочтительного направления: <tex>\mathbb{E}[\xi_t \mid \mathcal{F}_t] = 0</tex>.
+* Шум образует мартингальную структуру. Именно мартингальная природа шума гарантирует, что ошибки аппроксимации не накапливаются в одну сторону (не создают систематического смещения, англ. bias), а взаимно уничтожаются на длинной дистанции, позволяя алгоритму сходиться.
+=== Информационная фильтрация ===
+Ключевым элементом интуиции является понятие '''фильтрации''' <tex>\mathbb{F} = (\mathcal{F}_t)</tex> — формализации «памяти» или «контекста» системы. В глубоком обучении <tex>\mathcal{F}_t</tex> — это вся история весов, градиентов и состояний оптимизатора (например, скользящих средних в Adam) к шагу <tex>t</tex>.
+Утверждение «<tex>X</tex> — мартингал» всегда по умолчанию предполагает ответ на вопрос: «Мартингал ''относительно чего''?». Процесс может быть мартингалом относительно своей собственной истории, но перестать быть им, если мы добавим в фильтрацию какую-то скрытую переменную из будущего или из внешней среды. Понимание того, какая именно информация доступна модели в момент принятия решения, критически важно для корректного применения теорем о сходимости в RL и онлайн-обучении, где агент активно влияет на генерацию будущих данных.
-Интуитивно мартингал описывает концепцию «честной игры»: зная всю историю прошлых ходов, невозможно предсказать направление будущего изменения капитала. В машинном обучении сами данные или значения [[Функция потерь|функции потерь]] (англ. loss function) редко образуют «честную игру» — при успешном обучении ошибка монотонно убывает, что соответствует свойству ''супермартингала''. Однако шум, ошибки аппроксимации и стохастические градиенты в правильно настроенных алгоритмах формируют мартингальные структуры, что позволяет строго доказывать их сходимость.
 == Математический аппарат ==
@@ Строка 85: / Строка 108: @@
 Для обращения этого процесса (reverse-time SDE) используется теорема Гирсанова и концепция эквивалентности мартингальных мер. [[Скоринговая функция]] (англ. score function) <tex>\nabla_x \log p_t(x)</tex>, которую предсказывает нейросеть, тесно связана с производной Радона-Никодима и мартингальным представлением. Понимание мартингальных свойств винеровского процесса необходимо для вывода Evidence Lower Bound (ELBO) в непрерывном времени и доказательства того, что обратный SDE-процесс сэмплирует из целевого распределения данных.
+<!--
 == Связанные концепции ==
 * '''[[Марковские цепи]] (англ. Markov chains):''' любой марковский процесс с постоянным математическим ожиданием является мартингалом. В RL среда моделируется как [[Марковский процесс принятия решений]] (англ. Markov Decision Process, MDP), что делает аппарат мартингалов применимым к траекториям агента.
 * '''Стохастическая аппроксимация (Роббинса-Монро):''' общий класс итеративных алгоритмов поиска корней функций, зашумленных мартингальным шумом. SGD и Q-learning служат частными случаями стохастической аппроксимации.
 * '''Функции Ляпунова:''' в теории управления и анализе сходимости нелинейных алгоритмов ИИ функции Ляпунова часто конструируются так, чтобы быть супермартингалами относительно стохастической динамики системы.
+-->
 == См. также ==
-* [[Стохастический градиентный спуск]] (англ. Stochastic Gradient Descent)
+* [[Стохастический градиентный спуск]]
-* [[Обучение с подкреплением]] (англ. Reinforcement Learning)
+* [[Обучение с подкреплением]]
-* [[Стохастическая аппроксимация]] (англ. Stochastic Approximation)
+* [[Стохастическая аппроксимация]]
-* [[Многорукие бандиты]] (англ. Multi-Armed Bandits)
+* [[Многорукие бандиты]]
-* [[Диффузионные модели]] (англ. Diffusion Models)
+* [[Диффузионные модели]]
-* [[Винеровский процесс]] (англ. Wiener process)
+* [[Винеровский процесс]]
-* [[Концентрация меры]] (англ. Concentration of measure)
+* [[Концентрация меры]]
-* [[Функция Ляпунова]] (англ. Lyapunov function)
-* [[Теорема Гирсанова]] (англ. Girsanov's theorem)
-* [[Производная Радона-Никодима]] (англ. Radon-Nikodym derivative)
 == Литература ==