More theorems about scale-sensitive dimensions and learning
More theorems about scale-sensitive dimensions and learning
复制标题
更多关于尺度敏感维度和学习的定理
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
Philip M. Long
中科院分区：
文献类型：
--
作者：
P. Bartlett;Philip M. Long
我们提出了一种新的通用算法，用于学习 [0; 类； 1]-值函数在预测模型的推广中，并根据 Alon、Ben-David、Cesa-Bianchi 和 Haussler 提出的 Vapnik 维度的尺度敏感推广来证明该算法的预期绝对误差的一般上限。我们给出的下限意味着我们的上限一般不能改进超过一个常数。我们应用这个结果以及 Haussler 的技术，根据这种对尺度敏感的维度概念来获得包装数的新上限。使用不同的技术，我们根据卡恩斯和夏皮尔的脂肪粉碎函数获得了包装数的新界限。我们展示了如何应用两个包装界限来获得改进的不可知学习样本复杂性的一般界限。对于每个 > 0，我们为 [0; 类] 建立较弱的充分条件和较强的必要条件。 1] 值函数可以在 内进行不可知论的学习，成为统一的 Glivenko-Cantelli 类，并且可以通过仅使用该类的假设的算法在 内进行不可知论的学习。
We present a new general-purpose algorithm for learning classes of [0; 1]-valued functions in a generalization of the prediction model, and prove a general upper bound on the expected absolute error of this algorithm in terms of a scale-sensitive generalization of the Vapnik dimension proposed by Alon, Ben-David, Cesa-Bianchi and Haussler. We give lower bounds implying that our upper bounds cannot be improved by more than a constant in general. We apply this result, together with techniques due to Haussler, to obtain new upper bounds on packing numbers in terms of this scale-sensitive notion of dimension. Using a different technique, we obtain new bounds on packing numbers in terms of Kearns and Schapire’s fat-shattering function. We show how to apply both packing bounds to obtain improved general bounds on the sample complexity of agnostic learning. For each > 0, we establish weaker sufficient and stronger necessary conditions for a class of [0; 1]-valued functions to be agnostically learnable to within , to be an uniform Glivenko-Cantelli class, and to be agnostically learnable to within by an algorithm using only hypotheses from the class.