Notebook12_LinerRegNotes.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Notes: Solving the linear regression problem\n",
    "\n",
    "In the linear regression problem, you have a data matrix, $X$, and a response $y$, you want to find model parameters $\\theta$ that make $y \\approx X \\theta$. These notes sketch one method for solving this problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Notation\n",
    "\n",
    "Assume your data consists of $m$ observations and $n+1$ variables. One of these variables is the _response_ variable, $y$, which you want to predict from the other $n$ variables, $\\{x_0, \\ldots, x_{n-1}\\}$. You wish to fit a _linear model_ of the following form to these data,\n",
    "\n",
    "$$y_i \\approx x_{i,0} \\theta_0 + x_{i,1} \\theta_1 + \\cdots + x_{i,n-1} \\theta_{n-1} + \\theta_n,$$\n",
    "\n",
    "where $\\{\\theta_j | 0 \\leq j \\leq n\\}$ is the set of unknown coefficients. Your modeling task is to choose values for these coefficients that \"best fit\" the data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can arrange the observations into a tibble like this one:\n",
    "\n",
    "|     y      | x<sub>0</sub> | x<sub>1</sub> | $\\cdots$ | x<sub>n-1</sub> | x<sub>n</sub> |\n",
    "|:----------:|:-------------:|:-------------:|:--------:|:---------------:|:-------------:|\n",
    "|   $y_0$    |   $x_{0,1}$   |   $x_{0,2}$   | $\\cdots$ |   $x_{0,n-1}$   |      1.0      |\n",
    "|   $y_1$    |   $x_{1,1}$   |   $x_{1,2}$   | $\\cdots$ |   $x_{1,n-1}$   |      1.0      |\n",
    "|   $y_2$    |   $x_{2,1}$   |   $x_{2,2}$   | $\\cdots$ |   $x_{2,n-1}$   |      1.0      |\n",
    "|  $\\vdots$  |   $\\vdots$    |   $\\vdots$    | $\\vdots$ |    $\\vdots$     |      1.0      |\n",
    "|  $y_{m-1}$ |  $x_{m-1,1}$  |  $x_{m-1,2}$  | $\\cdots$ |  $x_{m-1,n-1}$  |      1.0      |\n",
    "\n",
    "This tibble includes an extra dummy variable, $x_n$, whose entries are all equal to 1.0. Treating each variable as a column vector, the modeling tasks is to find the vector $\\theta^T \\equiv (\\theta_0, \\theta_1, \\ldots, \\theta_{n})$ such that\n",
    "\n",
    "$$y \\approx X \\theta,$$\n",
    "\n",
    "where $y$ is the vector of responses and $X$ is the $m \\times (n+1)$ matrix whose columns are the corresponding vectors, $x_0$, $x_1$, $\\ldots$, $x_n$. The matrix $X$ composed this way from the predictors is sometimes referred to as the _(input) data matrix_."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So how should you choose $\\theta$? Suppose you are given $\\theta$. One way to measure its quality is to look at the difference between $y$ and the _(model) prediction_, $X \\theta$. A natural way to measure that difference is to use some vector norm, like the 2-norm (here, squared):\n",
    "\n",
    "$$ \\|X \\theta - y\\|_2^2 \\equiv \\|r\\|_2^2,$$\n",
    "\n",
    "where $r \\equiv X \\theta - y$ is the _residual error vector_ or just _residual_ for this model. Each element of $r$ is the residual for a given observation; thus, using the two-norm means each difference is squared, thereby \"penalizing\" larger differences more than smaller ones.\n",
    "\n",
    "> The additional squaring of $\\|r\\|_2$ could be interpreted similarly, though in reality it is chosen to simplify the math. In particular, recall (or convince yourself) that $\\|r\\|_2^2 = r^T r$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given this error measure, we can now formalize our mathematical goal as an optimization problem: compute the $\\theta$ that _minimizes_ this error:\n",
    "\n",
    "$$ \\theta_* = {\\arg\\min_\\theta} \\|X \\theta - y\\|_2^2. $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solving the optimization problem\n",
    "\n",
    "Recall from calculus that you can minimize (or maximize) a continuous function $f(x)$ in a single variable $x$ by computing its derivative $\\left.\\frac{df}{dx}\\right|_{x=x_*}$, setting it to zero, and then solving for $x_*$.\n",
    "\n",
    "> **Example.** Let $f(x) \\equiv a x^2 + b x + c$. Then its maximum or minimum occurs at\n",
    ">\n",
    "> $$\n",
    "    \\left. \\frac{df}{dx} \\right|_{x=x_*} = 2 a x_* + b = 0,\n",
    "  $$\n",
    ">\n",
    "> or when\n",
    "> \n",
    "> $$\n",
    "    x_* = -\\frac{b}{2 a}.\n",
    "  $$\n",
    ">\n",
    "> To show whether this value is a maximum, a minimum, or a saddle-point, you would look at the second derivative. But let's skip that detail for now."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the setting of multivariable calculus, the procedure is the same. Let $g(\\theta)$ be the (scalar) function to minimize or maximize, where $\\theta$ is a vector. For vectors, the analogue of the first-derivative is the _gradient_. We define the gradient of a scalar function $g$ with respect to the vector variable $\\theta$ to be the vector\n",
    "\n",
    "$$\n",
    "\\nabla_\\theta g(\\theta) \\equiv\n",
    "  \\left(\\begin{array}{c}\n",
    "    \\frac{\\partial g}{\\partial \\theta_0} \\\\\n",
    "    \\frac{\\partial g}{\\partial \\theta_1} \\\\\n",
    "    \\vdots \\\\\n",
    "    \\frac{\\partial g}{\\partial \\theta_{n-1}}\n",
    "  \\end{array}\\right),\n",
    "$$\n",
    "\n",
    "where $\\frac{\\partial g}{\\partial \\theta_i}$ is the partial derivative of $g$ with respect to $\\theta_i$. (To compute a partial derivative with respect to $\\theta_i$, take the ordinary derivative with respect to $\\theta_i$ while treating all other $\\theta_{j \\neq i}$ as constants.) The gradient produces a _vector_ of these partial derivatives.\n",
    "\n",
    "> **Example.** Let $\\theta \\equiv \\left(\\begin{array}{c} \\theta_0 \\\\ \\theta_1 \\end{array}\\right)$ and $g(\\theta) \\equiv \\|\\theta\\|_2^2$. That is,\n",
    ">\n",
    "> $$ g(\\theta) = \\|\\theta\\|_2^2 \\Longrightarrow g(\\theta_0, \\theta_1) = \\theta_0^2 + \\theta_1^2. $$\n",
    ">\n",
    "> Then,\n",
    ">\n",
    "> $$\n",
    "    \\nabla_\\theta\\, g(\\theta)\n",
    "      = \\left(\\begin{array}{c}\n",
    "          \\frac{\\partial g}{\\partial \\theta_0} \\\\\n",
    "          \\frac{\\partial g}{\\partial \\theta_1}\n",
    "        \\end{array}\\right)\n",
    "      = \\left(\\begin{array}{c}\n",
    "          \\frac{\\partial}{\\partial \\theta_0} (\\theta_0^2 + \\theta_1^2) \\\\\n",
    "          \\frac{\\partial}{\\partial \\theta_1} (\\theta_0^2 + \\theta_1^2)\n",
    "        \\end{array}\\right)\n",
    "      = \\left(\\begin{array}{c}\n",
    "          2 \\theta_0 \\\\\n",
    "          2 \\theta_1\n",
    "        \\end{array}\\right)\n",
    "      = 2 \\theta.\n",
    "  $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From the definition of the gradient, you should be able to verify the following identities. Below, take $v$ and $w$ to be vectors of length $n$ and $M$ to be an $n \\times n$ matrix.\n",
    "\n",
    "1. $\\nabla_v (v^T w) = w$.\n",
    "2. $\\nabla_v (v^T v) = 2v$. (That is, generalize the example above to an $n$-vector.)\n",
    "3. $\\nabla_v (v^T M v) = (M + M^T)v$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Computing the optimal parameters, $\\theta^*$.** Armed with the gradient, you are now ready to minimize $g(\\theta) \\equiv \\|X \\theta - y\\|_2^2$.\n",
    "\n",
    "In the same way that the derivative is zero at the minimum of a scalar function, the gradient will be zero at the minimum of $g(\\theta)$. So let's compute the gradient and set it to zero."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When\n",
    "\n",
    "$$\n",
    "  \\begin{eqnarray}\n",
    "    \\left. \\nabla_\\theta\\, g(\\theta) \\right|_{\\theta^*} = 0,\n",
    "  \\end{eqnarray}\n",
    "$$\n",
    "\n",
    "then\n",
    "\n",
    "$$\n",
    "\\begin{eqnarray}\n",
    "  \\nabla_{\\theta^*} \\|X\\theta^* - y\\|_2^2\n",
    "    & = & \\nabla_{\\theta^*} \\left( \\theta^{*T} X^T X \\theta^* - 2 \\theta^{*T} X^T y + y^T y \\right) \\\\\n",
    "    & = & 2 (X^T X \\theta^* - X^T y) \\\\\n",
    "    & = & 0.\n",
    "\\end{eqnarray}\n",
    "$$\n",
    "\n",
    "In other words, the $\\theta^*$ at the minimum is the solution of $X^T X \\theta^* = X^T y$. This system is known as the _normal equations_. If the data matrix $X$ has full rank, then this equation will have a solution.\n",
    "\n",
    "> Again, like the 1-D case, we've glossed over the fact that you need one more step to show that $\\theta^*$ minimizes the above equation."
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "celltoolbar": "Create Assignment",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}