Support Vector Machine/2. SVM with hard margin (from scratch).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# We have convex quadratic optimization problem \n",
    "\n",
    "$$\n",
    "\\begin{array}{ll}{\\underset{\\mathbf{w}, b}{\\operatorname{minimize}}} & {\\frac{1}{2}\\|\\mathbf{w}\\|^{2}} \\\\ {\\text { subject to }} & {y_{i}\\left(\\mathbf{w} \\cdot \\mathbf{x}_{i}+b\\right)-1 \\geq 0, i=1, \\ldots, m}\\end{array}\n",
    "$$\n",
    "\n",
    "### this problem can be solve by using Lagrange Multiplier\n",
    "\n",
    "# Lagrange multiplier\n",
    "\n",
    "The Italian-French mathematician Giuseppe Lodovico Lagrangia, also known as JosephLouis Lagrange, invented a strategy for finding the local maxima and minima of a function subject to equality constraint. It is called the method of Lagrange multipliers.\n",
    "\n",
    "let,\n",
    "$$\n",
    "\\begin{array}{c}{f(\\mathbf{w})=\\frac{1}{2}\\|\\mathbf{w}\\|^{2}} \\\\ {g_{i}(\\mathbf{w}, b)=y_{i}\\left(\\mathbf{w} \\cdot \\mathbf{x}_{i}+b\\right)-1, i=1, \\ldots, m}\\end{array}\n",
    "$$\n",
    "and 'm' constraint functions\n",
    "\n",
    "We introduce the Lagrangian function to this function:\n",
    "\n",
    "$$\n",
    "\\begin{array}{c}{\\mathcal{L}(\\mathbf{w}, b, \\alpha)=f(\\mathbf{w})-\\sum_{i=1}^{m} \\alpha_{i} g_{i}(\\mathbf{w}, b)} \\\\ {\\mathcal{L}(\\mathbf{w}, b, \\alpha)=\\frac{1}{2}\\|\\mathbf{w}\\|^{2}-\\sum_{i=1}^{m} \\alpha_{i}\\left[y_{i}\\left(\\mathbf{w} \\cdot \\mathbf{x}_{i}+b\\right)-1\\right]}\\end{array}\n",
    "$$\n",
    "\n",
    "You may have noticed that the method of Lagrange multipliers is used for solving problems with equality constraints, and here we are using them with inequality constraints. This is because the method still works for inequality constraints, provided some additional conditions (the KKT conditions) are met\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Wolfe dual problem \n",
    "\n",
    "The Lagrangian problem has 'm' inequality constraints (where 'm' is the number of training examples) and is typically solved using its dual form. The duality principle tells us that an optimization problem can be viewed from two perspectives. The first one is the primal problem, a minimization problem in our case, and the other one is the dual problem, which will be a maximization problem. What is interesting is that the maximum of the dual problem will always be less than or equal to the minimum of the primal problem (we say it provides a lower bound to the solution of the primal problem). \n",
    "\n",
    "The Lagrangian primal problem is:\n",
    "$$\n",
    "\\begin{array}{ll}{\\min _{\\mathbf{w}, b}} & {\\max _{\\alpha} \\quad \\mathcal{L}(\\mathbf{w}, b, \\alpha)} \\\\ {\\text { subject to }} & {\\alpha_{i} \\geq 0, \\quad i=1, \\ldots, m}\\end{array}\n",
    "$$\n",
    "\n",
    "Solving the minimization problem involves taking the partial derivatives of 'L' with respect to 'w' and 'b'.\n",
    "\n",
    "$$\n",
    "\\begin{array}{c}{\\nabla_{\\mathbf{w}} \\mathcal{L}=\\mathbf{w}-\\sum_{i=1}^{m} \\alpha_{i} y_{i} \\mathbf{x}_{i}=\\mathbf{0}} \\\\ {\\frac{\\partial \\mathcal{L}}{\\partial b}=-\\sum_{i=1}^{m} \\alpha_{i} y_{i}=0}\\end{array}\n",
    "$$\n",
    "\n",
    "From the first equation, we find that:\n",
    " \n",
    "$$\n",
    "\\mathbf{w}=\\sum_{i=1}^{m} \\alpha_{i} y_{i} \\mathbf{x}_{i}\n",
    "$$\n",
    "\n",
    "Let us substitute :\n",
    "\n",
    "\n",
    "$$\n",
    "\\begin{aligned} W(\\alpha, b) &=\\frac{1}{2}\\left(\\sum_{i=1}^{m} \\alpha_{i} y_{i} \\mathbf{x}_{i}\\right) \\cdot\\left(\\sum_{j=1}^{m} \\alpha_{j} y_{j} \\mathbf{x}_{j}\\right)-\\sum_{i=1}^{m} \\alpha_{i}\\left[y_{i}\\left(\\left(\\sum_{j=1}^{m} \\alpha_{j} y_{j} \\mathbf{x}_{j}\\right) \\cdot \\mathbf{x}_{i}+b\\right)-1\\right] \\\\ &=\\frac{1}{2} \\sum_{i=1}^{m} \\sum_{j=1}^{m} \\alpha_{i} \\alpha_{j} y_{i} y_{i} \\mathbf{x}_{i} \\cdot \\mathbf{x}_{j}-\\sum_{i=1}^{m} \\sum_{j=1}^{m} \\alpha_{i} \\alpha_{j} y_{i} y_{i} \\mathbf{x}_{i} \\cdot \\mathbf{x}_{j}-b \\sum_{i=1}^{m} \\alpha_{i} y_{i}+\\sum_{i=1}^{m} \\alpha_{i} \\\\ &=\\sum_{i=1}^{m} \\alpha_{i}-\\frac{1}{2} \\sum_{i=1}^{m} \\sum_{j=1}^{m} \\alpha_{i} \\alpha_{j} y_{i} y_{j} \\mathbf{x}_{i} \\cdot \\mathbf{x}_{j}-b \\sum_{i=1}^{m} \\alpha_{i} y_{i} \\end{aligned}\n",
    "$$\n",
    " \n",
    "The optimization problem is now called the **Wolfe dual problem**\n",
    "\n",
    "\n",
    "$$\n",
    "\\begin{array}{cl}{\\underset{\\alpha}{\\operatorname{maximize}}} & {\\sum_{i=1}^{m} \\alpha_{i}-\\frac{1}{2} \\sum_{i=1}^{m} \\sum_{j=1}^{m} \\alpha_{i} \\alpha_{j} y_{i} y_{j} \\mathbf{x}_{i} \\cdot \\mathbf{x}_{j}} \\\\ {\\text { subject to }} & {\\alpha_{i} \\geq 0, \\text { for any } i=1, \\ldots, m} \\\\ {} & {\\sum_{i=1}^{m} \\alpha_{i} y_{i}=0}\\end{array}\n",
    "$$\n",
    "\n",
    "\n",
    "# Karush-Kuhn-Tucker conditions\n",
    "\n",
    "Because we are dealing with inequality constraints, there is an additional requirement: the solution must also satisfy the Karush-Kuhn-Tucker (KKT) conditions. \n",
    " \n",
    "The KKT conditions are first-order necessary conditions for a solution of an optimization problem to be optimal. Moreover, the problem should satisfy some regularity conditions. Luckily for us, one of the regularity conditions is Slater’s condition, and we just saw that it holds for SVMs. Because the primal problem we are trying to solve is a convex problem, the KKT conditions are also sufficient for the point to be primal and dual optimal, and there is zero duality gap. \n",
    "\n",
    "1. Stationarity Condition:\n",
    "$$\n",
    "\\begin{array}{c}{\\nabla_{\\mathrm{w}} \\mathcal{L}=\\mathbf{w}-\\sum_{i=1}^{m} \\alpha_{i} y_{i} \\mathbf{x}_{i}=\\mathbf{0}} \\\\ {\\frac{\\partial \\mathcal{L}}{\\partial b}=-\\sum_{i=1}^{m} \\alpha_{i} y_{i}=0}\\end{array}\n",
    "$$\n",
    "2. Primal feasibility condition:\n",
    "$$\n",
    "y_{i}\\left(\\mathbf{w} \\cdot \\mathbf{x}_{i}+b\\right)-1 \\geq 0 \\quad \\text { for all } i=1, \\ldots, m\n",
    "$$\n",
    "\n",
    "3. Dual feasibility condition:\n",
    "\n",
    "$$\n",
    "\\alpha_{i} \\geq 0 \\quad \\text { for all } i=1, \\ldots, m\n",
    "$$\n",
    "\n",
    "4. Complementarity slackness condition: \n",
    "$$\n",
    "\\alpha_{i}\\left[y_{i}\\left(\\mathbf{w} \\cdot \\mathbf{x}_{i}+b\\right)-1\\right]=0 \\quad \\text { for all } i=1, \\ldots, m\n",
    "$$\n",
    "\n",
    "\n",
    "# Hypothesis function \n",
    "The SVMs use the same hypothesis function as the Perceptron. The class of an example 'x' is given by: \n",
    "$$\n",
    "h\\left(\\mathbf{x}_{i}\\right)=\\operatorname{sign}\\left(\\mathbf{w} \\cdot \\mathbf{x}_{i}+b\\right)\n",
    "$$\n",
    "\n",
    "When using the dual formulation, it is computed using only the support vectors: \n",
    "\n",
    "$$\n",
    "h\\left(\\mathbf{x}_{i}\\right)=\\operatorname{sign}\\left(\\sum_{j=1}^{S} \\alpha_{j} y_{j}\\left(\\mathbf{x}_{j} \\cdot \\mathbf{x}_{i}\\right)+b\\right)\n",
    "$$\n",
    "\n",
    "# Solving SVMs with a QP solver \n",
    "\n",
    "A QP solver is a program used to solve quadratic programming problems. In the following example, we will use the Python package called CVXOPT\n",
    "\n",
    "This package provides a method that is able to solve quadratic problems of the form\n",
    "\n",
    "$$\n",
    "\\begin{array}{cl}{\\underset{x}{\\operatorname{minimize}}} & {\\frac{1}{2} x^{T} P x+q^{T} x} \\\\ {\\text { subject to }} & {G x \\leq h} \\\\ {} & {A x=b}\\end{array}\n",
    "$$\n",
    "\n",
    "It does not look like our optimization problem, so we will need to rewrite it so that we can solve it with this package.  \n",
    "First, we note that in the case of the Wolfe dual optimization problem, what we are trying to minimize is , so we can rewrite the quadratic problem with  instead of  to better see how the two problems relate\n",
    "\n",
    "$$\n",
    "\\begin{array}{cl}{\\underset{x}{\\operatorname{minimize}}} & {\\frac{1}{2} \\alpha^{T} P \\alpha+q^{T} \\alpha} \\\\ {\\text { subject to }} & {G \\alpha \\leq h} \\\\ {} & {A \\alpha=b}\\end{array}\n",
    "$$\n",
    "\n",
    "We will change the Wolfe dual problem. First, we transform the maximization problem\n",
    "\n",
    "$$\n",
    "\\begin{array}{cl}{\\underset{\\alpha}{\\operatorname{maximize}}} & {-\\frac{1}{2} \\sum_{i=1}^{m} \\sum_{j=1}^{m} \\alpha_{i} \\alpha_{j} y_{i} y_{j} \\mathbf{x}_{i} \\cdot \\mathbf{x}_{j}+\\sum_{i=1}^{m} \\alpha_{i}} \\\\ {\\text { subject to }} & {\\alpha_{i} \\geq 0, \\text { for any } i=1, \\ldots, m} \\\\ {} & {\\sum_{i=1}^{m} \\alpha_{i} y_{i}=0}\\end{array}\n",
    "$$\n",
    "\n",
    "into a minimization problem by multiplying by -1. \n",
    "\n",
    "$$\n",
    "\\begin{array}{cl}{\\underset{\\alpha}{\\operatorname{minimize}}} & {\\frac{1}{2} \\sum_{i=1}^{m} \\sum_{j=1}^{m} \\alpha_{i} \\alpha_{j} y_{i} y_{j} \\mathbf{x}_{i} \\cdot \\mathbf{x}_{j}-\\sum_{i=1}^{m} \\alpha_{i}} \\\\ {\\text { subject to }} & {-\\alpha_{i} \\leq 0, \\text { for any } i=1, \\ldots, m} \\\\ {} & {\\sum_{i=1}^{m} \\alpha_{i} y_{i}=0}\\end{array}\n",
    "$$\n",
    "\n",
    "\n",
    "$$\n",
    "K\\left(\\mathbf{x}_{1}, \\ldots, \\mathbf{x}_{m}\\right)=\\left(\\begin{array}{cccc}{\\mathbf{x}_{1} \\cdot \\mathbf{x}_{1}} & {\\mathbf{x}_{1} \\cdot \\mathbf{x}_{2}} & {\\dots} & {\\mathbf{x}_{1} \\cdot \\mathbf{x}_{m}} \\\\ {\\mathbf{x}_{2} \\cdot \\mathbf{x}_{1}} & {\\mathbf{x}_{2} \\cdot \\mathbf{x}_{2}} & {\\ldots} & {\\mathbf{x}_{2} \\cdot \\mathbf{x}_{m}} \\\\ {\\vdots} & {\\vdots} & {\\ddots} & {\\vdots} \\\\ {\\mathbf{x}_{m} \\cdot \\mathbf{x}_{1}} & {\\mathbf{x}_{m} \\cdot \\mathbf{x}_{2}} & {\\dots} & {\\mathbf{x}_{m} \\cdot \\mathbf{x}_{m}}\\end{array}\\right)\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\alpha=\\left(\\alpha_{1}, \\ldots, \\alpha_{m}\\right)^{T} \\text { and } \\mathbf{y}=\\left(y_{1}, \\cdots, y_{m}\\right)^{T}\n",
    "$$\n",
    "\n",
    "\n",
    "We use them to construct a vectorized version of the Wolfe dual problem where 'yyT' denotes the outer product of 'y' \n",
    "\n",
    "$$\n",
    "\\begin{array}{cl}{\\underset{\\alpha}{\\operatorname{minimize}}} & {\\frac{1}{2} \\alpha^{T}\\left(\\mathbf{y y}^{T} K\\right) \\alpha-\\alpha} \\\\ {\\text { subject to }} & {-\\alpha \\leq 0} \\\\ {} & {\\mathbf{y} \\cdot \\alpha=0}\\end{array}\n",
    "$$\n",
    "\n",
    "We are now able to find out the value for each of the parameters $P, q, G, h, A, \\text { and } b$  required by the CVXOPT qp function. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "import cvxopt.solvers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 188,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_training_examples():\n",
    "    X1 = np.array([[8, 7], [4, 10], [9, 7], [7, 10],\n",
    "                   [9, 6], [4, 8], [10, 10]])\n",
    "    y1 = np.ones(len(X1))\n",
    "    X2 = np.array([[2, 7], [8, 3], [7, 5], [4, 4],\n",
    "                   [4, 6], [1, 3], [2, 5]])\n",
    "    y2 = np.ones(len(X2)) * -1\n",
    "    return X1, y1, X2, y2\n",
    "\n",
    "def get_dataset(get_examples):\n",
    "    X1, y1, X2, y2 = get_examples()\n",
    "    X, y = get_dataset_for(X1, y1, X2, y2)\n",
    "    return X, y\n",
    "\n",
    "def get_dataset_for(X1, y1, X2, y2):\n",
    "    X = np.vstack((X1, X2))\n",
    "    y = np.hstack((y1, y2))\n",
    "    return X, y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "X, y = get_dataset(get_training_examples) \n",
    "m = X.shape[0] \n",
    "\n",
    "# Gram matrix - The matrix of all possible inner products of X. \n",
    "K = np.array([np.dot(X[i], X[j])\n",
    "              for i in range(m)\n",
    "              for j in range(m)]).reshape((m, m)) \n",
    "P = cvxopt.matrix(np.outer(y, y) * K) \n",
    "q = cvxopt.matrix(-1 * np.ones(m)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let alpha be 1 for all obervations\n",
    "# Equality constraints \n",
    "A = cvxopt.matrix(y, (1, m)) # create 1*m matrix of y \n",
    "b = cvxopt.matrix(0.0) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Inequality constraints \n",
    "G = cvxopt.matrix(np.diag(-1 * np.ones(m))) \n",
    "h = cvxopt.matrix(np.zeros(m)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "     pcost       dcost       gap    pres   dres\n",
      " 0: -3.9356e+00 -7.2072e+00  4e+01  6e+00  2e+00\n",
      " 1: -5.9831e+00 -4.3032e+00  1e+01  2e+00  6e-01\n",
      " 2: -5.6350e-01 -1.1535e+00  2e+00  1e-01  4e-02\n",
      " 3: -6.2758e-01 -7.4538e-01  1e-01  2e-16  8e-15\n",
      " 4: -7.1507e-01 -7.1641e-01  1e-03  1e-16  7e-15\n",
      " 5: -7.1604e-01 -7.1605e-01  1e-05  2e-16  6e-15\n",
      " 6: -7.1605e-01 -7.1605e-01  1e-07  1e-16  4e-15\n",
      "Optimal solution found.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'x': <14x1 matrix, tc='d'>,\n",
       " 'y': <1x1 matrix, tc='d'>,\n",
       " 's': <14x1 matrix, tc='d'>,\n",
       " 'z': <14x1 matrix, tc='d'>,\n",
       " 'status': 'optimal',\n",
       " 'gap': 1.3419469236840556e-07,\n",
       " 'relative gap': 1.874098546047417e-07,\n",
       " 'primal objective': -0.716049284875814,\n",
       " 'dual objective': -0.7160494190705058,\n",
       " 'primal infeasibility': 1.110223024627425e-16,\n",
       " 'dual infeasibility': 3.964544722955217e-15,\n",
       " 'primal slack': 1.1266506979823477e-09,\n",
       " 'dual slack': 1.487034108307884e-08,\n",
       " 'iterations': 6}"
      ]
     },
     "execution_count": 114,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Solve the problem \n",
    "solution = cvxopt.solvers.qp(P, q, G, h, A, b) # return # dictionary which contains iterators\n",
    "solution  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1.1266506979823502e-09,\n",
       " 2.0459666064668313e-09,\n",
       " 2.2070588989814694e-09,\n",
       " 2.6220191259876066e-09,\n",
       " 3.0034651454022074e-09,\n",
       " 3.145946131950106e-09,\n",
       " 3.222391455730383e-09,\n",
       " 5.628814152545174e-09,\n",
       " 5.671715746141487e-09,\n",
       " 3.982638202441447e-08,\n",
       " 0.2540133015844077,\n",
       " 0.26450515438400674,\n",
       " 0.4515441819858147,\n",
       " 0.46203599749168495]"
      ]
     },
     "execution_count": 131,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Lagrange multipliers \n",
    "multipliers = np.ravel(solution['x']) \n",
    "multipliers\n",
    "sorted(multipliers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Support vectors have positive multipliers. \n",
    "has_positive_multiplier = multipliers > 1e-07 \n",
    "sv_multipliers = multipliers[has_positive_multiplier] \n",
    " \n",
    "support_vectors = X[has_positive_multiplier] \n",
    "support_vectors_y = y[has_positive_multiplier] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[9, 6],\n",
       "       [4, 8],\n",
       "       [2, 7],\n",
       "       [7, 5]])"
      ]
     },
     "execution_count": 152,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "support_vectors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "metadata": {},
   "outputs": [],
   "source": [
    "# computing 'w'\n",
    "def compute_w(multipliers, X, y):\n",
    "    return np.sum(multipliers[i] * y[i] * X[i] for i in range(len(y))) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.44444446 1.11111114]\n",
      "[0.44444453 1.11111128]\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Users\\GirrajJangid\\Anaconda3\\lib\\site-packages\\ipykernel_launcher.py:3: DeprecationWarning: Calling np.sum(generator) is deprecated, and in the future will give a different result. Use np.sum(np.fromiter(generator)) or the python sum builtin instead.\n",
      "  This is separate from the ipykernel package so we can avoid doing imports until\n"
     ]
    }
   ],
   "source": [
    "w = compute_w(multipliers, X, y) \n",
    "w_from_sv = compute_w(sv_multipliers, support_vectors, support_vectors_y)\n",
    " \n",
    "print(w)          # [0.44444446 1.11111114] \n",
    "print(w_from_sv)  # [0.44444446 1.11111114]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute 'b'\n",
    "def compute_b(w, X, y):\n",
    "    return np.sum([y[i] - np.dot(w, X[i]) for i in range(len(X))])/len(X)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-9.666666925153786"
      ]
     },
     "execution_count": 174,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b = compute_b(w, support_vectors, support_vectors_y) # -9.666668268506335 \n",
    "b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 246,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD8CAYAAABn919SAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAEINJREFUeJzt3XuMXGd5x/HvU2cjxmnxAlkQ9iY1kdAWFAyORgiIGlGM6lJikqJipRJVRFH9D6oDqkzj/mGopQoqowJWJSQr3Cpo6DYYQ1CLiUxTVKmkGsdgOwQLlUu864AHgbdcRmVjnv4xs1nbONnMZeeM3/l+JOvMef3OvI/O5bdnzzmzJzITSdKV7zeqLkCSNBgGuiQVwkCXpEIY6JJUCANdkgphoEtSIQx0SSqEgS5JhTDQJakQVw1zsGuvvTY3btw4zCEl6Yp39OjRH2Xm1Er9hhroGzdupNFoDHNISbriRcT3n0k/T7lIUiEMdEkqhIEuSYUw0CWpEAa6JBVixUCPiI9FxNmIOHlB23Mj4oGI+HZn+pzVLVOStJJnctviJ4B/AP7xgra7gSOZ+f6IuLsz/1eDL0+j7NCxefYdPsWZcy3WT9bYtXWG2zdvqLqsseX6GD3DXicrBnpmfjUiNl7SfBvw2s7rTwIPYqCPlUPH5tl98AStxfMAzJ9rsfvgCQBDpAKuj9FTxTrp9Rz6CzLzcYDO9PmDK0lXgn2HTz25oS5pLZ5n3+FTFVU03lwfo6eKdbLqF0UjYkdENCKi0Ww2V3s4DcmZc62u2rW6XB+jp4p10mug/zAiXgjQmZ59qo6ZeSAz65lZn5pa8U8R6AqxfrLWVbtWl+tj9FSxTnoN9C8Ad3Ze3wl8fjDl6Eqxa+sMtYk1F7XVJtawa+tMRRWNN9fH6Klinax4UTQi7qV9AfTaiJgD3gO8H5iNiLcDjwFvWbUKNZKWLup4V8VocH2MnirWSWTmqn34per1evrXFiWpOxFxNDPrK/Xzm6KSVAgDXZIKYaBLUiEMdEkqhIEuSYUw0CWpEAa6JBXCQJekQhjoklQIA12SCmGgS1IhDHRJKoSBLkmFMNAlqRAGuiQVwkCXpEIY6JJUCANdkgphoEtSIfoK9Ii4KyJORsQjEfHOQRUlSepez4EeETcCfw68Eng5cGtEvHhQhUmSutPPEfpLgK9l5i8y8wngP4A/GkxZkqRu9RPoJ4FbIuJ5EbEW+EPgusGUJUnq1lW9vjEzH42IvwMeAH4GfAN44tJ+EbED2AFw/fXX9zqcJGkFfV0UzcyPZuZNmXkL8GPg25fpcyAz65lZn5qa6mc4SdLT6PkIHSAinp+ZZyPieuDNwKsHU5YkqVt9BTrw2Yh4HrAIvCMzfzKAmiRJPegr0DPzdwdViCSpP35TVJIKYaBLUiEMdEkqhIEuSYUw0CWpEAa6JBXCQJekQhjoklQIA12SCmGgS1IhDHRJKoSBLkmFMNAlqRAGuiQVwkCXpEIY6JJUCANdkgphoEtSIQx0SSpEX4EeEe+KiEci4mRE3BsRzxpUYZKk7vT8kOiI2ADsBF6ama2ImAXuAD4xoNo04g4dm2ff4VOcOddi/WSNXVtnuH3zhqrLksZWz4F+wftrEbEIrAXO9F+SrgSHjs2z++AJWovnAZg/12L3wRMAhrpUkZ5PuWTmPPAB4DHgcWAhM788qMI02vYdPvVkmC9pLZ5n3+FTFVUkqedAj4jnALcBLwLWA9dExFsv029HRDQiotFsNnuvVCPlzLlWV+2SVl8/F0VfD3w3M5uZuQgcBF5zaafMPJCZ9cysT01N9TGcRsn6yVpX7ZJWXz+B/hjwqohYGxEBbAEeHUxZGnW7ts5Qm1hzUVttYg27ts5UVJGkni+KZuZDEXEf8DDwBHAMODCowjTali58epeLNDoiM4c2WL1ez0ajMbTxJKkEEXE0M+sr9fObopJUCANdkgphoEtSIQx0SSqEgS5JhTDQJakQBrokFcJAl6RCGOiSVAgDXZIKYaBLUiEMdEkqhIEuSYUw0CWpEAa6JBXCQJekQhjoklQIA12SCmGgS1Ihen5IdETMAP98QdMNwJ7M/FDfVY2y47NwZC8szMG6adiyBzZtr7oqaWQcOjY/Eg8PH5U6hqnnQM/MU8ArACJiDTAPfG5AdY2m47Nw/05YbLXnF06358FQl2iH6O6DJ2gtngdg/lyL3QdPAAw1TEeljmEb1CmXLcD/ZOb3B/R5o+nI3uUwX7LYardLYt/hU0+G6JLW4nn2HT41lnUM26AC/Q7g3sv9R0TsiIhGRDSazeaAhqvIwlx37dKYOXOu1VV76XUMW9+BHhFXA28C/uVy/5+ZBzKznpn1qampfoer1rrp7tqlMbN+stZVe+l1DNsgjtDfADycmT8cwGeNti17YOKSDWKi1m6XxK6tM9Qm1lzUVptYw66tM2NZx7D1fFH0An/CU5xuKc7ShU/vcpEua+mCY9V3l4xKHcMWmdn7myPWAqeBGzJzYaX+9Xo9G41Gz+NJ0jiKiKOZWV+pX19H6Jn5C+B5/XyGJGkw/KaoJBXCQJekQhjoklQIA12SCmGgS1IhDHRJKoSBLkmFMNAlqRAGuiQVwkCXpEIY6JJUCANdkgphoEtSIQx0SSqEgS5JhTDQJakQBrokFcJAl6RCGOiSVIi+nikaEZPAPcCNQAJ/lpn/NYjCdAU4PgtH9sLCHKybhi17YNP2qquSADh0bJ59h09x5lyL9ZM1dm2d4fbNG6oua1X1FejAh4EvZeYfR8TVwNoB1KQrwfFZuH8nLLba8wun2/NgqKtyh47Ns/vgCVqL5wGYP9di98ETAEWHes+nXCLi2cAtwEcBMvOXmXluUIVpxB3ZuxzmSxZb7XapYvsOn3oyzJe0Fs+z7/Cpiioajn7Ood8ANIGPR8SxiLgnIq65tFNE7IiIRkQ0ms1mH8NppCzMddcuDdGZc62u2kvRT6BfBdwEfCQzNwM/B+6+tFNmHsjMembWp6am+hhOI2XddHft0hCtn6x11V6KfgJ9DpjLzIc68/fRDniNgy17YOKSnWOi1m6XKrZr6wy1iTUXtdUm1rBr60xFFQ1Hz4GemT8ATkfE0hLaAnxzIFVp9G3aDtv2w7rrgGhPt+33gqhGwu2bN/C+N7+MDZM1AtgwWeN9b35Z0RdEASIze39zxCto37Z4NfAd4G2Z+ZOn6l+v17PRaPQ8niSNo4g4mpn1lfr1ddtiZn4dWHEQSdLq85uiklQIA12SCmGgS1IhDHRJKoSBLkmFMNAlqRAGuiQVwkCXpEIY6JJUCANdkgphoEtSIQx0SSqEgS5JhTDQJakQBrokFcJAl6RCGOiSVAgDXZIKYaBLUiH6eqZoRHwP+ClwHnjimTzE9Ip3fBaO7IWFOVg3DVv2+KR7jQa3zbHXV6B3/F5m/mgAnzP6js/C/TthsdWeXzjdngd3HFXLbVN4yqU7R/Yu7zBLFlvtdqlKbpui/0BP4MsRcTQidlyuQ0TsiIhGRDSazWafw1VsYa67dmlY3DZF/4F+c2beBLwBeEdE3HJph8w8kJn1zKxPTU31OVzF1k131y4Ni9um6DPQM/NMZ3oW+BzwykEUNbK27IGJ2sVtE7V2u1Qlt03RR6BHxDUR8VtLr4HfB04OqrCRtGk7bNsP664Doj3dtt+LTqqe26aAyMze3hhxA+2jcmjfLfNPmfm3T/eeer2ejUajp/EkaVxFxNFnclt4z7ctZuZ3gJf3+n5J0mB526IkFcJAl6RCGOiSVAgDXZIKYaBLUiEMdEkqhIEuSYUw0CWpEAa6JBXCQJekQhjoklQIA12SCmGgS1IhDHRJKoSBLkmFMNAlqRAGuiQVwkCXpEIY6JJUiL4DPSLWRMSxiPjiIArSFeT4LHzwRnjvZHt6fLbqiqSx1vNDoi9wF/Ao8OwBfJauFMdn4f6dsNhqzy+cbs8DbNpeXV3SGOvrCD0ipoE3AvcMphxdMY7sXQ7zJYutdrukSvR7yuVDwLuBXz1Vh4jYERGNiGg0m80+h9PIWJjrrl3Squs50CPiVuBsZh59un6ZeSAz65lZn5qa6nU4jZp10921S1p1/Ryh3wy8KSK+B3wGeF1EfGogVWn0bdkDE7WL2yZq7XZJleg50DNzd2ZOZ+ZG4A7gK5n51oFVptG2aTts2w/rrgOiPd223wuiUoUGcZeLxtWm7Qa4NEIGEuiZ+SDw4CA+S5LUG78pKkmFMNAlqRAGuiQVwkCXpEIY6JJUCANdkgphoEtSIQx0SSqEgS5JhTDQJakQBrokFcJAl6RCGOiSVAgDXZIKYaBLUiEMdEkqhIEuSYUw0CWpEAa6JBWi50CPiGdFxH9HxDci4pGI+JtBFvZrjs/CB2+E9062p8dnV3U4ST1yX61MPw+J/j/gdZn5s4iYAP4zIv4tM782oNqWHZ+F+3fCYqs9v3C6PQ8+dV4aJe6rler5CD3bftaZnej8y4FUdakje5c3kCWLrXa7pNHhvlqpvs6hR8SaiPg6cBZ4IDMfukyfHRHRiIhGs9nsbaCFue7aJVXDfbVSfQV6Zp7PzFcA08ArI+LGy/Q5kJn1zKxPTU31NtC66e7aJVXDfbVSA7nLJTPPAQ8CfzCIz/s1W/bARO3itolau13S6HBfrVQ/d7lMRcRk53UNeD3wrUEVdpFN22Hbflh3HRDt6bb9XmSRRo37aqUis7frmBGxCfgksIb2D4bZzHzaKx/1ej0bjUZP40nSuIqIo5lZX6lfz7ctZuZxYHOv75ckDZbfFJWkQhjoklQIA12SCmGgS1IhDHRJKoSBLkmF6Pk+9J4Gi2gC3x/agKvrWuBHVRcxIlwWy1wWy1wWy/pdFr+dmSv+7ZShBnpJIqLxTG70Hwcui2Uui2Uui2XDWhaecpGkQhjoklQIA713B6ouYIS4LJa5LJa5LJYNZVl4Dl2SCuERuiQVwkDvQkRcFxH/HhGPRsQjEXFX1TVVrfMYwmMR8cWqa6lSRExGxH0R8a3O9vHqqmuqSkS8q7N/nIyIeyPiWVXXNEwR8bGIOBsRJy9oe25EPBAR3+5Mn7MaYxvo3XkC+MvMfAnwKuAdEfHSimuq2l3Ao1UXMQI+DHwpM38HeDljukwiYgOwE6hn5o20n5dwR7VVDd0n+PWnt90NHMnMFwNHOvMDZ6B3ITMfz8yHO69/Snun3VBtVdWJiGngjcA9VddSpYh4NnAL8FGAzPxl57GM4+oqoBYRVwFrgTMV1zNUmflV4MeXNN9G+4FAdKa3r8bYBnqPImIj7Qd8PFRtJZX6EPBu4FdVF1KxG4Am8PHO6ad7IuKaqouqQmbOAx8AHgMeBxYy88vVVjUSXpCZj0P7wBB4/moMYqD3ICJ+E/gs8M7M/N+q66lCRNwKnM3Mo1XXMgKuAm4CPpKZm4Gfs0q/Uo+6zrnh24AXAeuBayLirdVWNT4M9C5FxATtMP90Zh6sup4K3Qy8KSK+B3wGeF1EfKrakiozB8xl5tJva/fRDvhx9Hrgu5nZzMxF4CDwmoprGgU/jIgXAnSmZ1djEAO9CxERtM+TPpqZf191PVXKzN2ZOZ2ZG2lf9PpKZo7lkVhm/gA4HREznaYtwDcrLKlKjwGvioi1nf1lC2N6gfgSXwDu7Ly+E/j8agzS80Oix9TNwJ8CJyLi6522v87Mf62wJo2GvwA+HRFXA98B3lZxPZXIzIci4j7gYdp3hR1jzL4xGhH3Aq8Fro2IOeA9wPuB2Yh4O+0fem9ZlbH9pqgklcFTLpJUCANdkgphoEtSIQx0SSqEgS5JhTDQJakQBrokFcJAl6RC/D+g0A2YMCIrQwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "qqq = pd.DataFrame(X)\n",
    "qqq['y']=y\n",
    "qqq[qqq['y']==-1][0]\n",
    "qqq[qqq['y']==-1][1]\n",
    "\n",
    "plt.scatter(qqq[qqq['y']==1][0],qqq[qqq['y']==1][1])\n",
    "plt.scatter(qqq[qqq['y']==-1][0],qqq[qqq['y']==-1][1])\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This formulation of the SVM is called the **hard margin SVM.** It cannot work when the data is not linearly separable. There are several Support Vector Machines formulations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**soft margin SVM** which will be able to work when data is non-linearly separable because of outliers. \n"
   ]
  },
  {
   "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}