Support Vector Machines (SVMs) Cheat Sheet

Support Vector Machines (SVMs) are powerful supervised learning models used for classification and regression. They work by finding an optimal hyperplane that best separates data points, maximizing the margin between classes, and can handle non-linear data through the kernel trick.

Core Principles

SVMs aim to find the hyperplane that maximizes the margin between different classes.
Support vectors are the data points closest to the hyperplane, crucially defining its position.
The kernel trick allows SVMs to learn non-linear decision boundaries by implicitly mapping data to a higher-dimensional space.
Different kernels (e.g., linear, polynomial, RBF/Gaussian) enable SVMs to model various data distributions.
The choice of kernel and its parameters significantly impacts SVM performance.
SVMs are effective even with high-dimensional data and relatively small training sets.
The dual formulation of SVMs can be more efficient for optimization.
Soft margins (using slack variables) allow SVMs to handle noisy data and misclassifications.

Action Steps

Understand your data: Is it linearly separable?
Choose an appropriate kernel function (linear, RBF, polynomial, etc.).
Tune kernel parameters (e.g., C, gamma for RBF) using cross-validation.
Consider feature scaling, especially for kernels like Gaussian.
Evaluate model performance using appropriate metrics (accuracy, precision, recall, F1-score).
For non-linear data, explore different kernels or the kernel trick.
For very large datasets, consider computational efficiency and alternative models.

Formulas

Hyperplane: $ \theta^T x + b = 0 $
Decision Function: $ h(x) = sign(\theta^T x + b) $
Margin (for linearly separable data): $ \text{margin} = \frac{2}{\|\theta\|_2} $
Gaussian Kernel: $ K(x_i, x_j) = \exp\left(-\frac{\|x_i - x_j\|_2^2}{2\sigma^2}\right) $
SVM Dual Objective: $ \text{Maximize } J(\alpha) = \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j \langle x_i, x_j \rangle $
Soft Margin Objective: $ \min_{\theta} \frac{1}{2} \sum_{j=1}^d \theta_j^2 + C \sum_{i} \xi_i $

Key Terms

Hyperplane: A decision boundary that separates data points into different classes.
Margin: The distance between the hyperplane and the nearest data points (support vectors) of any class.
Support Vectors: The data points that lie closest to the hyperplane and influence its position.
Kernel Trick: A method to implicitly map data into a higher-dimensional space, allowing linear separation of non-linearly separable data.
Kernel Function: A function (e.g., RBF, polynomial) that computes the dot product in a high-dimensional feature space without explicit mapping.
Slack Variables (ξ): Variables used in soft-margin SVMs to allow for misclassifications or points within the margin.
Regularization Parameter (C): Controls the trade-off between maximizing the margin and minimizing classification errors.
Dual Problem: An alternative formulation of the SVM optimization problem, often easier to solve and revealing the role of support vectors.

Pro Tips

For high-dimensional data, linear SVMs are often very effective.
The RBF kernel is a good default choice when unsure about the data's structure.
Feature scaling is crucial for distance-based kernels like RBF.
The 'kernel trick' avoids explicit computation in high-dimensional spaces, saving resources.
Understanding the dual problem can provide insights into the role of support vectors.
For datasets with many outliers, a smaller C value in soft-margin SVMs might be beneficial.

Pitfalls to Avoid

Choosing the wrong kernel can lead to poor performance.
Overfitting can occur if kernel parameters are not tuned properly.
SVMs can be computationally expensive for very large datasets.
Interpreting the model can be challenging, especially with non-linear kernels.
Ignoring feature scaling can severely degrade performance for certain kernels.

Real World Examples

Image Classification: Classifying images of cats versus dogs using features extracted from the images.
Text Categorization: Sorting emails into spam or not spam based on word frequencies and other text features.
Bioinformatics: Predicting protein function or gene classification based on sequence data.
Handwriting Recognition: Recognizing handwritten digits or characters.

People

Kaiqun Fu: Instructor
Andrew Ng: Mentioned for advice on SVMs vs. Logistic Regression