Minimax-optimal classification with dyadic decision trees

• Published in: IEEE transactions on information theory 2006-04, Vol.52 (4), p.1335-1353
• Main Authors: Scott, C., Nowak, R.D.
• Format: Article
• Language: English
• Subjects: Applied sciences; Classification; Classification tree analysis; Classifiers; Complexity regularization; Computation; Computational complexity; Convergence; DDT; Decision trees; Dyadics; Exact sciences and technology; feature rejection; generalization error bounds; Information theory; Information, signal and communications theory; manifold learning; minimax optimality; Minimax techniques; Noise level; Optimization; Partitioning algorithms; Performance analysis; pruning; rates of convergence; recursive dyadic partitions; Risk management; Signal and communications theory; Signal representation. Spectral analysis; Signal, noise; Statistical learning; statistical learning theory; Telecommunications and information theory
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2006.871056

Decision trees are among the most popular types of classifiers, with interpretability and ease of implementation being among their chief attributes. Despite the widespread use of decision trees, theoretical analysis of their performance has only begun to emerge in recent years. In this paper, it is shown that a new family of decision trees, dyadic decision trees (DDTs), attain nearly optimal (in a minimax sense) rates of convergence for a broad range of classification problems. Furthermore, DDTs are surprisingly adaptive in three important respects: they automatically 1) adapt to favorable conditions near the Bayes decision boundary; 2) focus on data distributed on lower dimensional manifolds; and 3) reject irrelevant features. DDTs are constructed by penalized empirical risk minimization using a new data-dependent penalty and may be computed exactly with computational complexity that is nearly linear in the training sample size. DDTs comprise the first classifiers known to achieve nearly optimal rates for the diverse class of distributions studied here while also being practical and implementable. This is also the first study (of which we are aware) to consider rates for adaptation to intrinsic data dimension and relevant features.