Due on: Friday, JUNE 25th at 23:59 PST

Where: Brightspace (https://bright.uvic.ca/d2l/home/136102)

Instructions: >? You must complete this assignment entirely on your own. In other words, you should come up

with the solution yourself, write the code yourself, conduct the experiments yourself, analyze the

results yourself, and finally, write it all solely by yourself. The university policies on academic

dishonesty (a.k.a. cheating) will be taken very seriously.

? This does not mean that you need to go to a cave and self-isolate while preparing the assignment.

You are allowed to have high-level discussions with your classmates about the course material.

You are also more than welcome to use Piazza or come to office hours and ask questions. If in

doubt, ask!?? we are here to help.

? If you are still stuck, you can use books and published online material (i.e., material that has a

fixed URL). However, you must explicitly credit all sources. You are also not allowed

to copy-paste online materials. Woe to you if we catch you copy-pasting the uncredited

sources!

?C Why ??if stuck??? Assignments are designed to develop your practical ML skills and make

you strong. If you do the assignments well, the project will feel like a piece of cake. So,

give your best. But, on the other hand, do not waste a whole week on a single question:

if you are stuck on a question for a few days, ask (us) for help!

? If you cannot make it until the deadline, you can use a maximum of two grace days per

assignment. They are not free, though: each grace day comes with the 25% mark penalty

(so submitting on Monday evening would reduce your score by 25%; submitting on Tuesday

would further reduce it by 50%). No other accommodations will be provided unless explicitly

approved by the instructor at least 7 days before the deadline.

? These assignments are supposed to be really hard! Start early! You will need at least

two weeks to complete them!

?C If you do not feel challenged enough, please let me know, and I??ll think of something.

? Remember: you will need to gather at least one-third of all points during the assign-

ments to pass the course. If you don??t, you will get an F!

? Make sure to follow the technical requirements outlined below. TAs have the full power to take

50% off your grade if you disregard some of them.

? Be sure that your answers are clear and easy for TAs to understand. They can penalize you if

your solutions lack clarity or are convoluted (in a non-algebraic way), even if they are nominally

correct.

? We will try to grade your assignments within seven (7) days of the initial submission deadline.

1

? If you think there is a problem with your grade, you have one week to raise concerns after the

grades go public. Grading TAs will be holding office hours during those seven days to address

any such problems. After that, your grade is set in stone.

Technical matters:

? You must type up your analysis and solutions electronically and submit them as a self-containing

Jupyter notebook. Jupyter notebooks can contain code, its output, and images. They can also

be used to type math and proofs in LATEX mode.

?C You must use LATEX mode to type formulas. Typing a?2=sqrt(3)+b1 is a pretty good

way to lose 50% of your grade for no good reason.

? Each problem should be submitted as a separate file.

? Each file should be named SurnameInitial N.ipynb, where N is two digit-padded problem

number. Correct: SmithJ 05.ipynb. Incorrect: JohnSmith V12345 Problem 1.ipynb,

prob1.pdf etc.

? Zip all ipynb files and submit them as assignment1.zip to the Brightspace. Do not submit

RAR, TAR, 7zip, SHAR and whatnot; just use good ol?? ZIP. Do not include other files.

? The first cell of each Jupyter notebook must start with your name and V number. See the

attached notebook for the details.

? Your notebook should be organized sequentially according to the problem statement. Use

sections (with the appropriate numbers and labels) within the notebook. Figures and relevant

code should be placed in the proper location in the document.

? Notebook code must be runnable! Ideally, all answers will be the output of a code cell.

? You must use Python 3 to complete the assignments. Feel free to use NumPy and pandas as

you find it fit. Use SciPy, scikit-learn, and other non-standard libraries only when explicitly

allowed to do so.

? Your first executable cell should set the random seed to 1337 to ensure the reproducibility of

your results. For Numpy/SciPy and pandas, use numpy.random.seed(1337); otherwise, use

random.seed(1337).

? Document your code! Use either Markdown cells or Python comments to let us know what you

have done!

? Finally, be concise! We do not appreciate long essays that amount to basically nothing.

This assignment consists of 4 problems. Some are intended only for graduate students (those

taking CSC 503), and are labelled as such. Some contain bonus sections: you can use bonus points

to improve your overall homework score. Bonus points cannot be transferred to other assignments or

the final project. Any graduate-level problem counts as a bonus problem for undergraduate students.

Some problems are purposefully open-ended. Whatever you think the correct answer is, make

sure to support it with code and data.

2

Problem 1. The American Handwriting [40 points]

The U.S. National Institute of Standards and Technology collected digital images of the digits written

by high school students and the U.S. Census Bureau employees over the years. These images serve

as the basis of the extremely popular MNIST dataset that is commonly used to benchmark machine

learning classifiers.

Wouldn??t it be a good idea to play with that dataset? To do so, install Keras and load the MNIST

dataset as follows:

from keras.datasets import mnist

(train_X, train_y), (test_X, test_y) = mnist.load_data()

Now, let??s see how we can use neural networks to classify these images.

1. [Derivative; 5 points] Calculate the gradient of the softmax function:

f(x)i =

exi??

j e

x

j

2. [Simple; 10 points] Implement a simple one-layered neural network from scratch (using only

NumPy). The implementation should include the forward propagation (i.e. prediction), and

the backpropagation-powered gradient descent for training the network. Feel free to select

the number of nodes in the hidden layer yourself (it must be, however, greater than 10; the

recommended value is 128). Each hidden node should use the sigmoid activation function.

The output layer should use the softmax activation function to produce the final 10 values

(probabilities of each digit). You can use either classical or stochastic gradient descent. Learning

rate and the number of iterations are also up to you; you can experiment with {0.001, 0.01, 0.1}

to get a sense of the best learning rate.

Plot the network??s accuracy (or error) on test data as the number of iterations increases. Does

it keep raising (falling) with the number of gradient descent iterations?

3. [Keras; 5 points] Now use Keras to model and train the exact same network. Faster, slower?

Better?

4. [ReLU; 5 points] This time, use the ReLU activation functions instead of the sigmoids. What

happens?

5. [Dropout; 5 points] Now add two hidden layers. You should end up with a three-layer deep

neural network. Use Keras to model the network and add dropout to each layer. Further-

more, use L2 regularization for the training objective. Use cross-validation to select the best

regularization and dropout hyperparameters. How much improvement did you get?

6. [Convolution; 5 points] Use Keras to model and train a simple convolutional network with

one convolutional layer, one pooling layer, and one fully connected layer. You are free to pick

any hyperparameters you want: play with the data and provide some justification behind your

hyperparameter selection. How much improvement did you get, if any?

7. [Mugshots; 5 points] Display nine images of your choice that were consistently misclassified

by all of the above models (if there are no such images, pick at least those that were mis-

classified most of the time). You can plot an image via matplotlib.pyplot.imshow(image,

cmap=??gray??). Would you be able to classify those images yourself or not? Why?

3

It goes without saying: for each model, provide the corresponding training and test errors with

the metrics of your choice.

Bonus [5 points]: Use the leaky ReLU activation function for your artisan neural network you

made from scratch ([Simple]). Any improvements?

Problem 2. Support machines [20 points]

We have seen in the class how to use support vector machines to perform binary classification. Let??s

now see how they work in practice by playing with the sklearn??s SVM implementation.

1. [Hard; 5 points] Select all images corresponding to ones and sevens from the MNIST dataset,

and train a hard-margin SVM classifier that classifies if an image depicts 1 or 7. How good is

it? Can it even be done?

2. [Soft; 5 points] Now train a soft-margin SVM classifier for the same problem. Use cross-

validation to select the best value of C. Did you achieve better results?

3. [Kernel; 5 points] Try the following kernels with the best soft-margin model and see which

one is the best:

(a) polynomial kernel of various degrees;

(b) Gaussian kernel with various values of ?? (also known as radial basis function kernel); and

(c) linear kernel.

So far, we??ve only used SVMs for binary for binary classification. But did you know that they can

be used for multiclass classification as well? One common way to do it is by using all-vs-all (AVA)

classification trick: train n(n? 1) binary classifiers fi,j that distinguish between the pairs of classes

i and j (if you have, of course, n different classes). Then, you can classify an example x as:

f(x) = arg max

i

??

j

fi,j(x).

4. [AVA; 5 points] Use the best-performing SVM model thus far to implement the multiclass

AVA classification for all digits at once. Once done, plot the confusion matrix (heatmap) of all

n2 classifiers.

Again, for each model, make sure to provide the training and test errors in the metrics of your

choice.

Problem 3. Pigs, begone! [20 points]

Let??s get rid of those annoying spam texts! First, get the SMS dataset from https://archive.ics.

uci.edu/ml/machine-learning-databases/00228/. This dataset consists of short SMS messages

and their class (spam or ham, where ham is not spam).

Represent each message as a bag of words, and use these bags of words to train your Na ive Bayes

classifier to predict if a message is a spam or not.

Use 70/30% split for the training/test data. How good is your simple classifier?

4

Problem 4. Uber-SVM [20 points; only for CSC 503]

Sometimes it is worth using different slack variables for different classes in the soft-margin SVM

formulation. For example, we will use this trick if the datasets are not balanced, or if it is more

important to correctly classify one class instead of the other. More formally, for a binary classification

problem between two classes + and ?, we would like to optimize the following function: