Lab 8: Support Vector Machines

From 6.034 Wiki

(Difference between revisions)
Jump to: navigation, search
m
Line 1: Line 1:
__TOC__
__TOC__
-
This lab is due by [todo] at 10:00pm.   
+
This lab is due by Friday, November 4 at 10:00pm.   
-
To work on this lab, you will need to get the code:
+
To work on this lab, you will need to get the code, much like you did for the previous labs.  You can:
-
[todo]
+
* Use Git on your computer: <tt>git clone username@athena.dialup.mit.edu:/mit/6.034/www/labs/lab7</tt>
 +
* Use Git on Athena: <tt>git clone /mit/6.034/www/labs/lab7</tt>
 +
* Download it as a ZIP file: http://web.mit.edu/6.034/www/labs/lab7/lab7.zip
 +
* View the files individually: http://web.mit.edu/6.034/www/labs/lab7/
-
<!--The online tester is now available! Online tests will be made available by the end of Tuesday, November 10.  In the meantime, the local tester provides thorough unit tests for each section of the lab.-->
+
<!--'''Online tests will be made available by the end of [todo].''' In the meantime, the local tester provides thorough unit tests for each section of the lab.--> <!--The online tester is now available!  '''If you downloaded the lab files on or before Sunday, October 23, you may need to <tt>git pull</tt> or download a new [http://web.mit.edu/6.034/www/labs/lab6/tester.py <tt>tester.py</tt>]''' in order to pass the online tests.-->
Your answers for this lab belong in the main file <tt>lab7.py</tt>.  
Your answers for this lab belong in the main file <tt>lab7.py</tt>.  
 +
= Problems =
= Problems =
Line 83: Line 87:
-
=== Extra Credit Project: Train a support vector machine ===
+
=== 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.  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.  The following resources 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

Revision as of 22:26, 25 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

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.


Support Vector Machines

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:

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. The following resources may be helpful:


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

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, DecisionBoundary, 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.


DecisionBoundary

A DecisionBoundary is defined by two parameters: a normal vector w, and an offset b. w is represented as a vector: a list or tuple of coordinates. You can access these parameters using the attributes .w and .b.


SupportVectorMachine

A SupportVectorMachine is a classifier that uses a DecisionBoundary to classify points. It has a list of training points and optionally a list of support vectors. You can access these parameters using these attributes:

  • svm.boundary, the SVM's DecisionBoundary.
  • 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 lists or tuples of coordinates, returns their sum as a list of coordinates.

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

Personal tools