47:19
MLT | End-term | PYQ | T2(2024) | Detailed solution | IITM BS | Data Science | Machine learning
MLSquare
Overview
This video provides detailed solutions to past exam questions (PYQs) related to Machine Learning, specifically for the T2 (2024) term at IIT Madras BS. It covers a range of fundamental concepts including Principal Component Analysis (PCA), regularization techniques like Ridge loss, ensemble methods such as Bagging and Boosting, Support Vector Machines (SVMs) with both hard and soft margins, Naive Bayes, clustering, decision trees and information gain, kernel functions, logistic regression, perceptron algorithm, neural network architectures, and various loss functions like SSE, hinge loss, and logistic loss. The explanations often involve mathematical derivations and graphical interpretations to clarify the underlying principles.
How was this?
Save this permanently with flashcards, quizzes, and AI chat
Chapters
- The variance captured along a direction V is equal to the eigenvalue corresponding to the eigenvector V.
- In PCA, we focus on directions that are eigenvectors of the covariance matrix.
- The top two principal components capture variance equal to the sum of the two largest eigenvalues.
- The proportion of total variance captured by the top k components is the sum of the top k eigenvalues divided by the total sum of all eigenvalues.
Understanding how eigenvalues of the covariance matrix relate to variance is crucial for interpreting PCA results and determining how much information is retained by a reduced set of principal components.
Given eigenvalues 15, 5, 5, 0, 0, the top two components capture (15+5) / (15+5+5+0+0) = 20/25 = 80% of the variance.
- Ridge loss is defined as the sum of squared errors plus a penalty term proportional to the squared L2 norm of the weight vector (lambda * ||W||^2).
- The regularized loss on the training data decreases as the regularization parameter (lambda) increases.
- The function f(lambda) representing the model's performance on the training set is inversely proportional to lambda.
This section explains the trade-off between fitting the training data and keeping the model simple using regularization, which is key to preventing overfitting.
The graph shows that as lambda (regularization parameter) increases, the training loss decreases, implying an inverse relationship between the model's performance metric and lambda.
- Bagging combines base models with low bias and high variance using bootstrap aggregation (sampling with replacement).
- Boosting combines base models with high bias and low variance using an additive combination method.
- Random Forests use deep decision trees (high depth), while Boosting often uses shallow trees (decision stumps).
- Bagging can be parallelized, whereas Boosting requires sequential processing.
Differentiating between bagging and boosting helps in choosing the right ensemble method based on the characteristics of the base learners and the desired outcome (e.g., variance reduction vs. bias reduction).
Random Forests are an example of Bagging, and Gradient Boosted Decision Trees are an example of Boosting.
- In a hard margin SVM, the prediction for a new data point X is signum(W^T * X).
- The signum function outputs +1 if the input is positive and -1 if the input is negative.
- If the data point X and the weight vector W are in the same direction, W^T * X is positive, leading to a prediction of +1.
- If X and W are in opposite directions, W^T * X is negative, leading to a prediction of -1.
Understanding the prediction mechanism of hard margin SVMs is fundamental to how these models classify data points based on their position relative to the decision boundary and hyperplanes.
Given W and X1 in the same direction, W^T * X1 > 0, so Y1 = +1. Given W and X2 in opposite directions, W^T * X2 < 0, so Y2 = -1.
- The core idea of independence is that the joint probability of random variables is the product of their marginal probabilities.
- Naive Bayes applies this by assuming class conditional independence.
- Class conditional independence means the probability of observing features, given a class, can be calculated by multiplying the probabilities of each feature given that class.
The class conditional independence assumption simplifies the calculation of posterior probabilities in Naive Bayes, making it computationally efficient, though it might not always hold true in real-world data.
The joint probability P(feature1, feature2 | class) is assumed to be P(feature1 | class) * P(feature2 | class).
- To find the cluster boundary, calculate the mean of data points for each cluster.
- The cluster boundary is the perpendicular bisector of the line connecting the means of two clusters.
- If the means are (x1_mean, x2_mean) and (-x1_mean, -x2_mean), the boundary line passes through the origin.
- The equation of the boundary line is derived from the perpendicular bisector property.
This illustrates a geometric method for determining the decision boundary between two clusters, often used in unsupervised learning algorithms like K-means.
For cluster means (-2, -1) and (2, 1), the line connecting them has slope 1/2. The perpendicular bisector through the origin has equation 2x1 + x2 = 0.
- In a hard margin SVM, supporting hyperplanes are defined by W^T * X = 1 and W^T * X = -1.
- The distance from the origin to a hyperplane W^T * X = c is |c| / ||W||.
- The distance between the two supporting hyperplanes is twice the distance from the origin to one hyperplane.
- This distance is a measure of the margin's width.
The margin width is a key characteristic of SVMs, and calculating the distance between supporting hyperplanes quantifies this margin, which is related to the model's generalization ability.
For hyperplanes W^T * X = 1 and W^T * X = -1, the distance between them is 2 / ||W||. If W = [3, 4], ||W|| = 5, so the distance is 2/5.
- Information Gain measures the reduction in entropy achieved by splitting a dataset on a particular feature.
- Entropy quantifies the impurity or disorder of a set of data points.
- A pure node (all data points belong to the same class) has zero entropy.
- Information Gain = Entropy(parent) - Weighted Average Entropy(children).
Information gain is a fundamental metric used in building decision trees to select the best feature to split on at each node, aiming to create the most homogeneous child nodes.
Given a parent node with 50 positive and 150 negative examples, and children nodes with (50 pos, 50 neg) and (0 pos, 100 neg), the information gain is calculated using their respective entropies.
- A polynomial kernel of degree P is generally defined as K(X, Y) = (1 + X^T * Y)^P.
- Kernels map data into a higher-dimensional space where it might be linearly separable.
- The output of a kernel function should always be non-negative.
- For the polynomial kernel (1 + X^T * Y)^P, the output is guaranteed to be non-negative when P is an even number.
Understanding kernel functions is essential for using algorithms like SVMs with non-linearly separable data, as they allow for efficient computation in high-dimensional feature spaces.
A polynomial kernel of degree 2, K(X, Y) = (1 + X^T * Y)^2, will always produce a non-negative output.
- Data points where X1*X2 > 0 are in the first or third quadrant (excluding axes).
- If X1*Y > 0, points in the first quadrant have Y=+1, and points in the third quadrant have Y=-1.
- Such data is linearly separable with a positive margin.
- The Perceptron algorithm is guaranteed to converge in a finite number of iterations if the data is linearly separable and has a positive margin.
This connects the geometric properties of data points (quadrant location, sign of products) to the theoretical guarantees of learning algorithms like the Perceptron.
Data where X1*X2 > 0 and X1*Y > 0 is linearly separable with a positive margin, ensuring Perceptron convergence.
- The probability of a test point belonging to class 1 in logistic regression is P(Y=1|X) = 1 / (1 + exp(-(W^T * X + b))).
- If biases are ignored (b=0), P(Y=1|X) = 1 / (1 + exp(-W^T * X)).
- Given a probability, we can infer the value of W^T * X.
- Different weight vectors W can result in the same W^T * X value for a specific input X.
This demonstrates how to reverse-engineer the relationship between input features, weights, and predicted probabilities in logistic regression.
If P(Y=1|X=1,1) = 1 / (1 + exp(2)), then W^T * X = -2. For X=[1,1], this implies W1 + W2 = -2.
- The Perceptron algorithm starts with a zero weight vector.
- When a misclassification occurs for data point X with label Y, the weight vector W is updated as W_new = W_old + Y*X.
- The final weight vector is a linear combination of the data points that caused updates.
- The coefficients of this linear combination are the labels (Y_i), which are integers (+1 or -1).
This explains the mathematical basis for the Perceptron's weight updates and shows that the resulting weight vector is constrained to be an integer linear combination of the input data points.
The final weight vector W can be expressed as the sum of Yi * Xi for all data points i that triggered an update.
- The primal SVM problem maximizes ||W||^2/2 subject to Y_i * (W^T * X_i) >= 1.
- The dual problem involves optimizing Lagrange multipliers (alpha_i).
- The optimal weight vector W* is a linear combination of support vectors: W* = sum(alpha_i * Y_i * X_i).
- Complementary slackness conditions link alpha_i and the margin constraints: alpha_i > 0 implies Y_i * (W*^T * X_i) = 1 (data point is a support vector).
Understanding the dual formulation and complementary slackness is key to grasping how SVMs identify support vectors and the relationship between them and the optimal hyperplane.
If alpha_i > 0, then the data point X_i lies on one of the supporting hyperplanes (Y_i * W*^T * X_i = 1), making X_i a support vector.
- Soft margin SVM minimizes ||W||^2/2 + C * sum(zeta_i), where zeta_i are slack variables.
- Slack variables (zeta_i) allow for some misclassifications or margin violations.
- The hyperparameter C controls the trade-off between maximizing the margin and minimizing classification errors.
- A very large C approximates hard margin SVM, while C=0 leads to W=0 and large zeta_i.
The soft margin formulation makes SVMs robust to noisy or non-linearly separable data by allowing controlled errors, with the hyperparameter C tuning this flexibility.
A large C penalizes margin violations heavily, pushing the model towards a hard margin solution, while a small C allows more violations for a wider margin.
- Three key conditions govern the optimal solution in soft margin SVM:
- 1. alpha_i * (1 - Y_i * W^T * X_i - zeta_i) = 0
- 2. beta_i * (-zeta_i) = 0
- 3. alpha_i + beta_i = C (where alpha_i, beta_i are Lagrange multipliers and C is the regularization parameter).
These conditions are crucial for deriving the properties of support vectors and slack variables in soft margin SVMs, helping to determine their values and relationships.
If alpha_i > 0 and beta_i > 0, then zeta_i must be 0 and Y_i * W^T * X_i = 1 (a support vector on the margin). If alpha_i = C, then beta_i = 0, implying zeta_i = 0.
- Zero-one loss is the ideal but non-convex loss function for classification.
- Squared loss ( (W^T*X*Y - 1)^2 ) is a convex surrogate but can be overly sensitive to outliers.
- Hinge loss ( max(0, 1 - W^T*X*Y) ) is used in SVMs and is convex.
- Logistic loss ( log(1 + exp(-W^T*X*Y)) ) is another convex surrogate, commonly used in logistic regression.
Understanding different loss functions helps in choosing the appropriate algorithm for a classification task, as each function has different properties and implications for model training.
The green curve represents the hinge loss, the red curve the logistic loss, and the blue curve the perceptron loss (max(0, -W^T*X*Y)).
- Logistic loss is log(1 + exp(-W^T*X*Y)).
- Hinge loss is max(0, 1 - W^T*X*Y).
- The intersection occurs when the logistic loss equals the non-zero part of the hinge loss: log(1 + exp(-z)) = 1 - z, where z = W^T*X*Y.
- Solving this equation leads to W^T*X*Y = log(e-1).
Finding the intersection point helps compare the behavior of different loss functions and understand where their predictions or gradients might align or diverge.
Setting log(1 + exp(-z)) = 1 - z and solving for z yields z = log(e-1).
- A neural network's architecture defines the number of layers, neurons per layer, and connections.
- Weights connect neurons between layers; biases are typically added to neuron inputs (ignored here).
- The total number of weights is the sum of weights required for each layer's connections.
- Input layer size, hidden layer sizes, and output layer size determine the total weight count.
Understanding network architecture is fundamental to calculating the model's capacity (number of parameters) and computational cost.
For 5 inputs, two hidden layers of 100 neurons each, and 1 output neuron (ignoring biases), the weights are (5*100) + (100*100) + (100*1) = 500 + 10000 + 100 = 10600 weights.
- Binary Cross-Entropy loss is calculated as -[Y*log(P) + (1-Y)*log(1-P)], where P is the predicted probability.
- P must be strictly between 0 and 1 to avoid log(0) or log(1) issues.
- The sigmoid activation function outputs values in the range (0, 1), making it suitable for binary cross-entropy.
- ReLU and linear activations can output 0 or values outside (0,1), making them less suitable for direct use with binary cross-entropy.
Choosing the correct activation function for the output layer is critical for ensuring the model outputs valid probabilities required by loss functions like binary cross-entropy.
Sigmoid function outputs are always in (0,1), preventing undefined log terms in the binary cross-entropy calculation.
- SSE for a single data point is (W^T*X - Y)^2, where Y is the true label and W^T*X is the predicted value (Y-hat).
- The gradient of SSE with respect to the weight vector W is 2 * (W^T*X - Y) * X.
- This can be written as 2 * (Y-hat - Y) * X.
- This gradient indicates the direction and magnitude to adjust weights to minimize SSE.
Calculating the gradient of the SSE loss is essential for optimization algorithms like gradient descent, which iteratively update weights to minimize prediction errors.
The gradient of SSE with respect to W is 2 * (predicted_value - true_value) * input_vector.
Key takeaways
- Eigenvalues of the covariance matrix directly represent the variance captured along the corresponding eigenvector directions, a core concept in PCA.
- Regularization techniques like Ridge loss help prevent overfitting by penalizing large weights, balancing model complexity with data fit.
- Bagging and Boosting are ensemble methods that combine multiple models; Bagging reduces variance by averaging, while Boosting reduces bias by sequentially correcting errors.
- SVMs aim to find the widest margin separating classes, with support vectors being the critical data points defining this margin.
- Naive Bayes relies on the strong assumption of class conditional independence to simplify probability calculations.
- The Perceptron algorithm guarantees convergence on linearly separable data, and its resulting weights are integer linear combinations of data points.
- Soft margin SVMs provide flexibility by allowing some misclassifications, controlled by the hyperparameter C, making them robust to noisy data.
- Different loss functions (hinge, logistic, squared) serve as convex surrogates for the non-convex zero-one loss in classification, each with distinct properties.
- The choice of activation function (e.g., sigmoid) is crucial for ensuring valid probability outputs required by specific loss functions like binary cross-entropy.
Key terms
Covariance MatrixEigenvaluesPrincipal Component Analysis (PCA)Ridge LossL2 NormBaggingBoostingBootstrap AggregationSupport Vector Machine (SVM)Hard MarginSoft MarginSupporting HyperplanesNaive BayesClass Conditional IndependenceInformation GainEntropyKernel FunctionPolynomial KernelPerceptron AlgorithmLinearly SeparableLogistic RegressionBinary Cross-EntropySigmoid FunctionSum of Squared Errors (SSE)
Test your understanding
- How does the eigenvalue of a covariance matrix relate to the variance explained by its corresponding eigenvector in PCA?
- What is the primary trade-off managed by the regularization parameter lambda in Ridge loss, and how does it affect the model?
- Explain the fundamental difference in the bias-variance characteristics of base models used in Bagging versus Boosting.
- What are support vectors in the context of SVMs, and how do the complementary slackness conditions help identify them?
- Under what conditions is the Perceptron algorithm guaranteed to converge, and what is the nature of the resulting weight vector?
- Why is the sigmoid activation function typically preferred for the output layer when using binary cross-entropy loss?
- How does the hyperparameter C in soft margin SVM influence the model's tolerance for misclassifications and margin violations?