Machine Learning Techniques · Quiz 2 · Jan 2024

**Step 1: Analyze the minimum training misclassification rate for \(k\)-NN with \(k = 3\).** We have 80 training points (40 in Class 0 and 40 in Class 1), and each point is considered its own neighbor during classification. If the two classes are well-separated in the feature space (for instance, all 40 points of Class 0 are clustered closely together around one region and all 40 points of Class 1 are clustered around another distant region), then for every training point, its 3 nearest neighbors (itself plus the 2 closest points) will belong to the **same class**. Therefore, the minimum number of misclassifications that can occur on the training dataset is **0**. **Answer: 0**

In the \(k\)-Nearest Neighbors (\(k\)-NN) algorithm: - When \(k\) is very small (e.g., \(k = 1\)), the decision boundary is highly jagged and sensitive to individual noisy points or outliers (forming small isolated islands around outliers). - As \(k\) **increases**, the prediction at any point averages over a larger neighborhood of \(k\) training points, smoothing out the effect of individual outliers and making the **decision boundary smoother**. Since the statement is true, we enter **1** (for yes). **Answer: 1**

Compare the two regression models: - **Model P (Linear)**: \(\hat{y}_i = w_0 + w_1 x\) - **Model Q (Quadratic / Degree-2 Polynomial)**: \(\hat{y}_i = w_0 + w_1 x + w_2 x^2\) Notice that Model P is a **special case** of Model Q (obtained when \(w_2 = 0\)). Because Model Q has strictly higher hypothesis class capacity (an extra degree of freedom \(w_2 x^2\)) and is fit by minimizing MSE on the **training dataset**, Model Q can always achieve a training MSE **less than or equal to** Model P, and is more likely to provide accurate predictions on the **training dataset** by capturing curvature in house prices vs. square footage. **Answer: B (Model Q)** A: **Incorrect:** Model P is a restricted special case of Model Q (\(w_2 = 0\)) and cannot achieve a lower training error than Model Q. B: **Correct:** Model Q includes the quadratic term \(w_2 x^2\), giving it greater flexibility to fit the training data at least as well as (and typically better than) Model P. C: **Incorrect:** A higher-degree polynomial model achieves lower or equal training MSE compared to a nested linear model. D: **Incorrect:** On the training set, the nested superset model Q always achieves less or equal MSE regardless of the distribution.

Let us evaluate each statement regarding the performance of Model P (\(w_0 + w_1 x\)) and Model Q (\(w_0 + w_1 x + w_2 x^2\)) on the training dataset: - **A is correct**: Because Model P is strictly linear in \(x\), it has high bias when the true relationship between square footage and house price is non-linear (struggling to capture non-linear patterns). - **B is correct**: Because Model Q includes the squared feature \(x^2\) and minimizes squared error (MSE), extreme values (outliers) in square footage \(x\) are squared, giving them huge leverage and making Model Q sensitive to outliers. - **C is incorrect**: Statistical model fit on a dataset depends on the data distribution and model complexity, not the personal budget constraints of homebuyers. - **D is incorrect**: A more complex model is never guaranteed to always perform well on unseen test data (it may overfit). **Answer: A, B** A: **Correct:** A simple linear model \(w_0 + w_1 x\) cannot capture non-linear curvature in housing prices. B: **Correct:** Squaring the feature \(x^2\) amplifies extreme square-footage values, making the quadratic fit sensitive to outliers. C: **Incorrect:** Homebuyer budget constraints are external to the mathematical relationship between model complexity and training error. D: **Incorrect:** Higher-order polynomial models can overfit and perform poorly on unseen test data.

**Step 1: Identify the columns of \(X \in \mathbb{R}^{3 \times 4}\) that belong to class \(y = 1\).** Given \(y = [1, 0, 1, 1]^T\), the samples with \(y_i = 1\) are **columns 1, 3, and 4** (a total of \(N_1 = 3\) positive examples): - Column 1 (\(y_1 = 1\)): \([1, 0, 0]^T\) - Column 3 (\(y_3 = 1\)): \([0, 0, 1]^T\) - Column 4 (\(y_4 = 1\)): \([0, 1, 0]^T\) **Step 2: Compute the Maximum Likelihood Estimate \(\hat{p}_2^1 = \hat{P}(f_2 = 1 \mid y = 1)\).** Look at Row 2 (feature \(f_2\)) across columns 1, 3, and 4: the values are \(0, 0, 1\) (so \(f_2 = 1\) in **1** out of the **3** positive samples): \[\hat{p}_2^1 = \frac{1}{3} \approx 0.33\] **Answer: 0.33**

**Step 1: Compute the Maximum Likelihood Estimate \(\hat{p}_1^1 = \hat{P}(f_1 = 1 \mid y = 1)\).** From Q#194, the 3 samples with label \(y_i = 1\) are columns 1, 3, and 4: - Look at Row 1 (feature \(f_1\)) across columns 1, 3, and 4: the values are \(1, 0, 0\) (so \(f_1 = 1\) in **1** out of the **3** positive samples): \[\hat{p}_1^1 = \frac{1}{3} \approx 0.33\] **Answer: 0.33**

**Step 1: Identify the training set when the 3rd sample \((5, 12)\) is held out as the validation point.** The remaining \(n = 3\) training points are: - Sample 1: \((x_1, y_1) = (3, 8)\) - Sample 2: \((x_2, y_2) = (0, 3)\) - Sample 4: \((x_4, y_4) = (6, 13)\) **Step 2: Compute the means \(\bar{x}\) and \(\bar{y}\) of the 3 training points.** \[\bar{x} = \frac{3 + 0 + 6}{3} = 3, \qquad \bar{y} = \frac{8 + 3 + 13}{3} = 8\] **Step 3: Compute the slope \(w_1\) using ordinary least squares.** \[w_1 = \frac{\sum (x_i - \bar{x})(y_i - \bar{y})}{\sum (x_i - \bar{x})^2} = \frac{(3 - 3)(8 - 8) + (0 - 3)(3 - 8) + (6 - 3)(13 - 8)}{(3 - 3)^2 + (0 - 3)^2 + (6 - 3)^2}\] \[w_1 = \frac{0 + (-3)(-5) + (3)(5)}{0 + 9 + 9} = \frac{15 + 15}{18} = \frac{30}{18} = \frac{5}{3} \approx 1.67\] **Answer: 1.67**

**Step 1: Find the intercept \(w_0\) of the linear regression line fit on Samples 1, 2, and 4.** From Q#196, \(\bar{x} = 3\), \(\bar{y} = 8\), and \(w_1 = \frac{5}{3}\): \[w_0 = \bar{y} - w_1 \bar{x} = 8 - \frac{5}{3}(3) = 8 - 5 = 3\] Thus, the fitted regression line is: \[\hat{y} = 3 + \frac{5}{3} x\] **Step 2: Predict \(\hat{y}\) for the left-out 3rd sample at \(x = 5\).** \[\hat{y}(5) = 3 + \frac{5}{3}(5) = 3 + \frac{25}{3} = \frac{34}{3} \approx 11.33 \approx 11.3\] **Answer: D (11.3)** A: **Incorrect:** `12` is the true target value \(y_3\) of the 3rd sample, not the model's LOOCV prediction. B: **Incorrect:** `13` is the target value of Sample 4. C: **Incorrect:** Arithmetic error; \(3 + 25/3 = 11.33\), not \(12.3\). D: **Correct:** Using \(w_0 = 3\) and \(w_1 = 5/3\), the prediction at \(x = 5\) is \(3 + 25/3 = 11.33 \approx 11.3\). E: **Incorrect:** `11.3` is listed in Option D.

**Step 1: Recall the dual prediction formula for Kernel Regression.** Given \(w = \phi(X) \alpha\) where \(\alpha = [2.3, -1.0, 0.4, -0.7]^T\), the prediction for a test point \(x_{\text{test}}\) is: \[\hat{y}(x_{\text{test}}) = w^T \phi(x_{\text{test}}) = \sum_{i=1}^4 \alpha_i \, \phi(x_i)^T \phi(x_{\text{test}}) = \sum_{i=1}^4 \alpha_i \, k(x_i, x_{\text{test}})\] **Step 2: Evaluate the degree-3 polynomial kernel \(k(x_i, x_{\text{test}}) = (x_i^T x_{\text{test}} + 1)^3\) at \(x_{\text{test}} = [0, 0, 0, 0]^T\).** For every training point \(x_i\), \(x_i^T [0, 0, 0, 0]^T = 0\), so: \[k(x_i, 0) = (0 + 1)^3 = 1 \quad \text{for all } i = 1, 2, 3, 4\] **Step 3: Sum the dual coefficients \(\alpha_i\).** \[\hat{y}(0) = \sum_{i=1}^4 \alpha_i (1) = 2.3 + (-1.0) + 0.4 + (-0.7) = 1.0 = 1\] **Answer: 1**

**Step 1: Count the class prior parameters.** There are \(C = 5\) classes \(y \in \{0, 1, 2, 3, 4\}\). Since the 5 class prior probabilities \(P(y = c)\) must sum to 1 (\(\sum_{c=0}^4 P(y = c) = 1\)), we need **\(C - 1 = 5 - 1 = 4\)** independent prior parameters (or \(5\) if unnormalized). **Step 2: Count the class-conditional feature parameters.** For each of the \(C = 5\) classes and each of the \(d = 3\) conditionally independent binary features \(f_1, f_2, f_3 \in \{0, 1\}\), we need 1 Bernoulli parameter \(P(f_j = 1 \mid y = c)\) (since \(P(f_j = 0 \mid y = c) = 1 - P(f_j = 1 \mid y = c)\)): \[\text{Feature parameters} = 5 \times 3 = 15\] **Step 3: Sum the parameters.** \[\text{Total parameters} = 4 + 15 = 19\] (Within the accepted range `19 to 20`.) **Answer: 19**

**Step 1: Express the predicted vector \(\hat{y}\) when \(w^*\) is orthogonal to all columns of \(X\).** The columns of \(X \in \mathbb{R}^{d \times n}\) are the data points \(x_1, x_2, \dots, x_n \in \mathbb{R}^d\). If \(w^*\) is orthogonal to the subspace spanned by the columns of \(X\), then for every data point \(x_i\): \[\hat{y}_i = (w^*)^T x_i = 0 \quad \text{for all } i = 1, \dots, n\] In vector form, \(\hat{y} = X^T w^* = 0\). **Step 2: Compute the total squared error.** \[\text{Squared Error} = \sum_{i=1}^n (y_i - \hat{y}_i)^2 = \sum_{i=1}^n (y_i - 0)^2 = \|y\|^2\] **Answer: C (\(\|y\|^2\))** A: **Incorrect:** A squared error of 0 would require \(\hat{y} = y\), which only happens if \(y = 0\). B: **Incorrect:** The squared error equals \(\|y\|^2\), not 1. C: **Correct:** Since \((w^*)^T x_i = 0\) for every column \(x_i\) of \(X\), the predictions are all 0 and the squared error is \(\|y - 0\|^2 = \|y\|^2\). D: **Incorrect:** The squared error is uniquely determined in terms of \(\|y\|^2\).

**Step 1: Recall the closed-form solution for Ridge Regression.** Given design matrix \(X = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}\), target vector \(Y = \begin{bmatrix} 3 \\ 5 \end{bmatrix}\), and regularization parameter \(\lambda = 1\): \[\beta = (X^T X + \lambda I)^{-1} X^T Y\] (Note: whether \(X\) has samples as rows or columns, let us check \(X^T X + I\) and \(X X^T + I\)): - With \(X = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}\): \[X^T X + I = \begin{bmatrix} 1 & 3 \\ 2 & 4 \end{bmatrix} \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} + \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 10 & 14 \\ 14 & 20 \end{bmatrix} + \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 11 & 14 \\ 14 & 21 \end{bmatrix}\] \[X^T Y = \begin{bmatrix} 1 & 3 \\ 2 & 4 \end{bmatrix} \begin{bmatrix} 3 \\ 5 \end{bmatrix} = \begin{bmatrix} 18 \\ 26 \end{bmatrix}\] Determinant of \(X^T X + I\): \(11(21) - 14(14) = 231 - 196 = 35\). \[\beta = \frac{1}{35} \begin{bmatrix} 21 & -14 \\ -14 & 11 \end{bmatrix} \begin{bmatrix} 18 \\ 26 \end{bmatrix} = \frac{1}{35} \begin{bmatrix} 378 - 364 \\ -252 + 286 \end{bmatrix} = \frac{1}{35} \begin{bmatrix} 14 \\ 34 \end{bmatrix} = \begin{bmatrix} 0.4 \\ 0.971 \end{bmatrix}\] - Now check when columns of \(X\) are data points (\(X \in \mathbb{R}^{d \times n}\)), so the design matrix with rows as samples is \(X^T\), giving \(\beta = (X X^T + \lambda I)^{-1} X Y\): \[X X^T + I = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \begin{bmatrix} 1 & 3 \\ 2 & 4 \end{bmatrix} + \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 5 & 11 \\ 11 & 25 \end{bmatrix} + \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 6 & 11 \\ 11 & 26 \end{bmatrix}\] \[X Y = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \begin{bmatrix} 3 \\ 5 \end{bmatrix} = \begin{bmatrix} 13 \\ 29 \end{bmatrix}\] Determinant of \(X X^T + I\): \(6(26) - 11(11) = 156 - 121 = 35\). \[\beta = \frac{1}{35} \begin{bmatrix} 26 & -11 \\ -11 & 6 \end{bmatrix} \begin{bmatrix} 13 \\ 29 \end{bmatrix} = \frac{1}{35} \begin{bmatrix} 338 - 319 \\ -143 + 174 \end{bmatrix} = \frac{1}{35} \begin{bmatrix} 19 \\ 31 \end{bmatrix} \approx \begin{bmatrix} 0.5429 \\ 0.8857 \end{bmatrix} \approx [0.54, 0.88]\] **Answer: C (\(\beta = [0.54, 0.88]\))** A: **Incorrect:** Does not account for the \(\lambda I\) Ridge penalty and \(X X^T\) inversion. B: **Incorrect:** \([1, 0.5]\) is the unregularized OLS solution (\(\lambda = 0\)), since \(1(1)+2(0.5)=2\) or \(1(1)+3(0.5)=2.5\). C: **Correct:** Using \(X \in \mathbb{R}^{d \times n}\), \(\beta = (X X^T + I)^{-1} X Y = \frac{1}{35}[19, 31]^T \approx [0.54, 0.88]\). D: **Incorrect:** Does not match \((X X^T + I)^{-1} X Y\). E: **Incorrect:** Option C is the exact rounded value.

**Step 1: Write the classification conditions for zero 0-1 loss on all 4 points.** A linear classifier through the origin with weight vector \(\mathbf{w}\) predicts label `1` when \(\mathbf{w}^T \mathbf{x} > 0\) and label `0` when \(\mathbf{w}^T \mathbf{x} < 0\) (or \(\le 0\)): 1. For \((\mathbf{u}, 1)\): requires \(\mathbf{w}^T \mathbf{u} > 0\). 2. For \((-2\mathbf{u}, 0)\): requires \(\mathbf{w}^T (-2\mathbf{u}) = -2(\mathbf{w}^T \mathbf{u}) < 0 \iff \mathbf{w}^T \mathbf{u} > 0\). 3. For \((3\mathbf{u}, 1)\): requires \(\mathbf{w}^T (3\mathbf{u}) = 3(\mathbf{w}^T \mathbf{u}) > 0 \iff \mathbf{w}^T \mathbf{u} > 0\). 4. For \((-4\mathbf{u}, 0)\): requires \(\mathbf{w}^T (-4\mathbf{u}) = -4(\mathbf{w}^T \mathbf{u}) < 0 \iff \mathbf{w}^T \mathbf{u} > 0\). All four points are classified with zero error if and only if **\(\mathbf{w}^T \mathbf{u} > 0\)**. **Answer: B (\(\mathbf{w}^T \mathbf{u} > 0\))** A: **Incorrect:** If \(\mathbf{w}^T \mathbf{u} < 0\), every point gets the opposite label (100% misclassification loss). B: **Correct:** When \(\mathbf{w}^T \mathbf{u} > 0\), positive multiples of \(\mathbf{u}\) have positive dot products (label 1) and negative multiples have negative dot products (label 0). C: **Incorrect:** If \(\mathbf{w}^T \mathbf{u} = 0\), all four points lie on the decision boundary. D: **Incorrect:** Any vector \(\mathbf{w}\) with \(\mathbf{w}^T \mathbf{u} > 0\) (for example, \(\mathbf{w} = \mathbf{u}\) for \(\mathbf{u} \ne 0\)) achieves zero loss.

Let us analyze the geometry of the decision hyperplane \(\mathbf{w}^T \mathbf{x} = 0\) (the line through the origin perpendicular to the normal vector \(\mathbf{w}\)): - For any point \(\mathbf{x}\), the inner product \(\mathbf{w}^T \mathbf{x} = \|\mathbf{w}\| \cdot (\text{signed perpendicular distance of } \mathbf{x} \text{ from the line } \mathbf{w}^T \mathbf{x} = 0 \text{ in the direction of } \mathbf{w})\). - **A is correct (\(0 < \mathbf{w}^T \mathbf{x}_1 < \mathbf{w}^T \mathbf{x}_2 < \mathbf{w}^T \mathbf{x}_3\))**: Points \(\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3\) all lie on the positive side of the hyperplane (where \(\mathbf{w}\) points), at progressively larger perpendicular distances from the decision boundary line: \(\text{dist}(\mathbf{x}_1) < \text{dist}(\mathbf{x}_2) < \text{dist}(\mathbf{x}_3)\). - **B is correct (\(\mathbf{w}^T \mathbf{x}_4 = 0\))**: Point \(\mathbf{x}_4\) lies directly **on** the decision boundary line, which is orthogonal to \(\mathbf{w}\). - **C is incorrect**: \(\mathbf{x}_1\) is closer to the boundary line than \(\mathbf{x}_2\), so \(\mathbf{w}^T \mathbf{x}_1 < \mathbf{w}^T \mathbf{x}_2\). - **D is correct (\(\mathbf{w}^T \mathbf{x}_5 < 0\))**: Point \(\mathbf{x}_5\) lies on the opposite (negative) side of the hyperplane from \(\mathbf{w}\). - **E is incorrect**: Point \(\mathbf{x}_3\) lies far on the positive side of the hyperplane, so \(\mathbf{w}^T \mathbf{x}_3 > 0\). **Answer: A, B, D** A: **Correct:** \(\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3\) lie on the positive side of the boundary at increasing perpendicular distances along \(\mathbf{w}\). B: **Correct:** \(\mathbf{x}_4\) lies on the line through the origin perpendicular to \(\mathbf{w}\), so \(\mathbf{w}^T \mathbf{x}_4 = 0\). C: **Incorrect:** \(\mathbf{x}_2\) is farther from the decision line in the direction of \(\mathbf{w}\) than \(\mathbf{x}_1\). D: **Correct:** \(\mathbf{x}_5\) lies on the negative half-space opposite to \(\mathbf{w}\), so \(\mathbf{w}^T \mathbf{x}_5 < 0\). E: **Incorrect:** \(\mathbf{x}_3\) is in the positive half-space, so \(\mathbf{w}^T \mathbf{x}_3 > 0\).

Let us evaluate each statement about **Decision Trees** and **\(k\)-NN**: - **A is correct**: In a decision tree, the quality of a candidate split question \(Q\) at a node is measured by its **Information Gain (IG)**; a question \(Q_1\) is considered "better" than \(Q_2\) if and only if \(\text{IG}(Q_1) > \text{IG}(Q_2)\). - **B is correct**: \(k\)-NN is a **lazy (instance-based, non-parametric) learner** that does not distill the training data into a fixed parameter vector; it must retain and search the **entire training dataset** at test time to find the \(k\) nearest neighbors of a test point. - **C is incorrect**: If the threshold \(\theta\) is chosen smaller than the minimum value (or larger than the maximum value) of feature \(f_k\) in the dataset, one of the two resulting subsets will be **empty**. - **D is correct**: The maximum depth of a decision tree controls model complexity and bias-variance trade-off, so it is a **hyperparameter** tuned using **cross-validation**. - **E is incorrect**: Decision trees overfit when the maximum depth is set too **high** (deep, unpruned trees); setting the maximum depth too *low* causes **underfitting** (high bias). **Answer: A, B, D** A: **Correct:** Decision tree splitting selects the question that maximizes Information Gain. B: **Correct:** As an instance-based lazy learner, \(k\)-NN requires the training dataset during inference to compute distances. C: **Incorrect:** If \(\theta < \min(f_k)\) or \(\theta \ge \max(f_k)\), one side of the partition is empty. D: **Correct:** Maximum tree depth is a model hyperparameter selected via cross-validation. E: **Incorrect:** Low maximum depth leads to underfitting; high maximum depth leads to overfitting.