# 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.

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