Ансамблевые методы Монте-Карло

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

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

Перейти к: навигация, поиск

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

Статья написана с использованием LLM Qwen3.7-Max и проверена участником Arsen Temirov 00:27, 20 июля 2026 (MSD)

Промпт приводится полностью в Обсуждение:Ансамблевые методы Монте-Карло

Содержание

1 Мотивация
2 Формальная постановка
3 Основные алгоритмы
4 Применение в машинном обучении
5 Вычислительные аспекты и современные направления
6 Ограничения
7 См. также
8 Литература

Ансамблевые методы Монте-Карло (англ. Ensemble Monte Carlo, EMC) — семейство стохастических алгоритмов для оценки математических ожиданий, численного интегрирования и сэмплирования из сложных многомерных распределений. В отличие от классических методов Монте-Карло по цепям Маркова (англ. Markov Chain Monte Carlo, MCMC), где каждая цепь эволюционирует изолированно, EMC оперирует ансамблем — набором из $K$ взаимодействующих состояний (частиц, «блуждателей»). Геометрия целевого пространства передаётся между элементами ансамбля на каждом шаге, что позволяет алгоритму исследовать мультимодальные распределения и пространства с сильными корреляциями без ручной настройки метрики.

В машинном обучении и искусственном интеллекте ансамблевые методы применяются для байесовского вывода (англ. Bayesian inference), оценки неопределённости (англ. Uncertainty Quantification), байесовской оптимизации (англ. Bayesian optimization), а также в генеративных моделях и обучении с подкреплением (англ. reinforcement learning).

Мотивация

Классические алгоритмы MCMC — Метрополиса — Гастингса (англ. Metropolis–Hastings), сэмплер Гиббса (англ. Gibbs sampler) — страдают от медленного перемешивания (англ. slow mixing). Если целевое распределение обладает несколькими изолированными модами или вытянуто вдоль изогнутых многообразий, одиночный блуждатель застревает в одной моде на время, экспоненциально растущее с высотой барьера.

Ансамблевый подход решает эту проблему за счёт коллективного взаимодействия. Набор из $K$ блуждателей одновременно покрывает разные области пространства и обменивается информацией:

положение соседей задаёт естественный масштаб и направление шага, избавляя от необходимости оценивать ковариационную матрицу или гессиан;
обмен состояниями между «горячими» и «холодными» копиями позволяет перепрыгивать через барьеры низкой вероятности;
клонирование и удаление частиц (ресэмплинг) концентрирует вычислительный бюджет в областях высокой апостериорной плотности.

Формальная постановка

Пусть $S = \{X_1, X_2, \dots, X_K\}$ — ансамбль из $K$ состояний, $X_k \in \mathbb{R}^d$ . Целевое распределение, из которого ведётся сэмплирование, обозначается $\pi(x)$ . Совместное распределение ансамбля факторизуется:

$\Pi(S) = \prod_{k=1}^K \pi(X_k)$

Алгоритм строит марковскую цепь в пространстве $\mathbb{R}^{K \times d}$ с переходным ядром $T(S \to S')$ , удовлетворяющим условию детального баланса (англ. detailed balance):

$\Pi(S)\, T(S \to S') = \Pi(S')\, T(S' \to S)$

Существенная деталь: ядро обновления $i$ -го элемента зависит от остальных состояний $S \setminus \{X_i\}$ . Именно эта зависимость позволяет адаптировать предлагающее распределение (англ. proposal distribution) к локальной геометрии без явного вычисления градиентов или вторых производных.

Основные алгоритмы

Аффинно-инвариантный сэмплер со «стретч-мувом»

Алгоритм, предложенный Гудманом и Виром^[1], стал де-факто стандартом для задач малой и средней размерности и реализован в библиотеке emcee^[1]. На каждом шаге для блуждателя $X_i$ :

Случайно выбирается «компаньон» $X_j$ из текущего ансамбля ( $j \neq i$ ).
Генерируется скаляр $z$ из вспомогательного распределения $g(z) \propto 1/\sqrt{z}$ на отрезке $[1/a,\; a]$ (обычно $a = 2$ ).
Пробное состояние строится вдоль прямой между $X_i$ и $X_j$ :

$Y = X_j + z\,(X_i - X_j)$

Шаг принимается с вероятностью:

$q = \min\!\left(1,\; z^{\,d-1}\,\frac{\pi(Y)}{\pi(X_i)}\right)$

Множитель $z^{d-1}$ — якобиан аффинного отображения в $d$ -мерном пространстве. Ключевое свойство алгоритма — аффинная инвариантность (англ. affine invariance): при замене $x \mapsto Ax + b$ с невырожденной матрицей $A$ статистика цепи не меняется. На практике это означает, что сэмплер одинаково хорошо работает с параметрами, различающимися на порядки (например, learning rate и weight decay), без предварительного масштабирования.

Параллельный отжиг

Параллельный отжиг (англ. parallel tempering)^[1] расширяет ансамбль в «температурное» измерение. Каждая из $K$ цепей сэмплирует из сглаженного распределения:

$\pi_k(x) \propto [\pi(x)]^{1/T_k}, \qquad 1 = T_1 < T_2 < \dots < T_K$

«Горячие» цепи ( $T_K \gg 1$ ) свободно пересекают энергетические барьеры и глобально исследуют пространство; «холодная» цепь ( $T_1 = 1$ ) точно локализуется в модах. Периодически между соседними цепями предлагаются обмены состояниями с вероятностью, определяемой отношением правдоподобий. Благодаря обменам информация о далёких модах «стекает» вниз по температурной лестнице.

Последовательный Монте-Карло и ансамблевый фильтр Калмана

Последовательный Монте-Карло (англ. Sequential Monte Carlo, SMC)^[1] и ансамблевый фильтр Калмана (англ. Ensemble Kalman Filter, EnKF)^[1] добавляют к ансамблю временну́ю динамику. В SMC на каждом шаге частицы мутируют (MCMC-переход), после чего выполняется ресэмплинг: частицы с большим весом клонируются, с малым — удаляются. EnKF использует эмпирическую ковариацию ансамбля вместо обращения матриц размерности $d \times d$ , что делает метод применимым к нелинейным динамическим системам с $d \sim 10^6$ .

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

Байесовская оптимизация и подбор гиперпараметров

В задачах байесовской оптимизации размерность пространства гиперпараметров (англ. hyperparameter) обычно не превышает нескольких десятков. Аффинно-инвариантные ансамблевые сэмплеры используются для оценки апостериорного распределения параметров суррогатных моделей, в частности гауссовских процессов (англ. Gaussian process). Аффинная инвариантность здесь особенно уместна: типичный набор гиперпараметров включает длину корреляции, амплитуду ядра и уровень шума, различающиеся на порядки.

Калиброванная оценка неопределённости

В вероятностных графических моделях и байесовских обобщённых линейных моделях EMC даёт асимптотически точные выборки из апостериорного распределения. В отличие от вариационного вывода (англ. variational inference), который минимизирует KL-дивергенцию и систематически занижает дисперсию, ансамблевый MCMC не вносит аппроксимационного смещения. Это важно при оценке эпистемической неопределённости (англ. epistemic uncertainty) в задачах, где цена ошибки высока — медицинская диагностика, автономное вождение.

Сэмплирование в генеративных моделях

В энергетических моделях (англ. Energy-Based Models) и диффузионных моделях (англ. diffusion models) генерация сводится к сэмплированию из распределения $\pi(x) \propto \exp(-E(x))$ . SMC с промежуточными температурными уровнями позволяет избежать коллапса мод (англ. mode collapse), характерного для динамики Ланжевена (англ. Langevin dynamics) с фиксированным шагом, и обеспечивает более равномерное покрытие многообразия данных.

Байесовское обучение с подкреплением

В частично наблюдаемых марковских процессах принятия решений (англ. POMDP) ансамбли частиц одновременно отслеживают скрытое состояние среды и обновляют апостериорное распределение параметров динамики перехода. SMC здесь выступает альтернативой фильтру Калмана для существенно нелинейных моделей.

Вычислительные аспекты и современные направления

Параллелизм. Вычисление правдоподобия для каждого из $K$ блуждателей на этапе proposal не зависит от остальных — задача embarrassingly parallel. Это позволяет масштабировать алгоритмы на тысячи ядер CPU и GPU-кластеры.

Дифференцируемый SMC. С конца 2010-х годов SMC интегрируется с автоматическим дифференцированием. Несмещенные оценки градиентов маргинального правдоподобия, получаемые через SMC, позволяют обучать параметры скрытых марковских моделей и глубоких генеративных сетей стандартным градиентным спуском.

Нейросетевые proposal-распределения. Для преодоления ограничения $K > d$ в пространствах высокой размерности ансамблевую философию комбинируют с нормализующими потоками (англ. normalizing flows): нейросеть обучается предсказывать адаптивное proposal-распределение для каждого блуждателя, что делает возможным сэмплирование из апостериорных распределений параметров глубоких сетей.

Ограничения

Базовые ансамблевые сэмплеры (в первую очередь stretch move) упираются в проклятие размерности. При $d \gg 1$ объём пространства растёт экспоненциально, и фиксированный ансамбль из $K$ точек не покрывает гиперсферу вокруг $X_j$ . Вероятность принятия $q$ стремится к нулю, цепь вырождается. В задачах с миллионами параметров (глубокое обучение) ансамблевые методы уступают место стохастическим градиентным методам MCMC (англ. SG-MCMC) и вариационному выводу. Тем не менее для задач размерности $d \leq 10^2$ , где требуется строгая байесовская инференция, ансамблевые сэмплеры остаются рабочим инструментом первого выбора.

См. также

Литература

Goodman J., Weare J. Ensemble samplers with affine invariance // Communications in Applied Mathematics and Computational Science. — 2010. — Т. 5. — № 1. — С. 65—80.
Foreman-Mackey D., Hogg D. W., Lang D., Goodman J. emcee: The MCMC Hammer // Publications of the Astronomical Society of the Pacific. — 2013. — Т. 125. — № 925. — С. 306—312.
Del Moral P., Doucet A., Jasra A. Sequential Monte Carlo samplers // Journal of the Royal Statistical Society: Series B. — 2006. — Т. 68. — № 3. — С. 411—436.
Evensen G. The Ensemble Kalman Filter: Theoretical Formulation and Practical Implementation // Ocean Dynamics. — 2003. — Т. 53. — № 4. — С. 343—367.
Earl D. J., Deem M. W. Parallel tempering: Theory, applications, and new perspectives // Physical Chemistry Chemical Physics. — 2005. — Т. 7. — № 23. — С. 3910—3916.
Doucet A., De Freitas N., Gordon N. (eds.) Sequential Monte Carlo Methods in Practice. — New York: Springer, 2001. — 581 с.
Robert C. P., Casella G. Monte Carlo Statistical Methods. — 2nd ed.. — New York: Springer, 2004. — 645 с.

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%90%D0%BD%D1%81%D0%B0%D0%BC%D0%B1%D0%BB%D0%B5%D0%B2%D1%8B%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%9C%D0%BE%D0%BD%D1%82%D0%B5-%D0%9A%D0%B0%D1%80%D0%BB%D0%BE»

@@ Строка 5: / Строка 5: @@
 '''Ансамблевые методы Монте-Карло''' (англ. ''Ensemble Monte Carlo'', EMC) — семейство стохастических алгоритмов для оценки математических ожиданий, численного интегрирования и сэмплирования из сложных многомерных распределений. В отличие от классических [[Марковские цепи Монте-Карло|методов Монте-Карло по цепям Маркова]] (англ. ''Markov Chain Monte Carlo'', MCMC), где каждая цепь эволюционирует изолированно, EMC оперирует '''ансамблем''' — набором из <tex>K</tex> взаимодействующих состояний (частиц, «блуждателей»). Геометрия целевого пространства передаётся между элементами ансамбля на каждом шаге, что позволяет алгоритму исследовать мультимодальные распределения и пространства с сильными корреляциями без ручной настройки метрики.
-В [[Машинное обучение|машинном обучении]] и искусственном интеллекте ансамблевые методы применяются для [[Байесовский вывод|байесовского вывода]] (англ. ''Bayesian inference''), [[Оценка неопределённости|оценки неопределённости]] (англ. ''Uncertainty Quantification''), [[Байесовская оптимизация|байесовской оптимизации]] (англ. ''Bayesian optimization''), а также в генеративных моделях и [[Обучение с подкреплением|обучении с подкреплением]] (англ. ''reinforcement learning'').
+В [[Машинное обучение|машинном обучении]] и искусственном интеллекте ансамблевые методы применяются для [[Байесовский вывод|байесовского вывода]] (англ. ''Bayesian inference''), [[Оценка неопределенности в машинном обучении|оценки неопределённости]] (англ. ''Uncertainty Quantification''), [[Байесовская оптимизация|байесовской оптимизации]] (англ. ''Bayesian optimization''), а также в генеративных моделях и [[Обучение с подкреплением|обучении с подкреплением]] (англ. ''reinforcement learning'').
 == Мотивация ==
@@ Строка 80: / Строка 80: @@
 '''Дифференцируемый SMC.''' С конца 2010-х годов SMC интегрируется с автоматическим дифференцированием. Несмещенные оценки градиентов маргинального правдоподобия, получаемые через SMC, позволяют обучать параметры скрытых марковских моделей и глубоких генеративных сетей стандартным градиентным спуском.
-'''Нейросетевые proposal-распределения.''' Для преодоления ограничения <tex>K > d</tex> в пространствах высокой размерности ансамблевую философию комбинируют с [[Нормализующие потоки|нормализующими потоками]] (англ. ''normalizing flows''): нейросеть обучается предсказывать адаптивное proposal-распределение для каждого блуждателя, что делает возможным сэмплирование из апостериорных распределений параметров глубоких сетей.
+'''Нейросетевые proposal-распределения.''' Для преодоления ограничения <tex>K > d</tex> в пространствах высокой размерности ансамблевую философию комбинируют с [[Нормализующий поток|нормализующими потоками]] (англ. ''normalizing flows''): нейросеть обучается предсказывать адаптивное proposal-распределение для каждого блуждателя, что делает возможным сэмплирование из апостериорных распределений параметров глубоких сетей.
 == Ограничения ==
-Базовые ансамблевые сэмплеры (в первую очередь stretch move) упираются в проклятие размерности. При <tex>d \gg 1</tex> объём пространства растёт экспоненциально, и фиксированный ансамбль из <tex>K</tex> точек не покрывает гиперсферу вокруг <tex>X_j</tex>. Вероятность принятия <tex>q</tex> стремится к нулю, цепь вырождается. В задачах с миллионами параметров (глубокое обучение) ансамблевые методы уступают место [[Стохастический градиентный спуск|стохастическим градиентным методам MCMC]] (англ. ''SG-MCMC'') и вариационному выводу. Тем не менее для задач размерности <tex>d \lesssim 10^2</tex>, где требуется строгая байесовская инференция, ансамблевые сэмплеры остаются рабочим инструментом первого выбора.
+Базовые ансамблевые сэмплеры (в первую очередь stretch move) упираются в проклятие размерности. При <tex>d \gg 1</tex> объём пространства растёт экспоненциально, и фиксированный ансамбль из <tex>K</tex> точек не покрывает гиперсферу вокруг <tex>X_j</tex>. Вероятность принятия <tex>q</tex> стремится к нулю, цепь вырождается. В задачах с миллионами параметров (глубокое обучение) ансамблевые методы уступают место [[Стохастический градиентный спуск|стохастическим градиентным методам MCMC]] (англ. ''SG-MCMC'') и вариационному выводу. Тем не менее для задач размерности <tex>d \leq 10^2</tex>, где требуется строгая байесовская инференция, ансамблевые сэмплеры остаются рабочим инструментом первого выбора.
 == См. также ==