Unit 3: Linear & Probabilistic Classification Models - Practice Quiz

Supervised learning is defined by its use of a dataset where each data point is tagged with a correct label or output. The algorithm learns to map inputs to outputs based on these examples.

The Perceptron is a foundational algorithm for supervised learning of binary classifiers. It's a linear classifier that makes its predictions based on a linear predictor function combining a set of weights with the feature vector.

A single-layer Perceptron can only learn linearly separable patterns, meaning it separates the data points with a straight line (in 2D) or a hyperplane (in higher dimensions).

Logistic Regression is a classification algorithm. It models the probability that a given input point belongs to a certain class, making it suitable for tasks like spam detection or medical diagnosis.

The Sigmoid (or logistic) function, which has an 'S' shape, is used to squash the output of the linear model into the range [0, 1], which can be interpreted as a probability.

The entire algorithm is a direct application of Bayes' Theorem, which describes the probability of an event based on prior knowledge of conditions that might be related to the event.

The 'naïve' assumption is the simplifying belief that the features are conditionally independent. This assumption makes the computations much simpler, and despite being often incorrect in reality, the classifier works surprisingly well in practice.

'K' is a user-defined hyperparameter that specifies how many of the closest training examples are used to determine the class of a new data point via majority voting.

KNN is a lazy learning (or instance-based) algorithm because it doesn't build an explicit model during training. It simply stores the entire training dataset. The actual work of calculating distances and finding neighbors is deferred until a prediction is needed.

The path from the root to a leaf represents a series of rules or tests. The leaf node itself represents the final outcome or classification for a data point that follows that path.

Splitting criteria like Information Gain (based on entropy) or Gini Impurity are used to select the feature that will result in the 'purest' possible child nodes, effectively separating the classes as much as possible with that single split.

An SVM seeks to find a decision boundary (a hyperplane) that has the largest possible margin, or distance, between the data points of the different classes.

Support vectors are the critical data points that lie on the margin. These are the points that 'support' or define the position and orientation of the hyperplane. If any other point were removed, the hyperplane would not change.

A True Positive occurs when the actual class is positive, and the model's prediction is also positive. It represents a correct positive prediction.

Precision measures the accuracy of the positive predictions. It answers the question: 'Of all the instances that the model labeled as positive, what proportion were actually positive?'

Recall measures the model's ability to find all the actual positive samples. It answers the question: 'Of all the actual positive instances, what proportion did the model correctly identify?'

The Receiver Operating Characteristic (ROC) curve plots the True Positive Rate (TPR), also known as Recall or Sensitivity, on the y-axis versus the False Positive Rate (FPR) on the x-axis for various threshold settings.

An Area Under the ROC Curve (AUC-ROC) of 1.0 means the model has a True Positive Rate of 1 and a False Positive Rate of 0, perfectly distinguishing between all positive and negative classes.

A Precision-Recall (PR) curve plots Precision (y-axis) against Recall (x-axis) for different classification thresholds. It is a fundamental tool for evaluating classifiers.

In imbalanced datasets, the large number of true negatives can make the ROC curve look overly optimistic. The PR curve does not use true negatives in its calculations, so it provides a more accurate picture of a model's performance on the minority (positive) class.

The Perceptron Convergence Theorem states that the algorithm will converge and find a separating hyperplane in a finite number of steps if and only if the training data is linearly separable. While a small learning rate and feature normalization can affect the speed and stability of convergence, they do not provide the guarantee of convergence itself.

In logistic regression, the coefficients represent the change in the log-odds of the outcome for a one-unit change in the predictor. The odds ratio is calculated as . In this case, . This means that for each one-unit increase in smoking_years, the odds of having the disease are multiplied by 2, i.e., they double.

Even when the conditional independence assumption is violated, Naïve Bayes can still be an effective classifier. The assumption is mainly a mathematical convenience that simplifies the computation of posterior probabilities. Violations mean the output probabilities are not reliable, but as long as the correct class gets the highest probability, the classification (the argmax) will still be correct. This is known as the model being a good 'discriminative' classifier despite being a poor 'generative' one.

First, calculate Precision and Recall. \nPrecision = TP / (TP + FP) = 80 / (80 + 20) = 80 / 100 = 0.8. \nRecall = TP / (TP + FN) = 80 / (80 + 40) = 80 / 120 = 2/3 ≈ 0.67. \nThen, calculate the F1-Score: \nF1 = 2 (Precision Recall) / (Precision + Recall) = 2 (0.8 0.67) / (0.8 + 0.67) = 2 * 0.536 / 1.47 ≈ 1.072 / 1.47 ≈ 0.73.

When , the model's prediction for a new point is determined solely by its single nearest neighbor in the training set. This makes the model extremely sensitive to noise and individual data points, leading to a complex and jagged decision boundary. This represents low bias (it fits the training data very closely) and high variance (it changes drastically with small changes in the training data), which is characteristic of overfitting.

Gini Impurity is calculated as , where is the probability of a sample belonging to class . In this node, the total number of samples is 80. The probability of Class A is . The probability of Class B is . \nTherefore, Gini Impurity = . This represents the maximum impurity for a binary case.

The SVM's decision boundary and margin are determined exclusively by the support vectors—the data points that lie on the margin or are misclassified within the margin. Data points that are correctly classified and are far away from the margin (i.e., not support vectors) do not influence the model's hyperplane. Therefore, removing such a point will have no effect on the final decision boundary.

The ROC curve plots the True Positive Rate (TPR) against the False Positive Rate (FPR). A model with no discriminative power will have an ROC curve that follows the diagonal line from (0,0) to (1,1), which corresponds to random guessing. The area under this diagonal line is 0.5. A score of 1.0 indicates a perfect classifier, and a score of 0.0 indicates a perfectly inverse classifier.

The ROC curve's FPR (FP / (FP + TN)) can be misleading on imbalanced datasets. A huge number of true negatives (TN) can make the FPR appear very low even with a large number of false positives (FP). The PR curve, which focuses on precision (TP / (TP + FP)) and recall (TP / (TP + FN)), does not use TN. It is therefore more sensitive to changes in the number of false positives and provides a better picture of performance when the positive class is rare.

A false positive in a spam filter means a legitimate email ('ham') is incorrectly classified as spam. This is highly undesirable. Precision is calculated as TP / (TP + FP), where TP is spam correctly identified and FP is ham incorrectly identified as spam. Maximizing precision means minimizing the number of false positives. Recall (sensitivity) is less critical; missing a few spam emails (false negatives) is generally more acceptable than losing important emails.

The large gap between training and test accuracy is a classic sign of overfitting. The decision tree has learned the training data, including its noise, too well. Pre-pruning techniques, such as setting a max_depth or a minimum number of samples per leaf, restrict the tree's growth and complexity. This helps the model generalize better to unseen data, thus improving test set performance by reducing variance.

The parameter C controls the trade-off between maximizing the margin and minimizing the classification error on the training set. A large value of C places a high penalty on misclassified examples, forcing the model to create a smaller, more complex margin that correctly classifies more training points. This can lead to overfitting. Conversely, a small C allows for a wider margin and more misclassifications.

KNN relies on a distance metric (like Euclidean distance) to find the 'nearest' neighbors. If one feature has a much larger scale than others (e.g., salary in dollars vs. age in years), the distance will be almost entirely dominated by that single feature. Scaling brings all features to a comparable range, ensuring that each feature contributes more equally to the distance metric, leading to a more meaningful and robust model.

Logistic regression first computes a linear combination of the input features, . This output can range from to . The sigmoid function, , is then applied to squash this output into the range [0, 1]. This transformed value can be interpreted as the probability of the positive class, which is essential for binary classification.

The posterior probability calculation involves multiplying several conditional probabilities, including . If a word never appeared in the training data for any class, its conditional probability will be 0. Since the overall calculation is a product of these probabilities, the entire posterior probability for every class will become zero, making classification impossible. This is known as the 'zero-frequency problem,' which is solved by smoothing techniques like Laplace (add-one) smoothing.

If one model's ROC curve is consistently above another's, it means that for any given False Positive Rate (FPR), Model A achieves a higher True Positive Rate (TPR). This indicates that Model A is unambiguously better at discriminating between the classes. This will also result in a higher AUC-ROC for Model A. While it often correlates with higher accuracy and AUC-PR, it's not a mathematical guarantee for all possible thresholds or dataset imbalances.

Supervised learning requires labeled data—that is, data with a known outcome or target variable. Predicting loan approval, estimating house prices, and identifying handwritten digits are all supervised tasks (classification and regression). Grouping customers into segments without pre-defined labels is an example of unsupervised learning, specifically clustering, where the goal is to discover inherent patterns or structures in the data.

Decision Trees partition the feature space into a set of hyper-rectangles using a series of axis-aligned splits. The resulting decision boundary is composed of these rectangular regions, which is inherently non-linear (also called a piecewise linear boundary). In contrast, Perceptron, Logistic Regression, and Linear SVM all create linear decision boundaries by default.

The baseline for a Precision-Recall curve represents the performance of a 'no-skill' classifier that guesses randomly. Such a classifier would have a precision equal to the proportion of positive instances in the dataset, regardless of the recall value. Therefore, for a dataset with 20% positive instances, the baseline is a horizontal line at a precision level of 0.2.

The harmonic mean has a property of being closer to the smaller of the two numbers. This means that for the F1-score to be high, both precision and recall must be high. If one of the metrics is very low (e.g., Precision=1.0, Recall=0.1), the F1-score will be pulled down significantly (F1 ≈ 0.18), whereas a simple average would be misleadingly high (0.55). This property makes the F1-score a more robust measure for balancing the precision-recall trade-off.

The parameter in the RBF kernel defines the influence of a single training example. A small means a large radius of influence, so the model is influenced by points that are far away. This results in a smoother, less complex decision boundary, which is less likely to overfit but may have higher bias. Conversely, a large leads to a more complex boundary that is more sensitive to individual data points, increasing the risk of overfitting. Decreasing makes the model behave more like a linear SVM.

This phenomenon is known as complete or perfect separation. In this case, the likelihood function does not have a maximum. To perfectly classify the training data, the model tries to make the predicted probabilities for each class exactly 0 or 1. To achieve this, the input to the sigmoid function, , must go to or , which requires the weights to grow infinitely large. Regularization (L1 or L2) is the standard solution to this problem by adding a penalty term that prevents the weights from becoming too large.

When ROC curves cross, it means that neither model is universally better than the other across all possible classification thresholds. The choice depends on the specific application requirements. Model A performs better on the left side of the ROC plot (low FPR), which is the region of interest for applications where false positives are very costly (e.g., spam filtering, medical diagnosis where a false alarm leads to expensive procedures). This region corresponds to high-specificity, high-precision operating points. Model B would be better if maximizing the true positive rate is critical, even at the cost of accepting more false positives.

Naïve Bayes assumes that all features are conditionally independent given the class. In text, this is rarely true (e.g., the words 'San' and 'Francisco' are highly dependent). When features are dependent, the model multiplies their probabilities together, effectively 'double-counting' the evidence for a particular class. If several correlated words pointing to the same class appear, their multiplied probabilities can push the final posterior probability towards 0 or 1 much faster than is warranted. This leads to over-confident and poorly calibrated probability scores, even if the final classification decision (the argmax) is often correct.

Standard decision trees (like CART, ID3, C4.5) create axis-aligned splits. They cannot create diagonal splits. To approximate a diagonal decision boundary, the algorithm must make a series of horizontal and vertical cuts. This results in a 'stair-step' or jagged boundary. To create a fine-grained approximation of the diagonal line, the tree needs to be very deep, with many nodes each making a small refinement to the boundary. This is a classic limitation of decision trees and highlights their high variance and tendency to overfit data with non-axis-aligned structures.

In highly imbalanced datasets, AUC-ROC can be misleadingly optimistic. A model can achieve a high AUC-ROC by simply correctly classifying the majority negative class, which inflates the True Negative Rate. The Precision-Recall (PR) curve does not involve True Negatives and is thus more sensitive to improvements in positive class prediction. A random classifier on this dataset would have an AUC-PR close to the class imbalance ratio (0.001). Model Y's AUC-PR of 0.60 is far superior to Model X's 0.40, indicating it is much better at identifying fraudulent transactions with reasonable precision. Therefore, for tasks like fraud detection where the positive class is rare and important, the model with the higher AUC-PR should be preferred.

The Perceptron Convergence Theorem's central requirement is that the training data must be linearly separable. If a hyperplane that perfectly separates the classes exists, the algorithm is guaranteed to find one. However, if the data is not linearly separable, the algorithm will never find a solution that correctly classifies all points. As it corrects one misclassified point, it may misclassify another point that was previously correct. This leads to the decision boundary shifting back and forth indefinitely, and the weights will never stabilize. This is a fundamental limitation of the standard Perceptron algorithm.

The core issue of the curse of dimensionality for distance-based methods like KNN is that as the number of dimensions () increases, the volume of the space grows exponentially. To maintain the same density of data points, the number of required samples also needs to grow exponentially. With a fixed number of data points, the space becomes increasingly sparse. Consequently, the distance between any two points in the space becomes more uniform. The ratio of the distance to the nearest neighbor to the distance to the farthest neighbor approaches 1. This makes it difficult to distinguish between 'near' and 'far' neighbors, rendering the local neighborhood concept, which is central to KNN, unstable and less informative.

Micro-averaging aggregates the contributions of all classes to compute the average metric. It is essentially a global calculation of precision and recall, which means it is heavily weighted by the performance on the most frequent classes. A high micro-F1 (0.90) suggests good overall performance, dominated by the large number of correct predictions for class A. Macro-averaging computes the metric independently for each class and then takes the average, treating all classes equally. A low macro-F1 (0.60) indicates that the average performance per class is poor. The large discrepancy means that the high performance on class A is masking very poor performance on the rare classes B and C, which are being averaged down in the macro-F1 score.

L1 regularization (Lasso) promotes sparsity by adding a penalty proportional to the absolute value of the weights (). When faced with a group of highly correlated features, Lasso tends to be unstable and will arbitrarily pick one feature from the group to have a non-zero coefficient, while shrinking the coefficients of the other correlated features to exactly zero. L2 regularization (Ridge) adds a penalty proportional to the squared magnitude of the weights (). It does not perform feature selection in this way. Instead, it will shrink the coefficients of the correlated features together, distributing the 'importance' among them and keeping them all in the model with small, similar coefficient values.

Both the primal and dual SVM problems are convex. The key advantage of the dual formulation is that the data points only appear in the form of dot products (). This structure is what enables the kernel trick. Instead of performing an expensive, or even infinite-dimensional, explicit transformation and then computing the dot product , we can replace the dot product with a kernel function that computes the same value efficiently in the original feature space. This makes it computationally feasible to create non-linear decision boundaries in very high-dimensional feature spaces.

Decision trees are not rotation-invariant. Their splitting criteria are based on axis-aligned thresholds (e.g., ). When the data is rotated, a simple decision boundary in the original space may become a complex, diagonal one in the new, rotated space. The decision tree will have to approximate this new diagonal boundary with a large number of axis-aligned 'stair-step' splits. This will result in a much more complex and deeper tree, which is more likely to overfit the training data and generalize poorly to unseen data, thus leading to worse performance.

The decision boundary in a Gaussian Naïve Bayes (GNB) classifier occurs where the posterior probabilities are equal: . By expanding this using Bayes' theorem and the Gaussian PDF, and then taking the logarithm, the decision boundary is defined by an equation that is quadratic in the features . The quadratic terms come from the part of the Gaussian distribution. If the variance is assumed to be the same for both classes, the quadratic terms cancel out, resulting in a linear boundary. However, if the variances differ between classes, the boundary will be quadratic, which can take the form of a hyperbola, parabola, or ellipse/circle. Therefore, GNB is a linear classifier only under the specific condition of equal class variances.

One-hot encoding creates many new binary features. Consider a categorical feature 'City' with 100 unique values. One-hot encoding creates 100 new columns. If two data points differ in their 'City' (e.g., 'London' vs. 'Paris'), their one-hot vectors will be different in two positions (one is [..., 1, ..., 0, ...] and the other is [..., 0, ..., 1, ...]). In Euclidean distance, the squared difference for these two dimensions will be . This single categorical difference contributes a squared distance of 2. This might be a much larger value than the contribution from several scaled numerical features, causing the categorical feature to overwhelm the distance metric and unduly influence the choice of neighbors. This makes proper feature scaling and potentially using other distance metrics (like Hamming distance for the categorical part) crucial.

The ROC curve is created by plotting the True Positive Rate (TPR) against the False Positive Rate (FPR) at various threshold settings. Since this classifier outputs a constant probability, there is only one effective threshold. If we set the threshold below 0.6, all instances are classified as positive (TPR=1, FPR=1). If we set the threshold above 0.6, all instances are classified as negative (TPR=0, FPR=0). The ROC curve therefore consists of only two points: (0,0) and (1,1). The curve is the straight line connecting these two points. The area under this diagonal line is exactly 0.5. This represents the performance of a random classifier, which is what this model effectively is, as it cannot distinguish between positive and negative instances.

The standard Perceptron algorithm does not converge on non-linearly separable data. The Pocket Algorithm is a modification that addresses this. While the main Perceptron weight vector continues to be updated with every misclassification, the algorithm also maintains a separate weight vector in its 'pocket'. After each update, the new weight vector is evaluated on the entire training set. If it has fewer misclassifications than the vector currently in the pocket, it replaces it. After a set number of iterations, the algorithm returns the pocketed weight vector, not the final updated one. The trade-off is that it is more computationally expensive because it requires evaluating the entire dataset after each weight update, but it guarantees to find a reasonably good (though not necessarily optimal) solution even for non-separable data.

In a hard-margin SVM, all points must be correctly classified and be outside the margin. This is often impossible with real-world, noisy data. The soft-margin SVM introduces non-negative slack variables for each data point . The constraint becomes . If a point is correctly classified and outside the margin, . If it is on the margin or inside it (a margin violation), . If it is on the wrong side of the decision boundary (a misclassification), . The objective function is then modified to penalize the sum of these slack variables, controlled by the hyperparameter C. This allows the model to find a balance between maximizing the margin and minimizing the classification errors.

The bias-variance trade-off is a central concept in supervised learning. Bias is the error from erroneous assumptions in the learning algorithm. High bias (underfitting) means a model is too simple to capture the underlying patterns (e.g., fitting a line to a sine wave). Logistic Regression, being linear, has high bias if the true decision boundary is complex. Variance is the error from sensitivity to small fluctuations in the training set. High variance (overfitting) means a model is too complex and captures noise in the training data (e.g., a deep, unpruned decision tree fitting every single training point). This model will perform poorly on new data. The trade-off is that decreasing bias (by using a more complex model) often increases variance, and vice-versa.

Let . The log loss is . We need to find . Using the chain rule, . First, . A useful property of the sigmoid function is that its derivative is . Multiplying the two parts gives: . This remarkably simple form for the gradient is one reason why the combination of sigmoid and log loss is so widely used.

Information Gain is calculated as . First, we calculate the entropy of the parent node (). With 50 samples of each of the 2 classes (total 100), the proportions are and . The entropy is bit. Next, we calculate the entropy of the child nodes. The left child has 50 samples of Class 0 and 0 of Class 1, so it is a pure node. Its entropy is 0. The right child has 0 samples of Class 0 and 50 of Class 1, so it is also a pure node. Its entropy is 0. The weighted average entropy of the children is . Therefore, the Information Gain is bit. This represents the maximum possible information gain for a binary split, as the split perfectly resolves all uncertainty.