Tree-structured regression and the differentiation of integrals. (English) Zbl 1122.62027

Summary: This paper provides answers to questions regarding the almost sure limiting behavior of rooted, binary tree-structured rules for regression. Examples show that questions raised by L. Gordon and the present author [J. Multivariate Anal. 15, 147–163 (1984; Zbl 0542.62032)] have negative answers. For these examples of regression functions and sequences of their associated binary tree-structured approximations, for all regression functions except those in a set of the first category, almost sure consistency fails dramatically on events of full probability. One consequence is that almost sure consistency of binary tree-structured rules such as classification and regression tree (CART) requires conditions beyond requiring that (1) the regression function be in \({\mathcal L}^1\), (2) partitions of a Euclidean feature space be into polytopes with sides parallel to the coordinate axes, (3) the mesh of the partitions becomes arbitrarily fine almost surely and (4) the empirical learning sample content of each polytope be “large enough.”
The material in this paper includes the solution to a problem raised by Dudley in discussions. The main results have a corollary regarding the lack of almost sure consistency of certain Bayes-risk consistent rules for classification.


62G08 Nonparametric regression and quantile regression
60F15 Strong limit theorems
28A15 Abstract differentiation theory, differentiation of set functions
26B05 Continuity and differentiation questions
62C12 Empirical decision procedures; empirical Bayes procedures


Zbl 0542.62032


Full Text: DOI arXiv


[1] Breiman, L., Friedman, J. H., Olshen, R. A. and Stone, C. J. (1984). Classification and Regression Trees . Wadsworth, Belmont, CA. Since 1993 this book has been published by Chapman and Hall, New York. · Zbl 0541.62042
[2] Busemann, H. and Feller, W. (1934). Zur Differentiation der Lebesgueschen Integrale. Fund. Math. 22 226–256. · Zbl 0009.10601
[3] de Guzmán, M. (1975). Differentiation of Integrals in R\(^n\) . Lecture Notes in Math. 481 . Springer, Berlin. · Zbl 0327.26010
[4] Devroye, L., Györfi, L. and Lugosi, G. (1996). A Probabilistic Theory of Pattern Recognition . Springer, New York. · Zbl 0853.68150
[5] Devroye, L. and Krzyżak, A. (2002). New multivariate product density estimators. J. Multivariate Anal. 82 88–110. · Zbl 0995.62034
[6] Donoho, D. L. (1997). CART and best-ortho-basis: A connection. Ann. Statist. 25 1870–1911. · Zbl 0942.62044
[7] Gersho, A. and Gray, R. M. (1992). Vector Quantization and Signal Compression . Kluwer, Dordrecht. · Zbl 0782.94001
[8] Gordon, L. and Olshen, R. A. (1984). Almost surely consistent nonparametric regression from recursive partitioning schemes. J. Multivariate Anal. 15 147–163. · Zbl 0542.62032
[9] Hastie, T., Tibshirani, R. and Friedman, J. (2001). The Elements of Statistical Learning: Data Mining, Inference and Prediction . Springer, New York. · Zbl 0973.62007
[10] Lugosi, G. and Nobel, A. (1996). Consistency of data-driven histogram methods for density estimation and classification. Ann. Statist. 24 687–706. · Zbl 0859.62040
[11] Nobel, A. (1996). Histogram regression estimation using data-dependent partitions. Ann. Statist. 24 1084–1105. · Zbl 0862.62038
[12] Ripley, B. D. (1996). Pattern Recognition and Neural Networks . Cambridge Univ. Press. · Zbl 0853.62046
[13] Saks, S. (1934). Remarks on the differentiability of the Lebesgue indefinite integral. Fund. Math. 22 257–261. · Zbl 0009.10602
[14] Stone, C. J. (1977). Consistent nonparametric regression (with discussion). Ann. Statist. 5 595–645. · Zbl 0366.62051
[15] Zhang, H. and Singer, B. (1999). Recursive Partitioning in the Health Sciences . Springer, New York. · Zbl 0920.62135
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.