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 maximally separates data points of different classes, with the 'kernel trick' enabling them to handle non-linear data.

Core Principles

SVMs aim to find the hyperplane with the largest margin between classes.
The margin is the distance between the hyperplane and the nearest data points (support vectors).
Maximizing the margin reduces model capacity, leading to better generalization.
Kernels allow SVMs to map data into higher dimensions, enabling linear separation of non-linearly separable data.
The dual problem formulation is often more efficient for solving SVMs.
Support vectors are the data points closest to the hyperplane, crucial for defining it.

Action Steps

Choose an appropriate kernel function (linear, polynomial, RBF, sigmoid, etc.).
Tune kernel parameters (e.g., C, gamma, sigma) using cross-validation.
Consider feature scaling, especially for kernels like Gaussian RBF.
For non-linearly separable data, use non-linear kernels or the kernel trick.
If data is very large, consider computational efficiency and alternative models.

Formulas

Margin: $margin = \frac{2}{\|\|\theta\|_2}$
Decision Function: $h(x) = sign(\theta^T x)$ $h(x) = sign(\sum_{i \in SV} \alpha_i y_i \langle x_i, x \rangle + b)$ where $b = \frac{1}{|SV|} \sum_{i \in SV} (y_i - \sum_{j \in SV} \alpha_j y_j \langle x_i, x_j \rangle)$
Gaussian Kernel: $K(x_i, x_j) = \exp\left(-\frac{\|x_i - x_j\|_2^2}{2\sigma^2}\right)$
Sigmoid Kernel: $K(x_i, x_j) = \tanh (\alpha x_i^T x_j + c)$
Cosine Similarity Kernel: $K(x_i, x_j) = \frac{x_i^T x_j}{\|x_i\| \|x_j\|}$
Chi-squared Kernel: $K(x_i, x_j) = \exp \left(-\gamma \sum_k \frac{(x_{ik} - x_{jk})^2}{x_{ik} + x_{jk}}\right)$

Key Terms

Hyperplane: A decision boundary that separates data points into different classes.
Margin: The distance between the hyperplane and the closest data points (support vectors).
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-linear data.
RBF Kernel: Radial Basis Function kernel, a popular choice for non-linear SVMs.
Slack Variables: Variables introduced in soft-margin SVMs to allow for misclassifications.
Dual Problem: An alternative formulation of the SVM optimization problem, often easier to solve.

Pro Tips

The 'kernel trick' allows SVMs to operate in a high-dimensional feature space without explicitly computing the coordinates of the data in that space.
For high-dimensional data, linear SVMs are often preferred.
For smaller datasets with complex patterns, non-linear kernels like RBF can be very effective.
The parameter C in soft-margin SVMs controls the trade-off between maximizing the margin and minimizing classification errors.
When using the Gaussian kernel, feature scaling is crucial for good performance.

Pitfalls to Avoid

Choosing the wrong kernel can lead to poor performance.
Overfitting can occur if the kernel parameters are not tuned properly.
SVMs can be computationally expensive for very large datasets.
Interpreting the decision boundary in high-dimensional feature spaces can be challenging.
Ignoring feature scaling can significantly degrade performance with certain kernels.

People

Kaiqun Fu: Instructor
Andrew Ng: Source of advice on SVMs vs. Logistic Regression