03_linear_regression.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# default_exp linear_regression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#hide\n",
    "from nbdev.showdoc import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linear Regression\n",
    "\n",
    "> This tutorial describes linear regression technique and demonstrates how it works via an example of fitting a curve using linear regression.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Definition\n",
    "\n",
    "Regression is an approach to modeling the relationship between a real-valued target $y$ (dependent variable) and data points $X$ (independent variables). In other words, linear regression describes the relationship between input and output and predicts the output based on the input data.\n",
    "\n",
    ">Note: $X$ is a vector of features, i.e. $X = <x_1, x_2,\\cdots, x_n>$\n",
    "\n",
    "Examples of linear regression include, predicting the weight from gender, age, and height, or predicting the stock price today from the prices of yesterday.\n",
    "\n",
    "\n",
    "We wish to learn $f:X\\to Y$, where $Y$ is a real number, given $\\{<X^1,y^1>,\\cdots, <X^m,y^m>\\}$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear Regression Intuition\n",
    "\n",
    "### How much is my house worth?\n",
    "\n",
    "<img src=\"images/linear_regression_1.svg\" width=\"700\"/>\n",
    "\n",
    "<!-- ![](img/linear_regression_1.svg) -->\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Compare Prices of Other Houses\n",
    "\n",
    "Intuitively, we plot the recent houses (e.g. last two years), and check how much other houses are sold.\n",
    "\n",
    "<img src=\"images/linear_regression_2.svg\" width=\"700\"/>\n",
    "<!-- ![](img/linear_regression_2.svg) -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Check the prices of the sold houses that have the *same* square feet as my house.\n",
    "\n",
    "<!-- ![](img/linear_regression_3.svg) -->\n",
    "\n",
    "<img src=\"images/linear_regression_3.svg\" width=\"700\"/>\n",
    "\n",
    "What if no house was sold with exactly the same size?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I look at some small range of square footage around my actual square footage, and check the houses within this range.\n",
    "\n",
    "<!-- ![](img/linear_regression_4.svg) -->\n",
    "\n",
    "<img src=\"images/linear_regression_4.svg\" width=\"700\"/>\n",
    "\n",
    "\n",
    "The problem is, I am only considering a few houses and throwing out all other observations as if they have nothing to do with the value of my house. \n",
    "\n",
    "We can leverage all the information we can from all the observations to  come up with a good prediction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear Regression Model\n",
    "\n",
    "<img src=\"images/linear_regression_5.svg\" width=\"700\"/>\n",
    "\n",
    "\n",
    "<!-- ![](img/linear_regression_5.svg) -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Formal Problem Description\n",
    "\n",
    "Let's assume that we are going to predict the price of houses (in dollars), $y$, based on their area (in square feet), $x$. Therefore, training set = $\\{<x^1,y^1>,\\cdots,<x^m,y^m>\\}$, where:\n",
    "\n",
    "- $m$: number of trainig examples\n",
    "\n",
    "\n",
    "- $x$: input variable\n",
    "\n",
    "\n",
    "- $y$: output variable or target label\n",
    "\n",
    "\n",
    "- $(x^i,y^i)$: is the $i$th training example\n",
    "\n",
    "\n",
    "$$\\hat y = f(x) = w_0 + w_1x$$\n",
    "\n",
    "where $w_0$ and $w_1$ are the paramaters of the $f(x)$ that we need to find."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Which Line to Choose?\n",
    "\n",
    "<img src=\"images/linear_regression_6.svg\" width=\"700\"/>\n",
    "\n",
    "<!-- ![](img/linear_regression_6.svg) -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Compute Cost\n",
    "\n",
    "We define the cost as the Residual Sum of Squares (RSS), which is:\n",
    "\n",
    "$$RSS(w_0,w_1)=\\sum_{i=1}^{m}(y_i-[w_0+w_1x_i])^2$$\n",
    "\n",
    "\n",
    "We *minimize* the cost over all possible values of $w_0$ and $w_1$.\n",
    "\n",
    "<img src=\"images/linear_regression_7.svg\" width=\"700\"/>\n",
    "\n",
    "<!-- ![](img/linear_regression_7.svg) -->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fit Data with a Line or ...?\n",
    "\n",
    "We might consider a quadratic function or even higher order polynomial function to fit the data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import altair as alt\n",
    "from ipywidgets import *\n",
    "\n",
    "# Generate some random data\n",
    "rng = np.random.RandomState(1)\n",
    "number_of_points = 50\n",
    "x = rng.rand(number_of_points)**2\n",
    "y = 10 - 0.5 / (x + 0.1) + rng.randn(number_of_points)\n",
    "source = pd.DataFrame({\"square feet\": x, \"price\": y})\n",
    "\n",
    "# Define the chart\n",
    "base = alt.Chart(source).mark_circle(color=\"blue\", size=70).encode(\n",
    "    alt.X(\"square feet\", axis=alt.Axis(labels=False)),\n",
    "    alt.Y(\"price\", axis=alt.Axis(labels=False)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_poly(degree):\n",
    "    return base + base.transform_regression(\n",
    "        \"square feet\", \"price\", method=\"poly\", order=degree).mark_line(size=3, color=\"red\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "interact(plot_poly,degree=widgets.IntSlider(min=1, max=20, step=1, value=1));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/lr_house_line_ex.png\" width=\"500\" height=\"500\" align=\"left\"/>\n",
    "\n",
    "\n",
    "\n",
    "<img src=\"images/lr_house_ex.png\" width=\"500\" height=\"500\" align=\"right\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Polynomial Regression Model\n",
    "\n",
    "If we represent the relationship between the independent variable $x$ and dependent variable $y$ as an $n$th degree polynomial, then the regression model is called **polynomial regression**. Therefore, we have:\n",
    "\n",
    "\n",
    "$$y_i=w_0+w_1x_i+w_2x_i^2+\\cdots+w_nx_i^n+\\epsilon_i$$\n",
    "\n",
    "\n",
    "We treat each $x_i^p$ for $p=1,\\cdots,n$ as a different feature. i.e. $feature\\ 1=x, feature\\ 2=x^2,\\cdots, feature\\ n=x^n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overfitting Problem\n",
    "\n",
    "We fit a quadratic function and look at the plot and notice that quadratic fit is better than a line. Then, we might think a higher order polynomial even fits the data better. We try 13th order polynomial and minimize the residual sum of squares. The residual sum of error is quite small, which means this 13th order polynomial is the best fit for the data. However, based on this function the price my house is unrealistically low whereas I think my house isn't worth so little.  \n",
    "\n",
    "\n",
    "<img src=\"images/linear_regression_2_13.svg\" height=\"700\"/>\n",
    "\n",
    "<!-- ![](img/linear_regression_2_13.svg) -->\n",
    "\n",
    "Quadratic function: $\\hat{y}=w_0+w_1x+w_2x^2$, and 13th order polynomial: $\\hat{y}=w_0+w_1x+w_2x^2+\\cdots w_{13}x^{13}$\n",
    "\n",
    "The reason is this 13th order polynomial is *overfitting* the data. It means even though our model fits the observations really well, it doesn't generalize well to predicting new observations. It minimizes\n",
    "the residual sum of squares, but it ends up leading to very bad predictions. Although, the quadratic function didn't minimize residual sum of squares as much as the 13th order polynomial, it still is a better model."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## How to Prevent Overfitting\n",
    "\n",
    "Considering our dataset, we remove some of the houses and fit the model on the remaining ones. We minimize the RSS error. Then, we predict the values of the held-out houses (i.e. the houses we left out) and compare the predicted values with their actual values. \n",
    "\n",
    "The dataset (e.g houses) that we use to fit the model is called **Training set**. And the dataset that we use for prediction (held-out) is called **Test set**. \n",
    "\n",
    "In order to see how well our model works, we do a little bit of analysis. We look at the residual sum of squares on the houses in our training set that is called **training error**. We then estimate the model parameters $w=[w_0,w_1]$. We take these estimated parameters and see how well we predicting the actual values of the houses that are in test set. We use the predicted value (value on the line) and again we look at the residual sum of squares over all the houses that are in the test set, and is called **test error**. Then, we assess how the test error and training error vary as function of the model complexity.\n",
    "\n",
    "<img src=\"images/linear_regression_tr_test.svg\" width=\"700\"/>\n",
    "\n",
    "<!-- ![](img/linear_regression_tr_test.svg) -->\n",
    "\n",
    "If we notice that there is a big difference between training error and test error, it means that model is likely overfitted. Another sign of overfitting is that the parameter values $w$ are very large."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Regularization\n",
    "\n",
    "We add a penalty term to the Residual sum of squares (RSS). This extra term penalizes the parameters $w$ from getting large values. Therefore, instead of minimizing the RSS, we minimize the combination of RSS and this additional regularization expression.\n",
    "\n",
    "\n",
    "$$J(\\mathbf{w})=\\sum_{i=1}^{m}\\Big( y_i-f(x_i)\\Big)^2+\\lambda\\|\\mathbf{w}\\|^2$$\n",
    "\n",
    "\n",
    "where $\\|\\mathbf{w}\\|^2 = \\sqrt{w_1^2 +w_2^2+\\cdots w_k^2}$, and $\\lambda$ is a hyperparameter that balances tradeoff."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear Regression General Expansion\n",
    "\n",
    "In general, if we have a dataset of $m$ instances with $k$ features, $\\mathbf{x}=<x_1,x_2,\\cdots,x_k>$ and a real valued target $y$, then the linear regression model takes the form:\n",
    "\n",
    "\n",
    "$$y_i=w_0+w_1h_1(x_1)+w_2h_2(x_2)+\\cdots+w_kh_k(x_k)+\\epsilon_i= w_0 +\\sum_{j=1}^{k}w_jh_j(x_i)+\\epsilon_i$$\n",
    "\n",
    "\n",
    "\n",
    "Considering our house price prediction, instead of using only area of the house, we can add more features such as number of bathrooms, number of bedrooms, age of the house, etc.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Regression Problem Statement\n",
    "\n",
    "The general approach is as follows:\n",
    "\n",
    "- Instances: $<\\mathbf{x}_i,y_i>$\n",
    "\n",
    "- Learn: mapping from $\\mathbf{x}$ to $y\\equiv f(\\mathbf{x})$\n",
    "\n",
    "- Given the basis functions $h_1, h_2,\\cdots,h_k$ where $h_j(\\mathbf{x})\\in \\mathbb{R}$\n",
    "\n",
    "- Find coeffcients $\\mathbf{w}=[w_0,w_1,\\cdots,w_k]$, where $f(\\mathbf{x})\\thickapprox \\hat{f}(\\mathbf{x})=w_0+\\sum_{j}w_jh_j(\\mathbf{x})$\n",
    "\n",
    "\n",
    "- In order to find coefficients, we need to minimize the **mean residual square error**:\n",
    "\n",
    "\n",
    "$$J(\\mathbf{w}) = \\frac{1}{m}\\sum_{i=1}^{m}\\left( f(\\mathbf{x}_i) - \\left(w_0 +\\sum_{j=1}^{k}w_jh_j(\\mathbf{x})\\right)\\right)^2$$\n",
    "\n",
    "\n",
    "\n",
    "$$\\mathbf{w}^* = \\underset{\\mathbf{w}}{\\arg\\min}\\ J(\\mathbf{w})$$\n",
    "\n",
    "\n",
    ">Note: The reason it's called *linear* regression is that the model is a linear combinations of the input features.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example: Fit a Line to Two Diminsional Data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We would like to find a **line** that **fits** our training examples the **best**.\n",
    "\n",
    "<img src=\"images/linear_regression_ex_model.png\" width=\"500\" height=\"500\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since we are looling for a line to fit our training set, we need to find a function $\\hat y = f(x)$ that estimates $y^i$ for all $1\\leq i \\leq m$. Thus, we have:\n",
    "\n",
    "\n",
    "$$\\hat y = f(x) = w_0 + w_1x$$\n",
    "\n",
    "$w_0$ and $w_1$ are the paramaters that we need to find."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cost Function (Error Function)\n",
    "\n",
    "We wish to estimate the actual $y$, i.e. we want to minimize the error as much as possible. The error is the difference between the actual $y^i$ and our estimated/predicted $\\hat{y}^i$ for all $1\\leq i \\leq m$. \n",
    "\n",
    "\n",
    "The error/cost function is:\n",
    "\n",
    "\n",
    "$$J(w_0,w_1) = \\frac{1}{m}\\sum_{i=1}^{m}\\left( y^i - (w_0 + w_1 x^i)\\right)^2$$\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Precisely, we need to minimize the **mean residual squared error**:\n",
    "\n",
    "\n",
    "$$\\text{minimize } J(w_0,w_1) = \\underset{w0,w_1}{\\arg\\min} \\frac{1}{m}\\sum_{i=1}^{m}\\left( \\hat{y}^i - (w_0 + w_1 x^i)\\right)^2$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fitting the Linear Regression Model using Gradient Descent Algorithm\n",
    "\n",
    "\n",
    "In order to mininze the cost function, we need to take the gradient (i.e. derivative) of the function with resptect to our parameters $w_0$ and $w_1$, set it zero and solve for $w_0$ and $w_1$.\n",
    " \n",
    " \n",
    "$$\\frac{\\partial{J}}{\\partial{w_0}} = \\frac{-2}{m} \\sum_{i=1}^{m}\\left(\\hat{y}^i - (w_0 + w_1 x^i)\\right)$$\n",
    "\n",
    "\n",
    "$$\\frac{\\partial{J}}{\\partial{w_1}} = \\frac{-2}{m} \\sum_{i=1}^{m}x^i\\left(\\hat{y}^i - (w_0 + w_1 x^i)\\right)$$\n",
    "\n",
    "<img src=\"images/gradient_descent.png\" width=\"500\"/>\n",
    "\n",
    "*image source: https://towardsdatascience.com/gradient-descent-algorithm-and-its-variants-10f652806a3*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The gradient descent algorithm:\n",
    "\n",
    "initialize $w_0^{(0)} = w_1^{(0)} = 0$, for $t=0$\n",
    "\n",
    "for $t=1$ to *num_iterations*\n",
    "   \n",
    "\n",
    "   \n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\n",
    "$w_0^{(t+1)} = w_0^{(t)} - \\eta \\frac{-2}{m} \\sum_{i=1}^{m}\\left(\\hat{y}^i - (w_0 + w_1 x^i)\\right) $\n",
    "\n",
    "\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\n",
    "$w_1^{(t+1)} = w_1^{(t)} - \\eta\\frac{-2}{m} \\sum_{i=1}^{m}x^i\\left(\\hat{y}^i - (w_0 + w_1 x^i)\\right)$\n",
    "\n",
    "\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$t = t+1$\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implemented Functions\n",
    "\n",
    "All the functions, their implementations and documentations are described below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#export\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import altair as alt\n",
    "\n",
    "\n",
    "def generate_data(n):\n",
    "    \"\"\"It generates dummy data.\"\"\"\n",
    "    noise = np.random.randn(n,1)\n",
    "    X = 2 * np.random.rand(n,1)\n",
    "    y = 5 + 3 * X + noise\n",
    "    return X,y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#export\n",
    "def make_point_plot(x,y):\n",
    "    \"\"\"It plots the point chart of the data\"\"\"\n",
    "    \n",
    "    data_points = pd.DataFrame({'x': x.flatten(), 'y': y.flatten()})\n",
    "    chart = alt.Chart(data_points).mark_point(size=50, color='red',filled=True).encode(\n",
    "        x=\"x\",\n",
    "        y=\"y\"\n",
    "    )\n",
    "    return chart\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#export\n",
    "def make_line_plot(x,y):\n",
    "    \"\"\"It plots the line chart of the data\"\"\"\n",
    "    \n",
    "    data = pd.DataFrame({'x': x.flatten(), 'y': y.flatten()})\n",
    "    line = alt.Chart(data).mark_line(size=3).encode(\n",
    "        x=\"x\",\n",
    "        y=\"y\"\n",
    "    )\n",
    "    return line"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#export\n",
    "def gradient_descent(data,w_0_t,w_1_t,learning_rate,num_iterations):\n",
    "    \"\"\"Gradient descent implementation, which gets `data`, starting `w_0` and `w_1`, `learning_rate` \n",
    "    and the number of iterations `num_iterations`\"\"\"\n",
    "    \n",
    "    w_0 = 0\n",
    "    w_1 = 0\n",
    "    (X,y) = data\n",
    "    N = len(X)\n",
    "    for t in range(0,num_iterations):\n",
    "        w_0_deriv = np.zeros((N,N))\n",
    "        w_1_deriv = np.zeros((N,N))\n",
    "        w_0_deriv = -2 * (y - (w_0_t + w_1_t * X))\n",
    "        w_1_deriv = -2 * np.dot(X.T, (y - (w_0_t + w_1_t * X)))\n",
    "        w0_sum = np.sum(w_0_deriv,axis=0)\n",
    "        w1_sum = np.sum(w_1_deriv,axis=0)\n",
    "        w_0 = w_0 - learning_rate * (w0_sum / N)\n",
    "        w_1 = w_1 - learning_rate * (w1_sum / N)\n",
    "        w_0_t = w_0\n",
    "        w_1_t = w_1\n",
    "    return w_0, w_1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Run an Example\n",
    "\n",
    "In this example, we generate some linear-looking data and then find the line that fits the data. The function that we use to generate the data is $y=5+3x+\\text{Gaussian noise}$. Our goal is to find $\\theta=[w_0,w_1]$ where $w_0=5$ and $w_1=3$ or close enough, as we have noise and it makes it impossible to recover the exact paratmeters of the function. We use the `generate_data` function to generate the training data. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(100)\n",
    "\n",
    "# Approximate y = 5 + 3x\n",
    "X,y = generate_data(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The chart below shows the generated dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "<div id=\"altair-viz-b25208df9f04454cb7a0850e4434ea68\"></div>\n",
       "<script type=\"text/javascript\">\n",
       "  (function(spec, embedOpt){\n",
       "    const outputDiv = document.getElementById(\"altair-viz-b25208df9f04454cb7a0850e4434ea68\");\n",
       "    const paths = {\n",
       "      \"vega\": \"https://cdn.jsdelivr.net/npm//vega@5?noext\",\n",
       "      \"vega-lib\": \"https://cdn.jsdelivr.net/npm//vega-lib?noext\",\n",
       "      \"vega-lite\": \"https://cdn.jsdelivr.net/npm//vega-lite@4.0.2?noext\",\n",
       "      \"vega-embed\": \"https://cdn.jsdelivr.net/npm//vega-embed@6?noext\",\n",
       "    };\n",
       "\n",
       "    function loadScript(lib) {\n",
       "      return new Promise(function(resolve, reject) {\n",
       "        var s = document.createElement('script');\n",
       "        s.src = paths[lib];\n",
       "        s.async = true;\n",
       "        s.onload = () => resolve(paths[lib]);\n",
       "        s.onerror = () => reject(`Error loading script: ${paths[lib]}`);\n",
       "        document.getElementsByTagName(\"head\")[0].appendChild(s);\n",
       "      });\n",
       "    }\n",
       "\n",
       "    function showError(err) {\n",
       "      outputDiv.innerHTML = `<div class=\"error\" style=\"color:red;\">${err}</div>`;\n",
       "      throw err;\n",
       "    }\n",
       "\n",
       "    function displayChart(vegaEmbed) {\n",
       "      vegaEmbed(outputDiv, spec, embedOpt)\n",
       "        .catch(err => showError(`Javascript Error: ${err.message}<br>This usually means there's a typo in your chart specification. See the javascript console for the full traceback.`));\n",
       "    }\n",
       "\n",
       "    if(typeof define === \"function\" && define.amd) {\n",
       "      requirejs.config({paths});\n",
       "      require([\"vega-embed\"], displayChart, err => showError(`Error loading script: ${err.message}`));\n",
       "    } else if (typeof vegaEmbed === \"function\") {\n",
       "      displayChart(vegaEmbed);\n",
       "    } else {\n",
       "      loadScript(\"vega\")\n",
       "        .then(() => loadScript(\"vega-lite\"))\n",
       "        .then(() => loadScript(\"vega-embed\"))\n",
       "        .catch(showError)\n",
       "        .then(() => displayChart(vegaEmbed));\n",
       "    }\n",
       "  })({\"config\": {\"view\": {\"continuousWidth\": 400, \"continuousHeight\": 300}}, \"data\": {\"name\": \"data-d77d4f31777d11718b31df3feb164da9\"}, \"mark\": {\"type\": \"point\", \"color\": \"red\", \"filled\": true, \"size\": 50}, \"encoding\": {\"x\": {\"type\": \"quantitative\", \"field\": \"x\"}, \"y\": {\"type\": \"quantitative\", \"field\": \"y\"}}, \"$schema\": \"https://vega.github.io/schema/vega-lite/v4.0.2.json\", \"datasets\": {\"data-d77d4f31777d11718b31df3feb164da9\": [{\"x\": 0.8057606627582843, \"y\": 5.667516515220155}, {\"x\": 0.7085966002126411, \"y\": 7.468470203965426}, {\"x\": 1.0012286388859064, \"y\": 9.156721719221363}, {\"x\": 0.8903532576622766, \"y\": 7.41862373646544}, {\"x\": 0.1808655763928717, \"y\": 6.523917516129846}, {\"x\": 0.5471258400548813, \"y\": 7.155596361559026}, {\"x\": 1.8869541954854538, \"y\": 10.882042255677762}, {\"x\": 0.05308928266788393, \"y\": 4.089224517435358}, {\"x\": 0.07999737928130157, \"y\": 5.050496307020729}, {\"x\": 0.5662807194396391, \"y\": 6.953843602592299}, {\"x\": 1.1646883404335377, \"y\": 8.03603803579799}, {\"x\": 1.9817856058496541, \"y\": 11.380520305671855}, {\"x\": 1.9852844748059362, \"y\": 10.372258374095145}, {\"x\": 1.9862347449620896, \"y\": 11.775551306572048}, {\"x\": 0.22009666193312594, \"y\": 6.333010791509039}, {\"x\": 1.3289628919278802, \"y\": 8.882477532393013}, {\"x\": 1.0479736689766257, \"y\": 7.6126406300779665}, {\"x\": 0.34629981961746203, \"y\": 7.068632143985733}, {\"x\": 1.8859204898300514, \"y\": 10.219625846785737}, {\"x\": 0.4837201719525046, \"y\": 5.332842269602078}, {\"x\": 1.997864537686424, \"y\": 12.612575273734532}, {\"x\": 1.1653876302997974, \"y\": 10.037768065412799}, {\"x\": 0.36655800126115157, \"y\": 5.847794864570242}, {\"x\": 0.7736908438355805, \"y\": 6.478636793255444}, {\"x\": 0.3793470578242992, \"y\": 6.32255986403684}, {\"x\": 0.82154134605062, \"y\": 8.401706239260813}, {\"x\": 1.1893601378034109, \"y\": 9.299080757245042}, {\"x\": 1.4331721862566797, \"y\": 10.66107268391537}, {\"x\": 0.973782964738247, \"y\": 7.595110835012439}, {\"x\": 0.6191796355334092, \"y\": 6.913214921455005}, {\"x\": 1.1548827456556947, \"y\": 8.68704784552239}, {\"x\": 0.8834156391374859, \"y\": 6.207029922187122}, {\"x\": 0.7193562052010725, \"y\": 6.401716310008782}, {\"x\": 0.6426638640176272, \"y\": 7.744445603072168}, {\"x\": 0.4164144803920453, \"y\": 6.999688202710314}, {\"x\": 0.9025172481236687, \"y\": 7.251604816903004}, {\"x\": 0.9836858205281078, \"y\": 9.14067972961345}, {\"x\": 1.7981526295874224, \"y\": 8.703841062378665}, {\"x\": 1.4587209220588824, \"y\": 8.019763717315335}, {\"x\": 1.540179545839391, \"y\": 8.388104123603247}, {\"x\": 0.7508784951239764, \"y\": 6.708196323699465}, {\"x\": 0.6874790704707687, \"y\": 6.394265474598878}, {\"x\": 1.3100704119986448, \"y\": 8.937525799224836}, {\"x\": 1.422075986420995, \"y\": 8.653289223784821}, {\"x\": 0.2270751504373525, \"y\": 6.980973526067366}, {\"x\": 0.2660573787471501, \"y\": 4.065076512588169}, {\"x\": 0.9120781152122479, \"y\": 6.7529242465071135}, {\"x\": 0.31947246031702026, \"y\": 6.315925134118427}, {\"x\": 1.9232838075492915, \"y\": 9.1562729198257}, {\"x\": 1.6752314897236196, \"y\": 11.496408335782988}, {\"x\": 1.0403213740758466, \"y\": 6.932946524909822}, {\"x\": 0.4365445154563088, \"y\": 5.759887352833437}, {\"x\": 0.26983744506479757, \"y\": 4.8694661736496245}, {\"x\": 1.9581406909677377, \"y\": 10.046489708537342}, {\"x\": 1.4140869913782863, \"y\": 9.351124441968537}, {\"x\": 1.7199511138913262, \"y\": 10.667662932166298}, {\"x\": 0.7743452556572781, \"y\": 6.460808420461355}, {\"x\": 0.5016680396634496, \"y\": 7.754473861717328}, {\"x\": 0.5988760378894045, \"y\": 6.717016867750814}, {\"x\": 1.7137910568100314, \"y\": 9.25164168916506}, {\"x\": 0.9459679811364421, \"y\": 6.956105553926309}, {\"x\": 1.3265540940322564, \"y\": 8.99830123158483}, {\"x\": 1.6114572148735704, \"y\": 10.072216266544332}, {\"x\": 0.5059610092994482, \"y\": 6.531431576526956}, {\"x\": 0.15914687794064974, \"y\": 3.8419112344411275}, {\"x\": 1.4655212100314303, \"y\": 8.352353752384975}, {\"x\": 1.922794955007211, \"y\": 11.38142374670918}, {\"x\": 1.9076094683353255, \"y\": 11.459033618329801}, {\"x\": 0.9809981037677993, \"y\": 8.969915750703189}, {\"x\": 1.2643841288655102, \"y\": 7.360961775537605}, {\"x\": 1.4659900396759846, \"y\": 7.556781818841236}, {\"x\": 1.8048190064959324, \"y\": 10.7805502456551}, {\"x\": 0.32449383749640015, \"y\": 5.641704377436392}, {\"x\": 0.8117626447351225, \"y\": 6.7460699561156146}, {\"x\": 0.8341814711673217, \"y\": 9.5371519750069}, {\"x\": 1.3911820565841477, \"y\": 8.62283175783785}, {\"x\": 0.8496944758496632, \"y\": 8.299536757875831}, {\"x\": 1.7162284521028595, \"y\": 8.84169301722776}, {\"x\": 1.693864959218838, \"y\": 10.662168213450787}, {\"x\": 0.14039822781737765, \"y\": 4.31667159078984}, {\"x\": 0.603504826968297, \"y\": 7.500635951129598}, {\"x\": 1.9592473620603403, \"y\": 11.564632152319426}, {\"x\": 0.07125399310606961, \"y\": 3.6470744497398178}, {\"x\": 0.9847852939971642, \"y\": 8.859330003458174}, {\"x\": 1.9047537060270927, \"y\": 11.493083517404346}, {\"x\": 1.6211475170589422, \"y\": 10.291675421773569}, {\"x\": 0.5886608825927424, \"y\": 6.874854637676141}, {\"x\": 1.1924670370366823, \"y\": 8.60568474593312}, {\"x\": 0.8623557045994599, \"y\": 7.008241289007391}, {\"x\": 1.1847950059779726, \"y\": 7.354933818739986}, {\"x\": 1.787504209440412, \"y\": 8.656560622583067}, {\"x\": 1.1080423795434124, \"y\": 8.693291095737242}, {\"x\": 0.9857330146905476, \"y\": 9.833772471033809}, {\"x\": 0.6385409143790024, \"y\": 6.538719392968032}, {\"x\": 0.526731566101448, \"y\": 8.41213078012988}, {\"x\": 1.0845612270715916, \"y\": 8.256701115245988}, {\"x\": 0.16452904786404798, \"y\": 5.417563677867521}, {\"x\": 1.271273419650797, \"y\": 8.81777785293999}, {\"x\": 1.5928104503724156, \"y\": 9.593417240220132}, {\"x\": 1.9094950108616178, \"y\": 8.241333497362083}]}}, {\"mode\": \"vega-lite\"});\n",
       "</script>"
      ],
      "text/plain": [
       "alt.Chart(...)"
      ]
     },
     "execution_count": null,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "origin_chart = make_point_plot(X,y)\n",
    "\n",
    "#show the chart\n",
    "origin_chart"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We set the initial parameters to 0:  $w_0^{(0)} = w_1^{(0)} = 0$, define the number of iterations of the graditent descent algorithm as well as the learning rate. Then, we run the `gradient_descent` function. The outputs of this function are the estimated parameters $w_0$ and $w_1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "w_0 = [4.92304901], w_1 = [2.97394648]\n"
     ]
    }
   ],
   "source": [
    "initial_w_0 = 0\n",
    "initial_w_1 = 0\n",
    "num_iterations = 1000\n",
    "learning_rate = 0.1\n",
    "\n",
    "data = (X,y)\n",
    "w_0,w_1 = gradient_descent(data,initial_w_0,initial_w_1,learning_rate,num_iterations)\n",
    "\n",
    "print(\"w_0 = {}, w_1 = {}\".format(w_0,w_1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The estimated parameters are $w_0 = 4.923$ and $w_1 = 2.97$ that are close enough to $w_0=5$ and $w_1=3$. Let's plot the line."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "<div id=\"altair-viz-d3c1b6e759444a6cacf374e677ca0fe5\"></div>\n",
       "<script type=\"text/javascript\">\n",
       "  (function(spec, embedOpt){\n",
       "    const outputDiv = document.getElementById(\"altair-viz-d3c1b6e759444a6cacf374e677ca0fe5\");\n",
       "    const paths = {\n",
       "      \"vega\": \"https://cdn.jsdelivr.net/npm//vega@5?noext\",\n",
       "      \"vega-lib\": \"https://cdn.jsdelivr.net/npm//vega-lib?noext\",\n",
       "      \"vega-lite\": \"https://cdn.jsdelivr.net/npm//vega-lite@4.0.2?noext\",\n",
       "      \"vega-embed\": \"https://cdn.jsdelivr.net/npm//vega-embed@6?noext\",\n",
       "    };\n",
       "\n",
       "    function loadScript(lib) {\n",
       "      return new Promise(function(resolve, reject) {\n",
       "        var s = document.createElement('script');\n",
       "        s.src = paths[lib];\n",
       "        s.async = true;\n",
       "        s.onload = () => resolve(paths[lib]);\n",
       "        s.onerror = () => reject(`Error loading script: ${paths[lib]}`);\n",
       "        document.getElementsByTagName(\"head\")[0].appendChild(s);\n",
       "      });\n",
       "    }\n",
       "\n",
       "    function showError(err) {\n",
       "      outputDiv.innerHTML = `<div class=\"error\" style=\"color:red;\">${err}</div>`;\n",
       "      throw err;\n",
       "    }\n",
       "\n",
       "    function displayChart(vegaEmbed) {\n",
       "      vegaEmbed(outputDiv, spec, embedOpt)\n",
       "        .catch(err => showError(`Javascript Error: ${err.message}<br>This usually means there's a typo in your chart specification. See the javascript console for the full traceback.`));\n",
       "    }\n",
       "\n",
       "    if(typeof define === \"function\" && define.amd) {\n",
       "      requirejs.config({paths});\n",
       "      require([\"vega-embed\"], displayChart, err => showError(`Error loading script: ${err.message}`));\n",
       "    } else if (typeof vegaEmbed === \"function\") {\n",
       "      displayChart(vegaEmbed);\n",
       "    } else {\n",
       "      loadScript(\"vega\")\n",
       "        .then(() => loadScript(\"vega-lite\"))\n",
       "        .then(() => loadScript(\"vega-embed\"))\n",
       "        .catch(showError)\n",
       "        .then(() => displayChart(vegaEmbed));\n",
       "    }\n",
       "  })({\"config\": {\"view\": {\"continuousWidth\": 400, \"continuousHeight\": 300}}, \"layer\": [{\"data\": {\"name\": \"data-d77d4f31777d11718b31df3feb164da9\"}, \"mark\": {\"type\": \"point\", \"color\": \"red\", \"filled\": true, \"size\": 50}, \"encoding\": {\"x\": {\"type\": \"quantitative\", \"field\": \"x\"}, \"y\": {\"type\": \"quantitative\", \"field\": \"y\"}}}, {\"data\": {\"name\": \"data-fe04dd34dbf1c590d7ac876197c4c736\"}, \"mark\": {\"type\": \"line\", \"size\": 3}, \"encoding\": {\"x\": {\"type\": \"quantitative\", \"field\": \"x\"}, \"y\": {\"type\": \"quantitative\", \"field\": \"y\"}}}], \"$schema\": \"https://vega.github.io/schema/vega-lite/v4.0.2.json\", \"datasets\": {\"data-d77d4f31777d11718b31df3feb164da9\": [{\"x\": 0.8057606627582843, \"y\": 5.667516515220155}, {\"x\": 0.7085966002126411, \"y\": 7.468470203965426}, {\"x\": 1.0012286388859064, \"y\": 9.156721719221363}, {\"x\": 0.8903532576622766, \"y\": 7.41862373646544}, {\"x\": 0.1808655763928717, \"y\": 6.523917516129846}, {\"x\": 0.5471258400548813, \"y\": 7.155596361559026}, {\"x\": 1.8869541954854538, \"y\": 10.882042255677762}, {\"x\": 0.05308928266788393, \"y\": 4.089224517435358}, {\"x\": 0.07999737928130157, \"y\": 5.050496307020729}, {\"x\": 0.5662807194396391, \"y\": 6.953843602592299}, {\"x\": 1.1646883404335377, \"y\": 8.03603803579799}, {\"x\": 1.9817856058496541, \"y\": 11.380520305671855}, {\"x\": 1.9852844748059362, \"y\": 10.372258374095145}, {\"x\": 1.9862347449620896, \"y\": 11.775551306572048}, {\"x\": 0.22009666193312594, \"y\": 6.333010791509039}, {\"x\": 1.3289628919278802, \"y\": 8.882477532393013}, {\"x\": 1.0479736689766257, \"y\": 7.6126406300779665}, {\"x\": 0.34629981961746203, \"y\": 7.068632143985733}, {\"x\": 1.8859204898300514, \"y\": 10.219625846785737}, {\"x\": 0.4837201719525046, \"y\": 5.332842269602078}, {\"x\": 1.997864537686424, \"y\": 12.612575273734532}, {\"x\": 1.1653876302997974, \"y\": 10.037768065412799}, {\"x\": 0.36655800126115157, \"y\": 5.847794864570242}, {\"x\": 0.7736908438355805, \"y\": 6.478636793255444}, {\"x\": 0.3793470578242992, \"y\": 6.32255986403684}, {\"x\": 0.82154134605062, \"y\": 8.401706239260813}, {\"x\": 1.1893601378034109, \"y\": 9.299080757245042}, {\"x\": 1.4331721862566797, \"y\": 10.66107268391537}, {\"x\": 0.973782964738247, \"y\": 7.595110835012439}, {\"x\": 0.6191796355334092, \"y\": 6.913214921455005}, {\"x\": 1.1548827456556947, \"y\": 8.68704784552239}, {\"x\": 0.8834156391374859, \"y\": 6.207029922187122}, {\"x\": 0.7193562052010725, \"y\": 6.401716310008782}, {\"x\": 0.6426638640176272, \"y\": 7.744445603072168}, {\"x\": 0.4164144803920453, \"y\": 6.999688202710314}, {\"x\": 0.9025172481236687, \"y\": 7.251604816903004}, {\"x\": 0.9836858205281078, \"y\": 9.14067972961345}, {\"x\": 1.7981526295874224, \"y\": 8.703841062378665}, {\"x\": 1.4587209220588824, \"y\": 8.019763717315335}, {\"x\": 1.540179545839391, \"y\": 8.388104123603247}, {\"x\": 0.7508784951239764, \"y\": 6.708196323699465}, {\"x\": 0.6874790704707687, \"y\": 6.394265474598878}, {\"x\": 1.3100704119986448, \"y\": 8.937525799224836}, {\"x\": 1.422075986420995, \"y\": 8.653289223784821}, {\"x\": 0.2270751504373525, \"y\": 6.980973526067366}, {\"x\": 0.2660573787471501, \"y\": 4.065076512588169}, {\"x\": 0.9120781152122479, \"y\": 6.7529242465071135}, {\"x\": 0.31947246031702026, \"y\": 6.315925134118427}, {\"x\": 1.9232838075492915, \"y\": 9.1562729198257}, {\"x\": 1.6752314897236196, \"y\": 11.496408335782988}, {\"x\": 1.0403213740758466, \"y\": 6.932946524909822}, {\"x\": 0.4365445154563088, \"y\": 5.759887352833437}, {\"x\": 0.26983744506479757, \"y\": 4.8694661736496245}, {\"x\": 1.9581406909677377, \"y\": 10.046489708537342}, {\"x\": 1.4140869913782863, \"y\": 9.351124441968537}, {\"x\": 1.7199511138913262, \"y\": 10.667662932166298}, {\"x\": 0.7743452556572781, \"y\": 6.460808420461355}, {\"x\": 0.5016680396634496, \"y\": 7.754473861717328}, {\"x\": 0.5988760378894045, \"y\": 6.717016867750814}, {\"x\": 1.7137910568100314, \"y\": 9.25164168916506}, {\"x\": 0.9459679811364421, \"y\": 6.956105553926309}, {\"x\": 1.3265540940322564, \"y\": 8.99830123158483}, {\"x\": 1.6114572148735704, \"y\": 10.072216266544332}, {\"x\": 0.5059610092994482, \"y\": 6.531431576526956}, {\"x\": 0.15914687794064974, \"y\": 3.8419112344411275}, {\"x\": 1.4655212100314303, \"y\": 8.352353752384975}, {\"x\": 1.922794955007211, \"y\": 11.38142374670918}, {\"x\": 1.9076094683353255, \"y\": 11.459033618329801}, {\"x\": 0.9809981037677993, \"y\": 8.969915750703189}, {\"x\": 1.2643841288655102, \"y\": 7.360961775537605}, {\"x\": 1.4659900396759846, \"y\": 7.556781818841236}, {\"x\": 1.8048190064959324, \"y\": 10.7805502456551}, {\"x\": 0.32449383749640015, \"y\": 5.641704377436392}, {\"x\": 0.8117626447351225, \"y\": 6.7460699561156146}, {\"x\": 0.8341814711673217, \"y\": 9.5371519750069}, {\"x\": 1.3911820565841477, \"y\": 8.62283175783785}, {\"x\": 0.8496944758496632, \"y\": 8.299536757875831}, {\"x\": 1.7162284521028595, \"y\": 8.84169301722776}, {\"x\": 1.693864959218838, \"y\": 10.662168213450787}, {\"x\": 0.14039822781737765, \"y\": 4.31667159078984}, {\"x\": 0.603504826968297, \"y\": 7.500635951129598}, {\"x\": 1.9592473620603403, \"y\": 11.564632152319426}, {\"x\": 0.07125399310606961, \"y\": 3.6470744497398178}, {\"x\": 0.9847852939971642, \"y\": 8.859330003458174}, {\"x\": 1.9047537060270927, \"y\": 11.493083517404346}, {\"x\": 1.6211475170589422, \"y\": 10.291675421773569}, {\"x\": 0.5886608825927424, \"y\": 6.874854637676141}, {\"x\": 1.1924670370366823, \"y\": 8.60568474593312}, {\"x\": 0.8623557045994599, \"y\": 7.008241289007391}, {\"x\": 1.1847950059779726, \"y\": 7.354933818739986}, {\"x\": 1.787504209440412, \"y\": 8.656560622583067}, {\"x\": 1.1080423795434124, \"y\": 8.693291095737242}, {\"x\": 0.9857330146905476, \"y\": 9.833772471033809}, {\"x\": 0.6385409143790024, \"y\": 6.538719392968032}, {\"x\": 0.526731566101448, \"y\": 8.41213078012988}, {\"x\": 1.0845612270715916, \"y\": 8.256701115245988}, {\"x\": 0.16452904786404798, \"y\": 5.417563677867521}, {\"x\": 1.271273419650797, \"y\": 8.81777785293999}, {\"x\": 1.5928104503724156, \"y\": 9.593417240220132}, {\"x\": 1.9094950108616178, \"y\": 8.241333497362083}], \"data-fe04dd34dbf1c590d7ac876197c4c736\": [{\"x\": 0.8057606627582843, \"y\": 7.319338103503201}, {\"x\": 0.7085966002126411, \"y\": 7.030377381425598}, {\"x\": 1.0012286388859064, \"y\": 7.900649403639013}, {\"x\": 0.8903532576622766, \"y\": 7.570911953602286}, {\"x\": 0.1808655763928717, \"y\": 5.4609335591885575}, {\"x\": 0.5471258400548813, \"y\": 6.550171982153747}, {\"x\": 1.8869541954854538, \"y\": 10.534749807554947}, {\"x\": 0.05308928266788393, \"y\": 5.080933699859622}, {\"x\": 0.07999737928130157, \"y\": 5.16095693914621}, {\"x\": 0.5662807194396391, \"y\": 6.607137568331547}, {\"x\": 1.1646883404335377, \"y\": 8.386769808162084}, {\"x\": 1.9817856058496541, \"y\": 10.816773346881583}, {\"x\": 1.9852844748059362, \"y\": 10.82717879590845}, {\"x\": 1.9862347449620896, \"y\": 10.830004848497204}, {\"x\": 0.22009666193312594, \"y\": 5.577604708053652}, {\"x\": 1.3289628919278802, \"y\": 8.875313532818314}, {\"x\": 1.0479736689766257, \"y\": 8.03966662147311}, {\"x\": 0.34629981961746203, \"y\": 5.952926144987276}, {\"x\": 1.8859204898300514, \"y\": 10.531675622256648}, {\"x\": 0.4837201719525046, \"y\": 6.361606918501032}, {\"x\": 1.997864537686424, \"y\": 10.864591229667276}, {\"x\": 1.1653876302997974, \"y\": 8.388849458800415}, {\"x\": 0.36655800126115157, \"y\": 6.013172893037666}, {\"x\": 0.7736908438355805, \"y\": 7.223964178308901}, {\"x\": 0.3793470578242992, \"y\": 6.051206862824}, {\"x\": 0.82154134605062, \"y\": 7.366269011079129}, {\"x\": 1.1893601378034109, \"y\": 8.46014241317849}, {\"x\": 1.4331721862566797, \"y\": 9.185226397179065}, {\"x\": 0.973782964738247, \"y\": 7.81902743753515}, {\"x\": 0.6191796355334092, \"y\": 6.7644561138009465}, {\"x\": 1.1548827456556947, \"y\": 8.357608494059198}, {\"x\": 0.8834156391374859, \"y\": 7.5502798473903745}, {\"x\": 0.7193562052010725, \"y\": 7.062375870838969}, {\"x\": 0.6426638640176272, \"y\": 6.8342969525065875}, {\"x\": 0.4164144803920453, \"y\": 6.1614433938016955}, {\"x\": 0.9025172481236687, \"y\": 7.607087010253687}, {\"x\": 0.9836858205281078, \"y\": 7.848478000682654}, {\"x\": 1.7981526295874224, \"y\": 10.270658702971264}, {\"x\": 1.4587209220588824, \"y\": 9.261206970162068}, {\"x\": 1.540179545839391, \"y\": 9.503460557860773}, {\"x\": 0.7508784951239764, \"y\": 7.156121474089996}, {\"x\": 0.6874790704707687, \"y\": 6.967574978120979}, {\"x\": 1.3100704119986448, \"y\": 8.819128308578396}, {\"x\": 1.422075986420995, \"y\": 9.152226892703522}, {\"x\": 0.2270751504373525, \"y\": 5.598358359397165}, {\"x\": 0.2660573787471501, \"y\": 5.714289420176984}, {\"x\": 0.9120781152122479, \"y\": 7.635520517305803}, {\"x\": 0.31947246031702026, \"y\": 5.873143014148655}, {\"x\": 1.9232838075492915, \"y\": 10.642792129579455}, {\"x\": 1.6752314897236196, \"y\": 9.905097811392022}, {\"x\": 1.0403213740758466, \"y\": 8.016909105966375}, {\"x\": 0.4365445154563088, \"y\": 6.221309040782899}, {\"x\": 0.26983744506479757, \"y\": 5.725531135107702}, {\"x\": 1.9581406909677377, \"y\": 10.746454635428645}, {\"x\": 1.4140869913782863, \"y\": 9.128468048993884}, {\"x\": 1.7199511138913262, \"y\": 10.038091580404814}, {\"x\": 0.7743452556572781, \"y\": 7.225910364044445}, {\"x\": 0.5016680396634496, \"y\": 6.414982916556607}, {\"x\": 0.5988760378894045, \"y\": 6.704074300996148}, {\"x\": 1.7137910568100314, \"y\": 10.01977190031307}, {\"x\": 0.9459679811364421, \"y\": 7.736307164879005}, {\"x\": 1.3265540940322564, \"y\": 8.868149896788466}, {\"x\": 1.6114572148735704, \"y\": 9.715436530998472}, {\"x\": 0.5059610092994482, \"y\": 6.427749978507034}, {\"x\": 0.15914687794064974, \"y\": 5.39634331231213}, {\"x\": 1.4655212100314303, \"y\": 9.281430662661133}, {\"x\": 1.922794955007211, \"y\": 10.641338308281249}, {\"x\": 1.9076094683353255, \"y\": 10.596177483601377}, {\"x\": 0.9809981037677993, \"y\": 7.840484874876145}, {\"x\": 1.2643841288655102, \"y\": 8.683259747535152}, {\"x\": 1.4659900396759846, \"y\": 9.282824936933663}, {\"x\": 1.8048190064959324, \"y\": 10.290484151132404}, {\"x\": 0.32449383749640015, \"y\": 5.888076321150882}, {\"x\": 0.8117626447351225, \"y\": 7.3371876766940005}, {\"x\": 0.8341814711673217, \"y\": 7.403860066714103}, {\"x\": 1.3911820565841477, \"y\": 9.060349998720454}, {\"x\": 0.8496944758496632, \"y\": 7.4499949124292755}, {\"x\": 1.7162284521028595, \"y\": 10.027020583471757}, {\"x\": 1.693864959218838, \"y\": 9.960512752462648}, {\"x\": 0.14039822781737765, \"y\": 5.3405858302178}, {\"x\": 0.603504826968297, \"y\": 6.717840071997679}, {\"x\": 1.9592473620603403, \"y\": 10.749745816032284}, {\"x\": 0.07125399310606961, \"y\": 5.1349545765812294}, {\"x\": 0.9847852939971642, \"y\": 7.85174777593906}, {\"x\": 1.9047537060270927, \"y\": 10.587684599328641}, {\"x\": 1.6211475170589422, \"y\": 9.744254971101466}, {\"x\": 0.5886608825927424, \"y\": 6.673694975828763}, {\"x\": 1.1924670370366823, \"y\": 8.469382165226184}, {\"x\": 0.8623557045994599, \"y\": 7.48764872913967}, {\"x\": 1.1847950059779726, \"y\": 8.446565955441985}, {\"x\": 1.787504209440412, \"y\": 10.238990871325996}, {\"x\": 1.1080423795434124, \"y\": 8.218307751999074}, {\"x\": 0.9857330146905476, \"y\": 7.854566246561975}, {\"x\": 0.6385409143790024, \"y\": 6.822035520929383}, {\"x\": 0.526731566101448, \"y\": 6.489520502857436}, {\"x\": 1.0845612270715916, \"y\": 8.148476061189685}, {\"x\": 0.16452904786404798, \"y\": 5.412349597626506}, {\"x\": 1.271273419650797, \"y\": 8.703748129636136}, {\"x\": 1.5928104503724156, \"y\": 9.659982051291703}, {\"x\": 1.9094950108616178, \"y\": 10.601784986165914}]}}, {\"mode\": \"vega-lite\"});\n",
       "</script>"
      ],
      "text/plain": [
       "alt.LayerChart(...)"
      ]
     },
     "execution_count": null,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y_predicted = w_0 + w_1 * X\n",
    "line = make_line_plot(X,y_predicted)\n",
    "\n",
    "#show the charts\n",
    "origin_chart + line"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "learning_rate: 0.0010 => w_0 = [3.7720079], w_1 = [3.84479659]\n",
      "learning_rate: 0.0100 => w_0 = [4.83820114], w_1 = [3.0435688]\n",
      "learning_rate: 0.1000 => w_0 = [4.92304901], w_1 = [2.97394648]\n",
      "learning_rate: 0.0020 => w_0 = [4.08495606], w_1 = [3.66089023]\n"
     ]
    }
   ],
   "source": [
    "\n",
    "num_iterations = 1000\n",
    "l_rates = [0.001,0.01,0.1,0.002]\n",
    "all_params = []\n",
    "\n",
    "# X,y = generate_data()\n",
    "data = (X,y)\n",
    "for i in range(0,len(l_rates)):\n",
    "    initial_w_0 = 0\n",
    "    initial_w_1 = 0\n",
    "    learning_rate = l_rates[i]\n",
    "    w_0,w_1 = gradient_descent(data,initial_w_0,initial_w_1,learning_rate,num_iterations)\n",
    "    all_params.append((w_0,w_1))\n",
    "    print(\"learning_rate: {:.4f} => w_0 = {}, w_1 = {}\".format(learning_rate,w_0,w_1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graduate Admission Prediction\n",
    "\n",
    "We are going to use a dataset to predict the chance of getting admission in graduate school from the perspective of Indian students. The dataset is available at [this link](https://www.kaggle.com/mohansacharya/graduate-admissions)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Content\n",
    "\n",
    "The dataset contains several parameters which are considered important during the application for Masters Programs.\n",
    "The parameters included are :\n",
    "\n",
    "- GRE Scores ( out of 340 )\n",
    "\n",
    "- TOEFL Scores ( out of 120 )\n",
    "\n",
    "- University Rating ( out of 5 )\n",
    "\n",
    "- Statement of Purpose and Letter of Recommendation Strength ( out of 5 )\n",
    "\n",
    "- Undergraduate GPA ( out of 10 )\n",
    "\n",
    "- Research Experience ( either 0 or 1 )\n",
    "\n",
    "- Chance of Admit ( ranging from 0 to 1 )\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Acknowledgements\n",
    "\n",
    "This dataset is inspired by the UCLA Graduate Dataset. The test scores and GPA are in the older format.\n",
    "The dataset is owned by Mohan S Acharya."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's code it up!\n",
    "\n",
    "We are using [Turi Create library](https://github.com/apple/turicreate)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre>Finished parsing file /Users/mehdi/git_repos/ml_tutorial/data/admission_predict.csv</pre>"
      ],
      "text/plain": [
       "Finished parsing file /Users/mehdi/git_repos/ml_tutorial/data/admission_predict.csv"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre>Parsing completed. Parsed 100 lines in 0.036391 secs.</pre>"
      ],
      "text/plain": [
       "Parsing completed. Parsed 100 lines in 0.036391 secs."
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "------------------------------------------------------\n",
      "Inferred types from first 100 line(s) of file as \n",
      "column_type_hints=[int,int,int,int,float,float,float,int,float]\n",
      "If parsing fails due to incorrect types, you can correct\n",
      "the inferred type list above and pass it to read_csv in\n",
      "the column_type_hints argument\n",
      "------------------------------------------------------\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre>Finished parsing file /Users/mehdi/git_repos/ml_tutorial/data/admission_predict.csv</pre>"
      ],
      "text/plain": [
       "Finished parsing file /Users/mehdi/git_repos/ml_tutorial/data/admission_predict.csv"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre>Parsing completed. Parsed 500 lines in 0.005148 secs.</pre>"
      ],
      "text/plain": [
       "Parsing completed. Parsed 500 lines in 0.005148 secs."
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import turicreate as tc\n",
    "import os\n",
    "\n",
    "\n",
    "# Load the data\n",
    "file_name = os.path.join(\"data\",\"admission_predict.csv\")\n",
    "data = tc.SFrame(file_name)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#hide\n",
    "# data.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Split the data into train and test sets\n",
    "train_data, test_data = data.random_split(0.8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PROGRESS: Creating a validation set from 5 percent of training data. This may take a while.\n",
      "          You can set ``validation_set=None`` to disable validation tracking.\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre>Linear regression:</pre>"
      ],
      "text/plain": [
       "Linear regression:"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre>--------------------------------------------------------</pre>"
      ],
      "text/plain": [
       "--------------------------------------------------------"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre>Number of examples          : 382</pre>"
      ],
      "text/plain": [
       "Number of examples          : 382"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre>Number of features          : 7</pre>"
      ],
      "text/plain": [
       "Number of features          : 7"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre>Number of unpacked features : 7</pre>"
      ],
      "text/plain": [
       "Number of unpacked features : 7"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre>Number of coefficients    : 8</pre>"
      ],
      "text/plain": [
       "Number of coefficients    : 8"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre>Starting Newton Method</pre>"
      ],
      "text/plain": [
       "Starting Newton Method"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre>--------------------------------------------------------</pre>"
      ],
      "text/plain": [
       "--------------------------------------------------------"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre>+-----------+----------+--------------+--------------------+----------------------+---------------------------------+-----------------------------------+</pre>"
      ],
      "text/plain": [
       "+-----------+----------+--------------+--------------------+----------------------+---------------------------------+-----------------------------------+"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre>| Iteration | Passes   | Elapsed Time | Training Max Error | Validation Max Error | Training Root-Mean-Square Error | Validation Root-Mean-Square Error |</pre>"
      ],
      "text/plain": [
       "| Iteration | Passes   | Elapsed Time | Training Max Error | Validation Max Error | Training Root-Mean-Square Error | Validation Root-Mean-Square Error |"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre>+-----------+----------+--------------+--------------------+----------------------+---------------------------------+-----------------------------------+</pre>"
      ],
      "text/plain": [
       "+-----------+----------+--------------+--------------------+----------------------+---------------------------------+-----------------------------------+"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre>| 1         | 2        | 1.008480     | 0.263005           | 0.161696             | 0.060754                        | 0.058639                          |</pre>"
      ],
      "text/plain": [
       "| 1         | 2        | 1.008480     | 0.263005           | 0.161696             | 0.060754                        | 0.058639                          |"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre>+-----------+----------+--------------+--------------------+----------------------+---------------------------------+-----------------------------------+</pre>"
      ],
      "text/plain": [
       "+-----------+----------+--------------+--------------------+----------------------+---------------------------------+-----------------------------------+"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre>SUCCESS: Optimal solution found.</pre>"
      ],
      "text/plain": [
       "SUCCESS: Optimal solution found."
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre></pre>"
      ],
      "text/plain": []
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Create the model and automatically pick the right model for the data\n",
    "model = tc.linear_regression.create(train_data, target=\"Chance of Admit\", \n",
    "                                                features=[\"GRE Score\",\"TOEFL Score\",\"University Rating\",\"SOP\",\"LOR\" ,\"CGPA\",\"Research\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div style=\"max-height:1000px;max-width:1500px;overflow:auto;\"><table frame=\"box\" rules=\"cols\">\n",
       "    <tr>\n",
       "        <th style=\"padding-left: 1em; padding-right: 1em; text-align: center\">name</th>\n",
       "        <th style=\"padding-left: 1em; padding-right: 1em; text-align: center\">index</th>\n",
       "        <th style=\"padding-left: 1em; padding-right: 1em; text-align: center\">value</th>\n",
       "        <th style=\"padding-left: 1em; padding-right: 1em; text-align: center\">stderr</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">(intercept)</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">None</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">-1.2194234077908317</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">0.12345599580590878</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">GRE Score</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">None</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">0.001618826787445662</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">0.0005996922897142088</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">TOEFL Score</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">None</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">0.002719675267851057</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">0.0010471136127637685</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">University Rating</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">None</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">0.0055687118093857325</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">0.004480660941075841</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">SOP</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">None</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">0.003933393122657006</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">0.005291439585231497</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">LOR</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">None</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">0.01230804029449188</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">0.004900628289324322</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">CGPA</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">None</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">0.12190995423260485</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">0.011405325159564978</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">Research</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">None</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">0.030518127884338626</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">0.007681798415697063</td>\n",
       "    </tr>\n",
       "</table>\n",
       "[8 rows x 4 columns]<br/>\n",
       "</div>"
      ],
      "text/plain": [
       "Columns:\n",
       "\tname\tstr\n",
       "\tindex\tstr\n",
       "\tvalue\tfloat\n",
       "\tstderr\tfloat\n",
       "\n",
       "Rows: 8\n",
       "\n",
       "Data:\n",
       "+-------------------+-------+-----------------------+-----------------------+\n",
       "|        name       | index |         value         |         stderr        |\n",
       "+-------------------+-------+-----------------------+-----------------------+\n",
       "|    (intercept)    |  None |  -1.2194234077908317  |  0.12345599580590878  |\n",
       "|     GRE Score     |  None |  0.001618826787445662 | 0.0005996922897142088 |\n",
       "|    TOEFL Score    |  None |  0.002719675267851057 | 0.0010471136127637685 |\n",
       "| University Rating |  None | 0.0055687118093857325 |  0.004480660941075841 |\n",
       "|        SOP        |  None |  0.003933393122657006 |  0.005291439585231497 |\n",
       "|        LOR        |  None |  0.01230804029449188  |  0.004900628289324322 |\n",
       "|        CGPA       |  None |  0.12190995423260485  |  0.011405325159564978 |\n",
       "|      Research     |  None |  0.030518127884338626 |  0.007681798415697063 |\n",
       "+-------------------+-------+-----------------------+-----------------------+\n",
       "[8 rows x 4 columns]"
      ]
     },
     "execution_count": null,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "model.coefficients"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Do the prediction and save them into an array\n",
    "predictions = model.predict(test_data)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'max_error': 0.16061435621560105, 'rmse': 0.05529337777075813}"
      ]
     },
     "execution_count": null,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Evaluate the model and save the results\n",
    "results = model.evaluate(test_data)\n",
    "results"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}