Lab 8: Support Vector Machines

From 6.034 Wiki

(Difference between revisions)
Jump to: navigation, search
(Support Vector Machines: eliminate DecisionBoundary class)
(Train a support vector machine)
Line 91: Line 91:
[todo]
[todo]
-
In class and in this lab, we have seen how to calculate the final parameters of an SVM (given the decision boundary), and we've used the equations to assess how well an SVM has been trained, but we haven't actually attempted to train an SVM.  In practice, training an SVM is a hill-climbing problem in alpha-space using the Lagrangian.  There's a bit of math involved.  The following resources may be helpful:
+
In class and in this lab, we have seen how to calculate the final parameters of an SVM (given the decision boundary), and we've used the equations to assess how well an SVM has been trained, but we haven't actually attempted to train an SVM.  In practice, training an SVM is a hill-climbing problem in alpha-space using the Lagrangian.  There's a bit of math involved, typically computed using Sequential Minimal Optimization.   
 +
 
 +
If you want to learn more about training SVMs, the following resources (mostly beyond the scope of 6.034) may be helpful:
* [http://cs.nyu.edu/~dsontag/courses/ml12/slides/lecture5.pdf SVM lecture notes] from a machine-learning class at NYU
* [http://cs.nyu.edu/~dsontag/courses/ml12/slides/lecture5.pdf SVM lecture notes] from a machine-learning class at NYU
* [http://www-ai.cs.uni-dortmund.de/LEHRE/SEMINARE/SS09/AKTARBEITENDESDM/LITERATUR/PlattSMO.pdf paper on Sequential Minimal Optimization]
* [http://www-ai.cs.uni-dortmund.de/LEHRE/SEMINARE/SS09/AKTARBEITENDESDM/LITERATUR/PlattSMO.pdf paper on Sequential Minimal Optimization]
Line 97: Line 99:
* [http://courses.csail.mit.edu/6.034f/ai3/SVM.pdf SVM slides], from the [[Reference material and playlist]]
* [http://courses.csail.mit.edu/6.034f/ai3/SVM.pdf SVM slides], from the [[Reference material and playlist]]
* Wikipedia articles on [https://en.wikipedia.org/wiki/Support_vector_machine#Linear_SVM SMV math] and [https://en.wikipedia.org/wiki/Sequential_minimal_optimization Sequential Minimal Optimization]
* Wikipedia articles on [https://en.wikipedia.org/wiki/Support_vector_machine#Linear_SVM SMV math] and [https://en.wikipedia.org/wiki/Sequential_minimal_optimization Sequential Minimal Optimization]
-
 
-
 
-
For some unspecified amount of extra credit, extend your code and/or the API to train a support vector machine.  Possible extensions include implementing kernel functions or writing code to graphically display your training data and SVM boundary.  If you can come up with a reasonably simple procedure for training an SVM, preferably using only built-in Python packages, we may even use your code in a future 6.034 lab!  (With your permission, of course.)
 
-
 
-
To receive your extra credit, send your code to 6.034-2015-support@mit.edu '''by December 4, 2015''', ideally with some sort of documentation.  (Briefly explain what you did and how you did it.)
 
== Survey ==
== Survey ==

Revision as of 19:22, 28 October 2016

Contents


This lab is due by Friday, November 4 at 10:00pm.

To work on this lab, you will need to get the code, much like you did for the previous labs. You can:


Your answers for this lab belong in the main file lab7.py.


Problems: Support Vector Machines

This lab is divided into two independent parts. In the first part, you'll code subroutines necessary for training and using neural networks. In the second part, you'll code subroutines for using and validating support vector machines.


SVM Equations and Properties

Vector Math

We'll start with some basic functions for manipulating vectors. For now, we will represent an n-dimensional vector as a list or tuple of n coordinates. dot_product should compute the dot product of two vectors, while norm computes the length of a vector. (There is a simple implementation of norm that uses dot_product.) Implement both functions.

(If these look familiar, it's probably because you saw them on Lab 5. Feel free to copy your implementations from your lab5.py.)

def dot_product(u, v):
def norm(v):


Later, when you need to actually manipulate vectors, note that we have also provided methods for adding two vectors (vector_add) and for multiplying a scalar by a vector (scalar_mult). (See the API, below.)

SVM Equations (reference only)

Next, we will use the following five SVM equations. Recall from recitation that Equations 1-3 define the decision boundary and the margin width, while Equations 4 & 5 can be used to calculate the alpha (supportiveness) values for the training points.


Image:Lab6 Eqns.png


For more information about how to apply these equations, see:

Using the SVM Boundary Equations

We will start by using Equation 1 to classify a point with a given SVM, ignoring the point's actual classification (if any). According to Equation 1, a point's classification is +1 when w·x + b > 0, or -1 when w·x + b < 0. If w·x + b = 0, the point lies on the decision boundary, so its classification is ambiguous.

First, evaluate the expression w·x + b to calculate how positive a point is. svm is a SupportVectorMachine object, and point is a Point (see the API below for details).

def positiveness(svm, point):


Next, classify a point as +1 or -1. If the point lies on the boundary, return 0.

def classify(svm, point):


Then, use the SVM's current decision boundary to calculate its margin width (Equation 2):

def margin_width(svm):


Finally, we will check that the gutter constraint is satisfied. The gutter constraint requires that positiveness be +1 for positive support vectors, and -1 for negative support vectors. Our function will also check that no training points lie between the gutters -- that is, every training point should have a positiveness value indicating that it either lies on a gutter or outside the margin. (Note that the gutter constraint does not check whether points are classified correctly.) Implement check_gutter_constraint, which should return a set (not a list) of the training points that violate one or both conditions:

def check_gutter_constraint(svm):

Using the Supportiveness Equations

To train a support vector machine, every training point is assigned a supportiveness value (also known as an alpha value, or a Lagrange multiplier), representing how important the point is in determining (or "supporting") the decision boundary. The supportiveness values must satisfy a number of conditions, which we will check below.

First, implement check_alpha_signs to check each point's supportiveness value. Each training point should have a non-negative supportiveness. Specifically, all support vectors should have positive supportiveness, while all non-support vectors should have a supportiveness of 0. This function, like check_gutter_constraint above, should return a set of the training points that violate either of the supportiveness conditions.

def check_alpha_signs(svm):


Implement check_alpha_equations to check that the SVM's supportiveness values are consistent with its boundary equation and the classifications of its training points. Return True if both Equations 4 and 5 are satisfied, otherwise False.

def check_alpha_equations(svm):

Classification Accuracy

Once a support vector machine has been trained -- or even while it is being trained -- we want to know how well it has classified the training data. Write a function that checks whether the training points were classified correctly and returns a set containing the training points that were misclassified, if any.

def misclassified_training_points(svm):


Train a support vector machine

[todo]

In class and in this lab, we have seen how to calculate the final parameters of an SVM (given the decision boundary), and we've used the equations to assess how well an SVM has been trained, but we haven't actually attempted to train an SVM. In practice, training an SVM is a hill-climbing problem in alpha-space using the Lagrangian. There's a bit of math involved, typically computed using Sequential Minimal Optimization.

If you want to learn more about training SVMs, the following resources (mostly beyond the scope of 6.034) may be helpful:

Survey

Please answer these questions at the bottom of your lab7.py file:

  • NAME: What is your name? (string)
  • COLLABORATORS: Other than 6.034 staff, whom did you work with on this lab? (string, or empty string if you worked alone)
  • HOW_MANY_HOURS_THIS_LAB_TOOK: Approximately how many hours did you spend on this lab? (number or string)
  • WHAT_I_FOUND_INTERESTING: Which parts of this lab, if any, did you find interesting? (string)
  • WHAT_I_FOUND_BORING: Which parts of this lab, if any, did you find boring or tedious? (string)
  • (optional) SUGGESTIONS: What specific changes would you recommend, if any, to improve this lab for future years? (string)


(We'd ask which parts you find confusing, but if you're confused you should really ask a TA.)

When you're done, run the online tester to submit your code.

API

Support Vector Machines

The file svm_api.py defines the Point and SupportVectorMachine classes, as well as some helper functions for vector math, all described below.

Point

A Point has the following attributes:

  • point.name, the name of the point (a string).
  • point.coords, the coordinates of the point, represented as a vector (a tuple or list of numbers).
  • point.classification, the classification of the point, if known. Note that classification (if any) is a number, typically +1 or -1.
  • point.alpha, the supportiveness (alpha) value of the point, if assigned.

The Point class supports iteration (to iterate through the coordinates).

SupportVectorMachine

A SupportVectorMachine is a classifier that uses a decision boundary to classify points. The decision boundary is defined by a normal vector w (a vector, represented as a list or tuple of coordinates), and an offset b (a number). The SVM also has a list of training points and optionally a list of support vectors. You can access its parameters using these attributes:

  • svm.w, the normal vector w.
  • svm.b, the offset b.
  • svm.training_points, a list of Point objects with known classifications.
  • svm.support_vectors, a list of Point objects that serve as support vectors for the SVM. Every support vector is also a training point.

Helper functions for vector math

vector_add: Given two vectors represented as iterable vectors (lists or tuples of coordinates) or Points, returns their vector sum as a list of coordinates.

scalar_mult: Given a constant scalar and an iterable vector (as a tuple or list of coordinates) or a Point, returns a scaled list of coordinates.

Personal tools