Sequential PAC learning
Sequential PAC learning
复制标题
顺序 PAC 学习
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
R. Greiner
中科院分区：
文献类型：
--
作者：
Dale Schuurmans;R. Greiner
我们考虑使用“在线”停止规则来减少拍学习所需的训练样本的数量。不是收集一个大的训练样本，可以证明足以消除所有坏的假设，而是一次观察一个训练样本，并“在线”决定是否停止并返回一个假设，或者继续训练。这种方法的主要好处是，我们可以检测假设者何时实际上已经“[收敛]”，并在标准固定样本大小界限之前停止训练。本文提出了一系列这样的顺序学习过程：分布免费拍学习，“雾有界拍”转换，分布特定的拍学习，分别。我们分析了这些程序的最坏情况预期训练样本量，并表明这通常小于现有的固定样本量界限-同时提供完全相同的最坏情况拍保证。我们还提供了下限，表明这些减少最多可以涉及常数（可能是对数）的因素。然而，实证研究表明，这些顺序学习过程实际上在实践中使用的训练样本要少很多倍。
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.