Statistical Prediction Unit 9 ReviewSupport Vector Machines & Kernels

What Are Support Vector Machines?

• Supervised learning models used for classification and regression analysis
• Goal is to find a hyperplane that best divides a dataset into two classes
• Hyperplane is a decision boundary that separates data points of different classes
• Maximize the margin between the two classes to achieve better generalization
• Support vectors are the data points closest to the hyperplane and influence its position and orientation
• SVMs can handle high-dimensional data and work well with a clear margin of separation
• Effective in cases where the number of dimensions is greater than the number of samples

Key Concepts in SVM

• Hyperplane: A subspace of one dimension less than its ambient space, used to separate data points
• Margin: The distance between the hyperplane and the closest data points from each class
  • Larger margins indicate better separation and generalization
• Support Vectors: The data points closest to the hyperplane that define the margin
  • These points have the most influence on the position and orientation of the hyperplane
• Slack Variables: Allow for some misclassifications in the training data to handle noise and outliers
• Regularization Parameter (C): Controls the trade-off between maximizing the margin and minimizing misclassifications
  • Higher C values prioritize minimizing misclassifications, while lower values prioritize maximizing the margin

Linear SVMs: The Basics

• Used when the data is linearly separable
• Objective is to find the optimal hyperplane that maximizes the margin between classes
• Mathematically, the hyperplane is defined as: $w \cdot x + b = 0$
  • $w$ is the normal vector to the hyperplane
  • $b$ is the bias term
• Classification is performed based on the sign of the decision function: $f(x) = w \cdot x + b$
  • If $f(x) > 0$, the point is classified as positive; otherwise, it is classified as negative
• Training involves solving an optimization problem to find the optimal values of $w$ and $b$

Dealing with Non-Linear Data: Kernel Trick

• Many real-world datasets are not linearly separable
• Kernel trick allows SVMs to handle non-linear data by mapping it to a higher-dimensional space
• Input data is transformed into a higher-dimensional feature space where it becomes linearly separable
• Kernel functions compute the similarity between pairs of data points in the original space
• Common kernel functions include linear, polynomial, radial basis function (RBF), and sigmoid
• Kernel trick allows SVMs to learn complex decision boundaries without explicitly computing the transformed features

Common Kernel Functions

• Linear Kernel: $K(x, y) = x^T y$
  • Used when the data is already linearly separable
• Polynomial Kernel: $K(x, y) = (\gamma x^T y + r)^d$
  • $d$ is the degree of the polynomial, $\gamma$ is a scaling parameter, and $r$ is a constant term
• Radial Basis Function (RBF) Kernel: $K(x, y) = \exp(-\gamma ||x - y||^2)$
  • Most commonly used kernel, works well in many cases
  • $\gamma$ controls the width of the Gaussian function
• Sigmoid Kernel: $K(x, y) = \tanh(\gamma x^T y + r)$
  • Originates from neural networks and can be used as a proxy for neural network classifiers

SVM Optimization and Training

• Training an SVM involves solving a quadratic optimization problem
• Objective is to minimize the following function: $\frac{1}{2} ||w||^2 + C \sum_{i=1}^n \xi_i$
  • $||w||^2$ is the L2-norm of the weight vector, which controls the margin
  • $C$ is the regularization parameter that balances margin maximization and misclassification tolerance
  • $\xi_i$ are slack variables that allow for misclassifications
• Constraints ensure that each data point is classified correctly with a certain margin
• Optimization problem is typically solved using quadratic programming (QP) solvers
• Sequential Minimal Optimization (SMO) is a popular algorithm for training SVMs efficiently

Pros and Cons of SVMs

Pros:

• Effective in high-dimensional spaces and cases where the number of dimensions exceeds the number of samples
• Memory-efficient as they use a subset of training points (support vectors) for prediction
• Versatile with the use of different kernel functions for non-linear decision boundaries
• Robust to outliers and has good generalization performance

Cons:

• Choosing the appropriate kernel function and tuning hyperparameters can be challenging
• Training time can be long for large datasets, especially with non-linear kernels
• Sensitive to the choice of kernel and regularization parameters
• Difficult to interpret the model and understand the importance of individual features

Real-World Applications of SVMs

• Text and document classification (spam filtering, sentiment analysis)
• Image classification and object detection (face recognition, handwritten digit recognition)
• Bioinformatics (protein classification, cancer diagnosis)
• Financial forecasting and stock market analysis
• Fault detection and condition monitoring in industrial systems
• Geographical information systems (GIS) and remote sensing
• Anomaly detection and intrusion detection in network security