Accueil › Glossaire › Monte Carlo

Monte Carlo (Méthodes de Monte Carlo)

Les méthodes de Monte Carlo sont une famille d’algorithmes computationnels qui utilisent l’échantillonnage aléatoire répété pour obtenir des résultats numériques. En intelligence artificielle et en machine learning, elles permettent d’approximer des distributions de probabilité complexes, d’estimer des intégrales intractables et de simuler des systèmes stochastiques.

Le nom vient du casino de Monte-Carlo à Monaco, en référence au caractère aléatoire de ces méthodes. Le principe fondamental est simple : si vous ne pouvez pas calculer quelque chose analytiquement, simulez-le un grand nombre de fois et prenez la moyenne. Par la loi des grands nombres, cette moyenne converge vers la vraie valeur quand le nombre de simulations tend vers l’infini.

En IA, les méthodes de Monte Carlo sont omniprésentes. Elles alimentent l’inférence bayésienne (MCMC pour approximer les postérieures), le reinforcement learning (Monte Carlo Tree Search dans AlphaGo, estimations de retour Monte Carlo), les modèles génératifs (échantillonnage dans les VAE et les modèles de diffusion), l’estimation d’incertitude, et l’optimisation stochastique.

Le principe Monte Carlo

L’intuition : estimer par le hasard

Imaginez que vous voulez calculer l’aire d’un lac de forme irrégulière. L’approche analytique nécessiterait de résoudre des intégrales complexes sur le contour du lac. L’approche Monte Carlo est plus directe : lancez des milliers de cailloux aléatoirement sur une zone qui contient le lac. Comptez combien tombent dans l’eau. Le rapport « cailloux dans l’eau / cailloux total » multiplié par l’aire totale de la zone donne une estimation de l’aire du lac. Plus vous lancez de cailloux, plus l’estimation est précise.

C’est exactement le même principe pour estimer π : inscrivez un cercle dans un carré, lancez des points aléatoires, et le rapport des points dans le cercle sur le total converge vers π/4. C’est un exemple classique, mais le vrai pouvoir des méthodes Monte Carlo se révèle en haute dimension, où les méthodes déterministes (quadrature) deviennent exponentiellement coûteuses tandis que Monte Carlo reste faisable.

Le formalisme

On veut calculer l’espérance d’une fonction f(x) sous une distribution P(x) :

E_P[f(x)] = ∫ f(x) · P(x) dx

L’estimateur Monte Carlo est simplement la moyenne empirique sur N échantillons tirés de P :

Ê[f(x)] = (1/N) · Σᵢ f(xᵢ), xᵢ ~ P(x)

Par la loi des grands nombres, cet estimateur converge vers la vraie espérance quand N → ∞. Le théorème central limite garantit que l’erreur décroît en O(1/√N), indépendamment de la dimension de x. C’est crucial : en dimension 100, une quadrature nécessiterait 10^100 points, tandis que Monte Carlo reste praticable avec quelques milliers d’échantillons.

Les techniques d’échantillonnage

Monte Carlo simple (échantillonnage direct)

Quand on peut tirer directement des échantillons de P(x) (par exemple si P est une gaussienne ou une uniforme), l’estimation Monte Carlo est triviale. On tire N échantillons i.i.d. et on calcule la moyenne. C’est rapide et simple, mais ça suppose qu’on sait échantillonner P, ce qui est rarement le cas pour les postérieures bayésiennes complexes.

Échantillonnage par rejet (Rejection Sampling)

Quand on ne peut pas échantillonner directement P mais qu’on connaît sa forme (à une constante près), on utilise une distribution enveloppe Q facile à échantillonner. On tire un échantillon x de Q, puis on l’accepte avec une probabilité proportionnelle à P(x)/Q(x). Les échantillons acceptés suivent la distribution P.

Le problème du rejection sampling est son efficacité : en haute dimension, le taux d’acceptation chute exponentiellement car il est difficile de trouver une enveloppe Q qui soit à la fois facile à échantillonner et suffisamment proche de P.

Échantillonnage par importance (Importance Sampling)

Au lieu d’échantillonner P directement, on échantillonne une distribution proposale Q(x) plus facile, puis on corrige le biais en pondérant chaque échantillon par le rapport w(x) = P(x)/Q(x) (poids d’importance) :

E_P[f(x)] ≈ Σᵢ wᵢ · f(xᵢ) / Σᵢ wᵢ, xᵢ ~ Q(x)

L’importance sampling ne nécessite pas de connaître la constante de normalisation de P (elle s’annule dans le ratio). C’est la base des filtres particulaires (Sequential Monte Carlo) utilisés en suivi d’objets et en traitement du signal. La difficulté est de choisir Q : si Q est trop différente de P, les poids sont très variables et l’estimation est instable.

MCMC : Markov Chain Monte Carlo

MCMC est la combinaison de deux idées : les chaînes de Markov et l’échantillonnage Monte Carlo. Au lieu de tirer des échantillons indépendants (impossible pour les postérieures complexes), on construit une chaîne de Markov dont la distribution stationnaire est la distribution cible P(x). En faisant tourner la chaîne assez longtemps, les échantillons produits se comportent comme des tirages de P.

L’histoire commence en 1953 au laboratoire de Los Alamos, quand Nicholas Metropolis et ses collègues ont conçu l’algorithme de Metropolis pour simuler des systèmes physiques. Hastings l’a généralisé en 1970. Mais c’est la « révolution MCMC » des années 1990 en statistique, initiée par les travaux de Gelfand et Smith (1990) sur le Gibbs sampler, qui a démocratisé ces méthodes.

Metropolis-Hastings

L’algorithme Metropolis-Hastings est le MCMC le plus général. À chaque itération :

1. Proposer un nouveau point x’ à partir du point actuel x via une distribution proposale Q(x’|x).

2. Calculer le ratio d’acceptation α = min(1, [P(x’)·Q(x|x’)] / [P(x)·Q(x’|x)]).

3. Accepter x’ avec probabilité α (sinon rester en x).

La beauté de cet algorithme est qu’il ne nécessite que le ratio P(x’)/P(x), pas la constante de normalisation de P. C’est exactement ce dont on a besoin en inférence bayésienne, où la postérieure est connue à une constante près.

Le choix de la proposale Q est critique. Trop large, les propositions sont souvent rejetées (l’algorithme stagne). Trop étroite, les pas sont trop petits et l’exploration est lente (forte autocorrélation). La règle empirique est de viser un taux d’acceptation autour de 23 % pour les distributions continues multidimensionnelles.

Gibbs Sampling

Le Gibbs sampling (Geman et Geman, 1984) est un cas particulier de MCMC qui met à jour les variables une par une, conditionnellement à toutes les autres. À chaque itération, pour chaque variable zᵢ, on échantillonne zᵢ ~ P(zᵢ | z₁, …, zᵢ₋₁, zᵢ₊₁, …, zₙ, x).

L’avantage est qu’il n’y a pas de rejet : chaque échantillon est toujours accepté. L’inconvénient est qu’il nécessite de connaître les distributions conditionnelles, ce qui n’est possible que pour certaines familles de modèles (modèles conjugués, graphes factorisés). Le Gibbs sampling est le moteur de l’inférence dans les logiciels comme BUGS, JAGS et Stan (via NUTS).

Hamiltonian Monte Carlo (HMC)

HMC (Duane et al., 1987 ; Neal, 2011) est la méthode MCMC la plus efficace pour les distributions continues de haute dimension. Au lieu de faire des pas aléatoires, HMC exploite la dynamique hamiltonienne (la physique des systèmes conservatifs) pour proposer des mouvements qui explorent l’espace efficacement.

L’analogie physique : imaginez une bille sur une surface dont la hauteur est proportionnelle à -log P(x). On donne une impulsion aléatoire à la bille et on la laisse rouler selon les équations de Hamilton pendant un certain temps. Le point d’arrivée est la proposition. Les régions de haute probabilité correspondent aux vallées, et la bille y passe naturellement plus de temps.

NUTS (No-U-Turn Sampler, Hoffman et Gelman, 2014) automatise le choix des hyperparamètres de HMC (nombre de pas, taille du pas), éliminant un frein majeur à l’adoption. Stan, le logiciel de programmation probabiliste le plus utilisé en statistique bayésienne, repose sur NUTS.

Applications en IA et ML

Inférence bayésienne

C’est l’application historique et la plus importante des méthodes Monte Carlo en ML. MCMC permet d’approximer la postérieure P(θ|données) des paramètres θ d’un modèle, fournissant non seulement une estimation ponctuelle mais aussi une quantification complète de l’incertitude. C’est la différence entre dire « le paramètre vaut 0.73 » et « le paramètre est entre 0.65 et 0.81 avec 95% de probabilité ».

Les réseaux de neurones bayésiens utilisent MCMC (ou son alternative, la VI) pour placer des distributions sur les poids. Le résultat est un modèle qui quantifie son incertitude, essentiel pour les applications critiques.

Monte Carlo Tree Search (MCTS)

MCTS est l’algorithme derrière AlphaGo, AlphaZero et MuZero. Pour choisir un coup dans un jeu (Go, échecs), MCTS construit un arbre de recherche en simulant des milliers de parties aléatoires à partir de chaque position possible. Les branches qui mènent le plus souvent à la victoire sont explorées plus en profondeur (balance exploration/exploitation via UCB1).

MCTS est un cas particulier de méthode Monte Carlo appliquée à la planification dans les MDP (Markov Decision Processes). C’est aussi la base des algorithmes de planification dans le reinforcement learning, où l’agent « imagine » des trajectoires futures avant de choisir une action.

Monte Carlo en reinforcement learning

Les méthodes Monte Carlo en RL estiment la valeur d’un état (ou d’une paire état-action) en moyennant les retours observés sur des épisodes complets. Contrairement aux méthodes de différence temporelle (TD), elles n’utilisent pas de bootstrap : elles attendent la fin de l’épisode pour calculer le retour réel.

L’avantage est l’absence de biais (le retour est exact, pas estimé). L’inconvénient est la variance élevée (un seul épisode peut être non représentatif) et l’impossibilité d’apprendre pendant l’épisode (il faut attendre la fin). En pratique, les méthodes TD et actor-critic (qui combinent MC et TD) dominent, mais les estimations MC restent utilisées comme baseline et dans certains algorithmes comme REINFORCE.

Modèles génératifs

L’échantillonnage Monte Carlo est au coeur de tous les modèles génératifs. Les VAE utilisent la reparamétrisation (un cas spécial d’échantillonnage Monte Carlo) pour estimer le gradient de l’ELBO. Les modèles de diffusion effectuent un échantillonnage itératif (chaque pas de débruitage est un échantillonnage conditionnel). L’estimateur de gradient REINFORCE (score function estimator) utilisé dans le BBVI et le RLHF est un estimateur Monte Carlo.

Sequential Monte Carlo (Filtres Particulaires)

Les méthodes SMC (aussi appelées filtres particulaires) étendent Monte Carlo aux distributions qui évoluent dans le temps. On maintient un ensemble de « particules » (échantillons pondérés) qui représentent la distribution courante. À chaque pas de temps, les particules sont propagées, pondérées par la vraisemblance des nouvelles observations, et rééchantillonnées. Les applications incluent le suivi d’objets, la localisation de robots, le traitement du signal, et la finance quantitative.

MCMC vs Variational Inference

Outils et librairies

Stan : le logiciel de référence pour l’inférence bayésienne par MCMC. Utilise NUTS (HMC automatique) et s’interface avec Python (PyStan, CmdStanPy) et R (RStan). Idéal pour les modèles statistiques traditionnels et les modèles hiérarchiques.

PyMC : framework Python pour la modélisation bayésienne. Supporte NUTS, Metropolis, Sequential MC, et s’intègre avec JAX pour l’accélération GPU.

Pyro / NumPyro : frameworks de programmation probabiliste (PyTorch / JAX) qui supportent à la fois MCMC et VI, avec passage fluide de l’un à l’autre. NumPyro utilise NUTS compilé en JAX pour des performances excellentes.

Turing.jl : framework Julia pour MCMC composable (HMC, NUTS, Gibbs, SMC, particle MCMC), exploitant les performances de Julia et la différentiation automatique.

emcee : échantillonneur MCMC en Python basé sur l’algorithme affine-invariant (Goodman et Weare), populaire en astrophysique et en sciences physiques pour sa simplicité et sa parallélisation facile.

Défis pratiques

Burn-in : les premiers échantillons d’une chaîne MCMC sont biaisés par le point de départ. On les jette (« burn-in ») avant de collecter les échantillons utiles. Typiquement, on jette les 10 à 50 % premiers échantillons, mais la taille optimale du burn-in est difficile à déterminer.

Diagnostic de convergence : comment savoir si la chaîne a convergé vers la distribution cible ? Les métriques courantes incluent le R-hat (Gelman-Rubin, qui compare la variance intra-chaîne et inter-chaîne sur plusieurs chaînes parallèles), l’Effective Sample Size (nombre d’échantillons effectivement indépendants après correction de l’autocorrélation), et l’inspection visuelle des traces.

Malédiction de la dimensionnalité : en haute dimension, les régions de haute probabilité deviennent des « coquilles » fines et difficiles à trouver. Metropolis-Hastings classique perd en efficacité. HMC atténue ce problème mais ne l’élimine pas pour les dimensions extrêmes (millions de paramètres).

Multimodalité : quand la distribution cible a plusieurs modes séparés, les chaînes MCMC peuvent rester coincées dans un seul mode pendant très longtemps. Les méthodes de tempering (parallel tempering, simulated tempering) et les méthodes SMC aident à traverser les barrières entre modes.