Implementation Assignment #2 solution

The following languages are acceptable: Java, C/C++, Python, Matlab



You can work in a team of up to 3 people. Each team will only need to submit one copy of the source code and report. You need to explicitly state each member's contribution in percentages (a rough estimate).



Your source code and report will be submitted through TEACH



You need to submit a readme le that contains the programming language version you use (e.g. python 2.7 ) and the command to run your code (e.g. python main.py).



Please make sure that you can be run code remotely on the server (i.e. babylon01 ) especially if you develop your code using c/c++ under visual studio.



Be sure to answer all the questions in your report. You will be graded based on your code as well as the report. In particular, the clarity and quality of the report will be worth 10 pts. So please write your report in clear and concise manner. Clearly label your gures, legends, and tables.



In your report, the results should always be accompanied by discussions of the results. Do the re-sults follow your expectation? Any surprises? What kind of explanation can you provide?








Perceptron algorithm for Optical Character Recognition (total points: 80 pts + 10 report pts + 10 result pts)







Task description. In the Optical Character Recognition (OCR) we seek to predict a number (between 0 to 9) for a given image of handwritten digit. In this assignment we simplify the OCR into a binary classi cation task. Speci cally, we consider predictions for only two numbers 3 and 5. The goal in this assignment is to develop variations of the perceptron algorithm to classify handwritten digits of numbers 3 or 5.




Data. All the handwritten digits are originally taken from http://www.kaggle.com/c/digit-recognizer/data The original dataset contains the sample digits suitable for OCR. We extract samples with only labels 3 and




Following a little pre-processings we produce three datasets for this assignment as follows:



Train Set (pa2 train.csv): Includes 4888 rows (samples). Each sample is in fact a list of 785 values. The rst number is the digit's label which is 3 or 5. The other 784 oating values are the the attened gray-scale values from a 2d digital handwritten image with shape 28 28.



Validation Set (pa2 valid.csv): Includes 1629 rows. Each row obeys the same format given for the train set. This set will be used to select your best trained model.



Test Set (pa2 test.csv): Includes 1629 rows. Each row contains only 784 numbers. The label column is omitted from each row.






Important Guidelines. For all parts of this assignment:




Please assign labels +1 to number 3 and -1 to label 5. In your produced predictions, please use only +1 and -1 as labels not 3 and 5.



Please do not shu e the given data. While in practice shu ing should be used to improve training convergence, for this assignment we ask you not to shu e the data to ensure determinstic results for assessment purpose.



To simplify the notation in this assignment, your load function which loads train, validation and test dataset should add a bias feature to the dataset. The bias feature is a feature with value of 1.0 for all of the samples. Therefore the feature size for each samples will become 785.












Part 1 (20 pts) : Online Perceptron. In the online perceptron algorithm we train a linear classi er with parameter w to predict the label of a sample with equation:




y^ = sign(wT x)
(1)



Where y^ 2 f 1; 1g. Algorithm 1 describes the online perceptron.







Algorithm 1 Online Perceptron







procedure OnlinePerceptron
w0 0
t 0



while iter < iters:
for all sample xt in train set: // no shu ing
6:
u
sign(wT x
)


t
t t


if ytut 0:
8:
wt+1 wt + ytxt
9:
t t + 1










2



Where xt is the sample at time step t and yt is its correct label. As we can see, the weight at time step t+1 is equivalent to below summation:






X


wt+1 =
yixi
(2)
xi2St




where St is a list containing all the previous samples that have been incorrectly classi ed by the model (some example may appear multiple times). Therefore the prediction at time (t+1) can also be given by:






X


y^t+1 = sign((
yixi)T xt+1)
(3)
xi2St




In this part we are interested in the following experiments for the online perceptron algorithm:




Implement the online perceptron model with algorithm described in Algorithm 1. Set the iters = 15. During the training, at the end of each iteration use the current w to make prediction on the validation samples. Record the accuracies for the train and validation at the end of each iteration. Plot the recorded train and validation accuracies versus the iteration number.



Does the train accuracy reach to 100%? Why?



Use the validation accuracy to decide the test number for iters. Apply the resulting model to make predictions for the samples in the test set. Generate the prediction le oplabel.csv. Please note that your le should only contain +1 (for 3) and -1 (for 5) and the number of rows should be the same as pa2 test.csv.






Part 2 (20 pts) : Average Perceptron. In this part we are interested to utilize average perceptron to deal with some issues regarding the online perceptron. Algorithm 2 describes the average perceptron.










Algorithm 2 Average Perceptron







procedure AveragePerceptron



w 0



c 0



w 0 // keeps running average weight



s 0 // keeps sum of cs



while iter < iters:
for all sample xt in the train set: // no shu ing
8: ut sign(wT xt)

if ytut 0:



10:
if s + c 0 :
11:
w
sw+cw


s+c






12:
s s + c
w w + ytxt
14:




c


0
15:


else: c


c + 1
16:
if c 0:










17:
w
sw
+cw


s+c































As shown in the Algorithm 2, we compute a running average w which is used to predict the label of any sample xi as follows:




y^(x) = sign(wT xi)
(4)



We are interested in below experiments for average perceptron:




(a) Please implement the average perceptron described in Algorithm 2.







3



Plot the train and validation accuracies versus the iteration number for iters = 1; :::; 15.



How average model has a ected the validation accuracy comparing to the online perceptron?



Part 3 (40 pts). Polynomial Kernel Perceptron. The online/average perceptron in Algorithm( 1 and 2) are linear models. In order to increase the model's complexity, one can project the feature vectors into a high (or even in nite) dimensions by applying a projection function . In this case the prediction at time (t+1) is given by:




y^t+1 = sign( (wt+1)T (xt+1))
(5)
Or equivalently by:
X






y^t+1 = sign((
yi (xi))T (xt+1))
(6)
xi2St




Where St is a list containing all the previous sample vectors for which the model has a wrong predictions (there can be repetitions for a sample). Simplifying above equation yields:






X


y^t+1 = sign(
yi (xt+1)T (xi)))
(7)
xi2St




As we see in the equation 7, the prediction at each time steps utilizes a similarity terms i.e. (xt+1)T (xi) between the current projected sample (xt+1) and all the previous samples which we have incorrect predic-tions.




Let's de ne a kernel function with parameter vectors x and y to be k(x; y) = (x)T (y). Therefore the equation is simpli ed to:



X


y^t+1 = sign(
yik(xt+1; xi))
(8)
xi2St




There are di erent kernel functions. For example to compute the similarity between vectors x and y in the polynomial space (with polynomial degree p) we utilize below kernel:




kp(x; y) = (1 + xT y)p
(9)



For p = 1 we have a linear kernel. In this part we are interested in polynomial kernel perceptron as described in Algorithm 3:







Algorithm 3 Kernel (polynomial) Perceptron







procedure KernelPerceptron



N : number of train samples; F : number of features
3: XN F train set

N 1 0
5:
yN 1 train labels


6:
kp(x; y) = (1 + xT y)p
8xi; xj 2 X
7:
KN N (i; j) = kp(xi; xj)
8:







while iter < iters:
for all sample xi 2 X: // no shu ing
12:
if yiu 0:Pj
K[j; i] [j]y[j])
11:
u = sign(


13:
[i]
[i] + 1











Please consider below experiments:




Implement the polynomial kernel function kp in the Algorithm 3. This function takes two vectors x1 and x2 and an integer p for the polynomial degree, and returns a real value.



4



De ne a Gram matrix K with size N N where N is the number of training samples. Fill matrix K(i; j) = kp(xi; xj) for all of the pairs in the training set.



Implement the rest of the kernel perceptron in Algorithm 3. For each p in [1, 2, 3, 7, 15]:



Run the algorithm to compute .



At the end of each iteration use the current to predict validation set.



Record the train and validation accuracy for each iteration and plot the train and validation accu-racies versus the iteration number.



Record the best validation accuracy achieved for each p over all iterations.



Plot the recorded best validation accuracies versus degrees. Please explain how p is a ecting the train and validation performance.



Use your best (the best you found over all d and iterations above) to predict the test data-set. Please name the predicted le as kplabel.csv.






Submission. Your submission should include the following:




Your source code with a short instruction on how to run the code in a readme.txt.



Your report only in pdf, which begins with a general introduction section, followed by one section for each part of the assignment.



Two prediction les oplabel.csv and kplabel.csv. These prediction le will be scored against the ground truth y values and 10% of the grade will be based on this score.



Please note that all the les should be in one folder and compressed only by .zip.