Machine Learning Techniques · End Term · May 2026 · FN

**1. Understand the effect of positive uniform feature scaling on the Perceptron:** We are given a linearly separable dataset \(S = \{(x_1, y_1), \dots, (x_n, y_n)\}\) in \(\mathbb{R}^d\) (separable through the origin) and a scaled dataset \(S' = \{(cx_1, y_1), \dots, (cx_n, y_n)\}\) with \(c > 1\). The perceptron starts at \(w^{(0)} = 0\) with learning rate \(\eta = 1\) and processes points in the exact same order. **2. Trace the weight updates on \(S\) and \(S'\):** Suppose at step \(t\), the weight vector on \(S'\) is \(w'^{(t)} = c w^{(t)}\). Since \(w^{(0)} = 0\), this holds at \(t = 0\). When examining the \(i\)-th sample, the activation on \(S'\) is: \[(w'^{(t)})^T (c x_i) = c^2 (w^{(t)})^T x_i\] Because \(c > 1 > 0\), \(c^2 > 0\), so the sign of \((w'^{(t)})^T (cx_i)\) is identical to the sign of \((w^{(t)})^T x_i\). Therefore, a mistake occurs on \(S'\) if and only if a mistake occurs on \(S\), and the update \(w'^{(t+1)} = w'^{(t)} + y_i (c x_i) = c(w^{(t)} + y_i x_i) = c w^{(t+1)}\) preserves the exact scaling \(w' = c w\) at every step! **3. Evaluate the mistake bound, convergence, and decision boundary:** - In Novikoff's mistake bound \(M \le (R/\gamma)^2\), scaling all \(x_i\) by \(c\) scales the radius \(R' = cR\) and the margin \(\gamma' = c\gamma\), so the ratio \((R'/\gamma')^2 = (R/\gamma)^2\) is unchanged. - Since \(S\) is linearly separable, \(S'\) is also linearly separable by the exact same unit normal vector, so the perceptron is guaranteed to converge on \(S'\). - At convergence, \(w'_{\text{final}} = c w_{\text{final}}\). Because scaling a normal vector by a positive constant \(c > 0\) does not change the hyperplane \(\{x : w^T x = 0\}\), both produce the exact same decision boundary. **Answer: C, D — The perceptron is guaranteed to converge on S', and it produces the exact same decision boundary on S and S'.** A: **Incorrect:** Scaling all points by \(c > 0\) multiplies both the maximum norm \(R\) and the margin \(\gamma\) by \(c\), leaving the mistake bound \(R^2/\gamma^2\) unchanged. B: **Incorrect:** If \(y_i (w^{*T} x_i) > 0\) for all \(i\), then \(y_i (w^{*T} (cx_i)) = c y_i (w^{*T} x_i) > 0\) for all \(i\) since \(c > 0\), so \(S'\) remains linearly separable. C: **Correct:** Because \(S'\) is linearly separable, the Perceptron Convergence Theorem guarantees convergence in a finite number of mistakes. D: **Correct:** At every step, the weight vector on \(S'\) is \(w' = c w\), so the final hyperplane \(\{x : (cw)^T x = 0\} = \{x : w^T x = 0\}\) is identical.

**1. Understand linear vs. non-linear decision boundaries in \(\mathbb{R}^d\):** A binary classifier has a linear decision boundary in the original feature space \(\mathbb{R}^d\) if the boundary between predicted classes \(+1\) and \(-1\) (or \(0\)) is a single hyperplane \(w^T x + b = 0\). If the boundary is curved, piecewise linear with multiple segments, or quadratic, it is non-linear in \(x\). **2. Analyze each classifier:** - **A. Perceptron:** Predicts \(\text{sign}(w^T x + b)\), so its decision boundary is the single hyperplane \(w^T x + b = 0\) (always linear). - **B. Logistic Regression:** Predicts positive when \(\sigma(w^T x + b) \ge 0.5 \iff w^T x + b \ge 0\), which is a single hyperplane (always linear). - **C. 1-Nearest-Neighbour (1-NN) with Euclidean distance:** Partitions the space into Voronoi cells around training points. When there are multiple training points, the boundary between classes is piecewise linear (composed of multiple hyperplane segments meeting at angles), which is non-linear overall. - **D. Decision tree using axis-aligned splits:** Partitions the feature space into axis-aligned rectangles, producing a step-like (piecewise axis-aligned) non-linear boundary. - **E. Gaussian Naive Bayes with different class-conditional variances:** Comparing log-posteriors \(\ln P(y=1|x) = \ln P(y=0|x)\) when \(\sigma_{1j}^2 \neq \sigma_{0j}^2\) leaves quadratic terms \(x_j^2\) that do not cancel, yielding a quadratic (non-linear) boundary. - **F. SVM with a linear kernel:** Learns \(f(x) = w^T x + b = 0\), which is always a linear hyperplane. - **G. SVM with an RBF (Gaussian) kernel:** Learns \(\sum_i \alpha_i y_i \exp(-\gamma \|x - x_i\|^2) + b = 0\), which is a curved non-linear boundary in \(\mathbb{R}^d\). **Answer: C, D, E, G — 1-NN, Decision tree, Gaussian Naive Bayes with unequal variances, and RBF-kernel SVM.** A: **Incorrect:** The perceptron decision boundary is \(w^T x + b = 0\), which is always a single linear hyperplane in \(\mathbb{R}^d\). B: **Incorrect:** Since \(\sigma(z) \ge 0.5 \iff z \ge 0\), logistic regression's boundary is \(w^T x + b = 0\), which is strictly linear in \(x\). C: **Correct:** With multiple training points, 1-NN forms a piecewise linear boundary made of Voronoi facets, which is non-linear as a whole. D: **Correct:** Axis-aligned splits create rectangular regions whose combined boundary is a step-function (non-linear) surface. E: **Correct:** Unequal class-conditional variances \(\sigma_{1j}^2 \neq \sigma_{0j}^2\) produce quadratic terms \(x_j^2\) in the log-odds ratio, creating a quadratic decision boundary. F: **Incorrect:** A linear kernel \(K(x, x') = x^T x'\) produces a linear hyperplane \(w^T x + b = 0\) in the input space. G: **Correct:** An RBF kernel maps inputs into an infinite-dimensional feature space, yielding a non-linear decision boundary in \(\mathbb{R}^d\).

**1. Recall the definition and derivatives of the sigmoid function:** The logistic sigmoid function is defined for all \(z \in \mathbb{R}\) as: \[g(z) = \frac{1}{1 + e^{-z}}\] **2. Check the symmetry property \(g(-z) = 1 - g(z)\):** Compute \(1 - g(z)\): \[1 - g(z) = 1 - \frac{1}{1 + e^{-z}} = \frac{e^{-z}}{1 + e^{-z}} = \frac{1}{e^z + 1} = g(-z)\] Thus, Statement A is **correct**. **3. Check monotonicity using the first derivative \(g'(z)\):** Differentiating \(g(z)\) gives: \[g'(z) = \frac{e^{-z}}{(1 + e^{-z})^2} = g(z)(1 - g(z))\] Since \(e^{-z} > 0\) for every real number \(z \in \mathbb{R}\), we have \(g'(z) > 0\) strictly for all \(z \in \mathbb{R}\). Therefore, \(g(z)\) is a **strictly increasing** function on \(\mathbb{R}\). Thus, Statement C is **correct** and Statement B is **incorrect**. **4. Check convexity using the second derivative \(g''(z)\):** Differentiating \(g'(z) = g(z)(1 - g(z))\) gives: \[g''(z) = g'(z)(1 - 2g(z)) = g(z)(1 - g(z))(1 - 2g(z))\] For \(z < 0\), \(g(z) < 0.5 \implies g''(z) > 0\) (convex). For \(z > 0\), \(g(z) > 0.5 \implies g''(z) < 0\) (concave). Since \(g(z)\) changes from convex to concave at \(z = 0\), it is not convex on all of \(\mathbb{R}\). Thus, Statement D is **incorrect**. **Answer: A, C — g(-z) = 1 - g(z) and g is a strictly increasing function.** A: **Correct:** Simplifying \(g(-z) = \frac{1}{1+e^z} = \frac{e^{-z}}{e^{-z}+1} = 1 - \frac{1}{1+e^{-z}} = 1 - g(z)\) confirms this identity for all \(z \in \mathbb{R}\). B: **Incorrect:** Because \(g'(z) = \frac{e^{-z}}{(1+e^{-z})^2} > 0\) for all \(z \in \mathbb{R}\), \(g\) has no flat regions and is strictly increasing. C: **Correct:** The derivative \(g'(z) = g(z)(1 - g(z))\) is strictly positive for all \(z \in \mathbb{R}\), proving that \(g\) is strictly increasing. D: **Incorrect:** For \(z > 0\), \(g(z) > 0.5\) and \(g''(z) < 0\), so \(g\) is concave on \((0, \infty)\), not convex on all of \(\mathbb{R}\).

**1. Understand the role of \(k\) in \(k\)-Nearest Neighbours (\(k\)-NN):** In \(k\)-NN regression or classification, the prediction at a query point \(x\) is obtained by averaging (or majority voting) over the \(k\) closest training examples: \[\hat{f}(x) = \frac{1}{k} \sum_{x_i \in N_k(x)} y_i\] **2. Analyze how changing \(k\) affects bias:** - When \(k\) is **increased**, we average over a larger neighbourhood around \(x\), pulling in points that are farther away and potentially have different true function values \(f(x_i)\). This smoothing makes the decision boundary simpler and less flexible, which **increases bias**. - When \(k\) is **decreased** (e.g., down to \(k = 1\)), the prediction relies only on the immediate local vicinity of \(x\), allowing the model to closely track the true underlying function and **decreasing bias**. **3. Analyze how changing \(k\) affects variance:** - Assuming independent noise \(\epsilon_i\) with variance \(\sigma^2\), the variance of the average of \(k\) neighbours scales as \(\frac{\sigma^2}{k}\). - Therefore, **increasing \(k\)** averages out random noise across more neighbours and **decreases variance**. - Conversely, **decreasing \(k\)** makes the prediction highly sensitive to the noise of individual nearby training points, which **increases variance**. **Answer: A, D — Increasing k increases bias, and decreasing k increases variance.** A: **Correct:** Larger \(k\) averages over a wider region of the feature space, smoothing out local patterns and increasing model bias. B: **Incorrect:** Decreasing \(k\) makes the model more flexible and local, which decreases bias rather than increasing it. C: **Incorrect:** Increasing \(k\) averages over more data points (variance \(\propto 1/k\)), which reduces variance rather than increasing it. D: **Correct:** Smaller \(k\) relies on fewer neighbours (e.g., a single noisy point at \(k=1\)), making predictions much more sensitive to sample noise and increasing variance.

**1. Evaluate each operation's effect on model complexity, bias, and variance:** Recall the bias-variance trade-off: operations that restrict a model's flexibility (regularization, pruning) increase bias and decrease variance, whereas operations that increase model capacity (deeper trees, more hidden units) decrease bias and increase variance. **2. Check each statement step by step:** - **Statement A:** Regularizing weights (e.g., L1/L2 penalty in linear or logistic regression) shrinks weight magnitudes toward zero, restricting model flexibility. This **increases bias** and **decreases variance**. (Correct!) - **Statement B:** Increasing the maximum depth of a decision tree makes the tree more complex and flexible, allowing it to fit finer details and noise. This **decreases bias** and **increases variance**, which is the opposite of Statement B. (Incorrect.) - **Statement C:** Increasing the number of hidden units in a neural network increases its representational capacity (expressiveness), which **decreases bias** and **increases variance**. (Correct!) - **Statement D:** In an SVM, the optimal weight vector \(w^* = \sum_{i \in SV} \alpha_i y_i x_i\) and bias \(b^*\) depend *only* on the support vectors (where \(\alpha_i > 0\)). Non-support vectors have \(\alpha_i = 0\), so removing them from the training set produces the exact same classifier, leaving both **bias and variance unchanged**. (Correct!) **Answer: A, C, D — Regularizing weights increases bias and decreases variance; adding hidden units decreases bias and increases variance; removing non-support vectors leaves bias and variance unchanged.** A: **Correct:** Weight regularization constrains the hypothesis space, trading a small increase in bias for a reduction in variance. B: **Incorrect:** Deeper decision trees have higher capacity and overfit more easily, meaning they have lower bias and higher variance. C: **Correct:** Adding hidden units increases the network's capacity to fit complex functions, decreasing bias while increasing variance. D: **Correct:** Non-support vectors have dual multipliers \(\alpha_i = 0\) and play no role in defining the decision boundary, so removing them does not alter the learned model.

**1. Set up the logistic regression threshold condition:** In logistic regression, the predicted probability of the positive class is given by the sigmoid function: \[P(y = 1 \mid x) = \sigma(w^T x) = \frac{1}{1 + e^{-w^T x}}\] We are told that a point is classified as positive if \(P(y = 1 \mid x) \ge 0.75\), and we want to express this decision rule in the equivalent linear form \(w^T x \ge \theta\). **2. Solve for the threshold \(\theta\):** Let \(z = w^T x\). Because \(\sigma(z)\) is strictly increasing, \(\sigma(z) \ge 0.75\) is equivalent to \(z \ge \theta\) where \(\sigma(\theta) = 0.75\): \[\frac{1}{1 + e^{-\theta}} = 0.75 = \frac{3}{4}\] Take the reciprocal of both sides: \[1 + e^{-\theta} = \frac{4}{3} \implies e^{-\theta} = \frac{1}{3} \implies e^{\theta} = 3\] Taking the natural logarithm of both sides: \[\theta = \ln(3) \approx 1.0986\] Rounding to two decimal places gives \(1.10\). **Answer: 1.10.**

**1. Identify the layer sizes of the feed-forward neural network:** We have a fully connected network with no bias terms and the following layer dimensions: - Input layer: \(n_0 = 5\) features - First hidden layer: \(n_1 = 10\) neurons - Second hidden layer: \(n_2 = 10\) neurons - Output layer: \(n_3 = 3\) neurons **2. Calculate the number of weights between each consecutive pair of layers:** In a fully connected layer without bias terms, the weight matrix connecting a layer of size \(n_{l-1}\) to a layer of size \(n_l\) has \(n_{l-1} \times n_l\) parameters: - Input to Hidden Layer 1: \(5 \times 10 = 50\) weights - Hidden Layer 1 to Hidden Layer 2: \(10 \times 10 = 100\) weights - Hidden Layer 2 to Output Layer: \(10 \times 3 = 30\) weights **3. Sum the weights across all layers:** \[\text{Total weights} = 50 + 100 + 30 = 180\] **Answer: 180.**

**1. Recall the normal equations for Ordinary Least Squares (OLS):** In ordinary least-squares linear regression, we seek \(w^*\) that minimizes the squared error loss: \[L(w) = \|y - Xw\|^2 = (y - Xw)^T (y - Xw)\] Setting the gradient with respect to \(w\) to zero gives the normal equation: \[X^T (y - Xw^*) = 0\] **2. Interpret the normal equation geometrically:** The vector \(\hat{y} = Xw^*\) is the orthogonal projection of \(y\) onto the column space \(\text{Col}(X)\), and \(e = y - Xw^*\) is the residual vector. The condition \(X^T(y - Xw^*) = 0\) means that the residual vector \(y - Xw^*\) is orthogonal to every column of \(X\), and therefore orthogonal to any linear combination of the columns of \(X\), including \(Xw^*\). **3. Derive the algebraic identity:** Premultiplying \(X^T(y - Xw^*) = 0\) by \((w^*)^T\) gives: \[(w^*)^T X^T (y - Xw^*) = (Xw^*)^T (y - Xw^*) = 0\] This holds for any input matrix \(X\) and target vector \(y\). **Answer: A — (Xw^*)^T (y - Xw^*) = 0.** A: **Correct:** Since \(X^T(y - Xw^*) = 0\), multiplying on the left by \((w^*)^T\) gives \((Xw^*)^T(y - Xw^*) = 0\), reflecting that the prediction \(Xw^*\) is orthogonal to the residual \(y - Xw^*\). B: **Incorrect:** The inner product \((Xw^*)^T(Xw^*) = \|Xw^*\|^2\) is zero only when the predicted vector \(Xw^*\) is the zero vector, not in general. C: **Incorrect:** We have \(y^T(y - Xw^*) = (y - Xw^* + Xw^*)^T(y - Xw^*) = \|y - Xw^*\|^2\), which equals the residual sum of squares and is non-zero whenever \(y \notin \text{Col}(X)\). D: **Incorrect:** The residual \(y - Xw^*\) is zero only if \(y\) lies in the column space of \(X\); in general, OLS only minimizes \(\|y - Xw\|^2\).

**1. Understand Leave-One-Out Cross-Validation (LOOCV) on an SVM:** We have a dataset \(\mathcal{D} = \{(x_1, y_1), \dots, (x_N, y_N)\}\) of \(N\) points. When trained on the full dataset \(\mathcal{D}\), the SVM has \(K\) support vectors. In LOOCV, for each \(n \in \{1, \dots, N\}\), we train an SVM on \(\mathcal{D} \setminus \{(x_n, y_n)\}\) and record the 0-1 test error \(e_n \in \{0, 1\}\) on the held-out point \((x_n, y_n)\). The LOOCV error is: \[E_{\text{CV}} = \frac{1}{N} \sum_{n=1}^{N} e_n\] **2. Analyze what happens when a non-support vector is left out:** Suppose \((x_n, y_n)\) is **not** a support vector of the SVM trained on the full dataset \(\mathcal{D}\). Then its optimal dual multiplier is \(\alpha_n = 0\), and it lies strictly on the correct side of the margin (\(y_n(w^T x_n + b) > 1\)). Because removing a point with \(\alpha_n = 0\) does not change the optimal SVM solution at all, the SVM trained on \(\mathcal{D} \setminus \{(x_n, y_n)\}\) is identical to the full SVM and classifies \((x_n, y_n)\) correctly! Thus, \(e_n = 0\) for all \(N - K\) non-support vectors. **3. Bound the total number of LOOCV errors:** Since only the \(K\) support vectors can possibly be misclassified when left out (\(e_n \le 1\) for support vectors, and \(e_n = 0\) for non-support vectors): \[\sum_{n=1}^{N} e_n \le K \implies E_{\text{CV}} = \frac{1}{N} \sum_{n=1}^{N} e_n \le \frac{K}{N}\] **Answer: A — E_CV <= K / N.** A: **Correct:** Removing any non-support vector leaves the SVM hyperplane unchanged and correctly classified (\(e_n = 0\)), so at most the \(K\) support vectors can contribute to the LOOCV error. B: **Incorrect:** Not every support vector is necessarily misclassified when removed (many remain on the correct side of the decision boundary), so \(E_{\text{CV}}\) can be strictly less than \(K/N\). C: **Incorrect:** A support vector on the margin boundary (\(y_i(w^T x_i + b) = 1\)) may still be classified correctly when held out, so \(E_{\text{CV}}\) is an upper bound \(\le K/N\), not always equal to \(K/N\). D: **Incorrect:** The number of support vectors \(K\) directly bounds the leave-one-out cross-validation error via \(E_{\text{CV}} \le K/N\).

**1. Write the objective and closed-form solution for 1D Ridge Regression:** In one-dimensional ridge regression without a bias term, we minimize the regularized squared error loss: \[J(w) = \sum_{i=1}^{n} (y_i - w x_i)^2 + \lambda w^2\] Taking the derivative with respect to \(w\) and setting it to zero: \[\frac{dJ}{dw} = -2 \sum_{i=1}^{n} x_i(y_i - w x_i) + 2\lambda w = 0\] \[\left(\sum_{i=1}^{n} x_i^2 + \lambda\right) w = \sum_{i=1}^{n} x_i y_i \implies w_{\text{ridge}} = \frac{\sum_{i=1}^{n} x_i y_i}{\sum_{i=1}^{n} x_i^2 + \lambda}\] **2. Substitute the given values:** We are given \(\sum_i x_i^2 = 10\), \(\sum_i x_i y_i = 4\), and \(\lambda = 10\). Substituting these into the formula: \[w_{\text{ridge}} = \frac{4}{10 + 10} = \frac{4}{20} = 0.20\] **Answer: 0.20.**

**1. Recall how PCA captures variance using the covariance matrix:** Given the covariance matrix \(\Sigma = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix}\), the variance captured by the first principal component equals the **largest eigenvalue** \(\lambda_{\max}\) of \(\Sigma\). **2. Find the eigenvalues of \(\Sigma\):** Solve the characteristic equation \(\det(\Sigma - \lambda I) = 0\): \[\det \begin{bmatrix} 3 - \lambda & 1 \\ 1 & 3 - \lambda \end{bmatrix} = (3 - \lambda)^2 - 1^2 = 0\] \[(3 - \lambda)^2 = 1 \implies 3 - \lambda = \pm 1\] Thus, the two eigenvalues are: - \(\lambda_1 = 3 + 1 = 4\) - \(\lambda_2 = 3 - 1 = 2\) **3. Conclude:** The largest eigenvalue is \(\lambda_1 = 4\), so the first principal component captures a variance of \(4\). **Answer: C — 4.** A: **Incorrect:** The value \(2\) is the smaller eigenvalue \(\lambda_2 = 3 - 1 = 2\), which corresponds to the second principal component. B: **Incorrect:** The value \(3\) is the variance of each individual original feature (diagonal entry), not the variance along the first principal component. C: **Correct:** The eigenvalues of \(\begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix}\) are \(3 + 1 = 4\) and \(3 - 1 = 2\); the largest eigenvalue \(4\) is the variance captured by the first principal component. D: **Incorrect:** The value \(6\) is the trace \(\text{Tr}(\Sigma) = 3 + 3 = 6\), which is the total variance across *both* principal components combined.

**1. Identify the probability distributions estimated in a Naive Bayes classifier:** We have a \(3\)-class classification problem (\(C = 3\)) with \(K\) discrete attributes, where each attribute takes \(V = 5\) possible values. A Naive Bayes model specifies: 1. The class prior probabilities \(P(Y = c)\) for \(c \in \{1, 2, 3\}\). 2. The class-conditional feature distributions \(P(X_k = v \mid Y = c)\) for each attribute \(k \in \{1, \dots, K\}\) and each class \(c \in \{1, 2, 3\}\). **2. Count the independent parameters for the class priors:** Since \(\sum_{c=1}^{3} P(Y = c) = 1\), knowing any \(3 - 1 = 2\) prior probabilities uniquely determines the third. Thus, the class priors require \(2\) independent parameters. **3. Count the independent parameters for the conditional distributions:** For a fixed class \(c\) and a fixed attribute \(X_k\), the probabilities over the \(5\) possible attribute values must sum to \(1\): \[\sum_{v=1}^{5} P(X_k = v \mid Y = c) = 1\] Thus, each attribute-class pair requires \(5 - 1 = 4\) independent parameters. Across \(3\) classes and \(K\) attributes, this gives: \[3 \times K \times 4 = 12K \text{ parameters}\] **4. Sum the parameters:** \[\text{Total independent parameters} = 12K + 2\] **Answer: B — 12K + 2.** A: **Incorrect:** This counts only \(1\) parameter per attribute per class (as for binary features) instead of \(5 - 1 = 4\) parameters for a 5-valued discrete attribute. B: **Correct:** We need \(3 - 1 = 2\) parameters for the 3 class priors, plus \(3 \times K \times (5 - 1) = 12K\) parameters for the class-conditional distributions, totaling \(12K + 2\). C: **Incorrect:** Naive Bayes assumes conditional independence across the \(K\) attributes given the class, avoiding an exponential number of parameters. D: **Incorrect:** The parameter count scales linearly with the number of attributes \(K\), not cubically.

**1. Recall the KKT optimality conditions for a soft-margin SVM (no bias term):** The primal problem minimizes \(\frac{1}{2}\|w\|^2 + C \sum_i \xi_i\) subject to \(y_i(w^T x_i) \ge 1 - \xi_i\) and \(\xi_i \ge 0\). With Lagrange multipliers \(\alpha_i \ge 0\) (for the margin constraints) and \(\beta_i \ge 0\) (for \(\xi_i \ge 0\)), the KKT conditions at the optimum include: 1. Stationarity w.r.t. \(\xi_i\): \(C - \alpha_i^* - \beta_i^* = 0 \implies \beta_i^* = C - \alpha_i^*\). 2. Complementary slackness: \[\alpha_i^* \big(y_i(w^{*T} x_i) - 1 + \xi_i^*\big) = 0 \quad \text{and} \quad \beta_i^* \xi_i^* = 0\] **2. Apply the given condition \(0 < \alpha_i^* < C\):** - Since \(\alpha_i^* < C\), stationarity gives \(\beta_i^* = C - \alpha_i^* > 0\). - From complementary slackness \(\beta_i^* \xi_i^* = 0\) and \(\beta_i^* > 0\), we must have \(\xi_i^* = 0\). - Since \(\alpha_i^* > 0\), the first complementary slackness condition requires: \[y_i(w^{*T} x_i) - 1 + \xi_i^* = 0\] Substituting \(\xi_i^* = 0\) gives \(y_i(w^{*T} x_i) = 1\). **3. Conclude:** A point with \(0 < \alpha_i^* < C\) lies exactly on the margin hyperplane (\(y_i(w^{*T} x_i) = 1\)) and has zero slack (\(\xi_i^* = 0\)). **Answer: C — y_i(w^{*T} x_i) = 1 and xi_i^* = 0.** A: **Incorrect:** Since \(y_i(w^{*T} x_i) = 1 > 0\), the point is correctly classified and lies right on the margin boundary. B: **Incorrect:** A positive slack \(\xi_i^* > 0\) requires \(\beta_i^* = 0\), which only happens when \(\alpha_i^* = C\), not when \(\alpha_i^* < C\). C: **Correct:** When \(0 < \alpha_i^* < C\), complementary slackness forces \(\beta_i^* = C - \alpha_i^* > 0 \implies \xi_i^* = 0\) and \(y_i(w^{*T} x_i) = 1 - \xi_i^* = 1\). D: **Incorrect:** From stationarity \(\alpha_i^* + \beta_i^* = C\), having \(\alpha_i^* < C\) implies \(\beta_i^* = C - \alpha_i^* > 0\).

**1. Analyze the requirements of the classification task:** We are given a binary classification dataset where the two classes are perfectly linearly separable, and our goal is to learn a **linear decision boundary** separating the classes (without requiring calibrated probability estimates). **2. Compare Perceptron, Logistic Regression, and Decision Trees:** - **Perceptron:** Directly learns a linear decision boundary \(w^T x + b = 0\) and is guaranteed to converge to a separating hyperplane in finitely many steps on any linearly separable dataset. - **Logistic Regression:** Also models a linear decision boundary \(w^T x + b = 0\) (where \(\sigma(w^T x + b) = 0.5\)). Both Perceptron and Logistic Regression are linear classifiers that separate the feature space with a single hyperplane. - **Decision Tree:** Splits the space using axis-aligned thresholds, producing a piecewise axis-aligned (non-linear) boundary rather than a single linear hyperplane in general. **3. Conclude:** Both Perceptron and Logistic Regression are linear classifiers that learn a linear decision boundary. **Answer: C — Both Perceptron and Logistic Regression.** A: **Incorrect:** While Perceptron learns a linear boundary, Logistic Regression is also a linear classifier whose decision boundary \(w^T x + b = 0\) is linear. B: **Incorrect:** Perceptron is also a standard linear classifier guaranteed to find a linear separating boundary on linearly separable data. C: **Correct:** Both Perceptron and Logistic Regression are linear classifiers that partition the feature space using a linear hyperplane \(w^T x + b = 0\). D: **Incorrect:** Decision trees produce axis-aligned rectangular partitions rather than a general linear hyperplane.

**1. Understand the geometry of clusters in Euclidean \(k\)-means:** In \(k\)-means clustering with Euclidean distance, each data point \(x\) is assigned to the cluster \(c\) whose centroid \(\mu_c\) is closest to \(x\). That is, cluster 3 consists of all points \(x\) satisfying: \[\|x - \mu_3\|^2 \le \|x - \mu_j\|^2 \quad \text{for all } j \in \{1, 2, 3\}\] Expanding both sides gives a linear inequality for each \(j\): \[2(\mu_j - \mu_3)^T x \le \|\mu_j\|^2 - \|\mu_3\|^2\] **2. Use the convexity of Voronoi cells:** Because each cluster assignment region (Voronoi cell) is the intersection of half-spaces, **every cluster region in Euclidean \(k\)-means is a convex set**. By definition of convexity, if two points \(p = (2, 2)\) and \(q = (2, -2)\) belong to cluster 3, then the entire line segment connecting \(p\) and \(q\) must also belong to cluster 3: \[x(t) = t(2, 2) + (1 - t)(2, -2) = (2,\; 4t - 2) \quad \text{for all } t \in [0, 1]\] **3. Check which candidate point lies on the segment between \((2, 2)\) and \((2, -2)\):** Setting \(t = 0.5\) (the midpoint of \((2, 2)\) and \((2, -2)\)) gives: \[x(0.5) = \frac{1}{2}(2, 2) + \frac{1}{2}(2, -2) = (2, 0)\] Therefore, \((2, 0)\) is guaranteed to belong to cluster 3 regardless of where the centroids are located. **Answer: C — (2, 0).** A: **Incorrect:** The point \((0, 0)\) does not lie on the line segment between \((2, 2)\) and \((2, -2)\), so it could easily be closer to another cluster's centroid. B: **Incorrect:** The point \((4, 0)\) is not a convex combination of \((2, 2)\) and \((2, -2)\), so its cluster assignment depends on the exact positions of the centroids. C: **Correct:** Voronoi cells in Euclidean \(k\)-means are convex sets; since \((2, 0) = \frac{1}{2}(2, 2) + \frac{1}{2}(2, -2)\) is the midpoint of two points in cluster 3, it must also belong to cluster 3. D: **Incorrect:** The point \((0, 2)\) does not lie on the line segment between \((2, 2)\) and \((2, -2)\), so it is not guaranteed to be in cluster 3.

**1. Determine the dual multipliers \(\alpha_1^*, \alpha_2^*, \alpha_3^*\) using KKT conditions:** We have a soft-margin SVM in \(\mathbb{R}^3\) with no bias term and \(C = 10\), trained on three points: - Point 1 (\(y_1 = +1\)): \(y_1(w^{*T} x_1) = 1.5 > 1\). Since this point is strictly outside the margin, its slack is \(\xi_1^* = 0\) and its margin constraint is inactive, so by complementary slackness \(\alpha_1^* = 0\) (which is why \(x_1\)'s coordinates are not needed!). - Point 2 (\(x_2 = (0.2, 0.3, 0.4),\; y_2 = +1\)): \(y_2(w^{*T} x_2) = 0.36 < 1\). Since \(y_2(w^{*T} x_2) < 1\), this point violates the margin and has positive slack \(\xi_2^* = 1 - 0.36 = 0.64 > 0\). By complementary slackness, \(\beta_2^* = 0 \implies \alpha_2^* = C = 10\). - Point 3 (\(x_3 = (0.15, 0.28, 0.35),\; y_3 = -1\)): \(y_3(w^{*T} x_3) = -0.306 < 1\). This point also has positive slack \(\xi_3^* = 1.306 > 0\), so \(\alpha_3^* = C = 10\). **2. Compute the optimal weight vector \(w^*\):** From the primal-dual relationship \(w^* = \sum_{i=1}^3 \alpha_i^* y_i x_i\): \[w^* = 0 \cdot (+1)x_1 + 10(+1)x_2 + 10(-1)x_3 = 10(x_2 - x_3)\] Substitute \(x_2 = (0.2, 0.3, 0.4)\) and \(x_3 = (0.15, 0.28, 0.35)\): \[w^* = 10(0.2 - 0.15,\; 0.3 - 0.28,\; 0.4 - 0.35) = 10(0.05, 0.02, 0.05) = (0.5, 0.2, 0.5)\] (Check: \(w^{*T} x_2 = 0.5(0.2) + 0.2(0.3) + 0.5(0.4) = 0.1 + 0.06 + 0.2 = 0.36\), matching the problem statement!) **3. Compute the perpendicular distance between \(w^T x = +1\) and \(w^T x = -1\):** First calculate the norm \(\|w^*\|\): \[\|w^*\| = \sqrt{0.5^2 + 0.2^2 + 0.5^2} = \sqrt{0.25 + 0.04 + 0.25} = \sqrt{0.54} \approx 0.734847\] The total margin width (perpendicular distance between \(w^T x = +1\) and \(w^T x = -1\)) is: \[\text{Distance} = \frac{2}{\|w^*\|} = \frac{2}{\sqrt{0.54}} \approx 2.721655\] Rounding to two decimal places gives \(2.72\). **Answer: 2.72.**

**1. Recall the definitions of Entropy and Information Gain:** For a node \(S\) with class proportions \(p_1, \dots, p_C\), the Shannon entropy is: \[H(S) = -\sum_{c=1}^{C} p_c \log_2(p_c)\] When \(S\) is split on a feature \(A\) into child nodes \(S_1, \dots, S_V\), the information gain is: \[\text{IG}(S, A) = H(S) - \sum_{v=1}^{V} \frac{|S_v|}{|S|} H(S_v)\] **2. Evaluate each statement:** - **Statement A:** If all child nodes \(S_v\) are perfectly pure (each containing only a single class), then \(H(S_v) = 0\) for every child \(v\). Substituting \(H(S_v) = 0\) into the formula gives \(\text{IG}(S, A) = H(S) - 0 = H(S)\), the entropy of the parent node. (Correct!) - **Statement B:** When all examples in a node belong to a single class \(c\), we have \(p_c = 1\) and \(p_j = 0\) for \(j \neq c\). Since \(-1 \log_2(1) = 0\), the entropy of a pure node is \(0\). (Correct!) - **Statement C:** By the concavity of entropy (Jensen's inequality), the weighted average of child entropies can never exceed the parent entropy, so \(\text{IG}(S, A) \ge 0\) always; information gain can never be negative. (Incorrect.) - **Statement D:** Although the *weighted average* entropy across all children cannot exceed \(H(S)\), an *individual* child node can easily have higher entropy than the parent! For example, if a parent has \(90\) positive and \(10\) negative samples (\(H \approx 0.47\)), and a split sends \(80\) positive samples to Child 1 (\(H = 0\)) and \(10\) positive + \(10\) negative samples to Child 2, then Child 2 has \(H = 1.0 > 0.47\). (Incorrect.) **Answer: A, B — Pure children give information gain equal to parent entropy, and a single-class node has entropy 0.** A: **Correct:** Pure child nodes have \(H(S_v) = 0\), so \(\text{IG}(S, A) = H(S) - 0 = H(S)\). B: **Correct:** When \(p_1 = 1\) and all other \(p_c = 0\), \(H(S) = -1 \log_2(1) = 0\). C: **Incorrect:** Because Shannon entropy is a concave function of the class distribution, conditioning on a feature can never increase expected entropy, so \(\text{IG}(S, A) \ge 0\) always. D: **Incorrect:** An individual child node can be more balanced (higher entropy) than a skewed parent node, as long as the weighted average across all children is at most the parent entropy.

**1. Understand how Bagging (Bootstrap Aggregating) works:** In bagging, \(M\) base learners \(\hat{f}_1, \dots, \hat{f}_M\) are trained independently on bootstrap samples of the training dataset, and their predictions are averaged: \[\hat{f}_{\text{bag}}(x) = \frac{1}{M} \sum_{m=1}^{M} \hat{f}_m(x)\] If each base learner has variance \(\sigma^2\) and pairwise correlation \(\rho\), the variance of the ensemble average is: \[\text{Var}(\hat{f}_{\text{bag}}(x)) = \rho \sigma^2 + \frac{1 - \rho}{M} \sigma^2\] **2. Evaluate each statement:** - **Statement A:** Since \(\rho \sigma^2 + \frac{1-\rho}{M}\sigma^2 < \sigma^2\) whenever \(\rho < 1\) and \(M > 1\), bagging reduces the variance of the prediction. (Correct!) - **Statement B:** The expected value of the average of identically distributed base learners equals the expected value of a single base learner (\(E[\hat{f}_{\text{bag}}] = E[\hat{f}_1]\)), so bagging does **not** substantially reduce bias (in fact, bootstrap sampling slightly increases bias). (Incorrect.) - **Statement C:** From the variance formula \(\rho \sigma^2 + \frac{1-\rho}{M}\sigma^2\), smaller pairwise correlation \(\rho\) (more diverse base learners) leads to a much larger reduction in variance. (Correct!) - **Statement D:** Because bagging reduces variance without reducing bias, it is most effective when applied to **low-bias, high-variance** base learners such as deep, unpruned decision trees. (Correct!) - **Statement E:** If every base learner produces identical predictions (\(\rho = 1\)), the average is identical to a single learner, so the variance remains \(\sigma^2\) (zero reduction). (Incorrect.) **Answer: A, C, D — Bagging reduces variance, helps most when base learners are diverse/weakly correlated, and works best with high-variance, low-bias base learners.** A: **Correct:** Averaging multiple bootstrap-trained models averages out sample-specific fluctuations, reducing prediction variance. B: **Incorrect:** The expectation of an average of identically distributed models equals the expectation of a single model, so bagging does not reduce bias. C: **Correct:** When base learners are weakly correlated (small \(\rho\)), the ensemble variance \(\rho\sigma^2 + \frac{1-\rho}{M}\sigma^2\) drops much more significantly. D: **Correct:** Since bagging targets variance rather than bias, pairing it with low-bias, high-variance learners like deep unpruned trees yields low overall error. E: **Incorrect:** Averaging \(M\) identical copies of a random variable gives the exact same random variable with the exact same variance.

**1. Write down the log-likelihood function for the given Gaussian model:** We are given independent observations \(y_i \sim \mathcal{N}(\log(w / x_i), 1)\) with unknown parameter \(w > 0\) and known positive inputs \(x_i > 0\). The probability density function for the \(i\)-th observation is: \[p(y_i \mid x_i, w) = \frac{1}{\sqrt{2\pi}} \exp\left( -\frac{1}{2}\big(y_i - \log(w / x_i)\big)^2 \right)\] Taking the natural logarithm and summing over all \(i\), the log-likelihood \(\ell(w)\) is: \[\ell(w) = -\frac{n}{2}\log(2\pi) - \frac{1}{2} \sum_{i} \big(y_i - \log w + \log x_i\big)^2\] **2. Differentiate \(\ell(w)\) with respect to \(w\) and set to zero:** Using the chain rule (where \(\frac{d}{dw} \log(w / x_i) = \frac{1}{w}\)): \[\frac{d\ell(w)}{dw} = -\sum_{i} \big(y_i - \log(w / x_i)\big) \cdot \left(-\frac{1}{w}\right) = \frac{1}{w} \sum_{i} \big(y_i - \log(w / x_i)\big) = 0\] **3. Simplify the Maximum Likelihood condition:** Since \(w > 0\), we can multiply both sides by \(w\) to obtain: \[\sum_{i} \big(y_i - \log(w / x_i)\big) = 0 \implies \sum_{i} y_i = \sum_{i} \log\left(\frac{w}{x_i}\right)\] **Answer: A — sum_i y_i = sum_i log(w / x_i).** A: **Correct:** Differentiating the sum of squared residuals \(\sum_i (y_i - \log(w/x_i))^2\) with respect to \(w\) multiplies each residual by \(-1/w\); factoring out \(1/w\) gives \(\sum_i y_i = \sum_i \log(w/x_i)\). B: **Incorrect:** The derivative of \(\log(w/x_i) = \log w - \log x_i\) with respect to \(w\) is \(1/w\) (independent of \(x_i\)), so there is no factor of \(x_i\) multiplying each residual. C: **Incorrect:** Because \(\frac{d}{dw}\log(w/x_i) = \frac{1}{w}\), the factor \(1/x_i\) cancels with \(x_i\) in the chain rule and does not appear as a weight on \(y_i\). D: **Incorrect:** The mean of \(y_i\) is \(\log(w/x_i)\), not \(w/x_i\), so the normal equation equates \(\sum_i y_i\) to \(\sum_i \log(w/x_i)\).