Méthodes de Monte-Carlo

 ECTS

SEMESTRE

CM

TD

TP

EI

Travail personnel

7 h

14 h

0 h

0 h

36 h

Langues d'enseignement

Français

Responsable(s)

Mots clefs

Simulation aléatoire ; Méthode de Monte-Carlo ; Réduction de la variance ; Méthodes MCMC ; Recuit simulé ; Descente de gradient stochastique

Prérequis

Théorie des probabilités (niveau M1) ; Rudiments de Python

À l’issue du module, les étudiants seront en mesure d'utiliser la simulation aléatoire pour résoudre des problèmes déterministes complexes.

   Ce cours se compose de deux volets distincts (quoique étroitement connectés), qui partagent en commun le fait de recourir à des procédés de simulation aléatoire pour résoudre des problèmes dont l'énoncé est pourtant défini de manière parfaitement déterministe, sans faire intervenir d'aléa.

   Le premier volet du cours porte sur la « méthode de Monte-Carlo » pour évaluer une quantité de nature intégrale (donc déterministe), consistant à écrire celle-ci, dans un premier temps, en tant qu'espérance probabiliste, puis à estimant statistiquement cette espérance à l'aide de simulations aléatoires. Dans plusieurs cas d'usage, le résultat approché que cette méthode fournit concernant le calcul de la quantité d'intérêt s'avèrera plus précis que celui qu'on aurait obtenu par des méthodes d'analyse numérique “classiques” !

   Outre l'estimation de la quantité d'intérêt en tant que telle, le cours expliquera aussi comment déterminer l'intervalle de confiance associé à l'estimateur obtenu. Il peut être important de disposer de moyens de réduire la largeur de l'intervalle qu'on arrive à obtenir pour un cout de calcul donné : cela est l'objectif des techniques dites de réduction de la variance. Le cours présente quatre de ces techniques : l'échantillonnage préférentiel ; le conditionnement ; le couplage ; et la variable de contrôle.

   Dans certaines situations d'usage, la simulation des variables aléatoires s'avère être un problème plus complexe que la mise en œuvre de la méthode de Monte-Carlo elle-même. Le cours expliquera comment on peut alors, dans de nombreux cas, utiliser les méthodes de chaines de Markov pour Monte-Carlo [dites « méthodes MCMC »] pour pallier cette difficulté.

   À partir du chapitre sur les chaines de Markov pour Monte-Carlo, on effectuera une transition naturelle vers le second volet du cours, consacré pour sa part aux méthodes stochastiques d'optimisation de fonctions. On commencera par présenter la plus célèbre de ces méthodes, à savoir le recuit simulé : celui-ci étant étroitement apparenté à l'algorithme MCMC de Metropolis-Hastings qu'on aura vu précédemment. Le cours explique aussi comment on peut améliorer le recuit simulé par l'idée de recuit parallèle (« parallel tempering »).

   Le dernier chapitre, enfin, sera consacré à la méthode de descente de gradient stochastique, un procédé d'optimisation qui est notamment au cœur de l'entrainement des réseaux de neurones artificiels !

   Ce module comprendra une large partie de mise en œuvre informatique des concepts étudiés, que nous effectuerons en l'occurrence avec Python.

Niveaux

Description et verbes opérationnels

Connaître 

Connaitre le protocole d'estimation d'une espérance par méthode de Monte-Carlo, et la façon de déterminer l'intervalle de confiance associé

Connaitre les principales techniques de réduction de la variance

Connaitre le principe des méthodes MCMC, en particulier les chaines de Metropolis-Hastings

Connaitre l'algorithme de recuit simulé ; l'algorithme de recuit parallèle ; l'algorithme de descente de gradient stochastique

Comprendre

Comprendre dans quelles situations la méthode de Monte-Carlo pour le calcul d'une espérance est pertinente, quelles sont ses forces et ses limites

Comprendre le comportement des chaines de Markov impliquées dans les différents algorithmes d'évolution stochastique abordés dans ce cours

Appliquer 

Déterminer théoriquement les quantités auxiliaires requises par les méthodes abordées dans ce cours : fonction de quantile d'une loi à simuler ; espérance d'une variable de contrôle ; ratios de densité d'une mesure à échantillonner par Metropolis-Hastings ; gradient de la fonction dont on optimise l'espérance ; etc.

Implémenter informatiquement une méthode de Monte-Carlo, une technique de réduction de la variance

Implémenter informatiquement un algorithme de Metropolis-Hastings, de recuit simulé (éventuellement parallèle), de descente de gradient stochastique

Analyser 

Choisir une technique de réduction de la variance adaptée au calcul considéré

Identifier les situations où les chaines de Markov pour Monte-Carlo sont à privilégier sur la simulation “directe”

Reconnaitre une situation se prêtant à telle ou telle méthode stochastique d'optimisation

Régler adroitement les paramètres des algorithmes stochastiques

Synthétiser

Évaluer

Porter un regard critique sur la convergence d'un estimateur de Monte-Carlo

Porter un regard critique sur la solution obtenue par un procédé stochastique d'optimisation

Contrôle Continu

Examen écrit

Oral / Soutenance

Rapport / Projet