Estimating Learning Curves of Concept Learning.

Abstract

In this paper, we describe an approximation method which enables us to study the average generalization performance of learning directly via hypothesis testing inequalities. This unites the learning and the hypothesis testing in a common viewpoint. In particular, we investigate learning curves of a so-called ill-disposed learning algorithm, which can provide useful implications regarding the problem of overfitting from a practical and yet scientific viewpoint. The learning problem is stated in the probably approximately correct (PAC) learning model, but only the average generalization performance is addressed. The resulting bounds are directly related to the number of system weights. The advantages of the theory are that it alleviates the practical pessimism frequently claimed for the results of the VC theory, and provides general insights. We illustrate the results with some numerical simulations. Copyright 1997 Elsevier Science Ltd.