Machine Learning Techniques · Quiz 2 · May 2025

**1. Set Up the Log-Likelihood Function:** - We are given \( n \) independent data points \( (x_i, y_i) \) where \( x_i \in \mathbb{R}^+ \), \( w > 0 \), and: \[ y_i \mid x_i \sim \mathcal{N}(\log(w x_i), 1) \] - Using logarithm properties, \( \log(w x_i) = \log(w) + \log(x_i) \). Let \( \theta = \log(w) \). - The conditional probability density for each observation is: \[ p(y_i \mid x_i; w) = \frac{1}{\sqrt{2\pi}} \exp\left( -\frac{1}{2} (y_i - \log(w) - \log(x_i))^2 \right) \] **2. Maximize the Log-Likelihood with Respect to \( w \):** - The log-likelihood function \( \ell(w) \) over all \( n \) points is: \[ \ell(w) = -\frac{n}{2}\log(2\pi) - \frac{1}{2}\sum_{i=1}^n (y_i - \log(x_i) - \log(w))^2 \] - Differentiating \( \ell(w) \) with respect to \( w \) and setting the derivative to zero: \[ \frac{\partial \ell(w)}{\partial w} = \frac{1}{w}\sum_{i=1}^n (y_i - \log(x_i) - \log(w)) = 0 \] - Since \( w > 0 \), we solve for \( \log(\hat{w}_{MLE}) \): \[ n \log(\hat{w}_{MLE}) = \sum_{i=1}^n (y_i - \log(x_i)) \implies \log(\hat{w}_{MLE}) = \frac{1}{n}\sum_{i=1}^n (y_i - \log(x_i)) \] - Taking the exponential on both sides yields: \[ \hat{w}_{MLE} = \exp\left( \frac{1}{n}\sum_{i=1}^n (y_i - \log(x_i)) \right) \] **Answer: \( \hat{w}_{MLE} = \exp\left(\frac{1}{n}\sum_{i=1}^n (y_i - \log(x_i))\right) \) (Option A).** A: **Correct:** Setting the derivative of the Gaussian log-likelihood with mean \( \log(w) + \log(x_i) \) to zero gives \( \log(\hat{w}_{MLE}) = \frac{1}{n}\sum_{i=1}^n (y_i - \log(x_i)) \), so \( \hat{w}_{MLE} = \exp\left(\frac{1}{n}\sum_{i=1}^n (y_i - \log(x_i))\right) \). B: **Incorrect:** The derivative of \( \log(w x_i) = \log(w) + \log(x_i) \) with respect to \( \log(w) \) is \( 1 \), so there is no extra factor of \( x_i \) multiplying \( y_i \) or \( \log(x_i) \). C: **Incorrect:** \( \frac{1}{n}\sum_{i=1}^n (y_i - \log(x_i)) \) is the estimate for \( \log(w) \), so we must exponentiate it to obtain \( \hat{w}_{MLE} \). D: **Incorrect:** \( y_i \) is not multiplied by \( x_i \) inside the sum.

**1. Formulate the Posterior Distribution in Bayesian Linear Regression:** - Likelihood: \( y \mid X, w \sim \mathcal{N}(X^T w, \sigma^2 I) \), so the negative log-likelihood (up to an additive constant) is: \[ -\log p(y \mid X, w) = \frac{1}{2\sigma^2} \|y - X^T w\|_2^2 + \text{const} \] - Prior: \( w \sim \mathcal{N}(0, \gamma^2 I) \), so the negative log-prior (up to an additive constant) is: \[ -\log p(w) = \frac{1}{2\gamma^2} \|w\|_2^2 + \text{const} \] **2. Derive the MAP Objective and Identify \( \lambda \):** - Maximizing the posterior \( p(w \mid y, X) \propto p(y \mid X, w)p(w) \) is equivalent to minimizing the sum of the negative log-likelihood and negative log-prior: \[ \hat{w}_{MAP} = \arg\min_w \left\{ \frac{1}{2\sigma^2}\|y - X^T w\|_2^2 + \frac{1}{2\gamma^2}\|w\|_2^2 \right\} \] - Multiplying the objective by \( 2\sigma^2 > 0 \) (which does not change the minimizer) gives: \[ \hat{w}_{MAP} = \arg\min_w \left\{ \|y - X^T w\|_2^2 + \frac{\sigma^2}{\gamma^2}\|w\|_2^2 \right\} \] - Comparing this with \( \arg\min_w \left\{ \|y - X^T w\|_2^2 + \lambda\|w\|_2^2 \right\} \), we get: \[ \lambda = \frac{\sigma^2}{\gamma^2} \] **Answer: \( \lambda = \frac{\sigma^2}{\gamma^2} \) (Option C).** A: **Incorrect:** \( \lambda \) is the ratio of noise variance \( \sigma^2 \) to prior variance \( \gamma^2 \), not their product. B: **Incorrect:** This is the reciprocal \( \frac{\gamma^2}{\sigma^2} \); stronger prior certainty (smaller \( \gamma^2 \)) increases regularization \( \lambda \). C: **Correct:** Multiplying the negative log-posterior \( \frac{1}{2\sigma^2}\|y - X^T w\|^2 + \frac{1}{2\gamma^2}\|w\|^2 \) by \( 2\sigma^2 \) yields \( \lambda = \frac{\sigma^2}{\gamma^2} \). D: **Incorrect:** \( \lambda \) is not \( \frac{1}{\sigma^2 + \gamma^2} \).

**1. Compare Training and Validation Errors Across Hyperparameter Settings:** - **Setting 1:** Training Error = \( 150 \), Validation Error = \( 160 \). - **Setting 2:** Training Error = \( 145 \), Validation Error = \( 150 \) (lowest validation error). - **Setting 3:** Training Error = \( 140 \), Validation Error = \( 190 \) (low training error but high validation error, indicating overfitting). - **Setting 4:** Training Error = \( 170 \), Validation Error = \( 180 \). **2. Select the Best Hyperparameter Setting:** - Hyperparameters are always chosen based on **validation error** because validation performance measures how well the model generalizes to unseen data. - **Setting 2** achieves the lowest validation error (\( 150 \)) while maintaining a low training error (\( 145 \)), demonstrating the best generalization. **Answer: Setting 2, because it has the lowest validation error and a relatively low training error, indicating a good generalization.** A: **Incorrect:** Setting 3 has the lowest training error (140) but the highest validation error (190), which indicates overfitting rather than good generalization. B: **Correct:** Setting 2 achieves the lowest validation error (150) along with a low training error (145), indicating the best generalization on unseen data. C: **Incorrect:** More iterations alone do not guarantee better generalization; Setting 1 has higher training and validation errors than Setting 2. D: **Incorrect:** Setting 4 has high training (170) and validation (180) errors due to an overly large learning rate.

**1. Bias-Variance Trade-off Between \( \hat{w}_{MLE} \) and \( \hat{w}_{MAP} \):** - The Mean Squared Error (MSE) of an estimator \( \hat{w} \) is the sum of its squared bias and its variance: \[ \text{MSE}(\hat{w}) = \mathbb{E}\left[\|\hat{w} - w\|^2\right] = \|\text{Bias}(\hat{w})\|^2 + \text{Var}(\hat{w}) \] - While the ordinary least squares / MLE estimator \( \hat{w}_{MLE} \) is **unbiased** (\( \text{Bias}(\hat{w}_{MLE}) = 0 \)), it can have high variance (especially when features are correlated or sample size is small). - The MAP / Ridge estimator \( \hat{w}_{MAP} = (X X^T + \lambda I)^{-1} X y \) introduces a small bias for \( \lambda > 0 \), but reduces variance significantly. - By the existence theorem for Ridge regression, there always exists some regularization parameter \( \lambda > 0 \) for which the reduction in variance outweighs the squared bias, yielding \( \text{MSE}(\hat{w}_{MAP}) < \text{MSE}(\hat{w}_{MLE}) \). **Answer: The estimator \( \hat{w}_{MAP} \) can achieve lower MSE than \( \hat{w}_{MLE} \) for some \( \lambda > 0 \), where \( \lambda \in \mathbb{R} \) (Option C).** A: **Incorrect:** Being unbiased only guarantees zero bias, not minimum MSE; a slightly biased estimator with much lower variance can have a smaller total MSE. B: **Incorrect:** \( \hat{w}_{MAP} \) does not *always* beat \( \hat{w}_{MLE} \) for every choice of \( \lambda \); if \( \lambda \) is too large, the squared bias dominates and increases MSE. C: **Correct:** By trading a small amount of bias for a larger reduction in variance, \( \hat{w}_{MAP} \) (Ridge regression) can achieve a lower MSE than \( \hat{w}_{MLE} \) for an appropriate \( \lambda > 0 \). D: **Incorrect:** When the sample size is small, \( \hat{w}_{MLE} \) has much higher variance than \( \hat{w}_{MAP} \), so their MSEs are not equal.

**1. Analyze the Effect of Duplicating Points and Adding Exact-Fit Points:** - Let \( w^* = \arg\min_{w \in \mathbb{R}^d} \|X^T w - y\|_2^2 = \arg\min_{w} \sum_{i=1}^n (x_i^T w - y_i)^2 \). - When we duplicate all \( n \) points in \( D \), the sum of squared errors over the duplicated dataset is simply \( 2 \sum_{i=1}^n (x_i^T w - y_i)^2 \). - Next, we add 10 new points \( (\tilde{x}_j, \tilde{y}_j) \) that lie **exactly** on the hyperplane \( \tilde{y}_j = \tilde{x}_j^T w^* \). **2. Check the Minimizer of the New Objective:** - The new objective function is: \[ J_{\text{new}}(w) = 2 \sum_{i=1}^n (x_i^T w - y_i)^2 + \sum_{j=1}^{10} (\tilde{x}_j^T w - \tilde{y}_j)^2 \] - At \( w = w^* \), the first term achieves its global minimum \( 2 \sum_{i=1}^n (x_i^T w^* - y_i)^2 \), and the second term is \( \sum_{j=1}^{10} (\tilde{x}_j^T w^* - \tilde{y}_j)^2 = 0 \) (which is also the minimum possible value of a sum of squares, since squares are non-negative). - Because \( w^* \) simultaneously minimizes both non-negative parts of \( J_{\text{new}}(w) \), the optimal solution \( w_{\text{new}}^* \) remains \( w^* \). **Answer: TRUE.** A: **Correct:** Duplicating the original points scales the original loss by 2, and the 10 new points have zero residual at \( w^* \), so \( w^* \) simultaneously minimizes both terms of the new objective. B: **Incorrect:** Because the new points have zero error at \( w^* \) and duplicating all original points only multiplies the original objective by 2, the minimizer does not change.

**1. Relate Gaussian Conditional Log-Likelihood to Sum of Squared Errors:** - In the linear regression model \( y = w^T x + \epsilon \) with \( \epsilon \sim \mathcal{N}(0, \sigma^2) \), the conditional distribution of \( y_i \) given \( x_i \) is \( \mathcal{N}(w^T x_i, \sigma^2) \). - For \( n \) independent observations, the conditional log-likelihood of \( w \) is: \[ \ell(w) = \sum_{i=1}^n \log p(y_i \mid x_i; w) = -\frac{n}{2}\log(2\pi\sigma^2) - \frac{1}{2\sigma^2}\sum_{i=1}^n (y_i - w^T x_i)^2 = -\frac{n}{2}\log(2\pi\sigma^2) - \frac{1}{2\sigma^2}\|y - X^T w\|_2^2 \] - Since \( -\frac{n}{2}\log(2\pi\sigma^2) \) is constant with respect to \( w \) and \( \frac{1}{2\sigma^2} > 0 \), maximizing \( \ell(w) \) with respect to \( w \) is mathematically equivalent to minimizing \( \|y - X^T w\|_2^2 \). **Answer: TRUE.** A: **Correct:** Under zero-mean i.i.d. Gaussian noise \( \mathcal{N}(0, \sigma^2) \), the log-likelihood is a negative linear function of the sum of squared residuals \( \|y - X^T w\|_2^2 \), so maximizing log-likelihood is equivalent to minimizing \( \|y - X^T w\|_2^2 \). B: **Incorrect:** The equivalence holds directly from the exponent of the Gaussian probability density function.

**1. Analyze the Column Space Projection (\( X^T w^* \)):** - Here \( X \in \mathbb{R}^{d \times n} \) has \( d \) rows (features) and \( n \) columns (data points), so \( X^T \in \mathbb{R}^{n \times d} \) has \( d \) columns in \( \mathbb{R}^n \), where each column of \( X^T \) corresponds to one feature across the \( n \) samples. - Minimizing \( \|X^T w - y\|_2^2 \) projects the label vector \( y \in \mathbb{R}^n \) orthogonally onto the column space of \( X^T \), which is the subspace spanned by the \( d \) features. Thus \( X^T w^* \) is the projection of the labels onto the subspace spanned by the features (**Option A is true**, Option B is false). **2. Analyze the Normal Equations for \( w^* \):** - By the normal equations (taking the minimum-norm least squares solution), \( X X^T w^* = X y \). - Even more generally, any component of \( w \) orthogonal to the column space of \( X \) (the span of the data points \( x_1, \dots, x_n \in \mathbb{R}^d \)) lies in the nullspace of \( X^T \) and does not affect \( X^T w \). The minimum-norm/standard solution \( w^* = X \alpha \) lies in the column space of \( X \), which is the **span of the data points** in \( \mathbb{R}^d \) (**Option C is true**, Option D is false). **Answer: Options A and C.** A: **Correct:** \( X^T w^* \in \mathbb{R}^n \) is a linear combination of the columns of \( X^T \) (the feature vectors across samples), representing the orthogonal projection of \( y \) onto the subspace spanned by the features. B: **Incorrect:** The data points are columns of \( X \) in \( \mathbb{R}^d \), whereas \( X^T w^* \) lies in \( \mathbb{R}^n \) (the span of the feature columns of \( X^T \)). C: **Correct:** From \( X X^T w^* = X y \), the optimal weight vector \( w^* \in \mathbb{R}^d \) is a linear combination of the columns of \( X \), so it lies in the span of the data points. D: **Incorrect:** The features are vectors in \( \mathbb{R}^n \), whereas \( w^* \in \mathbb{R}^d \) lies in the span of the data points.

**1. Compare Generative and Discriminative Models:** - **Generative Models:** Model the class-conditional distribution \( p(x \mid y) \) and prior \( p(y) \) (or joint distribution \( p(x, y) \)), capturing **how the features \( x \) are generated** given the label \( y \), and then use Bayes' rule to find \( p(y \mid x) \). Examples include Gaussian Naive Bayes, LDA, and GMMs. (**Option A is true**, Options D and E are false). - **Discriminative Models:** Directly model the conditional probability \( p(y \mid x) \) (or learn a decision boundary directly) without modeling how the features \( x \) are generated. Examples include Logistic Regression and SVMs. (**Option C is true**, Option B is false). **Answer: Options A and C.** A: **Correct:** Generative models learn the joint/class-conditional distribution \( p(x \mid y) \), modeling how the features are generated. B: **Incorrect:** Discriminative models do not model how features are generated; they directly model \( p(y \mid x) \). C: **Correct:** Discriminative models directly estimate the posterior class probability \( p(y \mid x) \). D: **Incorrect:** Modeling \( p(y \mid x) \) directly is the objective of a discriminative model, whereas generative models model \( p(x \mid y) \) and \( p(y) \). E: **Incorrect:** Gaussian Naive Bayes models \( p(x \mid y) \) and \( p(y) \), making it a generative model, not a discriminative model.

**1. Compute Euclidean Distances from the Test Point \( x_{\text{test}} = [3, 2]^T \):** - Point 1: \( (1, 2) \), \( y_1 = 3.5 \implies d_1 = \sqrt{(3 - 1)^2 + (2 - 2)^2} = \sqrt{4 + 0} = 2.0 \) - Point 2: \( (2, 1) \), \( y_2 = 2.8 \implies d_2 = \sqrt{(3 - 2)^2 + (2 - 1)^2} = \sqrt{1 + 1} = \sqrt{2} \approx 1.414 \) - Point 3: \( (3, 3) \), \( y_3 = 5.1 \implies d_3 = \sqrt{(3 - 3)^2 + (2 - 3)^2} = \sqrt{0 + 1} = 1.0 \) - Point 4: \( (4, 2) \), \( y_4 = 4.7 \implies d_4 = \sqrt{(3 - 4)^2 + (2 - 2)^2} = \sqrt{1 + 0} = 1.0 \) - Point 5: \( (5, 3) \), \( y_5 = 6.2 \implies d_5 = \sqrt{(3 - 5)^2 + (2 - 3)^2} = \sqrt{4 + 1} = \sqrt{5} \approx 2.236 \) - Point 6: \( (6, 1) \), \( y_6 = 5.9 \implies d_6 = \sqrt{(3 - 6)^2 + (2 - 1)^2} = \sqrt{9 + 1} = \sqrt{10} \approx 3.162 \) **2. Identify the 3 Nearest Neighbors and Average Their Labels:** - The 3 smallest distances correspond to Point 3 (\( d_3 = 1.0 \)), Point 4 (\( d_4 = 1.0 \)), and Point 2 (\( d_2 \approx 1.414 \)). - Their labels are \( y_3 = 5.1 \), \( y_4 = 4.7 \), and \( y_2 = 2.8 \). - The predicted value for 3-NN regression is the average of these three labels: \[ \hat{y} = \frac{5.1 + 4.7 + 2.8}{3} = \frac{12.6}{3} = 4.2 \] **Answer: 4.2.**

**1. Trace the Regions Predicted as Label 1 (`+`) by the Decision Tree:** - **Left Subtree (\( f_1 \le 1.5 \) is Yes):** - Next split is \( f_1 < 0 \): - If **No** (\( 0 \le f_1 \le 1.5 \)), the leaf predicts **0** (`-`). - If **Yes** (\( f_1 < 0 \)), we check \( f_2 > 1.5 \): - If **Yes** (\( f_1 < 0 \) and \( f_2 > 1.5 \)), the leaf predicts **1** (`+`). (Top-left green region where \( f_1 < 0, f_2 > 1.5 \)). - If **No** (\( f_1 < 0 \) and \( f_2 \le 1.5 \)), the leaf predicts **0** (`-`). - **Right Subtree (\( f_1 \le 1.5 \) is No, i.e., \( f_1 > 1.5 \)):** - Next split is \( f_2 < 0 \): - If **Yes** (\( f_1 > 1.5 \) and \( f_2 < 0 \)), the leaf predicts **1** (`+`). (Bottom-right green region where \( f_1 > 1.5, f_2 < 0 \)). - If **No** (\( f_1 > 1.5 \) and \( f_2 \ge 0 \)), the leaf predicts **0** (`-`). **2. Match with the Decision Boundary Plots:** - Only **Option B** shows the green `+` (label 1) region in the top-left (\( f_1 < 0, f_2 > 1.5 \)) and bottom-right (\( f_1 > 1.5, f_2 < 0 \)), and red `-` (label 0) everywhere else. **Answer: Option B.** A: **Incorrect:** This plot places the upper-left green `+` region in \( 0 < f_1 \le 1.5, f_2 > 1.5 \) instead of \( f_1 < 0, f_2 > 1.5 \). B: **Correct:** Label 1 (`+`) is predicted exclusively when \( (f_1 < 0 \text{ and } f_2 > 1.5) \) or \( (f_1 > 1.5 \text{ and } f_2 < 0) \), matching the second plot. C: **Incorrect:** This plot places the right-side green `+` region in \( f_1 > 1.5, f_2 > 0 \) instead of \( f_1 > 1.5, f_2 < 0 \). D: **Incorrect:** This plot shades the entire upper-left quadrant \( f_1 \le 1.5, f_2 > 0 \) as green (`+`).

**1. Trace the Datapoint \( (f_1, f_2) = (2, 2) \) Through the Decision Tree:** - **Root Node (\( f_1 \le 1.5 \)):** Since \( f_1 = 2 > 1.5 \), we follow the **No** branch to the right child node. - **Right Child Node (\( f_2 < 0 \)):** Since \( f_2 = 2 \not< 0 \), we follow the **No** branch to the right leaf node. - **Leaf Node:** The leaf node outputs class label **0**. **Answer: 0.**

**1. Identify the Conditional Distributions Given \( y = 0 \):** - We are given a test point \( x_{\text{test}} = [0, 0]^T \), so \( f_1 = 0 \) and \( f_2 = 0 \). - For class \( y = 0 \): - Feature 1 is binary with \( P(f_1 = 1 \mid y = 0) = \hat{p}_1^0 = 0.4 \), so: \[ P(f_1 = 0 \mid y = 0) = 1 - 0.4 = 0.6 \] - Feature 2 is Gaussian with \( (f_2 \mid y = 0) \sim \mathcal{N}(0, 1) \), so its density at \( f_2 = 0 \) is: \[ p(f_2 = 0 \mid y = 0) = \frac{1}{\sqrt{2\pi (1)}} e^{-\frac{(0 - 0)^2}{2(1)}} = \frac{1}{\sqrt{2\pi}} \approx 0.39894 \] **2. Compute the Naive Bayes Conditional Likelihood Given \( y = 0 \):** - By the Naive Bayes conditional independence assumption: \[ P(x_{\text{test}} = [0, 0]^T \mid y = 0) = P(f_1 = 0 \mid y = 0) \cdot p(f_2 = 0 \mid y = 0) = 0.6 \times \frac{1}{\sqrt{2\pi}} \approx 0.6 \times 0.39894 = 0.23936 \approx 0.24 \] **Answer: 0.24.**

**1. Compute the Posterior Score for Class \( y = 0 \) at \( x_{\text{test}} = [0, 1.5]^T \):** - Prior: \( P(Y = 0) = 1 - P(Y = 1) = 1 - 0.4 = 0.6 \). - For \( f_1 = 0 \): \( P(f_1 = 0 \mid y = 0) = 1 - 0.4 = 0.6 \). - For \( f_2 = 1.5 \) with \( (f_2 \mid y = 0) \sim \mathcal{N}(0, 1) \): \[ p(f_2 = 1.5 \mid y = 0) = \frac{1}{\sqrt{2\pi}} e^{-\frac{(1.5 - 0)^2}{2}} = \frac{1}{\sqrt{2\pi}} e^{-1.125} \] - Unnormalized posterior for \( y = 0 \): \[ S_0 = P(Y = 0) P(f_1 = 0 \mid y = 0) p(f_2 = 1.5 \mid y = 0) = 0.6 \times 0.6 \times \frac{1}{\sqrt{2\pi}} e^{-1.125} = \frac{0.36}{\sqrt{2\pi}} e^{-1.125} \approx \frac{0.36 \times 0.32465}{\sqrt{2\pi}} \approx \frac{0.11687}{\sqrt{2\pi}} \] **2. Compute the Posterior Score for Class \( y = 1 \) at \( x_{\text{test}} = [0, 1.5]^T \):** - Prior: \( P(Y = 1) = 0.4 \). - For \( f_1 = 0 \): \( P(f_1 = 0 \mid y = 1) = 1 - 0.5 = 0.5 \). - For \( f_2 = 1.5 \) with \( (f_2 \mid y = 1) \sim \mathcal{N}(1, 1) \): \[ p(f_2 = 1.5 \mid y = 1) = \frac{1}{\sqrt{2\pi}} e^{-\frac{(1.5 - 1)^2}{2}} = \frac{1}{\sqrt{2\pi}} e^{-0.125} \] - Unnormalized posterior for \( y = 1 \): \[ S_1 = P(Y = 1) P(f_1 = 0 \mid y = 1) p(f_2 = 1.5 \mid y = 1) = 0.4 \times 0.5 \times \frac{1}{\sqrt{2\pi}} e^{-0.125} = \frac{0.20}{\sqrt{2\pi}} e^{-0.125} \approx \frac{0.20 \times 0.88250}{\sqrt{2\pi}} \approx \frac{0.17650}{\sqrt{2\pi}} \] **3. Compare Scores:** - Since \( S_1 > S_0 \) (\( 0.1765 > 0.1169 \)), the Naive Bayes classifier predicts class **1**. **Answer: 1.**

**1. Find Class Proportions at the Root Node:** - Total patients = \( 1000 \). - Total positive patients = \( 300 + 100 = 400 \implies p_+ = \frac{400}{1000} = 0.4 \). - Total negative patients = \( 50 + 550 = 600 \implies p_- = \frac{600}{1000} = 0.6 \). **2. Calculate the Root Entropy:** - Using the given values \( \log_2(0.4) = -1.32 \) and \( \log_2(0.6) = -0.74 \): \[ H(\text{Root}) = -p_+ \log_2(p_+) - p_- \log_2(p_-) = -0.4(-1.32) - 0.6(-0.74) = 0.528 + 0.444 = 0.972 \approx 0.97 \] **Answer: 0.97.**