{ "cells": [ { "cell_type": "raw", "metadata": {}, "source": [ "---\n", "title: 'Course introduction'\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": [ "## Syllabus\n", "\n", "- **Videos:** Every lecture will be recorded by SCPD\n", "\n", "- **Email policy:** Please use the Piazza site for most questions. For administrative issues that only concern you, email the course staff mailing list: \n", "[stats202-aut2021-staff@lists.stanford.edu](mailto:stats202-aut2021-staff@lists.stanford.edu)\n", "\n", "- **Website:** [stats202.stanford.edu](http://stats202.stanford.edu)\n", "\n", "- If you are auditing the class (not registered on Axess), email us your SUNet ID in order to gain access to the lectures and homework on canvas." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Prediction challenges\n", "\n", "### The MNIST dataset is a library of handwritten digits \n", "\n", "\n", "```{figure} figs/mnist.jpg\n", "---\n", "height: 300px\n", "name: mnist\n", "---\n", "MNIST dataset\n", "```\n", "\n", "- In a prediction challenge, you are given a training set of images of handwritten digits,\n", "which are labeled from 0 to 9.\n", "\n", "- You are also given a test set of handwritten digits, which are not identified.\n", "\n", "- Your job is to assign a digit to each image in the test set." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### The Netflix prize\n", "\n", "Netflix popularized prediction challenges by organizing an open, blind\n", "contest to improve its recommendation system.\n", "\n", "```{figure} figs/tikz/netflix1.png\n", "---\n", "height: 500px\n", "name: netflix1\n", "---\n", "Netflix 1\n", "```\n", "\n", "\n", "### The Netflix prize\n", "\n", "Netflix popularized prediction challenges by organizing an open, blind\n", "contest to improve its recommendation system.\n", "\n", "```{figure} figs/tikz/netflix2.png\n", "---\n", "height: 500px\n", "name: netflix2\n", "---\n", "Netflix 2\n", "```" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### The Netflix prize\n", "\n", "Netflix popularized prediction challenges by organizing an open, blind\n", "contest to improve its recommendation system.\n", "\n", "```{figure} figs/tikz/netflix3.png\n", "---\n", "height: 500px\n", "name: netflix3\n", "---\n", "Netflix 3\n", "```\n", "\n", "**The prize was $1 million.**\n", "\n", "*(Cue Dr. Evil jokes if anyone knows Austin Powers movies...)*\n", "\n", "\n", "## Unsupervised learning\n", "\n", "In **unsupervised learning** we start with a data matrix:\n", "\n", "```{figure} figs/tikz/unsupervised.png\n", "---\n", "height: 500px\n", "name: unsupervised\n", "---\n", "Unsupervised learning setup\n", "```\n", "\n", "- Quantitative, eg. weight, height, number of children, ...;\n", "\n", "- Qualitative, eg. college major, profession, gender, ...;\n", "\n", "### Goals of unsupervised learning\n", "\n", "In **unsupervised learning** we start with a data matrix:\n", "\n", "Our goal is to:\n", "\n", "1. Find meaningful relationships between the variables or units: Correlation analysis.\n", "2. Find interpretable low-dimensional representations of the data which make it easy to visualize the variables and units. PCA, ICA, isomap, locally linear embeddings, etc.\n", "3. Find meaningful groupings of the data. Clustering.\n", "\n", "Unsupervised learning is sometimes referred to in Statistics as **exploratory data analysis**. \n", "\n", "## Supervised learning\n", "\n", "### Setup\n", "\n", "In **supervised learning**, there are *input* variables, and *output* variables:\n", "\n", "
\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Classification problems\n", "\n", "In **supervised learning**, there are *input* variables, and *output* variables:\n", "\n", "
\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Goals of supervised learning\n", "\n", "In **supervised learning**, there are *input* variables, and *output* variables:\n", "\n", "- If $X$ is the vector of inputs for a particular sample. The output variable is modeled by:\n", "$$Y = f(X) + \\underbrace{ \\varepsilon}_{\\text{Random error}}$$\n", "\n", "- Our goal is to learn the function $f$, using a set of training samples $(x_1,y_1)\\dots(x_n,y_n)$\n", "\n", "### Regression model\n", "\n", "$$Y = f(X) + \\varepsilon$$\n", "\n", "#### Motivations\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "
**Prediction:** Useful when the input variable is readily available, but the output variable is not.Example: Predict stock prices next month using data from last year.
\n", "**Inference:** A model for $f$ can help us understand the structure\n", "of the data --- which variables influence the output, and which don't?\n", "What is the relationship between each variable and the output,\n", "e.g. linear, non-linear? Example: What is\n", "the influence of genetic variations on the incidence of heart\n", "disease.
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Kaggle: data analysis competitions\n", "\n", "#### Business model\n", "\n", "1. Organize prediction competitions hosted online.\n", "\n", "2. Offer companies consulting services from Kaggle ``stars''.\n", "\n", "**Kaggle-in-class is a competition engine offered to degree-granting institutions for free. Stats 202 was the first class to use it (or so I'm told)!**" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Kaggle: data analysis competitions\n", "\n", "#### A sample Kaggle challenge\n", "\n", "Help out San Francisco's foremost Baroque ensemble bring in subscriptions!\n", "\n", "1. Using Philharmonia's database of subscriptions and single ticket sales, including information about concerts, and patrons, predict who will subscribe for the 2021-2022 season.\n", "\n", "2. Create an interactive visualization of Philharmonia's database using the R package Shiny.\n", "\n", "**This year's competition coming soon!**" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Parametric and nonparametric methods\n", "\n", "There are (broadly) two kinds of supervised learning method:\n", "\n", "1. **Parametric methods:** We assume that $f$ takes a specific form. For example, a linear form:\n", "$$f(X) = X_1\\beta_1+\\dots +X_p\\beta_p$$\n", "with parameters $\\beta_1,\\dots,\\beta_p$. Using the training data, we try to *fit* the parameters. \n", "\n", "2. **Non-parametric methods:** We don't make any assumptions on the form of $f$, but we restrict how *wiggly* or *rough* the function can be." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Parametric vs. nonparametric prediction\n", "\n", "
\n", "\n", "\n", "\n", "\n", "\n", "\n", "
\n", "
\n", "\n", "1. Parametric methods have a limit of fit quality. Non-parametric methods can keep improving as we add more data to fit.\n", "\n", "2. Parametric methods are often simpler to interpret." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Prediction error\n", "\n", "- Our goal in supervised learning is to minimize the prediction error\n", "\n", "- For regression models, this is typically the **Mean Squared Error (MSE)**:\n", "\n", "$$MSE(\\hat f) = E(y_0 - \\hat f(x_0))^2.$$\n", "\n", "- Unfortunately, this quantity cannot be computed, because we don't know the joint distribution of $(x_0,y_0)$.\n", "\n", "- We can compute a sample average using the training data; this is known as the training MSE:\n", "\n", "$$MSE_\\text{training}(\\hat f) = \\frac{1}{n}\\sum_{i=1}^n (y_i-\\hat f(x_i))^2.$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Key quantities\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "
**Training data**$(x_1,y_1),(x_2,y_2)\\dots (x_n,y_n)$
**Predicted function**$\\hat f$, a function of (i.e. learned on) training data
**Future data**$(x_0,y_0)$ having some distribution (usually related to distribution of\n", "training data)
**Prediction error (MSE) **$MSE(\\hat f) = E(y_0 - \\hat f(x_0))^2.$
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Prediction error\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "
**Training data**$(x_1,y_1),(x_2,y_2)\\dots (x_n,y_n)$
**Predicted function**$\\hat f$, a function of (i.e. learned on) training data
**Future data**$(x_0,y_0)$ having some distribution (usually related to distribution of\n", "training data)
**Prediction error (MSE) **$MSE(\\hat f) = E(y_0 - \\hat f(x_0))^2.$
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Prediction error\n", "\n", "1. The main challenge of statistical learning is that **a low training MSE does not imply a low MSE.**\n", "\n", "2. If we have test data $\\{(x'_i,y'_i);i=1,\\dots,m\\}$ which were not used to fit the model, a better measure of quality for $\\hat f$ is the test MSE:\n", "\n", "$$MSE_\\text{test}(\\hat f) = \\frac{1}{m}\\sum_{i=1}^m (y'_i-\\hat f(x'_i))^2.$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Prediction error\n", "\n", "
\n", "\n", "
\n", "\n", "The circles are simulated data from the black curve $f$ by adding Gaussian noise. In this artificial example, we *know* what $f$ is.\n", "\n", "Three estimates $\\hat f$ are shown: Linear regression, Splines (very smooth),\n", "Splines (quite rough)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Prediction error\n", "\n", "
\n", "\n", "
\n", "\n", "Red line: Test MSE, Gray line: Training MSE." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Prediction error\n", "\n", "
\n", "\n", "
\n", "\n", "The function $f$ is now almost linear." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Prediction error\n", "\n", "
\n", "\n", "
\n", "\n", "When the noise $\\varepsilon$ has small variance relative to $f$, the third method does well." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### The bias variance decomposition\n", "\n", "- Let $x_0$ be a fixed test point, $y_0 = f(x_0) + \\varepsilon_0$, and $\\hat f$ be estimated from $n$ training samples $(x_1,y_1)\\dots(x_n,y_n)$. \n", "\n", "- Let $E$ denote the expectation over $y_0$ and the training outputs $(y_1,\\dots,y_n)$. Then, the Mean Squared Error at $x_0$ can be decomposed:\n", "\n", "$$MSE(x_0) = E( y_0 - \\hat f(x_0))^2 = \\text{Var}(\\hat f(x_0)) + [\\text{Bias}(\\hat f(x_0))]^2 + \\text{Var}(\\varepsilon_0)$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### The bias variance decomposition\n", "\n", "$$MSE(x_0) = E( y_0 - \\hat f(x_0))^2 = \\text{Var}(\\hat f(x_0)) + [\\text{Bias}(\\hat f(x_0))]^2 + \\text{Var}(\\varepsilon_0)$$\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "
**Variance:**$\\text{Var}(\\hat f(x_0))$The variance of the estimate of $Y$: $E[\\hat f(x_0) - E(\\hat f(x_0))]^2$
**Bias:** $[\\text{Bias}(\\hat f(x_0))]^2$This measures how much the estimate of $\\hat f$ at $x_0$ changes when we sample\n", "and average over new training data.
**Irreducible error:**\n", "$\\text{Var}(\\varepsilon_0)$This is how much of the response is not predictable by any method.
\n", "\n", "- Each fitting method has its own variance and bias. No method can improve on irreducible error.\n", "\n", "- A good method has small **variance + squared bias**." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Prediction error\n", "\n", "
\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "
Sample #1Sample #2Sample #3Sample #4
\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "
All fitsBias (estimated)
\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Implications of bias variance decomposition\n", "\n", "$$MSE(x_0) = E(y_0 - \\hat f(x_0))^2 = \\text{Var}(\\hat f(x_0)) + [\\text{Bias}(\\hat f(x_0))]^2 + \\text{Var}(\\varepsilon).$$\n", "\n", "1. The MSE is always positive.\n", "\n", "2. Each element on the right hand side is always positive.\n", "\n", "3. Therefore, typically when we decrease the bias beyond some point, we increase the variance, and vice-versa.\n", "\n", "More flexibility $\\iff$ Higher variance $\\iff$ Lower bias." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Implications of bias variance decomposition\n", "\n", "
\n", "\n", "
\n", "\n", "$\\;\\;\\;\\;\\;$ Squiggly $f$, high noise $\\;\\;\\;\\;\\;$ Linear $f$, high noise $\\;\\;\\;\\;$ Squiggly $f$, low noise" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Classification problems\n", "\n", "\n", "\n", "\n", "- In a classification setting, the output takes values in a discrete set.\n", "\n", "- For example, if we are predicting the brand of a car based on a number of variables, the function $f$ takes values in the set $\\{\\text{Ford, Toyota, Mercedes-Benz}, \\dots\\}$. \n", "\n", "- Model is no longer\n", "$$\\cancel{Y=f(X)+\\epsilon}$$ \n", "\n", "- \n", "We will use slightly different notation:\n", "$$\n", "\\begin{aligned}\n", "P(X,Y): & \\text{ joint distribution of }(X,Y),\\\\\n", "P(Y\\mid X): &\\text{ conditional distribution of }X\\text{ given }Y,\\\\\n", "\\hat y_i: &\\text{ prediction for }x_i.\n", "\\end{aligned}\n", "$$\n", "\n", "- For classification we are interested in learning $P(Y\\mid X)$.\n", "\n", "- Connection between the classification and regression: both try to learn $E(Y\\mid X)$ but the type of $Y$ is different.\n", "\n", "### Loss function for classification\n", "\n", "- There are many ways to measure the error of a classification prediction. One of the most common is the 0-1 loss:\n", "\n", "$$E(\\mathbf{1}(y_0 \\neq \\hat y_0) )$$\n", "\n", "- Like the MSE, this quantity can be estimated from training or test data by taking a sample average:\n", "\n", "$$\\frac{1}{n}\\sum_{i=1}^n\\mathbf{1}(y_i \\neq \\hat y_i)$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Bayes classifier\n", "\n", "
\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Bayes classifier\n", "\n", "- The Bayes classifier assigns:\n", "$$\\hat y_i = \\text{argmax}_j \\;\\; P(Y=j \\mid X= x_i)$$\n", "\n", "- It can be shown that this is the best classifier under the 0-1 loss.\n", "\n", "- In practice, we never know the joint probability $P$. However, we may assume that it exists.\n", "\n", "- Many classification methods approximate $P(Y=j \\mid X=x_i)$ with $\\hat{P}(Y=j \\mid X=x_i)$\n", "and predict using this approximate Bayes classifier." ] } ], "metadata": { "celltoolbar": "Slideshow", "jupytext": { "cell_metadata_filter": "all,-slideshow", "formats": "ipynb,Rmd,md:myst" }, "kernelspec": { "display_name": "R", "language": "R", "name": "ir" }, "language_info": { "codemirror_mode": "r", "file_extension": ".r", "mimetype": "text/x-r-source", "name": "R", "pygments_lexer": "r", "version": "3.6.1" } }, "nbformat": 4, "nbformat_minor": 2 }