local polynomial regression

kernel regression, knn methods, and partitions and trees can be generated by minimizing the following sum:

$$\sum _{i=1}^n{w}_i(x)(c-Y_i{)}^2,$$

as a function of $x$. This is a simple optimization problem which yields the solution

$$c^{\ast }(x)=\frac{{\sum }_i{w}_i(x)Y_i}{{\sum }_i{w}_i(x)}.$$

Thus, we can see that KNN regression arises from taking $w_i(x)=1[x\in N_k(X_i)]$ ($N_k(x)$ are the k-nearest neighbours of $x$). More generally, partition-based regressors follow from taking $w_i(x)=1[R(x)=R(x_i)]$, where $R(x)$ is the region of the feature space to which $x$ belongs. Finally, kernel regression follows from taking $w_i(x)=K(||x-X_i||/h)$.

We note that above equation is solved for at test time, i.e., for each new test point $x$. In that sense, they are “local”: The (weight of) the set of samples recruited to take part in the optimization depends on the locality of the test point $x$.

Local polynomial regression generalizes the above by replacing $c$ with a polynomial. The objective becomes, for dimension $d=1$,

$$\sum _{i=1}^n{w}_i(x)(Y_i-\sum _{j=0}^r{\beta }_j{x}^j{)}^2.$$

Note we’re minimizing over ${\beta }_0,\dots ,{\beta }_r$, which will be functions of $x$. If $r=1$ this is referred to as local linear regression. By writing it out in matrix form, it’s not hard to see that solution is

$$\beta (x)=(A^{T}WA{)}^{-1}{W}^{T}Ay,$$

where $A$ is the matrix with $i$-th row equal to $a(x_i)$ and $W$ is the diagonal matrix whose $i$-th diagonal entry is $w_i(x)$. The predictor is then $\hat{m}(x)=(1,x,\dots ,x^r{)}^T\beta (x)$. The solution is very reminiscent of weighted least squares.