Монте-Карло

Интеграл — это ожидание

Метод Монте-Карло целиком стоит на одном переписывании: любой интеграл можно прочитать как ожидание, а ожидание — оценить средним.

$$\htmlData{k=integral}{\int f(x)\,p(x)\,dx} = \htmlData{k=expect}{\mathbb{E}_{p}[f(X)]} \approx \htmlData{k=average}{\frac{1}{n}\sum_{i=1}^{n} f(x_i)}, \quad x_i \sim p$$

Смысл этого хода в том, что среднее не зависит от размерности. Сетка из $m$ точек по каждой из $d$ осей требует $m^d$ вычислений и умирает уже при $d = 10$; Монте-Карло нужно столько точек, сколько нужно для требуемой точности, и число осей в эту оценку не входит. Именно поэтому в машинном обучении почти всякое ожидание считается сэмплированием, а не квадратурой.

Два свойства оценки

Несмещённость. $\mathbb{E}\left[\frac{1}{n}\sum_i f(x_i)\right] = \mathbb{E}[f(X)]$ по линейности ожидания — при любом $n$, даже при $n = 1$. Оценка по одному сэмплу уже несмещена. Это то, на чём стоит SGD: один минибатч даёт несмещённую оценку градиента.

Дисперсия. $\operatorname{Var}\left(\frac{1}{n}\sum_i f(x_i)\right) = \frac{\operatorname{Var}(f(X))}{n}$ для независимых сэмплов. Отсюда стандартная ошибка $\propto \frac{1}{\sqrt{n}}$: чтобы получить лишний десятичный знак, нужно в сто раз больше сэмплов. Скорость $1/\sqrt{n}$ — не недостаток реализации, а свойство метода, и обойти её можно только уменьшив числитель.

Здесь и появляется урок предыдущего шага в новом виде. Несмещённость у нас есть бесплатно; вся работа — в дисперсии.

Когда несмещённость бесполезна

Возьмём задачу, где это видно без всякой философии: оценить $P(X > t)$ для $X \sim \mathcal{N}(0,1)$. Оценка — доля сэмплов, попавших в хвост, и она безупречно несмещена.

При $t = 3$ в хвост попадает один сэмпл из $741$. Взяв $500$ сэмплов, вы с вероятностью $\approx 51\%$ не поймаете ни одного и получите ответ ровно нуль. Оценка при этом сообщит нулевую стандартную ошибку — то есть «$0 \pm 0$», ответ, ошибочный на $100\%$ и не подающий никаких признаков беды.

Виджет открыт как раз в этой конфигурации: $t = 3$, $500$ сэмплов.

истина: 1.350e-3 наивная MC

порог t

3

сэмплов n

500

включить importance sampling

попаданий в хвост

0 / 500

наивная MC · оценка

0.000e+0

наивная MC · ст. ошибка

0.00e+0

Importance sampling

Идея: сэмплировать из другого распределения $q$, которое чаще заглядывает туда, где $f$ не равно нулю, и исправить перекос весами.

$\mathbb{E}_p[f(X)] = \int f(x)\frac{p(x)}{q(x)}q(x)\,dx = \mathbb{E}_q\!\left[f(X)\frac{p(X)}{q(X)}\right]$

Всё преобразование — умножить и поделить на $q$. Отношение $w(x) = \frac{p(x)}{q(x)}$ называется весом, или отношением правдоподобий, и оно ровно то, что удерживает оценку несмещённой при сэмплировании из неправильного распределения.

Включите тумблер в виджете. При $t = 3$ с предложением $\mathcal{N}(3, 1)$ оценка попадает в $1.24 \cdot 10^{-3}$ против истины $1.35 \cdot 10^{-3}$, и её стандартная ошибка — $1.0 \cdot 10^{-4}$, тогда как у наивной оценки её просто нет.

Выигрыш по дисперсии на один сэмпл, посчитанный точно:

$t$	$P(X>t)$	выигрыш при $q = \mathcal{N}(t, 1)$
$2$	$2.3 \cdot 10^{-2}$	$18\times$
$3$	$1.3 \cdot 10^{-3}$	$218\times$
$4$	$3.2 \cdot 10^{-5}$	$7000\times$

Чем реже событие, тем больше выигрыш — то есть importance sampling помогает тем сильнее, чем безнадёжнее наивный подход.

Выбор $q$ — это вся сложность

Метод несмещён при любом $q$ с достаточным носителем, но дисперсия зависит от $q$ резко. Подвигайте слайдер сдвига при $t = 3$:

сдвиг	выигрыш по дисперсии
$0$	$1\times$ (это и есть наивная MC)
$1$	$16\times$
$2$	$97\times$
$3$	$218\times$
$4$	$141\times$
$5$	$31\times$

Оптимум около $q = \mathcal{N}(t, 1)$, и уход в обе стороны портит дело. Слишком маленький сдвиг возвращает исходную проблему. Слишком большой создаёт новую: $q$ сэмплирует далеко в хвост, где $p/q$ огромно, и оценку начинают определять несколько сэмплов с гигантскими весами.

Два правила, которые из этого следуют:

• носитель $q$ должен покрывать носитель $f \cdot p$. Если $q(x) = 0$ там, где $f(x)p(x) \ne 0$, оценка смещена, и никакое $n$ этого не исправит — вклад этой области просто не может появиться;
• тяжёлые хвосты у $q$ безопаснее лёгких. Ошибка «$q$ уже, чем $p$» даёт неограниченные веса и бесконечную дисперсию; ошибка «$q$ шире, чем нужно» стоит лишь части эффективности.

Практический индикатор — эффективный размер выборки

$n_{\text{eff}} = \frac{\left(\sum_i w_i\right)^2}{\sum_i w_i^2}$

Если из тысячи сэмплов $n_{\text{eff}}$ равно десяти, вы фактически считаете по десяти точкам, что бы ни показывала формальная стандартная ошибка. В байесовском выводе это стандартная диагностика, и смотреть на неё нужно раньше, чем на сам ответ.

Где это встретится дальше

Importance sampling — не приём для хвостовых вероятностей, а несущая конструкция:

• off-policy RL: оценить отдачу политики $\pi$ по данным, собранным политикой $\mu$. Веса — $\pi/\mu$, и клипование этих весов есть буквально PPO;
• ELBO: ожидание по $q(z)$ вместо недоступного $p(z \mid x)$ — блок 4;
• оценка перплексии и нормировок в моделях, где сумма по словарю неподъёмна.

Во всех трёх случаях структура одна: считать ожидание по неудобному распределению через удобное, платя весами.