Lecture 4: Nonparametric regression

Nonparametric regression

• Linear models are quite restrictive and one may ask how one can achieve more flexibility.

• In this lecture we will look at the nonparametric regression problem with squared loss \(L(y_1,y_2)=(y_1-y_2)^2\)

• We already know that the Bayes-rule is \(m^\ast(x)=\mathbb E[Y|X=x]\)

Nonparametric regression k-nearest-neighbour (knn)

Nonparametric regression k-nearest-neighbour (knn)

Nonparametric regression k-nearest-neighbour (knn)

• Note that this is slower than the “parametric” MSE of \(pn^{-1}\)
• In particular it now grows exponentially in \(p\)

Nonparametric regression k-nearest-neighbour (knn)

Nonparametric regression kernel smoother

• We have learned that the knn estimator can be written as \[\hat m^{knn}(x)= \frac 1 k w_i(x_i) Y_i,\]

• Note that \(w_i(x)\) is not smooth as a function of \(x\). This also makes the estimator not smooth. Given that we assume that \(m^\ast\) is smooth, this may not be desirable.

• An alternative are kernel smoothers.

Nonparametric regression kernel smoother

Nonparametric regression kernel smoother

Nonparametric regression Curse of dimensionality

• We have seen that under a Lipschitz condition, both kernel smoother and knn have an asymptotic mean squared error of order \(n^{-2/(2+p)}\).

• One can show that under the assumption that \(m^\ast\) is twice continuously differentiable, the rate for both methods can be improved to \[n^{-4/(4+p)}.\]

• But this rate is still exponentially decreasing in \(p\). Furthermore, it has been shown that no method can do better under the given assumptions.

Nonparametric regression Curse of dimensionality

Here an example:

Nonparametric regression Curse of dimensionality

• A new observation \(x_0\) will have very few or no observations in its neighborhood
  • This leads to high variance
  • and high bias when increasing the size of the neighborhood
• Under the model of the previous slide, the setting \(n=50,p=1\) has the same expected amount of observations in a neighbourhood as the setting \(n=7.5\times10^{110}, p=100\).

Nonparametric regression Curse of dimensionality

Nonparametric regression Splines

• We want to establish a framework to estimate additive regression functions.
• To this end, assume \(p=1\) until further notice.

Nonparametric regression Splines

Nonparametric regression Natural splines

• Splines (used for regression, see next slide) have high variance at the boundaries.
• Solution: Let the piecewise polynomial function have a lower degree at \((−\infty,x_1],[x_l,\infty)\).

• Note that natural splines have dimension \(l+1\) which is in particular independent of the order \(k\) (compare to dimension \(k+l+1\) for splines) .
• There is also a truncated power basis and a B-splines basis for natural splines

Nonparametric regression Linear regression with splines

• We still assume the one-dimensional case, \(p=1\).

• Instead of looking at observations \((X_i,Y_i)_{i=1,\dots,n}\) we can consider a natural splines basis and look at observations \((g_1(X_i), \dots, g_{l+1}(X_i), Y_i)_{i=1,\dots,n}.\)

• By doing so we are able to approximate any natural spline in \(x\) instead of just linear functions in \(x\), while still being in a linear regression framework, i.e., \[\hat \beta = {\arg \min }_\beta \sum_i (Y_i - { G_i^T}\beta )^2= (\mathbf G^T\mathbf G)^{-1}\mathbf G^T\mathbf Y\] where \(G_i^T=(g_1(X_i), \dots, g_{l+1}(X_i))\), the rows of \(\mathbf G\).

• Problem: How do we choose the number of knotpoints \(l\) and their position?

  • First thought: Cross validation. But that would be quite expensive to run.

Nonparametric regression Smoothing splines

• Let’s look at the following minimization problem: \[\hat m= \arg\min_{m} \sum_i (Y_i-m(X_i))^2+\lambda\int_a^b m''(x)^2\mathrm dx,\] where:
  • minimization runs over all twice times differentiable functions \(m\)
  • observations \(X_i\) are in \([a,b]\) for all \(i\)

Nonparametric regression Smoothing splines

Nonparametric regression Smoothing splines

Nonparametric regression Smoothing splines as generalized ridge regression

We can conclude the following:

• Let \(\mathbf G\) be the matrix with with rows \(G_i=(g_1(X_i), \dots, g_{n+1}(X_i))\).
  • \(\{g_j\}_{j=1,\dots,n+1}\) is a basis for natural cubic splines with knots \(X_1, \dots X_n\).
• Define

\[\hat \beta = \arg\min_{\beta} \sum_i (Y_i- G_i^T\beta)^2+\lambda\int_0^1 \left\{{\sum_j \beta_jg_j''}(x)\right\}^2\mathrm dx.\]

• Then, \[\sum_j \hat \beta_j g_j=\arg\min_{m} \sum_i (Y_i-m(X_i))^2+\lambda\int_0^1 m''(x)^2\mathrm dx.\]

Nonparametric regression Smoothing splines as generalized ridge regression

Smoothing splines can be seen as a special case of generalized ridge regression:

• Write \(\mathbf W_{ij}=\int_0^1g_i''(x)g_j''(x)\mathrm dx,\) then

\[\begin{aligned} &\arg\min_{\beta} \sum_i (Y_i- G_i^T\beta)^2+\lambda\int_0^1 \left\{{\sum_j \beta_jg_j''}(x)\right\}^2\mathrm dx\\= &\arg\min_{\beta} \sum_i (Y_i- G_i^T\beta)^2+\lambda \beta^T \mathbf W \beta. \end{aligned}\]

• Hence, \[\hat \beta= (\mathbf G^T\mathbf G+\lambda \mathbf W)^{-1}\mathbf G^T\mathbf Y.\]

Nonparametric regression Smoothing splines equivalence to kernel smoothing

• It can be shown the smoothing splines are asymptotically equivalent to kernel smoothers with varying bandwidth and a specific choice of kernel, see Silverman (1984) or Wang, Du, and Shen (2013) for a more recent contribution.

• In general, smoothing splines are more practical since they can be efficiently calculated while kernel smoothers are much easier to analyze theoretically.

Nonparametric regression Additive models

• We have seen that fully nonparametric methods suffer from the curse of dimensionality:

  • the optimal rate of convergence for twice continuously differentiable functions is \(n^{-4/(4+p)}\).

• One solution is to restrict oneself to the class of additive functions \[\mathcal G=\{m| m(x)=m_1(x_1)+\cdots +m_p(x_p)\}\]

• Stone (1985) showed that the components \(m_k\), if twice continuously differentiable, can be estimated with one-dimensional rate of \(n^{-4/4+1}\)

• The components \(m_j\) are usually estimated via the so called backfitting algorithm (Hastie and Tibshirani 1990).

Nonparametric regression Additive models: backfitting

Backffitting comprises the following two steps:

• Note that Smooth is a one-dimensional regression problem.
• In practice Smooth is most often a smoothing spline.
  • It has been shown backfitting via smoothing splines achieve a rate of order \(p n^{-4/4+1}\).
• Problem: Additive methods are still not optimal in the case of sparsity (i.e. some features being not relevant) and interactions between features.