W46L12 - Lecture 12 notes

Support Vector Machines (SVM)

SVMs are discriminative classifiers that determine a decision boundary to separate classes.

The Goal: Find a hyperplane (a line in 2D, a plane in 3D) that separates data points of two classes with the widest possible margin.
The Margin: The "empty" space between the decision boundary and the closest data points of either class. These closest points are the Support Vectors.
Mathematical Definition: The boundary is defined by W^T X + B = 0. The optimization problem tries to minimize the length of the vector W (which maximizes the margin) subject to the constraint that all data points are correctly classified outside the margin.
Limitations:
- Outliers: A single outlier (e.g., a blue point sitting among red points) can make it impossible to draw a linear line that separates classes perfectly.
- Narrow Margins: Even if separable, an outlier can force the margin to be extremely narrow to satisfy the "hard" constraint, which makes the model sensitive to noise and prone to overfitting.

To handle outliers and non-linearly separable data, SVMs introduce Slack Variables (ξ).

Function: Slack variables relax the strict constraints. They allow some data points to fall within the margin or even on the wrong side of the hyperplane during training.
The Cost Parameter (C): This is a crucial hyperparameter that controls the trade-off between maximizing the margin and minimizing classification errors.
- Large C: Penalizes slack variables heavily. The model tries hard not to missclassify any training points. This mimics a Hard Margin and increases the risk of overfitting.
- Small C: Penalizes slack variables less. It accepts a wider margin even if some training points are misclassified. This leads to a simpler model (regularization) but risks underfitting.
Output: Unlike Logistic Regression (which gives probabilities), standard SVMs strictly output a class label.

When a linear line cannot separate data (e.g., a red cluster surrounded by a blue ring), SVMs use the Kernel Trick.

Concept: The data is projected (lifted) into a higher-dimensional space. In this high-dimensional space, data that was previously tangled becomes linearly separable by a flat plane.
Kernel Trick Efficiency: Instead of actually calculating the coordinates in the high-dimensional space (which is computationally expensive), the algorithm calculates the "similarity" (dot product) between points using a kernel function.
Common Kernels:
- Radial Basis Function (RBF): The most universal kernel. It uses a parameter Gamma (γ).
  - High Gamma: Considers only close points as similar. Creates complex, jagged boundaries. High risk of overfitting.
  - Low Gamma: Considers far points as similar. Creates smoother, simpler boundaries.
- Polynomial: Useful for data with polynomial relationships.
- Sigmoid: similar to neural network activation.

SVMs can be adapted for regression tasks (predicting continuous values).

The Tube (ε): Instead of a margin separating classes, SVR tries to fit a "tube" around the data.
Logic: The algorithm ignores errors for points that fall inside the tube. It only penalizes points that fall outside the tube.
Goal: Find the flattest function that fits the data within the epsilon tolerance.

Naive Bayes is a generative classifier based on probability theory, specifically Bayes' Theorem.

Bayes' Theorem: P(Y|X) = [P(X|Y) · P(Y)] / P(X)
- P(Y|X) (Posterior): The probability of the class Y given the features X (what we want to find).
- P(X|Y) (Likelihood): The probability of seeing these features given the class.
- P(Y) (Prior): The general probability of the class occurring.
The "Naive" Assumption: The model assumes that all features are independent of each other given the class label.
- Mathematical implication: P(X₁, X₂ | Y) = P(X₁ | Y) · P(X₂ | Y).
- Reality: This assumption rarely holds true in real-world data (features are usually correlated), but the model works surprisingly well despite this.

Gaussian Naive Bayes: Used for continuous features. Assumes data follows a normal (Gaussian) distribution.
Multinomial Naive Bayes: Used for discrete counts (e.g., word counts in text classification).
Bernoulli Naive Bayes: Used for binary features (e.g., word presence/absence: Yes/No).

Pros: Very fast, works well with small datasets, handles high dimensions well.
Cons:
- Zero Frequency Problem: If a feature value never appears in the training set for a specific class, the probability becomes zero, wiping out the entire calculation.
- Independence Assumption: Ignoring correlations can limit performance on complex datasets.

Decision Trees are discriminative models that split data into subsets based on feature values, forming a tree structure.

Greedy Approach: The tree is built step-by-step. At each node, the algorithm chooses the current best split without worrying about whether it leads to the global optimal tree.
Logic: It asks a series of True/False questions (e.g., "Is feature X > 5?").
Interpretability: Highly interpretable. You can trace the path from the root to a leaf to understand exactly why a decision was made.

To decide which feature to split on, the algorithm measures "purity" using:

Entropy: Measures the disorder in a set. High entropy means mixed classes (impure); low entropy means mostly one class (pure).
Gini Index/Impurity: A similar measure to entropy but computationally slightly faster. Ranges from 0 (perfectly pure) to 0.5 (perfectly mixed binary classes).
Information Gain: The difference between the impurity before the split and the weighted impurity after the split. The algorithm selects the feature that provides the highest Information Gain.

The Problem: Decision trees naturally tend to grow very deep, creating complex rules that memorize the training data (overfitting).
Solutions:
- Pruning: Limiting the depth of the tree.
- Min Samples Split: Requiring a minimum number of samples to allow a node to split further.
- Ensembling (Random Forests): Because a single tree is a "weak learner" (high variance), combining many trees into a Random Forest creates a "strong learner" that generalizes better.