MSPA-MCS: Probabilistic Graphical Models: Theory and Algorithms

Yale University, New Haven CT

Investigators

Abstract

PROPOSAL NO: 0528412 INSTITUTION: Yale University PRINCIPAL INVESTIGATOR: Sekhar Tatikonda TITLE: MSPA-MCS: Probabilistic Graphical Models: Theory and Algorithms ABSTRACT: 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.