MSPA-MCS: Probabilistic Graphical Models: Theory and Algorithms

MSPA-MCS：概率图形模型：理论和算法

• 批准号: 0528412
• 负责人: Sekhar Tatikonda
• 金额: --
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-09-15 至 2009-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0528412&HistoricalAwards=false
• 关键词: MSPA; MCS; Probabilistic; Graphical; Models

PROPOSAL NO: 0528412 INSTITUTION: Yale UniversityPRINCIPAL INVESTIGATOR: Sekhar TatikondaTITLE: MSPA-MCS: Probabilistic Graphical Models: Theory and AlgorithmsABSTRACT:This project will study a class of computational algorithms (sum-product, belief-propagation, and cavity method) that appear to work well in practice, but for which there is not yet a good theoretical understanding of why and when they should work. The algorithms have been applied to problems that are known to be at the edge of what is computationally feasible and problems of established practical value, such as the design of good error correction codes, solutions to hard combinatorial optimization problems, and the development of decentralized estimation techniques.All the algorithms can be viewed as forms of message passing: an optimization problem involving many variables is solved by an iterative procedure where the results of calculations involving small subsets of variables become the inputs for subsequent calculations at neighboring sets of variables. Mathematically, the algorithms can be represented by a flow of messages between a large collection of interconnected sites. The mathematical challenge is to understand cases where messages can flow around a big loop, so that a site receives incoming messages derived from messages sent from the same site at earlier stages of the calculation. There is a potential for misleading feedback.The PIs have already demonstrated that some message-passing problems can be transformed mathematically into problems where tools from statistical physics can be applied. In particular, they have shown that the feedback problem is related to the phenomenon of phase transition in physical systems composed of enormous numbers of interacting particles. The project will build on this insight, drawing ideas from statistics, computer science, engineering, and statistical physics.

提案编号：0528412 机构：耶鲁大学 首席研究员：Sekhar Tatikonda 标题：MSPA-MCS：概率图形模型：理论和算法 摘要：该项目将研究一类在实践中表现良好的计算算法（和积、置信传播和空腔方法），但对于其原因和时间尚无良好的理论理解 他们应该工作。 这些算法已应用于已知的计算可行的边缘问题和已确定的实用价值的问题，例如良好的纠错码的设计、硬组合优化问题的解决方案以及分散估计技术的开发。所有算法都可以视为消息传递的形式：涉及许多变量的优化问题通过迭代过程来解决，其中的结果 涉及小变量子集的计算成为相邻变量集后续计算的输入。从数学上讲，这些算法可以用大量互连站点之间的消息流来表示。数学挑战是理解消息可以绕大循环流动的情况，以便站点在计算的早期阶段接收从同一站点发送的消息派生的传入消息。可能会出现误导性反馈。PI 已经证明，一些消息传递问题可以在数学上转化为可以应用统计物理学工具的问题。特别是，他们表明反馈问题与由大量相互作用粒子组成的物理系统中的相变现象有关。该项目将建立在这一见解的基础上，汲取统计学、计算机科学、工程学和统计物理学的想法。