A multiresolution approach to pattern recognition

This paper reports on a family of computationally practical classifiers called dyadic classification trees (DCTs). Like many multiresolution methods in other application areas, DCTs are formed by recursive dyadic partitioning of the input space, followed by pruning to avoid overfitting. We investigate three pruning rules, each motivated by statistical learning theory. These pruning rules involve penalties that are non-additive, data-dependent, and scale-dependent. They produce learning rules that achieve near-minimax rates of convergence for a certain class of problems defined in terms of the smoothness of the Bayes decision boundary. Efficient algorithms exist for implementing each pruning rule. We then briefly mention an extension of dyadic classification trees that places polynomial decision boundaries at each leaf node. This polynomial decorated dyadic classification trees achieve faster rates for smoother decision boundaries, and have improved approximation capabilities relative to classifiers that employ a single polynomial decision rule, such as polynomial-kernel SVMs.