{ "cells": [ { "cell_type": "raw", "metadata": {}, "source": [ "---\n", "title: 'Nonlinear methods'\n", "author: \"Sergio Bacallado, Jonathan Taylor\"\n", "subtitle: \"[web.stanford.edu/class/stats202](http://web.stanford.edu/class/stats202)\"\n", "date: \"Autumn 2020\"\n", "output:\n", " slidy_presentation:\n", " css: styles.css\n", "---" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Non-linear regression\n", "\n", "
\n", "\n", "
\n", "\n", "**Problem:** How do we model a non-linear relationship?\n", "\n", "- **Left:** Regression of `wage` onto `age`.\n", "\n", "- **Right:** Logistic regression for classes `wage>250` and `wage<250`\n", "\n", "## Basis functions\n", "\n", "**Strategy:**\n", "\n", "\n", "\n", "## Piecewise constant\n", "\n", "
\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Piecewise polynomials\n", "\n", "
\n", "\n", "
\n", "\n", "## Cubic splines\n", "\n", "\n", "\n", "## Natural cubic splines\n", "\n", "
\n", "\n", "
\n", "\n", "- Spline which is linear instead of cubic for $X<\\xi_1$, $X>\\xi_K$.\n", "\n", "- The predictions are more stable for extreme values of $X$.\n", "\n", "## Choosing the number and locations of knots\n", "\n", "
\n", "\n", "
\n", "\n", "- The locations of the knots are typically quantiles of $X$.\n", "\n", "- The number of knots, $K$, is chosen by cross validation:\n", "\n", "## Natural cubic splines vs. polynomial regression\n", "\n", "
\n", "\n", "
\n", "\n", "- Splines can fit complex functions with few parameters.\n", "\n", "- Polynomials require high degree terms to be flexible.\n", "\n", "- High-degree polynomials can be unstable at the edges.\n", "\n", "## Smoothing splines\n", "\n", "Find the function $f$ which minimizes\n", "\n", "$$\\color{Blue}{\\sum_{i=1}^n (y_i - f(x_i))^2} + \\color{Red}{ \\lambda \\int f''(x)^2 dx}$$\n", "\n", "- The RSS when using $f$ to predict.\n", "\n", "- A penalty for the roughness of the function.\n", "\n", "### Facts\n", "\n", "- The minimizer $\\hat f$ is a natural cubic spline, with knots at each sample point $x_1,\\dots,x_n$.\n", "\n", "- Obtaining $\\hat f$ is similar to a Ridge regression.\n", "\n", "## Advanced: deriving a smoothing spline\n", "\n", "
    \n", "
  1. Show that if you fix the values $f(x_1),\\dots,f(x_2)$, the roughness \n", "$$\\int f''(x)^2 dx$$\n", "is minimized by a natural cubic spline.\n", "
  2. Deduce that the solution to the smoothing spline problem is a natural cubic spline, which can be written in terms of its basis functions.\n", "$$f(x) = \\beta_0 + \\beta_1 f_1(x) + \\dots \\beta_{n+3} f_{n+3}(x)$$\n", "
  3. Letting $\\mathbf N$ be a matrix with $\\mathbf N(i,j) = f_j(x_i)$, we can write the objective function:\n", "$$ (y - \\mathbf N\\beta)^T(y - \\mathbf N\\beta) + \\lambda \\beta^T \\Omega_{\\mathbf N}\\beta, $$\n", "where $\\Omega_{\\mathbf N}(i,j) = \\int N_i''(t) N_j''(t) dt$.\n", "
\n", "\n", "## Advanced: deriving a smoothing spline" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
    \n", "
  1. By simple calculus, the coefficients $\\hat \\beta$ which minimize\n", "$$ (y - \\mathbf N\\beta)^T(y - \\mathbf N\\beta) + \\lambda \\beta^T \\Omega_{\\mathbf N}\\beta, $$\n", "are $\\hat \\beta = (\\mathbf N^T \\mathbf N + \\lambda \\Omega_{\\mathbf N})^{-1} \\mathbf N^T y$.\n", "
  2. Note that the predicted values are a linear function of the observed values:\n", "$$\\hat y = \\underbrace{\\mathbf N (\\mathbf N^T \\mathbf N + \\lambda \\Omega_{\\mathbf N})^{-1} \\mathbf N^T}_{\\mathbf S_\\lambda} y$$\n", "
  3. The **degrees of freedom** for a smoothing spline are:\n", "$$\\text{Trace}(\\mathbf S_\\lambda)= \\mathbf S_\\lambda(1,1) + \\mathbf S_\\lambda(2,2) + \\cdots + \\mathbf S_\\lambda(n,n) $$\n", "
\n", "\n", "## Natural cubic splines vs. Smoothing splines\n", "\n", "
\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "
**Natural cubic splines****Smoothing splines**
\n", "
    \n", "
  • Fix the locations of $K$ knots at quantiles of $X$.\n", "
  • Number of knots $KFind the natural cubic spline $\\hat f$ which minimizes the RSS:\n", "$$\\sum_{i=1}^n (y_i - f(x_i) )^2$$\n", "
  • Choose $K$ by cross validation.\n", "
\n", "		\n", "
    \n", "
  • Put $n$ knots at $x_1,\\dots,x_n$.\n", "
  • We could find a cubic spline which makes the RSS $=0$ $\\longrightarrow$ {\\color{Red}Overfitting!}\n", "
  • Instead, we obtain the fitted values $\\hat f(x_1),\\dots,\\hat f(x_n)$ through an algorithm similar to Ridge regression.\n", "
  • The function $\\hat f$ is the only natural cubic spline that has these fitted values.\n", "
\n", "
\n", "
\n", "\n", "## Choosing the regularization parameter $\\lambda$\n", "\n", "- We typically choose $\\lambda$ through cross validation. \n", "\n", "- Fortunately, we can solve the problem for any $\\lambda$ with the same complexity of diagonalizing an $n\\times n$ matrix.\n", "\n", "- There is a shortcut for LOOCV:\n", "$$\n", "\\begin{aligned}\n", "RSS_\\text{loocv}(\\lambda) &= \\sum_{i=1}^n (y_i - \\hat f_\\lambda^{(-i)}(x_i))^2 \\\\\n", "&= \\sum_{i=1}^n \\left[\\frac{y_i-\\hat f_\\lambda(x_i)}{1-\\mathbf S_\\lambda(i,i)}\\right]^2\n", "\\end{aligned}\n", "$$\n", "\n", "## Choosing the regularization parameter $\\lambda$\n", "\n", "
\n", "\n", "
\n", "\n", "# Local linear regression\n", "\n", "
\n", "\n", "
\n", "\n", "- Sample points nearer $x$ are weighted higher in corresponding regression.\n", "\n", "## Algorithm\n", "\n", "To predict the regression function $f$ at an input $x$:\n", "
    \n", "
  1. Assign a weight $K_i(x)$ to the training point $x_i$, such that:\n", "\n", "
  2. Perform a **weighted least squares** regression; i.e. find $(\\beta_0,\\beta_1)$ which minimize\n", "$$\\hat{\\beta}(x) = \\text{argmin}_{(\\beta_0, \\beta_1)} \\sum_{i=i}^n K_i(x) (y_i - \\beta_0 -\\beta_1 x_i)^2.$$\n", "
  3. Predict $\\hat f(x) = \\hat \\beta_0(x) + \\hat \\beta_1(x) x$. \n", "
\n", "\n", "## Generalized nearest neighbors\n", "\n", "
    \n", "
  1. Set $K_i(x)=1$ if $x_i$ is one of $x$'s $k$ nearest neighbors.\n", "
  2. Perform a ``regression'' with only an intercept; i.e. find $\\beta_0$ which minimizes\n", "$$\\hat{\\beta}_0(x) = \\text{argmin}_{\\beta_0} \\sum_{i=i}^n K_i(x)(y_i - \\beta_0)^2.$$\n", "
  3. Predict $\\hat f(x) = \\hat \\beta_0(x)$.\n", "
  4. Common choice that is smoother than nearest neighbors\n", "$$K_i(x) = \\exp(-\\|x-x_i\\|^2/2\\lambda)$$\n", "
\n", "\n", "## Local linear regression\n", "\n", "
\n", "\n", "
\n", "\n", "- The *span* $k/n$, is chosen by cross-validation.\n", "\n", "# Generalized Additive Models (GAMs)\n", "\n", "- Extension of non-linear models to multiple predictors:\n", "\n", "$$\\;\\;\\mathtt{wage} = \\beta_0 + \\beta_1\\times \\mathtt{year} + \\beta_2\\times \\mathtt{age} + \\beta_3 \\times\\mathtt{education} +\\epsilon$$\n", "\n", "$$\\longrightarrow \\;\\;\\mathtt{wage} = \\beta_0 + f_1(\\mathtt{year}) + f_2(\\mathtt{age}) + f_3(\\mathtt{education}) +\\epsilon$$\n", "\n", "- The functions $f_1,\\dots,f_p$ can be polynomials, natural splines, smoothing splines, local regressions...\n", "\n", "## Fitting a GAM\n", "\n", "$$\\mathtt{wage} = \\beta_0 + f_1(\\mathtt{year}) + f_2(\\mathtt{age}) + f_3(\\mathtt{education}) +\\epsilon$$\n", "\n", "\n", "\n", "## Fitting a GAM\n", "\n", "\n", "\n", "## Backfitting: coordinate descent\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Backfitting: coordinate descent and LASSO\n", "\n", "\n", "\n", "## Backfitting: GAM\n", "\n", "\n", "\n", "## Properties\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Example: Regression for `Wage`\n", "\n", "
\n", "\n", "
\n", "\n", "- `year`: natural spline with df=4.\n", "\n", "- `age`: natural spline with df=5.\n", "\n", "- `education`: factor.\n", "\n", "## Example: Regression for `Wage`\n", "\n", "
\n", "\n", "
\n", "\n", "- `year`: smoothing spline with df=4.\n", "\n", "- `age`: smoothing spline with df=5.\n", "\n", "- `education`: step function\n", "\n", "## Classification\n", "\n", "We can model the log-odds in a classification problem using a GAM:\n", "\n", "$$\\log \\frac{P(Y=1\\mid X)}{P(Y=0\\mid X)} = \\beta_0 + f_1(X_1) + \\dots + f_p(X_p).$$\n", "\n", "Again fit by backfitting ...\n", "\n", "## Backfitting: GAM with logistic loss\n", "\n", "\n", "\n", "## Example: Classification for `Wage>250`\n", "\n", "
\n", "\n", "
\n", "\n", "- `year`: linear\n", "\n", "- `age`: smoothing spline with df=5\n", "\n", "- `education`: step function\n", "\n", "## Example: Classification for `Wage>250`\n", "\n", "
\n", "\n", "
\n", "\n", "- Same model excluding cases `education == \"