CINQA Seminar Series Spring 2010

Aram Galstyan , Ph.D. - May 5, 2010

USC Information Sciences Institute
USC Viterbi School of Engineering

Statistical Mechanics of Inference and Learning

Many problems in machine learning can be framed as reconstructing a process or a structure based on some noisy observations. For instance, in object tracking one is interested in inferring an object's trajectory based on noisy observations of its spatial location. In social network analysis, one is interested in inferring the latent social structure based on the pattern of interactions between individuals. An important theoretical issue underlying those problems is whether there are fundamental limits on one's ability to infer such processes/structures at all. While one expects the quality of inference to degrade with increasing noise, it is not trivial whether the deterioration will be gradual or undergo drastic changes, thus indicating inference instabilities.  In this talk I will present a statistical mechanics based framework for analyzing such problems. In the first part of the talk I will provide a brief introduction to basic concepts in statistical mechanics, followed by a demonstration of the approach on two concrete examples - maximum a posteriori estimation of hidden Markov processes, and detection of latent community structures in networks. It will be shown that in both cases there are inference instabilities that are related to the critical phase transitions in the corresponding statistical mechanical systems.

Follow this link to visit Dr. Galstyan's homepage.

Giuseppe Caire, Ph.D. - May 26, 2010

USC Department of Electrical Engineering - Systems
USC Viterbi School of Engineering

The sum-product algorithm in channel decoding, estimation and Bayesian inference

In 1993, two French researchers in electrical engineering, Berrou and Glavieux, presented a new family of channel codes nicknamed "Turbo Codes'' and a new iterative decoding algorithm, with performance very close to the Shannon capacity limit. This remarkable result is recognized as the beginning of "modern coding theory,'' the pillars of which are: 1) randomlike codes based on sparse graphs; 2) a low-complexity iterative decoding algorithm particularly suited to these sparse graph structures.

Berrou and Glavieux decoder was later recognized to be in fact a special case of a very general algorithm called sum-product, that computes exactly or approximately the marginalization of a multi-variate function by exploiting its factorization in simpler terms and the corresponding Factor Graph structure. When the multivariate function is a joint posterior probability distribution, the sum-product algorithm is known as "Belief Propagation'' algorithm, and was widely studied as a poweful heuristic tool to solve inference problems in Bayesian networks.

This talks provides a tutorial presentation of the sum-product algorithm, its application to channel decoding and some techniques for the analysis of its performance and convergence properties. Some recent applications to problems in biology and computer science will be also presented.

Follow this link to visit Dr. Caire's homepage.

Seminars are from 3:15-4:15 p.m. in Physical Sciences room 306

Download the Spring 2010 Seminar Series flyer!