CSCI 567, Fall’18
Haipeng Luo
Homework #3 Programming Assignments
Due: 11:59 pm, October 21, 2018
General instructions
Starting point Your repository will have now a directory “P3/”. Please do not change the name of this
repository or the names of any files we have added to it. Please perform. a git pull to retrieve these files.
You will find within it: boosting.py, boosting.sh, boosting check.py, boosting test.py, clas
sifier.py, data loader.py, decision stump.py, decision tree.py, decision tree.sh, deci
sion tree check.py, decision tree test.py, pegasos.py, pegasos.sh, requirements.txt
Download the data Please download mnist subset.json from Piazza/Resource/Homework. Please DO
NOT push it into your repository when you submit your results. Otherwise, you will get 20% deduction of
your score of this assignment.
High-level descriptions
Dataset We will use mnist subset (images of handwritten digits from 0 to 9). This is the same subset
of the full MNIST that we used for Homework 1 and Homework 2. As before, the dataset is stored in a
JSON-formated file mnist subset.json. You can access its training, validation, and test splits using the keys
‘train’, ‘valid’, and ‘test’, respectively. For example, suppose we load mnist subset.json to the variable x.
Then, x[0train0] refers to the training set of mnist subset. This set is a list with two elements: x[0train0][0]
containing the features of size N (samples) D (dimension of features), and x[0train0][1] containing the
corresponding labels of size N.
Tasks
1. You will be asked to implement the linear support vector machine (SVM) for binary classification
(Sect. 1). Specifically, you will
finish implementing the following three functions—objective function, pegasos train,
and pegasos test—in pegasos.py. Refer to pegasos.py and Sect. 1 for more information.
run the script. pegasos.sh after you finish your implementation. This will output pegasos.json.
add, commit, and push (1) the pegasos.py, and (2) the pegasos.json file that you have
created.
2. You will be asked to implement the boosting algorithms with decision stump (Sect. 2). Specifically,
you will
finish implementing the following classes — boosting, decision stump, AdaBoost and Log
itBoost. Refer to boosting.py, decision stump.py and Sect. 2 for more information.
test and debug your code using the provided boosting check.py.
run the script. boosting.sh (which executes boosting test.py). This will output boost
ing.json.
add, commit, and push (1) the boosting.py, (2) the decision stump.py, and (3) the boost
ing.json.
3. You will be asked to implement the decision tree classifier (Sect. 3). Specifically, you will
1
finish implementing the following classes — DecisionTree, TreeNode. Refer to decision tree.py
and Sect. 3 for more information.
test and debug your code using the provided decision tree check.py.
run the script. decision tree.sh (which executes decision tree test.py). This will out-
put decision tree.json.
add, commit, and push (1) the decision tree.py, (2) the decision tree.json
As in the previous homework, you are not responsible for loading/pre-processing data; we have done
that for you (e.g., we have pre-processed the data so it has two classes: digits 0–4 and digits 5–9.). For
specific instructions, please refer to text in Sect. 1 and 2 and the instructions in pegasos.py and boost
ing.py.
Cautions Please do not import packages that are not listed in the provided code. Follow the instructions
in each section strictly to code up your solutions. Do not change the output format. Do not modify the
code unless we instruct you to do so. A homework solution that does not match the provided setup,
such as format, name, initializations, etc., will not be graded. It is your responsibility to make sure that
your code runs with the provided commands and scripts on the VM. Finally, make sure that you git add,
commit, and push all the required files, including your code and generated output files.
2
Problem 1 Pegasos: a stochastic gradient based solver for linear SVM
In this question, you will build a linear SVM (i.e. without kernel) classifier using the Pegasos algorithm [1].
Given a training setf(xn 2RD, yn 2f1, 1g)gNn=1, the primal formulation of linear SVM can be written as
L2-regularized hinge loss as shown in the class:
minw l2jjwjj22 + 1N
n
maxf0, 1 ynwTxng. (1)
Note that here we include the bias term b into parameter w by appending x with 1, which is slightly different
from what was discussed in the class.
Instead of turning it into dual formulation, we are going to solve the primal formulation directly with
a gradient-base algorithm. Recall for (batch) gradient descent, at each iteration of parameter update, we
compute the gradients for all data points and take the average (or sum). When the training set is large
(i.e., N is a large number), this is often too computationally expensive. Stochastic gradient descent with
mini-batch alleviates this issue by computing the gradient on a subset of the data at each iteration.
Pegasos, a representative solver of eq. (1), is exactly applying stochastic gradient descent with mini-
batch to this problem, with an extra step of projection described below (this is also called projected stochas-
tic gradient descent). The pseudocode of Pegasos is given in Algorithm 1. At the t-th iteration of parameter
update, we first take a mini-batch of data At of size K [step (3)], and define A+t At to be the subset
of samples for which wt suffers a non-zero loss [step (4)]. Next we set the learning rate ht = 1/(lt)
[step (5)]. We then perform. a two-step parameter update as follows. We first compute (1 htl)wt
and for all samples (x, y)2 A+t we add the vector yhtK x to (1 htl)wt. We denote the resulting vector by
wt+1
2
[step (6)]. This step is in fact exactly stochastic gradient descent: wt+1
2
= wt htrt where
rt = lwt 1K
(x,y)2A+t
yx
is the (sub)gradient of the objective function on the mini-batch At at wt. Last, we set wt+1 to be the projec-
tion of wt+1
2
onto the set
B =fw :jjwjj2 1/
p
lg
to control its L2 norm. This can be obtained simply by scaling wt+1 by min
(
1, 1/
pl
jjwt+1
2
jj
)
[step (e)].
For more details of Pegasos algorithm you may refer to the original paper [1].
Now you are going to implement Pegasos and train a binary linear SVM classifier on the dataset
mnist subset.json. You are going to implement three functions—objective function, pegasos train,
and pegasos test—in a script. named pegasos.py. You will find detailed programming instructions in
the script.
1.1 Finish the implementation of the function objective function, which corresponds to the objective
function in the primal formulation of SVM.
1.2 Finish the implementation of the function pegasos train, which corresponds to Algorithm 1.
3
Algorithm 1 The Pegasos algorithm
Require: a training set S =f(xn 2RD, yn 2f1, 1g)gNn=1, the total number of iterations T, the batch size
K, and the regularization parameter l.
Output: the last weight wT+1.
1: Initialization: w1 = 0
2: for t = 1, 2, , T do
3: Randomly choose a subset of data At 2S (with replacement) such thatjAtj= K
4: Set A+t =f(x, y)2At : ywTt xt b,
s, otherwise. (2)
That is, each decision stump function only looks at a single dimension xd of the input vector x, and check
whether xd is larger than b. Then s decides which label to predict if xd > b.
Please first read classifier.py and decision stump.py, and then complete the class “DecisionS-
tump” by implementing the “TODO” part(s) as indicated in decision stump.py.
2.3 AdaBoost AdaBoost is a powerful and popular boosting method, summarized in Algorithm 2.
Algorithm 2 The AdaBoost algorithm
Require: H: A set of classifiers, where h2Htakes a D-dimensional vector as input and outputs either +1
or 1, a training setf(xn 2RD, yn 2f+1, 1g)gN 1n=0 , the total number of iterations T.
Ensure: Learn H(x) = sign
h
T 1t=0 btht(x)
i
, where ht 2Hand bt 2R.
1: Initialization D0(n) = 1N ,8n2f0, 1, , N 1g.
2: for t = 0, 1, , T 1 do
3: find ht = argminh2H n Dt(n)I[yn 6= h(xn)]
4: compute et = n Dt(n)I[yn 6= ht(xn)]
5: compute bt = 12 log 1 ete
t
6: compute Dt+1(n) =
(
Dt(n)exp( bt), if yn = ht(xn)
Dt(n)exp(bt), otherwise , 8n2f0, 1, , N 1g
7: normalize Dt+1(n) Dt+1(n)
n0 Dt+1(n0)
, 8n2f0, 1, , N 1g
8: end for
Please read the class ”AdaBoost” defined in boosting.py, and then complete the class by implement-
ing the ”TODO” part(s) as indicated in boosting.py.
2.4 Final submission Please run boosting.sh, which will generate boosting.json. Add, commit,
and push boosting.py, decision stump.py and boosting.json before the due date.
5
Problem 3 Decision Tree
In this question, you will implement a simple decision tree algorithm. For simplicity, only discrete features
are considered here.
3.1 Conditional Entropy Recall that the quality of a split can be measured by the conditional entropy.
Please read decision tree.py and complete the function “conditional entropy” (where we use base 2
for logarithm).
3.2 Tree construction The building of a decision tree involves growing and pruning. For simplicity, in
this programming set you are only asked to grow a tree.
As discussed a tree can be constructed by recursively splitting the nodes if needed, as summarized in
Algorithm 3 (whose interface is slightly different from the pseudocode discussed in the class). Please read
decision tree.py and complete the function “split”.
Algorithm 3 The recursive procedure of decision tree algorithm
1: function TREENODE.SPLIT(self)
2: find the best attribute to split the node
3: split the node into child nodes
4: for child node in child nodes do
5: if child node.splittable then . See Slide 27 of Lec 7 for the three “non-splittable” cases
6: child node.split()
7: end if
8: end for
9: end function
3.3 Final submission Please run decision tree.sh, which will generate decision tree.json. Add,
commit, and push decision tree.py, decision tree.json before the due date.