{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Support Vector Machine (SVM)\n",
    "We are given two sets of points in ${\\bf R}^n$, $\\{x_1, \\ldots, x_N\\}$ and $\\{y_1, \\ldots, y_M\\}$, and wish to find a function $f(x) = w^T x - b$ that linearly separates the points, i.e. $f(x_i) \\geq 1$ for $i = 1, \\ldots, N$ and $f(y_i) \\leq -1$ for $i = 1, \\ldots, M$. That is, the points are separated by two hyperplanes, $w^T x - b = 1$ and $w^T x - b = -1$.\n",
    "\n",
    "Perfect linear separation is not always possible, so we seek to minimize the amount that these inequalities are violated. The violation of point $x_i$ is $\\text{max} \\{1 + b - w^T x_i, 0\\}$, and the violation of point $y_i$ is $\\text{max} \\{1 - b + w^T y_i, 0\\}$. We tradeoff the error $\\sum_{i=1}^N \\text{max} \\{1 + b - w^T x_i, 0\\} + \\sum_{i=1}^M \\text{max} \\{1 - b + w^T y_i, 0\\}$ with the distance between the two hyperplanes, which we want to be large, via minimizing $\\|w\\|^2$.\n",
    "\n",
    "We can write this problem as\n",
    "\\begin{array}{ll}\n",
    "    \\mbox{minimize}   & \\|w\\|^2 + C * (\\sum_{i=1}^N \\text{max} \\{1 + b - w^T x_i, 0\\} + \\sum_{i=1}^M \\text{max} \\{1 - b + w^T y_i, 0\\}) \\\\\n",
    "\\end{array},\n",
    "where $w \\in {\\bf R}^n$ and $b \\in {\\bf R}$ are our optimization variables.\n",
    "\n",
    "We can solve the problem as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "using Convex\n",
    "using SCS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "## Generate data.\n",
    "n = 2; # dimensionality of data\n",
    "C = 10; # inverse regularization parameter in the objective\n",
    "N = 10; # number of positive examples\n",
    "M = 10; # number of negative examples\n",
    "\n",
    "using Distributions\n",
    "# positive data points\n",
    "pos = rand(MvNormal([1.0, 2.0], 1.0), N);\n",
    "# negative data points\n",
    "neg = rand(MvNormal([-1.0, 2.0], 1.0), M);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "function svm(pos, neg, solver=SCSSolver(verbose=0))\n",
    "    # Create variables for the separating hyperplane w'*x = b.\n",
    "    w = Variable(n)\n",
    "    b = Variable()\n",
    "    # Form the objective.\n",
    "    obj = sumsquares(w) + C*sum(max(1+b-w'*pos, 0)) + C*sum(max(1-b+w'*neg, 0))\n",
    "    # Form and solve problem.\n",
    "    problem = minimize(obj)\n",
    "    solve!(problem, solver)\n",
    "    return evaluate(w), evaluate(b)\n",
    "end;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "w, b = svm(pos, neg);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "## Plot our results.\n",
    "using Gadfly\n",
    "# Generate the separating hyperplane\n",
    "line_x = -2:0.1:2;\n",
    "line_y = (-w[1] * line_x + b)/w[2];\n",
    "# Plot the positive points, negative points, and separating hyperplane.\n",
    "plot(Scale.y_continuous(minvalue=-1, maxvalue=4),\n",
    "    layer(x=pos[1,:], y=pos[2,:], Geom.point,\n",
    "        Theme(default_color=color(\"green\"))),\n",
    "    layer(x=neg[1,:], y=neg[2,:], Geom.point,\n",
    "        Theme(default_color=color(\"red\"))),\n",
    "    layer(x=line_x, y=line_y, Geom.line,\n",
    "        Theme(default_color=color(\"blue\"))))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.3.1",
   "language": "julia",
   "name": "julia 0.3"
  },
  "language_info": {
   "name": "julia",
   "version": "0.3.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}