Classification algorithms using adaptive partitioning

DOI10.1214/14-AOS1234zbMATH Open1310.62074MaRDI QIDQ482871FDOQ482871

Authors Peter Binev, Albert Cohen, Wolfgang Dahmen, Ronald DeVore

Publication date 6 January 2015

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.0839

zbMATH Keywords

binary classificationadaptive methodsset estimatorstree-based algorithms

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Neural nets and related approaches to inference from stochastic processes (62M45) Computational learning theory (68Q32) Numerical interpolation (65D05)

Abstract: Algorithms for binary classification based on adaptive tree partitioning are formulated and analyzed for both their risk performance and their friendliness to numerical implementation. The algorithms can be viewed as generating a set approximation to the Bayes set and thus fall into the general category of set estimators. In contrast with the most studied tree-based algorithms, which utilize piecewise constant approximation on the generated partition [IEEE Trans. Inform. Theory 52 (2006) 1335-1353; Mach. Learn. 66 (2007) 209-242], we consider decorated trees, which allow us to derive higher order methods. Convergence rates for these methods are derived in terms the parameter $alpha$ of margin conditions and a rate $s$ of best approximation of the Bayes set by decorated adaptive partitions. They can also be expressed in terms of the Besov smoothness $$ of the regression function that governs its approximability by piecewise polynomials on adaptive partition. The execution of the algorithms does not require knowledge of the smoothness or margin conditions. Besov smoothness conditions are weaker than the commonly used H"{o}lder conditions, which govern approximation by nonadaptive partitions, and therefore for a given regression function can result in a higher rate of convergence. This in turn mitigates the compatibility conflict between smoothness and margin parameters.

Recommendations

• Improved classification rates under refined margin conditions
• 10.1162/153244304773936108
• scientific article; zbMATH DE number 2089371
• A novel algorithm to optimize classification trees
• Learning Theory

Cites work

• scientific article; zbMATH DE number 3860199 (Why is no real title available?)
• scientific article; zbMATH DE number 1215245 (Why is no real title available?)
• scientific article; zbMATH DE number 893887 (Why is no real title available?)
• Adaptation to anisotropy and inhomogeneity via dyadic piecewise polynomial selection
• Classification algorithms using adaptive partitioning
• Fast learning rates for plug-in classifiers
• Minimax-optimal classification with dyadic decision trees
• Optimal aggregation of classifiers in statistical learning.
• Risk bounds for statistical learning
• Theory of Classification: a Survey of Some Recent Advances
• Tree approximation and optimal encoding
• Universal algorithms for learning theory. II: Piecewise polynomial functions

Cited in

(5)

• A method to enrich experimental datasets by means of numerical simulations in view of classification tasks
• Exact asymptotic orders of various randomized widths on Besov classes
• Improved classification rates under refined margin conditions
• Classification algorithms using adaptive partitioning
• Rate of convergence of \(k\)-nearest-neighbor classification rule

This page was built for publication: Classification algorithms using adaptive partitioning

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