Description
1 Question 1 – Boosting (40 points)
We learned about boosting in lecture and the topic is covered in Murphy 16.4. On page 555 Murphy claims
that “it was proved that one could boost the performance (on the training set) of any weak learner arbitrarily
high, provided the weak learned could always perform slightly better than chance.” We will now verify this
in the AdaBoost framework.
1. (10 points) Given a set of N observations (x
j
, yj
) where y
j
is the label y
j ∈ {−1, 1}, let ht(x) be the
weak classifier at step t and let αt be its weight. First we note that the final classifier after T steps is
defined as:
H(x) = sgn (X
T
t=1
αtht(x)
)
= sgn{f(x)}
Where
f(x) = X
T
t=1
αtht(x)
Show that:
Training =
1
N
X
N
j=1
δ(H(x
j
) 6= y
j
) ≤
1
N
X
N
j=1
exp(−f(x
j
)y
j
)
Where δ(H(x
j
) 6= y
j
) is 1 if H(x
j
) 6= y
j
and 0 otherwise.
2. (10 points) The weight for each data point j at step t + 1 can be defined recursively by:
w
(t+1)
j =
w
(t)
i
exp(−αty
jht(x
j
))
Zt
Where Zt
is a normalizing constant ensuring the weights sum to 1:
Zt =
X
N
j=1
w
t
j
exp(−αty
jht(x
j
))
Show that:
1
N
X
N
j=1
exp(−f(x
j
)y
j
) = Y
T
t=1
Zt
1
3. (20 points) We showed above that training error is bounded above by QT
t=1 Zt
. At step t the values
Z1, Z2, . . . , Zt−1 are already fixed therefore at step t we can choose αt
to minimize Zt
. Let
t =
X
N
j=1
w
t
j
δ(ht(x
j
) 6= y
j
)
be the weighted training error for weak classifier ht(x) then we can re-write the formula for Zt as:
Zt = (1 − t) exp(−αt) + t exp(αt)
(a) First find the value of αt
that minimizes Zt
then show that
Z
opt
t = 2p
t(1 − t)
(b) Assume we choose Zt
this way. Then re-write t =
1
2 − γt where γt > 0 implies better than
random and γt < 0 implies worse than random. Then show that:
Zt ≤ exp(−2γ
2
t
)
You may want to use the fact that log(1 − x) ≤ −x for 0 ≤ x < 1 Thus we have: training ≤ Y T t=1 Zt ≤ exp(−2 X T t=1 γ 2 t ) (c) Finally, show that if each classifier is better than random (e.g. γt ≥ γ for all t and γ > 0) that:
training ≤ exp(−2T γ2
)
Which shows that the training error can be made arbitrarily small with enough steps.
2 Question 2 – Action recognition with CNN (60 points+20 bonus)
In this section, you will train convolutional neural networks (CNN) to classify images and videos using
Pytorch. Similar to homework 2, we use the UCF101 data (see http://crcv.ucf.edu/data/UCF101.php). There
are also 10 classes of data in this homework but the actual classes and data are different from the homework
2. Each clip has 3 frames and each frame is 64 ∗ 64 pixels. The label of clips are in q3 2 data.mat. trLb
are labels for training clips and valLb are labels for validation clips.
You will first train a CNN for action classification for each image. Then try to improve the network
architecture and submit the classification results on the test data to Kaggle. Then, you will train a CNN using
3D convolution to classify each clip as a video rather than a image, and submit your results to Kaggle.
The detail instructions and questions are in the jupyter notebook Action CNN.ipynb. In this file,there
are 8 ’To Do’ spots for you to fill. The score of each ’To Do’ is specified at the spot. For the 5th and 8th
’TO DO’, you need to submit results csv files to Kaggle. The results would be evaluated by Categorization
Accuracy.
For the 5th ’TO DO’ submit the result .csv file to http://www.kaggle.com/c/cse512springhw3.
For the 8th ’To Do’ submit the result .csv file to http://www.kaggle.com/c/cse512springhw3video.
We will maintain a leader board for each Kaggle competition, and the top three entries at the end of the
competition (assignment due date) will receive 10 bonus points. Any submission that rises to top three after
the assignment deadline is not eligible for bonus points. The ranking will be based on the Categorization
2
Accuracy. To prevent exploiting test data, you are allowed to make a maximum of 2 submissions per 24
hours. Your submission will be evaluated immediately and the leader board will be updated.
Environment setting:
Please make a ./data folder under the same directory with the Action CNN.ipynb file. Put data
./trainClips, ./valClips, ./testClips and q3 2 data.mat under ./data.
We recommend using virtual environment for the project. If you choose not to use a virtual environment,
it is up to you to make sure that all dependencies for the code are installed globally on your machine. To set
up a virtual environment, run the following in the command-line innterface:
cd your_hw3_folder
sudo pip install virtualenv # This may already be installed
virtualenv .env # Create a virtual environment
source .env/bin/activate # Activate the virtual environment
pip install -r requirements.txt # Install dependencies
# Note that this does NOT install TensorFlow or PyTorch,
# which you need to do yourself.
# Work on the assignment for a while …
# … and when you’re done:
deactivate # Exit the virtual environment
Note that every time you want to work on the assignment, you should run ’source .env/bin/activate’ (from
within your hw3 folder) to re-activate the virtual environment, and deactivate again whenever you are done.
3 What to submit?
3.1 Blackboard submission
For question 1, please put everything in one single pdf file and submit it on Blackboard, please include
your name and student ID in the first page of the pdf file. For question 2, submit the jupyter notebook files
Action CNN.ipynb with your answers filled at the ’To Do’ spots. Put the pdf file and your jupyter notebook
file in a folder named: SUBID FirstName LastName (e.g., 10947XXXX heeyoung kwon). Zip this folder and
submit the zip file on Blackboard. Your submission must be a zip file, i.e, SUBID FirstName LastName.zip.
3.2 Kaggle submission
For Question 2, you must submit a .csv file to for each Kaggle competition to get the Categorization Accuracy. A submission file should contain two columns: Id and Class. The file should contain a header and have
the following format.
Id, Class
0, 3
1, 7
2, 2
… …
A sample submission file is available from the competition site and our handout. You MUST use your Stony
Brook CS email account to submit. A submission file can be automatically generated by predict on test()
and predict on test 3d()in Action CNN.ipynb.
3
4 Cheating warnings
Don’t cheat. You must do the homework yourself, otherwise you won’t learn. You must use your real name
to register on Kaggle. Do not create multiple accounts to bypass the submission limitation per 24 hours.
Doing so will be considered cheating.
4
