Unit 5: Machine learning-2 - Subjective Questions

A Support Vector Machine (SVM) is a supervised machine learning algorithm used for classification and regression tasks. It works by finding an optimal decision boundary (hyperplane) that best separates data points of different classes.

Hyperplane:

• A hyperplane is a decision boundary that separates classes in the feature space.
• In a 2D space it is a line, in 3D space it is a plane, and in higher dimensions it is called a hyperplane.
• The equation of a hyperplane is given by: where is the weight vector and is the bias.

Support Vectors:

• Support vectors are the data points that lie closest to the hyperplane.
• They are critical because they define the position and orientation of the hyperplane.
• Removing a support vector would change the position of the hyperplane, while removing other points would not.

Key Idea:

• SVM aims to maximize the margin, which is the distance between the hyperplane and the nearest data points of either class.
• A larger margin generally leads to better generalization on unseen data.

Margin in SVM:

• The margin is the distance between the separating hyperplane and the closest data points (support vectors) from either class.
• SVM seeks to find the maximum margin hyperplane because a wider margin reduces the generalization error.
• The margin width is given by so maximizing the margin is equivalent to minimizing .

Hard Margin Classifier:

• Assumes the data is perfectly linearly separable.
• No misclassification is allowed; all points must lie on the correct side of the margin.
• Very sensitive to outliers and noise.
• Optimization: minimize subject to .

Soft Margin Classifier:

• Allows some misclassifications by introducing slack variables .
• Useful when data is not perfectly separable or contains noise.
• Optimization: minimize
• The parameter C controls the trade-off between maximizing the margin and minimizing classification errors.

Summary:

• Hard margin: strict, no errors, requires separable data.
• Soft margin: flexible, tolerates errors, works with real-world noisy data.

Kernel Trick:

• The kernel trick is a technique that allows SVM to handle non-linearly separable data by implicitly mapping the input features into a higher-dimensional space.
• Instead of computing the transformation explicitly, the kernel function computes the dot product in the higher-dimensional space directly:
  
• This avoids the heavy computation of explicit transformations, making it computationally efficient.

Common Kernel Functions:

• Linear Kernel: Used when data is linearly separable.

• Polynomial Kernel: Captures polynomial relationships of degree .

• Radial Basis Function (RBF) / Gaussian Kernel: Handles complex non-linear boundaries; very popular.

• Sigmoid Kernel: Behaves like a neural network activation.

Advantage: The kernel trick enables SVM to create complex decision boundaries without explicitly increasing computational cost.

Setup:
Consider a binary classification problem with data points where . The hyperplane is defined as:

Decision Rule:

• For positive class:
• For negative class:

Combined constraint:

Margin Calculation:

• The distance from a point to the hyperplane is
• For support vectors, , so the distance from each side is .
• Total margin width =

Optimization Objective:

• To maximize the margin , we minimize .
• For mathematical convenience (differentiability), we minimize .

Final Formulation:

Why minimizing maximizes margin:

• Margin is inversely proportional to .
• A smaller gives a larger margin, which improves generalization and reduces overfitting.

This is a convex quadratic optimization problem solved using Lagrange multipliers.

A Decision Tree is a supervised learning algorithm used for both classification and regression tasks. It models decisions in a tree-like structure where data is split based on feature values.

Structure of a Decision Tree:

• Root Node: The topmost node representing the entire dataset, which gets divided.
• Internal/Decision Nodes: Nodes that represent a test on a feature (attribute).
• Branches: Outcomes of a test, connecting nodes.
• Leaf/Terminal Nodes: Final nodes that give the predicted class or value.

How Predictions are Made:

1. Start at the root node.
2. At each internal node, a test is applied on a feature (e.g., Is age > 30?).
3. Follow the branch corresponding to the test result.
4. Repeat until a leaf node is reached.
5. The leaf node's label is returned as the prediction.

Example:

• For a loan approval system, the tree might first check income, then credit score, then employment status to decide approval.

Advantages:

• Easy to understand and interpret (white-box model).
• Requires little data preprocessing.
• Handles both numerical and categorical data.

Entropy:

• Entropy measures the impurity or randomness in a dataset.

• It quantifies the uncertainty of class labels in a node.

• Formula for a dataset with classes:
  
  where is the proportion of samples belonging to class .

• Interpretation:

  • Entropy = 0 means the node is pure (all samples same class).
  • Entropy = 1 (for binary) means maximum impurity (50-50 split).

Information Gain:

• Information Gain measures the reduction in entropy after splitting a dataset on an attribute.
• It helps decide which feature to split on at each node.
• Formula:
  
  where is the subset of for which attribute has value .

How they are used:

• At each node, the algorithm computes information gain for all attributes.
• The attribute with the highest information gain is selected for splitting.
• This continues recursively to build the tree.

Goal: Maximize information gain to create the purest possible child nodes.

Gini Index:

• The Gini Index (or Gini Impurity) measures the probability of incorrectly classifying a randomly chosen element if it were labeled according to the class distribution in the node.

• Formula:
  
  where is the proportion of samples of class .

• Interpretation:

  • Gini = 0 means perfectly pure node.
  • Higher Gini means more impurity.

Comparison: Gini Index vs Entropy

Key Points:

• Both measure impurity and often produce similar trees.
• Gini is computationally cheaper as it avoids logarithms.
• Entropy is more informative theoretically but slightly slower.
• In practice, the choice rarely affects accuracy significantly.

Overfitting in Decision Trees:

• Overfitting occurs when a decision tree learns the training data too well, including noise and outliers.
• Such trees become very deep and complex, capturing patterns that do not generalize to unseen data.
• Symptoms: High accuracy on training data but poor accuracy on test data.

Causes:

• Growing the tree until every leaf is pure.
• Too many splits based on noisy features.
• Insufficient training data.

Pruning:
Pruning reduces the size of the tree to improve generalization. There are two main approaches:

1. Pre-Pruning (Early Stopping):

• Stops the tree growth early during construction.
• Common stopping criteria:
  • Maximum tree depth.
  • Minimum number of samples to split a node.
  • Minimum information gain threshold.
• Advantage: Faster; Disadvantage: May stop too early (underfitting).

2. Post-Pruning:

• The tree is fully grown first, then unnecessary branches are removed.
• Techniques include:
  • Reduced Error Pruning: Remove nodes if it improves validation accuracy.
  • Cost Complexity Pruning (CCP): Balances tree complexity and error using a parameter .
• Advantage: Usually more accurate than pre-pruning.

Summary: Pruning creates simpler, more general trees that perform better on new data.

Clustering:

• Clustering is an unsupervised learning technique that groups similar data points together based on their features.
• Points within a cluster are more similar to each other than to points in other clusters.
• No predefined labels are used; the algorithm discovers structure in the data.
• Examples: Customer segmentation, image segmentation, document grouping.

Supervised vs Unsupervised Learning:

Supervised Learning Example:

• Predicting whether an email is spam or not using labeled emails.

Unsupervised Learning Example:

• Grouping customers into segments based on purchasing behavior without predefined categories.

Key Difference: Supervised learning learns a mapping from inputs to known outputs, while unsupervised learning explores data without labeled outputs.

K-Means Clustering Algorithm:
K-Means partitions data into K clusters, where each data point belongs to the cluster with the nearest centroid.

Steps:

1. Choose K: Decide the number of clusters .
2. Initialize Centroids: Randomly select initial cluster centroids.
3. Assignment Step: Assign each data point to the nearest centroid using a distance measure (usually Euclidean):
   
4. Update Step: Recalculate each centroid as the mean of all points assigned to it:
   
5. Repeat: Repeat assignment and update steps until centroids no longer change (convergence).

Objective Function (minimize):

Advantages:

• Simple and easy to implement.
• Computationally efficient and scalable.
• Works well with spherical, well-separated clusters.

Limitations:

• Requires the number of clusters to be specified in advance.
• Sensitive to initial centroid placement.
• Sensitive to outliers and noise.
• Struggles with non-spherical or varying-density clusters.

Hierarchical Clustering:

• Hierarchical clustering builds a hierarchy of clusters represented as a tree-like diagram called a dendrogram.
• It does not require specifying the number of clusters in advance.
• Clusters are formed by successively merging or splitting groups based on similarity.

Two Main Approaches:

1. Agglomerative (Bottom-Up):

• Starts with each data point as its own cluster.
• Repeatedly merges the two closest clusters.
• Continues until all points are in a single cluster.
• Most commonly used approach.

2. Divisive (Top-Down):

• Starts with all data points in one single cluster.
• Repeatedly splits clusters into smaller ones.
• Continues until each point is its own cluster.
• Computationally more expensive.

Linkage Criteria (to measure cluster distance):

• Single Linkage: Minimum distance between points of two clusters.
• Complete Linkage: Maximum distance between points of two clusters.
• Average Linkage: Average distance between all pairs.
• Ward's Method: Minimizes variance within clusters.

Comparison:

Advantage: Produces a dendrogram allowing analysis at different levels of granularity.

Determining the optimal number of clusters is a key challenge in K-Means. Two popular methods are the Elbow Method and the Silhouette Score.

1. Elbow Method:

• Plots the Within-Cluster Sum of Squares (WCSS) against different values of .
  
• As increases, WCSS decreases.
• The elbow point is where the rate of decrease sharply slows down, resembling an elbow.
• This point is chosen as the optimal .
• Limitation: The elbow is sometimes ambiguous.

2. Silhouette Score:

• Measures how similar a point is to its own cluster compared to other clusters.
• For a point :
  
  where:
  • = average distance to points in its own cluster.
  • = average distance to points in the nearest other cluster.
• Range: to .
  • Close to : well-clustered.
  • Close to : on cluster boundary.
  • Negative: possibly misclassified.
• The with the highest average silhouette score is optimal.

Summary: The Elbow Method is quick and visual, while the Silhouette Score gives a more quantitative measure of cluster quality.

Confusion Matrix:

• A confusion matrix is a table used to evaluate the performance of a classification model.
• It compares predicted labels with actual labels.

Key Terms:

• TP: Correctly predicted positive cases.
• TN: Correctly predicted negative cases.
• FP: Negative cases wrongly predicted as positive (Type I error).
• FN: Positive cases wrongly predicted as negative (Type II error).

Performance Metrics:

• Accuracy: Overall correctness of the model.
  

• Precision: Of predicted positives, how many are correct.
  

• Recall (Sensitivity): Of actual positives, how many were correctly identified.
  

• F1-Score: Harmonic mean of precision and recall.
  

When to use:

• Accuracy is misleading for imbalanced datasets.
• Precision matters when false positives are costly.
• Recall matters when false negatives are costly.
• F1-Score balances both.

Cross-Validation:

• Cross-validation is a model evaluation technique used to assess how well a model generalizes to unseen data.
• It involves partitioning the data into subsets, training on some, and testing on others.

K-Fold Cross-Validation:

1. The dataset is randomly divided into K equal-sized folds.
2. The model is trained on folds and tested on the remaining fold.
3. This process is repeated times, each time using a different fold as the test set.
4. The final performance is the average of all evaluations:
   

Example: In 5-Fold CV, data is split into 5 parts; the model trains and tests 5 times.

Benefits over Simple Train-Test Split:

• Better use of data: Every data point is used for both training and testing.
• Reduced variance: Averaging over folds gives a more reliable estimate.
• Less bias: Not dependent on a single random split.
• Robust evaluation: Reduces the risk of an overly optimistic or pessimistic result.

Variants:

• Stratified K-Fold: Preserves class distribution in each fold (good for imbalanced data).
• Leave-One-Out (LOOCV): K equals the number of samples.

Limitation: More computationally expensive since the model is trained multiple times.

Bias-Variance Tradeoff:
The bias-variance tradeoff describes the balance between two sources of error that affect a model's ability to generalize.

Bias:

• Error due to overly simplistic assumptions in the model.
• High bias means the model fails to capture underlying patterns.
• Leads to underfitting.

Variance:

• Error due to excessive sensitivity to small fluctuations in training data.
• High variance means the model captures noise as if it were signal.
• Leads to overfitting.

Total Error Decomposition:

Relationship with Fitting:

The Tradeoff:

• Decreasing bias (more complex model) usually increases variance.
• Decreasing variance (simpler model) usually increases bias.
• The goal is to find the optimal balance that minimizes total error.

Techniques to Balance:

• Regularization, cross-validation, ensemble methods, and proper model complexity selection.

Comparison of SVM and Decision Trees:

Support Vector Machine:

• Excels in high-dimensional spaces.
• Effective when there is a clear margin of separation.
• Memory-intensive due to support vectors.

Decision Tree:

• Easy to understand and interpret.
• Handles both numerical and categorical data naturally.
• Prone to overfitting without pruning.

Conclusion:

• Use SVM for complex, high-dimensional problems with clear margins.
• Use Decision Trees when interpretability and simplicity are important.

ROC Curve (Receiver Operating Characteristic):

• The ROC curve is a graphical plot used to evaluate the performance of a binary classifier across different threshold settings.

• It plots:

  • True Positive Rate (TPR / Recall) on the Y-axis:
    
  • False Positive Rate (FPR) on the X-axis:
    

• Each point on the curve corresponds to a different classification threshold.

Interpretation:

• A curve closer to the top-left corner indicates better performance.
• The diagonal line represents random guessing (no discrimination).

AUC (Area Under the Curve):

• AUC measures the entire two-dimensional area under the ROC curve.
• Range: 0 to 1.
  • AUC = 1: Perfect classifier.
  • AUC = 0.5: No better than random guessing.
  • AUC < 0.5: Worse than random.

Uses:

• Compares multiple models regardless of classification threshold.
• Useful for imbalanced datasets.
• Higher AUC indicates better ability to distinguish between classes.

Advantage: ROC and AUC provide a threshold-independent evaluation of model performance.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise):

• DBSCAN is a density-based clustering algorithm that groups together points that are closely packed and marks isolated points as outliers (noise).

Key Parameters:

• (eps): The maximum radius of the neighborhood around a point.
• MinPts: Minimum number of points required to form a dense region.

Types of Points:

• Core Point: Has at least MinPts within its -neighborhood.
• Border Point: Within of a core point but has fewer than MinPts neighbors.
• Noise Point: Neither a core nor a border point (outlier).

Algorithm Steps:

1. Pick an unvisited point.
2. Retrieve its -neighborhood.
3. If it is a core point, form a cluster and expand it by including density-reachable points.
4. If it is not a core point, label it as noise (may later become a border point).
5. Repeat until all points are visited.

Differences from K-Means:

Advantages:

• Does not require specifying the number of clusters.
• Can find arbitrarily shaped clusters.
• Robust to outliers (identifies them as noise).

Limitation: Struggles with clusters of varying densities and choosing suitable and MinPts.

In an SVM with an RBF (Gaussian) kernel, two important hyperparameters control the model's behavior: C and gamma ().

1. The C Parameter (Regularization):

• Controls the trade-off between achieving a low training error and a smooth decision boundary (margin width).
• Small C:
  • Allows more misclassifications (larger margin).
  • Simpler decision boundary.
  • Higher bias, lower variance (may underfit).
• Large C:
  • Penalizes misclassifications heavily (smaller margin).
  • Complex decision boundary that fits training data closely.
  • Lower bias, higher variance (may overfit).

2. The Gamma () Parameter:

• Defines how far the influence of a single training example reaches in the RBF kernel:
  
• Small :
  • Larger influence radius; smoother, more general boundary.
  • May underfit.
• Large :
  • Smaller influence radius; boundary closely follows individual points.
  • May overfit (captures noise).

Combined Effect:

Tuning: These parameters are usually optimized together using techniques like Grid Search with cross-validation to find the best combination.

Imbalanced Datasets:

• An imbalanced dataset is one where the classes are not represented equally (e.g., 95% negative, 5% positive).
• Common in fraud detection, disease diagnosis, and anomaly detection.

Why Accuracy is Insufficient:

• Accuracy measures overall correctness:
  
• In an imbalanced dataset, a model can achieve high accuracy by simply predicting the majority class.
• Example: If 95% of samples are negative, a model predicting all negatives gets 95% accuracy but fails to detect any positive cases.
• This gives a misleading sense of good performance.

Preferred Alternative Metrics:

• Precision: Focuses on correctness of positive predictions.
  

• Recall (Sensitivity): Focuses on detecting actual positives (critical for rare classes).
  

• F1-Score: Harmonic mean balancing precision and recall.
  

• ROC-AUC: Threshold-independent measure of class separability.

• Precision-Recall (PR) Curve: More informative than ROC for highly imbalanced data.

Additional Techniques:

• Resampling: Oversampling minority (SMOTE) or undersampling majority class.
• Class weights: Assigning higher penalty to minority class misclassification.

Conclusion: For imbalanced data, metrics like Precision, Recall, F1-Score, and AUC provide a truer picture of performance than accuracy alone.