মন্টে কার্লো — দৈবচয়নে অনুমান

Diffusion model — ২০২২-এর AI revolution-এর প্রধান চালক। গণিত surprisingly elegant — সব মন্টে কার্লো-ভিত্তিক। Sohl-Dickstein (২০১৫), Ho et al. (২০২০, DDPM), Song et al. (২০২১, score-based) — ইতিহাস।

(১) মৌলিক ধারণা:

• Forward process: image-এ ধীরে ধীরে noise add — শেষে pure Gaussian noise.
• Reverse process: pure noise থেকে শুরু, ধাপে ধাপে noise remove — image.
• Network শেখে: "এই noisy image-এ কতটা noise আছে?"

(২) Monte Carlo sampling-এ কী?

• প্রতিটি step-এ random Gaussian noise sample.
• $x_{t-1} = \mu_\theta(x_t, t) + \sigma_t \cdot \epsilon$, $\epsilon \sim N(0, I)$।
• এই Gaussian sample-ই "creativity" — same prompt থেকে different images.
• Total sampling: $T = 50-1000$ steps.

(৩) Score-based view:

• Network শেখে $\nabla_x \log p(x)$ — score function.
• Langevin dynamics — score follow করে probable image-এ পৌঁছানো।
• Stochastic Differential Equation (SDE) interpretation.

(৪) DDPM-এর সরল algorithm:

def sample_image(model, T=1000, shape=(3,256,256)):
    x = torch.randn(shape)  # pure noise
    for t in reversed(range(T)):
        z = torch.randn_like(x) if t > 0 else 0
        x = (1/sqrt(alpha[t])) * (x - (1-alpha[t])/sqrt(1-alpha_bar[t]) * model(x, t))
        x = x + sigma[t] * z  # MC sampling step
    return x

(৫) Sampler choice — Monte Carlo variants:

• DDPM (১০০০ steps): ধীর, কিন্তু high quality.
• DDIM (Song ২০২১): Deterministic-ish, ৫০ steps.
• DPM-Solver: ১০-২০ steps, fast.
• Euler, Heun: ODE solvers.

(৬) Why so much sampling?

• Direct image generation high-D distribution থেকে — intractable.
• Iterative refinement = MC chain.
• প্রতিটি step ছোট, controllable.

(৭) Conditioning:

• Text-to-image: classifier-free guidance — text-conditioned vs unconditional sample combine.
• Inpainting: masked region-এ MC, rest fixed.
• ControlNet: pose, depth-conditioned sampling.

(৮) Computational cost:

• SDXL: ৫০ steps × ৩.৫B params = ~৫ seconds A100-এ।
• Each step: full forward pass!
• Distillation (LCM): ১-৪ steps possible.
• Future: 1-step distilled diffusion.

(৯) Why MC works here:

• High-D image space — grid impossible.
• Manifold structure — MC explore efficiently.
• Stochasticity = creativity.

(১০) Bangladesh use cases:

• Bangla calligraphy generation.
• Local content creation — fashion, food, festival imagery.
• Educational content — historical Bengal scenes.
• Privacy: local diffusion, no cloud upload.

মূল উপলব্ধি: Stable Diffusion-এর "magic" আসলে clever Monte Carlo. ১৯৪৭-এর random sampling idea + ২০২২-এর neural network = $20B industry. Beautiful continuity in mathematics.

MCTS (Coulom ২০০৬, Kocsis-Szepesvári ২০০৬) — game AI-এর একটি landmark. AlphaGo (২০১৬) এই algorithm-এর masterpiece. আজকের AlphaZero, MuZero, OpenAI Five — সবেই MCTS-ভিত্তিক।

(১) Game tree problem:

• Chess: ~$10^{120}$ game states.
• Go: ~$10^{170}$ — observable universe-এর atom-এর চেয়ে বেশি।
• Brute force impossible.

(২) Vanilla minimax:

• সব move evaluate, best বাছ — depth-limited.
• Alpha-beta pruning helps, কিন্তু branching factor বড় হলে সমস্যা।
• Heuristic evaluation function — domain expertise.

(৩) MCTS — ৪ ধাপ:

1. Selection: Root থেকে leaf, UCB1 score-এ।
2. Expansion: Leaf-এ নতুন child.
3. Simulation (rollout): Random play to game end.
4. Backpropagation: Result tree-এ update.

(৪) UCB1 — exploration vs exploitation:

$\text{UCB1}(s) = \dfrac{w_s}{n_s} + c\sqrt{\dfrac{\ln N}{n_s}}$

• প্রথম term: average win rate (exploitation)।
• দ্বিতীয় term: under-explored nodes-এ visit (exploration)।
• $c$: balance constant.

(৫) AlphaGo — MCTS + Neural Networks:

• Policy network: কোন move likely?
• Value network: এই position-এ winning chance কত?
• MCTS: NN-এর guidance-এ tree explore.
• Random rollout-এর বদলে value network — efficient.

(৬) AlphaZero (২০১৭) — পরের generation:

• No human games — pure self-play.
• Single network: policy + value combined.
• Chess, shogi, Go — all superhuman.
• ৪ ঘণ্টায় Stockfish (chess world champion engine)-কে হারায়।

(৭) MuZero (২০১৯) — without rules:

• Game rules জানে না — শেখে।
• Atari games + Go + chess + shogi all handle.
• Latent space planning.

(৮) Why MCTS > minimax:

• Adaptive — অনিশ্চিত branches বেশি explore.
• Anytime — যেকোনো সময় থামানো যায়।
• Asymmetric — promising paths-এ বেশি depth.
• Statistical backbone — আসলে multi-armed bandit.

(৯) MCTS-এর চ্যালেঞ্জ:

• Tactical positions-এ short-term miss.
• Memory: tree বড়।
• Hyperparameter tuning ($c$, depth)।
• Hidden information game (poker)-এ struggle.

(১০) MCTS beyond games:

• Robot motion planning: Possible paths search.
• Drug discovery: Molecular space exploration.
• RL planning: Model-based RL.
• LLM reasoning: Tree of Thoughts, MCTS-style decomposition.
• AlphaCode (২০২২): Code generation-এ rollout.

(১১) AGI implications:

• "Search + learning" — Sutton-এর বিখ্যাত "Bitter Lesson"।
• MCTS = principled search; NN = learning.
• একসাথে AGI-র recipe?

মূল উপলব্ধি: AlphaGo-এর সাফল্য — যাদু না, mathematics. MCTS-এর Monte Carlo intuition + deep learning = world-class game playing. আজকের ChatGPT-এর reasoning research-এও MCTS techniques. Old idea, modern application.

$1/\sqrt{n}$ — Monte Carlo-র blessing ও curse. Slow convergence সমস্যা। ৭০ বছরের গবেষণায় অনেক variance reduction techniques. Modern AI-তে অপরিহার্য।

(১) কেন slow?

• CLT: error standard deviation $\sigma/\sqrt{n}$।
• $\sigma$ ছোট হলে — variance কম।
• "Direct" $\sigma$ কমাতে পারলে — fewer samples.

(২) Importance Sampling:

• "Important regions"-এ বেশি sample.
• $E_p[f] = E_q[f \cdot p/q]$ — proposal distribution $q$।
• Weights compensate for biased sampling.
• Optimal $q^* \propto |f| \cdot p$ — variance ০।

উদাহরণ:

import numpy as np

# Naive: f(x) = exp(-x²/2) over [3, ∞)
n = 100000
x = np.random.uniform(3, 10, n)
naive = (10-3) * np.mean(np.exp(-x**2/2))

# Importance: sample from exponential (heavy tail)
x = 3 + np.random.exponential(1.0, n)
weights = np.exp(-(x-3)) * (10-3)  # ratio
better = np.mean(np.exp(-x**2/2) / np.exp(-(x-3)) * 1.0)
print(f"Naive variance: high. Importance: low.")

(৩) Antithetic Variates:

• Pair $(X, X')$ where $X' = -X$ or symmetric.
• $f(X) + f(X')$ — variance reduce if negatively correlated.
• Especially good for symmetric integrands.
• Half computational cost!

(৪) Control Variates:

• $\hat{\theta} = \bar{f} - c(\bar{g} - E[g])$।
• $g$ correlated with $f$, $E[g]$ known.
• Reduce variance using known relationship.

(৫) Stratified Sampling:

• Domain into strata, sample from each.
• Variance always ≤ random sampling.
• Cube discretization in low-D.

(৬) Quasi-Monte Carlo (QMC):

• Random এর বদলে low-discrepancy sequences (Sobol, Halton)।
• Convergence $O(\log^k n / n)$ — much better!
• Caveat: low-D-এ ভাল, high-D-এ break.

(৭) Markov Chain MC (MCMC):

• Complex distribution-এ sample সরাসরি কঠিন।
• Markov chain তৈরি যার stationary distribution = target.
• Metropolis-Hastings, Gibbs sampling, Hamiltonian MC.

(৮) AI-তে variance reduction:

• Reparameterization trick (VAE): $z = \mu + \sigma \cdot \epsilon$ — gradient through sampling.
• Control variates in RL: Advantage = Reward − Value baseline.
• Generalized Advantage Estimation (GAE): Bias-variance trade.
• REINFORCE বনাম PPO: Variance reduction-এ baseline.

(৯) Practical guidelines:

• Always at least try antithetic — free 2x.
• Importance sampling — domain knowledge থাকলে।
• QMC — low-D, smooth integrands.
• Stratified — যেখানে structure আছে।

(১০) Modern research:

• Multi-level Monte Carlo (MLMC): Different precision levels.
• Neural importance sampling: NN learns optimal proposal.
• Sequential MC: Time-evolving distributions.

(১১) Computational reality:

• GPU-এ vectorization — base MC দ্রুত।
• Variance reduction ১০x ভাল = ১০x cheaper.
• Production AI-তে cost matter.

মূল উপলব্ধি: "Just throw more samples" — toy approach. Production-এ variance reduction critical. Diffusion model-এ ৫০ steps vs ১০০০ steps — variance reduction-এর প্রয়োগ। Hidden art of Monte Carlo.

Gal & Ghahramani (২০১৬) এর মূল paper "Dropout as a Bayesian Approximation" — deep learning-এ uncertainty quantification-এর সবচেয়ে practical method. Theoretical elegance + practical simplicity.

(১) Standard Dropout:

• Training-এ randomly neurons turn off (probability $p$)।
• Test-এ all neurons on, scale by $(1-p)$।
• Regularization — overfitting reduce.

(২) Gal-Ghahramani insight:

• "Dropout = approximate Bayesian inference"।
• প্রতিটি dropout mask = different network.
• Multiple masks = ensemble = posterior approximation.

(৩) MC Dropout — test-time:

• Dropout test-এও on রাখুন।
• Same input N বার forward pass — different dropout masks.
• N predictions-এর mean = prediction.
• N predictions-এর variance = uncertainty.

(৪) Code:

import torch

def mc_predict(model, x, n_samples=100):
    model.train()  # dropout on!
    preds = []
    for _ in range(n_samples):
        with torch.no_grad():
            preds.append(model(x))
    preds = torch.stack(preds)
    mean = preds.mean(0)
    std = preds.std(0)  # uncertainty
    return mean, std

(৫) Two types of uncertainty:

• Aleatoric: Data-noise uncertainty — irreducible.
• Epistemic: Model uncertainty — more data → less.
• MC Dropout primarily captures epistemic.

(৬) Benefits:

• No new training — existing dropout model-এ applicable.
• Theoretical foundation — variational inference.
• Computationally cheap (relative to full BNN)।

(৭) Limitations:

• $N$ forward passes — inference slower.
• Calibration ভাল না — over/underconfident.
• Dropout rate — hyperparameter sensitive.
• Out-of-distribution detection limited.

(৮) Production use cases:

• Medical imaging:
  • Diabetic retinopathy detection — uncertainty triage.
  • "Confident vs uncertain" — radiologist priority.
• Self-driving cars:
  • Object detection uncertainty.
  • "Don't know what this is" — slow down.
• Active Learning:
  • Most uncertain samples — label first.
  • Annotation cost reduce.
• Anomaly detection:
  • High uncertainty = unusual input.

(৯) Alternatives:

• Deep Ensembles: Multiple models trained independently. Often outperforms MC Dropout.
• Bayesian NN (BNN): Explicit weight distributions. Computationally expensive.
• SWAG: SGD trajectory-এ Gaussian fit.
• Conformal Prediction: Distribution-free guarantees.

(১০) Calibration metrics:

• Expected Calibration Error (ECE)।
• Brier score.
• Reliability diagram.

(১১) Recent advances:

• Last-layer Bayesian: Just final layer Bayesian — efficient.
• Functional MC Dropout: Function space.
• Test-time augmentation: Input perturbations.

(১২) Bangladesh AI ethics:

• Medical AI deploy — uncertainty critical.
• "Auto-detected from X-ray" — confidence ছাড়া dangerous.
• Bangla NLP-এ rare words — model uncertainty.
• Loan default prediction — explain uncertainty to borrower.

(১৩) The bigger picture:

• "Confident wrong" worst than "uncertain right"।
• AI safety — uncertainty quantification critical.
• Hallucination in LLMs — uncertainty calibration challenge.

মূল উপলব্ধি: MC Dropout — beautiful Monte Carlo application. ১৯৪৭-এর random sampling, ২০১৪-এর dropout, ২০১৬-এর Bayesian interpretation = production-ready uncertainty. Modern AI-এ confident predictions overrated; calibrated uncertainty undervalued.