Computing That Serves

Probability Collectives and Supervised Learning


Thursday, March 8, 2007 - 11:00am


David Wolpert, Intelligent Systems Division, Ames Research Center, NASA

There are two major fields that analyze distributed systems: statistical physics and game theory.  These fields can be re-expressed in a way that makes them mathematically identical. Doing so allows us to combine techniques from them, producing a hybrid formalism. That hybrid is called Probability Collectives (PC).
As borne out by numerous experiments, PC is particularly well-suited to black-box optimization and associated problems in distributed control.  The core idea is that rather than directly optimize a variable of interest x, often it is preferable to optimize an associated probability distribution, P(x). That optimization can be done either via Monte Carlo Optimization (MCO) or, under certain circumstances, in closed form.
Recently is was realized that one can map MCO into a supervised machine learning problem. This means that all the powerful techniques of supervised learning can be used to improve MCO. As a special case, those techniques can be used to improve the optimization of P(x) in a PC-based optimizer. In this way the techniques of supervised learning can be leveraged to improve black-box optimization and distributed control.
In this talk I review PC. I also illustrate the identity between MCO and supervised learning using PC. In particular, I present results showing how cross-validation can be used to adaptively set an annealing schedule for the optimization of P(x), and to adaptively modify the complexity of P(x). I also illustrate the benefit of bagging in PC.


David Wolpert received degrees in physics from the University of California, Santa Barbara, and from Princeton University.  He is currently a Senior Computer Scientist at NASA and a consulting professor at Stanford.  He was formerly head of a data mining group at IBM Almaden Research and a Postdoc at the Santa Fe Institute. His work primarily concerns how to design collectives of complex adaptive agents to achieve a global goal (i.e., distributed control and/or optimization). Other work investigates the bounds on computation that hold in broad classes of physical universes, and the use of self-dissimilarity as a complexity measure. He also works on extending game theory to sub-rational games using techniques from statistical physics.