New approaches to Gibbs measures at the interface of probability and computational complexity

The concept of a "Gibbs distribution" - developed during the rise of statistical mechanics in the 19th century by Clausius, Maxwell, Boltzmann, Hamilton, and Gibbs - defines a probability distribution over configurations of particles based on an energy function governed by local interactions. Not only have Gibbs distributions proved invaluable in describing the behaviour of physical systems, but the simple framework of Gibbs distributions has become ubiquitous in fields far from statistical physics under the name "probabilistic graphical models": these fields include Bayesian statistics, optimisation, machine learning, mathematical biology, artificial intelligence, and many others.

Gibbs distributions are remarkably effective because they respect the underlying structure of a complex system: probabilistic dependencies are specified by a simple network structure, corresponding to the network indicating which components of the system interact.

Although the specification of a Gibbs distribution is very simple, the resulting probability distribution on configurations can be staggeringly complex. Typically the number of possible configurations grows as an exponential function of the system size, and so it is computationally hopeless to enumerate and calculate exact statistics of the system. Nevertheless, it is sometimes possible to understand all of the relevant global information about the system - the macroscopic `observables' - with simple and efficient algorithms, and this is why probabilistic graphical models arise so often in practical applications.

This research proposal aims to develop new rigorous analytic and computational methods for understanding Gibbs distributions, and in particular, the physical heuristics that underly two associated algorithms, Markov Chain Monte Carlo and Belief Propagation.

The proposal involves three interrelated goals.

The first is to make rigorous an detailed family of predictions from statistical physics about Gibbs distributions on random, or "mean-field", networks. Such random networks are used as both an approximation of physical systems and as a model of real-life networks, but have the advantage of being more amenable to analysis.

The second goal is to prove mathematically that the original mathematical model of a fluid, the "hard sphere model", exhibits a freezing transition from liquid to solid. The model, which is purely geometric, without any forces between molecules except for excluded volume, dates back to at least Boltzmann's time but has proved extremely resistant to rigorous analysis.

The third and final goal is to study the extremes of Gibbs distributions: which networks maximise or minimise certain statistics? Besides delineating the boundaries of what is possible in a given Gibbs distribution, these questions also have connections to long-standing open problems in combinatorics.

The proposed research promises significant long-term practical impact, based on advancing the understanding of two widely used algorithms: Belief Propagation and Markov Chain Monte Carlo. These are simple, very general algorithms which are used in many practical applications from engineering, to Bayesian statistics, to economics, to data mining. The various uses of these algorithms often fall under the name of "Machine Learning": automated procedures for computers to `learn' or infer underlying truths from large amounts of noisy data.

The algorithms are used to perform inference on and to sample from probabilistic graphical models: models in which dependencies between random variables follow the structure of a network. These models originated in theoretical physics long before computers were even invented, but have proved hugely important due to their simple formulation and the availability of simple algorithms (whose origins again lie in statistical physics) to perform inference.

What is needed is a greater understanding of the conditions under which these algorithms will perform as intended. In general, these algorithms are simply heuristics - used without any guarantees on their performance. By developing a deeper understanding of the fundamentals of the models from statistical physics, the research from this proposal can help classify the conditions under which efficient algorithmic inference is feasible or not.

The focus of Aim 1 of the proposal is on models generated at random (mean field models) which are important in the study of algorithms as a source of hard computational problems. By gaining a precise understanding of the relationship between various phase transitions in the models and the performance of message passing algorithms we can begin to understand the structures that impede algorithmic performance.

The focus of Aim 2 is on models with the geometric structure of Euclidean space - the geometry that arises in physical systems.

Finally, the focus of Aim 3 is on extremal structures: given a set of constraints, which graphical structures maximise or minimise certain important parameters. The practical use of such results is in providing a priori bounds on parameters in the course of algorithmic design and analysis.


To ensure that research from this proposal does in fact reach practitioners and impact real-world algorithms, I will submit papers to and present work at leading Machine Learning conferences (such as NIPS and COLT) at which both academics and practitioners interact, as well as conferences and journals in both mathematics and computer science.

One final important aspect of delivering impact from this proposal is the communication of ideas and results between these different scientific communities, each of whom have their own terminology and perspective on the same general models and problems. By actively pursuing interdisciplinary collaboration and continuing to speak in conferences and seminars in different fields, I will contribute to the exchange of ideas between computer science, machine learning, statistical physics, probability and combinatorics.