Prof Tong Zhang – Rutgers University, USA
Spectral Methods for Learning Graphical Models
This talk presents a methodology for learning graphical models with hidden nodes that I have been studying with collaborators in recent years. The idea is to employ algebraic techniques (in particular, matrix decomposition and spectral methods) to learn unobserved quantities in graphical models. The talk focuses on tree models, and covers two aspects of the underlying learning problem: parameter estimation and structural learning. The first part is concerned with parameter estimation, where an algorithm called learnHMM is presented that learns hidden Markov models. It is shown that this method can efficiently recover the correct HMM dynamics with a sample complexity depending on some mild conditions of the underlying system. The advantage of this approach over some traditional methods (such as EM) is that our algorithm does not suffer from local minimum issues in nonconvex optimization, and it handles high dimensional observations and long range dependencies more easily. The method can be extended to estimating parameters for nonlinear systems and general tree structured graphical models with unobserved nodes. The second part is concerned with structural learning, where an algorithm is presented to learn the underlying tree topology of a broad class of multivariate tree models with hidden nodes. Exact recovery of the tree structure can be established based on certain natural dependencies on statistical and structural properties of the underlying joint distribution. This method handles high dimensional observations and is more general than existing approaches. Collaborators: Daniel Hsu, Sham Kakade, Anima Anandkumar, Le Song.
School of Computing, Robert Gordon University, St Andrew Street, Aberdeen, Lecture Room A12, 14:00 – 15:00.