MSPA-MCS: Markov Random Fields: Structure and Algorithms

MSPA-MCS：马尔可夫随机场：结构和算法

• 批准号: 0528488
• 负责人: Elchanan Mossel
• 金额: $ 50万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-09-01 至 2009-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0528488&HistoricalAwards=false
• 关键词: MSPA; MCS; Markov; Random; Fields

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.

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