Description

Part 1: Setup
• Remote connect to a EWS machine.
ssh (netid)@remlnx.ews.illinois.edu
• Load python module, this will also load pip and virtualenv.
module load python/3.4.3
• Reuse the virtual environment from previous MPs.
source ~/cs446sp_2018/bin/activate
• Copy mp5 into your svn directory, and change directory to mp5.
cd ~/(netid) svn cp https://subversion.ews.illinois.edu/svn/sp18-cs446/_shared/mp5 . cd mp5
• Install the requirements through pip.
pip install –upgrade pip pip install -r requirements.txt
• Create data directory, download the data into the data directory, and unzip the data.
mkdir data
wget –user (netid) –ask-password https://courses.engr.illinois.edu/cs446/sp2018/ secure/assignment5_data.zip -O data/assignment5_data.zip unzip data/assignment5_data.zip -d data/
• Prevent svn from checking in the data directory.
svn propset svn:ignore data .
1
Part 2: Exercises
In this exercise we will use SVM to recognize handwritten digits. The dataset we use is MNIST handwritten digit database, where every handwritten digit image is represented as 28 × 28 pixels, each with value 0 to 255. We want to classify each image as one of 0 to 9.

Figure 1: MNIST examples.
In the provided version of MNIST dataset, features are flattened into 784 = 28 × 28 dimensional vectors. To save running time, we only use the first 50%(5000) of the original MNIST test data as our training dataset, and the next 50%(5000) of the original test data as our test dataset.
In this exercise, we will first use Scikit Learn’s built-in multiclass classification functions to train one-vs-rest(one-vs-all) and one-vs-one multiclass linear SVM models. Then we will implement one-vs-rest and one-vs-one multiclass classifiers ourselves, using binary SVM models.
random state=12345
Throughout the exercise, we will use sklearn.svm.LinearSVC as our binary SVM classifier, with default parameters unless specifically mentioned, andfor reproductivity. If you are not familiar with Scikit Learn, please make sure you understand how to use fit and predict methods in the above link.
Part 2.1 Using Built-in Multiclass Functions
In this exercise, we will use Scikit Learn’s sklearn.multiclass.OneVsRestClassifier and sklearn.multiclass.OneVsOneClassifier to perform multiclass classification. We will also use Crammer-Singer multiclass SVM (the multiclass SVM formulation in the lecture), which is supported in sklearn.svm.LinearSVC .
Task 1:
sklearn multiclass prediction
Implementin model/sklearn multiclass.py , which takes training and test features and labels, as well as a string mode being one of “ovr”, “ovo”, or “crammer”. The function should pick the correct classifier to train and predict labels for both training and test data.
Thinking Questions: How would you compare OVR, OVO and Crammer-Singer, in terms of classification accuracy and time efficiency?
Part 2.2 Implementing One-vs-Rest and One-vs-One Classification
In this exercise, we will use sklearn.svm.LinearSVC only with binary labels, 0 and 1.
(You can use any other two labels, but 0 and 1 are recommended.) We will implement class MulticlassSVM in model/self multiclass.py , which is constructed given mode being one of “ovr” and “ovo”. When fit and predict methods are called, it will call the correct version of multiclass classification given mode .
Task 2:
bsvm ovr student
Implementbsvm ovo student in model/self multiclass.py , which takes training data X and y , and returns a python dict with keys being labels for OVR, and pairs of labels for OVO, and with values being trained OVR or OVO binary sklearn.svm.LinearSVC classifiers.
Task 3:
Implement scores ovr student scores ovo student in model/self multiclass.py , which takes features X , and returns a numpy ndarray Score with shape (#Samples,#Labels), where Score(i,j) is the number of votes of the j-th label received for the i-th sample in OVO, and is the confidence score of the j-th label for the i-th sample in OVR (use decision function as confidence score).
Thinking Questions: Why do we need use confidence scores for OVR? Why do we not use confidence scores for OVO?
After the scoring functions are implemented, predict ovr and predict ovo will return the labels with maximum votes.
Part 2.3 Implementing Multiclass SVM
In this part, we will implement our own loss function of (Crammer-Singer) multiclass linear SVM as:

where δj,yi = 1 if j = yi and 0 if j 6= yi, and optimize it via gradient descent. Your task is to compute the loss function and the gradients of the loss function w.r.t. W = [w1,…,wK]>∈ RK×d, given W, X = [x1,…,xN]>∈RN×d, Y = [y1,…,yN] ∈{0,…,9}N and C = 1.
Task 4:
loss student
Implementgrad student in model/self multiclass.py , which takes
W , X and y , and returns the loss function and its gradient w.r.t. W respectively.
Hint:
1. Think some concrete cases, for example the one in the written assignment.
2. Though not required, try using matrix operations of Numpy when possible for faster performance. Some useful functions: np.sum , np.max , np.argmax .
Part 2.4 Comparing Built-in and Self-Implemented Functions
Part 3: Writing Tests
In test.py we have provided basic test-cases. Feel free to write more. To test the code, run
nose2
Part 4: Submit
Submitting the code is equivalent to committing the code. This can be done with the follow command:
svn commit -m “Some meaningful comment here.”
Lastly, double check on your browser that you can see your code at
https://subversion.ews.illinois.edu/svn/sp18-cs446/(netid)/mp5/
Note: The assignment will be autograded. It is important that you do not use additional libraries, or change the provided functions input and output.