PhD Studentship - Spectral methods for learning tree-structured graphical models.

Spectral methods for learning tree-structured graphical models.

Supervision : François Denis and Liva Ralaivola, Université d’Aix-Marseille

Deadline : 08/20/2011

A PhD studentship is available as part of the french ANR funded project LAMPADA on "Learning Algorithms, Models an sPArse representations for structured DAta" being jointly undertaken by Inria Lille Nord Europe (Marc Tommasi), the Laboratoire d’Informatique Fondamentale de Marseille (François Denis), the Laboratoire Hubert Curien de Saint-Etienne (Marc Sebban) and the Laboratoire d’Informatique de Paris 6 (Patrick Gallinari). See http://lampada.gforge.inria.fr/wiki....

The student will be based in the Laboratoire d’Informatique Fondamentale de Marseille (France) and join the QARMA team headed by Liva Ralaivola. He/she will be supervised by Pr François Denis (http://www.lif.univ-mrs.fr/ fdenis) and Liva Ralaivola (http://www.lif.univ-mrs.fr/ liva). The project will include collaboration with the project MOSTRARE (Lille INRIA Nord Europe).

The studentship is funded by an ANR project and will start from 1st October 2011 or as soon as possible thereafter. The studentship is funded for 3 years (currently 1400 euros per month - net income).

Requirements : The PhD candidate should have or expect to obtain a MSc or equivalent in computer science or mathematics. The following qualities are desirable : strong interests in machine learning or statistics ; excellent record of academic and/or professional achievement ; strong mathematical skills ; strong programming skills ; good written and spoken communication skills in French or English.

Project Description :

Graphical models are probabilistic models where dependencies between observable and latent random variables are represented by a graph. HMM are simple kinds of graphical models. Tree-structured graphical models extend the expressivity of HMM and are widely used in bio-informatics and Natural Language Processing. The question of the inference of parameters of a tree-structured graphical model is not completely solved, even when the tree topology of the underlying model is unique and supposed to be known. The inference of the topology of the model from samples is still an open question.

Recent learning methods rely on algebraic and geometrical properties of these models and reduce the inference of parameters topology of the models to spectral computations on matrices. Indeed, tree-structured graphical models can be seen as particular rational tree series which can be described by means of natural algebraic operators.

At first, the student will study the link between two formalisms, tree-structured graphical models and tree rational stochastic languages, and compare the algorithms described in the references below. Then, she/he will study the question of the identifiability of tree-structured graphical models from samples and explore the possibility of developing a semi-supervised-like learning algorithm, when some topology-samples pairs are available. Two extensions could be considered : kernelization and extension to more general graphical models, for example based on regular graphs.

References :

 A Spectral Algorithm for Learning Hidden Markov Models, Daniel Hsu, Sham M. Kakade, Tong Zhang, COLT 2009
 A Spectral Algorithm for Latent Tree Graphical Models, Parikh, Le Song, Xing, ICML 2011
 Grammatical inference as a principal component analysis problem, R. Bailly, F. Denis, and L. Ralaivola, ICML 2009
 A Spectral Approach for Probabilistic Grammatical Inference on Trees, R. Bailly, A. Habrard, F. Denis, ALT 2010
 A Hilbert Space Embedding for Distributions, Smola, Gretton, Le Song, Schölkopf, ALT 2007 - Nonparametric Tree Graphical Models via Kernel Embeddings, Le Song, Gretton, Guestrin, AISTAT 2010
 Learning Latent Tree Graphical Models de Choi, Tan, Anandkumar et Willsky, JMLR 2011

=== Contact and application ===

For further information, please contact Prof. François Denis (francois.denis@lif.univ-mrs.fr), or Prof. Liva Ralaivola (liva.ralaivola@lif.univ-mrs.fr).

If you are interested and believe that you qualify, please send your application to Prof. François Denis and Prof. Liva Ralaivola, before August 20, 2011. Include :
 Curriculum Vitae with the names and contact details of at least 2 references
 A list of exams and grades obtained
 A cover letter explaining how your skills and research interests fit the project