Exercise6/exercise6.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Programming Exercise 6:\n",
    "# Support Vector Machines\n",
    "\n",
    "## Introduction\n",
    "\n",
    "In this exercise, you will be using support vector machines (SVMs) to build a spam classifier. Before starting on the programming exercise, we strongly recommend watching the video lectures and completing the review questions for the associated topics.\n",
    "\n",
    "All the information you need for solving this assignment is in this notebook, and all the code you will be implementing will take place within this notebook. The assignment can be promptly submitted to the coursera grader directly from this notebook (code and instructions are included below).\n",
    "\n",
    "Before we begin with the exercises, we need to import all libraries required for this programming exercise. Throughout the course, we will be using [`numpy`](http://www.numpy.org/) for all arrays and matrix operations, [`matplotlib`](https://matplotlib.org/) for plotting, and [`scipy`](https://docs.scipy.org/doc/scipy/reference/) for scientific and numerical computation functions and tools. You can find instructions on how to install required libraries in the README file in the [github repository](https://github.com/dibgerge/ml-coursera-python-assignments)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# used for manipulating directory paths\n",
    "import os\n",
    "\n",
    "# Scientific and vector computation for python\n",
    "import numpy as np\n",
    "\n",
    "# Import regular expressions to process emails\n",
    "import re\n",
    "\n",
    "# Plotting library\n",
    "from matplotlib import pyplot\n",
    "\n",
    "# Optimization module in scipy\n",
    "from scipy import optimize\n",
    "\n",
    "# will be used to load MATLAB mat datafile format\n",
    "from scipy.io import loadmat\n",
    "\n",
    "# library written for this exercise providing additional functions for assignment submission, and others\n",
    "import utils\n",
    "\n",
    "# define the submission/grader object for this exercise\n",
    "grader = utils.Grader()\n",
    "\n",
    "# tells matplotlib to embed plots within the notebook\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Submission and Grading\n",
    "\n",
    "\n",
    "After completing each part of the assignment, be sure to submit your solutions to the grader. The following is a breakdown of how each part of this exercise is scored.\n",
    "\n",
    "\n",
    "| Section | Part                                             | Submitted Function                | Points |\n",
    "| :-      |:-                                                |:-                                 | :-:    |\n",
    "| 1       | [Gaussian Kernel](#section1)                     | [`gaussianKernel`](#gaussianKernel)        |  25    |\n",
    "| 2       | [Parameters (C, $\\sigma$) for Dataset 3](#section2)| [`dataset3Params`](#dataset3Params)      |  25    |\n",
    "| 3       | [Email Preprocessing](#section3)                 | [`processEmail`](#processEmail)          |  25    |\n",
    "| 4       | [Email Feature Extraction](#section4)            | [`emailFeatures`](#emailFeatures)         |  25    |\n",
    "|         | Total Points                                     |                                   |100     |\n",
    "\n",
    "\n",
    "You are allowed to submit your solutions multiple times, and we will take only the highest score into consideration.\n",
    "\n",
    "<div class=\"alert alert-block alert-warning\">\n",
    "At the end of each section in this notebook, we have a cell which contains code for submitting the solutions thus far to the grader. Execute the cell to see your score up to the current section. For all your work to be submitted properly, you must execute those cells at least once.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1 Support Vector Machines\n",
    "\n",
    "In the first half of this exercise, you will be using support vector machines (SVMs) with various example 2D datasets. Experimenting with these datasets will help you gain an intuition of how SVMs work and how to use a Gaussian kernel with SVMs. In the next half of the exercise, you will be using support\n",
    "vector machines to build a spam classifier."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Example Dataset 1\n",
    "\n",
    "We will begin by with a 2D example dataset which can be separated by a linear boundary. The following cell plots the training data, which should look like this:\n",
    "\n",
    "![Dataset 1 training data](Figures/dataset1.png)\n",
    "\n",
    "In this dataset, the positions of the positive examples (indicated with `x`) and the negative examples (indicated with `o`) suggest a natural separation indicated by the gap. However, notice that there is an outlier positive example `x` on the far left at about (0.1, 4.1). As part of this exercise, you will also see how this outlier affects the SVM decision boundary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load from ex6data1\n",
    "# You will have X, y as keys in the dict data\n",
    "data = loadmat(os.path.join('Data', 'ex6data1.mat'))\n",
    "X, y = data['X'], data['y'][:, 0]\n",
    "\n",
    "# Plot training data\n",
    "utils.plotData(X, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this part of the exercise, you will try using different values of the $C$ parameter with SVMs. Informally, the $C$ parameter is a positive value that controls the penalty for misclassified training examples. A large $C$ parameter tells the SVM to try to classify all the examples correctly. $C$ plays a role similar to $1/\\lambda$, where $\\lambda$ is the regularization parameter that we were using previously for logistic regression.\n",
    "\n",
    "\n",
    "The following cell will run the SVM training (with $C=1$) using SVM software that we have included with the starter code (function `svmTrain` within the `utils` module of this exercise). When $C=1$, you should find that the SVM puts the decision boundary in the gap between the two datasets and *misclassifies* the data point on the far left, as shown in the figure (left) below.\n",
    "\n",
    "<table style=\"text-align:center\">\n",
    "    <tr>\n",
    "        <th colspan=\"2\" style=\"text-align:center\">SVM Decision boundary for example dataset 1 </th>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td style=\"text-align:center\">C=1<img src=\"Figures/svm_c1.png\"/></td>\n",
    "        <td style=\"text-align:center\">C=100<img src=\"Figures/svm_c100.png\"/></td>\n",
    "    </tr>\n",
    "</table>\n",
    "\n",
    "<div class=\"alert alert-block alert-warning\">\n",
    "In order to minimize the dependency of this assignment on external libraries, we have included this implementation of an SVM learning algorithm in utils.svmTrain. However, this particular implementation is not very efficient (it was originally chosen to maximize compatibility between Octave/MATLAB for the first version of this assignment set). If you are training an SVM on a real problem, especially if you need to scale to a larger dataset, we strongly recommend instead using a highly optimized SVM toolbox such as [LIBSVM](https://www.csie.ntu.edu.tw/~cjlin/libsvm/). The python machine learning library [scikit-learn](http://scikit-learn.org/stable/index.html) provides wrappers for the LIBSVM library.\n",
    "</div>\n",
    "<br/>\n",
    "<div class=\"alert alert-block alert-warning\">\n",
    "**Implementation Note:** Most SVM software packages (including the function `utils.svmTrain`) automatically add the extra feature $x_0$ = 1 for you and automatically take care of learning the intercept term $\\theta_0$. So when passing your training data to the SVM software, there is no need to add this extra feature $x_0 = 1$ yourself. In particular, in python your code should be working with training examples $x \\in \\mathcal{R}^n$ (rather than $x \\in \\mathcal{R}^{n+1}$); for example, in the first example dataset $x \\in \\mathcal{R}^2$.\n",
    "</div>\n",
    "\n",
    "Your task is to try different values of $C$ on this dataset. Specifically, you should change the value of $C$ in the next cell to $C = 100$ and run the SVM training again. When $C = 100$, you should find that the SVM now classifies every single example correctly, but has a decision boundary that does not\n",
    "appear to be a natural fit for the data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# You should try to change the C value below and see how the decision\n",
    "# boundary varies (e.g., try C = 1000)\n",
    "C = 1\n",
    "\n",
    "model = utils.svmTrain(X, y, C, utils.linearKernel, 1e-3, 20)\n",
    "utils.visualizeBoundaryLinear(X, y, model)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id=\"section1\"></a>\n",
    "### 1.2 SVM with Gaussian Kernels\n",
    "\n",
    "In this part of the exercise, you will be using SVMs to do non-linear classification. In particular, you will be using SVMs with Gaussian kernels on datasets that are not linearly separable.\n",
    "\n",
    "#### 1.2.1 Gaussian Kernel\n",
    "\n",
    "To find non-linear decision boundaries with the SVM, we need to first implement a Gaussian kernel. You can think of the Gaussian kernel as a similarity function that measures the “distance” between a pair of examples,\n",
    "($x^{(i)}$, $x^{(j)}$). The Gaussian kernel is also parameterized by a bandwidth parameter, $\\sigma$, which determines how fast the similarity metric decreases (to 0) as the examples are further apart.\n",
    "You should now complete the code in `gaussianKernel` to compute the Gaussian kernel between two examples, ($x^{(i)}$, $x^{(j)}$). The Gaussian kernel function is defined as:\n",
    "\n",
    "$$ K_{\\text{gaussian}} \\left( x^{(i)}, x^{(j)} \\right) = \\exp \\left( - \\frac{\\left\\lvert\\left\\lvert x^{(i)} - x^{(j)}\\right\\lvert\\right\\lvert^2}{2\\sigma^2} \\right) = \\exp \\left( -\\frac{\\sum_{k=1}^n \\left( x_k^{(i)} - x_k^{(j)}\\right)^2}{2\\sigma^2} \\right)$$\n",
    "<a id=\"gaussianKernel\"></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gaussianKernel(x1, x2, sigma):\n",
    "    \"\"\"\n",
    "    Computes the radial basis function\n",
    "    Returns a radial basis function kernel between x1 and x2.\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    x1 :  numpy ndarray\n",
    "        A vector of size (n, ), representing the first datapoint.\n",
    "    \n",
    "    x2 : numpy ndarray\n",
    "        A vector of size (n, ), representing the second datapoint.\n",
    "    \n",
    "    sigma : float\n",
    "        The bandwidth parameter for the Gaussian kernel.\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    sim : float\n",
    "        The computed RBF between the two provided data points.\n",
    "    \n",
    "    Instructions\n",
    "    ------------\n",
    "    Fill in this function to return the similarity between `x1` and `x2`\n",
    "    computed using a Gaussian kernel with bandwidth `sigma`.\n",
    "    \"\"\"\n",
    "    sim = 0\n",
    "    # ====================== YOUR CODE HERE ======================\n",
    "\n",
    "\n",
    "\n",
    "    # =============================================================\n",
    "    return sim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once you have completed the function `gaussianKernel` the following cell will test your kernel function on two provided examples and you should expect to see a value of 0.324652."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x1 = np.array([1, 2, 1])\n",
    "x2 = np.array([0, 4, -1])\n",
    "sigma = 2\n",
    "\n",
    "sim = gaussianKernel(x1, x2, sigma)\n",
    "\n",
    "print('Gaussian Kernel between x1 = [1, 2, 1], x2 = [0, 4, -1], sigma = %0.2f:'\n",
    "      '\\n\\t%f\\n(for sigma = 2, this value should be about 0.324652)\\n' % (sigma, sim))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*You should now submit your solutions.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grader[1] = gaussianKernel\n",
    "grader.grade()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2.2 Example Dataset 2\n",
    "\n",
    "The next part in this notebook will load and plot dataset 2, as shown in the figure below. \n",
    "\n",
    "![Dataset 2](Figures/dataset2.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load from ex6data2\n",
    "# You will have X, y as keys in the dict data\n",
    "data = loadmat(os.path.join('Data', 'ex6data2.mat'))\n",
    "X, y = data['X'], data['y'][:, 0]\n",
    "\n",
    "# Plot training data\n",
    "utils.plotData(X, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From the figure, you can obserse that there is no linear decision boundary that separates the positive and negative examples for this dataset. However, by using the Gaussian kernel with the SVM, you will be able to learn a non-linear decision boundary that can perform reasonably well for the dataset. If you have correctly implemented the Gaussian kernel function, the following cell will proceed to train the SVM with the Gaussian kernel on this dataset.\n",
    "\n",
    "You should get a decision boundary as shown in the figure below, as computed by the SVM with a Gaussian kernel. The decision boundary is able to separate most of the positive and negative examples correctly and follows the contours of the dataset well.\n",
    "\n",
    "![Dataset 2 decision boundary](Figures/svm_dataset2.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# SVM Parameters\n",
    "C = 1\n",
    "sigma = 0.1\n",
    "\n",
    "model= utils.svmTrain(X, y, C, gaussianKernel, args=(sigma,))\n",
    "utils.visualizeBoundary(X, y, model)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id=\"section2\"></a>\n",
    "#### 1.2.3 Example Dataset 3\n",
    "\n",
    "In this part of the exercise, you will gain more practical skills on how to use a SVM with a Gaussian kernel. The next cell will load and display a third dataset, which should look like the figure below.\n",
    "\n",
    "![Dataset 3](Figures/dataset3.png)\n",
    "\n",
    "You will be using the SVM with the Gaussian kernel with this dataset. In the provided dataset, `ex6data3.mat`, you are given the variables `X`, `y`, `Xval`, `yval`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load from ex6data3\n",
    "# You will have X, y, Xval, yval as keys in the dict data\n",
    "data = loadmat(os.path.join('Data', 'ex6data3.mat'))\n",
    "X, y, Xval, yval = data['X'], data['y'][:, 0], data['Xval'], data['yval'][:, 0]\n",
    "\n",
    "# Plot training data\n",
    "utils.plotData(X, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Your task is to use the cross validation set `Xval`, `yval` to determine the best $C$ and $\\sigma$ parameter to use. You should write any additional code necessary to help you search over the parameters $C$ and $\\sigma$. For both $C$ and $\\sigma$, we suggest trying values in multiplicative steps (e.g., 0.01, 0.03, 0.1, 0.3, 1, 3, 10, 30).\n",
    "Note that you should try all possible pairs of values for $C$ and $\\sigma$ (e.g., $C = 0.3$ and $\\sigma = 0.1$). For example, if you try each of the 8 values listed above for $C$ and for $\\sigma^2$, you would end up training and evaluating (on the cross validation set) a total of $8^2 = 64$ different models. After you have determined the best $C$ and $\\sigma$ parameters to use, you should modify the code in `dataset3Params`, filling in the best parameters you found. For our best parameters, the SVM returned a decision boundary shown in the figure below. \n",
    "\n",
    "![](Figures/svm_dataset3_best.png)\n",
    "\n",
    "<div class=\"alert alert-block alert-warning\">\n",
    "**Implementation Tip:** When implementing cross validation to select the best $C$ and $\\sigma$ parameter to use, you need to evaluate the error on the cross validation set. Recall that for classification, the error is defined as the fraction of the cross validation examples that were classified incorrectly. In `numpy`, you can compute this error using `np.mean(predictions != yval)`, where `predictions` is a vector containing all the predictions from the SVM, and `yval` are the true labels from the cross validation set. You can use the `utils.svmPredict` function to generate the predictions for the cross validation set.\n",
    "</div>\n",
    "<a id=\"dataset3Params\"></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dataset3Params(X, y, Xval, yval):\n",
    "    \"\"\"\n",
    "    Returns your choice of C and sigma for Part 3 of the exercise \n",
    "    where you select the optimal (C, sigma) learning parameters to use for SVM\n",
    "    with RBF kernel.\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    X : array_like\n",
    "        (m x n) matrix of training data where m is number of training examples, and \n",
    "        n is the number of features.\n",
    "    \n",
    "    y : array_like\n",
    "        (m, ) vector of labels for ther training data.\n",
    "    \n",
    "    Xval : array_like\n",
    "        (mv x n) matrix of validation data where mv is the number of validation examples\n",
    "        and n is the number of features\n",
    "    \n",
    "    yval : array_like\n",
    "        (mv, ) vector of labels for the validation data.\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    C, sigma : float, float\n",
    "        The best performing values for the regularization parameter C and \n",
    "        RBF parameter sigma.\n",
    "    \n",
    "    Instructions\n",
    "    ------------\n",
    "    Fill in this function to return the optimal C and sigma learning \n",
    "    parameters found using the cross validation set.\n",
    "    You can use `svmPredict` to predict the labels on the cross\n",
    "    validation set. For example, \n",
    "    \n",
    "        predictions = utils.svmPredict(model, Xval)\n",
    "\n",
    "    will return the predictions on the cross validation set.\n",
    "    \n",
    "    Note\n",
    "    ----\n",
    "    You can compute the prediction error using \n",
    "    \n",
    "        np.mean(predictions != yval)\n",
    "    \"\"\"\n",
    "    # You need to return the following variables correctly.\n",
    "    C = 1\n",
    "    sigma = 0.3\n",
    "\n",
    "    # ====================== YOUR CODE HERE ======================\n",
    "\n",
    "    \n",
    "    \n",
    "    # ============================================================\n",
    "    return C, sigma"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The provided code in the next cell trains the SVM classifier using the training set $(X, y)$ using parameters loaded from `dataset3Params`. Note that this might take a few minutes to execute."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Try different SVM Parameters here\n",
    "C, sigma = dataset3Params(X, y, Xval, yval)\n",
    "\n",
    "# Train the SVM\n",
    "# model = utils.svmTrain(X, y, C, lambda x1, x2: gaussianKernel(x1, x2, sigma))\n",
    "model = utils.svmTrain(X, y, C, gaussianKernel, args=(sigma,))\n",
    "utils.visualizeBoundary(X, y, model)\n",
    "print(C, sigma)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One you have computed the values `C` and `sigma` in the cell above, we will submit those values for grading.\n",
    "\n",
    "*You should now submit your solutions.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grader[2] = lambda : (C, sigma)\n",
    "grader.grade()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id=\"section3\"></a>\n",
    "## 2 Spam Classification\n",
    "\n",
    "Many email services today provide spam filters that are able to classify emails into spam and non-spam email with high accuracy. In this part of the exercise, you will use SVMs to build your own spam filter.\n",
    "\n",
    "You will be training a classifier to classify whether a given email, $x$, is spam ($y = 1$) or non-spam ($y = 0$). In particular, you need to convert each email into a feature vector $x \\in \\mathbb{R}^n$ . The following parts of the exercise will walk you through how such a feature vector can be constructed from an email.\n",
    "\n",
    "The dataset included for this exercise is based on a a subset of the [SpamAssassin Public Corpus](http://spamassassin.apache.org/old/publiccorpus/). For the purpose of this exercise, you will only be using the body of the email (excluding the email headers)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 Preprocessing Emails\n",
    "\n",
    "Before starting on a machine learning task, it is usually insightful to take a look at examples from the dataset. The figure below shows a sample email that contains a URL, an email address (at the end), numbers, and dollar\n",
    "amounts.\n",
    "\n",
    "<img src=\"Figures/email.png\" width=\"700px\" />\n",
    "\n",
    "While many emails would contain similar types of entities (e.g., numbers, other URLs, or other email addresses), the specific entities (e.g., the specific URL or specific dollar amount) will be different in almost every\n",
    "email. Therefore, one method often employed in processing emails is to “normalize” these values, so that all URLs are treated the same, all numbers are treated the same, etc. For example, we could replace each URL in the\n",
    "email with the unique string “httpaddr” to indicate that a URL was present.\n",
    "\n",
    "This has the effect of letting the spam classifier make a classification decision based on whether any URL was present, rather than whether a specific URL was present. This typically improves the performance of a spam classifier, since spammers often randomize the URLs, and thus the odds of seeing any particular URL again in a new piece of spam is very small. \n",
    "\n",
    "In the function `processEmail` below, we have implemented the following email preprocessing and normalization steps:\n",
    "\n",
    "- **Lower-casing**: The entire email is converted into lower case, so that captialization is ignored (e.g., IndIcaTE is treated the same as Indicate).\n",
    "\n",
    "- **Stripping HTML**: All HTML tags are removed from the emails. Many emails often come with HTML formatting; we remove all the HTML tags, so that only the content remains.\n",
    "\n",
    "- **Normalizing URLs**: All URLs are replaced with the text “httpaddr”.\n",
    "\n",
    "- **Normalizing Email Addresses**:  All email addresses are replaced with the text “emailaddr”.\n",
    "\n",
    "- **Normalizing Numbers**: All numbers are replaced with the text “number”.\n",
    "\n",
    "- **Normalizing Dollars**: All dollar signs ($) are replaced with the text “dollar”.\n",
    "\n",
    "- **Word Stemming**: Words are reduced to their stemmed form. For example, “discount”, “discounts”, “discounted” and “discounting” are all replaced with “discount”. Sometimes, the Stemmer actually strips off additional characters from the end, so “include”, “includes”, “included”, and “including” are all replaced with “includ”.\n",
    "\n",
    "- **Removal of non-words**: Non-words and punctuation have been removed. All white spaces (tabs, newlines, spaces) have all been trimmed to a single space character.\n",
    "\n",
    "The result of these preprocessing steps is shown in the figure below. \n",
    "\n",
    "<img src=\"Figures/email_cleaned.png\" alt=\"email cleaned\" style=\"width: 600px;\"/>\n",
    "\n",
    "While preprocessing has left word fragments and non-words, this form turns out to be much easier to work with for performing feature extraction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.1.1 Vocabulary List\n",
    "\n",
    "After preprocessing the emails, we have a list of words for each email. The next step is to choose which words we would like to use in our classifier and which we would want to leave out.\n",
    "\n",
    "For this exercise, we have chosen only the most frequently occuring words as our set of words considered (the vocabulary list). Since words that occur rarely in the training set are only in a few emails, they might cause the\n",
    "model to overfit our training set. The complete vocabulary list is in the file `vocab.txt` (inside the `Data` directory for this exercise) and also shown in the figure below.\n",
    "\n",
    "<img src=\"Figures/vocab.png\" alt=\"Vocab\" width=\"150px\" />\n",
    "\n",
    "Our vocabulary list was selected by choosing all words which occur at least a 100 times in the spam corpus,\n",
    "resulting in a list of 1899 words. In practice, a vocabulary list with about 10,000 to 50,000 words is often used.\n",
    "Given the vocabulary list, we can now map each word in the preprocessed emails into a list of word indices that contains the index of the word in the vocabulary dictionary. The figure below shows the mapping for the sample email. Specifically, in the sample email, the word “anyone” was first normalized to “anyon” and then mapped onto the index 86 in the vocabulary list.\n",
    "\n",
    "<img src=\"Figures/word_indices.png\" alt=\"word indices\" width=\"200px\" />\n",
    "\n",
    "Your task now is to complete the code in the function `processEmail` to perform this mapping. In the code, you are given a string `word` which is a single word from the processed email. You should look up the word in the vocabulary list `vocabList`. If the word exists in the list, you should add the index of the word into the `word_indices` variable. If the word does not exist, and is therefore not in the vocabulary, you can skip the word.\n",
    "\n",
    "<div class=\"alert alert-block alert-warning\">\n",
    "**python tip**: In python, you can find the index of the first occurence of an item in `list` using the  `index` attribute. In the provided code for `processEmail`, `vocabList` is a python list containing the words in the vocabulary. To find the index of a word, we can use `vocabList.index(word)` which would return a number indicating the index of the word within the list. If the word does not exist in the list, a `ValueError` exception is raised. In python, we can use the `try/except` statement to catch exceptions which we do not want to stop the program from running. You can think of the `try/except` statement to be the same as an `if/else` statement, but it asks for forgiveness rather than permission.\n",
    "\n",
    "An example would be:\n",
    "<br>\n",
    "\n",
    "```\n",
    "try:\n",
    "    do stuff here\n",
    "except ValueError:\n",
    "    pass\n",
    "    # do nothing (forgive me) if a ValueError exception occured within the try statement\n",
    "```\n",
    "</div>\n",
    "<a id=\"processEmail\"></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def processEmail(email_contents, verbose=True):\n",
    "    \"\"\"\n",
    "    Preprocesses the body of an email and returns a list of indices \n",
    "    of the words contained in the email.    \n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    email_contents : str\n",
    "        A string containing one email. \n",
    "    \n",
    "    verbose : bool\n",
    "        If True, print the resulting email after processing.\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    word_indices : list\n",
    "        A list of integers containing the index of each word in the \n",
    "        email which is also present in the vocabulary.\n",
    "    \n",
    "    Instructions\n",
    "    ------------\n",
    "    Fill in this function to add the index of word to word_indices \n",
    "    if it is in the vocabulary. At this point of the code, you have \n",
    "    a stemmed word from the email in the variable word.\n",
    "    You should look up word in the vocabulary list (vocabList). \n",
    "    If a match exists, you should add the index of the word to the word_indices\n",
    "    list. Concretely, if word = 'action', then you should\n",
    "    look up the vocabulary list to find where in vocabList\n",
    "    'action' appears. For example, if vocabList[18] =\n",
    "    'action', then, you should add 18 to the word_indices \n",
    "    vector (e.g., word_indices.append(18)).\n",
    "    \n",
    "    Notes\n",
    "    -----\n",
    "    - vocabList[idx] returns a the word with index idx in the vocabulary list.\n",
    "    \n",
    "    - vocabList.index(word) return index of word `word` in the vocabulary list.\n",
    "      (A ValueError exception is raised if the word does not exist.)\n",
    "    \"\"\"\n",
    "    # Load Vocabulary\n",
    "    vocabList = utils.getVocabList()\n",
    "\n",
    "    # Init return value\n",
    "    word_indices = []\n",
    "\n",
    "    # ========================== Preprocess Email ===========================\n",
    "    # Find the Headers ( \\n\\n and remove )\n",
    "    # Uncomment the following lines if you are working with raw emails with the\n",
    "    # full headers\n",
    "    # hdrstart = email_contents.find(chr(10) + chr(10))\n",
    "    # email_contents = email_contents[hdrstart:]\n",
    "\n",
    "    # Lower case\n",
    "    email_contents = email_contents.lower()\n",
    "    \n",
    "    # Strip all HTML\n",
    "    # Looks for any expression that starts with < and ends with > and replace\n",
    "    # and does not have any < or > in the tag it with a space\n",
    "    email_contents =re.compile('<[^<>]+>').sub(' ', email_contents)\n",
    "\n",
    "    # Handle Numbers\n",
    "    # Look for one or more characters between 0-9\n",
    "    email_contents = re.compile('[0-9]+').sub(' number ', email_contents)\n",
    "\n",
    "    # Handle URLS\n",
    "    # Look for strings starting with http:// or https://\n",
    "    email_contents = re.compile('(http|https)://[^\\s]*').sub(' httpaddr ', email_contents)\n",
    "\n",
    "    # Handle Email Addresses\n",
    "    # Look for strings with @ in the middle\n",
    "    email_contents = re.compile('[^\\s]+@[^\\s]+').sub(' emailaddr ', email_contents)\n",
    "    \n",
    "    # Handle $ sign\n",
    "    email_contents = re.compile('[$]+').sub(' dollar ', email_contents)\n",
    "    \n",
    "    # get rid of any punctuation\n",
    "    email_contents = re.split('[ @$/#.-:&*+=\\[\\]?!(){},''\">_<;%\\n\\r]', email_contents)\n",
    "\n",
    "    # remove any empty word string\n",
    "    email_contents = [word for word in email_contents if len(word) > 0]\n",
    "    \n",
    "    # Stem the email contents word by word\n",
    "    stemmer = utils.PorterStemmer()\n",
    "    processed_email = []\n",
    "    for word in email_contents:\n",
    "        # Remove any remaining non alphanumeric characters in word\n",
    "        word = re.compile('[^a-zA-Z0-9]').sub('', word).strip()\n",
    "        word = stemmer.stem(word)\n",
    "        processed_email.append(word)\n",
    "\n",
    "        if len(word) < 1:\n",
    "            continue\n",
    "\n",
    "        # Look up the word in the dictionary and add to word_indices if found\n",
    "        # ====================== YOUR CODE HERE ======================\n",
    "\n",
    "        \n",
    "\n",
    "        # =============================================================\n",
    "\n",
    "    if verbose:\n",
    "        print('----------------')\n",
    "        print('Processed email:')\n",
    "        print('----------------')\n",
    "        print(' '.join(processed_email))\n",
    "    return word_indices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once you have implemented `processEmail`, the following cell will run your code on the email sample and you should see an output of the processed email and the indices list mapping."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#  To use an SVM to classify emails into Spam v.s. Non-Spam, you first need\n",
    "#  to convert each email into a vector of features. In this part, you will\n",
    "#  implement the preprocessing steps for each email. You should\n",
    "#  complete the code in processEmail.m to produce a word indices vector\n",
    "#  for a given email.\n",
    "\n",
    "# Extract Features\n",
    "with open(os.path.join('Data', 'emailSample1.txt')) as fid:\n",
    "    file_contents = fid.read()\n",
    "\n",
    "word_indices  = processEmail(file_contents)\n",
    "\n",
    "#Print Stats\n",
    "print('-------------')\n",
    "print('Word Indices:')\n",
    "print('-------------')\n",
    "print(word_indices)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*You should now submit your solutions.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grader[3] = processEmail\n",
    "grader.grade()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id=\"section4\"></a>\n",
    "### 2.2 Extracting Features from Emails\n",
    "\n",
    "You will now implement the feature extraction that converts each email into a vector in $\\mathbb{R}^n$. For this exercise, you will be using n = # words in vocabulary list. Specifically, the feature $x_i \\in \\{0, 1\\}$ for an email corresponds to whether the $i^{th}$ word in the dictionary occurs in the email. That is, $x_i = 1$ if the $i^{th}$ word is in the email and $x_i = 0$ if the $i^{th}$ word is not present in the email.\n",
    "\n",
    "Thus, for a typical email, this feature would look like:\n",
    "\n",
    "$$ x = \\begin{bmatrix} \n",
    "0 & \\dots & 1 & 0 & \\dots & 1 & 0 & \\dots & 0 \n",
    "\\end{bmatrix}^T \\in \\mathbb{R}^n\n",
    "$$\n",
    "\n",
    "You should now complete the code in the function `emailFeatures` to generate a feature vector for an email, given the `word_indices`.\n",
    "<a id=\"emailFeatures\"></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def emailFeatures(word_indices):\n",
    "    \"\"\"\n",
    "    Takes in a word_indices vector and produces a feature vector from the word indices. \n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    word_indices : list\n",
    "        A list of word indices from the vocabulary list.\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    x : list \n",
    "        The computed feature vector.\n",
    "    \n",
    "    Instructions\n",
    "    ------------\n",
    "    Fill in this function to return a feature vector for the\n",
    "    given email (word_indices). To help make it easier to  process \n",
    "    the emails, we have have already pre-processed each email and converted\n",
    "    each word in the email into an index in a fixed dictionary (of 1899 words).\n",
    "    The variable `word_indices` contains the list of indices of the words \n",
    "    which occur in one email.\n",
    "    \n",
    "    Concretely, if an email has the text:\n",
    "\n",
    "        The quick brown fox jumped over the lazy dog.\n",
    "\n",
    "    Then, the word_indices vector for this text might look  like:\n",
    "               \n",
    "        60  100   33   44   10     53  60  58   5\n",
    "\n",
    "    where, we have mapped each word onto a number, for example:\n",
    "\n",
    "        the   -- 60\n",
    "        quick -- 100\n",
    "        ...\n",
    "\n",
    "    Note\n",
    "    ----\n",
    "    The above numbers are just an example and are not the actual mappings.\n",
    "\n",
    "    Your task is take one such `word_indices` vector and construct\n",
    "    a binary feature vector that indicates whether a particular\n",
    "    word occurs in the email. That is, x[i] = 1 when word i\n",
    "    is present in the email. Concretely, if the word 'the' (say,\n",
    "    index 60) appears in the email, then x[60] = 1. The feature\n",
    "    vector should look like:\n",
    "        x = [ 0 0 0 0 1 0 0 0 ... 0 0 0 0 1 ... 0 0 0 1 0 ..]\n",
    "    \"\"\"\n",
    "    # Total number of words in the dictionary\n",
    "    n = 1899\n",
    "\n",
    "    # You need to return the following variables correctly.\n",
    "    x = np.zeros(n)\n",
    "\n",
    "    # ===================== YOUR CODE HERE ======================\n",
    "\n",
    "    \n",
    "    \n",
    "    # ===========================================================\n",
    "    \n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once you have implemented `emailFeatures`, the next cell will run your code on the email sample. You should see that the feature vector had length 1899 and 45 non-zero entries."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Extract Features\n",
    "with open(os.path.join('Data', 'emailSample1.txt')) as fid:\n",
    "    file_contents = fid.read()\n",
    "\n",
    "word_indices  = processEmail(file_contents)\n",
    "features      = emailFeatures(word_indices)\n",
    "\n",
    "# Print Stats\n",
    "print('\\nLength of feature vector: %d' % len(features))\n",
    "print('Number of non-zero entries: %d' % sum(features > 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*You should now submit your solutions.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grader[4] = emailFeatures\n",
    "grader.grade()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 Training SVM for Spam Classification\n",
    "\n",
    "In the following section we will load a preprocessed training dataset that will be used to train a SVM classifier. The file `spamTrain.mat` (within the `Data` folder for this exercise) contains 4000 training examples of spam and non-spam email, while `spamTest.mat` contains 1000 test examples. Each\n",
    "original email was processed using the `processEmail` and `emailFeatures` functions and converted into a vector $x^{(i)} \\in \\mathbb{R}^{1899}$.\n",
    "\n",
    "After loading the dataset, the next cell proceed to train a linear SVM to classify between spam ($y = 1$) and non-spam ($y = 0$) emails. Once the training completes, you should see that the classifier gets a training accuracy of about 99.8% and a test accuracy of about 98.5%."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load the Spam Email dataset\n",
    "# You will have X, y in your environment\n",
    "data = loadmat(os.path.join('Data', 'spamTrain.mat'))\n",
    "X, y= data['X'].astype(float), data['y'][:, 0]\n",
    "\n",
    "print('Training Linear SVM (Spam Classification)')\n",
    "print('This may take 1 to 2 minutes ...\\n')\n",
    "\n",
    "C = 0.1\n",
    "model = utils.svmTrain(X, y, C, utils.linearKernel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Compute the training accuracy\n",
    "p = utils.svmPredict(model, X)\n",
    "\n",
    "print('Training Accuracy: %.2f' % (np.mean(p == y) * 100))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Execute the following cell to load the test set and compute the test accuracy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load the test dataset\n",
    "# You will have Xtest, ytest in your environment\n",
    "data = loadmat(os.path.join('Data', 'spamTest.mat'))\n",
    "Xtest, ytest = data['Xtest'].astype(float), data['ytest'][:, 0]\n",
    "\n",
    "print('Evaluating the trained Linear SVM on a test set ...')\n",
    "p = utils.svmPredict(model, Xtest)\n",
    "\n",
    "print('Test Accuracy: %.2f' % (np.mean(p == ytest) * 100))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4 Top Predictors for Spam\n",
    "\n",
    "To better understand how the spam classifier works, we can inspect the parameters to see which words the classifier thinks are the most predictive of spam. The next cell finds the parameters with the largest positive values in the classifier and displays the corresponding words similar to the ones shown in the figure below.\n",
    "\n",
    "<div style=\"border-style: solid; border-width: 1px; margin: 10px 10px 10px 10px; padding: 10px 10px 10px 10px\">\n",
    "our  click  remov guarante visit basenumb dollar pleas price will nbsp most lo ga hour\n",
    "</div>\n",
    "\n",
    "Thus, if an email contains words such as “guarantee”, “remove”, “dollar”, and “price” (the top predictors shown in the figure), it is likely to be classified as spam.\n",
    "\n",
    "Since the model we are training is a linear SVM, we can inspect the weights learned by the model to understand better how it is determining whether an email is spam or not. The following code finds the words with the highest weights in the classifier. Informally, the classifier 'thinks' that these words are the most likely indicators of spam."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Sort the weights and obtin the vocabulary list\n",
    "# NOTE some words have the same weights, \n",
    "# so their order might be different than in the text above\n",
    "idx = np.argsort(model['w'])\n",
    "top_idx = idx[-15:][::-1]\n",
    "vocabList = utils.getVocabList()\n",
    "\n",
    "print('Top predictors of spam:')\n",
    "print('%-15s %-15s' % ('word', 'weight'))\n",
    "print('----' + ' '*12 + '------')\n",
    "for word, w in zip(np.array(vocabList)[top_idx], model['w'][top_idx]):\n",
    "    print('%-15s %0.2f' % (word, w))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.5 Optional (ungraded) exercise: Try your own emails\n",
    "\n",
    "Now that you have trained a spam classifier, you can start trying it out on your own emails. In the starter code, we have included two email examples (`emailSample1.txt` and `emailSample2.txt`) and two spam examples (`spamSample1.txt` and `spamSample2.txt`). The next cell runs the spam classifier over the first spam example and classifies it using the learned SVM. You should now try the other examples we have provided and see if the classifier gets them right. You can also try your own emails by replacing the examples (plain text files) with your own emails.\n",
    "\n",
    "*You do not need to submit any solutions for this optional (ungraded) exercise.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "filename = os.path.join('Data', 'emailSample1.txt')\n",
    "\n",
    "with open(filename) as fid:\n",
    "    file_contents = fid.read()\n",
    "\n",
    "word_indices = processEmail(file_contents, verbose=False)\n",
    "x = emailFeatures(word_indices)\n",
    "p = utils.svmPredict(model, x)\n",
    "\n",
    "print('\\nProcessed %s\\nSpam Classification: %s' % (filename, 'spam' if p else 'not spam'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.6 Optional (ungraded) exercise: Build your own dataset\n",
    "\n",
    "In this exercise, we provided a preprocessed training set and test set. These datasets were created using the same functions (`processEmail` and `emailFeatures`) that you now have completed. For this optional (ungraded) exercise, you will build your own dataset using the original emails from the SpamAssassin Public Corpus.\n",
    "\n",
    "Your task in this optional (ungraded) exercise is to download the original\n",
    "files from the public corpus and extract them. After extracting them, you should run the `processEmail` and `emailFeatures` functions on each email to extract a feature vector from each email. This will allow you to build a dataset `X`, `y` of examples. You should then randomly divide up the dataset into a training set, a cross validation set and a test set.\n",
    "\n",
    "While you are building your own dataset, we also encourage you to try building your own vocabulary list (by selecting the high frequency words that occur in the dataset) and adding any additional features that you think\n",
    "might be useful. Finally, we also suggest trying to use highly optimized SVM toolboxes such as [`LIBSVM`](https://www.csie.ntu.edu.tw/~cjlin/libsvm/) or [`scikit-learn`](http://scikit-learn.org/stable/modules/classes.html#module-sklearn.svm).\n",
    "\n",
    "*You do not need to submit any solutions for this optional (ungraded) exercise.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}