C1_W2_Linear_Regression.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Practice Lab: Linear Regression\n",
    "\n",
    "Welcome to your first practice lab! In this lab, you will implement linear regression with one variable to predict profits for a restaurant franchise.\n",
    "\n",
    "\n",
    "# Outline\n",
    "- [ 1 - Packages ](#1)\n",
    "- [ 2 - Linear regression with one variable ](#2)\n",
    "  - [ 2.1 Problem Statement](#2.1)\n",
    "  - [ 2.2  Dataset](#2.2)\n",
    "  - [ 2.3 Refresher on linear regression](#2.3)\n",
    "  - [ 2.4  Compute Cost](#2.4)\n",
    "    - [ Exercise 1](#ex01)\n",
    "  - [ 2.5 Gradient descent ](#2.5)\n",
    "    - [ Exercise 2](#ex02)\n",
    "  - [ 2.6 Learning parameters using batch gradient descent ](#2.6)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"1\"></a>\n",
    "## 1 - Packages \n",
    "\n",
    "First, let's run the cell below to import all the packages that you will need during this assignment.\n",
    "- [numpy](www.numpy.org) is the fundamental package for working with matrices in Python.\n",
    "- [matplotlib](http://matplotlib.org) is a famous library to plot graphs in Python.\n",
    "- ``utils.py`` contains helper functions for this assignment. You do not need to modify code in this file.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from utils import *\n",
    "import copy\n",
    "import math\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 -  Problem Statement\n",
    "\n",
    "Suppose you are the CEO of a restaurant franchise and are considering different cities for opening a new outlet.\n",
    "- You would like to expand your business to cities that may give your restaurant higher profits.\n",
    "- The chain already has restaurants in various cities and you have data for profits and populations from the cities.\n",
    "- You also have data on cities that are candidates for a new restaurant. \n",
    "    - For these cities, you have the city population.\n",
    "    \n",
    "Can you use the data to help you identify which cities may potentially give your business higher profits?\n",
    "\n",
    "## 3 - Dataset\n",
    "\n",
    "You will start by loading the dataset for this task. \n",
    "- The `load_data()` function shown below loads the data into variables `x_train` and `y_train`\n",
    "  - `x_train` is the population of a city\n",
    "  - `y_train` is the profit of a restaurant in that city. A negative value for profit indicates a loss.   \n",
    "  - Both `X_train` and `y_train` are numpy arrays."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# load the dataset\n",
    "x_train, y_train = load_data()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### View the variables\n",
    "Before starting on any task, it is useful to get more familiar with your dataset.  \n",
    "- A good place to start is to just print out each variable and see what it contains.\n",
    "\n",
    "The code below prints the variable `x_train` and the type of the variable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# print x_train\n",
    "print(\"Type of x_train:\",type(x_train))\n",
    "print(\"First five elements of x_train are:\\n\", x_train[:5]) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`x_train` is a numpy array that contains decimal values that are all greater than zero.\n",
    "- These values represent the city population times 10,000\n",
    "- For example, 6.1101 means that the population for that city is 61,101\n",
    "  \n",
    "Now, let's print `y_train`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# print y_train\n",
    "print(\"Type of y_train:\",type(y_train))\n",
    "print(\"First five elements of y_train are:\\n\", y_train[:5])  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly, `y_train` is a numpy array that has decimal values, some negative, some positive.\n",
    "- These represent your restaurant's average monthly profits in each city, in units of \\$10,000.\n",
    "  - For example, 17.592 represents \\$175,920 in average monthly profits for that city.\n",
    "  - -2.6807 represents -\\$26,807 in average monthly loss for that city."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Check the dimensions of your variables\n",
    "\n",
    "Another useful way to get familiar with your data is to view its dimensions.\n",
    "\n",
    "Please print the shape of `x_train` and `y_train` and see how many training examples you have in your dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print ('The shape of x_train is:', x_train.shape)\n",
    "print ('The shape of y_train is: ', y_train.shape)\n",
    "print ('Number of training examples (m):', len(x_train))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The city population array has 97 data points, and the monthly average profits also has 97 data points. These are NumPy 1D arrays."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Visualize your data\n",
    "\n",
    "It is often useful to understand the data by visualizing it. \n",
    "- For this dataset, you can use a scatter plot to visualize the data, since it has only two properties to plot (profit and population). \n",
    "- Many other problems that you will encounter in real life have more than two properties (for example, population, average household income, monthly profits, monthly sales).When you have more than two properties, you can still use a scatter plot to see the relationship between each pair of properties.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create a scatter plot of the data. To change the markers to red \"x\",\n",
    "# we used the 'marker' and 'c' parameters\n",
    "plt.scatter(x_train, y_train, marker='x', c='r') \n",
    "\n",
    "# Set the title\n",
    "plt.title(\"Profits vs. Population per city\")\n",
    "# Set the y-axis label\n",
    "plt.ylabel('Profit in $10,000')\n",
    "# Set the x-axis label\n",
    "plt.xlabel('Population of City in 10,000s')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Your goal is to build a linear regression model to fit this data.\n",
    "- With this model, you can then input a new city's population, and have the model estimate your restaurant's potential monthly profits for that city."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"4\"></a>\n",
    "## 4 - Refresher on linear regression\n",
    "\n",
    "In this practice lab, you will fit the linear regression parameters $(w,b)$ to your dataset.\n",
    "- The model function for linear regression, which is a function that maps from `x` (city population) to `y` (your restaurant's monthly profit for that city) is represented as \n",
    "    $$f_{w,b}(x) = wx + b$$\n",
    "    \n",
    "\n",
    "- To train a linear regression model, you want to find the best $(w,b)$ parameters that fit your dataset.  \n",
    "\n",
    "    - To compare how one choice of $(w,b)$ is better or worse than another choice, you can evaluate it with a cost function $J(w,b)$\n",
    "      - $J$ is a function of $(w,b)$. That is, the value of the cost $J(w,b)$ depends on the value of $(w,b)$.\n",
    "  \n",
    "    - The choice of $(w,b)$ that fits your data the best is the one that has the smallest cost $J(w,b)$.\n",
    "\n",
    "\n",
    "- To find the values $(w,b)$ that gets the smallest possible cost $J(w,b)$, you can use a method called **gradient descent**. \n",
    "  - With each step of gradient descent, your parameters $(w,b)$ come closer to the optimal values that will achieve the lowest cost $J(w,b)$.\n",
    "  \n",
    "\n",
    "- The trained linear regression model can then take the input feature $x$ (city population) and output a prediction $f_{w,b}(x)$ (predicted monthly profit for a restaurant in that city)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"5\"></a>\n",
    "## 5 - Compute Cost\n",
    "\n",
    "Gradient descent involves repeated steps to adjust the value of your parameter $(w,b)$ to gradually get a smaller and smaller cost $J(w,b)$.\n",
    "- At each step of gradient descent, it will be helpful for you to monitor your progress by computing the cost $J(w,b)$ as $(w,b)$ gets updated. \n",
    "- In this section, you will implement a function to calculate $J(w,b)$ so that you can check the progress of your gradient descent implementation.\n",
    "\n",
    "#### Cost function\n",
    "As you may recall from the lecture, for one variable, the cost function for linear regression $J(w,b)$ is defined as\n",
    "\n",
    "$$J(w,b) = \\frac{1}{2m} \\sum\\limits_{i = 0}^{m-1} (f_{w,b}(x^{(i)}) - y^{(i)})^2$$ \n",
    "\n",
    "- You can think of $f_{w,b}(x^{(i)})$ as the model's prediction of your restaurant's profit, as opposed to $y^{(i)}$, which is the actual profit that is recorded in the data.\n",
    "- $m$ is the number of training examples in the dataset\n",
    "\n",
    "#### Model prediction\n",
    "\n",
    "- For linear regression with one variable, the prediction of the model $f_{w,b}$ for an example $x^{(i)}$ is representented as:\n",
    "\n",
    "$$ f_{w,b}(x^{(i)}) = wx^{(i)} + b$$\n",
    "\n",
    "This is the equation for a line, with an intercept $b$ and a slope $w$\n",
    "\n",
    "#### Implementation\n",
    "\n",
    "Please complete the `compute_cost()` function below to compute the cost $J(w,b)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"ex01\"></a>\n",
    "### Exercise 1\n",
    "\n",
    "Complete the `compute_cost` below to:\n",
    "\n",
    "* Iterate over the training examples, and for each example, compute:\n",
    "    * The prediction of the model for that example \n",
    "    $$\n",
    "    f_{wb}(x^{(i)}) =  wx^{(i)} + b \n",
    "    $$\n",
    "   \n",
    "    * The cost for that example  $$cost^{(i)} =  (f_{wb} - y^{(i)})^2$$\n",
    "    \n",
    "\n",
    "* Return the total cost over all examples\n",
    "$$J(\\mathbf{w},b) = \\frac{1}{2m} \\sum\\limits_{i = 0}^{m-1} cost^{(i)}$$\n",
    "  * Here, $m$ is the number of training examples and $\\sum$ is the summation operator\n",
    "\n",
    "If you get stuck, you can check out the hints presented after the cell below to help you with the implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# UNQ_C1\n",
    "# GRADED FUNCTION: compute_cost\n",
    "\n",
    "def compute_cost(x, y, w, b): \n",
    "    \"\"\"\n",
    "    Computes the cost function for linear regression.\n",
    "    \n",
    "    Args:\n",
    "        x (ndarray): Shape (m,) Input to the model (Population of cities) \n",
    "        y (ndarray): Shape (m,) Label (Actual profits for the cities)\n",
    "        w, b (scalar): Parameters of the model\n",
    "    \n",
    "    Returns\n",
    "        total_cost (float): The cost of using w,b as the parameters for linear regression\n",
    "               to fit the data points in x and y\n",
    "    \"\"\"\n",
    "    # number of training examples\n",
    "    m = x.shape[0] \n",
    "    \n",
    "    # You need to return this variable correctly\n",
    "    total_cost = 0\n",
    "    \n",
    "    ### START CODE HERE ###  \n",
    "    \n",
    "    ### END CODE HERE ### \n",
    "\n",
    "    return total_cost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "  <summary><font size=\"3\" color=\"darkgreen\"><b>Click for hints</b></font></summary>\n",
    "    \n",
    "    \n",
    "   * You can represent a summation operator eg: $h = \\sum\\limits_{i = 0}^{m-1} 2i$ in code as follows:\n",
    "     ```python \n",
    "    h = 0\n",
    "    for i in range(m):\n",
    "        h = h + 2*i\n",
    "    ```\n",
    "  \n",
    "   * In this case, you can iterate over all the examples in `x` using a for loop and add the `cost` from each iteration to a variable (`cost_sum`) initialized outside the loop.\n",
    "\n",
    "   * Then, you can return the `total_cost` as `cost_sum` divided by `2m`.\n",
    "     \n",
    "    <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b> Click for more hints</b></font></summary>\n",
    "        \n",
    "    * Here's how you can structure the overall implementation for this function\n",
    "    ```python \n",
    "    def compute_cost(x, y, w, b):\n",
    "        # number of training examples\n",
    "        m = x.shape[0] \n",
    "    \n",
    "        # You need to return this variable correctly\n",
    "        total_cost = 0\n",
    "    \n",
    "        ### START CODE HERE ###  \n",
    "        # Variable to keep track of sum of cost from each example\n",
    "        cost_sum = 0\n",
    "    \n",
    "        # Loop over training examples\n",
    "        for i in range(m):\n",
    "            # Your code here to get the prediction f_wb for the ith example\n",
    "            f_wb = \n",
    "            # Your code here to get the cost associated with the ith example\n",
    "            cost = \n",
    "        \n",
    "            # Add to sum of cost for each example\n",
    "            cost_sum = cost_sum + cost \n",
    "\n",
    "        # Get the total cost as the sum divided by (2*m)\n",
    "        total_cost = (1 / (2 * m)) * cost_sum\n",
    "        ### END CODE HERE ### \n",
    "\n",
    "        return total_cost\n",
    "    ```\n",
    "    \n",
    "    If you're still stuck, you can check the hints presented below to figure out how to calculate `f_wb` and `cost`.\n",
    "    \n",
    "    <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b>Hint to calculate f_wb</b></font></summary>\n",
    "           &emsp; &emsp; For scalars $a$, $b$ and $c$ (<code>x[i]</code>, <code>w</code> and <code>b</code> are all scalars), you can calculate the equation $h = ab + c$ in code as <code>h = a * b + c</code>\n",
    "          <details>\n",
    "              <summary><font size=\"2\" color=\"blue\"><b>&emsp; &emsp; More hints to calculate f</b></font></summary>\n",
    "               &emsp; &emsp; You can compute f_wb as <code>f_wb = w * x[i] + b </code>\n",
    "           </details>\n",
    "    </details>\n",
    "\n",
    "     <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b>Hint to calculate cost</b></font></summary>\n",
    "          &emsp; &emsp; You can calculate the square of a variable z as z**2\n",
    "          <details>\n",
    "              <summary><font size=\"2\" color=\"blue\"><b>&emsp; &emsp; More hints to calculate cost</b></font></summary>\n",
    "              &emsp; &emsp; You can compute cost as <code>cost = (f_wb - y[i]) ** 2</code>\n",
    "          </details>\n",
    "    </details>\n",
    "        \n",
    "    </details>\n",
    "\n",
    "</details>\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can check if your implementation was correct by running the following test code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Compute cost with some initial values for paramaters w, b\n",
    "initial_w = 2\n",
    "initial_b = 1\n",
    "\n",
    "cost = compute_cost(x_train, y_train, initial_w, initial_b)\n",
    "print(type(cost))\n",
    "print(f'Cost at initial w: {cost:.3f}')\n",
    "\n",
    "# Public tests\n",
    "from public_tests import *\n",
    "compute_cost_test(compute_cost)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected Output**:\n",
    "<table>\n",
    "  <tr>\n",
    "    <td> <b>Cost at initial w:<b> 75.203 </td> \n",
    "  </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"6\"></a>\n",
    "## 6 - Gradient descent \n",
    "\n",
    "In this section, you will implement the gradient for parameters $w, b$ for linear regression. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As described in the lecture videos, the gradient descent algorithm is:\n",
    "\n",
    "$$\\begin{align*}& \\text{repeat until convergence:} \\; \\lbrace \\newline \\; & \\phantom {0000} b := b -  \\alpha \\frac{\\partial J(w,b)}{\\partial b} \\newline       \\; & \\phantom {0000} w := w -  \\alpha \\frac{\\partial J(w,b)}{\\partial w} \\tag{1}  \\; & \n",
    "\\newline & \\rbrace\\end{align*}$$\n",
    "\n",
    "where, parameters $w, b$ are both updated simultaniously and where  \n",
    "$$\n",
    "\\frac{\\partial J(w,b)}{\\partial b}  = \\frac{1}{m} \\sum\\limits_{i = 0}^{m-1} (f_{w,b}(x^{(i)}) - y^{(i)}) \\tag{2}\n",
    "$$\n",
    "$$\n",
    "\\frac{\\partial J(w,b)}{\\partial w}  = \\frac{1}{m} \\sum\\limits_{i = 0}^{m-1} (f_{w,b}(x^{(i)}) -y^{(i)})x^{(i)} \\tag{3}\n",
    "$$\n",
    "* m is the number of training examples in the dataset\n",
    "\n",
    "    \n",
    "*  $f_{w,b}(x^{(i)})$ is the model's prediction, while $y^{(i)}$, is the target value\n",
    "\n",
    "\n",
    "You will implement a function called `compute_gradient` which calculates $\\frac{\\partial J(w)}{\\partial w}$, $\\frac{\\partial J(w)}{\\partial b}$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"ex02\"></a>\n",
    "### Exercise 2\n",
    "\n",
    "Please complete the `compute_gradient` function to:\n",
    "\n",
    "* Iterate over the training examples, and for each example, compute:\n",
    "    * The prediction of the model for that example \n",
    "    $$\n",
    "    f_{wb}(x^{(i)}) =  wx^{(i)} + b \n",
    "    $$\n",
    "   \n",
    "    * The gradient for the parameters $w, b$ from that example \n",
    "        $$\n",
    "        \\frac{\\partial J(w,b)}{\\partial b}^{(i)}  =  (f_{w,b}(x^{(i)}) - y^{(i)}) \n",
    "        $$\n",
    "        $$\n",
    "        \\frac{\\partial J(w,b)}{\\partial w}^{(i)}  =  (f_{w,b}(x^{(i)}) -y^{(i)})x^{(i)} \n",
    "        $$\n",
    "    \n",
    "\n",
    "* Return the total gradient update from all the examples\n",
    "    $$\n",
    "    \\frac{\\partial J(w,b)}{\\partial b}  = \\frac{1}{m} \\sum\\limits_{i = 0}^{m-1} \\frac{\\partial J(w,b)}{\\partial b}^{(i)}\n",
    "    $$\n",
    "    \n",
    "    $$\n",
    "    \\frac{\\partial J(w,b)}{\\partial w}  = \\frac{1}{m} \\sum\\limits_{i = 0}^{m-1} \\frac{\\partial J(w,b)}{\\partial w}^{(i)} \n",
    "    $$\n",
    "  * Here, $m$ is the number of training examples and $\\sum$ is the summation operator\n",
    "\n",
    "If you get stuck, you can check out the hints presented after the cell below to help you with the implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# UNQ_C2\n",
    "# GRADED FUNCTION: compute_gradient\n",
    "def compute_gradient(x, y, w, b): \n",
    "    \"\"\"\n",
    "    Computes the gradient for linear regression \n",
    "    Args:\n",
    "      x (ndarray): Shape (m,) Input to the model (Population of cities) \n",
    "      y (ndarray): Shape (m,) Label (Actual profits for the cities)\n",
    "      w, b (scalar): Parameters of the model  \n",
    "    Returns\n",
    "      dj_dw (scalar): The gradient of the cost w.r.t. the parameters w\n",
    "      dj_db (scalar): The gradient of the cost w.r.t. the parameter b     \n",
    "     \"\"\"\n",
    "    \n",
    "    # Number of training examples\n",
    "    m = x.shape[0]\n",
    "    \n",
    "    # You need to return the following variables correctly\n",
    "    dj_dw = 0\n",
    "    dj_db = 0\n",
    "    \n",
    "    ### START CODE HERE ### \n",
    "    \n",
    "    ### END CODE HERE ### \n",
    "        \n",
    "    return dj_dw, dj_db"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "  <summary><font size=\"3\" color=\"darkgreen\"><b>Click for hints</b></font></summary>\n",
    "       \n",
    "    * You can represent a summation operator eg: $h = \\sum\\limits_{i = 0}^{m-1} 2i$ in code as follows:\n",
    "     ```python \n",
    "    h = 0\n",
    "    for i in range(m):\n",
    "        h = h + 2*i\n",
    "    ```\n",
    "    \n",
    "    * In this case, you can iterate over all the examples in `x` using a for loop and for each example, keep adding the gradient from that example to the variables `dj_dw` and `dj_db` which are initialized outside the loop. \n",
    "\n",
    "   * Then, you can return `dj_dw` and `dj_db` both divided by `m`.    \n",
    "    <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b> Click for more hints</b></font></summary>\n",
    "        \n",
    "    * Here's how you can structure the overall implementation for this function\n",
    "    ```python \n",
    "    def compute_gradient(x, y, w, b): \n",
    "        \"\"\"\n",
    "        Computes the gradient for linear regression \n",
    "        Args:\n",
    "          x (ndarray): Shape (m,) Input to the model (Population of cities) \n",
    "          y (ndarray): Shape (m,) Label (Actual profits for the cities)\n",
    "          w, b (scalar): Parameters of the model  \n",
    "        Returns\n",
    "          dj_dw (scalar): The gradient of the cost w.r.t. the parameters w\n",
    "          dj_db (scalar): The gradient of the cost w.r.t. the parameter b     \n",
    "         \"\"\"\n",
    "    \n",
    "        # Number of training examples\n",
    "        m = x.shape[0]\n",
    "    \n",
    "        # You need to return the following variables correctly\n",
    "        dj_dw = 0\n",
    "        dj_db = 0\n",
    "    \n",
    "        ### START CODE HERE ### \n",
    "        # Loop over examples\n",
    "        for i in range(m):  \n",
    "            # Your code here to get prediction f_wb for the ith example\n",
    "            f_wb = \n",
    "            \n",
    "            # Your code here to get the gradient for w from the ith example \n",
    "            dj_dw_i = \n",
    "        \n",
    "            # Your code here to get the gradient for b from the ith example \n",
    "            dj_db_i = \n",
    "     \n",
    "            # Update dj_db : In Python, a += 1  is the same as a = a + 1\n",
    "            dj_db += dj_db_i\n",
    "        \n",
    "            # Update dj_dw\n",
    "            dj_dw += dj_dw_i\n",
    "    \n",
    "        # Divide both dj_dw and dj_db by m\n",
    "        dj_dw = dj_dw / m\n",
    "        dj_db = dj_db / m\n",
    "        ### END CODE HERE ### \n",
    "        \n",
    "        return dj_dw, dj_db\n",
    "    ```\n",
    "    \n",
    "    If you're still stuck, you can check the hints presented below to figure out how to calculate `f_wb` and `cost`.\n",
    "    \n",
    "    <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b>Hint to calculate f_wb</b></font></summary>\n",
    "           &emsp; &emsp; You did this in the previous exercise! For scalars $a$, $b$ and $c$ (<code>x[i]</code>, <code>w</code> and <code>b</code> are all scalars), you can calculate the equation $h = ab + c$ in code as <code>h = a * b + c</code>\n",
    "          <details>\n",
    "              <summary><font size=\"2\" color=\"blue\"><b>&emsp; &emsp; More hints to calculate f</b></font></summary>\n",
    "               &emsp; &emsp; You can compute f_wb as <code>f_wb = w * x[i] + b </code>\n",
    "           </details>\n",
    "    </details>\n",
    "        \n",
    "    <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b>Hint to calculate dj_dw_i</b></font></summary>\n",
    "           &emsp; &emsp; For scalars $a$, $b$ and $c$ (<code>f_wb</code>, <code>y[i]</code> and <code>x[i]</code> are all scalars), you can calculate the equation $h = (a - b)c$ in code as <code>h = (a-b)*c</code>\n",
    "          <details>\n",
    "              <summary><font size=\"2\" color=\"blue\"><b>&emsp; &emsp; More hints to calculate f</b></font></summary>\n",
    "               &emsp; &emsp; You can compute dj_dw_i as <code>dj_dw_i = (f_wb - y[i]) * x[i] </code>\n",
    "           </details>\n",
    "    </details>\n",
    "        \n",
    "    <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b>Hint to calculate dj_db_i</b></font></summary>\n",
    "             &emsp; &emsp; You can compute dj_db_i as <code> dj_db_i = f_wb - y[i] </code>\n",
    "    </details>\n",
    "        \n",
    "    </details>\n",
    "\n",
    "</details>\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the cells below to check your implementation of the `compute_gradient` function with two different initializations of the parameters $w$,$b$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Compute and display gradient with w initialized to zeroes\n",
    "initial_w = 0\n",
    "initial_b = 0\n",
    "\n",
    "tmp_dj_dw, tmp_dj_db = compute_gradient(x_train, y_train, initial_w, initial_b)\n",
    "print('Gradient at initial w, b (zeros):', tmp_dj_dw, tmp_dj_db)\n",
    "\n",
    "compute_gradient_test(compute_gradient)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's run the gradient descent algorithm implemented above on our dataset.\n",
    "\n",
    "**Expected Output**:\n",
    "<table>\n",
    "  <tr>\n",
    "    <td> <b>Gradient at initial , b (zeros)<b></td>\n",
    "    <td> -65.32884975 -5.83913505154639</td> \n",
    "  </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Compute and display cost and gradient with non-zero w\n",
    "test_w = 0.2\n",
    "test_b = 0.2\n",
    "tmp_dj_dw, tmp_dj_db = compute_gradient(x_train, y_train, test_w, test_b)\n",
    "\n",
    "print('Gradient at test w, b:', tmp_dj_dw, tmp_dj_db)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected Output**:\n",
    "<table>\n",
    "  <tr>\n",
    "    <td> <b>Gradient at test w<b></td>\n",
    "    <td> -47.41610118 -4.007175051546391</td> \n",
    "  </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"2.6\"></a>\n",
    "### 2.6 Learning parameters using batch gradient descent \n",
    "\n",
    "You will now find the optimal parameters of a linear regression model by using batch gradient descent. Recall batch refers to running all the examples in one iteration.\n",
    "- You don't need to implement anything for this part. Simply run the cells below. \n",
    "\n",
    "- A good way to verify that gradient descent is working correctly is to look\n",
    "at the value of $J(w,b)$ and check that it is decreasing with each step. \n",
    "\n",
    "- Assuming you have implemented the gradient and computed the cost correctly and you have an appropriate value for the learning rate alpha, $J(w,b)$ should never increase and should converge to a steady value by the end of the algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gradient_descent(x, y, w_in, b_in, cost_function, gradient_function, alpha, num_iters): \n",
    "    \"\"\"\n",
    "    Performs batch gradient descent to learn theta. Updates theta by taking \n",
    "    num_iters gradient steps with learning rate alpha\n",
    "    \n",
    "    Args:\n",
    "      x :    (ndarray): Shape (m,)\n",
    "      y :    (ndarray): Shape (m,)\n",
    "      w_in, b_in : (scalar) Initial values of parameters of the model\n",
    "      cost_function: function to compute cost\n",
    "      gradient_function: function to compute the gradient\n",
    "      alpha : (float) Learning rate\n",
    "      num_iters : (int) number of iterations to run gradient descent\n",
    "    Returns\n",
    "      w : (ndarray): Shape (1,) Updated values of parameters of the model after\n",
    "          running gradient descent\n",
    "      b : (scalar)                Updated value of parameter of the model after\n",
    "          running gradient descent\n",
    "    \"\"\"\n",
    "    \n",
    "    # number of training examples\n",
    "    m = len(x)\n",
    "    \n",
    "    # An array to store cost J and w's at each iteration — primarily for graphing later\n",
    "    J_history = []\n",
    "    w_history = []\n",
    "    w = copy.deepcopy(w_in)  #avoid modifying global w within function\n",
    "    b = b_in\n",
    "    \n",
    "    for i in range(num_iters):\n",
    "\n",
    "        # Calculate the gradient and update the parameters\n",
    "        dj_dw, dj_db = gradient_function(x, y, w, b )  \n",
    "\n",
    "        # Update Parameters using w, b, alpha and gradient\n",
    "        w = w - alpha * dj_dw               \n",
    "        b = b - alpha * dj_db               \n",
    "\n",
    "        # Save cost J at each iteration\n",
    "        if i<100000:      # prevent resource exhaustion \n",
    "            cost =  cost_function(x, y, w, b)\n",
    "            J_history.append(cost)\n",
    "\n",
    "        # Print cost every at intervals 10 times or as many iterations if < 10\n",
    "        if i% math.ceil(num_iters/10) == 0:\n",
    "            w_history.append(w)\n",
    "            print(f\"Iteration {i:4}: Cost {float(J_history[-1]):8.2f}   \")\n",
    "        \n",
    "    return w, b, J_history, w_history #return w and J,w history for graphing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's run the gradient descent algorithm above to learn the parameters for our dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# initialize fitting parameters. Recall that the shape of w is (n,)\n",
    "initial_w = 0.\n",
    "initial_b = 0.\n",
    "\n",
    "# some gradient descent settings\n",
    "iterations = 1500\n",
    "alpha = 0.01\n",
    "\n",
    "w,b,_,_ = gradient_descent(x_train ,y_train, initial_w, initial_b, \n",
    "                     compute_cost, compute_gradient, alpha, iterations)\n",
    "print(\"w,b found by gradient descent:\", w, b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected Output**:\n",
    "<table>\n",
    "  <tr>\n",
    "    <td> <b> w, b found by gradient descent<b></td>\n",
    "    <td> 1.16636235 -3.63029143940436</td> \n",
    "  </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will now use the final parameters from gradient descent to plot the linear fit. \n",
    "\n",
    "Recall that we can get the prediction for a single example $f(x^{(i)})= wx^{(i)}+b$. \n",
    "\n",
    "To calculate the predictions on the entire dataset, we can loop through all the training examples and calculate the prediction for each example. This is shown in the code block below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = x_train.shape[0]\n",
    "predicted = np.zeros(m)\n",
    "\n",
    "for i in range(m):\n",
    "    predicted[i] = w * x_train[i] + b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will now plot the predicted values to see the linear fit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Plot the linear fit\n",
    "plt.plot(x_train, predicted, c = \"b\")\n",
    "\n",
    "# Create a scatter plot of the data. \n",
    "plt.scatter(x_train, y_train, marker='x', c='r') \n",
    "\n",
    "# Set the title\n",
    "plt.title(\"Profits vs. Population per city\")\n",
    "# Set the y-axis label\n",
    "plt.ylabel('Profit in $10,000')\n",
    "# Set the x-axis label\n",
    "plt.xlabel('Population of City in 10,000s')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Your final values of $w,b$ can also be used to make predictions on profits. Let's predict what the profit would be in areas of 35,000 and 70,000 people. \n",
    "\n",
    "- The model takes in population of a city in 10,000s as input. \n",
    "\n",
    "- Therefore, 35,000 people can be translated into an input to the model as `np.array([3.5])`\n",
    "\n",
    "- Similarly, 70,000 people can be translated into an input to the model as `np.array([7.])`\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "predict1 = 3.5 * w + b\n",
    "print('For population = 35,000, we predict a profit of $%.2f' % (predict1*10000))\n",
    "\n",
    "predict2 = 7.0 * w + b\n",
    "print('For population = 70,000, we predict a profit of $%.2f' % (predict2*10000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected Output**:\n",
    "<table>\n",
    "  <tr>\n",
    "    <td> <b> For population = 35,000, we predict a profit of<b></td>\n",
    "    <td> $4519.77 </td> \n",
    "  </tr>\n",
    "  \n",
    "  <tr>\n",
    "    <td> <b> For population = 70,000, we predict a profit of<b></td>\n",
    "    <td> $45342.45 </td> \n",
    "  </tr>\n",
    "</table>"
   ]
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}