Численные методы
Метод Монте-Карло
AlphaGo использовал Monte Carlo Tree Search. GPT-4 с tree-of-thought reasoning использует вариации MCTS. Stable Diffusion - это reverse-time MCMC. Байесовские нейронные сети обучаются через MCMC или variational inference. Monte Carlo - не один алгоритм, это математический принцип, лежащий в основе половины современного ML.
- **AlphaGo/AlphaZero:** MCTS с нейросетевой эвристикой - UCB1 для exploration, rollouts для оценки позиций. 4-1 против чемпиона мира Ли Седоля в 2016.
- **Stable Diffusion/DALL-E:** reverse diffusion - MCMC цепь от N(0,I) к сложному распределению изображений. Score function обучается нейросетью.
- **Stan/PyMC:** NUTS (No-U-Turn Sampler) - автоматический HMC для байесовских моделей. Используется в медицинских клинических исследованиях, финансовых моделях.
Monte Carlo интегрирование: ошибка O(1/√N) независимо от размерности
**AlphaGo использовал MCTS - Monte Carlo Tree Search.** В 2016 году это обыграло чемпиона мира в го. В 2025 каждый LLM с tree-of-thought reasoning использует варианты этого алгоритма. Monte Carlo - не один метод, а целый класс: интегрирование, MCMC, tree search, particle filters.
Классические квадратуры для d-мерного интеграла с n точками на ось требуют nᵈ вычислений. При d=20, n=10: 10²⁰ операций. Monte Carlo: N случайных точек, ошибка σ/√N - **не зависит от d**. При d≥5 Monte Carlo всегда выигрывает.
**Оценка интеграла:** I = ∫_Ω f(x)dx = vol(Ω)·E[f(X)] где X ~ Uniform(Ω). MC estimator: Î_N = vol(Ω)·(1/N)·Σᵢ f(xᵢ) Центральная предельная теорема: Î_N ~ N(I, σ²/N) где σ² = Var[f(X)]. Ошибка: |Î_N - I| ≈ σ/√N с 68% вероятностью. Для ε точности нужно N = σ²/ε² точек - независимо от d!
Медленная сходимость - главный недостаток. Чтобы уменьшить ошибку в 10x, нужно в 100x больше точек. Именно поэтому существуют variance reduction методы: importance sampling, control variates, quasi-MC.
MC интеграл при d=100 имеет ту же формулу ошибки σ/√N что и при d=1. В чём тогда практическая трудность?
Формула σ/√N верна, но σ зависит от функции. В высоких размерностях объём гиперкуба концентрируется у краёв - подынтегральная функция имеет огромную дисперсию. Нужны: важностная выборка, quasi-MC.
Importance Sampling: сэмплировать умнее
P(X > 4.5) для X ~ N(0,1) = 3.4×10⁻⁶. Наивный MC: из 1 миллиона точек только 3-4 попадут в хвост - оценка с огромной дисперсией. **Importance sampling**: сэмплировать из распределения q центрированного на хвосте, корректировать весами w = p/q. Те же точки - в 100x меньше дисперсия.
**Математика importance sampling:** E_p[f(X)] = ∫ f(x)·p(x)dx = ∫ f(x)·[p(x)/q(x)]·q(x)dx = E_q[f(X)·w(X)] где w(x) = p(x)/q(x) - importance weights. IS estimator: (1/N)·Σᵢ f(xᵢ)·w(xᵢ), xᵢ ~ q Оптимальный q*(x) ∝ |f(x)|·p(x) - даёт нулевую дисперсию, но требует знания ответа. Diagnostic: ESS = (Σwᵢ)²/Σwᵢ² - эффективный размер выборки. ESS << N означает плохой выбор q.
q(x) с более лёгкими хвостами чем p(x)·f(x) - катастрофа. Веса w=p/q становятся бесконечно большими в хвостах, где q(x)→0. Один такой образец доминирует всю оценку. Всегда: q должна покрывать support p·f, иметь тяжелее или равные хвосты.
В importance sampling нужно q(x) > 0 везде, где f(x)p(x) ≠ 0. Что произойдёт при нарушении?
Если q(x₀)=0, но f(x₀)p(x₀)≠0, то вклад точки x₀ не учитывается вообще - смещение. Если q(x) малое, а f(x)p(x)/q(x) большое, дисперсия весов w_i=p(x_i)/q(x_i) может стать бесконечной.
MCMC: сэмплирование без нормировочной константы
В байесовской статистике p(θ|data) ∝ p(data|θ)·p(θ). Нормировочная константа - интеграл по всем θ, обычно вычислительно недоступный. **MCMC** строит цепь Маркова со стационарным распределением p(θ|data) - не нужна нормировка, нужно только отношение p(θ')/p(θ).
**Детальный баланс (detailed balance):** π(x)T(x→x') = π(x')T(x'→x). Это достаточное условие того, что π - стационарное распределение цепи. Критерий принятия min(1, p(x')/p(x)) обеспечивает детальный баланс автоматически. **Диагностика перемешивания:** - Acceptance rate 20-50%: оптимальный размер шага (RW-MH в d измерениях: шаг ≈ 2.38/√d) - R-hat статистика Gelman-Rubin: должна быть < 1.01 для нескольких цепей - Effective Sample Size (ESS): из 50000 шагов реально независимых может быть 500 **Гибридные методы:** - HMC (Hamiltonian MC): использует градиенты для больших шагов - основа Stan, PyMC - NUTS (No-U-Turn Sampler): автоматическая длина траектории - стандарт байесовского ML
Diffusion models - это MCMC в reverse time. Деноизинг от шума к изображению - это цепь Маркова с learned transition kernel. Score matching обучает log-gradient целевого распределения, Langevin dynamics использует его для сэмплирования.
В Metropolis-Hastings шаг принимается даже если p(x') < p(x). Зачем?
Если всегда идти к росту p - жадный алгоритм застрянет в локальной моде. Вероятностное принятие гарантирует detailed balance: стационарное распределение цепи = целевое p(x).
Ключевые идеи
- **MC интегрирование:** E[f(X)] ≈ (1/N)Σf(xᵢ), ошибка O(1/√N) - не зависит от размерности d. При d≥5 выигрывает у квадратур.
- **MCTS:** UCB1 = Q(s,a) + c·√(log N(s)/N(s,a)) - exploration-exploitation трейдоф, основа AlphaGo.
- **Importance Sampling:** E_p[f] = E_q[f·p/q], q должна покрывать support p·f с тяжёлыми хвостами. ESS = (Σwᵢ)²/Σwᵢ² для диагностики.
- **MCMC Metropolis-Hastings:** принять x' с min(1, p(x')/p(x)) - детальный баланс гарантирует стационарность. Не нужна нормировочная константа.
- **Diffusion models:** обратная диффузия = MCMC с learned score function. От шума к изображению через цепь Маркова.
Связанные темы
Monte Carlo пронизывает весь probabilistic ML:
- Численные методы в ML — Рандомизированные алгоритмы линейной алгебры - Monte Carlo для матричных вычислений
- Numerical Integration (квадратуры) — MC дополняет квадратуры: лучше в высоких d, хуже в 1D для гладких f