world:partition
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
world:partition [2019/02/16 09:06] douc [A useful result for the consistency of Decision Trees.] |
world:partition [2023/10/18 16:52] rdouc [A useful result for the consistency of Decision Trees.] |
||
|---|---|---|---|
| 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%> | ||
| + | __**Stone's 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$ | ||
world/partition.txt · Last modified: 2023/10/18 16:52 by rdouc
Page Tools
