Classification algorithms using adaptive partitioning

Peter Binev; Albert Cohen; Wolfgang Dahmen; Ronald DeVore

doi:10.1214/14-AOS1234

Classification algorithms using adaptive partitioning

Peter Binev, Albert Cohen, Wolfgang Dahmen, Ronald DeVore

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

© 2014 Institute of Mathematical Statistics. 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 - 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 Holder 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.

Original language	English (US)
Pages (from-to)	2141-2163
Number of pages	23
Journal	The Annals of Statistics
Volume	42
Issue number	6
DOIs	https://doi.org/10.1214/14-AOS1234
State	Published - Dec 2014
Externally published	Yes

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledged KAUST grant number(s): KUS-C1-016-04
Acknowledgements: Supported by the Office of Naval Research Contracts ONR-N00014-08-1-1113, ONR-N0001409-1-0107; the AFOSR Contract FA95500910500; the ARO/DoD Contract W911NF-07-1-0185; the NSF Grants DMS-09-15231, DMS-12-22390 and DMS-09-15104; the Special Priority Program SPP 1324, funded by DFG; the French German PROCOPE contract 11418YB; the Agence Nationale de la Recherche (ANR) project ECHANGE (ANR-08-EMER-006); the excellence chair of the Foundation "Sciences Mathematiques de Paris" held by Ronald DeVore. This publication is based on work supported by Award No. KUS-C1-016-04, made by King Abdullah University of Science and Technology (KAUST).
This publication acknowledges KAUST support, but has no KAUST affiliated authors.

Access to Document

10.1214/14-AOS1234

Cite this

@article{32f04f2edfb245c2a3488da997479d93,

title = "Classification algorithms using adaptive partitioning",

abstract = "{\textcopyright} 2014 Institute of Mathematical Statistics. 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 - 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 Holder 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.",

author = "Peter Binev and Albert Cohen and Wolfgang Dahmen and Ronald DeVore",

note = "KAUST Repository Item: Exported on 2020-10-01 Acknowledged KAUST grant number(s): KUS-C1-016-04 Acknowledgements: Supported by the Office of Naval Research Contracts ONR-N00014-08-1-1113, ONR-N0001409-1-0107; the AFOSR Contract FA95500910500; the ARO/DoD Contract W911NF-07-1-0185; the NSF Grants DMS-09-15231, DMS-12-22390 and DMS-09-15104; the Special Priority Program SPP 1324, funded by DFG; the French German PROCOPE contract 11418YB; the Agence Nationale de la Recherche (ANR) project ECHANGE (ANR-08-EMER-006); the excellence chair of the Foundation {"}Sciences Mathematiques de Paris{"} held by Ronald DeVore. This publication is based on work supported by Award No. KUS-C1-016-04, made by King Abdullah University of Science and Technology (KAUST). This publication acknowledges KAUST support, but has no KAUST affiliated authors.",

year = "2014",

month = dec,

doi = "10.1214/14-AOS1234",

language = "English (US)",

volume = "42",

pages = "2141--2163",

journal = "The Annals of Statistics",

issn = "0090-5364",

publisher = "Institute of Mathematical Statistics",

number = "6",

}

TY - JOUR

T1 - Classification algorithms using adaptive partitioning

AU - Binev, Peter

AU - Cohen, Albert

AU - Dahmen, Wolfgang

AU - DeVore, Ronald

N1 - KAUST Repository Item: Exported on 2020-10-01 Acknowledged KAUST grant number(s): KUS-C1-016-04 Acknowledgements: Supported by the Office of Naval Research Contracts ONR-N00014-08-1-1113, ONR-N0001409-1-0107; the AFOSR Contract FA95500910500; the ARO/DoD Contract W911NF-07-1-0185; the NSF Grants DMS-09-15231, DMS-12-22390 and DMS-09-15104; the Special Priority Program SPP 1324, funded by DFG; the French German PROCOPE contract 11418YB; the Agence Nationale de la Recherche (ANR) project ECHANGE (ANR-08-EMER-006); the excellence chair of the Foundation "Sciences Mathematiques de Paris" held by Ronald DeVore. This publication is based on work supported by Award No. KUS-C1-016-04, made by King Abdullah University of Science and Technology (KAUST). This publication acknowledges KAUST support, but has no KAUST affiliated authors.

PY - 2014/12

Y1 - 2014/12

N2 - © 2014 Institute of Mathematical Statistics. 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 - 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 Holder 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.

AB - © 2014 Institute of Mathematical Statistics. 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 - 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 Holder 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.

UR - http://hdl.handle.net/10754/597780

UR - http://projecteuclid.org/euclid.aos/1413810724

UR - http://www.scopus.com/inward/record.url?scp=84908209335&partnerID=8YFLogxK

U2 - 10.1214/14-AOS1234

DO - 10.1214/14-AOS1234

M3 - Article

SN - 0090-5364

VL - 42

SP - 2141

EP - 2163

JO - The Annals of Statistics

JF - The Annals of Statistics

IS - 6

ER -

Classification algorithms using adaptive partitioning

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this