Generalization error for multi-class margin classification

@article{citeulike:2330392, abstract = {In this article, we study rates of convergence of the generalization error of multi-class margin classifiers. In particular, we develop an upper bound theory quantifying the generalization error of various large margin classifiers. The theory permits a treatment of general margin losses, convex or nonconvex, in presence or absence of a dominating class. Three main results are established. First, for any fixed margin loss, there may be a trade-off between the ideal and actual generalization performances with respect to the choice of the class of candidate decision functions, which is governed by the trade-off between the approximation and estimation errors. In fact, different margin losses lead to different ideal or actual performances in specific cases. Second, we demonstrate, in a problem of linear learning, that the convergence rate can be arbitrarily fast in the sample size \$n\$ depending on the joint distribution of the input/output pair. This goes beyond the anticipated rate \$O(n^{-1})\$. Third, we establish rates of convergence of several margin classifiers in feature selection with the number of candidate variables \$p\$ allowed to greatly exceed the sample size \$n\$ but no faster than \$exp(n)\$.}, author = {Shen, Xiaotong and Wang, Lifeng }, citeulike-article-id = {2330392}, doi = {10.1214/07-EJS069}, journal = {Electronic Journal of Statistics}, pages = {307--330}, posted-at = {2008-02-04 19:26:27}, priority = {2}, title = {Generalization error for multi-class margin classification}, url = {http://dx.doi.org/10.1214/07-EJS069}, volume = {1}, year = {2007} }

TY - JOUR ID - citeulike:2330392 L3 - citeulike-article-id:2330392 TI - Generalization error for multi-class margin classification JF - Electronic Journal of Statistics VL - 1 SP - 307 EP - 330 N2 - In this article, we study rates of convergence of the generalization error of multi-class margin classifiers. In particular, we develop an upper bound theory quantifying the generalization error of various large margin classifiers. The theory permits a treatment of general margin losses, convex or nonconvex, in presence or absence of a dominating class. Three main results are established. First, for any fixed margin loss, there may be a trade-off between the ideal and actual generalization performances with respect to the choice of the class of candidate decision functions, which is governed by the trade-off between the approximation and estimation errors. In fact, different margin losses lead to different ideal or actual performances in specific cases. Second, we demonstrate, in a problem of linear learning, that the convergence rate can be arbitrarily fast in the sample size $n$ depending on the joint distribution of the input/output pair. This goes beyond the anticipated rate $O(n^{-1})$. Third, we establish rates of convergence of several margin classifiers in feature selection with the number of candidate variables $p$ allowed to greatly exceed the sample size $n$ but no faster than $exp(n)$. AU - Shen, Xiaotong AU - Wang, Lifeng PY - 2007/// UR - http://dx.doi.org/10.1214/07-EJS069 ER -