Programmé en UV2 MAJ MTS
Présentation :
L'objectif de ce module est de présenter aux étudiants d'une manière que nous espèrons simple un certain nombre de concepts et méthodes relativement avancés en probabilités et statistiques.
Ce module d'enseignement abordera les domaines suivants: théorèmes limites (lois des grands nombres, théorème de la limite centrale), théorie des grandes déviations, méthodes de Monte Carlo par Chaînes de Markov (MCMC), et l'algorithme Expectation Maximization (EM).
Pour faciliter l'apprentissage 3 séances de Travaux Pratiques sont programmées; lors de ces séances les étudiants pourront appréhender par l'expérience les théorèmes vus en cours (Limite Centrale, Cramer, etc...) dans des cas simples (jeux de pile ou face, etc...), et mettre en oeuvre certains algorithmes avancés présentés en cours (méthode forward backward par exemple).
Objectifs (obsolète):
- Rappels sur les Théorèmes Limites (Cours I), séance de TP associée (TP I): l'objectif de ce cours est de présenter les principaux théorèmes de la théorie des probabilités et de manipuler ces théorèmes au travers de quelques exercices simples. Lors de la séance de TP associée (TP I) les étudiants pourront observer par la simulation sur ordinateurs l'effet des théorèmes limites (lois des grands nombres, théorème central limite).
- Chaînes de Markov (Cours II et III): les chaînes de Markov (à temps discret ou à temps continu) sont des processus aléatoires caractérisés par une propriété de dépendance des valeurs futures du processus à la valeur présente uniquement. Les chaînes de Markov sont très utilisées pour modéliser un grand nombre de phénomènes qui vérifient cette propriété de Markov faible. En particulier, dans le domaine des télécommunications et plus particulièrement de l'évaluation de performances, les chaînes de Markov sont un outil essentiel pour modéliser les phénomènes d'attente (accès concurrent à une ressource partagée comme la bande passante, le disque, le CPU...). Les Cours II et III porteront respectivement sur les chaînes de Markov à temps discret et sur les chaînes de Markov à temps continu. Il est important d'acquérir des bases sur les processus markoviens avant d'aborder les cours IV et V (méthodes de Monte Carlo par chaînes de Markov) et VI et VII (algorithme Expectation Maximization).
- Méthodes de Monte Carlo par Chaînes de Markov (Cours IV et V): il s'agit ici d'une famille d'algorithmes (Hastings Metropolis, Gibbs, recuit simulé) qui reposent tous sur un même principe: simuler une chaîne de Markov qui converge en distribution vers une loi que l'on se donne comme loi cible. Ces méthodes sont surtout utilisées dans un cadre bayésien, c'est-à-dire quand certaines quantités non observées sont considérées comme étant elles-mêmes des variables aléatoires, la loi cible étant alors la loi a posteriori (loi de ces variables "cachées" conditionnellement à la valeur des variables observées).
- Algorithme Expectation Maximization (Cours VI et VII), séance de TP associée (TP II): l'algorithme Expectation Maximization (EM), présenté dans sa généralité par Dempster, Laird et Rubin en 1977, est une technique essentiellement utilisée pour identifier les paramètres des modèles à "données manquantes" (modèles de mélanges, modèles de chaînes de Markov cachées, modèles à données censurées, etc...). L'identification des paramètres des modèles en données manquantes est un problème complexe. L'objectif des Cours VI et VII est de présenter l'algorithme EM, de démontrer certaines de ces propriétés (propriété de stabilité), et de détailler suffisamment les étapes E et M de cet algorithme pour que les étudiants soient capables de le mettre en oeuvre lors de la séance de TP qui sera associée à ce cours (TP2). Nous verrons aussi comment l'algorithme EM peut être utilisé pour résoudre des systèmes linéaires inverses avec contraintes de positivité (problèmes LININPOS) au sens de la minimisation de la divergence de Küllback-Leibler entre les termes de droite et de gauche de ces systèmes linéaires (Vardi, 1992).
- Théorie des Grandes Dévations (Cours VIII) et TP associé (TP 3): la théorie des grandes déviations s'intéresse à l'estimation de la probabilité des événements rares; c'est une théorie asymptotique par nature; on peut considérer la théorie des grandes déviations comme une extension des théorèmes limites; pour l'ingénieur télécom (en particulier l'ingénieur en télétrafic) la théorie des grandes déviations est utile, par exemple, pour calculer des quantités comme la probabilité de débordement d'un buffer, de violation d'un SLA, pour la caractérisation d'un trafic (multimédia) par sa bande passante effective, etc...
Pré-requis :
- bases en probabilités et en statistiques
- bases en algorithmique (programmation en langage Matlab, ou Octave, ou Scilab)
Liens :
Dublin Institute for Advances Studies, Applied Probability Group, http://www.stp.dias.ie/APG/dias_apg_pub.html [tutorial sur la théorie des grandes déviations]
Volume horaire :
21h
Contenu détaillé :
Nous présentons ici le contenu détaillé de chacune des parties de ce cours:
- Cours I: inégalité de Markov, inégalité de Chebyshev, inégalité de Jensen, lois faible et forte des grands nombres, théorème de la limite centrale
- TP I: cette étude par simulation portera sur l'estimation de la valeur de la constante PI par des lancers de fléchettes sur une cible; on expérimentera les théorèmes limites (lois des grands nombres, théorème central limite) par la simulation sur ordinateurs.
- Cours II et III (chaînes de Markov): propriété de Markov faible, homogénéité, probabilité de transition, générateur infinitésimal, diagramme de transition d'états, équations de Chapman Kolmogorov, irréductibilité, périodicité/récurrence nulle/récurrence non nulle, ergodicité, équations d'équilibrage de charge
- Cours IV et V (méthodes MCMC): méthodes "directes" pour simuler des variables aléatoires (inversion de la fonction de répartition, Box et Müller, etc...), technique d'échantillonage d'importance, méthode acceptation/rejet, algorithme de Hastings Metropolis, méthode du recuit simulé, algorithme d'échantillonage de Gibbs
- Cours VI et VII (algo. EM): rappel sur l'estimation Maximum Likelihood, modèles à données incomplètes, fonction Q de l'algorithme EM, présentation des étapes E et M, stabilité numérique de l'algorithme EM, convergence (vers un point selle ou un extrêmum local), mise en oeuvre pratique de l'étape E dans le cas des modèles de Markov cachés (algorithme avant/arrière), méthode EM pour la résolution des problèmes LININPOS [si temps disponible]
- TP II: la séance de TP II permettra aux étudiants de mettre en oeuvre l'algorithme EM sous la forme d'un script Matlab, dans le cas de l'identification des paramètres d'une chaîne de Markov cachée: nous prendrons le cas de l'identification des paramètres d'un modèle de trafic MMPP (Markov Modulated Poisson Process) ou du décodage MAP (Maximum A Posteriori) d'un code convolutif sur un canal à bruit additif blanc gaussien.
- TP III: ce TP aura lieu avant le cours VIII auquel il est associé. Lors du TP 3 les étudiants pourront observer par la simulation sur ordinateurs le théorème de Chernoff (et le comparer au théorème de la limite centrale) dans le cas de la distribution du nombre de "piles" dans un jeu de pile ou face.
- Cours VIII (grandes déviations): fonction génératrice des moments, fonction génératrice des cumulants, transformée de Legendre Fenchel, fonction de taux des grandes déviations, cas particulier des variables de Bernoulli, de Gauss et exponentielle, théorème de Chernoff
Année 2006/2007
Dernière mise à jour le 20-JUL-06
Validation par le responsable de programme le
|
