CS 491/691 Project 5 Binary Classification solution


Original Work ?


5/5 - (4 votes)

1 Binary Classification (50 points)
File name: binary classification.py
You will implement a linear classifier with a decision boundary that maximizes the margin between
positive and negative samples (SVM). The details of SVM can be quite complex, and so here you will
implement a simpler version of it for 2D data.
We provide you with a function for generating data (features and labels):
data = generate_training_data_binary(num)
num indicates the training set. There are four different datasets (num=1, num=2, num=3, num=4) which
you will need to train on and provide results for. All the datasets are linearly separable. data is a numpy
array containing 2D features and their corresponding label in each row. So data[0] will have the form
[x1, x2, y] where [x1, x2] is the feature for the first training sample and it has the label y. y can be -1
or 1.
We have also provided you with a function to plot the training data so you can visualize it:
Implement: You must write the following function:
[w,b,S] = svm_train_brute(training_data)
This function will return the decision boundary for your classifier and a numpy array of support vectors
S. That is, it will return the line characterized by w and b that separates the training data with the largest
margin between the positive and negative class.
Since the decision boundary is a line in the case of separable 2D data, you can find the best decision
boundary (the one with the maximum margin between positive and negative samples) by looking at lines
that separate the data and choosing the best one (the one with the maximum margin). The maximum
margin separator depends only on the support vectors. So you can find the maximum margin separator via
a brute force search over possible support vectors. In 2D there can only be either 2 or 3 support vectors.
In order to implement your training function, you will need to write some helper functions:
Implement: Write a function that compute the distance between a point and a hyperplane. In 2D, the
hyperplane is a line, defined by w and b. Your code must work for hyperplanes in 2D. Do not worry about
higher dimensions.
dist = distance_point_to_hyperplane(pt, w, b)
Implement: Write a function that takes a set of data, and a separator, and computes the margin.
margin = compute_margin(data, w, b)
Implement: You will need to write the following function to test new data given a decision boundary.
The following function will output the class y for a given test point x.
y = svm_test_brute(w,b,x)
Use the above helper functions when writing your training function.
Write-Up: Give the details of your method in your report. Plot the training data and your decision
boundary for each of the four datasets provided by the generate_training_data_binary function. Also
provide the margins for each of the separators in your report.
2 Multi-Class Classification (50 points)
File name: multiclass classification.py Now, let’s assume we’re working with data that comes from
more than two classes. You can still use an SVM to classify data into one of the Y classes by using multiple
SVMs in a one-vs-all fashion. Instead of thinking about it as class 1 versus class 2 versus class 3… you think
of it as class 1 versus not class 1, and class 2 versus not class 2. So you would have one binary classifier for
each class to distinguish that class from the rest.
We will provide you with a function to generate training data:
[data, Y] = generate_training_data_multi(num)
Similarly to the binary data generation function, num indicates the particular set of data, and there are
2. Each dataset has a different number of classes. The classes are identified from 1 to Y, where Y is the
number of classes.
We have also provided you with a function to plot the training data so you can visualize it:
Implement: Implement the following function:
[W, B] = svm_train_multiclass(training_data)
This function should use your previously implemented svm_train_brute to train one binary classifier
for each class. It will return the Y decision boundaries, one for each class (one-vs-rest). W is an array of ws
and B is an array of bs where wix + bi
is the decision boundary for the i
th class.
Implement: You will also implement a test function:
y = svm_test_multiclass(W,B,x)
This function will take the C decision boundaries as input and a test point x, and will return the predicted
class, c. There are two special cases you will need to account for. You may find that a test point is in the
“rest” for all of your one-vs-rest classifiers, and so it belongs to no class. You can just return -1 (null) when
this happens. You may also find that a test point belongs to two classes. In this case you may choose the
class for which the test point is the farthest from the decision boundary.
Write-Up: Plot the training data, and the decision boundaries for each one-vs-rest problem on all
multi-class datasets.