Article ID Journal Published Year Pages File Type
4951216 Journal of Computer and System Sciences 2017 24 Pages PDF
Abstract
In the framework of agnostic learning, one of the main open problems of the theory of multi-category pattern classification is the characterization of the way the complexity varies with the number C of categories. More precisely, if the classifier is characterized only through minimal learnability hypotheses, then the optimal dependency on C that an upper bound on the probability of error should exhibit is unknown. We consider margin classifiers. They are based on classes of vector-valued functions with one component function per category, and the classes of component functions are uniform Glivenko-Cantelli classes. For these classifiers, an Lp-norm Sauer-Shelah lemma is established. It is then used to derive guaranteed risks in the L∞ and L2-norms. These bounds improve over the state-of-the-art ones with respect to their dependency on C, which is sublinear.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,