Differences

This shows you the differences between two versions of the page.

--- world:partition [2019/02/16 09:06]
douc [A useful result for the consistency of Decision Trees.]
+++ world:partition [2022/03/16 07:40]
127.0.0.1 external edit
@@ Line 1: / Line 1: @@
+{{page>:defs}}
+====== 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$

Welcome to Randal Douc's wiki

User Tools

Site Tools

Differences

Page Tools