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 that maximizes the margin between classes.
• The margin is the distance between the hyperplane and the nearest data points (support vectors).
• Kernels allow SVMs to map data into higher dimensions, enabling linear separation of non-linearly separable data.
• The 'kernel trick' computes dot products in the feature space implicitly, avoiding explicit high-dimensional mapping.
• SVMs can be sensitive to outliers, especially with a large regularization parameter C.
• The dual problem formulation is often more efficient for solving SVMs.
• Different kernels (e.g., Gaussian, polynomial, sigmoid) offer flexibility for various data types.

Action Steps

• Understand the data: Is it linearly separable?
• Choose an appropriate kernel function (linear, polynomial, RBF, sigmoid).
• Select a regularization parameter (e.g., C for soft-margin SVMs).
• Train the SVM model using the chosen kernel and parameters.
• Evaluate the model's performance using appropriate metrics.
• Tune hyperparameters (kernel parameters, C) for optimal results.
• Consider feature scaling, especially for kernels like Gaussian RBF.

Formulas

• Hyperplane: $ \theta^T x = 0 $
• Decision Function: $ h(x) = \text{sign}(\theta^T x) $
• Margin (for linear SVM): $ \text{margin} = \frac{2}{\|\theta\|_2} $
• Gaussian Kernel: $ K(\mathbf{x}_i, \mathbf{x}_j) = \exp\left(-\frac{\|\mathbf{x}_i - \mathbf{x}_j\|^2}{2\sigma^2}\right) $
• Sigmoid Kernel: $ K(\mathbf{x}_i, \mathbf{x}_j) = \tanh (\alpha \mathbf{x}_i^T \mathbf{x}_j + c) $
• Cosine Similarity Kernel: $ K(\mathbf{x}_i, \mathbf{x}_j) = \frac{\mathbf{x}_i^T \mathbf{x}_j}{\|\mathbf{x}_i\| \ \mathbf{x}_j\|} $
• Primal SVM Objective: $ \min_{\theta} \frac{1}{2} \sum_{j=1}^{d} \theta_j^2 $
• SVM Dual Objective: $ \text{Maximize } J(\boldsymbol{\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 \mathbf{x}_i, \mathbf{x}_j \rangle $

Key Terms

• Hyperplane: A decision boundary that separates data points into different classes.
• Margin: The distance between the hyperplane and the closest data points 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 to find linear separators for non-linear data.
• Regularization (C): A parameter that 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.
• Slack Variables (ξ): Variables introduced to allow for misclassifications in non-linearly separable data.

Pro Tips

• For high-dimensional data, linear kernels are often efficient.
• The Gaussian RBF kernel is a good default choice when unsure.
• Tuning the regularization parameter C is crucial for balancing margin maximization and misclassification.
• Cross-validation is essential for selecting the best kernel and hyperparameters.
• For very large datasets, consider approximations or alternative methods due to computational cost.

Pitfalls to Avoid

• Choosing the wrong kernel can lead to poor performance.
• Overfitting can occur if the regularization parameter C is too large.
• Underfitting can occur if the margin is too wide and the model is too simple.
• Ignoring feature scaling can significantly impact performance with certain kernels.
• SVMs can be computationally expensive for very large datasets.

People

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