# Underlying similarities between Knn and Least squares

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)

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

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.

## 1 Answer

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

• +1 for great details! Mar 26 '20 at 13:07
• +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 Mar 26 '20 at 16:04
• @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. Mar 26 '20 at 21:00