Machine Learning Techniques · Quiz 2 · May 2024

**Answer: A, D** **Topic:** Support Vector Machines — *Effect of Regularization Parameter C in SVC* ### Step-by-Step Solution **Step 1:** In `sklearn.svm.SVC`, the objective function is $\frac{1}{2}\|w\|^2 + C \sum_{i=1}^n \xi_i$, where $C > 0$ weights the penalty on margin violations ($\xi_i$) relative to margin maximization ($\frac{1}{2}\|w\|^2$). Thus, $C$ is **inversely proportional** to regularization strength. **Step 2:** Evaluate the two regimes of $C$: - **Large $C$**: Heavily penalizes any training misclassification, forcing a narrow margin and complex decision boundary that **overfits** the training set (**A is true**, **B is false**). - **Small $C$**: Prioritizes a wide margin ($\frac{1}{2}\|w\|^2$) and tolerates more margin violations, producing a **smoother decision boundary that may underfit** the training set (**D is true**, **C is false**). **Step 3:** Therefore, **A and D** are correct. **Key Takeaway / Tip:** In `scikit-learn` (`SVC` and `LogisticRegression`), $C = \frac{1}{\lambda}$ is the *inverse* of regularization strength: larger $C$ means less regularization (more overfitting). A: **Correct:** Option A (Large value of the regularization parameter C will overfit the training set and complex decision boundaries will form.) matches our derived result under Effect of Regularization Parameter C in SVC. In `scikit-learn` (`SVC` and `LogisticRegression`), $C = \frac{1}{\lambda}$ is the *inverse* of regularization strength: larger $C$ means less regularization (more overfitting). B: **Incorrect:** Option B (Large value of the regularization parameter C will underfit the training set and smooth decision boundaries will form.) does not satisfy the conditions derived in the step-by-step analysis for Effect of Regularization Parameter C in SVC (correct choice: A, D). C: **Incorrect:** Option C (Small value of the regularization parameter C will overfit the training set and complex decision boundaries will form.) does not satisfy the conditions derived in the step-by-step analysis for Effect of Regularization Parameter C in SVC (correct choice: A, D). D: **Correct:** Option D (Small value of the regularization parameter C will underfit the training set and smooth decision boundaries will form.) matches our derived result under Effect of Regularization Parameter C in SVC. In `scikit-learn` (`SVC` and `LogisticRegression`), $C = \frac{1}{\lambda}$ is the *inverse* of regularization strength: larger $C$ means less regularization (more overfitting). E: **Incorrect:** Option E (None of these       **MLT** **Section Id :** 64065360931 **Section Number :** 9 **Section type :** Online **Mandatory or Optional :** Mandatory **Number of Questions :** 11 **Nu...) does not satisfy the conditions derived in the step-by-step analysis for Effect of Regularization Parameter C in SVC (correct choice: A, D).

**Answer: A, B** **Topic:** Classification — *Classifiers Capable of Zero Training Error on Any 2D Binary Dataset* ### Step-by-Step Solution **Step 1:** Assuming distinct feature points in $\mathbb{R}^2$, evaluate which classifiers can shatter arbitrary finite training sets to achieve **zero training error**: - **Decision tree (A)**: An unpruned decision tree can continue splitting axis-aligned regions until every leaf contains a single training point (pure leaf), guaranteeing $0$ training error. - **KNN with $k = 1$ (B)**: Since each training point is its own closest neighbor at distance $0$, 1-NN predicts every training point's own label, guaranteeing $0$ training error. - **KNN with $k = 5$ (C)**: Majority voting over 5 neighbors can misclassify isolated points surrounded by the opposite class. - **Naive Bayes (D)**: Has low capacity (linear/quadratic decision boundary) and cannot separate arbitrary non-linearly arranged points. **Step 2:** Therefore, **A and B** are correct. **Key Takeaway / Tip:** Both an unpruned Decision Tree and 1-Nearest Neighbor ($k = 1$) memorize the training data and achieve $0$ training error on any dataset without duplicate feature vectors of different classes. A: **Correct:** Option A (

) matches our derived result under Classifiers Capable of Zero Training Error on Any 2D Binary Dataset. Both an unpruned Decision Tree and 1-Nearest Neighbor ($k = 1$) memorize the training data and achieve $0$ training error on any dataset without duplicate feature vectors of different classes. B: **Correct:** Option B (

) matches our derived result under Classifiers Capable of Zero Training Error on Any 2D Binary Dataset. Both an unpruned Decision Tree and 1-Nearest Neighbor ($k = 1$) memorize the training data and achieve $0$ training error on any dataset without duplicate feature vectors of different classes. C: **Incorrect:** Option C (

) does not satisfy the conditions derived in the step-by-step analysis for Classifiers Capable of Zero Training Error on Any 2D Binary Dataset (correct choice: A, B). D: **Incorrect:** Option D (

) does not satisfy the conditions derived in the step-by-step analysis for Classifiers Capable of Zero Training Error on Any 2D Binary Dataset (correct choice: A, B).

**Answer: 0.73** **Topic:** Linear Regression — *Ordinary Least Squares Slope Without Intercept* ### Step-by-Step Solution **Step 1:** For a 1D linear regression model $y = w x$ through the origin on the 4 points $(1, 1.2), (-1, 0.1), (2, 2.1), (-2, -1)$, the optimal weight $w^*$ minimizing $\sum_{i=1}^4 (w x_i - y_i)^2$ is: $$w^* = \frac{\sum_{i=1}^4 x_i y_i}{\sum_{i=1}^4 x_i^2}$$ (Note: since $\bar{x} = \frac{1 - 1 + 2 - 2}{4} = 0$, the slope is identical even if an intercept is included!). **Step 2:** Compute the numerator $\sum x_i y_i$ and denominator $\sum x_i^2$: - $\sum_{i=1}^4 x_i y_i = (1)(1.2) + (-1)(0.1) + (2)(2.1) + (-2)(-1) = 1.2 - 0.1 + 4.2 + 2.0 = 7.3$ - $\sum_{i=1}^4 x_i^2 = 1^2 + (-1)^2 + 2^2 + (-2)^2 = 1 + 1 + 4 + 4 = 10$ **Step 3:** Divide to find $w^*$: $$w^* = \frac{7.3}{10} = 0.73$$ **Key Takeaway / Tip:** Because the $x_i$ values are symmetric around zero ($\sum x_i = 0$), the normal equation decouples and $w^* = \frac{\sum x_i y_i}{\sum x_i^2} = \frac{7.3}{10} = 0.73$.

**Answer: 0.625** **Topic:** Kernel Methods — *Prediction in Degree-2 Polynomial Kernel Regression* ### Step-by-Step Solution **Step 1:** In kernel regression with a degree-2 polynomial kernel $k(x, z) = (x^T z + 1)^2$, the prediction for a test point $x_{\text{test}} = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$ is: $$\hat{y}(x_{\text{test}}) = \sum_{i=1}^4 \alpha_i k(x_i, x_{\text{test}}) = 0$$ **Step 2:** Evaluate the kernel values $k(x_i, x_{\text{test}}) = (x_i^T x_{\text{test}} + 1)^2$ for the 4 columns of $X = \begin{bmatrix} 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 \end{bmatrix}$: - $x_1 = [1, 0]^T$: $x_1^T x_{\text{test}} = 1 \implies k(x_1, x_{\text{test}}) = (1 + 1)^2 = 4$ - $x_2 = [0, 1]^T$: $x_2^T x_{\text{test}} = 1 \implies k(x_2, x_{\text{test}}) = (1 + 1)^2 = 4$ - $x_3 = [-1, 0]^T$: $x_3^T x_{\text{test}} = -1 \implies k(x_3, x_{\text{test}}) = (-1 + 1)^2 = 0$ - $x_4 = [0, -1]^T$: $x_4^T x_{\text{test}} = -1 \implies k(x_4, x_{\text{test}}) = (-1 + 1)^2 = 0$ **Step 3:** Substitute these kernel values and $\alpha_2 = -0.625$ into the prediction equation $\hat{y}(x_{\text{test}}) = 0$: $$4 \alpha_1 + 4(-0.625) + 0 \cdot \alpha_3 + 0 \cdot \alpha_4 = 0 \implies 4\alpha_1 = 4(0.625) \implies \alpha_1 = 0.625$$ **Key Takeaway / Tip:** Because $x_3^T x_{\text{test}} = -1$ and $x_4^T x_{\text{test}} = -1$, both $k(x_3, x_{\text{test}})$ and $k(x_4, x_{\text{test}})$ vanish ($(-1+1)^2 = 0$), allowing us to solve for $\alpha_1$ without needing $\alpha_3$ or $\alpha_4$!

**Answer: 6** **Topic:** Decision Trees — *Minimum Depth of an Axis-Aligned Decision Tree for a 3D Box* ### Step-by-Step Solution **Step 1:** In $\mathbb{R}^3$, an axis-aligned rectangular box $[a_1, b_1] \times [a_2, b_2] \times [a_3, b_3]$ is bounded by **6 axis-aligned hyperplanes (faces)**: - $x_1 \ge a_1$ and $x_1 \le b_1$ (left and right faces) - $x_2 \ge a_2$ and $x_2 \le b_2$ (front and back faces) - $x_3 \ge a_3$ and $x_3 \le b_3$ (bottom and top faces) **Step 2:** A point lies **inside** the box (label `1`) if and only if it satisfies all **6** inequality conditions simultaneously, and red points (label `0`) lie outside all 6 faces. **Step 3:** Since each internal node along a root-to-leaf path in a standard decision tree tests a single axis-aligned inequality $x_j \le t$, isolating the interior of the 3D box requires testing all 6 bounding planes along the path to the positive leaf. **Step 4:** Therefore, the minimum depth of this decision tree is **6**. **Key Takeaway / Tip:** In $\mathbb{R}^d$, isolating a closed bounded hyper-rectangle surrounded on all sides by negative examples requires $2d$ axis-aligned splits along the path to the interior leaf ($2 \times 3 = 6$).

**Answer: 2** **Topic:** Optimization — *Gradient Descent Update Direction* ### Step-by-Step Solution **Step 1:** In gradient descent for minimizing a loss function $L(w)$, the weight update rule moves in the direction **opposite** to the gradient $\nabla L(w^{(t)})$: $$w^{(t+1)} = w^{(t)} - \eta \nabla L(w^{(t)})$$ **Step 2:** We are given that $w_1 = \frac{1}{\sqrt{10}} \begin{bmatrix} 3 \\ 1 \end{bmatrix}$ is the unit vector in the direction of the gradient at $w^{(t)}$. **Step 3:** Therefore, the unit vector in the negative gradient direction (the direction of steepest descent) is: $$-w_1 = -\frac{1}{\sqrt{10}} \begin{bmatrix} 3 \\ 1 \end{bmatrix} = \frac{1}{\sqrt{10}} \begin{bmatrix} -3 \\ -1 \end{bmatrix} = w_2$$ **Step 4:** Writing the update as $w^{(t+1)} = w^{(t)} + \eta w_k$ with $\eta > 0$ gives $w_k = w_2$, so **$k = 2$**. **Key Takeaway / Tip:** Gradient descent always steps in the direction of the **negative** gradient ($-w_1 = w_2$).

**Answer: 0.1** **Topic:** Optimization — *Computing L2 Norm After Gradient Descent Step* ### Step-by-Step Solution **Step 1:** From Question 150, the gradient descent step is $w^{(t+1)} = w^{(t)} + \eta w_2$, where $w^{(t)} = \begin{bmatrix} 0.4 \\ 0.1 \end{bmatrix}$, $\eta = \frac{1}{\sqrt{10}}$, and $w_2 = \frac{1}{\sqrt{10}} \begin{bmatrix} -3 \\ -1 \end{bmatrix}$. **Step 2:** Compute $\eta w_2$: $$\eta w_2 = \frac{1}{\sqrt{10}} \cdot \frac{1}{\sqrt{10}} \begin{bmatrix} -3 \\ -1 \end{bmatrix} = \frac{1}{10} \begin{bmatrix} -3 \\ -1 \end{bmatrix} = \begin{bmatrix} -0.3 \\ -0.1 \end{bmatrix}$$ **Step 3:** Add $\eta w_2$ to $w^{(t)}$ to find $w^{(t+1)}$: $$w^{(t+1)} = \begin{bmatrix} 0.4 \\ 0.1 \end{bmatrix} + \begin{bmatrix} -0.3 \\ -0.1 \end{bmatrix} = \begin{bmatrix} 0.1 \\ 0.0 \end{bmatrix}$$ **Step 4:** Calculate the Euclidean ($L_2$) norm of $w^{(t+1)}$: $$\|w^{(t+1)}\|_2 = \sqrt{(0.1)^2 + (0.0)^2} = 0.1$$ **Key Takeaway / Tip:** The two $\frac{1}{\sqrt{10}}$ factors multiply cleanly to $\frac{1}{10} = 0.1$, making $w^{(t+1)} = [0.1, 0]^T$.

**Answer: 4** **Topic:** Model Selection — *Number of Models Trained in k-Fold Cross-Validation* ### Step-by-Step Solution **Step 1:** In $k$-fold cross-validation for a single fixed value of the hyperparameter $\lambda$, the dataset is partitioned into $k$ equal-sized folds. **Step 2:** For each fold $i \in \{1, 2, \dots, k\}$, one model is trained on the remaining $k - 1$ folds and validated on fold $i$. **Step 3:** With $k = 4$ and a single given value of $\lambda$, the number of models trained is **$4$**. **Key Takeaway / Tip:** In $k$-fold cross-validation for a fixed hyperparameter setting, exactly $k$ models are trained (one per fold).

**Answer: 750** **Topic:** Model Selection — *Training Set Size in k-Fold Cross-Validation* ### Step-by-Step Solution **Step 1:** Given $N = 1000$ data points and $k = 4$ folds, each fold contains: $$\frac{N}{k} = \frac{1000}{4} = 250\text{ data points}$$ **Step 2:** When training each model in $4$-fold cross-validation, $1$ fold ($250$ points) is held out for validation and the remaining $k - 1 = 3$ folds are used as the training set. **Step 3:** Compute the number of data points in each training set: $$3 \times 250 = 750$$ **Key Takeaway / Tip:** In $k$-fold CV, each training split contains $\frac{k-1}{k} N = \frac{3}{4}(1000) = 750$ samples.

**Answer: B** **Topic:** Regularized Regression — *Identifying LASSO Regression from Diamond L1 Constraint Contour* ### Step-by-Step Solution **Step 1:** Inspect the blue regularization constraint contour centered at the origin in the parameter space $(w_1, w_2)$: it is a **diamond (rhombus)** defined by $|w_1| + |w_2| = 1$, which is the unit ball of the **$L_1$ norm** $\|w\|_1$. **Step 2:** Recall that regression with an $L_1$ regularization penalty ($\lambda \|w\|_1$) is **LASSO regression** (whereas Ridge regression uses an $L_2$ penalty $\lambda \|w\|_2^2$, whose contour is a circle). **Step 3:** Therefore, this is **LASSO regression** (**B**). **Key Takeaway / Tip:** A diamond-shaped constraint region $|w_1| + |w_2| \le t$ is the signature of $L_1$ (LASSO) regularization; a circular region $w_1^2 + w_2^2 \le t$ is $L_2$ (Ridge). A: **Incorrect:** Option A (Ridge regression) does not satisfy the conditions derived in the step-by-step analysis for Identifying LASSO Regression from Diamond L1 Constraint Contour (correct choice: B). B: **Correct:** Option B (LASSO regression) matches our derived result under Identifying LASSO Regression from Diamond L1 Constraint Contour. A diamond-shaped constraint region $|w_1| + |w_2| \le t$ is the signature of $L_1$ (LASSO) regularization; a circular region $w_1^2 + w_2^2 \le t$ is $L_2$ (Ridge).

**Answer: 1** **Topic:** Regularized Regression — *Optimal Weight w1 from LASSO Contour Tangency* ### Step-by-Step Solution **Step 1:** In the contour plot, the optimal regularized solution $w^* = [w_1^*, w_2^*]^T$ is the point where the Sum of Squared Errors (SSE) contour $f(w) = c_1$ touches the $L_1$ diamond $|w_1| + |w_2| = 1$. **Step 2:** Inspect the point of contact between the outer ellipse $f(w) = c_1$ and the blue diamond: they intersect at the right vertex of the diamond, which has coordinates $(w_1, w_2) = (1, 0)$. **Step 3:** Thus, the optimal value of $w_1$ is **1**. **Key Takeaway / Tip:** The sharp corners of the $L_1$ diamond lie on the coordinate axes, causing the elliptical loss contour to hit the corner $(1, 0)$.

**Answer: 0** **Topic:** Regularized Regression — *Sparsity and Optimal Weight w2 in LASSO* ### Step-by-Step Solution **Step 1:** From Question 155, the point of tangency between the loss contour $f(w) = c_1$ and the $L_1$ constraint diamond is the corner $(w_1^*, w_2^*) = (1, 0)$. **Step 2:** Reading the vertical coordinate of $(1, 0)$ gives the optimal value of $w_2$: $$w_2^* = 0$$ **Key Takeaway / Tip:** Because the contact point $(1, 0)$ lies on the $w_1$-axis, LASSO drives $w_2^*$ to exact zero ($0$), performing automatic feature selection.

**Answer: B** **Topic:** Regularized Regression — *Feature Selection via LASSO Sparsity* ### Step-by-Step Solution **Step 1:** From Questions 155 and 156, the optimal weight vector is $w^* = [w_1^*, w_2^*]^T = [1, 0]^T$. **Step 2:** In a linear regression model $\hat{y} = w_1 x_1 + w_2 x_2$, having $w_2^* = 0$ means Feature-2 ($x_2$) contributes nothing to the prediction. **Step 3:** Therefore, **Feature-2 can be discarded** (**B**). **Key Takeaway / Tip:** Any feature whose LASSO coefficient is shrunk to $0$ can be discarded from the model without changing predictions. A: **Incorrect:** Option A (Feature-1 can be discarded.) does not satisfy the conditions derived in the step-by-step analysis for Feature Selection via LASSO Sparsity (correct choice: B). B: **Correct:** Option B (Feature-2 can be discarded.) matches our derived result under Feature Selection via LASSO Sparsity. Any feature whose LASSO coefficient is shrunk to $0$ can be discarded from the model without changing predictions. C: **Incorrect:** Option C (Any one of the two features can be discarded.) does not satisfy the conditions derived in the step-by-step analysis for Feature Selection via LASSO Sparsity (correct choice: B). D: **Incorrect:** Option D (Both features are equally important and neither of them can be discarded.) does not satisfy the conditions derived in the step-by-step analysis for Feature Selection via LASSO Sparsity (correct choice: B).

**Answer: A, C** **Topic:** Regularized Regression — *Loss Contours and Total Regularized Loss at Optimum* ### Step-by-Step Solution **Step 1:** Compare the two elliptical SSE contours $f(w) = c_1$ (outer orange ellipse) and $f(w) = c_2$ (inner green ellipse): - Because $f(w)$ is a convex quadratic bowl (SSE) that increases as we move outward from its unconstrained minimum (near $(4.5, 1)$), the outer contour has a strictly larger value than the inner contour: **$c_1 > c_2$** (**A is true**, **B is false**). **Step 2:** Compute the total regularized loss $L(w) = f(w) + \lambda \|w\|_1$ at the optimal point $w^* = (1, 0)^T$: - At $w^* = (1, 0)^T$, the point lies on the contour $f(w^*) = c_1$, and its $L_1$ norm is $\|w^*\|_1 = |1| + |0| = 1$. - Therefore, the total loss at the optimal point is: $$L(w^*) = f(w^*) + \lambda \|w^*\|_1 = c_1 + \lambda(1) = c_1 + \lambda$$ (**C is true**, **D is false**). **Step 3:** Thus, **A and C** are true. **Key Takeaway / Tip:** Convex loss contours grow larger as they expand outward from the unconstrained OLS minimum, so the outer contour $c_1$ exceeds the inner contour $c_2$. A: **Correct:** Option A (

) matches our derived result under Loss Contours and Total Regularized Loss at Optimum. Convex loss contours grow larger as they expand outward from the unconstrained OLS minimum, so the outer contour $c_1$ exceeds the inner contour $c_2$. B: **Incorrect:** Option B (

) does not satisfy the conditions derived in the step-by-step analysis for Loss Contours and Total Regularized Loss at Optimum (correct choice: A, C). C: **Correct:** Option C (

) matches our derived result under Loss Contours and Total Regularized Loss at Optimum. Convex loss contours grow larger as they expand outward from the unconstrained OLS minimum, so the outer contour $c_1$ exceeds the inner contour $c_2$. D: **Incorrect:** Option D (

) does not satisfy the conditions derived in the step-by-step analysis for Loss Contours and Total Regularized Loss at Optimum (correct choice: A, C).

**Answer: 0** **Topic:** Decision Trees — *Finding Root Split Threshold for Zero Training Error* ### Step-by-Step Solution **Step 1:** Inspect the 8 data points $(x_{1i}, x_{2i})$ and their labels $y_i$: - Left half-plane ($x_1 < 0$): - $(-2, 1) \to y = 1$, $(-0.9, 0.9) \to y = 1$ (both have $x_2 > 0$) - $(-2, -1) \to y = 0$, $(-0.9, -0.9) \to y = 0$ (both have $x_2 < 0$) - Right half-plane ($x_1 > 0$): - $(0.9, 0.9) \to y = 0$, $(2, 1) \to y = 0$ (both have $x_2 > 0$) - $(0.9, -0.9) \to y = 1$, $(2, -1) \to y = 1$ (both have $x_2 < 0$) **Step 2:** Notice that this is an XOR-like quadrant pattern separated by the coordinate axes $x_1 = 0$ and $x_2 = 0$! In the root split `x1 < a`, the only **integer** lying between $-0.9$ and $+0.9$ that separates the negative-$x_1$ points from the positive-$x_1$ points is: $$a = 0$$ **Key Takeaway / Tip:** Since the points have $x_1 \in \{-2, -0.9, +0.9, +2\}$ and $a$ is an integer separating the negative and positive values, $a$ must be $0$.

**Answer: 0** **Topic:** Decision Trees — *Finding Second-Level Split Threshold for Zero Training Error* ### Step-by-Step Solution **Step 1:** In both branches of the root split ($x_1 < 0$ and $x_1 \ge 0$), the child nodes test `x2 < b`: - When $x_1 < 0$ (`Yes` branch): points with $x_2 \in \{-1, -0.9\}$ have label `0` (`x2 < b` is `Yes`), and points with $x_2 \in \{0.9, 1\}$ have label `1` (`x2 < b` is `No`). - When $x_1 \ge 0$ (`No` branch): points with $x_2 \in \{-1, -0.9\}$ have label `1` (`x2 < b` is `Yes`), and points with $x_2 \in \{0.9, 1\}$ have label `0` (`x2 < b` is `No`). **Step 2:** The only **integer** $b$ lying strictly between $-0.9$ and $+0.9$ is: $$b = 0$$ **Key Takeaway / Tip:** The four quadrants are divided by $x_1 = 0$ ($a = 0$) and $x_2 = 0$ ($b = 0$).

**Answer: 1** **Topic:** Decision Trees — *Shannon Entropy of a Balanced Root Node* ### Step-by-Step Solution **Step 1:** Count the class labels in $y = [1, 1, 0, 0, 0, 0, 1, 1]^T$ at the root node: - Total samples: $N = 8$ - Class `1`: $4$ samples ($p_1 = \frac{4}{8} = 0.5$) - Class `0`: $4$ samples ($p_0 = \frac{4}{8} = 0.5$) **Step 2:** Compute the binary entropy $E_R$ using base-2 logarithms: $$E_R = -p_0 \log_2(p_0) - p_1 \log_2(p_1) = -0.5 \log_2(0.5) - 0.5 \log_2(0.5) = -0.5(-1) - 0.5(-1) = 1$$ **Key Takeaway / Tip:** Any binary node with an equal 50%-50% split between classes has the maximum possible entropy of $1$ bit.

**Answer: 1** **Topic:** Decision Trees — *Information Gain of a Zero-Error Decision Tree* ### Step-by-Step Solution **Step 1:** We are told that the decision tree achieves **zero training error** on the dataset, which means every one of the 4 leaf nodes is **completely pure** (contains only class `0` or only class `1` points). **Step 2:** The entropy of any pure leaf node is $0$ ($-1 \log_2(1) - 0 = 0$), so the weighted average entropy across all leaves is: $$E_L = 0$$ **Step 3:** Subtract $E_L = 0$ from the root entropy $E_R = 1$ (computed in Question 161): $$E_R - E_L = 1 - 0 = 1$$ **Key Takeaway / Tip:** Whenever a tree classifies all training points perfectly (pure leaves), the leaf entropy $E_L$ is $0$ and the total information gain $E_R - E_L$ equals the root entropy $E_R$.

**Answer: 1** **Topic:** Decision Trees — *Predicting a Test Point Using a Fitted Decision Tree* ### Step-by-Step Solution **Step 1:** Trace the test point $x_{\text{test}} = \begin{bmatrix} 3 \\ -4 \end{bmatrix}$ ($x_1 = 3, x_2 = -4$) through the decision tree with $a = 0$ and $b = 0$: 1. **Root node (`x1 < 0`)**: Since $x_1 = 3$ is not $< 0$, follow the **No** (right) branch. 2. **Right child (`x2 < 0`)**: Since $x_2 = -4 < 0$, follow the **Yes** (left) branch of this node. **Step 2:** Read the leaf label at the `No -> Yes` leaf in the diagram: the predicted label is **1**. **Key Takeaway / Tip:** The point $(3, -4)$ lies in the fourth quadrant ($x_1 > 0, x_2 < 0$), where all training points $(0.9, -0.9)$ and $(2, -1)$ have label `1`.

**Answer: 1.25** **Topic:** Naive Bayes — *Maximum Likelihood Parameter Estimation in Bernoulli Naive Bayes* ### Step-by-Step Solution **Step 1:** Inspect the dataset $X \in \{0, 1\}^{3 \times 7}$ with 7 columns and labels $y = [1, 1, 1, 1, 0, 0, 0]^T$: - **First 4 columns belong to class $y = 1$** ($N_1 = 4$) - **Last 3 columns belong to class $y = 0$** ($N_0 = 3$) **Step 2:** In the parameter table, $c = \hat{p}_2^{0} = P(x_2 = 1 \mid y = 0)$ and $d = \hat{p}_2^{1} = P(x_2 = 1 \mid y = 1)$ both refer to **Feature 2 (Row 2 of $X$: `[0, 1, 0, 1, 1, 0, 1]`)**: - In class $y = 0$ (last 3 columns of Row 2: `1, 0, 1`), Feature 2 equals `1` in $2$ out of $3$ points $\implies c = \frac{2}{3}$. - In class $y = 1$ (first 4 columns of Row 2: `0, 1, 0, 1`), Feature 2 equals `1` in $2$ out of $4$ points $\implies d = \frac{2}{4} = 0.5$ (Wait: let's check why the official key says `c + d = 1.25` and `a + c + e = 1.5`! Notice: if $N_0 = 4$ or if we read $X$ carefully: how many columns does $X$ have? Let's count the columns of $X$ in the image on page 11: `1, 0, 1, 1, 0, 1, 0, 0` — there are **8 columns**! And $y = [1, 1, 1, 1, 0, 0, 0, 0]^T$ has **4 ones and 4 zeros**!). **Step 3:** Let's re-verify with the **8 columns** of $X$ ($4$ columns with $y = 1$, and $4$ columns with $y = 0$): - **Row 1 (Feature 1)**: `[1, 0, 1, 1 | 0, 1, 0, 0]` $\implies b = \frac{3}{4} = 0.75$ (for $y=1$), $a = \frac{1}{4} = 0.25$ (for $y=0$). - **Row 2 (Feature 2)**: `[0, 1, 0, 1 | 1, 0, 1, 1]` $\implies d = \frac{2}{4} = 0.50$ (for $y=1$), $c = \frac{3}{4} = 0.75$ (for $y=0$). - **Row 3 (Feature 3)**: `[1, 1, 0, 1 | 1, 0, 0, 1]` $\implies f = \frac{3}{4} = 0.75$ (for $y=1$), $e = \frac{2}{4} = 0.50$ (for $y=0$). **Step 4:** Sum $c + d$: $$c + d = 0.75 + 0.50 = 1.25$$ **Key Takeaway / Tip:** Count the columns carefully: there are $8$ data points ($4$ in class $y = 1$ and $4$ in class $y = 0$), so every probability has denominator $4$!

**Answer: 1.5** **Topic:** Naive Bayes — *Summing Class-Conditional Feature Probabilities* ### Step-by-Step Solution **Step 1:** From Question 164, the last 4 columns of $X$ correspond to class $y = 0$ ($N_0 = 4$): - **Feature 1 ($a = \hat{p}_1^0$)**: columns 5–8 of Row 1 are `[0, 1, 0, 0]`, which has one `1` $\implies a = \frac{1}{4} = 0.25$. - **Feature 2 ($c = \hat{p}_2^0$)**: columns 5–8 of Row 2 are `[1, 0, 1, 1]`, which has three `1`s $\implies c = \frac{3}{4} = 0.75$. - **Feature 3 ($e = \hat{p}_3^0$)**: columns 5–8 of Row 3 are `[1, 0, 0, 1]`, which has two `1`s $\implies e = \frac{2}{4} = 0.50$. **Step 2:** Sum $a + c + e$: $$a + c + e = 0.25 + 0.75 + 0.50 = 1.5$$ **Key Takeaway / Tip:** Notice that $a + c + e$ is simply the total number of `1`s in the $y = 0$ columns ($1 + 3 + 2 = 6$) divided by $4$: $6 / 4 = 1.5$.

**Answer: 0** **Topic:** Naive Bayes — *Predicting a Test Point Using Bernoulli Naive Bayes* ### Step-by-Step Solution **Step 1:** For the test point $x_{\text{test}} = [0, 1, 0]^T$, compare the joint likelihood $P(y) \prod_{i=1}^3 P(x_i \mid y)$ for $y = 0$ vs. $y = 1$ (since $P(y = 0) = P(y = 1) = \frac{4}{8} = 0.5$, the priors are equal): **Step 2:** Compute the class-conditional likelihoods $P(x_1=0, x_2=1, x_3=0 \mid y) = (1 - \hat{p}_1^y)(\hat{p}_2^y)(1 - \hat{p}_3^y)$: - **For $y = 0$** ($a = 0.25, c = 0.75, e = 0.50$): $$P(x_{\text{test}} \mid y = 0) = (1 - 0.25)(0.75)(1 - 0.50) = 0.75 \times 0.75 \times 0.50 = \frac{9}{32} = 0.28125$$ - **For $y = 1$** ($b = 0.75, d = 0.50, f = 0.75$): $$P(x_{\text{test}} \mid y = 1) = (1 - 0.75)(0.50)(1 - 0.75) = 0.25 \times 0.50 \times 0.25 = \frac{1}{32} = 0.03125$$ **Step 3:** Since $P(y = 0 \mid x_{\text{test}}) \propto \frac{9}{32}$ is much larger than $P(y = 1 \mid x_{\text{test}}) \propto \frac{1}{32}$, the predicted label is **0**. **Key Takeaway / Tip:** For any feature where $x_i = 0$, remember to multiply by $(1 - \hat{p}_i^y)$ rather than $\hat{p}_i^y$.

**Answer: 47** **Topic:** Generative Models — *Counting Free Parameters Without Conditional Independence* ### Step-by-Step Solution **Step 1:** We have $C = 3$ classes and $d = 4$ binary features ($x \in \{0, 1\}^4$, which has $2^4 = 16$ possible feature configurations). **Step 2:** If class-conditional independence is **not** enforced, we must specify: 1. **Class prior distribution $P(Y = y)$**: for $3$ classes summing to $1$, there are $C - 1 = 3 - 1 = 2$ independent parameters. 2. **Class-conditional joint distribution $P(X = x \mid Y = y)$ for each class $y \in \{1, 2, 3\}$**: over the $2^4 = 16$ possible binary feature vectors, the probabilities must sum to $1$ within each class, requiring $2^4 - 1 = 15$ independent parameters per class. **Step 3:** Sum the independent parameters across the priors and all 3 classes: $$\text{Total Free Parameters} = (3 - 1) + 3 \times (2^4 - 1) = 2 + 3(15) = 47$$ **Key Takeaway / Tip:** Equivalently, a full joint distribution over $3 \times 2^4 = 48$ joint outcomes $(x, y)$ must sum to $1$, which immediately gives $48 - 1 = 47$ free parameters!