In this paper we present a simple partitioning based technique to refine
the statistical analysis of classification algorithms. The core of our
idea is to divide the input space into two parts such that the first
part contains a suitable vicinity around the decision boundary, while
the second part is sufficiently far away from the decision boundary.
Using a set of margin conditions we are then able to control the
classification error on both parts separately. By balancing out these
two error terms we obtain a refined error analysis in a final step. We
apply this general idea to the histogram rule and show that even for
this simple method we obtain, under certain assumptions, better rates
than the ones known for support vector machines, for certain plug-in
classifiers, and for a recently analyzed tree based
adaptive-partitioning ansatz. Moreover, we show that a margin condition
which sets the critical noise in relation to the decision boundary makes
it possible to improve the optimal rates proven for distributions
without this margin condition.
%0 Journal Article
%1 WOS:000438839900024
%A Blaschzyk, Ingrid
%A Steinwart, Ingo
%C 3163 SOMERSET DR, CLEVELAND, OH 44122 USA
%D 2018
%I INST MATHEMATICAL STATISTICS
%J ELECTRONIC JOURNAL OF STATISTICS
%K imported from:brittalenz
%N 1
%P 793-823
%R 10.1214/18-EJS1406
%T Improved classification rates under refined margin conditions
%V 12
%X In this paper we present a simple partitioning based technique to refine
the statistical analysis of classification algorithms. The core of our
idea is to divide the input space into two parts such that the first
part contains a suitable vicinity around the decision boundary, while
the second part is sufficiently far away from the decision boundary.
Using a set of margin conditions we are then able to control the
classification error on both parts separately. By balancing out these
two error terms we obtain a refined error analysis in a final step. We
apply this general idea to the histogram rule and show that even for
this simple method we obtain, under certain assumptions, better rates
than the ones known for support vector machines, for certain plug-in
classifiers, and for a recently analyzed tree based
adaptive-partitioning ansatz. Moreover, we show that a margin condition
which sets the critical noise in relation to the decision boundary makes
it possible to improve the optimal rates proven for distributions
without this margin condition.
@article{WOS:000438839900024,
abstract = {In this paper we present a simple partitioning based technique to refine
the statistical analysis of classification algorithms. The core of our
idea is to divide the input space into two parts such that the first
part contains a suitable vicinity around the decision boundary, while
the second part is sufficiently far away from the decision boundary.
Using a set of margin conditions we are then able to control the
classification error on both parts separately. By balancing out these
two error terms we obtain a refined error analysis in a final step. We
apply this general idea to the histogram rule and show that even for
this simple method we obtain, under certain assumptions, better rates
than the ones known for support vector machines, for certain plug-in
classifiers, and for a recently analyzed tree based
adaptive-partitioning ansatz. Moreover, we show that a margin condition
which sets the critical noise in relation to the decision boundary makes
it possible to improve the optimal rates proven for distributions
without this margin condition.},
added-at = {2021-09-13T10:24:35.000+0200},
address = {3163 SOMERSET DR, CLEVELAND, OH 44122 USA},
affiliation = {Blaschzyk, I (Corresponding Author), Univ Stuttgart, Inst Stochast \& Applicat, Pfaffenwaldring 57, D-70569 Stuttgart, Germany.
Blaschzyk, Ingrid; Steinwart, Ingo, Univ Stuttgart, Inst Stochast \& Applicat, Pfaffenwaldring 57, D-70569 Stuttgart, Germany.},
author = {Blaschzyk, Ingrid and Steinwart, Ingo},
author-email = {ingrid.blaschzyk@mathematik.uni-stuttgart.de
ingo.steinwart@mathematik.uni-stuttgart.de},
biburl = {https://puma.ub.uni-stuttgart.de/bibtex/210b15f299fcaf91f1dcd6b119dba99de/mathematik},
da = {2021-08-10},
doc-delivery-number = {GN2PL},
doi = {10.1214/18-EJS1406},
interhash = {5f8854e8e7c81b136ae83283a523b294},
intrahash = {10b15f299fcaf91f1dcd6b119dba99de},
issn = {1935-7524},
journal = {ELECTRONIC JOURNAL OF STATISTICS},
journal-iso = {Electron. J. Stat.},
keywords = {imported from:brittalenz},
language = {English},
number = 1,
number-of-cited-references = {10},
oa = {gold, Green Submitted},
pages = {793-823},
publisher = {INST MATHEMATICAL STATISTICS},
research-areas = {Mathematics},
times-cited = {1},
timestamp = {2021-09-13T08:24:35.000+0200},
title = {Improved classification rates under refined margin conditions},
type = {Article},
unique-id = {WOS:000438839900024},
usage-count-last-180-days = {1},
usage-count-since-2013 = {1},
volume = 12,
web-of-science-categories = {Statistics \& Probability},
year = 2018
}