On the generalization ability of on-line learning algorithms
On the generalization ability of on-line learning algorithms
复制标题
DOI：
10.1109/tit.2004.833339
复制
发表时间：
2004-09-01
影响因子：
2.5
通讯作者：
Gentile, C
中科院分区：
文献类型：
--
作者：
Cesa-Bianchi, N;Conconi, A;Gentile, C
在本文中，它显示了如何从由任意的在线学习算法产生的假设中提取一个具有很小风险的假设，该假设是在独立且相同分布的数据样本上运行的。使用一个简单的大偏差参数，我们证明了与该假设的风险相关的紧密依赖性界限，这是一个易于计算的统计统计量M-N与集合的在线性能相关的。通过M-N上方的尖端边界，我们根据经验核基质的光谱获得了内核感知算法的风险尾部边界。这些界限表明，通过我们的方法找到的线性假设在所有线性功能的类别上实现了铰链损失和保证金大小之间的最佳权衡，这一问题是由以前的结果所留下的。我们方法的独特特征是，我们方法的独特功能是，关键工具是用于我们的分析来自对单个序列预测的模型。即，一个模型对生成数据的来源没有概率假设。实际上，这些工具变得如此强大，以至于我们只需要非常基本的统计事实即可获得我们的最终风险范围。
In this paper, it is shown how to extract a hypothesis with small risk from the ensemble of hypotheses generated by an arbitrary on-line learning algorithm run on an independent and identically distributed (i.i.d.) sample of data. Using a simple large deviation argument, we prove tight data-dependent bounds for the risk of this hypothesis in terms of an easily computable statistic M-n associated with the on-line performance of the ensemble. Via sharp pointwise bounds on M-n, we then obtain risk tail bounds for kernel Perceptron algorithms in terms of the spectrum of the empirical kernel matrix. These bounds reveal that the linear hypotheses found via our approach achieve optimal tradeoffs between hinge loss and margin size over the class of all linear functions, an issue that was left open by previous results.A distinctive feature of our approach is that the key tools for our analysis come from the model of prediction of individual sequences; i.e., a model making no probabilistic assumptions on the source generating the data. In fact, these tools turn out to be so powerful that we only need very elementary statistical facts to obtain our final risk bounds.