Characterizing Rational Versus Exponential Learning Curves
We consider the standard problem of learning a concept from
random examples. Here a learning curve can be defined to be the expected
error of a learner's hypotheses as a function of training sample size.
Haussler, Littlestone and Warmuth have shown that, in the distribution
free setting, the smallest expected error a learner can achieve in the
worst case over a concept class C converges rationally to zero error (i.e.,
Theta(1=t) for training sample size t). However, recently Cohn and Tesauro
have demonstrated how exponential convergence can often be observed
in experimental settings (i.e., average error decreasing as e Theta(Gammat) ).
By addressing a simple nonuniformity in the original analysis, this paper
shows how the dichotomy between rational and exponential worst case
learning curves can be recovered in the distribution free theory. These
results support the experimental findings of Cohn and Tesauro: for finite
concept classes, any consistent learner achieves exponential convergence,
even in the worst case; but for continuous concept classes, no learner
can exhibit subrational convergence for every target concept and do
main distribution. A precise boundary between rational and exponential
convergence is drawn for simple concept chains. Here we show that some
where dense chains always force rational convergence in the worst case,
but exponential convergence can always be achieved for nowhere dense
chains.
Citation
D. Schuurmans.
"Characterizing Rational Versus Exponential Learning Curves". Journal of Computer System Sciences, 55(1), pp 140-160, March 1997.
| Keywords: |
rational, exponential, machine learning |
| Category: |
In Journal |
BibTeX
@article{Schuurmans:97,
author = {Dale Schuurmans},
title = {Characterizing Rational Versus Exponential Learning Curves},
Volume = "55",
Number = "1",
Pages = {140-160},
journal = {Journal of Computer System Sciences},
year = 1997,
}Last Updated: June 01, 2007
Submitted by Staurt H. Johnson 
