TCS-TR-A-06-11

Date: Fri Mar 3 15:48:55 2006

Title: Potential Functions for Stochastic Model Selection

Authors: Jan Poland

Contact:

First name: Jan
Last name: Poland
Address: Graduate School of Information Science and Technology, Hokkaido University, N-14, W-9, Sapporo 060-0814, Japan
Email: jan@ist.hokudai.ac.jp

Abstract. We prove performance guarantees for Bayesian learning algorithms, in particular stochastic model selection, with the help of potential functions. Such a potential quantifies the current state of learning in the system, in a way that the expected error in the next step is bounded by the expected decrease of the potential. For Bayesian stochastic model selection, an appropriate potential function will be specified by introducing the entropy potential, a quantity which we define as the worst-case entropy of a model class with regard to the true model. The resulting cumulative error bounds correspond to Solomonoff's theorem and are essentially sharp. They imply consistency, namely almost sure convergence of the predictive probabilities to the true ones, and loss/regret bounds for arbitrary bounded loss function. Although we formulate our results in the classification framework, they are equally applicable to the prediction of non-i.i.d. sequences.