Labs/lab08.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [],
   "source": [
    "# Initialize Otter\n",
    "import otter\n",
    "grader = otter.Notebook(\"lab08.ipynb\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "intro",
     "locked": true,
     "schema_version": 2,
     "solution": false
    }
   },
   "source": [
    "# Lab 8: Multiple Linear Regression and Feature Engineering\n",
    "\n",
    "In this lab, we will work through the process of:\n",
    "1. Implementing a linear model \n",
    "1. Defining loss functions\n",
    "1. Feature engineering\n",
    "1. Minimizing loss functions using numeric methods and analytical methods \n",
    "\n",
    "This lab will continue using the toy `tips` calculation dataset used in Labs 6 and 7.\n",
    "\n",
    "**This assignment should be completed and submitted by Tuesday, October 19th, 2021 at 11:59pm PDT**\n",
    "\n",
    "### Collaboration Policy\n",
    "\n",
    "Data science is a collaborative activity. While you may talk with others about the labs, we ask that you **write your solutions individually**. If you do discuss the assignments with others, please **include their names** at the top of this notebook."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "imports",
     "locked": true,
     "schema_version": 2,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import seaborn as sns\n",
    "from sklearn.feature_extraction import DictVectorizer\n",
    "import matplotlib.pyplot as plt\n",
    "np.random.seed(42)\n",
    "plt.style.use('fivethirtyeight')\n",
    "sns.set()\n",
    "sns.set_context(\"talk\")\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "load-data-text",
     "locked": true,
     "schema_version": 2,
     "solution": false
    }
   },
   "source": [
    "# Loading the Tips Dataset\n",
    "\n",
    "To begin, let's load the tips dataset from the `seaborn` library.  This dataset contains records of tips, total bill, and information about the person who paid the bill. This is the same dataset used in Lab 6, so it should look familiar! We looked at predicting tips based on one feature (total bill) in Lab 7."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "load-data-code",
     "locked": true,
     "schema_version": 2,
     "solution": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of Records: 244\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>total_bill</th>\n",
       "      <th>tip</th>\n",
       "      <th>sex</th>\n",
       "      <th>smoker</th>\n",
       "      <th>day</th>\n",
       "      <th>time</th>\n",
       "      <th>size</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>16.99</td>\n",
       "      <td>1.01</td>\n",
       "      <td>Female</td>\n",
       "      <td>No</td>\n",
       "      <td>Sun</td>\n",
       "      <td>Dinner</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>10.34</td>\n",
       "      <td>1.66</td>\n",
       "      <td>Male</td>\n",
       "      <td>No</td>\n",
       "      <td>Sun</td>\n",
       "      <td>Dinner</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>21.01</td>\n",
       "      <td>3.50</td>\n",
       "      <td>Male</td>\n",
       "      <td>No</td>\n",
       "      <td>Sun</td>\n",
       "      <td>Dinner</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>23.68</td>\n",
       "      <td>3.31</td>\n",
       "      <td>Male</td>\n",
       "      <td>No</td>\n",
       "      <td>Sun</td>\n",
       "      <td>Dinner</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>24.59</td>\n",
       "      <td>3.61</td>\n",
       "      <td>Female</td>\n",
       "      <td>No</td>\n",
       "      <td>Sun</td>\n",
       "      <td>Dinner</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   total_bill   tip     sex smoker  day    time  size\n",
       "0       16.99  1.01  Female     No  Sun  Dinner     2\n",
       "1       10.34  1.66    Male     No  Sun  Dinner     3\n",
       "2       21.01  3.50    Male     No  Sun  Dinner     3\n",
       "3       23.68  3.31    Male     No  Sun  Dinner     2\n",
       "4       24.59  3.61  Female     No  Sun  Dinner     4"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = sns.load_dataset(\"tips\")\n",
    "\n",
    "print(\"Number of Records:\", len(data))\n",
    "data.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Intro to Feature Engineering\n",
    "\n",
    "So far, we've only considered models of the form $\\hat{y} = f_{\\theta}(x) = \\sum_{j=0}^d x_j\\theta_j$, where $\\hat{y}$ is quantitative continuous. \n",
    "\n",
    "We call this a linear model because it is a linear combination of the features (the $x_j$). However, our features don't need to be numbers: we could have categorical values such as names. Additionally, the true relationship doesn't have to be linear, as we could have a relationship that is quadratic, such as the relationship between the height of a projectile and time.\n",
    "\n",
    "In these cases, we often apply **feature functions**, functions that take in some value and output another value. This might look like converting a string into a number, combining multiple numeric values, or creating a boolean value from some filter.\n",
    "\n",
    "Then, if we call $\\phi$ (\"phi\") our \"phi\"-ture function, our model takes the form $\\hat{y} = f_{\\theta}(x) = \\sum_{j=0}^d \\phi(x)_j\\theta_j$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example feature functions\n",
    "\n",
    "1. Constant feature function\n",
    "    - adds a column of 1s to out original dataset -- this feature/parameter are often called the **bias**\n",
    "1. One-hot encoding\n",
    "    - converts a single categorical feature into many binary features, each of which represents one of the possible values in the original column\n",
    "    - each of the binary feature columns produced contains a 1 for rows that had that column's label in the original column, and 0 elsewhere"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "q1",
     "locked": true,
     "schema_version": 2,
     "solution": false
    }
   },
   "source": [
    "## Question 1: Defining the Model and Feature Engineering\n",
    "\n",
    "In Lab 6 we used the constant model. Now let's make a more complicated model that utilizes other features in our dataset. Let our prediction for tip be a combination of the following features:\n",
    "\n",
    "$$ \\text{Tip} = \\theta_1 \\cdot \\text{total}\\_\\text{bill} + \\theta_2 \\cdot \\text{sex} + \\theta_3 \\cdot \\text{smoker} + \\theta_4 \\cdot \\text{day} + \\theta_5 \\cdot \\text{time} + \\theta_6 \\cdot \\text{size} $$\n",
    "\n",
    "Notice that some of these features are not numbers! But our linear model will need to predict a numerical value. Let's start by converting some of these non-numerical values into numerical values. Below we split the tips and the features."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "split-data",
     "locked": true,
     "schema_version": 2,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "tips = data['tip']\n",
    "X = data.drop(columns='tip')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "q1a",
     "locked": true,
     "schema_version": 2,
     "solution": false
    }
   },
   "source": [
    "### Question 1a: Feature Engineering\n",
    "\n",
    "First, let's convert our features to numerical values. A straightforward approach is to map some of these non-numerical features into numerical ones. \n",
    "\n",
    "For example, we can treat the day as a value from 1-7. However, one of the disadvantages in directly translating to a numeric value is that we unintentionally assign certain features disproportionate weight. Consider assigning Sunday to the numeric value of 7, and Monday to the numeric value of 1. In our linear model, Sunday will have 7 times the influence of Monday, which can lower the accuracy of our model.\n",
    "\n",
    "Instead, let's use one-hot encoding to better represent these features! \n",
    "\n",
    "As you will learn in lecture, one-hot encoding is a way that we can produce a binary vector to indicate non-numeric features. \n",
    "\n",
    "In the `tips` dataset for example, we encode Sunday as the vector `[0 0 0 1]` because our dataset only contains bills from Thursday through Sunday. This assigns a more even weight across each category in non-numeric features. Complete the code below to one-hot encode our dataset. This dataframe holds our \"featurized\" data, which is also often denoted by $\\phi$.\n",
    "\n",
    "**Hint:** You may find the [DictVectorizer class](https://scikit-learn.org/stable/modules/generated/sklearn.feature_extraction.DictVectorizer.html) useful when doing your one-hot encoding.\n",
    "\n",
    "<!--\n",
    "BEGIN QUESTION\n",
    "name: q1a\n",
    "-->"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>total_bill</th>\n",
       "      <th>sex</th>\n",
       "      <th>smoker</th>\n",
       "      <th>day</th>\n",
       "      <th>time</th>\n",
       "      <th>size</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>16.99</td>\n",
       "      <td>Female</td>\n",
       "      <td>No</td>\n",
       "      <td>Sun</td>\n",
       "      <td>Dinner</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>10.34</td>\n",
       "      <td>Male</td>\n",
       "      <td>No</td>\n",
       "      <td>Sun</td>\n",
       "      <td>Dinner</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>21.01</td>\n",
       "      <td>Male</td>\n",
       "      <td>No</td>\n",
       "      <td>Sun</td>\n",
       "      <td>Dinner</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>23.68</td>\n",
       "      <td>Male</td>\n",
       "      <td>No</td>\n",
       "      <td>Sun</td>\n",
       "      <td>Dinner</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>24.59</td>\n",
       "      <td>Female</td>\n",
       "      <td>No</td>\n",
       "      <td>Sun</td>\n",
       "      <td>Dinner</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   total_bill     sex smoker  day    time  size\n",
       "0       16.99  Female     No  Sun  Dinner     2\n",
       "1       10.34    Male     No  Sun  Dinner     3\n",
       "2       21.01    Male     No  Sun  Dinner     3\n",
       "3       23.68    Male     No  Sun  Dinner     2\n",
       "4       24.59  Female     No  Sun  Dinner     4"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "X.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "q1a-answer",
     "locked": false,
     "schema_version": 2,
     "solution": true
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>total_bill</th>\n",
       "      <th>size</th>\n",
       "      <th>sex_Male</th>\n",
       "      <th>sex_Female</th>\n",
       "      <th>smoker_Yes</th>\n",
       "      <th>smoker_No</th>\n",
       "      <th>day_Thur</th>\n",
       "      <th>day_Fri</th>\n",
       "      <th>day_Sat</th>\n",
       "      <th>day_Sun</th>\n",
       "      <th>time_Lunch</th>\n",
       "      <th>time_Dinner</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>16.99</td>\n",
       "      <td>2</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>10.34</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>21.01</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>23.68</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>24.59</td>\n",
       "      <td>4</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   total_bill  size  sex_Male  sex_Female  smoker_Yes  smoker_No  day_Thur  \\\n",
       "0       16.99     2         0           1           0          1         0   \n",
       "1       10.34     3         1           0           0          1         0   \n",
       "2       21.01     3         1           0           0          1         0   \n",
       "3       23.68     2         1           0           0          1         0   \n",
       "4       24.59     4         0           1           0          1         0   \n",
       "\n",
       "   day_Fri  day_Sat  day_Sun  time_Lunch  time_Dinner  \n",
       "0        0        0        1           0            1  \n",
       "1        0        0        1           0            1  \n",
       "2        0        0        1           0            1  \n",
       "3        0        0        1           0            1  \n",
       "4        0        0        1           0            1  "
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def one_hot_encode(data):\n",
    "    \"\"\"\n",
    "    Return the one-hot encoded dataframe of our input data.\n",
    "    \n",
    "    Parameters\n",
    "    -----------\n",
    "    data: a dataframe that may include non-numerical features\n",
    "    \n",
    "    Returns\n",
    "    -----------\n",
    "    A one-hot encoded dataframe that only contains numeric features\n",
    "    \n",
    "    \"\"\"\n",
    "    # I prefer get_dummies :)\n",
    "    one_hots = pd.get_dummies(X.select_dtypes('category'))\n",
    "    return pd.concat([data.select_dtypes(exclude=['category']), one_hots], axis=1)\n",
    "one_hot_X = one_hot_encode(X)\n",
    "one_hot_X.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<p><strong><pre style='display: inline;'>q1a</pre></strong> passed!</p>"
      ],
      "text/plain": [
       "q1a results: All test cases passed!"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grader.check(\"q1a\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "q1b",
     "locked": true,
     "schema_version": 2,
     "solution": false
    }
   },
   "source": [
    "### Question 1b: Defining the Model\n",
    "\n",
    "Now that all of our data is numeric, we can begin to define our model function. Notice that after one-hot encoding our data, we now have 12 features instead of 6. Therefore, our linear model now looks like:\n",
    "\n",
    "$$ \\text{Tip} = \\theta_1 \\cdot \\text{size} + \\theta_2 \\cdot \\text{total}\\_\\text{bill} + \\theta_3 \\cdot \\text{day}\\_\\text{Thur} + \\theta_4 \\cdot \\text{day}\\_\\text{Fri} + ... + \\theta_{11} \\cdot \\text{time}\\_\\text{Lunch} + \\theta_{12} \\cdot \\text{time}\\_\\text{Dinner} $$\n",
    "\n",
    "We can represent the linear combination above as a matrix-vector product. Implement the `linear_model` function to evaluate this product.\n",
    "\n",
    "**Hint**: You can use [np.dot](https://numpy.org/doc/stable/reference/generated/numpy.dot.html), [pd.DataFrame.dot](https://pandas.pydata.org/pandas-docs/stable/generated/pandas.DataFrame.dot.html), or the `@` operator to multiply matrices/vectors. However, while the `@` operator can be used to multiply `numpy` arrays, it generally will not work between two `pandas` objects, so keep that in mind when computing matrix-vector products!\n",
    "\n",
    "<!--\n",
    "BEGIN QUESTION\n",
    "name: q1b\n",
    "-->"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(244, 12)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "one_hot_X.to_numpy().shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "q1b-answer",
     "locked": false,
     "schema_version": 2,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def linear_model(thetas, X):\n",
    "    \"\"\"\n",
    "    Return the linear combination of thetas and features as defined above.\n",
    "    \n",
    "    Parameters\n",
    "    -----------\n",
    "    thetas: a 1D vector representing the parameters of our model ([theta1, theta2, ...])\n",
    "    X: a 2D dataframe of numeric features (may also be a 2D numpy array)\n",
    "    \n",
    "    Returns\n",
    "    -----------\n",
    "    A 1D vector representing the linear combination of thetas and features as defined above.\n",
    "    \"\"\"\n",
    "    return np.dot(X, thetas)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<p><strong><pre style='display: inline;'>q1b</pre></strong> passed!</p>"
      ],
      "text/plain": [
       "q1b results: All test cases passed!"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grader.check(\"q1b\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "grade": false,
     "grade_id": "q2",
     "locked": true,
     "schema_version": 2,
     "solution": false
    }
   },
   "source": [
    "## Question 2: Fitting the Model using Numeric Methods\n",
    "\n",
    "Recall in Lab 6 we defined multiple loss functions and found THE optimal theta using the `scipy.minimize` function. Adapt the loss functions and optimization code from Lab 6 (provided below) to work with our new linear model.\n",
    "\n",
    "<!--\n",
    "BEGIN QUESTION\n",
    "name: q2\n",
    "-->"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "q2-answer",
     "locked": false,
     "schema_version": 2,
     "solution": true
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0.09448702,  0.17599316,  0.31373902,  0.34618047, -0.22256394,\n",
       "       -0.13615577,  0.30569619,  0.4679786 ,  0.3465301 ,  0.44250891,\n",
       "        0.19396038,  0.12580097])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from scipy.optimize import minimize\n",
    "\n",
    "def l1(y, y_hat):\n",
    "    return np.abs(y - y_hat)\n",
    "\n",
    "def l2(y, y_hat):\n",
    "    return (y - y_hat)**2\n",
    "\n",
    "def minimize_average_loss(loss_function, model, X, y):\n",
    "    \"\"\"\n",
    "    Minimize the average loss calculated from using different theta vectors, and \n",
    "    estimate the optimal theta for the model.\n",
    "    \n",
    "    Parameters\n",
    "    -----------\n",
    "    loss_function: either the squared or absolute loss functions defined above\n",
    "    model: the model (as defined in Question 1b)\n",
    "    X: a 2D dataframe (or numpy array) of numeric features (one-hot encoded)\n",
    "    y: a 1D vector of tip amounts\n",
    "    \n",
    "    Returns\n",
    "    -----------\n",
    "    The estimate for the optimal theta vector that minimizes our loss\n",
    "    \"\"\"\n",
    "    \n",
    "    ## Notes on the following function call which you need to finish:\n",
    "    # \n",
    "    # 0. The first '...' should be replaced with the average loss evaluated on \n",
    "    #       the data X, y using the model and appropriate loss function.\n",
    "    # 1. x0 is the initial value for THETA.  Yes, this is confusing\n",
    "    #       but optimization people like x to be the thing they are \n",
    "    #       optimizing. Replace the second '...' with a random initial value for theta,\n",
    "    #       and remember that theta is now a vector. DO NOT hard-code the length of x0;\n",
    "    #       it should depend on the number of features in X. Look into np.random.\n",
    "    # 2. Your answer will be very similar to your answer to question 2 from lab 7.\n",
    "    avg_loss = lambda theta: np.mean(loss_function(y.to_numpy(), model(theta, X)))\n",
    "    return minimize(lambda theta: avg_loss(theta), x0=np.random.random((X.shape[1], 1)))['x']\n",
    "    # Notice above that we extract the 'x' entry in the dictionary returned by `minimize`. \n",
    "    # This entry corresponds to the optimal theta estimated by the function.\n",
    "\n",
    "minimize_average_loss(l2, linear_model, one_hot_X, tips)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<p><strong><pre style='display: inline;'>q2</pre></strong> passed!</p>"
      ],
      "text/plain": [
       "q2 results: All test cases passed!"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grader.check(\"q2\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "q3",
     "locked": true,
     "schema_version": 2,
     "solution": false
    }
   },
   "source": [
    "\n",
    "## Question 3: Fitting the Model using Analytic Methods\n",
    "\n",
    "Let's also fit our model analytically for the L2 loss function. Recall from lecture that with a linear model, we are solving the following optimization problem for least squares:\n",
    "\n",
    "$$\\min_{\\theta} ||\\Bbb{X}\\theta - \\Bbb{y}||^2$$\n",
    "\n",
    "We showed in [Lecture 13](https://docs.google.com/presentation/d/15olJS1Yuk22spzrNx4It6-eLm8gkZM4pFKKOWhKXBUI/edit#slide=id.p) that the optimal $\\hat{\\theta}$ when $X^TX$ is invertible is given by the equation: $(X^TX)^{-1}X^TY$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "q3a",
     "locked": true,
     "schema_version": 2,
     "solution": false
    }
   },
   "source": [
    "### Question 3a: Analytic Solution Using Explicit Inverses\n",
    "\n",
    "For this problem, implement the analytic solution above using `np.linalg.inv` to compute the inverse of $X^TX$.\n",
    "\n",
    "Reminder: To compute the transpose of a matrix, you can use `X.T` or `X.transpose()`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "nbgrader": {
     "grade": false,
     "grade_id": "q3a-answer",
     "locked": false,
     "schema_version": 2,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "def get_analytical_sol(X, y):\n",
    "    \"\"\"\n",
    "    Computes the analytical solution to our least squares problem\n",
    "    \n",
    "    Parameters\n",
    "    -----------\n",
    "    X: a 2D dataframe (or numpy array) of numeric features (one-hot encoded)\n",
    "    y: a 1D vector of tip amounts\n",
    "    \n",
    "    Returns\n",
    "    -----------\n",
    "    The estimate for theta computed using the equation mentioned above\n",
    "    \"\"\"\n",
    "    tmp = np.dot(X.T, X)\n",
    "    tmp_inv = np.linalg.inv(tmp)\n",
    "    return np.dot(np.dot(tmp_inv, X.T), y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, run the cell below to find the analytical solution for the `tips` dataset. Depending on the machine that you run your code on, you should either see an error or end up with thetas that are nonsensical (magnitudes greater than 10^15). This is not good!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 6.73780220e-01,  3.59016156e+00, -4.60019400e+14, -4.60019400e+14,\n",
       "        4.49206898e+13,  4.49206898e+13,  4.15098710e+14,  4.15098710e+14,\n",
       "        4.15098710e+14,  4.15098710e+14, -6.81398438e+00, -1.01713281e+01])"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "analytical_thetas = get_analytical_sol(one_hot_X, tips)\n",
    "analytical_thetas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "source": [
    "In the cell below, explain why we got the error above when trying to calculate the analytical solution for our one-hot encoded `tips` dataset.\n",
    "\n",
    "<!--\n",
    "BEGIN QUESTION\n",
    "name: q3a\n",
    "-->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Type your answer here, replacing this text._"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "source": [
    "### Question 3b: Fixing our One-Hot Encoding\n",
    "\n",
    "Now, let's fix our one-hot encoding approach from question 1 so we don't get the error we saw in question 3a. Complete the code below to one-hot-encode our dataset such that `one_hot_X_revised` has no redundant features.\n",
    "\n",
    "<!--\n",
    "BEGIN QUESTION\n",
    "name: q3b\n",
    "-->"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>total_bill</th>\n",
       "      <th>size</th>\n",
       "      <th>sex_Male</th>\n",
       "      <th>sex_Female</th>\n",
       "      <th>smoker_Yes</th>\n",
       "      <th>smoker_No</th>\n",
       "      <th>day_Thur</th>\n",
       "      <th>day_Fri</th>\n",
       "      <th>day_Sat</th>\n",
       "      <th>day_Sun</th>\n",
       "      <th>time_Lunch</th>\n",
       "      <th>time_Dinner</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>16.99</td>\n",
       "      <td>2</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>10.34</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>21.01</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>23.68</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>24.59</td>\n",
       "      <td>4</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   total_bill  size  sex_Male  sex_Female  smoker_Yes  smoker_No  day_Thur  \\\n",
       "0       16.99     2         0           1           0          1         0   \n",
       "1       10.34     3         1           0           0          1         0   \n",
       "2       21.01     3         1           0           0          1         0   \n",
       "3       23.68     2         1           0           0          1         0   \n",
       "4       24.59     4         0           1           0          1         0   \n",
       "\n",
       "   day_Fri  day_Sat  day_Sun  time_Lunch  time_Dinner  \n",
       "0        0        0        1           0            1  \n",
       "1        0        0        1           0            1  \n",
       "2        0        0        1           0            1  \n",
       "3        0        0        1           0            1  \n",
       "4        0        0        1           0            1  "
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "one_hot_X.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "   total_bill  size  sex_Female  smoker_No  day_Fri  day_Sat  day_Sun  \\\n",
      "0       16.99     2           1          1        0        0        1   \n",
      "1       10.34     3           0          1        0        0        1   \n",
      "2       21.01     3           0          1        0        0        1   \n",
      "3       23.68     2           0          1        0        0        1   \n",
      "4       24.59     4           1          1        0        0        1   \n",
      "\n",
      "   time_Dinner  \n",
      "0            1  \n",
      "1            1  \n",
      "2            1  \n",
      "3            1  \n",
      "4            1  \n",
      "Our analytical loss is:  1.0332855708786624\n",
      "Our numerical loss is:  1.0332855709696145\n"
     ]
    }
   ],
   "source": [
    "def one_hot_encode_revised(data):\n",
    "    \"\"\"\n",
    "    Return the one-hot encoded dataframe of our input data, removing redundancies.\n",
    "    \n",
    "    Parameters\n",
    "    -----------\n",
    "    data: a dataframe that may include non-numerical features\n",
    "    \n",
    "    Returns\n",
    "    -----------\n",
    "    A one-hot encoded dataframe that only contains numeric features without any redundancies.\n",
    "    \n",
    "    \"\"\"\n",
    "    # drop_first=True will get k-1 dummies out of k categorical\n",
    "    return pd.get_dummies(data, drop_first=True)\n",
    "one_hot_X_revised = one_hot_encode_revised(X)\n",
    "print(one_hot_X_revised.head())       # take a look at the revised one_hot_X\n",
    "revised_analytical_thetas = get_analytical_sol(one_hot_X_revised, tips)\n",
    "print(\"Our analytical loss is: \", l2(linear_model(revised_analytical_thetas, one_hot_X_revised), tips).mean())\n",
    "print(\"Our numerical loss is: \", l2(linear_model(minimize_average_loss(l2, linear_model, one_hot_X_revised, tips), one_hot_X_revised), tips).mean())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<p><strong><pre style='display: inline;'>q3b</pre></strong> passed!</p>"
      ],
      "text/plain": [
       "q3b results: All test cases passed!"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grader.check(\"q3b\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "source": [
    "### Question 3c: Analyzing our new One-Hot Encoding\n",
    "\n",
    "Why did removing redundancies in our one-hot encoding fix the problem we had in 3a?\n",
    "<!--\n",
    "BEGIN QUESTION\n",
    "name: q3c\n",
    "-->"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Type your answer here, replacing this text._"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "Note: An alternate approach is to use `np.linalg.solve` instead of `np.linalg.inv`. For the example above, even with the redundant features, `np.linalg.solve` will work well. Though in general, it's best to drop redundant features anyway.\n",
    "\n",
    "In case you want to learn more, here is a relevant Stack Overflow post: https://stackoverflow.com/questions/31256252/why-does-numpy-linalg-solve-offer-more-precise-matrix-inversions-than-numpy-li"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "source": [
    "---\n",
    "\n",
    "To double-check your work, the cell below will rerun all of the autograder tests."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "q1a results: All test cases passed!\n",
       "\n",
       "q1b results: All test cases passed!\n",
       "\n",
       "q2 results: All test cases passed!\n",
       "\n",
       "q3b results: All test cases passed!"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grader.check_all()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "source": [
    "## Submission\n",
    "\n",
    "Make sure you have run all cells in your notebook in order before running the cell below, so that all images/graphs appear in the output. The cell below will generate a zip file for you to submit. **Please save before exporting!**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "deletable": false,
    "editable": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "            <p>Your submission has been exported. Click <a href=\"lab08_2022_04_05T14_36_27_015244.zip\" download=\"lab08_2022_04_05T14_36_27_015244.zip\" target=\"_blank\">here</a>\n",
       "            to download the zip file.</p>\n",
       "            "
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Save your notebook first, then run this cell to export your submission.\n",
    "grader.export(pdf=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " "
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Create Assignment",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}