Научные вычисления
Monte Carlo методы
Nvidia RTX: каждый пиксель в современных играх - результат тысяч случайных лучей, интегрированных методом Монте-Карло (path tracing). JPMorgan оценивает риск портфеля из 10,000 инструментов через 1 миллион случайных сценариев за несколько минут - аналитическая формула невозможна. DeepMind AlphaGo использует Monte Carlo Tree Search для оценки позиций. MC - это метод превращения сложных вычислений в статистику.
- **NVIDIA RTX Path Tracing** - Monte Carlo интегрирование уравнения рендеринга; тысячи случайных световых путей на пиксель; denoising через ML сглаживает шум; основа фотореалистичной графики
- **JPMorgan Value-at-Risk** - 1M случайных сценариев за ночь для оценки максимального убытка с P=0.99; портфель из 50,000 инструментов с 100+ факторами риска; MC единственный практичный метод
- **DeepMind AlphaGo MCTS** - Monte Carlo Tree Search: случайное разыгрывание партий для оценки силы позиции; 10^170 возможных позиций в го - полный перебор невозможен
Метод Монте-Карло: базовые идеи
Как найти площадь фигуры неправильной формы? Бросить случайные точки в прямоугольник и посчитать процент попавших в фигуру - это классический Монте-Карло. Nvidia использует Monte Carlo Path Tracing для рендеринга фотореалистичной графики в играх (RTX). JPMorgan оценивает Value-at-Risk портфеля через миллионы случайных сценариев.
**Метод Монте-Карло** - вычисление интеграла I = integral f(x)dx через случайную выборку: I_N = (1/N) * sum f(x_i), x_i ~ uniform. Закон больших чисел: I_N -> I при N -> inf. Погрешность O(1/sqrt(N)) - независима от размерности пространства! Это делает MC незаменимым в высоких размерностях (>4D).
Почему MC интеграция особенно ценна в высокоразмерных пространствах (d > 10)?
Markov Chain Monte Carlo (MCMC)
Байесовский вывод: нужно sample из posterior P(theta | data) = P(data | theta) * P(theta) / P(data). Знаменатель P(data) - интеграл, часто неберущийся аналитически. MCMC строит цепь Маркова, стационарное распределение которой есть нужный posterior.
**MCMC** - семейство алгоритмов: **Metropolis-Hastings** (предлагаем шаг, принимаем с вероятностью min(1, p(x')/p(x))), **Gibbs sampling** (поочерёдно сэмплим каждую переменную из условного распределения), **HMC** (Hamiltonian Monte Carlo) - PyMC, Stan используют NUTS (No-U-Turn Sampler).
Что такое acceptance rate в Metropolis-Hastings и почему ~23% считается оптимальным?
Importance Sampling
Страховая компания оценивает вероятность катастрофического события (P < 0.001). Равномерная выборка: нужно 100,000+ сэмплов чтобы увидеть хотя бы 100 редких событий. Importance sampling: сэмплируем из другого распределения q(x) которое чаще попадает в редкую область.
**Importance Sampling**: E_p[f(x)] = E_q[f(x) * p(x)/q(x)] = E_q[f(x) * w(x)], где w(x) = p(x)/q(x) - importance weights. Выбор q: должен иметь тяжёлые хвосты там где p(x)*f(x) велик. Self-normalized IS: sum(f_i * w_i) / sum(w_i) - более стабильный. Используется в RL (off-policy learning), VAE (ELBO), rare event simulation.
Что такое importance weights в importance sampling?
Variance Reduction
Финансовая инженерия: оценить цену опциона через MC за 1 минуту вместо часа. Погрешность MC O(1/sqrt(N)) - чтобы улучшить в 10 раз нужно в 100 раз больше сэмплов. Альтернатива: уменьшить дисперсию оценщика, не увеличивая N.
Методы variance reduction: **Antithetic variables** - использовать пары (u, 1-u) из uniform; отрицательная корреляция снижает Var. **Control variates** - вычесть коррелированную величину с известным expectation. **Quasi-Monte Carlo** (QMC) - вместо random использовать low-discrepancy sequences (Halton, Sobol); погрешность O(log(N)^d / N) vs O(1/sqrt(N)).
Monte Carlo методы дают точный ответ при достаточно большом N
MC - вероятностный метод с погрешностью O(1/sqrt(N)). N=1M даёт погрешность ~0.1%. Для 6 знаков точности нужно N=10^12 сэмплов - нереально. Для высокой точности используют детерминированные методы (Gaussian quadrature в 1D-3D) или QMC (Sobol, Halton).
Сила MC - в масштабировании на высокие размерности и сложные распределения, а не в абсолютной точности. Ценообразование опционов (d=10-50 факторов): MC с variance reduction практичнее аналитических формул. Оценка pi с 10 знаками: детерминированная квадратура в 10,000 раз эффективнее MC.
Почему Quasi-Monte Carlo (Sobol sequences) точнее обычного MC при том же числе сэмплов?
Ключевые идеи
- **MC базис**: I_N = (1/N)*sum(f(x_i)); погрешность O(1/sqrt(N)); независима от размерности - ключевое преимущество при d > 5
- **MCMC**: Metropolis-Hastings строит цепь Маркова с нужным стационарным распределением; acceptance rate ~23% оптимален; PyMC/Stan для Bayesian inference
- **Importance Sampling**: сэмплировать из q(x), умножать на w=p/q; снижает дисперсию при редких событиях; основа off-policy RL и VAE
- **Variance Reduction**: antithetic variables, control variates, QMC (Sobol); QMC даёт O(log(N)/N) vs O(1/sqrt(N)) - в 10-100x точнее при том же N
Связанные темы
Monte Carlo методы применяются в оптимизации, ML и финансах:
- Numerical Optimization — Simulated Annealing и эволюционные алгоритмы - глобальная оптимизация через случайный поиск
- Вероятность и статистика — Закон больших чисел и CLT - теоретическое обоснование сходимости MC оценок
Вопросы для размышления
- Почему MCMC цепь требует burn-in период (выбрасывать первые 500-1000 сэмплов) и как определить достаточную длину burn-in на практике?
- Importance sampling снижает дисперсию при удачном выборе q, но может её увеличить при неудачном. Как обнаружить что выбор q плохой - какой диагностический сигнал?
- Nvidia использует MC path tracing с 128 сэмплами на пиксель, затем ML-denoising (DLSS). Почему гибрид 'немного MC + ML denoising' лучше чем 'много MC без denoising' для real-time рендеринга?