Sample Complexity Result for Multi-category Classifiers of Bounded Variation
Sample Complexity Result for Multi-category Classifiers of Bounded Variation
复制标题
有界变异多类别分类器的样本复杂度结果
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Khadija Musayeva
中科院分区：
文献类型：
--
作者：
Khadija Musayeva
当多类别分类器的经验性能与泛化性能在截断的铰损失函数的基础上定义时，我们通过经验L1 -范数覆盖数来控制这些性能之间均匀偏差的概率。对多类别分类器实现的函数所做的唯一假设是它们具有有界变差（BV）。对于这样的分类器，我们推导出足够的样本量估计，使上述性能具有高概率接近。特别地，我们感兴趣的是这个估计对类的数量C的依赖性。为此，首先，我们对vc维的尺度敏感版本上界，即在R^d上定义的BV函数集的散块维，当尺度趋于0时，它给出O（1/epsilon^d）。其次，我们提供了一个关于C的更清晰的脂肪粉碎维分解结果，对于BV函数集，它从O（C^(d/2 +1)）改进到O（Cln^2(C)）。这种改进随后传播到样本复杂性估计中。
We control the probability of the uniform deviation between empirical and generalization performances of multi-category classifiers by an empirical L1 -norm covering number when these performances are defined on the basis of the truncated hinge loss function. The only assumption made on the functions implemented by multi-category classifiers is that they are of bounded variation (BV). For such classifiers, we derive the sample size estimate sufficient for the mentioned performances to be close with high probability. Particularly, we are interested in the dependency of this estimate on the number C of classes. To this end, first, we upper bound the scale-sensitive version of the VC-dimension, the fat-shattering dimension of sets of BV functions defined on R^d which gives a O(1/epsilon^d ) as the scale epsilon goes to zero. Secondly, we provide a sharper decomposition result for the fat-shattering dimension in terms of C, which for sets of BV functions gives an improvement from O(C^(d/2 +1)) to O(Cln^2(C)). This improvement then propagates to the sample complexity estimate.