13. Support Vector Machine (SVM).ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>\n",
       "\n",
       "div.cell { /* Tunes the space between cells */\n",
       "margin-top:1em;\n",
       "margin-bottom:1em;\n",
       "}\n",
       "\n",
       "div.text_cell_render h1 { /* Main titles bigger, centered */\n",
       "font-size: 2.2em;\n",
       "line-height:1.4em;\n",
       "text-align:center;\n",
       "}\n",
       "\n",
       "div.text_cell_render h2 { /*  Parts names nearer from text */\n",
       "margin-bottom: -0.4em;\n",
       "}\n",
       "\n",
       "\n",
       "div.text_cell_render { /* Customize text cells */\n",
       "font-family: 'Arial';\n",
       "font-size:1.5em;\n",
       "line-height:1.4em;\n",
       "padding-left:3em;\n",
       "padding-right:3em;\n",
       "}\n",
       "\n",
       ".MathJax {\n",
       "    font-size: 70%;\n",
       "}\n",
       "</style>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import HTML\n",
    "css_file = './custom.css'\n",
    "HTML(open(css_file, \"r\").read())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Support Vector Machine (SVM)\n",
    "\n",
    "© 2018 Daniel Voigt Godoy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Definition\n",
    "\n",
    "Support Vector Machine is a ***large margin classifier***. It means it tries to determine a ***decision boundary*** such that the points closer to it, belonging to opposite classes, are separate by the ***largest margin*** possible.\n",
    "\n",
    "Effectively, it determines a ***line*** (for 1D data), a ***plane*** (for 2D data) or a ***hyper-plane*** (for 3+D data), such that its interval ***[-1, 1]*** is ***clear of data points***.\n",
    "\n",
    "For 1D data:\n",
    "$$\n",
    "y' = b + w_1x_1\n",
    "$$\n",
    "\n",
    "Therefore:\n",
    "- points in the ***negative class*** should fall ***below -1*** in the line (or plane/hyperplane)\n",
    "- points in the ***positive class*** should fall ***above 1*** in the line (or plane/hyperplane)\n",
    "\n",
    "For mathematical convenience, instead of using the traditional $y = 0$ for a ***negative class***, we use $y = -1$:\n",
    "\n",
    "$$\n",
    "\\hat{y} = \n",
    "\\begin{cases} -1 &\\mbox{if } \\boldsymbol{w^Tx} \\leq -1 \\\\\n",
    "1 & \\mbox{if } \\boldsymbol{w^Tx} \\geq 1\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "### 1.1 Dot Product\n",
    "\n",
    "Another way of represnting $y'$ is by using the ***dot product***:\n",
    "\n",
    "$$\n",
    "\\boldsymbol{w^Tx} = p ||\\boldsymbol{w}||^2\n",
    "$$\n",
    "\n",
    "In a nutshell, $p$ is the projection of a given sample $x$ onto the $\\ell_2$ ***norm*** of the ***weights***.\n",
    "\n",
    "### 1.2 Hinge Loss\n",
    "\n",
    "You can think of the [-1, 1] interval as a ***demilitarized zone*** where ***no point should be***.\n",
    "So, if a given point falls above (or below) its border, it will have a ***loss*** corresponding to ***how far \"behind enemy lines\"*** it is.\n",
    "\n",
    "This is called a ***hinge loss***:\n",
    "\n",
    "$$\n",
    "loss = max(0, 1 - y * y')\n",
    "$$\n",
    "\n",
    "![](https://developers.google.com/machine-learning/glossary/images/hinge-loss.svg)\n",
    "<center>Source: Google's Machine Learning Glossary</center>\n",
    "\n",
    "### 1.3 Minimizing the Cost Function\n",
    "\n",
    "For 1D, the ***largest margin*** corresponds to the ***smallest slope*** of the line (hence, the ***smallest*** $w_1$). \n",
    "\n",
    "In a multidimensional problem, the ***largest margin*** corresponds to the ***smallest*** (squared) $\\ell_2$ ***norm***.\n",
    "\n",
    "$$\n",
    "J(\\boldsymbol{w}) = \\frac{1}{2}||\\boldsymbol{w}||^2\n",
    "$$\n",
    "\n",
    "But we want to minimize it ***while keeping an empty margin***, so the restrictions are:\n",
    "\n",
    "$$\n",
    "subject \\ to \n",
    "\\begin{cases} \\boldsymbol{w^Tx^{(i)}} \\leq -1 &\\mbox{if } y = -1 \\\\\n",
    "\\boldsymbol{w^Tx^{(i)}} \\geq 1 & \\mbox{if } y = 1\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "This is actually a ***different cost function***. It has a ***regularization term*** only.\n",
    "\n",
    "The ***hinge loss*** is part of the ***constraint*** alone!\n",
    "\n",
    "\n",
    "### 1.4 Soft Margin\n",
    "\n",
    "Sometimes it is not possible to have a ***hard margin***, that is, a ***truly empty margin***. We can relax this assumption by cutting some ***slack*** to misclassified points - their ***hinge losses*** will be multiplied by a factor ***C*** and ***added to the cost***.\n",
    "\n",
    "So, the cost function that allows ***soft margins*** is:\n",
    "\n",
    "$$\n",
    "J(\\boldsymbol{w}) = \\frac{1}{2}||\\boldsymbol{w}||^2 + C \\sum_i^m{max(0, 1 - y^{(i)}*y'^{(i)})}\n",
    "$$\n",
    "\n",
    "You can think of ***C*** as the ***hardness*** of your margin. Larger values of C correspond to a harder margin.\n",
    "\n",
    "What if C is ***zero***? Isn't it the same as the original ***hard margin*** cost function? \n",
    "\n",
    "Yes, BUT the ***hardness*** was actually defined by the ***constraints*** in the original formulation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Experiment\n",
    "\n",
    "Time to try it yourself!\n",
    "\n",
    "There are 8 points, 4 ***green*** (positive) and 4 ***red*** (negative) points.\n",
    "\n",
    "There is only ***one*** feature $x$. So, the ***boundary*** is going to be the ***line*** shown on top of the data.\n",
    "\n",
    "The red and green ***dashed vertical lines*** define the ***margin***, that is, when the ***boundary*** has a value of -1 or 1.\n",
    "\n",
    "Points ***between the dashed lines*** are ***violating the margin***.\n",
    "\n",
    "The upper right plot shows the ***slack or loss*** for each one of the data points.\n",
    "\n",
    "The lower right plot shows the ***costs*** due to both terms: weights and losses.\n",
    "\n",
    "The controls below allow you to:\n",
    "- change ***bias*** and ***weights*** of the SVM line\n",
    "- use ***soft margin*** for cost computation\n",
    "- adjust the ***hardness*** of the margin ***C***\n",
    "\n",
    "Use the controls to play with different configurations and answer the ***questions*** below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from intuitiveml.supervised.classification.SVM import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "x, y = data()\n",
    "mysvm = plotSVM(x, y)\n",
    "vb1 = VBox(build_figure(mysvm), layout={'align_items': 'center'})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "3647f5ec8fca46268158092d6cd54f1a",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "VBox(children=(FigureWidget({\n",
       "    'data': [{'marker': {'color': 'green', 'line': {'color': 'black', 'width': 2…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "vb1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Questions\n",
    "\n",
    "1. Initially, there are ***two points*** violating the margin. Try different values for $b$ and $w_1$ to get a ***clear margin*** (no losses).\n",
    "\n",
    "\n",
    "2. While clearing the margin, did you pay attention to the ***cost***? Make sure that your solution has the ***minimum cost*** possible.\n",
    "\n",
    "\n",
    "3. What happens to the ***margin width*** as you ***increase*** $w_1$?\n",
    "\n",
    "\n",
    "4. Set $b$ back to 0 and $w_1$ back to 1. Check ***Use Soft Margin***. What happened to your cost?\n",
    "\n",
    "\n",
    "5. Try different values for $b$ and $w_1$ to ***minimize the cost***. This time, you ***may have points inside the margin***. Which value for $w_1$ did you get? Is it bigger or smaller than before? Why? Is the margin ***wider*** or ***narrower***?\n",
    "\n",
    "\n",
    "6. Change ***C*** to 0.1 and repeat the process. How did $w_1$ and the margin change? What does it mean to the ***hardness*** of the margin?\n",
    "\n",
    "\n",
    "7. Change ***C*** to 100.0 and repeat the process. How did $w_1$ and the margin change? What does it mean to the ***hardness*** of the margin?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Kernel Trick\n",
    "\n",
    "What if the ***two right-most*** points were ***red***? \n",
    "\n",
    "How can you possible draw a ***line*** to separate the colors? You can achieve that by using the ***kernel trick***!\n",
    "\n",
    "The idea is to ***increase dimensionality of the data*** (really!) to be able to achieve a linear separation. in ***higher dimensions***, data is more ***sparse*** and it is easier to find a ***hyper-plane*** that separates data ***linearly***.\n",
    "\n",
    "In our modified example, we can map every 1D point $x$ to a 2D point ($x, x^2)$. This is a ***polynomial kernel***.\n",
    "\n",
    "Going from 1D to 2D allows for a ***linear separation***, as you can see in the plot below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = np.array([-2.8, -2.2, -1.8, -1.3, -.4, 0.7, 1.1, 1.3, 1.9, 2.5])\n",
    "x2 = x ** 2\n",
    "x = np.concatenate([x.reshape(-1, 1), x2.reshape(-1, 1)], axis=1)\n",
    "y = np.array([0., 0., 0., 0., 0., 1., 1., 1., 0., 0.])\n",
    "\n",
    "mysvm3 = plotSVM(x=x, y=y)\n",
    "mysvm3.fit(is_soft=False)\n",
    "vb3 = VBox(build_3dfigure(mysvm3), layout={'align_items': 'center'})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "b1369ed808864fddaa3e6d578ed6028f",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "VBox(children=(FigureWidget({\n",
       "    'data': [{'marker': {'color': 'green', 'size': 5},\n",
       "              'mode': 'ma…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "vb3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Kernels\n",
    "\n",
    "These are some popular kernels commonly used with SVMs:\n",
    "\n",
    "1. ***Linear***: the same as ***no*** kernel\n",
    "2. ***Polynomial***: increases dimensions by generating polynomial features\n",
    "3. ***Sigmoid***: uses a sigmoid function as kernel\n",
    "4. ***Gaussian RBF***: it works as a ***similarity*** measure or ***distance***, it theoretically maps the points to an ***infinite-dimensional*** space!\n",
    "\n",
    "The last kernel actually raises a question: ***how to map into an infinite-dimensional*** space? It turns out, you ***don't***! \n",
    "\n",
    "Thanks to the mathematical properties of the ***dot product***, it is possible to compute the projection $p$ without performing the actual mapping. But this is ***beyond our scope*** now."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Scikit-Learn\n",
    "\n",
    "[SVM](https://scikit-learn.org/stable/modules/svm.html)\n",
    "\n",
    "Please check Aurelién Geron's \"Hand-On Machine Learning with Scikit-Learn and Tensorflow\" notebook on Support Vector Machines [here](https://github.com/ageron/handson-ml/blob/master/05_support_vector_machines.ipynb).\n",
    "\n",
    "You can also find a 3D plot of one os his examples, using the Iris Dataset, below:\n",
    "\n",
    "```python\n",
    "from sklearn import datasets\n",
    "iris = datasets.load_iris()\n",
    "\n",
    "y = iris['target']\n",
    "x = iris['data'][y != 2][:, (2, 3)]\n",
    "y = y[y != 2]\n",
    "\n",
    "# C = infinity -> Hard Margin\n",
    "svc = LinearSVC(fit_intercept=True, C=np.inf, loss='hinge')\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import datasets\n",
    "iris = datasets.load_iris()\n",
    "\n",
    "y = iris['target']\n",
    "x = iris['data'][y != 2][:, (2, 3)]\n",
    "y = y[y != 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "7933893f6ad34e8dbd973f3a83352be3",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "VBox(children=(FigureWidget({\n",
       "    'data': [{'marker': {'color': 'green', 'size': 5},\n",
       "              'mode': 'ma…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "mysvm2 = plotSVM(x=x, y=y)\n",
    "mysvm2.fit(is_soft=False)\n",
    "vb2 = VBox(build_3dfigure(mysvm2), layout={'align_items': 'center'})\n",
    "\n",
    "vb2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. More Resources\n",
    "\n",
    "[InfoGraphic](https://github.com/Avik-Jain/100-Days-Of-ML-Code/blob/master/Info-graphs/Day%2012.jpg)\n",
    "\n",
    "[SVM Explorer](https://github.com/plotly/dash-svm)\n",
    "\n",
    "[Support Vector Machines Tutorial](https://blog.statsbot.co/support-vector-machines-tutorial-c1618e635e93)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### This material is copyright Daniel Voigt Godoy and made available under the Creative Commons Attribution (CC-BY) license ([link](https://creativecommons.org/licenses/by/4.0/)). \n",
    "\n",
    "#### Code is also made available under the MIT License ([link](https://opensource.org/licenses/MIT))."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<script>\n",
       "  function code_toggle() {\n",
       "    if (code_shown){\n",
       "      $('div.input').hide('500');\n",
       "      $('#toggleButton').val('Show Code')\n",
       "    } else {\n",
       "      $('div.input').show('500');\n",
       "      $('#toggleButton').val('Hide Code')\n",
       "    }\n",
       "    code_shown = !code_shown\n",
       "  }\n",
       "\n",
       "  $( document ).ready(function(){\n",
       "    code_shown=false;\n",
       "    $('div.input').hide()\n",
       "  });\n",
       "</script>\n",
       "<form action=\"javascript:code_toggle()\"><input type=\"submit\" id=\"toggleButton\" value=\"Show Code\"></form>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import HTML\n",
    "HTML('''<script>\n",
    "  function code_toggle() {\n",
    "    if (code_shown){\n",
    "      $('div.input').hide('500');\n",
    "      $('#toggleButton').val('Show Code')\n",
    "    } else {\n",
    "      $('div.input').show('500');\n",
    "      $('#toggleButton').val('Hide Code')\n",
    "    }\n",
    "    code_shown = !code_shown\n",
    "  }\n",
    "\n",
    "  $( document ).ready(function(){\n",
    "    code_shown=false;\n",
    "    $('div.input').hide()\n",
    "  });\n",
    "</script>\n",
    "<form action=\"javascript:code_toggle()\"><input type=\"submit\" id=\"toggleButton\" value=\"Show Code\"></form>''')"
   ]
  },
  {
   "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.5.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}