Introduction aux modèles graphiques

Projets de fin de cours

Description

Le projet vous donne l'opportunité d'étudier plus en profondeur certains concepts du cours. Le sujet du projet doit être relié aux algorithmes, concepts ou méthodes présentées pendant le cours, mais à part cela, le choix du sujet est relativement libre. En particulier, il peut se faire "a la carte" selon vos interets.

Les projets de fin de cours peuvent prendre la forme suivante:

    * Une revue d'article(s) autour d'un sujet donné (articles de recherches ou chapitres du polycopié non étudiés en cours). Voir ci-dessous pour une liste de projets intéressants. 

    * Projet applicatif: application des méthodes vues en cours à un problème donné vous interessant (par exemple en vision, traitement du signal, intelligence artificielle, contrôle, etc...). Le projet peut se faire en commun avec un autre cours (après accord de l'enseignant correspondant), comme le cours de vision artificielle (Jean Ponce, Josef Sivic, Cordelia Schmid). Voir ci-dessous pour des exemples d'application des modèles graphiques.

    * Un projet théorique ou méthodologique.

Le projet doit s'effectuer seul ou a deux eleves (presentation, rapport). Une fois que vous avez une idée du projet qui vous intéresse, il est obligatoire de le faire valider par l'enseignant (par e-mail). En particulier, dans la mesure du possible, chaque personne/binome devra choisir un sujet different (les sujets deja choisis seront indiques comme tels sur la page web).


Evaluation

Le projet de fin de cours compte pour un tiers de la note finale. L'evaluation se fera sur:

    * Un rapport de moins de 6 pages présentant le projet et les resultats obtenus (en cas de projets applicatifs). Le rapport doit être écrit de telle sorte qu'une personne ayant suivi le cours puisse comprendre (pas besoin d'introduire longuement les modèles graphiques). Le rapport devra clairement présenter en français ou en anglais le problème étudié et les approches déjà existantes. Vous serez plus jugés sur la clarté du rapport que sur sa longueur.

    * Une présentation de 5 minutes (ou 10 pour les binomes) à l'ensemble de la classe (le 15 janvier 2010, de 14h a 17h, salle 103, ENS Cachan). La présentation (en français ou en anglais pour les non francophones) s'adresse aux autres élèves et le but est de faire ressortir dans le temps imparti les points importants (Attention à ne pas dépasser le temps imparti).



Revue d'articles ou de chapitres

Cette liste de projets a pour but de vous montrer des articles classiques (et si possible intéressants) utilisant ou améliorant les modèles graphiques. Cela peut donner une idée des sujets de recherches actuels ainsi que des possibilités de projets applicatifs. Même si vous n'en choisissez aucun dans cette liste, il est fortement conseillé d'en lire quelques-uns.


Analyse en composantes principales probabiliste Interpretation de l'ACP avec un modele graphique proche de l'analyse factorielle. Situation ou EM n'a pas de minima locaux.

Tipping, M. E.,  Bishop, C. M. 1999. Probabilistic principal component analysis. Journal of the Royal Statistical Society, Series B 61(3):611-622. [pdf]
 
Apprentissage de la structure - modeles multinomiaux Pour des donnees completes discretes, apprentissage des parametres et du graphe oriente.

D. Heckerman, D. Geiger, D. Chickering. Learning Bayesian networks: The Combination of Knowledge and Statistical Data.  Machine Learning, 20:197-243, 1995.

Apprentissage de la structure - modeles Gaussiens Pour des donnees completes Gausssiennes, apprentissage des parametres et du graphe oriente.

D. Geiger, D. Heckerman. Learning Gaussian networks.  Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence, pp. 235--243.
Methodes variationnelles pour l'inference Classe de technique pour l'inference approchee.

An introduction to variational methods for graphical models. M. I. Jordan, Z. Ghahramani, T. S. Jaakkola, and L. K. Saul. In M. I. Jordan (Ed.), Learning in Graphical Models, Cambridge: MIT Press, 1999
Methodes de simulations pour l'inference
(filtres particulaires)
Une methode de simulations pour les modeles graphiques dynamiques
Chapitre du polycopie

S. Arulampalam, S. Maskell, N. J. Gordon, and T. Clapp, A Tutorial on Particle Filters for On-line Non-linear/Non-Gaussian Bayesian Tracking, IEEE Transactions of Signal Processing, Vol. 50(2), pages 174-188, February 2002.

Doucet A., Godsill S.J. and Andrieu C., "On sequential Monte Carlo sampling methods for Bayesian filtering," Statist. Comput., 10, 197-208, 2000
 
Modeles Semi-Markoviens Une classe de modeles permettant de modeliser le temps passe dans chaque etat d'une chaine de Markov. Application aux modeles de Markov caches.

Note from Kevin Murphy [pdf]
Apprentissage de parametres dans les modeles graphiques non orientes (champs de Markov) Chapitre 9 du polycopie et articles.
Principe du maximum d'entropie - Dualite avec le maximum de vraisemblance Chapitre 19 du polycopie

S. Della Pietra, V. Della Pietra, and J. Lafferty, Inducing features of random fields,  IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, no. 4, pp. 380-393, April 1997
Modeles graphiques dynamiques Chapitre du polycopie. Sujets specifiques a definir.
Distributions conjuguees et inference Bayesienne Distributions a priori "pratiques" pour l'inference Bayesienne.
Applications generales de l'algorithme somme-produit (comme par exemple a la FFT) The generalized distributive law, S. M. Aji, R. J. Mceliece
Information Theory, IEEE Transactions on, Vol. 46, No. 2. (2000), pp. 325-343.



Exemples d'applications des modeles graphiques

Ces articles presentent des applications classiques. Ils peuvent vous donner des idees pour un projet applicatif ou etre utilises pour une revue d'articles.

Bioinformatique Chapitre du polycopie (demander le login/pwd par e-mail)
Vision/parole Segmentation d'images par EM:
Blobworld: Image Segmentation Using Expectation-Maximization and Its Application to Image Querying; Chad Carson, Serge Belongie, Hayit Greenspan and Jitendra Malik. IEEE Trans. on Pattern Analysis and Machine Intelligence, 24(8), 1026-1038, August 2002.

Articles de Kevin Murphy:
"Using the Forest to See the Trees:A Graphical Model Relating Features, Objects and Scenes"  Kevin Murphy, Antonio Torralba, William Freeman. NIPS'03 (Neural Info. Processing Systems)

Dynamic Bayesian Networks for Audio-Visual Speech Recognition  A. Nefian, L. Liang, X. Pi, X. Liu and K. Murphy. EURASIP, Journal of Applied Signal Processing, 11:1-15, 2002
Robotique Construction automatique de cartes:
Simultaneous Localization and Mapping with Sparse Extended Information Filters
Thrun et al. The International Journal of Robotics Research.2004; 23: 693-716.
(voir aussi chapitre du poly sur les KF)
Texte Naive Bayes:
A. McCallum and K. Nigam. A comparison of event models for Naive Bayes text classification. In AAAI-98 Workshop on Learning for Text Categorization, 1998. 

Latent Dirichlet allocation. D. Blei, A. Ng, and M. Jordan. Journal of Machine Learning Research, 3:993-1022, January 2003. [ .ps.gz | .pdf | code ]
Texte - Linguistique S. Vogel, H. Ney, and C. Tillmann. HMM-based word alignment in statistical translation. In Proceedings of the 16th conference on Computational linguistics, pp. 836-841, Morristown, NJ, USA, 1996. Association for Computational Linguistics.



Implementation d'algorithmes

N configurations les plus probables Implementation d'un algorithme (HMM ou graphes plus complexes), a partir des articles suivants:
Dennis Nilsson, Jacob Goldberger
s. An Efficient Algorithm for Sequentially finding the N-Best List , IJCAI, 1999
Chen Yanover, Yair Weiss, Finding the M Most Probable Configurations Using Loopy Belief Propagation, NIPS 2003.
 
Calcul (approche) de la largeur arborescente Comparer les heuristiques classiques a des methodes plus fines:
Mark Hopkins and Adnan Darwiche
A Practical Relaxation of Constant-Factor Treewidth Approximation Algorithms
Proceedings of the First European Workshop on Probabilistic Graphical Models 2002

ou exactes dans des cas particuliers:
Stefan Arnborg, Derek G. Corneil, Andrzej Proskurowski, Complexity of finding embeddings in a k-tree, SIAM Journal on Algebraic and Discrete Methods (1997)