[CPCC] TALK: Reducing the Complexity of Graphical Models (1/5/07 11 AM)

Ender Ayanoglu ayanoglu at uci.edu
Wed Jan 31 13:00:24 PST 2007


				  TALK

           Reducing the Complexity of Graphical Models via Cycles

				   by
			    Thomas R. Halford
		     Communication Sciences Institute
                     University of Southern California

			    February 5, 2007
				  11 AM
			 Engineering Tower 301


				Abstract

A decade ago, the introduction of turbo codes and iterative message
passing algorithms revolutionized the theory and practice of coding. In
the ensuing years, the coding theory community has become adept at
designing codes from good graphical models - that is, models which imply
low-complexity, near-optimal iterative message passing algorithms.
Specifically, modern codes are constructed by connecting a large number of
simple local codes together via a rich, random-like, cyclic
interconnection network. A key observation from this work is that the
introduction of cycles to graphical models can enable massive complexity
reductions in model, and thus decoding, complexity.

Whereas constructive graphical modeling problems (e.g., code design) have
been widely addressed by the coding theory community, less is understood
about the inverse problem of model extraction. Specifically, can good
cyclic graphical models be obtained for existing algebraic codes, or more
generally, for arbitrary systems?  What tradeoffs exist between model
complexity and cyclic topology for a given code?  If good models can
exist, how can they be obtained, or extracted?  This talk presents a
theoretical framework for the study of extractive graphical modeling
problems. We first examine the limits of extraction by providing a
characterization of the tradeoff between cyclic topology and complexity in
graphical models for linear codes.  Inasmuch as the cyclic topology of a
graphical model is related to the performance of the decoding algorithms
it implies, the bound presented in this talk provides insight into the
limits of graphical model extraction.  We then provide a formalization of
extraction as optimization and describe some novel heuristics for both
defining and solving this optimization problem.  We conclude with a
discussion of the importance of cyclic model extraction outside of coding.


			    Speaker's Biography

Thomas R. Halford received the B. A. Sc. degree in engineering physics
from Simon Fraser University, Burnaby, B.C., Canada, in 2001.  He is
currently a doctoral candidate at the University of Southern California,
Los Angeles, where his research focuses primarily on graphical models of
codes.  He spent the summer of 2005 visiting the Natural Language
Processing Group at IBM T. J. Watson Research Center, Yorktown Heights,
NY.


More information about the CPCC mailing list