Collaborative Research: Message-Passing Algorithms - from Practice to Theory and back to Practice

协作研究：消息传递算法——从实践到理论再回到实践

• 批准号: 0514801
• 负责人: Nigel Boston
• 金额: $ 20.95万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-15 至 2008-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0514801&HistoricalAwards=false
• 关键词: Collaborative; Research; Message; Passing; Algorithms

The research supported under this grant targets the thorough and effective understanding of message-passing algorithms which constitute a large and very potent class of estimation and detection techniques. Indeed, while message-passing (iterative) processing is very successful in practice, understanding its limitations and its sources of non-optimal behavior has been elusive. Despite the enormous impact that message-passing algorithms have, in particular in a communication scenario, practical systems currently rely almost exclusively on a simulation-based evaluation. In this situation, understanding the behavior and geometry of message-passing will not only reduce the necessity of simulations but provide powerful tools for system optimization.This proposal draws on recent exciting developments that connect message-passing algorithms to the well established theory of convex optimization. As it turns out, message-passing algorithms are intimately related to a linear programming formulation of the inference task at hand. In fact, belief propagation algorithms may be interpreted as an efficient duality-based method to closely approximate the solution to a linear program. Once such connections are established the investigators will strive to understand message-passing algorithms from an entirely new and fruitful point of view. Also, the investigators have already shown that the connection to convex optimization is rooted in the basic property of message-passing algorithms, namely that they operate only locally in a given graphical model. Thus the findings resulting from the approach investigated here will apply to any reasonable locally-operating algorithm.

这项拨款支持的研究旨在全面有效地理解消息传递算法，这些算法构成了一个庞大而非常有效的估计和检测技术类别。事实上，虽然消息传递（迭代）处理在实践中非常成功，但了解其局限性及其非最佳行为的来源一直是难以捉摸的。尽管消息传递算法具有巨大的影响，特别是在通信场景中，但实际系统目前几乎完全依赖于基于模拟的评估。在这种情况下，了解消息传递的行为和几何结构不仅可以减少模拟的必要性，还可以为系统优化提供强大的工具。这个建议借鉴了最近令人兴奋的发展，将消息传递算法与完善的凸优化理论联系起来。事实证明，消息传递算法与手头推理任务的线性规划公式密切相关。事实上，信念传播算法可以被解释为一种有效的基于对偶性的方法来接近线性规划的解。一旦建立了这样的联系，研究人员将努力从一个全新的、富有成效的角度来理解信息传递算法。此外，研究人员已经表明，与凸优化的联系根植于消息传递算法的基本属性，即它们仅在给定的图形模型中局部操作。因此，这里研究的方法所得到的结果将适用于任何合理的局部操作算法。