UC Irvine

Probabilistic graphical models provide a powerful framework for representing and reasoning about complex systems composed of many small overlapping subsystems. Key problems in graphical models can be formulated as probabilistic inference queries, such as computing the most likely configuration or the marginal probability of a random variable. Since these problems are intractable in general, a large class of approximate inference algorithms that exploit the factorization structure of graphical models have been developed.

In addition to the classic factorization structure, many graphical models also possess symmetric structure where groups of objects in the model are indistinguishable. Two types of symmetry arise regularly in practice: first, a model with state space symmetry contains factors with groups of states that have identical values; second, a model with factor symmetry contains groups of factors that have identical factor tables.

Although efficient inference algorithms for models with perfect symmetry have been well developed, most real problems do not contain perfect symmetry. Often, for example, a model with a symmetric substructure is perturbed by asymmetric evidence factors. Consequently, there is a great need for methods that accurately approximate the desired inference quantities using symmetric inference terms. While a few methods to address this problem exist, many are heuristic or address only certain aspects of the problem.

The goal of this thesis is to develop more intelligent ways to perform inference in graphical models with approximate symmetry. Our central strategy is to force groups of parameters in a variational inference relaxation to be symmetric. These symmetry groups are iteratively broken in a controlled manner to capture problem asymmetries more accurately; this procedure gives rise to a flexible class of coarse-to-fine inference algorithms. Furthermore, by using intelligently structured parameter symmetries, we are able to construct symmetric high-order inference terms which are often necessary to obtain high accuracy inference estimates. We develop algorithms both for models with state space symmetry and for models with factor symmetry, highlighting the deep similarities between these two classes of problems which has not been widely appreciated before.