{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Simple Linear Regression example\n",
    "Let's explore implementation of simple linear regression!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "233\n"
     ]
    }
   ],
   "source": [
    "# Assuming we’ve determined such an alpha and beta, then we make predictions simply with:\n",
    "def predict(alpha: float, beta: float, x_i: float) -> float:\n",
    "    return beta * x_i + alpha\n",
    "\n",
    "print(predict(33,20, 10))     # example of making prediction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### How should we choose alpha and beta? \n",
    "Minimize the error between predicted output and actual output y_i for each input x_i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def error(alpha: float, beta: float, x_i: float, y_i: float) -> float:\n",
    "    \"\"\"\n",
    "    The error from predicting beta * x_i + alpha\n",
    "    when the actual value is y_i\n",
    "    \"\"\"\n",
    "    return predict(alpha, beta, x_i) - y_i"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The total error\n",
    "We want to check total errors over the entire dataset. Here we add up the squared errors. The least squares solution is to choose the alpha and beta that make sum_of_sqerrors as small as possible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "Vector = List[float]\n",
    "def sum_of_sqerrors(alpha: float, beta: float, x: Vector, y: Vector) -> float:\n",
    "    return sum(error(alpha, beta, x_i, y_i) ** 2\n",
    "               for x_i, y_i in zip(x, y))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Error minimizing alpha and beta\n",
    "Use the calculous (or tedious algebra).\n",
    "\n",
    "The choice of alpha simply says that when we see the average value of the independent variable x, we predict the average value of the dependent variable y.\n",
    "\n",
    "The choice of beta means that when the input value increases by standard_deviation(x), the prediction then increases by correlation(x, y) * standard_deviation(y). In the case where x and y are perfectly correlated, a one-standard-deviation increase in x results in a one-standard-deviation-of-y increase in the prediction. When they’re perfectly anticorrelated, the increase in x results in a decrease in the prediction. And when the correlation is 0, beta is 0, which means that changes in x don’t affect the prediction at all."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from typing import Tuple\n",
    "\n",
    "import math\n",
    "\n",
    "def dot(v: Vector, w: Vector) -> float:\n",
    "    \"\"\"Computes v_1 * w_1 + ... + v_n * w_n\"\"\"\n",
    "    assert len(v) == len(w), \"vectors must be same length\"\n",
    "\n",
    "    return sum(v_i * w_i for v_i, w_i in zip(v, w))\n",
    "\n",
    "def sum_of_squares(v: Vector) -> float:\n",
    "    \"\"\"Returns v_1 * v_1 + ... + v_n * v_n\"\"\"\n",
    "    return dot(v, v)\n",
    "\n",
    "def mean(xs: List[float]) -> float:\n",
    "    return sum(xs) / len(xs)\n",
    "\n",
    "def de_mean(xs: List[float]) -> List[float]:\n",
    "    \"\"\"Translate xs by subtracting its mean (so the result has mean 0)\"\"\"\n",
    "    x_bar = mean(xs)\n",
    "    return [x - x_bar for x in xs]\n",
    "\n",
    "def variance(xs: List[float]) -> float:\n",
    "    \"\"\"Almost the average squared deviation from the mean\"\"\"\n",
    "    assert len(xs) >= 2, \"variance requires at least two elements\"\n",
    "\n",
    "    n = len(xs)\n",
    "    deviations = de_mean(xs)\n",
    "    return sum_of_squares(deviations) / (n - 1)\n",
    "\n",
    "def standard_deviation(xs: List[float]) -> float:\n",
    "    \"\"\"The standard deviation is the square root of the variance\"\"\"\n",
    "    return math.sqrt(variance(xs))\n",
    "\n",
    "def covariance(xs: List[float], ys: List[float]) -> float:\n",
    "    assert len(xs) == len(ys), \"xs and ys must have same number of elements\"\n",
    "\n",
    "    return dot(de_mean(xs), de_mean(ys)) / (len(xs) - 1)\n",
    "\n",
    "def correlation(xs: List[float], ys: List[float]) -> float:\n",
    "    \"\"\"Measures how much xs and ys vary in tandem about their means\"\"\"\n",
    "    stdev_x = standard_deviation(xs)\n",
    "    stdev_y = standard_deviation(ys)\n",
    "    if stdev_x > 0 and stdev_y > 0:\n",
    "        return covariance(xs, ys) / stdev_x / stdev_y\n",
    "    else:\n",
    "        return 0    # if no variation, correlation is zero\n",
    "\n",
    "def least_squares_fit(x: Vector, y: Vector) -> Tuple[float, float]:\n",
    "    \"\"\"\n",
    "    Given two vectors x and y,\n",
    "    find the least-squares values of alpha and beta\n",
    "    \"\"\"\n",
    "    beta = correlation(x, y) * standard_deviation(y) / standard_deviation(x)\n",
    "    alpha = mean(y) - beta * mean(x)\n",
    "    return alpha, beta"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Now let’s make a quick test\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = [i for i in range(-100, 110, 10)]\n",
    "y = [3 * i - 5 for i in x]\n",
    "\n",
    "# Should find that y = 3x - 5\n",
    "assert least_squares_fit(x, y) == (-5, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### in-class exercise\n",
    "First, design x, alpha and beta by yourself. Second, use formula beta * x + alpha + random_number to generate y. The random_number could be generated by random.random function, we add it here to make the problem more challenge! Third, use the function you learned today to learn alpha and beta from the x and y, and finally generate some test data by yourself to test the performance! \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}