MSPA-MCS: Markov Random Fields: Structure and Algorithms

点击翻译按钮获取中文摘要

Markov random fields (MRFs) provide a very general framework forcapturing conditional independence in large collections of randomvariables. The proposal is concerned with the spatial properties ofMRFs, and with two widely used algorithmic paradigms for solvinginference problems in them: Belief Propagation (BP) and Gibbs Sampling(GS). Though widely used, these algorithms (especially BP) lackrigorous performance guarantees in most situations. One major goal ofthe proposed research is a deeper understanding of the behavior of BPand GS for different classes of MRFs that arise in applications. Acentral thesis is that the performance of these algorithms isintimately tied to the spatial structure of the underlying MRF. Bymaking this connection precise the project aims at an improvedunderstanding of the algorithms and their relationship to one another.Based on this insight, a second major goal of the project is toinvestigate systematic methods for designing MRFs tailored to aspecific application; the MRFs should have suitable spatial propertiesso that algorithms like BP or GS (or variants thereof) are bothsuccessful in practice and provably effective.Markov random fields are a rich class of mathematical models that areextremely well suited to capturing the behavior of large systems ofindependent components whose interactions are best described instatistical terms (rather than in terms of deterministic laws). Suchsystems are ubiquitous in today's world. As a first example, considerthe millions of computers on the internet: the communication timebetween your computer and a given website is not a fixed quantity, butvaries depending on the number of other users, the time of day etc. Asecond example is the problem of modeling and predicting globalclimate, which depends on a very large number of factors that interactin statistically variable ways. Modeling such applications withMarkov random fields leads to a number of computational problemsthat---due to their extremely large size---are essentially impossibleto solve exactly. The primary goal of this research project is thedevelopment and analysis of efficient algorithmic methods forobtaining approximate solutions, with rigorous guarantees on accuracyand running time. In light of the broad range of scientific andengineering contexts in which Markov random fields are used, basicresearch on these algorithms has the potential for very broad impactin many domains, including modern-day computing and communicationsinfrastructure, intelligent systems for medical diagnosis, and themodeling of complex physical and biological systems.