Sample Complexity Result for Multi-category Classifiers of Bounded Variation
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Rademacher Complexity and Generalization Performance of Multi-category Margin Classifiers
One of the main open problems in the theory of multi-category margin classification is the form of the optimal dependency of a guaranteed risk on the number C of categories, the sample size m and the margin parameter gam…
Angle-Based Cost-Sensitive Multicategory Classification
Many real-world classification problems come with costs which can vary for different types of misclassification. It is thus important to develop cost-sensitive classifiers which minimize the total misclassification cost.…
ClassificationGeneral ClassificationMulti-category Angle-based Classifier Refit
Classification is an important statistical learning tool. In real application, besides high prediction accuracy, it is often desirable to estimate class conditional probabilities for new observations. For traditional pro…
General ClassificationDeep Cocktail Network: Multi-source Unsupervised Domain Adaptation with Category Shift
Unsupervised domain adaptation (UDA) conventionally assumes labeled source samples coming from a single underlying source distribution. Whereas in practical scenario, labeled data are typically collected from diverse sou…
Domain AdaptationMulti-Source Unsupervised Domain AdaptationUnsupervised Domain AdaptationOptimality Implies Kernel Sum Classifiers are Statistically Efficient
We propose a novel combination of optimization tools with learning theory bounds in order to analyze the sample complexity of optimal kernel sum classifiers. This contrasts the typical learning theoretic results which ho…
Learning Theory