Spectral methods for learning tree-structured graphical models.
Supervision : François Denis and Liva Ralaivola, Université
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).
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
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
– 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(at)lif.univ-mrs.fr), or Prof. Liva Ralaivola
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
– A list of exams and grades obtained
– A cover letter explaining how your skills and research interests fit the