## Effective Classification Learning

- Dale Schuurmans, AICML

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 fixedsamplesize approach to data collection that fails to achieve practical dataefficiency in most applications. In this thesis we consider an alternative ``sequential'' approach where the learner observes training examples oneatatime and decides online when to stop training. We prove that sequential learning strategies can paclearn with fewer training examples than previous fixedsamplesize 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 nonuniform in training sample size, and prove that a uniform analysis predicts the 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.

### Citation

D. Schuurmans. "Effective Classification Learning". Value of Information in Inference, Learning and Decision-Making, January 1996.Keywords: | Effective, learning, machine learning |

Category: |

### BibTeX

@incollection{Schuurmans:VOI-NIPS96, author = {Dale Schuurmans}, title = {Effective Classification Learning}, booktitle = {Value of Information in Inference, Learning and Decision-Making}, year = 1996, }

Last Updated: April 24, 2007

Submitted by William Thorne