Noise-Adaptive Margin-Based Active Learning and Lower Bounds under Tsybakov Noise Condition
Noise-Adaptive Margin-Based Active Learning and Lower Bounds under Tsybakov Noise Condition
复制标题
Tsybakov 噪声条件下基于噪声自适应裕度的主动学习和下界
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Aarti Singh
中科院分区：
文献类型：
--
作者：
Yining Wang;Aarti Singh
我们提出了一种简单的基于噪声的主动学习算法，以查找均质（通过原点）线性分隔符并分析其误差收敛时，当标签被噪声带来时。我们表明，当强加的噪声满足Tsybakov低噪声状况时（Mammen，Tsy-Bakov和其他1999年； Tsybakov 2004），算法是ABLETO适应未知水平的噪声水平，并且达到了最佳的STA-TISTISTISTISTISTISTISTISTISTISTISTISTISTISTISTISTISPISTISTIS率。我们还在Tsybakov噪声条件下（TNC）为Thembership查询合成方案得出了基于边缘基的主动学习量的下限（Angluin 1988）。我们的重新考虑暗示了基于流的选择采样方案（Cohn 1990）在TNC下进行一些公平简单数据分布的下限。令人惊讶的是，我们表明，即使基础数据分布与单位球的均匀分布一样简单，也无法提高这些复杂性。我们的证明涉及在D维单元球上构建一个分离的假设，并与精心设计的Tsybakakovnoise条件设计的标签分布。我们的分析也可能为其他下限的其他形式提供见解。
We present a simple noise-robust margin-based active learn-ing algorithm to find homogeneous (passing the origin) linearseparators and analyze its error convergence when labels arecorrupted by noise. We show that when the imposed noisesatisfies the Tsybakov low noise condition (Mammen, Tsy-bakov, and others 1999; Tsybakov 2004) the algorithm is ableto adapt to unknown level of noise and achieves optimal sta-tistical rate up to polylogarithmic factors. We also derive lower bounds for margin based active learningalgorithms under Tsybakov noise conditions (TNC) for themembership query synthesis scenario (Angluin 1988). Ourresult implies lower bounds for the stream based selectivesampling scenario (Cohn 1990) under TNC for some fairlysimple data distributions. Quite surprisingly, we show that thesample complexity cannot be improved even if the underly-ing data distribution is as simple as the uniform distributionon the unit ball. Our proof involves the construction of a well-separated hypothesis set on the d-dimensional unit ball alongwith carefully designed label distributions for the Tsybakovnoise condition. Our analysis might provide insights for otherforms of lower bounds as well.