Tractable Methods for Inference on Graphical Models

Alan S. Willsky
MIT

Monday, November 17, 2008 at 1:00PM

54-134 Engineering IV Building
Refreshments Served

Abstract: Graphical models represent a rich framework for probabilistic modeling of interactions and relationships among large number of variables. Optimal inference for such models - e.g., estimating some variables given (noisy) observations of some or all of the variables - however, can be quiet complex for models on graphs with loops. Developing tractable algorithms and saying something definitive about their performance is a very active of research, and in this talk we describe some of our work in this area. In particular, we describe our work on analyzing a well-known approximate algorithm, known as "Loopy Belief Propagation," (LBP) for Gaussian graphical models using what we refer to as walk-sum analysis, which captures the accumulation of statistics as messages in LBP as they propagate information throughout the graph. We also use walk-sum analysis to provide easily checked conditions for optimality of another class of algorithms based on propagating messages throughout embedded trees and subgraphs, and we use this formalism to develop adaptive methods for determining the most informative messages to send at any point in the algorithm's iterative process. This has implications for real distributed implementations in which sending messages consumes communication resources. We also briefly describe our work on learning or "thinning" graphical models using concepts of maximum entropy. This is a key problem not only in learning of models but also in a variety of inference algorithms including one that we have developed known as Recursive Cavity Modeling that involves propagating information outward from one or more "seed" nodes and fusing information around the boundary of the "cavity" formed by this outward propagation. Finally, we describe our contributions to a growing area of research, namely that involving breaking a complex graphical modeling problem into a set of smaller, tractable ones which overlap, relaxing the constraints of equality on the overlaps using Lagrangian methods, and then solving the dual optimization problem. We present results of applying such methods to so-called non-planar Ising models, including some adaptive methods for successfully adapting our decomposition to reduce and often remove the duality gap. We close with a few remarks on current and prospective research directions.

Biography: Alan S. Willsky received both the S.B. degree and the Ph.D. degree from the Massachusetts Institute of Technology in 1969 and 1973 respectively. He joined the M.I.T. faculty in 1973 and his present position is as the Edwin S. Webster Professor of Electrical Engineering and Co-Director of the Laboratory for Information and Decision Systems. Dr. Willsky was a founder, member of the Board of Directors, and Chief Scientific Consultant of Alphatech, Inc. (now BAE Systems Advanced Information Technologies) and continues as Chief Scientific Consultant at BAE Systems AIT. Dr. Willsky also held a 4-year position as a member of the US Air Force Scientific Advisory Board and received the US Air Force Award for Meritorious Service. Dr. Willsky has held visiting positions at Imperial College, London, L'Université de Paris-Sud, and the Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA) in Rennes, France. Dr. Willsky has given a number of plenary and keynote lectures at major scientific meetings. He is the author of the research monograph Digital Signal Processing and Control and Estimation Theory and is co-author of the undergraduate text Signals and Systems. He has published more than 190 journal publications and 350 conference papers. In 1975 he received the Donald P. Eckman Award from the American Automatic Control Council. He was awarded the 1979 Alfred Noble Prize by the ASCE and the 1980 Browder J. Thompson Memorial Prize Award by the IEEE for a paper excerpted from his monograph, and he recently received the 2004 Donald G. Fink Award from the IEEE. Dr. Willsky and his students, colleagues and postdoctoral associates have received a variety of Best Paper Awards at various conferences, most recently including the 2001 IEEE Conference on Computer Vision and Pattern Recognition, the 2002 Symposium on Uncertainty in Artificial Intelligence, the 2003 Spring Meeting of the American Geophysical Union, the 2004 International Conference on Information Processing in Sensor Networks, the 2004 Neural Information Processing Symposium, Fusion 2005, and the 2008 award from the journal Signal Processing for the outstanding paper in the year 2007. In addition, in October 2005, Dr. Willsky was presented with a Doctorat Honoris Causa from Université de Rennes in 2005 in connection with the 30th anniversary of the establishment of IRISA.