Sequential PAC Learning

Abstract

We consider the use of “on-line” stopping rules to reduce the number of training examples needed to pat-learn. Rather than collect a large training sample that can be proved sufficient to eliminate all bad hypotheses a przorz, the idea is instead to observe training examples one-at-a-time and decide “on-line” whether to stop and return a hypothesis, or continue training. The primary benefit of this approach is that we can detect when a hypothesizer has actually ‘[converged,” and halt training before the standard fixed-sample-size bounds. This paper presents a series of such sequential learning procedures for: distribution-free pat-learning, “mist ake-bounded to pat” conversion, and distribution-specific pat-learning, respectively. We analyze the worst case expected training sample size of these procedures, and show that this is often smaller than existing fixed sample size bounds — while providing the exact same worst case pat-guarantees. We also provide lower bounds that show these reductions can at best involve constant (and possibly log) factors. However, empirical studies show that these sequential learning procedures actually use many times fewer training examples in practice.