Effective classification learning
Hector J. Levesque, Dale Schuurmans · 1996
This thesis addresses the problem of learning a classification rule from random examples. We first consider the problem of learning a target concept with guaranteed accuracy and reliability given that the target belongs to some known class C; a task commonly referred to as probably approximately correct (pac) learning. Previous work on this problem assumes a fixed-sample-size approach to data collection that fails to achieve practical data-efficiency in most applications. In this thesis we consider an alternative approach where the learner observes training examples one-at-a-time and decides on-line when to stop training. We prove that sequential learning strategies can pac-learn with fewer training examples than previous fixed-sample-size approaches, even while incurring minimal computational overhead. Moreover, these new strategies use many times fewer training examples in practical case studies. Next, we study the average error of a learner's hypotheses as a function of training sample size--its so called learning curve. Specifically, we investigate the best learning curve that can be achieved in the worst case over a class of concepts C. Previous work has shown that rational convergence to zero error can always be obtained in this model, but it is impossible to do better in the worst case. However, recent empirical studies have shown that exponential convergence can be achieved in many experimental settings. We explain this discrepancy by noting that the previous analysis is non-uniform in training sample size, and prove that a uniform analysis predicts that exact same dichotomy as observed in the experimental studies. Overall, this thesis shows how the worst case theory of classification learning can be brought closer to practice.