It is mentioned in the ESL book Page 19, that Knn and Least squares end up approximating conditional expectation by averages.

To explain the statements in detail, the book mentions 3 equations.

  1. The one below is the matrix notation of the Least squares equation, after derivating w.r.t Beta. (eq: 2.6)

enter image description here

  1. The second equation is obtained after assuming enter image description here. This is then subsituted in the equation enter image description here and then differentiating, we get the below equation (eq: 2.16)

enter image description here

For the above equation the author says, "Note we have not conditioned on X; rather we have used our knowledge of the functional relationship to pool over values of X. The least squares solution (2.6) amounts to replacing the expectation in (2.16) by averages over the training data. So both k-nearest neighbors and Least squares end up approximating conditional expectations by averages."

After going through this, I am unable to intuitively understand how the similarities hold between them. Can somebody please explain.


In the second one, $X$ depicts a random vector (a random input) of size $p\times 1$, and in the first one it (denoting it as $\mathbf{X}$ in bold) depicts a collection and is of size $n\times p$, where $n$ is the number of samples. Since each row in (1) represents a data sample, we can write it as: $$\mathbf{X}=\begin{bmatrix} \mathbf{x}_1^T\\\vdots\\ \mathbf{x}_n^T\end{bmatrix}$$

which makes $\mathbf{X}^T\mathbf{X}$ in (1) $p\times p$, just as $XX^T$ in (2). Using this we can write $\mathbf{X}^T\mathbf{X}$ as below:$$\mathbf{X}^T\mathbf{X}=\sum_{i=1}^n \mathbf{x}_i \mathbf{x}_i^T\approx nE[XX^T]$$

And, $Y$ is a scalar random variable, so, $E[XY]$ is a valid expression of size $p\times 1$. In (1), we have $\mathbf{X}^T\mathbf{y}$, which can be expanded as: $$\mathbf{X}^T\mathbf{y}=\begin{bmatrix} \mathbf{x}_1&\dots & \mathbf{x}_n\end{bmatrix}\begin{bmatrix}y_1\\\vdots\\y_n\end{bmatrix}=\sum_{i=1}^n \mathbf{x_i}y_i\approx nE[XY]$$

As $n$ goes large these approximations become closer. So, imagine we replace the expressions in (1) with their expected value equivalents: $$\hat\beta\rightarrow (nE[XX^T])^{-1}nE[XY]=\frac{1}{n}(E[XX^T])^{-1}nE[XY]=(E[XX^T])^{-1}E[XY]=\beta$$

  • 2
    $\begingroup$ +1 for great details! $\endgroup$
    – Haitao Du
    Mar 26 '20 at 13:07
  • $\begingroup$ +1 (is less) for detailed explanation. Can you also please indicate the part/notation/area in these equations (if there is any) where it shows the "approximation by Global Linear function" in Linear regression, vs "approximation by Locally constant function" in Knn. Perhaps the removal of intercept for f(x) ? An intuitive answer would be really helpful. Thanks $\endgroup$
    – Salih
    Mar 26 '20 at 16:04
  • $\begingroup$ @Salih thanks and you're welcome. The equations I wrote are just matrix properties in the linalg & prob literature. So, there is no direct relation to Linear regression or KNN. $\endgroup$
    – gunes
    Mar 26 '20 at 21:00

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.