MSPA-MCS: Probabilistic Graphical Models: Theory and Algorithms

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

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.