Unit 3: SUPERVISED LEARNING: CLASSIFICATION - Subjective Questions

Lazy learning is an approach in which the algorithm postpones model construction until a prediction is required. The training data is stored, and generalization is performed during the query phase.

Working of -NN:

• Select a value of , representing the number of neighboring examples to consider.
• Calculate the distance between the query instance and every training instance, commonly using Euclidean distance:
  
• Select the closest training instances.
• Assign the query instance to the class receiving the majority vote.
• A distance-weighted version can give greater influence to closer neighbors.

The method is simple and requires almost no training time, but prediction can be expensive for large datasets.

The main factors affecting -NN performance are:

• Choice of : A small gives low bias but may be sensitive to noise. A large produces smoother decision boundaries but can cause underfitting.
• Distance measure: Euclidean, Manhattan, or cosine distance may be appropriate depending on the data.
• Feature scaling: Features with larger numerical ranges can dominate the distance calculation. Normalization or standardization is therefore important.
• Irrelevant features: Uninformative variables can distort distances and reduce classification accuracy.
• Class imbalance: Majority voting may favor the dominant class. Weighted voting or resampling can help.
• Computational cost: Prediction requires distance calculations against stored examples, which can be costly for large datasets.

The value of is usually selected using validation or cross-validation.

Naive Bayes is a probabilistic classifier based on Bayes' theorem. For a class and feature vector :

Since is common to all classes, classification is based on:

The naive assumption is that features are conditionally independent given the class:

Therefore, the decision rule becomes:

• is the prior probability of the class.
• is the likelihood of feature given the class.
• The probabilities are estimated from training data.

Naive Bayes is computationally efficient and performs well in text classification, although the independence assumption may not always hold.

Naive Bayes assumes that features are conditionally independent given the class. Thus, for features :

Advantages:

• Simplifies estimation of the joint probability distribution.
• Requires relatively little training data.
• Reduces computational complexity.
• Works effectively in high-dimensional applications such as document classification.
• Produces fast training and prediction.

Limitations:

• Real-world features are often correlated.
• Probability estimates may be inaccurate when the independence assumption is violated.
• A zero probability for an unseen feature value can make the entire product zero.
• Laplace smoothing is commonly used to avoid zero-frequency problems.

Although the assumption is often unrealistic, Naive Bayes can still classify accurately because the relative ranking of class probabilities may remain useful.

Decision tree construction follows a recursive divide-and-conquer strategy:

• Begin with the complete training dataset at the root node.
• Select the feature and split point that best separates the classes.
• Divide the dataset into subsets according to the selected test.
• Recursively repeat the process for each subset.
• Stop splitting when a stopping condition is reached, such as a pure node, maximum depth, minimum number of samples, or lack of useful improvement.
• Assign a class label to each leaf, usually the majority class of its training examples.

Common split criteria include information gain, gain ratio, and Gini impurity. The resulting tree represents a sequence of decisions from the root to a leaf. Pruning may be applied afterward to reduce overfitting.

Information gain measures the reduction in uncertainty after splitting a dataset using an attribute.

For a dataset containing classes , entropy is:

where is the proportion of examples belonging to class .

If attribute partitions into subsets , the expected entropy after the split is:

Therefore, information gain is:

The attribute with the highest information gain is selected for the split. A high value indicates that the attribute produces purer child nodes and reduces class uncertainty effectively. Information gain can favor attributes with many distinct values, so gain ratio is sometimes preferred.

Gini impurity measures the probability of incorrectly classifying an example if it is randomly labeled according to the class distribution in a node.

For a node containing classes:

where is the proportion of class in the node. Gini impurity is zero when all examples belong to one class and is highest when classes are evenly distributed.

Comparison:

• Entropy: Uses logarithms and is based on information theory.
• Gini impurity: Uses squared probabilities and is generally faster to compute.
• Both prefer splits that produce purer child nodes.
• Entropy and Gini often produce similar trees, although their selected splits can differ.
• Gini is commonly used in CART decision trees, while information gain is associated with algorithms such as ID3.

The best criterion depends on the implementation and validation performance.

A decision tree overfits when it learns noise and exceptional patterns in the training data instead of general relationships. Such a tree may have very high training accuracy but poor performance on unseen data.

Methods for controlling overfitting:

• Pre-pruning: Stop tree growth using maximum depth, minimum samples per split, minimum samples per leaf, or a minimum impurity decrease.
• Post-pruning: Grow a large tree and remove branches that provide little predictive benefit.
• Cost-complexity pruning: Optimize a criterion such as:
  
  where is the tree error, is the number of leaves, and controls the penalty for complexity.
• Cross-validation: Select the depth or pruning parameter using validation data.
• Ensembles: Random forests and boosting can improve generalization by combining multiple trees.

The objective is to balance model complexity and predictive accuracy.

Each path from the root of a decision tree to a leaf can be converted into one classification rule.

Conversion procedure:

• Start at the root node.
• Record every condition encountered along a path.
• Join conditions on the same path using AND.
• Assign the class at the leaf as the rule conclusion.
• Repeat for all root-to-leaf paths.

For example:

IF income is high AND credit score is good THEN approve loan.

Advantages of rules:

• Easier for humans to interpret than a large tree.
• Each rule provides an independent explanation for a prediction.
• Rules can be simplified or edited by domain experts.
• They are useful for knowledge representation and auditing.
• Individual rules can reveal important combinations of conditions.

A rule system must also define how conflicts are handled when multiple rules apply.

An SVM finds a decision boundary, called a hyperplane, that separates two classes while maximizing the margin between the classes.

A linear hyperplane is represented as:

For labeled examples where , the hard-margin constraints are:

The margin is inversely proportional to , so maximizing the margin is equivalent to minimizing:

The closest training examples to the boundary are called support vectors. They determine the position of the optimal hyperplane.

SVMs can use kernels to construct nonlinear decision boundaries in an implicit higher-dimensional feature space. They are effective in high-dimensional spaces but may require careful parameter and feature scaling.

Hard-margin SVM:

• Assumes the data is perfectly linearly separable.
• Does not allow classification errors or margin violations.
• Can be highly sensitive to noise and outliers.

Soft-margin SVM:

• Allows some examples to lie inside the margin or be misclassified.
• Introduces slack variables and minimizes:
  
• Works better when data is noisy or not perfectly separable.

The parameter controls the trade-off between margin width and training errors:

• A large strongly penalizes errors, producing a narrower margin and potentially overfitting.
• A small allows more violations, producing a wider margin and potentially better generalization.

The value of is commonly selected using cross-validation.

The kernel trick allows an SVM to learn nonlinear decision boundaries without explicitly transforming data into a high-dimensional feature space. It replaces inner products with a kernel function:

where maps the original input into another feature space.

Common kernels include:

• Linear kernel:
  
  Suitable when classes are approximately linearly separable.
• Polynomial kernel:
  
  Useful for polynomial relationships.
• Radial basis function kernel:
  
  Suitable for complex nonlinear patterns.
• Sigmoid kernel:
  

Kernel choice and parameters such as and degree strongly affect model performance.

A confusion matrix compares actual class labels with predicted labels.

• True Positive (TP): A positive instance is correctly predicted as positive.
• True Negative (TN): A negative instance is correctly predicted as negative.
• False Positive (FP): A negative instance is incorrectly predicted as positive. This is also called a Type I error.
• False Negative (FN): A positive instance is incorrectly predicted as negative. This is also called a Type II error.

The confusion matrix is the basis for accuracy, precision, recall, specificity, and the F1 score. It is particularly important for imbalanced datasets because it reveals the types of errors hidden by aggregate accuracy.

Accuracy is the proportion of all predictions that are correct. Using the confusion matrix:

The numerator contains correct positive and negative predictions, while the denominator contains all predictions.

Accuracy can be misleading when:

• The classes are highly imbalanced.
• One class is much more important than the other.
• The costs of false positives and false negatives are different.

For example, if 99% of transactions are legitimate, a classifier that always predicts legitimate may achieve 99% accuracy while detecting no fraud. Therefore, accuracy should be considered along with precision, recall, the confusion matrix, and metrics such as AUC or logarithmic loss.

Accuracy is most informative when classes are reasonably balanced and error costs are similar.

Logarithmic loss evaluates the quality of predicted probabilities rather than only the final class labels. For a binary target and predicted probability for class :

Interpretation:

• If , the contribution is .
• If , the contribution is .
• A confident correct prediction produces a small loss.
• A confident incorrect prediction produces a very large loss.
• A random probability of gives a loss of approximately per observation.

Logarithmic loss rewards well-calibrated probabilities and heavily penalizes overconfident errors. It is useful when predicted probabilities are used for risk estimation or decision-making.

The ROC curve evaluates a binary classifier over different decision thresholds. It plots:

• True Positive Rate (TPR):
  
• False Positive Rate (FPR):
  

Each threshold produces one point. Joining these points forms the ROC curve.

The Area Under the Curve (AUC) is the area beneath the ROC curve and summarizes ranking performance:

• : Perfect discrimination.
• : Performance equivalent to random ranking.
• : Usually indicates reversed predictions or poor ranking.

AUC can be interpreted as the probability that the classifier assigns a higher score to a randomly chosen positive example than to a randomly chosen negative example. It is threshold-independent, but it may be less informative than precision-recall analysis for highly imbalanced data.

Precision and recall measure different aspects of positive-class performance.

Precision is the proportion of predicted positives that are actually positive:

It answers: Of all instances predicted as positive, how many were correct?

Recall, also called sensitivity or true positive rate, is the proportion of actual positives that are detected:

It answers: Of all actual positive instances, how many were found?

Increasing the decision threshold often reduces false positives and improves precision, but it may increase false negatives and reduce recall. Lowering the threshold usually increases recall but can reduce precision.

For example, in disease screening, high recall may be prioritized to avoid missing patients. In an expensive follow-up process, high precision may be more important to reduce unnecessary investigations.

The F1 score combines precision and recall using their harmonic mean:

Substituting the confusion-matrix formulas gives:

The harmonic mean is used because it gives a low score when either precision or recall is low. Thus, a model cannot obtain a high F1 score by optimizing only one of these measures.

Usefulness:

• Appropriate when both false positives and false negatives matter.
• More informative than accuracy for imbalanced datasets.
• Provides a single summary of positive-class performance.

Limitation: The F1 score ignores true negatives and assumes precision and recall have equal importance. When their importance differs, the weighted score can be used.

These metrics evaluate different properties of a classifier:

• Accuracy: Measures the fraction of correct labels. It is simple but can be misleading under class imbalance.
• Precision: Measures the reliability of positive predictions and penalizes false positives.
• Recall: Measures how many actual positives are detected and penalizes false negatives.
• F1 score: Combines precision and recall using the harmonic mean.
• Logarithmic loss: Evaluates the quality and calibration of predicted probabilities, strongly penalizing confident errors.
• AUC: Measures the ability to rank positive instances above negative instances across all thresholds.

The choice depends on the application. Recall is important when missed positives are costly, precision is important when false alarms are costly, F1 is useful for balancing both, log loss is appropriate for probability quality, and AUC is useful for threshold-independent ranking comparison.

The total number of observations is:

Accuracy:

Precision:

Recall:

F1 score:

The model has high overall accuracy and detects approximately 88.89% of positive cases. Of the cases predicted positive, 80% are genuinely positive. The F1 score of approximately 0.842 indicates a reasonably good balance between precision and recall.