# Welcome to Randal Douc's wiki

A collaborative site on maths but not only!

• Theatre
• Research
• Teaching

### Miscellanous

world:partition


2017/10/07 23:39 ·

# A useful result for the consistency of Decision Trees.

Assume that, given iid $(X_i)_{i\in [1:n]}$ taking values in $[0,1]^d$ and some extra random variable $\Theta$, you build a decision tree with cells $A_\ell$. Note that $A_\ell$ are deterministically obtained from $(X_i)_{i\in [1:n]}$ and $\Theta$ but we do not stress the dependence on these variables in the notation.

Assume that $Y_i=r(X_i)+\epsilon_i$ where $(\epsilon_i)_{i \in [1:n]}$ are iid, centered with finite variance $\sigma^2$ and the $(\epsilon_i)$ are independent from the $(X_i)$ and $\Theta$. In what follows $(X,Y) \eqlaw (X_1,Y_1)$. Denote $$\hat r_n(x, \Theta) = \sum_{i=1}^n w_{ni} Y_i, \quad \mbox{where} \quad w_{ni}\eqdef \frac{\indiacc{X_i \in A_n(x, \Theta)}}{N_n(x, \Theta)}$$ where $A_n(x,\Theta)$ is the cell containing $x$ and $N_n(x, \Theta)=\card\set{i\in [1:n]}{X_i \in A_n(x,\Theta)}$. Define the diameter of any cell $A$ by $$\textrm{diam}(A) = \sup_{x,z \in A} \|x - z\|_2.$$

Theorem Assume that

• $\textrm{diam}(A_n(X,\Theta)) \to 0$ in probability, as $n \to \infty$.
• $N_n(X, \Theta) \to \infty$ in probability, as $n \to \infty$.

Then, $$\lim_{n\to \infty}\PE\lrb{(\hat r_n(X, \Theta)- r(X))^2} = 0,$$

$\bproof$ The proof is based on the following lemma:

Lemma Let $(Z_n)$ be a sequence of random variables that converge to $0$ in probability and take values on $\Zset$. Assume that $F$ is a bounded function on $\Zset$, which is continuous at $0$. Then $\PE[F(Z_n)] \to 0$.

Proof of the Lemma: Write $$\PE[F(Z_n)]=\PE[F(Z_n)\lrcb{\indi{|Z_n| >\epsilon}+\indi{|Z_n| \leq \epsilon}}]\leq \|F\|_\infty \PP(|Z_n|>\epsilon) + \sup_{|z| \leq \epsilon} F(z)$$ Thus, $\limsup_n \PE[F(Z_n)] \leq \sup_{|z| \leq \epsilon} F(z)$ and since $\epsilon$ is arbitrary, this concludes the proof. $\eproof$

Denote $\Delta(\rho)=\sup_{\|u-v\| \leq \rho} |r(u)-r(v)|$ and since $r$ is continuous on the compact set $[0,1]^d$, it is bounded and uniformly continuous. Therefore, $\Delta$ is a bounded function that converges to $0$ as $\rho \to 0$. Then, denoting $\rho_n(X,\Theta)=\textrm{diam} A_n(X,\Theta) \in [0,\sqrt{d}]$, we have by the triangular inequality, \begin{align*} \ltwo{\hat r_n(X, \Theta)- r(X)} & \leq \ltwo{\sum_{i=1}^{n} w_{ni} [r(X_i)-r(X)]} + \ltwo{\sum_{i=1}^{n} w_{ni} \epsilon_i}\\ & \leq \ltwo{\Delta(\rho_n(X,\Theta))}+\sigma \PE^{1/2}\lrb{\sum_{i=1}^{n} w^2_{ni}}\\ & \leq \ltwo{\Delta(\rho_n(X,\Theta))}+\sigma\PE^{1/2}\lrb{\frac{1}{N_n(X,\Theta)}\underbrace{\sum_{i=1}^{n} w_{ni}}_{=1}} \end{align*} The proof follows by applying the lemma to the random variables $Z_n=\rho_n(X,\Theta)$ on $[0,\sqrt{d}]$ with the function $\Delta$ that is bounded on $[0,\sqrt{d}]$ and continuous at $0$ and then to the random variables $Z_n=1/N_n(X,\Theta)$ taking values on $[0,1]$ with the bounded function $x\mapsto x$ on $[0,1]$ which is continuous at $0$. $\eproof$