Improved classification rates under refined margin conditions

DOI10.1214/18-EJS1406MaRDI QIDQ1746541zbMATH OpenOpenAlexFDO

Authors Ingrid Blaschzyk, Ingo Steinwart

Publication date 25 April 2018

Published in Electronic Journal of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.09109, https://projecteuclid.org/euclid.ejs/1520046229

zbMATH Keywords

classificationexcess riskfast rates of convergencehistogram rulestatistical learning

Mathematics Subject Classification ID

Asymptotic properties of nonparametric inference (62G20) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

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.

Recommendations

• On the Rate of Convergence of Local Averaging Plug-In Classification Rules Under a Margin Condition
• Improved classification rates for localized algorithms under margin conditions
• Classification algorithms using adaptive partitioning
• On the rate of convergence of error estimates for the partitioning classification rule
• Rate of convergence of k-nearest-neighbor classification rule

Cites work

• Classification algorithms using adaptive partitioning
• Fast learning rates for plug-in classifiers
• Fully adaptive density-based clustering
• scientific article; zbMATH DE number 893887 (Why is no real title available?)
• scientific article; zbMATH DE number 3280855 (Why is no real title available?)
• On the Rate of Convergence of Local Averaging Plug-In Classification Rules Under a Margin Condition
• Random forests
• Risk bounds for statistical learning
• Support Vector Machines

Cited in

(7)

• Adaptive learning rates for support vector machines working on data with low intrinsic dimension
• On the Rate of Convergence of Local Averaging Plug-In Classification Rules Under a Margin Condition
• Rate of convergence of k-nearest-neighbor classification rule
• Classification algorithms using adaptive partitioning
• Improved classification rates for localized algorithms under margin conditions
• Intrinsic dimension adaptive partitioning for kernel methods
• Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces

This page was built for publication: Improved classification rates under refined margin conditions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1746541)