Aggregation
1. Consider an aggregation classifier G constructed by uniform blending on 11 classifiers {g }11 .
That is,
11 G(x) = sign gt(x) .
t=1
Assume that each gt is of test 0/1 error Eout(gt) = et. Which of the following is the tightest upper
bound of Eout(G)? Choose the correct answer; explain your answer. [a]111 et
3 t=1 [b]111 et
4 t=1 [c]111 et
6 t=1 [d] 1 11 et
11 t=1
[e] 1 11 et 12 t=1
1 of 6
t t=1
2. Suppose that each x = (x1, x2) ∈ R2 is drawn uniformly from the region {0≤x1 ≤3,0≤x2 ≤3}
and the target function is f(x) = sign(x2 − x1). Consider blending the following three hypotheses linearly to approximate the target function.
That is,
g1(x) = g2(x) = g3(x) =
sign(x1 − 2) sign(x2 − 1) sign(x2 − 2)
3 G(x)=sign αt·gt(x)
t=1
with αt ∈ R. What is the smallest possible Eout(G)? Choose the correct answer; explain your
answer.
(Hint: The “boundary” of G must be a “combination” of the boundaries of gt)
[a] 6 18
[b] 5 18
[c] 4 18
[d] 3 18
[e] none of the other choices
3. When talking about non-uniform voting in aggregation, we mentioned that α can be viewed as a
weight vector learned from any linear algorithm coupled with the following transform: φ(x) = g1(x), g2(x), · · · , gT (x).
When studying kernel methods, we mentioned that the kernel is simply a computational short-cut for the inner product (φ(x))T (φ(x′)). In this problem, we mix the two topics together using the decision stumps as our gt(x).
Assume that the input vectors contain only even integers between (including) 2L and 2R, where L < R. Consider the decision stumps gs,i,θ(x) = s · signxi − θ, where
i d s θ
∈ {1,2,··· ,d},
is the finite dimensionality of the input space,
∈ {−1, +1},
is an odd integer between (2L, 2R).
Define φds(x) =
Kds(x, x′) = (φds(x))T (φds(x′))? Choose the correct answer; explain your answer.
[a] 2d(R−L)−2∥x−x′∥1 [b] 2d(R−L)2 −2∥x−x′∥21 [c] 2d(R−L)−2∥x−x′∥2 [d] 2d(R−L)2 −2∥x−x′∥2
[e] none of the other choices
. What is
g+1,1,2L+1(x), g+1,1,2L+3(x), . . . , g+1,1,2R−1(x), . . . , g−1,d,2R−1(x)
2 of 6
Adaptive Boosting
4. Consider applying the AdaBoost algorithm on a binary classification data set where 99% of the
examples are positive. Because there are so many positive examples, the base algorithm within
(2) AdaBoost returns a constant classifier g1(x) = +1 in the first iteration. Let un
example weight of each example in the second iteration. What is
(2) n:yn>0un ?
(2) n: yn<0 un
Choose the correct answer; explain your answer.
[a] 99 [b] 1/99
[c] 1 [d] 100
be the individual
[e] 1/100
5. For the AdaBoost algorithm introduced in Lecture 12, let Gt(x) = signtτ=1 gτ(x). How many
of the following are guaranteed to be non-increasing from the t-th iteration to the (t+1)-th iteration? Choose the correct answer; explain each non-increasing case within your answer.
- Ein(Gt) to Ein(Gt+1)
- Eout(Gt) to Eout(Gt+1)
N (t) N (t+1) • n=1un to n=1un
(t)
- un
(t)
- un
- [a] 1
- [b] 2
- [c] 3
- [d] 4
- [e] 5
(t+1) to un
(t+1) to un
when gt is correct on (xn, yn) when gt is incorrect on (xn, yn)
N (t) 1 6. For the AdaBoost algorithm introduced in Lecture 12, let Ut = n=1 un . Assume that 0 < εt < 2
for each hypothesis gt. What is Ut+1 ? Choose the correct answer; explain your answer. Ut
[a] εt(1−εt) [b] 2εt(1−εt)
[c] εt (1−εt )
[d] ln(1−εt) εt
[e] ln εt (1−εt )
3 of 6
7. Following the previous two problems, assume that εt ≤ ε < 21 , which of the following is the tightest upper bound on the number of iterations T required to ensure Ein(GT ) = 0? Choose the correct answer; explain your answer.
(Hint: use the fact that
112 ε(1−ε)≤2exp −2(2−ε)
4( 12 −ε)4
Random Forest = Bagging + Decision Tree
- Suppose we have a data set of size N = 1126, and we use bootstrapping to sample N′ examples. What is the minimum N′ such that the probability of getting at least one duplicated example (with # copies ≥ 2) is larger than 50%? Choose the correct answer; explain your answer.
[a] 25 [b] 30 [c] 35 [d] 40
[e] none of the other choices
- If bootstrapping is used to sample exactly 2N examples out of N, what is the probability that an
example is not sampled when N is very large? Choose the closest answer; explain your answer.
[a] 77.9% [b] 60.7% [c] 36.8% [d] 13.5%
[e] 1.8%
- Suppose we have a set of decision trees. Each tree comes with 2 node, each equipped with a fixed branching function. The root node is of two branches, evaluating whether x1 ≥ 0. If x1 < 0, the node connects to a leaf with some constant output. Otherwise the node connects to another node of two branches, evaluating whether x2 ≥ 0. Each of the branches connects to a constant leaf. Consider three-dimensional input vectors. That is, x = (x1,x2,x3). Which of the following data set can be shattered by the set of decision trees? Choose the correct answer; explain your answer.
[a] (1,1,−1),(−1,1,−1),(−1,−1,−1) [b] (1,1,−1),(−1,1,−1),(1,−1,−1)
[c] (1,1,−1),(−1,1,−1),(1,−1,−1),(−1,−1,−1) [d] (1,1,−1),(−1,1,−1),(1,−1,−1),(−1,−1,1)
[e] none of the other choices
for all 0 < ε < 21 ). [a] lnN
2( 12 −ε) [b] lnN
2( 12 −ε)2 [c] lnN
4( 12 −ε) [d] lnN
4( 12 −ε)2 [e] lnN
4 of 6
Experiments with Adaptive Boosting
For Problems 11-16, implement the AdaBoost-Stump algorithm as introduced in Classes 12 and 13. Run the algorithm on the following set for training:
https://www.csie.ntu.edu.tw/~htlin/course/ml21fall/hw6/hw6_train.dat
and the following set for testing:
https://www.csie.ntu.edu.tw/~htlin/course/ml21fall/hw6/hw6_test.dat
Use a total of T = 500 iterations (please do not stop earlier than 500), and calculate Ein and Eout with the 0/1 error.
For the decision stump algorithm, please implement the following steps. Any ties can be arbitrarily broken.
(1) For any feature i, sort all the xn,i values to x[n],i such that x[n],i ≤ x[n+1],i.
(2) Consider thresholds within −∞ and all the midpoints x[n],i+x[n+1],i . Test those thresholds with
2
s ∈ {−1, +1} to determine the best (s, θ) combination that minimizes Eu using feature i. in
(3) Pick the best (s, i, θ) combination by enumerating over all possible i.
For those interested in algorithms (who isn’t? 🙂 ), step 2 can be carried out in O(N) time only!!
- (*) What is the value of Ein(g1)? Choose the closest answer; provide your code.
[a] 0.29 [b] 0.33 [c] 0.37 [d] 0.41 [e] 0.45
- (*) What is the value of max1≤500≤t Ein(gt)? Choose the closest answer; provide your code.
[a] 0.40 [b] 0.45 [c] 0.50 [d] 0.55 [e] 0.60
- (*) What is the smallest t within the choices below such that min1≤τ≤t Ein(Gτ) ≤ 0.05? Choose the correct answer; provide your code.
[a] 60 [b] 160 [c] 260 [d] 360 [e] 460
- (*) What is the value of Eout(g1)? Choose the closest answer; provide your code.
[a] 0.40 [b] 0.45 [c] 0.50 [d] 0.55 [e] 0.60
5 of 6
Machine Learning (NTU, Fall 2021) instructor: Hsuan-Tien Lin
15. (*) Define Guniform(x) = sign Tt=1 gt(x). What is the value of Eout(Guniform)? Choose the closest answer; provide your code.
[a] 0.23 [b] 0.28 [c] 0.33 [d] 0.38 [e] 0.43
16. (*) What is the value of Eout(G500)? Choose the closest answer; provide your code.
[a] 0.14 [b] 0.18 [c] 0.22 [d] 0.26 [e] 0.30
6 of 6
