TCS-TR-A-06-23

Date: Thu Nov 30 19:22:54 2006

Title: Consistency Theorems for Discrete Bayesian Learning

Authors: Jan Poland

Contact:

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

Abstract. Bayes' rule specifies how to obtain a posterior from a class of hypotheses endowed with a prior and the observed data. There are three fundamental ways to use this posterior for predicting the future: marginalization (integration over the hypotheses w.r.t. the posterior), MAP (taking the a posteriori most probable hypothesis), and stochastic model selection (selecting a hypothesis at random according to the posterior distribution). If the hypothesis class is countable and contains the data generating distribution (this is termed the "realizable case"), strong consistency theorems are known for the former two methods, asserting almost sure convergence of the predictions to the truth as well as loss bounds. We prove corresponding results for stochastic model selection, for both discrete and continuous observation spaces. As a main technical tool, we will use the concept of a potential: this quantity, which is always positive, measures the total possible amount of future prediction errors. Precisely, in each time step, the expected potential decrease upper bounds the expected error. We introduce the entropy potential of a hypothesis class as its worst-case entropy with regard to the true distribution. Our results are proven within a general stochastic online prediction framework that comprises both online classification and prediction of non-i.i.d. sequences.