DATA7703 Week 7 Tutorial Solutions
2025 Semester 2
1. (a) No. Assume that 𝑤1 > 𝑤2 . From the table below, it is easy to see that for all the
four combinations of 𝑦1 , 𝑦2 ∈ {−1, +1}, the label 𝑦 = sgn(𝑤1 𝑦1 + 𝑤2 𝑦2 ) is always the
same as 𝑦1 .
𝑦1 𝑦2 𝑤1 𝑦1 + 𝑤2 𝑦2 𝑦
-1 -1 −𝑤1 − 𝑤2 -1
-1 1 −𝑤1 + 𝑤2 -1
1 -1 𝑤1 − 𝑤2 1
1 1 𝑤1 + 𝑤2 1
Thus we have 𝑐(𝑥) = sgn(𝑤1 𝑐1 (𝑥) + 𝑤2 𝑐2 (𝑥)) = 𝑐1 (𝑥) for any 𝑥. That is, 𝑐 is the same
as 𝑐1 when 𝑤1 > 𝑤2 . Similarly, 𝑐 is the same as 𝑐2 when 𝑤1 < 𝑤1 . So combining two
classifiers with different positive weights does not lead to a possibly more accurate
classifier.
If 𝑤1 = 𝑤2 , then sgn(𝑤1 𝑦1 + 𝑤2 𝑦2 ) = 0 when 𝑦1 + 𝑦2 = 0. That is, the combined pre-
diction is “uncertain”. While the combined classifier is different from both classifiers
in this case, it is again showing that combining two classifiers with positive weights
does not lead to a possibly more accurate classifier.
(b) The answer depends on whether 𝑐1 and 𝑐2 agree on any example 𝑥. If yes, simply
choose 𝑤1 = −1 and 𝑤2 = −2, then the prediction of 𝑐 on 𝑥 is opposite to those of
𝑐1 and 𝑐2 . If no, then 𝑐1 = −𝑐2 , and using the table in (a), it is easy to see that 𝑐 is
the same as either 𝑐1 or 𝑐2 .
2. (a) For any 𝑎, 𝑏, and any two random variables 𝑈, 𝑉 , we have Var(𝑎𝑈 +𝑏𝑉 ) = 𝑎2 Var(𝑈 )+
𝑏2 Var(𝑉 ) + 2𝑎𝑏 cov(𝑈, 𝑉 ) (verify this using definitions of variance and covariance if
you don’t know this). Hence
(︂ )︂
1 1 1 1 1
Var 𝑋1 + 𝑋2 = Var(𝑋1 ) + Var(𝑋2 ) + cov(𝑋1 , 𝑋2 )
2 2 4 4 2
1 1
= 𝜎 2 + 𝜌𝜎 2
2 2
1+𝜌 2
= 𝜎 .
2
(b) For any 𝑤1 , . . . , 𝑤𝑚 we have
𝑚
∑︁ ∑︁
Var(𝑤1 𝑋1 + . . . + 𝑤𝑚 𝑋𝑚 ) = 𝑤𝑖2 Var(𝑋𝑖 ) + 𝑤𝑖 𝑤𝑗 cov(𝑋𝑖 , 𝑋𝑗 )
𝑖=1 1≤𝑖̸=𝑗≤𝑚
𝑚
∑︁ ∑︁
= 𝑤𝑖2 𝜎 2 + 𝑤𝑖 𝑤𝑗 𝜌𝜎 2
𝑖=1 1≤𝑖̸=𝑗≤𝑚
1
1
When 𝑤1 , . . . , 𝑤𝑚 are all equal to 𝑚
, the last expression above is equal to
𝑚
∑︁ 1 2 ∑︁ 1 1 1
2
𝜎 + 2
𝜌𝜎 2 = 𝜎 2 + 𝑚(𝑚 − 1) 2 𝜌𝜎 2
𝑖=1
𝑚 1≤𝑖̸=𝑗≤𝑚
𝑚 𝑚 𝑚
1−𝜌 2
= 𝜌𝜎 2 + 𝜎 .
𝑚
3. (𝑥1 , 0) is an OOB observation for Tree 2 only, thus its OOB prediction is the one given
by Tree 2, that is, 1. Similarly, the OOB predictions for (𝑥2 , 1), (𝑥3 , 1), (𝑥4 , 0) are 1, 1,
1 respectively. Two out of the 4 OOB predictions are incorrect. Thus the OOB error is
2/4 = 0.5.
4. (a) No. All the models are built using bootstrap samples from the same dataset, and
thus they are correlated.
(b) No. Each time we construct a new model, the model is trained on a weighted training
set with weight determined by the predictions of the current ensemble. Thus a new
model depends on previous models, and is not independent of existing models.
(c) RF and bagging with DTs differs only in how a decision is trained on a bootstrap
sample. In bagging, the splitting variable at each node in a decision tree is chosen
from all 𝑑 features. In RF, the splitting variable at each node is chosen from 𝑚 < 𝑑
randomly chosen features — note that the random subset is separately sampled for
each node.
5. When 𝛾𝑡 ≥ 𝛾 > 0 for all 𝑡, the error rate of 𝐹𝑇 on the training set is upper bounded by
𝑇 √︀ 𝑇
2 2
∏︁ ∏︁ √︀
2
1 − 4𝛾𝑡 ≤ 1 − 4𝛾 2 = (1 − 4𝛾 2 )𝑇 /2 < 𝑒−4𝛾 ·𝑇 /2 = 𝑒−2𝛾 𝑇 ,
𝑡=1 𝑡=1
where we make use of the inequality 1 − 𝑥 < 𝑒−𝑥 for 𝑥 > 0.
Since there are 𝑛 training examples, an error rate less than 𝑛1 is the same as zero training
2
error. Thus if 𝑒−2𝛾 𝑇 ≤ 𝑛1 , then the training error is zero. Solving the inequality for 𝑇 ,
we have 𝑇 ≥ ln 𝑛
2𝛾 2
. That is, as long as 𝑇 ≥ ln 𝑛
2𝛾 2
, we have zero training error. Equivalently,
ln 𝑛
at most 2𝛾 2 basis models are needed to make the training error zero (more precisely, at
most ln 𝑛
2𝛾 2
− 1 basis models are needed).