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 les enseignants (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 "poster presentation" de 5 minutes à partir de moins de 8 feuilles A4, qui seront affichees au mur (le 15 decembre 2010, de 9h a 12h, salle I3, ENS Cachan). La présentation (en français ou en anglais pour les non francophones) s'adresse aussi aux autres élèves et le but est de faire ressortir dans le temps imparti les points importants.


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 Gaussiennes, 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

Une approche des méthodes variationelles pour l'inférence bayésienne:

Beal, M.J. and Ghahramani, Z.
Variational Bayesian Learning of Directed Graphical Models with Hidden Variables
To appear in Bayesian Analysis 1(4), 2006.
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.
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.
Analyse en composantes independantes A. Hyvärinen, E. Oja (2000): Independent Component Analysis: Algorithms and Application, Neural Networks, 13(4-5):411-430, 2000.

Cours de Hervé LeBorgne: http://www.eeng.dcu.ie/~hlborgne/pub/th_chap3.pdf
Jean-François Cardoso Dependence, Correlation and Gaussianity in Independent Component Analysis. Journal of Machine Learning Research 4(Dec):1177--1203, 2003. [pdf]

Analyse des correlations canoniques

L'ACC est un analogue de l'ACP pour l'analyse de la covariance entre entre deux variables aléatoires vectorielles X et Y.
  1. D. R Hardoon, S. Szedmak, et J. Shawe-Taylor, “Canonical correlation analysis: an overview with application to learning methods,” Neural Computation 16, no. 12 (2004): 2639–2664. 
  2. F. R Bach et M. I Jordan, “A probabilistic interpretation of canonical correlation analysis,” Dept. Statist., Univ. California, Berkeley, CA, Tech. Rep 688 (2005). 

Clustering par mélange d'ACP

M. E Tipping et C. M Bishop, “Mixtures of probabilistic principal component analyzers,” Neural computation 11, no. 2 (1999): 443–482.

Modèles relationels stochastiques
  • E. M Airoldi et al., “Mixed membership stochastic block models for relational data with application to protein-protein interactions,” dans Proceedings of the International Biometrics Society Annual Meeting, 2006.

  • Champs de Markov conditionels
    Charles Sutton, Andrew McCallum An Introduction to Conditional Random Fields for Relational Learning . In Lise Getoor and Ben Taskar, editors, Introduction to Statistical Relational Learning. MIT Press. 2007.


    Le processus de Dirichlet
  • R. M Neal, “Markov chain sampling methods for Dirichlet process mixture models,” Journal of computational and graphical statistics 9, no. 2 (2000): 249–265. 
  • Y. W Teh, “Dirichlet Process,” Submitted to Encyclopedia of Machine Learning (2007). 
  • A. Ranganathan, “The Dirichlet Process Mixture (DPM) Model” (2004). 


  • Modèles de Markov cachés factoriels
    Les HMM factoriels modélisent les états latent comme des produits d'états. Ils permettent d'introduire une structure combinatoire des états.
    1. Z. Ghahramani et M. I Jordan, “Factorial hidden Markov models,” Machine learning 29, no. 2 (1997): 245–273. 

    Generalized PCA
    1. M. Collins, S. Dasgupta, et R. E Schapire, “A generalization of principal component analysis to the exponential family,” Advances in neural information processing systems 1 (2002): 617–624. 

    Apprentissage de la structure dans les modèles graphiques Gaussien par régularisation L1

    Les méthodes de parcimonie convexe sont une approche récente au problème d'apprentissage de structure.
    1. J. Friedman, T. Hastie, et R. Tibshirani, “Sparse inverse covariance estimation with the graphical lasso,” Biostatistics 9, no. 3 (2008): 432. 



     Mélange de densités log-concave
     Les densités log-concave fournissent un modèle non-paramétrique intéressant pour modéliser les densités unimodales.

  • T Chang et G. Walther, “Clustering with mixtures of log-concave
    distributions
    ,” Computational Statistics & Data Analysis 51, no. 12
    (2007): 6242–6251.
  • G. Walther, “Inference and modeling with log-concave distributions,” Statistical Science 25 (2010).


  • Satisfaction de contrainte et sudoku

    T. K Moon et J. H Gunther, “Multiple constraint satisfaction by
    belief propagation: An example using sudoku
    ,” dans Adaptive and
    Learning Systems, 2006 IEEE Mountain Workshop on, 2006, 122–126.




    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)

    HMM phylogénétique:
    A. Siepel et D. Haussler, “Phylogenetic hidden Markov models,” Statistical methods in molecular evolution (2005), 3, 325–351. 

    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.

    Grammaires non-contextuelles probabilistes:
    Notes de cours de CMU, 1999



    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
    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)