Suppose we have training data $(\mathbf{x}_1, y_1), \dots, (\mathbf{x}_n, y_n)$ with $\mathbf{x}_i \in A \subset \mathbb{R}^p$ and $y_i \in \mathbb{R}$. We call $A$ the predictor space, and partition it into regions $A_1, \dots, A_J$.

Consider a predictor $\hat{f}: \mathbb{R}^p \to \mathbb{R}$ given by $$\hat{f}(\mathbf{x}) = \sum_{j=1}^{J}c_j \cdot \mathbf{I}(\mathbf{x} \in A_j)\text{,}$$ where $\mathbf{I}$ denotes the indicator function.

Our aim is to minimize the loss function $$\sum_{i=1}^{n}[y_i - \hat{f}(\mathbf{x}_i)]^2\text{.}$$

Without proof, both Elements of Statistical Learning by Hastie, Tibshirani, and Freedman (2nd ed.), as well as Modern Multivariate Statistical Techniques by Izenman state that the optimal $c_j$ by the loss function above is $$\hat{c}_j = \dfrac{1}{n_j}\sum_{\{j: y_j \in A_j\}}y_j$$ i.e., take the average of all $y_i$ values in region $A_j$ (where $n_j$ is the number of $y_i$ in region $A_j$).

How is this proven? It is a standard result that for a general estimator $\hat{f}(\mathbf{X})$ of a single value $Y$, the optimal estimator under squared-error loss is $\hat{f}(\mathbf{X}) = \mathbb{E}[Y \mid \mathbf{X}]$. However, I'm not clever enough to see how this fact could be applicable.

Edit: Is this just as simple as differentiating with respect to $c_j$ and setting that equal to $0$? Funny how an obvious approach seems to make sense after asking the question...

Edit 2: Unfortunately, that approach doesn't lead to a very clean solution... I obtain \begin{equation*} \hat{c}_j = \dfrac{\sum_{i=1}^{n}y_i \cdot \mathbf{I}(\mathbf{x}_i \in A_j) - \sum_{k \neq j}\hat{c}_k n_k}{n_j}\text{.} \end{equation*} after setting the partial derivative with respect to $c_j$ equal to $0$ of the loss function.

Edit 3: I think I figured it out. I screwed up in mixing up the indices. The answer currently up is great, and I'm accepting it.


Intuitively, if you were to choose a constant as your prediction, the best choice would be $E[y|x]$ as you quoted. If you can divide the predictor space into $J$ regions (pre-defined) and have the freedom to choose $J$ constants, then region specific conditional averages would your best choice. This is like taking the mean of the samples in the leaves of a decision tree.

$$E[Y|\mathbf X]=\sum_{j=1}^J \mathbb P(\mathbf X \in A_j)\mathbb E[Y|\mathbf X, \mathbf X\in A_j]=c_m$$ because only one of the terms in this sum is non-zero and that is the region of $\mathbf X$, say $m$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.