Level 1 — RecognitionTree-Based & Instance Methods

Tree-Based & Instance Methods

⏱ 20 minutes30 marksprintable — key stays hidden on paper

Level 1: Recognition

Time limit: 20 minutes Total marks: 30

Section A — Multiple Choice (1 mark each)

Choose the single best answer.

Q1. In a decision tree, the topmost node that contains the entire dataset is called the: (a) Leaf node (b) Root node (c) Internal node (d) Branch [1]

Q2. The entropy of a node that contains only samples of a single class is: (a) 1 (b) 0.5 (c) 0 (d) $\log_2 n$ [1]

Q3. Gini impurity for a binary node with class probabilities $p$ and $1-p$ is given by: (a) $-p\log_2 p - (1-p)\log_2(1-p)$ (b) $1 - p^2 - (1-p)^2$ (c) $p(1-p)$ (d) $1 - \max(p, 1-p)$ [1]

Q4. Bagging primarily reduces which component of model error? (a) Bias (b) Variance (c) Irreducible error (d) Both bias and variance equally [1]

Q5. In a Random Forest, in addition to bootstrap sampling of rows, each split considers: (a) All features (b) A random subset of features (c) Only the most important feature (d) Features chosen by the user manually [1]

Q6. Out-of-bag (OOB) samples for a given tree are: (a) The samples used to train that tree (b) The samples not selected in that tree's bootstrap sample (c) A separate test set held out before training (d) The misclassified samples [1]

Q7. AdaBoost, after each iteration, updates the training data by: (a) Removing correctly classified points (b) Increasing weights on misclassified points (c) Adding new synthetic points (d) Decreasing the learning rate [1]

Q8. Gradient Boosting builds each new tree to fit the: (a) Original labels (b) Residuals / negative gradient of the loss (c) Bootstrap sample (d) OOB error [1]

Q9. The Manhattan distance between $(1,2)$ and $(4,6)$ is: (a) 5 (b) 7 (c) 25 (d) 12 [1]

Q10. The "curse of dimensionality" makes KNN less effective because in high dimensions: (a) Distances become very small (b) All points become roughly equidistant (c) The value of K must be reduced (d) Euclidean distance is undefined [1]

Section B — Matching (1 mark each)

Q11–Q15. Match each term in Column A with the correct description in Column B. [5]

Column A		Column B
11. Pre-pruning		(P) Feature bagging + row bagging of trees
12. Feature importance		(Q) Stops tree growth early (e.g., max depth)
13. Random Forest		(R) Total impurity decrease attributed to a feature
14. Cosine distance		(S) Sequentially corrects errors of previous models
15. Boosting		(T) Based on angle between vectors, ignores magnitude

Section C — True/False with Justification (2 marks each)

State True or False (1 mark) and give a one-line justification (1 mark).

Q16. A fully grown, unpruned decision tree tends to overfit the training data. [2]

Q17. Increasing K in KNN always increases model variance. [2]

Q18. In XGBoost, the learning rate (eta) and number of trees are independent tuning knobs with no interaction. [2]

Q19. Information gain is computed as parent entropy minus the weighted average entropy of the child nodes. [2]

Q20. LightGBM grows trees leaf-wise (best-first) rather than level-wise. [2]

End of paper

Answer keyMark scheme & solutions

Section A (1 mark each)

Q1. (b) Root node. The root holds the full dataset before any split. [1]

Q2. (c) 0. A pure node has $p=1$ , and $-1\log_2 1 = 0$ ; no uncertainty. [1]

Q3. (b) $1 - p^2 - (1-p)^2$ . Gini $= 1 - \sum p_i^2$ . (Note: this equals $2p(1-p)$ , but option (c) omits the factor 2.) [1]

Q4. (b) Variance. Averaging many high-variance trees reduces variance while leaving bias roughly unchanged. [1]

Q5. (b) A random subset of features. Feature subsampling at each split decorrelates trees. [1]

Q6. (b) Samples not selected in that tree's bootstrap sample. ~37% of samples are OOB for each tree. [1]

Q7. (b) Increasing weights on misclassified points. This forces later weak learners to focus on hard cases. [1]

Q8. (b) Residuals / negative gradient of the loss. Each stage fits pseudo-residuals to reduce loss. [1]

Q9. (b) 7. $|4-1| + |6-2| = 3 + 4 = 7$ . [1]

Q10. (b) All points become roughly equidistant. Distance concentration undermines nearest-neighbor discrimination. [1]

Section B (1 mark each)

Q11 → Q (Pre-pruning stops growth early) Q12 → R (importance = total impurity decrease) Q13 → P (feature + row bagging) Q14 → T (angle-based, magnitude-invariant) Q15 → S (sequential error correction) [5 total]

Section C (2 marks each: 1 answer + 1 justification)

Q16. True. Unpruned trees keep splitting until leaves are pure, memorizing noise → high variance/overfit. [2]

Q17. False. Larger K averages more neighbors, smoothing the boundary → lower variance (higher bias). [2]

Q18. False. They interact: smaller eta needs more trees to reach the same fit; they must be tuned together. [2]

Q19. True. $IG = H(\text{parent}) - \sum_k \frac{n_k}{n} H(\text{child}_k)$ , exactly parent minus weighted child entropy. [2]

Q20. True. LightGBM uses leaf-wise (best-first) growth, splitting the leaf with max loss reduction, unlike level-wise trees. [2]

[
  {"claim":"Manhattan distance between (1,2) and (4,6) is 7","code":"result = (abs(4-1)+abs(6-2))==7"},
  {"claim":"Entropy of a pure node (p=1) is 0","code":"import sympy as sp; p=sp.Integer(1); H=-p*sp.log(p,2); result = sp.simplify(H)==0"},
  {"claim":"Gini for binary node 1-p^2-(1-p)^2 equals 2p(1-p)","code":"import sympy as sp; p=sp.symbols('p'); result = sp.simplify((1-p**2-(1-p)**2)-2*p*(1-p))==0"},
  {"claim":"Information gain example: parent entropy 1, two equal children with entropies 0.72 and 0 gives IG=0.64","code":"IG = 1 - (0.5*0.72 + 0.5*0.0); result = abs(IG-0.64)<1e-9"}
]