# Multiclass Support Vector Machine exercise

Complete and hand in this completed worksheet (including its outputs and any supporting code outside of the worksheet) with your assignment submission. For more details see the assignments page on the course website.

In this exercise you will:

• implement a fully-vectorized loss function for the SVM
• implement the fully-vectorized expression for its analytic gradient
• use a validation set to tune the learning rate and regularization strength
• optimize the loss function with SGD
• visualize the final learned weights
``````

In [1]:

# Run some setup code for this notebook.

import random
import numpy as np
import matplotlib.pyplot as plt

# This is a bit of magic to make matplotlib figures appear inline in the
# notebook rather than in a new window.
%matplotlib inline
plt.rcParams['figure.figsize'] = (10.0, 8.0) # set default size of plots
plt.rcParams['image.interpolation'] = 'nearest'
plt.rcParams['image.cmap'] = 'gray'

# Some more magic so that the notebook will reload external python modules;

``````

``````

In [2]:

# Load the raw CIFAR-10 data.
cifar10_dir = 'cs231n/datasets/cifar-10-batches-py'
X_train, y_train, X_test, y_test = load_CIFAR10(cifar10_dir)

# As a sanity check, we print out the size of the training and test data.
print 'Training data shape: ', X_train.shape
print 'Training labels shape: ', y_train.shape
print 'Test data shape: ', X_test.shape
print 'Test labels shape: ', y_test.shape

``````
``````

Training data shape:  (50000, 32, 32, 3)
Training labels shape:  (50000,)
Test data shape:  (10000, 32, 32, 3)
Test labels shape:  (10000,)

``````
``````

In [3]:

# Visualize some examples from the dataset.
# We show a few examples of training images from each class.
classes = ['plane', 'car', 'bird', 'cat', 'deer', 'dog', 'frog', 'horse', 'ship', 'truck']
num_classes = len(classes)
samples_per_class = 7
for y, cls in enumerate(classes):
idxs = np.flatnonzero(y_train == y)
idxs = np.random.choice(idxs, samples_per_class, replace=False)
for i, idx in enumerate(idxs):
plt_idx = i * num_classes + y + 1
plt.subplot(samples_per_class, num_classes, plt_idx)
plt.imshow(X_train[idx].astype('uint8'))
plt.axis('off')
if i == 0:
plt.title(cls)
plt.show()

``````
``````

``````
``````

In [4]:

# Subsample the data for more efficient code execution in this exercise.
num_training = 49000
num_validation = 1000
num_test = 1000

# Our validation set will be num_validation points from the original
# training set.
mask = range(num_training, num_training + num_validation)

# Our training set will be the first num_train points from the original
# training set.

# We use the first num_test points of the original test set as our
# test set.

print 'Train data shape: ', X_train.shape
print 'Train labels shape: ', y_train.shape
print 'Validation data shape: ', X_val.shape
print 'Validation labels shape: ', y_val.shape
print 'Test data shape: ', X_test.shape
print 'Test labels shape: ', y_test.shape

``````
``````

Train data shape:  (49000, 32, 32, 3)
Train labels shape:  (49000,)
Validation data shape:  (1000, 32, 32, 3)
Validation labels shape:  (1000,)
Test data shape:  (1000, 32, 32, 3)
Test labels shape:  (1000,)

``````
``````

In [5]:

# Preprocessing: reshape the image data into rows
X_train = np.reshape(X_train, (X_train.shape[0], -1))
X_val = np.reshape(X_val, (X_val.shape[0], -1))
X_test = np.reshape(X_test, (X_test.shape[0], -1))

# As a sanity check, print out the shapes of the data
print 'Training data shape: ', X_train.shape
print 'Validation data shape: ', X_val.shape
print 'Test data shape: ', X_test.shape

``````
``````

Training data shape:  (49000, 3072)
Validation data shape:  (1000, 3072)
Test data shape:  (1000, 3072)

``````
``````

In [6]:

# Preprocessing: subtract the mean image
# first: compute the image mean based on the training data
mean_image = np.mean(X_train, axis=0)
print mean_image[:10] # print a few of the elements
plt.figure(figsize=(4,4))
plt.imshow(mean_image.reshape((32,32,3)).astype('uint8')) # visualize the mean image

``````
``````

[ 130.64189796  135.98173469  132.47391837  130.05569388  135.34804082
131.75402041  130.96055102  136.14328571  132.47636735  131.48467347]

Out[6]:

<matplotlib.image.AxesImage at 0x11600fb90>

``````
``````

In [7]:

# second: subtract the mean image from train and test data
X_train -= mean_image
X_val -= mean_image
X_test -= mean_image

``````
``````

In [8]:

# third: append the bias dimension of ones (i.e. bias trick) so that our SVM
# only has to worry about optimizing a single weight matrix W.
# Also, lets transform both data matrices so that each image is a column.
X_train = np.hstack([X_train, np.ones((X_train.shape[0], 1))]).T
X_val = np.hstack([X_val, np.ones((X_val.shape[0], 1))]).T
X_test = np.hstack([X_test, np.ones((X_test.shape[0], 1))]).T

print X_train.shape, X_val.shape, X_test.shape

``````
``````

(3073, 49000) (3073, 1000) (3073, 1000)

``````

## SVM Classifier

Your code for this section will all be written inside cs231n/classifiers/linear_svm.py.

As you can see, we have prefilled the function `compute_loss_naive` which uses for loops to evaluate the multiclass SVM loss function.

``````

In [10]:

# Evaluate the naive implementation of the loss we provided for you:
from cs231n.classifiers.linear_svm import svm_loss_naive
import time

# generate a random SVM weight matrix of small numbers
W = np.random.randn(10, 3073) * 0.0001
loss, grad = svm_loss_naive(W, X_train, y_train, 0.00001)
print 'loss: %f' % (loss, )

``````

The `grad` returned from the function above is right now all zero. Derive and implement the gradient for the SVM cost function and implement it inline inside the function `svm_loss_naive`. You will find it helpful to interleave your new code inside the existing function.

To check that you have correctly implemented the gradient correctly, you can numerically estimate the gradient of the loss function and compare the numeric estimate to the gradient that you computed. We have provided code that does this for you:

``````

In [11]:

# Once you've implemented the gradient, recompute it with the code below
# and gradient check it with the function we provided for you

# Compute the loss and its gradient at W.
loss, grad = svm_loss_naive(W, X_train, y_train, 0.0)

# Numerically compute the gradient along several randomly chosen dimensions, and
# compare them with your analytically computed gradient. The numbers should match
# almost exactly along all dimensions.
f = lambda w: svm_loss_naive(w, X_train, y_train, 0.0)[0]

``````
``````

numerical: 5.967266 analytic: 5.965758, relative error: 0.000
numerical: -7.590548 analytic: -7.590233, relative error: 0.000
numerical: -27.647294 analytic: -27.648367, relative error: 0.000
numerical: 3.770782 analytic: 3.769005, relative error: 0.000
numerical: 15.991002 analytic: 15.991757, relative error: 0.000
numerical: -12.304308 analytic: -12.303347, relative error: 0.000
numerical: 4.761992 analytic: 4.762052, relative error: 0.000
numerical: 2.222510 analytic: 2.227860, relative error: 0.001
numerical: -12.876409 analytic: -12.876550, relative error: 0.000
numerical: 31.562372 analytic: 31.561316, relative error: 0.000

``````

### Inline Question 1:

It is possible that once in a while a dimension in the gradcheck will not match exactly. What could such a discrepancy be caused by? Is it a reason for concern? What is a simple example in one dimension where a gradient check could fail? Hint: the SVM loss function is not strictly speaking differentiable

• Coner case at the point x = 0.0
``````

In [18]:

# Next implement the function svm_loss_vectorized; for now only compute the loss;
# we will implement the gradient in a moment.
tic = time.time()
loss_naive, grad_naive = svm_loss_naive(W, X_train, y_train, 0.00001)
toc = time.time()
print 'Naive loss: %e computed in %fs' % (loss_naive, toc - tic)

from cs231n.classifiers.linear_svm import svm_loss_vectorized
tic = time.time()
loss_vectorized, _ = svm_loss_vectorized(W, X_train, y_train, 0.00001)
toc = time.time()
print 'Vectorized loss: %e computed in %fs' % (loss_vectorized, toc - tic)

# The losses should match but your vectorized implementation should be much faster.
print 'difference: %f' % (loss_naive - loss_vectorized)

``````
``````

Naive loss: 8.865619e+00 computed in 4.059970s
Vectorized loss: 8.865619e+00 computed in 0.180561s
difference: 0.000000

``````
``````

In [12]:

from cs231n.classifiers.linear_svm import svm_loss_vectorized
loss_vectorized, _ = svm_loss_vectorized(W, X_train, y_train, 0.00001)

``````
``````

In [61]:

# Complete the implementation of svm_loss_vectorized, and compute the gradient
# of the loss function in a vectorized way.

# The naive implementation and the vectorized implementation should match, but
# the vectorized version should still be much faster.
tic = time.time()
_, grad_naive = svm_loss_naive(W, X_train, y_train, 0.00001)
toc = time.time()
print 'Naive loss and gradient: computed in %fs' % (toc - tic)

tic = time.time()
_, grad_vectorized = svm_loss_vectorized(W, X_train, y_train, 0.00001)
toc = time.time()
print 'Vectorized loss and gradient: computed in %fs' % (toc - tic)

# The loss is a single number, so it is easy to compare the values computed
# by the two implementations. The gradient on the other hand is a matrix, so
# we use the Frobenius norm to compare them.
print 'difference: %f' % difference

``````
``````

Naive loss and gradient: computed in 4.098631s
Vectorized loss and gradient: computed in 0.591005s
difference: 0.000000

``````

We now have vectorized and efficient expressions for the loss, the gradient and our gradient matches the numerical gradient. We are therefore ready to do SGD to minimize the loss.

``````

In [13]:

# Now implement SGD in LinearSVM.train() function and run it with the code below
from cs231n.classifiers import LinearSVM
svm = LinearSVM()
tic = time.time()
loss_hist = svm.train(X_train, y_train, learning_rate=1e-7, reg=5e4,
num_iters=1500, verbose=True)
toc = time.time()
print 'That took %fs' % (toc - tic)

``````
``````

iteration 0 / 1500: loss 789.295527
iteration 100 / 1500: loss 286.829212
iteration 200 / 1500: loss 107.790742
iteration 300 / 1500: loss 42.150164
iteration 400 / 1500: loss 18.471476
iteration 500 / 1500: loss 10.574814
iteration 600 / 1500: loss 7.462733
iteration 700 / 1500: loss 5.594364
iteration 800 / 1500: loss 5.664587
iteration 900 / 1500: loss 5.793565
iteration 1000 / 1500: loss 5.320651
iteration 1100 / 1500: loss 5.425712
iteration 1200 / 1500: loss 5.469809
iteration 1300 / 1500: loss 5.172796
iteration 1400 / 1500: loss 4.882420
That took 8.663645s

``````
``````

In [14]:

# A useful debugging strategy is to plot the loss as a function of
# iteration number:
plt.plot(loss_hist)
plt.xlabel('Iteration number')
plt.ylabel('Loss value')

``````
``````

Out[14]:

<matplotlib.text.Text at 0x110f0fd50>

``````
``````

In [15]:

# Write the LinearSVM.predict function and evaluate the performance on both the
# training and validation set
y_train_pred = svm.predict(X_train)
print 'training accuracy: %f' % (np.mean(y_train == y_train_pred), )
y_val_pred = svm.predict(X_val)
print 'validation accuracy: %f' % (np.mean(y_val == y_val_pred), )

``````
``````

training accuracy: 0.373980
validation accuracy: 0.387000

``````
``````

In [10]:

from cs231n.classifiers import LinearSVM
# Use the validation set to tune hyperparameters (regularization strength and
# learning rate). You should experiment with different ranges for the learning
# rates and regularization strengths; if you are careful you should be able to
# get a classification accuracy of about 0.4 on the validation set.
learning_rates = [5e-7, 1e-7, 5e-6, 1e-6, 1e-5]
regularization_strengths = [5e4, 1e5]

# results is dictionary mapping tuples of the form
# (learning_rate, regularization_strength) to tuples of the form
# (training_accuracy, validation_accuracy). The accuracy is simply the fraction
# of data points that are correctly classified.
results = {}
best_val = -1   # The highest validation accuracy that we have seen so far.
best_svm = None # The LinearSVM object that achieved the highest validation rate.

################################################################################
# TODO:                                                                        #
# Write code that chooses the best hyperparameters by tuning on the validation #
# set. For each combination of hyperparameters, train a linear SVM on the      #
# training set, compute its accuracy on the training and validation sets, and  #
# store these numbers in the results dictionary. In addition, store the best   #
# validation accuracy in best_val and the LinearSVM object that achieves this  #
# accuracy in best_svm.                                                        #
#                                                                              #
# Hint: You should use a small value for num_iters as you develop your         #
# validation code so that the SVMs don't take much time to train; once you are #
# confident that your validation code works, you should rerun the validation   #
# code with a larger value for num_iters.                                      #
################################################################################
verbose = True
for lr in learning_rates:
for reg in regularization_strengths:
if verbose: print "Training with hyper parameter learning rate: %e, regularization: %e " % ( lr, reg )
svm = LinearSVM()
loss_hist = svm.train(X_train, y_train, learning_rate=lr, reg=reg,
num_iters=1500, verbose=False)

y_train_pred = svm.predict(X_train)
training_accuracy = np.mean(y_train == y_train_pred)

y_val_pred = svm.predict(X_val)
val_accuracy = np.mean(y_val == y_val_pred)

results[lr, reg] = (training_accuracy, val_accuracy)
if val_accuracy > best_val:
best_val = val_accuracy
best_svm = svm

# Print out results.
for lr, reg in sorted(results):
train_accuracy, val_accuracy = results[(lr, reg)]
print 'lr %e reg %e train accuracy: %f val accuracy: %f' % (lr, reg, train_accuracy, val_accuracy)

print 'best validation accuracy achieved during cross-validation: %f' % best_val

``````
``````

Training with hyper parameter learning rate: 5.000000e-07, regularization: 5.000000e+04
Training with hyper parameter learning rate: 5.000000e-07, regularization: 1.000000e+05
Training with hyper parameter learning rate: 1.000000e-07, regularization: 5.000000e+04
Training with hyper parameter learning rate: 1.000000e-07, regularization: 1.000000e+05
Training with hyper parameter learning rate: 1.000000e-06, regularization: 5.000000e+04
Training with hyper parameter learning rate: 1.000000e-06, regularization: 1.000000e+05
Training with hyper parameter learning rate: 5.000000e-05, regularization: 5.000000e+04

cs231n/classifiers/linear_svm.py:92: RuntimeWarning: overflow encountered in double_scalars
loss += 0.5 * reg * np.sum(W ** 2)
cs231n/classifiers/linear_svm.py:92: RuntimeWarning: overflow encountered in square
loss += 0.5 * reg * np.sum(W ** 2)

Training with hyper parameter learning rate: 5.000000e-05, regularization: 1.000000e+05
lr 1.000000e-07 reg 5.000000e+04 train accuracy: 0.369714 val accuracy: 0.383000
lr 1.000000e-07 reg 1.000000e+05 train accuracy: 0.354673 val accuracy: 0.367000
lr 5.000000e-07 reg 5.000000e+04 train accuracy: 0.335102 val accuracy: 0.337000
lr 5.000000e-07 reg 1.000000e+05 train accuracy: 0.326204 val accuracy: 0.339000
lr 1.000000e-06 reg 5.000000e+04 train accuracy: 0.283816 val accuracy: 0.263000
lr 1.000000e-06 reg 1.000000e+05 train accuracy: 0.229510 val accuracy: 0.222000
lr 5.000000e-05 reg 5.000000e+04 train accuracy: 0.043673 val accuracy: 0.042000
lr 5.000000e-05 reg 1.000000e+05 train accuracy: 0.100265 val accuracy: 0.087000
best validation accuracy achieved during cross-validation: 0.383000

cs231n/classifiers/linear_svm.py:114: RuntimeWarning: overflow encountered in multiply
dW += reg * W
cs231n/classifiers/linear_svm.py:104: RuntimeWarning: invalid value encountered in greater
select_wrong[margins > 0] = 1
cs231n/classifiers/linear_classifier.py:64: RuntimeWarning: invalid value encountered in subtract

``````
``````

In [14]:

# Visualize the cross-validation results
import math
x_scatter = [math.log10(x[0]) for x in results]
y_scatter = [math.log10(x[1]) for x in results]

# plot training accuracy
sz = [results[x][0]*1500 for x in results] # default size of markers is 20
plt.subplot(1,2,1)
plt.scatter(x_scatter, y_scatter, sz)
plt.xlabel('log learning rate')
plt.ylabel('log regularization strength')
plt.title('CIFAR-10 training accuracy')

# plot validation accuracy
sz = [results[x][1]*1500 for x in results] # default size of markers is 20
plt.subplot(1,2,2)
plt.scatter(x_scatter, y_scatter, sz)
plt.xlabel('log learning rate')
plt.ylabel('log regularization strength')
plt.title('CIFAR-10 validation accuracy')

``````
``````

Out[14]:

``````
``````

In [15]:

# Evaluate the best svm on test set
y_test_pred = best_svm.predict(X_test)
test_accuracy = np.mean(y_test == y_test_pred)
print 'linear SVM on raw pixels final test set accuracy: %f' % test_accuracy

``````
``````

linear SVM on raw pixels final test set accuracy: 0.368000

``````
``````

In [16]:

# Visualize the learned weights for each class.
# Depending on your choice of learning rate and regularization strength, these may
# or may not be nice to look at.
w = best_svm.W[:,:-1] # strip out the bias
w = w.reshape(10, 32, 32, 3)
w_min, w_max = np.min(w), np.max(w)
classes = ['plane', 'car', 'bird', 'cat', 'deer', 'dog', 'frog', 'horse', 'ship', 'truck']
for i in xrange(10):
plt.subplot(2, 5, i + 1)

# Rescale the weights to be between 0 and 255
wimg = 255.0 * (w[i].squeeze() - w_min) / (w_max - w_min)
plt.imshow(wimg.astype('uint8'))
plt.axis('off')
plt.title(classes[i])

``````
``````

``````

### Inline question 2:

Describe what your visualized SVM weights look like, and offer a brief explanation for why they look they way that they do.

``````

In [ ]:

``````