Active Learning in the Non-realizable Case
Active Learning in the Non-realizable Case
复制标题
DOI：
10.1007/11894841_9
复制
发表时间：
2006-10
期刊：
影响因子：
--
通讯作者：
Matti Kääriäinen
中科院分区：
文献类型：
--
作者：
Matti Kääriäinen
现有的主动学习算法大多基于可实现性假设：假设学习者的假设类包含一个目标函数，该目标函数完美地分类了所有的训练和测试用例。这种假设在实践中几乎是站不住脚的。本文研究了放松可实现性假设对主动学习样本复杂度的影响。首先，我们扩展了已有的关于查询学习的结果，证明了任何可实现情况下的主动学习算法都可以转化为容忍随机有界速率类噪声。因此，有界速率类噪声几乎不会给主动学习增加额外的复杂性，尤其是与被动学习相比，指数标签复杂度的降低仍然是可能的。我们的第二个结果表明，如果我们转移到统计学习理论的真正不可实现的模型，那么主动学习的标签复杂性与被动学习的标签复杂度具有相同的Ω(1/ε2)对精度参数ε的依赖关系。更具体地说，我们证明了在假设学习者假设类中最好的分类器具有至多β>；0的假设下，主动学习的标签复杂度为Ω(β2/ε2log(1/δ)，其中精度参数ε度量主动学习者必须获得的假设类中的最优，δ是置信度参数。这一下限的含义是，在主动学习的现实模型中，不应期望指数节省，因此，主动学习中的标签复杂性目标应该得到完善。
Most of the existing active learning algorithms are based on the realizability assumption: The learner’s hypothesis class is assumed to contain a target function that perfectly classifies all training and test examples. This assumption can hardly ever be justified in practice. In this paper, we study how relaxing the realizability assumption affects the sample complexity of active learning. First, we extend existing results on query learning to show that any active learning algorithm for the realizable case can be transformed to tolerate random bounded rate class noise. Thus, bounded rate class noise adds little extra complications to active learning, and in particular exponential label complexity savings over passive learning are still possible. However, it is questionable whether this noise model is any more realistic in practice than assuming no noise at all.Our second result shows that if we move to the truly non-realizable model of statistical learning theory, then the label complexity of active learning has the same dependence Ω(1/ε2) on the accuracy parameterεas the passive learning label complexity. More specifically, we show that under the assumption that the best classifier in the learner’s hypothesis class has generalization error at mostβ>0, the label complexity of active learning is Ω(β2/ε2log(1/δ)), where the accuracy parameterεmeasures how close to optimal within the hypothesis class the active learner has to get andδis the confidence parameter. The implication of this lower bound is that exponential savings should not be expected in realistic models of active learning, and thus the label complexity goals in active learning should be refined.