Estimating Learning Curves of Concept Learning
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.  1997 Elsevier Science Ltd.
learning curves concept learning generalization error sample complexity pac learning interpolation dimension