Bounds on the sample complexity of Bayesian learning using information theory and the VC dimension
Michael J. Kearns · 2003
Summary form only given. A Bayesian or average-case model of concept learning is given. The model provides more precise characterizations of the learning curve (sample complexity) behaviour that depends on properties of both the prior distribution over concepts and the sequence of instances seen by the learner. It unites in a common framework statistical physics and VC dimension theories of learning curves. A systematic investigation and comparison of two fundamental quantities in learning and information theory is undertaken. These are the probability of an incorrect prediction for an optimal learning algorithm, and the Shannon information gain. This paper provides an understanding of the sample complexity of learning in several existing models.>