Minimax Bounds for Active Learning
Minimax Bounds for Active Learning
复制标题
DOI：
10.1109/tit.2008.920189
复制
发表时间：
2007-06
影响因子：
2.5
通讯作者：
R. Castro;R. Nowak
中科院分区：
文献类型：
--
作者：
R. Castro;R. Nowak
本文分析了“主动学习”算法的潜在优势和理论挑战。主动学习涉及顺序采样过程，该过程使用从先前样本中收集的信息，以便集中采样并相对于基于非自适应（通常是随机）样本的“被动学习”算法加速学习过程。有许多经验和理论结果表明，在某些情况下，主动学习可能比被动学习更有效。然而，主动学习算法是反馈系统的事实使得它们的理论分析非常具有挑战性。本文旨在阐明主动学习中可实现的限制。使用极大极小分析技术，我们研究了可实现的分类误差收敛速度的广泛类别的分布特征的决策边界的规则性和噪声条件。结果清楚地表明，在何种条件下，人们可以期待通过积极学习取得重大成果。此外，我们表明，学习率推导出的d维特征空间中的“边界片段”类时，从上到下的特征边际密度有界是紧的。
This paper analyzes the potential advantages and theoretical challenges of "active learning" algorithms. Active learning involves sequential sampling procedures that use information gleaned from previous samples in order to focus the sampling and accelerate the learning process relative to "passive learning" algorithms, which are based on nonadaptive (usually random) samples. There are a number of empirical and theoretical results suggesting that in certain situations active learning can be significantly more effective than passive learning. However, the fact that active learning algorithms are feedback systems makes their theoretical analysis very challenging. This paper aims to shed light on achievable limits in active learning. Using minimax analysis techniques, we study the achievable rates of classification error convergence for broad classes of distributions characterized by decision boundary regularity and noise conditions. The results clearly indicate the conditions under which one can expect significant gains through active learning. Furthermore, we show that the learning rates derived are tight for "boundary fragment" classes in d-dimensional feature spaces when the feature marginal density is bounded from above and below.