Welcome to Randal Douc's wiki

You've loaded an old revision of the document! If you save it, you will create a new version with this data.

====== 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.
$$

<WRAP center round box 80%>
__**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,
$$
</WRAP>

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

<WRAP center round box 70%>
__**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$. 
</WRAP>
**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$

Please fill all the letters into the box to prove you're human. X Z S V U Please keep this field empty:

Edit summary

Welcome to Randal Douc's wiki

User Tools

Site Tools

Page Tools