{ "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 }