Markov random fields (MRFs) provide a very general framework for capturing conditional independence in large collections of random variables. The proposal is concerned with the spatial properties of MRFs, and with two widely used algorithmic paradigms for solving inference problems in them: Belief Propagation (BP) and Gibbs Sampling (GS). Though widely used, these algorithms (especially BP) lack rigorous performance guarantees in most situations. One major goal of the proposed research is a deeper understanding of the behavior of BP and GS for different classes of MRFs that arise in applications. A central thesis is that the performance of these algorithms is intimately tied to the spatial structure of the underlying MRF. By making this connection precise the project aims at an improved understanding of the algorithms and their relationship to one another. Based on this insight, a second major goal of the project is to investigate systematic methods for designing MRFs tailored to a specific application; the MRFs should have suitable spatial properties so that algorithms like BP or GS (or variants thereof) are both successful in practice and provably effective.
Markov random fields are a rich class of mathematical models that are extremely well suited to capturing the behavior of large systems of independent components whose interactions are best described in statistical terms (rather than in terms of deterministic laws). Such systems are ubiquitous in today's world. As a first example, consider the millions of computers on the internet: the communication time between your computer and a given website is not a fixed quantity, but varies depending on the number of other users, the time of day etc. A second example is the problem of modeling and predicting global climate, which depends on a very large number of factors that interact in statistically variable ways. Modeling such applications with Markov random fields leads to a number of computational problems that---due to their extremely large size---are essentially impossible to solve exactly. The primary goal of this research project is the development and analysis of efficient algorithmic methods for obtaining approximate solutions, with rigorous guarantees on accuracy and running time. In light of the broad range of scientific and engineering contexts in which Markov random fields are used, basic research on these algorithms has the potential for very broad impact in many domains, including modern-day computing and communications infrastructure, intelligent systems for medical diagnosis, and the modeling of complex physical and biological systems.
