Tutorial on Probabilistic Graphical Models: A Geometric and Topological View

Chao Chen, City University of New York (CUNY), United States

Qinfeng (Javen) Shi, University of Adelaide, Australia

Probabilistic Graphical Models (PGMs) use graphs to compactly represent high dimensional multimodal joint distributions over random variables. Factorizing the joint distribution via the graph (or equivalently via conditional independence) facilitates efficient queries. This makes PGMs very effective at modelling complex relationships between variables. These might be the relationships between symptoms and diseases, or the relationships between a set of sensor inputs and the state of the system being modelled, or the relationships between cellular metabolic reactions and the genes that encode them, or the relationships between users in a social network about whom we wish to draw inferences. The power of PGMs has seen them applied to all of these problems and many more, to the point where they are considered the workhorse for Machine Learning in structured output spaces.

In spite of the rich literature, many geometric and topological problems have arisen from the context of graphical models. These problems have proven difficulty and call for novel solutions. Examples include but are not limited to: encoding geometric and topological constraints in the inference output, capturing modes (local optima) of the high dimensional distribution described by a graphical model, etc. We believe introducing graphical models and these geometric and topological problems to the computational geometry community will lead to exciting new research directions.


  • Part 1: Representation and Basic (slides)

    Graphical models are used to model high dimensional joint distibution using graphs. Nodes of the graph correspond to different random variables, each of which can be assigned different discrete/continuous values. Edges of the graph encodes the conditional (in)dependence between variables.

  • Part 2: Inference (slides, updated)

    Inference algorithms are designed to compute the most possible value, the marginals, etc, of a given graphical model. Computational challenges are closely related to the simplicity of the graph.

  • Part 3: Advanced Inference (slides)

    Advanced inference problems have been posed. They are closely related to geometry and topology. For example, how to find the optimal solution with connectivity constraints? How to find the top M local maxima of the probability landscape?

  • Part 4: Learning Parameters and Structures (slides)

    With given training data, we need to estimate the underlying graph, and the associated parameters. So that when facing a new test data, we have a model that gives the best prediction (interpretation).

 Last modified: July 11th 2017