Seminar Details

Seminar Details


Mar 2

3:30 pm

Efficient Unsupervised Learning in High Dimensions with Trees and Mixtures

Marina Meila (Joint with Computer Science)


Carnegie Mellon University - Department of Computer Science

How to learn useful representations from observed data, so that the resulting models can perform a variety of tasks, some of them unspecified at the time of learning? This problem is called unsupervised learning and probabilistic approaches have proved to be particularly successful at it. However, operating with distributions over multidimensional domains raises specific problems - termed curse of dimensionality - that are not encountered in the univariate case. This talk shows how exploiting the computational properties of a simple graphical model, the tree, leads to efficient, elegant and powerful algorithms for learning in multidimensional domains.

The tree is special among graphical models for its outstanding computational properties. I will introduce the mixture of trees, a model that increases the representation power of the tree while preserving its computational advantages. Mixtures of trees can be estimated efficiently by a method based on the Maximum Spanning Tree and the EM algorithms.

The original algorithm is quadratic in the dimension of the domain. I will show that for sparse data it can be transformed in an algorithm that is subquadratic and that in simulations achieves speedups factors of up to a thousand.

No prior knowledge of graphical probability models is necessary to follow this talk.