Basser Seminar Series

Recent developments on the physical limits of inference

David H. Wolpert
Senior Computer Scientist, NASA Ames Research Center

Monday 03 December 2007, 4-5 pm, Note different day

School of IT Building, Lecture Theatre, Room 123, Level 1

Abstract

In this talk I first review the fact that all physical devices that perform observation, prediction, or recollection share an underlying mathematical structure. Devices with that structure are called “inference devices”.

I then present new existence and impossibility results concerning inference devices. These results have close connections with the mathematics of Turing Machines (TM's), e.g., some of the impossibility results for inference devices are related to the Halting theorem for TM's. Furthermore, one can define an analog of Universal TM's (UTM's) for inference devices, called “strong inference devices”. Strong inference devices can be used to define the “inference complexity” of an inference task, which is the analog of the Kolmogorov complexity of computing a string. Whereas the Kolmogorov complexity of a string is arbitrary up to specification of the UTM, there is no such arbitrariness in the inference complexity of an inference task. I present some new results bounding inference complexity.

Next I present some new graph-theoretic properties that govern any set of multiple inference devices. After this I present an extension of the framework to address physical devices that are used for control. I end with an extension of the framework to address probabilistic inference.

Speaker's biography

David Wolpert is a senior computer scientist at NASA's Ames Research Center where he formed up the collective intelligence group and a consulting professor in Stanford's Aeronautics and Aerospace Dept. His two current primary areas of research are game theory (both experimental and theoretical) and distributed control. He also does work in optimization, complexity, and the physics of computation. Previously he has concentrated on machine learning and Bayesian analysis.

Before coming to NASA he was a Research Manager at IBM Almaden Research Center. He had come to IBM from TXN Inc., a data-mining firm where he was Director of Research. Before that he was a postdoc at the Santa Fe Institute and the Center for Nonlinear Studies at Los Alamos. His degrees are in physics, from the University of California Santa Barbara and Princeton University.

He is the author of two books, three patents, close to one hundred refereed papers, and numerous awards.