Robust bounds for classification via selective sampling
Robust bounds for classification via selective sampling
复制标题
DOI：
10.1145/1553374.1553390
复制
发表时间：
2009-06
期刊：
影响因子：
--
通讯作者：
N. Cesa-Bianchi;C. Gentile;Francesco Orabona
中科院分区：
文献类型：
--
作者：
N. Cesa-Bianchi;C. Gentile;Francesco Orabona
在选择性抽样协议中，提出了一种新的二值分类算法。我们的算法使用正则化最小二乘（RLS）作为基本分类器，因此它可以在任何RKHS中有效地运行。与以前基于边缘的半监督算法不同，我们的采样条件取决于简单线性标签噪声模型下RLS估计的偏差和方差的同时上界。这一事实使我们能够证明对任意实例序列都适用的性能界限。特别是，我们表明，我们的采样策略通过查询Õ （d/ε2）查询（在RKHS情况下，d被合适的谱量取代），将贝叶斯最优分类器的边际近似为任何期望的精度ε。虽然这些是在完全监督的i.i.d情况下的标准速率，但在我们更困难的设置中，先前已知的最佳结果是Õ （d3/ε4）。初步实验表明，我们的一些算法也表现出良好的实用性能。
We introduce a new algorithm for binary classification in the selective sampling protocol. Our algorithm uses Regularized Least Squares (RLS) as base classifier, and for this reason it can be efficiently run in any RKHS. Unlike previous margin-based semi-supervised algorithms, our sampling condition hinges on a simultaneous upper bound on bias and variance of the RLS estimate under a simple linear label noise model. This fact allows us to prove performance bounds that hold for an arbitrary sequence of instances. In particular, we show that our sampling strategy approximates the margin of the Bayes optimal classifier to any desired accuracy ε by asking Õ (d/ε2) queries (in the RKHS case d is replaced by a suitable spectral quantity). While these are the standard rates in the fully supervised i.i.d. case, the best previously known result in our harder setting was Õ (d3/ε4). Preliminary experiments show that some of our algorithms also exhibit a good practical performance.