1.  Convolutional Neural Networks

We will work with the MNIST dataset for this question. This dataset contains 60,000 training im- ages of handwritten numbers from 0 to 9, and you need to recognize the handwritten numbers by building a CNN.

You will use the Keraslibrary for this. You might have to installthe library if it hasn’t been installed already. Please check the installation by printing out the version of Keras inside the python shell as follows.

import   keras

keras . _ _ version _ _

The above lines will give you the current version of Keras you are using. Once this works, you can proceed with the assignment.

(a)  Loading Dataset For using this dataset, you will need to import mnist and use it as follows.

from   keras . datasets   import  mnist

( train _X ,  train _ Y ) ,   ( test _X ,  test _Y )  =  mnist . load _ data ()

To verify that you have loaded the dataset correctly, try printing out the shape of your train and test dataset matrices.  Also, try to visualize individual images in this dataset by using imshow() function in pyplot. Below are some example images from the Tensorflow datasets catalog.

(b)  Preprocessing The data has images with 28 x 28 pixel values. Since we use just one grayscale color channel, you need to reshape the matrix such that we have a 28 x 28 x 1 sized matrix holding each input data-point in the training and testing dataset. The output variable can be converted into a one-hot vector by using the function to_categorical (make sure you import to_categorical from keras.utils). For example, if the output label for a given image is the digit

2, then the one-hot representation for this consists of a 10-element vector, where the element at index 2 is set to 1 and all the other elements are zero.

For preprocessing, scale the pixel values such that they lie between 0.0 and 1.0. Make sure that you use the appropriate conversion to float wherever required while scaling.

You can include all these steps into a single python function that loads your dataset appro- priately. Once you finish this, visualize some images using imshow() function.

(c) Implementation

Now, to define a CNN model, we will use the Sequentialmodule in Keras. We are providing you with the code for creating a simple CNN here. We use Conv2D (for declaring 2D con- volutional networks), MaxPooling2D (for maxpooling layer), Dense (for densely connected neural network layers) and Flatten (for flattening the input for next layer).

from  keras . optimizers  import SGD

def  create_cnn ( ) :

#  d efine  using  S equ ential

model  =  S equ ential   ( )

#  Convolution  l ay e r

model . add (

Conv2D( 3 2 ,   ( 3 ,  3) ,

a c t iv a t i o n = ' r e l u ' ,

k e r n e l _ i n i t i a l i z e r = ' he_uniform ' ,

input_shape = (2 8 ,  28 ,  1) )

)

#  Maxpooling  l ay e r

model . add ( MaxPooling2D ( ( 2 ,  2) ) )

#  F l a t t e n  output

model . add ( F l a t t e n ( ) )

#  Dense  l ay e r  of  100  neurons

model . add (

Dense  (100   ,

a c t iv a t i o n = ' r e l u ' ,

k e r n e l _ i n i t i a l i z e r = ' he_uniform ' )

)

model . add ( Dense ( 1 0 ,  a c t iv a t i o n = ' softmax ' ) )

#  i n i t i a l i z e  optimizer

opt  = SGD( l r = 0 . 0 1 ,  momentum= 0 . 9 )

#  compile  model

model . compile (

optimizer=opt ,

l o s s = ' c a t e g o r i c al_ c r o s s e n t r o py ' ,

metrics =[ ' accuracy ' ]

)

return  model

Specifically, we have added the following things in this code.

i. A single convolutional layer with 3 x 3 sized window for computing the convolution, with

32 filters

ii.  Maxpooling layer with 2 x 2 window size.

iii.  Flatten resulting features to reshape your output appropriately.

iv.  Dense layer on top of this (100 neurons) with ReLU activation

v.  Dense layer with 10 neurons for calculating softmax output (Our classification result will output one of the ten possible classes, corresponding to our digits)

After defining this model, we use Stochastic Gradient Descent (SGD) optimizer and cross- entropy loss to compile the model. We are using a learning rate of 0.01 and a momentum of 0.9 here.  We have added this to the given code stub already.  Please see that this code stub works for you. Try to print model.layers in your interactive shell to see that the model is generated as we defined.

(d) Training and Evaluating CNN

Now we will train the network. You can see some examples here. Look at the fit() and evalu- ate() methods.

You will call the fit method with a validation split of 0.1 (i.e.  10% of data will be used for validation in every epoch). Please use 10 epochs and a batch size of 32. When you evaluate the trained model, you can call the evaluate method on the test data-set. Please report the accuracy on test data after you have trained it as above. You can refer to the following while you write code for training and evaluating your CNN.

model . fit ( train _x ,  train _y ,  batch _ size =32 ,   epochs =10 ,

v a l i d a t i o n _ s p l i t =0 . 1)

score  =  model . evaluate ( test _x ,  test _y ,  verbose =0)

(e)  Experimentation

i.  Run the above training for 50 epochs.  Using pyplot, graph the validation and training accuracy after every 10 epochs.  Is there a steady improvement for both training and validation accuracy?

For accessing the required values while plotting, you can store the output of the fit method while training your network. Please refer to the code below.

epoch_history  =  model . f i t ( t r a i n_x ,  t r a i n_y ,  b at ch_ s iz e =32 ,  epochs =10 , v a l i d a t i o n _ s p l i t = 0 . 1 )

#  p r i n t  v a l i d a t i o n  and  t r a i n i n g  accuracy  over  epochs

p r i n t ( epoch_history . h i s t o ry [ ' accuracy ' ] )

p r i n t ( epoch_history . h i s t o ry [ ' val_ accuracy ' ] )

Make sure that your plot has a meaningful legend, title, and labels for X/Y axes.

ii. To avoid over-fitting in neural networks, we can‘drop out’a certain fraction of units ran- domly during the training phase. You can add the following layer (before the dense layer with 100 neurons) to your model defined in the function create_cnn.

model . add ( Dropout (0 . 5) )

Make sure you import Dropout from keras.layers! Now, train this CNN for 50 epochs. Graph the validation and train accuracy after every 10 epochs.

Thistutorial might be helpful if you want to see more examples of dropout with Keras.

iii. Add another convolution layer and maxpooling layer to the create_cnn function defined above (immediately following the existing maxpooling layer). For the additional convo- lution layer, use 64 output filters. Train this for 10 epochs and report the test accuracy.

iv. We used a learning rate of 0.01 in the given create_cnn function.  Using learning rates of 0.001 and 0.1 respectively, train the model and report accuracy on test data-set. Use Dropout, 2 convolution layers and train for 10 epochs for this experiment.

(f) Analysis

i.  Explain how the trends in validation and train accuracy change after using the dropout layer in the experiments.

ii.  How does the performance of CNN with two convolution layers differ as compared to CNN with a single convolution layer in your experiments?

iii.  How did changing learning rates change your experimental results in part (iv)?

2.  Random Forests for Image Approximation In this question, you will use random forest regression to approximate an image by learning a function, f  : R2 一 R , that takes image (x, y) coordinates as input and outputs pixel brightness. This way, the function learns to approximate areas of the image that it has not seen before.

a.  Start with an image of the Mona Lisa. If you don’t like the Mona Lisa, pick another interesting image of your choice.

b.  Preprocessing the input. To build your“training set,”uniformly sample 5,000 random (x, y) coordinate locations.

• What other preprocessing steps are necessary for random forests inputs? Describe them, implement them, and justify your decisions. In particular, do you need to perform mean subtraction, standardization, or unit-normalization?

c.  Preprocessing the output.  Sample pixel values at each of the given coordinate locations. Each pixel contains red, green, and blue intensity values, so decide how you want to handle this. There are several options available to you:

•  Convert the image to grayscale

•  Regress all three values at once, so your function maps (x, y) coordinates to (r, g, b) val- ues: f  : R2 一 R3

Figure 1: Left: http://tinyurl.com/mona-lisa-smallMona Lisa, Leonardo da Vinci, via Wikipedia. Licensed under Public Domain.  Middle: Example output of a decision tree regressor.  The input is a “feature vector”containing the (x, y) coordinates of the pixel.  The output at each point is an (r, g, b)  tuple. This tree has a depth of 7. Right: Example output of a k-NN regressor, where k = 1. The output at each pixel is equal to its closest sample from the training set.

•  Learn a different function for each channel, fRed : R2 一 R, and likewise for fGr een , fBl ue .

Note that you may need to rescale the pixel intensities to lie between 0.0 and 1.0. (The de- fault for pixel values may be between 0 and 255, but your image library may have different defaults.)

What other preprocessing steps are necessary for random regression forest outputs? Describe them, implement them, and justify your decisions.

d.  To build the final image, for each pixel of the output, feed the pixel coordinate through the random forest and color the resulting pixel with the output prediction.  You can then use imshow to view the result. (If you are using grayscale, try imshow(Y,  cmap=‘gray’) to avoid fake-coloring). You may use any implementation of random forests, but you should under- stand the implementation and you must cite your sources.

e.  Experimentation.

i.  Repeat the experiment for a random forest containing a single decision tree, but with depths 1, 2, 3, 5, 10, and 15. How does depth impact the result? Describe in detail why.

ii.  Repeat the experiment for a random forest of depth 7, but with number of trees equal to 1, 3, 5, 10, and 100. How does the number of trees impact the result? Describe in detail why.

iii. As a simple baseline, repeat the experiment using a k-NN regressor, for k = 1. This means that every pixel in the output will equal the nearest pixel from the“training set.”Compare and contrast the outlook: why does this look the way it does? You may use an existing implementation of k-NN but make sure to cite your source.

iv.  Experiment with different pruning strategies of your choice.

f.  Analysis.

i. What is the decision rule at each split point? Write down the 1-line formula for the split point at the root node for one of the trained decision trees inside the forest. Feel free to define any variables you need.

ii. Why does the resulting image look like the way it does? What shape are the patches of color, and how are they arranged?

WRITTEN EXERCISES

1. Maximum Margin Classifiers Suppose we are given n = 7 observations in p = 2 dimensions.  For each observation, there is an associated class label.

a.  Sketch the observations and the maximum- margin separating hyperplane.

b.  Describe the classification rule for the maxi- mal margin classifier. It should be something along the lines of“Classify as Red if β0+β 1x1 + β2x2 < 0, and classify to Blue otherwise.”Pro- vide the values for β0 , β 1 , and β2 .

c.  On your sketch, indicate the margin for the maximal margin hyperplane.

d.  Indicate the support vectors for the maximal margin classifier.

e.  Argue that a slight movement of the seventh observation would not affect the maximal mar- gin hyperplane.

f.  Sketch a hyperplane that separates the data, but is not the maximum-margin separating hy- perplane. Provide the equation for this hyperplane.

g.  Draw an additional observation on the plot so that the two classes are no longer separable by a hyperplane.

2.  Kernels In this question, we will get more hands-on experience working with kernels. Through- out, suppose our inputs live in 2 dimensional space. Formally, let X represent our input space, then X ⊆ R2 . For all x e X, let x1 and x2 be the first and second components of the input vector, respectively.

a.  We begin with the following motivating example.  Suppose we have a binary classification dataset consisting of four labeled datapoints, with labels y (i ) e {−1, +1}:

• x(1) = [−1, 1]⊤ , y (1) = +1

• x(2) = [1, 1]⊤ , y (2) = − 1

• x(3) = [1, − 1]⊤ , y (3) = +1

• x(4) = [−1, − 1]⊤ , y (4) = − 1

As you can see in the plot below, this dataset is not linearly separable, meaning there is no linear decision boundary that will perfectly classify the points with label +1 (filled in black)

and those with label −1 (not filled)1. Feelfree to give it a try ;)

2

2   

x(1) = (−1, 1)       x(2) = (1, 1)

1

− 1

x(4) = (−1, − 1)    x(3) = (1, − 1)

−2

φ(x)b

2   

1     

−2              − 1                                  1                2

− 1

−2 

φ(x)a

We will use a polynomial Kernel of degree 2 to find a linear decision boundary that perfectly separates this data. Namely, we will use a feature representation φ : R2 一 R6 :

l    x(x)     

φ(x) =

^2x1x2

^2x1

^2x2

i.  For each of the four data points, x(i ) , i = 1, 2, 3, 4, write the corresponding featurized vec- tor φ(x(i )).

ii.  Let φ(x)a be the ath component of the featurized vector. Choose two components a, b e {1, 2, 3, 4, 5, 6} from the featurized vectors and use these to plot the four featurized points in such a way that the data is linearly separable. Label your axes with thefeature you chose and label each point.  Use filled black circles to denote points with label +1 and unfilled black circles to denote points with label − 1.

b.  For two given inputs x,x\ e X, explicitly compute the inner product φ(x)  φ(x⊤ \) as a function of the components x1 ,x2 ,x ,x .

c.  For these same points and representation φ, show that we can equivalently calculate the in- ner product φ(x)  φ(x⊤ \) using a more efficient method, namely

(x⊤x\ + 1)2

That is, show that this is equivalent to the formula you got for the inner product in part b.

d.  Thinking more generally, assume our data is d -dimensional, meaning our input space X ⊆ Rd . The polynomial kernel of degree p = 2 would then correspond to the following feature map:

φ(x) = lxd(2) , . . . ,x1(2) , ^2xdxd −1 , . . . , ^2xdx1 , ^2xd −1xd −2 , . . . , ^2xd −1x1 , . . . , ^2x2x1 , ^2cxd , . . . , ^2cx1 , c |⊤ This featurized representation has dimensionality (d p(+) p) = (d 2(+)2), where (k(n)) is“n choose

k”, which is exponential in k, i.e., (k(n)) = O(n  )k . The corresponding kernel function is K (x,x\) =