MSPA-MCS: Markov Random Fields: Structure and Algorithms

马尔可夫随机场（mrf）为在大量随机变量集合中捕获条件独立性提供了一个非常通用的框架。本文研究了mrf的空间特性，并给出了两种广泛应用于mrf推理问题的算法范式：信念传播（BP）和吉布斯抽样（GS）。尽管这些算法（尤其是BP）被广泛使用，但在大多数情况下缺乏严格的性能保证。提出的研究的一个主要目标是更深入地了解bp和GS对应用中出现的不同类别的mrf的行为。中心论点是这些算法的性能与底层MRF的空间结构密切相关。通过使这种联系精确，该项目旨在提高对算法及其相互关系的理解。基于这一见解，该项目的第二个主要目标是研究针对特定应用设计mrf的系统方法；mrf应该具有合适的空间属性，这样像BP或GS（或其变体）这样的算法在实践中既成功又有效。马尔可夫随机场是一类丰富的数学模型，非常适合于捕捉由独立组件组成的大型系统的行为，这些系统的相互作用最好地描述为统计术语（而不是确定性定律）。这样的系统在当今世界无处不在。作为第一个例子，考虑到互联网上数百万台计算机：您的计算机和给定网站之间的通信时间不是固定的数量，而是根据其他用户的数量，一天中的时间等而变化。第二个例子是模拟和预测全球气候的问题，这取决于大量的因素，这些因素以统计上可变的方式相互作用。用马尔可夫随机场对这样的应用程序建模会导致许多计算问题，由于它们的尺寸非常大，基本上不可能精确地解决。本研究项目的主要目标是开发和分析获得近似解的有效算法方法，并严格保证准确性和运行时间。鉴于使用马尔可夫随机场的广泛科学和工程背景，对这些算法的基础研究在许多领域具有非常广泛的影响，包括现代计算和通信基础设施，医疗诊断的智能系统以及复杂物理和生物系统的建模。

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.