Topics in Universal Prediction and Adaptive Filtering

In this talk we consider the problems of prediction and adaptive filtering and introduce a class of "universal" algorithms that exhibit a form of competitive optimality. That is, rather than the traditional approach to such signal processing problems, we seek algorithms that, for every individual sequence, can outperform the best algorithm for that sequence chosen from a large class – even when this "best in class" algorithm can be chosen after observing the entire data sequence in advance. Using techniques similar in spirit to Bayesian combinations, we transform the associated sequential prediction or filtering problems into related problems of sequential probability assignment. In this manner, approaches from sequential universal data compression can be applied to provide algorithms that are universal in this new context.

After reviewing some prior results for linear prediction and filtering algorithms that are universal with respect to large, continuous classes of fixed algorithms, we consider two new extensions to even larger classes of models: models that are piecewise-linear in time and models that are piecewise-linear in space. Without knowing the data length, number of transitions or transition times, we will show that we can achieve the performance of the best piecewise-linear model that can choose number of segments, duration of these segments and the best regressor in each segment, a priori based on the entire sequence. We then use "context trees" to achieve the performance of the best piecewise linear model that can choose its partitioning of the real line (or regression space) and prediction parameters based on observing the entire sequence in advance. These new algorithms compete well against an exponential and a doubly-exponential number of models using tree-based techniques based on ideas from universal data compression.

Prof. Andrew C. Singer received the S.B., S.M., and Ph.D. degrees, all in electrical engineering and computer science, from the Massachusetts Institute of Technology in 1990, 1992, and 1996, respectively. Since 1998, he has been on the faculty of the Department of Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign, where he is currently an Associate Professor in the ECE department, a Research Associate Professor in the Coordinated Science Laboratory, and a Willett Faculty Scholar. During the academic year 1996, he was a Postdoctoral Research Affiliate in the Research Laboratory of Electronics at MIT. From 1996 to 1998, he was a Research Scientist at Sanders, A Lockheed Martin Company in Manchester, New Hampshire, where he designed algorithms, architectures and systems for a variety of DOD applications. His research spans statistical signal processing and communication systems, as well as information theory and machine learning. He was a Hughes Aircraft Masters Fellow, and was the recipient of the Harold L. Hazen Memorial Award for excellence in teaching in 1991. In 2000, he received the National Science Foundation CAREER Award, in 2001 he recieved the Xerox Faculty Research Award, and in 2002 was named a Willett Faculty Scholar. Dr. Singer serves as an Associate Editor for the IEEE Transactions on Signal Processing and is a member of the MIT Educational Council, and of Eta Kappa Nu and Tau Beta Pi.

In 2005, Prof. Singer was appointed as the Director of the Technology Entrepreneur Center (TEC) in the College of Engineering and has started several successful initiatives in the Center since. He also co-founded Intersymbol Communications, Inc., a venture-funded fabless semiconductor IC company, based in Champaign Illinois. Intersymbol develops signal processing enhanced chips for ultra-high speed optical communications systems.