CSC546 Homework 3

Description

Part-1: Basic Concepts
1. Classification and Cross-entropy loss
𝑥𝑛 is an input data sample, and it is a vector.
𝑦𝑛 is the ground-truth class label of 𝑥𝑛.
𝑦̂𝑛 is the output “soft-label”/confidence of a logistic regression classifier given the input 𝑥𝑛
𝑛 is from 1 to N
the number of classes is K
(1) write down the formula of binary cross-entropy (K=2), assuming 𝑦𝑛 is an integer
(2) write down the formula of cross-entropy (K≥2), assuming 𝑦𝑛 is a one-hot vector.
(3) Assume there are only two classes: class-0, class-1, and the data point 𝑥𝑛 is in class-1 (𝑦𝑛 = 1)
Assume the output is 𝑦̂𝑛 = 0.8 from a binary logistic regression classifier
Compute the binary cross-entropy loss associated with the single data sample 𝑥𝑛
note: show the steps
(4) Assume there are three classes: class-0, class-1 and class-2, and the data point 𝑥𝑛 is in class-2 (𝑦𝑛 = 2).
Assume the output is 𝑦̂𝑛 = [0.1, 0.2, 0.7]
𝑇
from a multi-class logistic regression classifier
Do one-hot-encoding on 𝑦𝑛, and then Compute the cross-entropy loss associated with the single data sample 𝑥𝑛
note: show the steps
(5) Show that the function 𝑓(𝑥) = −𝑙𝑜𝑔 (
1
1+𝑒−𝑥
) is convex in 𝑥. 𝑙𝑜𝑔 is the natural log
Here is a plot of the function, and it seems that the function is convex.
Hint: show that 𝜕
2𝑓
𝜕𝑥
2 ≥ 0 then it is convex. This explains why cross entropy loss is convex.
The concept of cross entropy is from information theory
2. Regression
𝑥𝑛 is an input data sample, and it is a vector.
M is the number of elements/features in 𝑥𝑛.
𝑦𝑛 is the ground-truth
𝑦𝑛 is a vector that has two elements [𝑦𝑛,1
, 𝑦𝑛,2
]. For example, 𝑦𝑛,1
is income, and 𝑦𝑛,2
is age, given input image 𝑥𝑛
𝑦̂𝑛 is the output of a regressor (e.g., linear regressor) given the input 𝑥𝑛
𝑛 is from 1 to N
(1) write down the formula of MSE loss
(2) write down the formula of MAE loss
(3) write down the formula of MAPE loss
3. Decision Tree
A decision tree is a partition of the input space.
Every leaf node of the tree corresponds to a region of the final partition of the input space.
(1) The output of a decision tree for regression looks like a staircase. Why?
(2) Is it a good strategy to build a deep tree such that every leaf-node of the tree is a pure node?
(3)~(6) are related to the tree below
(3) What is the total number of training samples according to the above tree?
(4) What is the max-depth of the tree?
(5) How many ‘pure’ nodes (entropy =0) does this tree have? What is the entropy on Node-0?
(6) How many leaf/terminal nodes?
4. Bagging and Random Forest
(1) Under what condition will Bagging work?
(2) Random-forest uses a strategy to reduce the correlation between trees. What is the strategy?
5. Boosting
What is the difference between boosting (e.g., XGBoost) and bagging (e.g., Random-forest) from the perspective of
variance and bias?
6. Stacking
(1) What is the difference between stacking and bagging?
(2) Could it be useful to stack many polynomial models of the same degree?
(3) Could it be useful to stack models of different types/structures?
7. Overfitting and Underfitting
It is easy to understand Overfitting and Underfitting, but it is hard to detect them.
Consider two scenarios in a classification task:
(1) the training accuracy is 100% and the testing accuracy is 50%
(2) the training accuracy is 80% and the testing accuracy is 70%
In which scenario is overfitting likely present?
Consider two new scenarios in a classification task:
(1) the training accuracy is 80% and the testing accuracy is 70%
(2) the training accuracy is 50% and the testing accuracy is 50%
In which scenario is underfitting likely present?
Keep in mind that, in real applications, the numbers in different scenarios may be very similar.
We can always increase model complexity to avoid underfitting.
We need to find the model with the “right” complexity (i.e., the best hyper-parameters) to reduce overfitting if possible.
8. Training, Validation, and Testing for Classification and Regression
(1) What are hyper-parameters of a model? Give some examples.
(2) Why do we need a validation set?
(3) Why don’t we just find the optimal hyper-parameters on the training set? e.g., find the model that performs the best
on the training set.
(4) Why don’t we optimize hyper-parameters using the testing set?
Terminologies: training(train) set(dataset), testing(test) set(dataset), validation (val) set(dataset)
9. SVM
(1) Why maximizing the margin in the input space will improve classifier robustness against noises?
(2) Will the margin in the input space be maximized by a nonlinear SVM?
(3) Why could SVM cause “out-of-memory” error for a large dataset?
(4) What is the purpose of using a kernel function?
10. Handle class-imbalance
We have a class-imbalanced dataset, and the task is to build a classifier on this dataset. From the perspective of PDF,
there are two types/scenarios of class-imbalance (see lecture notes). Now, assume we are in scenario-1.
(1) Why do we use weighted-accuracy to measure the performance of a classifier? i.e., What is the problem of the
standard accuracy?
(2) When class-weight is not an option for a classifier, what other options do we have to handle class-imbalance?
11. Entropy
The PMF for a discrete random variable 𝑋 is [𝑝1
, 𝑝2
, 𝑝3
, … 𝑝𝐾] and ∑𝑘 𝑝𝑘 = 1
Write down the entropy and show that:
(1) entropy is non-negative
(2) entropy reaches the maximum when the PMF is a uniform distribution, i.e., 𝑝𝑘 = 1/𝐾
Hint: you can use Jensen’s inequality in Q.12 or Lagrange Multiplier
12. Joint Entropy and Mutual Information
For a pair of discrete random variables 𝑋 and 𝑌 (scalars, not vectors) with the joint distribution 𝑝(𝑥, 𝑦), the joint
entropy 𝐻(𝑋, 𝑌) is defined as
𝐻(𝑋, 𝑌) = −∑∑𝑝(𝑥, 𝑦)𝑙𝑜𝑔(𝑝(𝑥, 𝑦))
𝑥 𝑦
which can also be expressed using mathematical expectation:
𝐻(𝑋, 𝑌) = −𝐸[𝑙𝑜𝑔(𝑝(𝑥, 𝑦))]
The entropy of 𝑋 (PDF is 𝑝(𝑥)) is defined as
𝐻(𝑋) = −∑𝑝(𝑥)𝑙𝑜𝑔(𝑝(𝑥))
𝑥
The entropy of 𝑌 (PDF is 𝑝(𝑦)) is defined as
𝐻(𝑌) = −∑𝑝(𝑦)𝑙𝑜𝑔(𝑝(𝑦))
𝑦
note: 𝑝(𝑥) and 𝑝(𝑦) represent different PDFs.
The mutual information is defined as
𝐼(𝑋, 𝑌) = ∑∑𝑝(𝑥, 𝑦)𝑙𝑜𝑔 (
𝑝(𝑥, 𝑦)
𝑝(𝑥)𝑝(𝑦)
)
𝑥 𝑦
Jensen’s inequality says: 𝐸[𝑓(𝑋)] ≥ 𝑓(𝐸[𝑋]) where 𝑓(𝑥) is a convex function.
Prove that 𝐻(𝑋, 𝑌) ≤ 𝐻(𝑋)+ 𝐻(𝑌)
Hint: show that 𝐼(𝑋, 𝑌) = 𝐻(𝑋)+ 𝐻(𝑌) − 𝐻(𝑋, 𝑌), and then show 𝐼(𝑋, 𝑌) ≥ 0 using Jensen’s inequality.
Part-2: Programming on classification and regression
Read the instructions in H3P2T1.ipynb, H3P2T2.ipynb, H3P2T3.ipynb
Grading: (points for each question/task)
Undergraduate Student Graduate Student
Question 1 5 5
Question 2 2 2
Question 3 6 6
Question 4 2 2
Question 5 2 2
Question 6 2 2
Question 7 2 2
Question 8 3 3
Question 9 3 2
Question 10 3 2
Question 11 Bonus (5 points) 2
Question 12 N.A. Bonus (5 points)
H3P2T1 30 30
H3P2T2 30 30
H3P2T3 10 10
Attention:
If you use test datasets for optimizing any model, you
will get zero score.