SVM/SVM-Theory.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Support Vector Machines"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## An optimization problem:\n",
    "Let a hyperplane be given by $W^{T}x + b$   \n",
    "Then the distance from the origin is given by: $\\frac{b}{||W||}$   \n",
    "And the distance of any general point ($\\textbf{x}$) is given by: $\\frac{|W^{T}x + b|}{||W||}$\n",
    "  \n",
    "Let y be the vector specifying the classes.   \n",
    "Let $y = 1, -1$ denote the two classes (Let's assume binary classification for now) \n",
    "  \n",
    "Then, for a perfect classifier, we need to have:\n",
    "$$y\\cdot(W^{T}x_{i} + b) \\geq 0 \\ \\  \\forall \\ \\ i \\in (1,\\dots,m)$$\n",
    "This is the 'constraint' for our optimization problem.\n",
    "  \n",
    "For getting an even better classifier, we also need to have the decision boundary located at a maximum distance from the data points. This distance is called the geometric margin. We also need to maximize this.\n",
    "  \n",
    "$$\\text{max}\\{ \\min_{i = 1\\dots m} \\frac{|W^{T}x_i + b|}{||W||} \\}$$\n",
    "\n",
    "Thus, this is the 'objective' of our optimization problem.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A few assumptions:\n",
    "As we have effectively chosen the class values to be $1, -1$, we have the following equality:   \n",
    "  \n",
    "$$\\frac{|W^{T}x_i + b|}{||W||} = \\frac{|y_i\\cdot (W^{T}x_i + b|)}{||W||}$$\n",
    "  \n",
    "Now, let's assume a perfect classifier that classifies all the data points.  \n",
    "As a direct consequence of the constraint condition, we have   \n",
    "   \n",
    "$$|y_i\\cdot (W^{T}x_i + b| = y_i\\cdot (W^{T}x_i + b)$$\n",
    "   \n",
    "Thus, the optimization condition now becomes   \n",
    "  \n",
    "$$\\text{max}\\{ \\min_{i = 1\\dots m} \\frac{y_i\\cdot (W^{T}x_i + b)}{||W||} \\}$$\n",
    "  \n",
    "Let the mininum distance be achieved at $i = i_0$, thus, the optimization condition now becomes:  \n",
    "  \n",
    "$$\\text{max}\\{ \\frac{y_{i_0}\\cdot (W^{T}x_{i_0} + b)}{||W||} \\}$$\n",
    "  \n",
    "The 'functional margin' is defined by:  $\\text{geometric margin}\\cdot ||W|| = y_{i_0}\\cdot (W^{T}x_{i_0} + b)$  \n",
    "  \n",
    "Let   \n",
    "$$\\epsilon := y_{i_0}\\cdot (W^{T}x_{i_0} + b)$$  \n",
    "$$\\tilde W := \\frac{W}{\\epsilon}$$  \n",
    "$$\\tilde b := \\frac{b}{\\epsilon}$$\n",
    "  \n",
    "Thus, we have that $y_i\\cdot (W^{T}x_i + b) \\gt y_{i_0}\\cdot (W^{T}x_{i_0} + b)$.  \n",
    "  \n",
    "Therefore, $y_i\\cdot (\\tilde{W}^{T}x_i + \\tilde{b}) \\geq 1$   \n",
    "  \n",
    "Which in turn implies that $\\frac{y_i\\cdot (\\tilde{W}^{T}x_i + \\tilde{b})}{||\\tilde W||} \\geq \\frac{1}{||\\tilde W||}$ \n",
    "  \n",
    "Thus the new simpler optimization condition and the constraint is: \n",
    "$$\\max{\\frac{1}{||\\tilde W||}} = \\min{||\\tilde W|| = \\min{ ||\\tilde W||^2}}$$\n",
    "  \n",
    "$$ y_i\\cdot (\\tilde{W}^{T}x_i + \\tilde{b}) \\geq 1 $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The C-SVM classifier:\n",
    "  \n",
    "For linearly separable cases where we assume a perfect classifier to exist, we have:\n",
    "$$\\frac{1}{2}\\min{ ||\\tilde W||^2} \\ \\  \\text{s.t} \\ \\  y_i\\cdot (\\tilde{W}^{T}x_i + \\tilde{b}) \\geq 1 $$\n",
    "   \n",
    "If a linear classifier cannot perfectly classify the points, we find a model using:  \n",
    "$$\\frac{1}{2}\\min{ ||\\tilde W||^2} + C\\sum_{i=1}^{m} L_{hinge}(\\tilde W^{T}x_i + \\tilde b, y_i)$$\n",
    "  \n",
    "Where $L_{hinge}(z, y)$ is the the hinge cost function.   \n",
    "  \n",
    "This is very similar to the logistic regression classifier, except that here, $C$ acts as $\\frac{1}{\\lambda}$, where $\\lambda$ is the regularization parameter. \n",
    "\n",
    "Thus the final cost function needed to be minimized is:\n",
    "$$\\frac{1}{2}||\\tilde W||^2 + C\\sum_{i=1}^{m} L_{hinge}(\\tilde W^{T}x_i + \\tilde b, y_i)$$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}