8.2 Support vector machines (SVM)

Support Vector Machines (SVMs) are powerful machine learning algorithms used for classification and regression. They work by finding the best hyperplane to separate data points into different classes, maximizing the margin between them.

SVMs can handle both linear and non-linear data using kernel functions. They're versatile and effective for various tasks, making them a key technique in advanced machine learning. Understanding SVMs is crucial for tackling complex classification problems.

Support Vector Machines: Principles and Foundations

Mathematical Formulation and Optimization

Top images from around the web for Mathematical Formulation and Optimization

• 

  【直观详解】支持向量机SVM | Go Further | Stay Hungry, Stay Foolish View original

  Is this image relevant?

• 

  Support vector machine - Wikipedia View original

  Is this image relevant?

• 

  Hinge loss - Wikipedia View original

  Is this image relevant?

• 

  【直观详解】支持向量机SVM | Go Further | Stay Hungry, Stay Foolish View original

  Is this image relevant?

• 

  Support vector machine - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Mathematical Formulation and Optimization

• 

  【直观详解】支持向量机SVM | Go Further | Stay Hungry, Stay Foolish View original

  Is this image relevant?

• 

  Support vector machine - Wikipedia View original

  Is this image relevant?

• 

  Hinge loss - Wikipedia View original

  Is this image relevant?

• 

  【直观详解】支持向量机SVM | Go Further | Stay Hungry, Stay Foolish View original

  Is this image relevant?

• 

  Support vector machine - Wikipedia View original

  Is this image relevant?

1 of 3

• Support vector machines (SVMs) are supervised learning algorithms used for classification and regression tasks based on finding optimal hyperplanes that maximize the margin between classes (binary classification, multi-class classification)
• SVMs aim to find the maximum-margin hyperplane, which is the hyperplane that maximally separates the classes in the feature space
  • The data points closest to the hyperplane are called support vectors and play a crucial role in determining the decision boundary
• The objective function of an SVM is formulated as a constrained optimization problem that minimizes the hinge loss, which penalizes misclassifications, while simultaneously maximizing the margin between the classes
  • The hinge loss is defined as $max(0, 1 - y_i(w^Tx_i + b))$, where $y_i$ is the true class label, $w$ is the weight vector, $x_i$ is the input feature vector, and $b$ is the bias term
• The optimization problem is solved using the Lagrange multipliers method, which introduces Lagrange multipliers for each training example and converts the problem into its dual form
  • The dual optimization problem is often easier to solve and provides insights into the role of support vectors

Decision Function and Support Vectors

• The decision function of an SVM is determined by the support vectors, their corresponding Lagrange multipliers, and the bias term
  • The decision function is given by $f(x) = sign(\sum_{i=1}^{n} \alpha_i y_i K(x_i, x) + b)$, where $\alpha_i$ are the Lagrange multipliers, $y_i$ are the class labels, $K(x_i, x)$ is the kernel function, and $b$ is the bias term
• The sign of the decision function determines the predicted class label for a given input
  • Positive values indicate one class (positive class), while negative values indicate the other class (negative class)
• Support vectors are the data points that lie closest to the decision boundary and have non-zero Lagrange multipliers
  • They are the critical points that define the margin and the decision boundary of the SVM
• The magnitude of the Lagrange multipliers associated with the support vectors indicates their importance in determining the decision boundary
  • Support vectors with larger Lagrange multipliers have a stronger influence on the model

SVM Model Construction for Classification and Regression

Linear and Non-linear SVMs

• Linear SVMs are used when the data is linearly separable in the original feature space
  • The hyperplane is a linear function of the input features, given by $w^Tx + b = 0$, where $w$ is the weight vector and $b$ is the bias term
• Non-linear SVMs are used when the data is not linearly separable in the original feature space
  • The data is transformed into a higher-dimensional space using kernel functions, where it becomes linearly separable
  • The kernel trick is employed to implicitly map the data into the higher-dimensional space without explicitly computing the transformed features
• Popular kernel functions for non-linear SVMs include:
  • Polynomial kernel: $K(x_i, x_j) = (\gamma x_i^T x_j + r)^d$, where $\gamma$ is the kernel coefficient, $r$ is the bias term, and $d$ is the degree of the polynomial
  • Radial Basis Function (RBF) kernel: $K(x_i, x_j) = exp(-\gamma ||x_i - x_j||^2)$, where $\gamma$ is the kernel coefficient
  • Sigmoid kernel: $K(x_i, x_j) = tanh(\gamma x_i^T x_j + r)$, where $\gamma$ is the kernel coefficient and $r$ is the bias term

Multi-class Classification and Support Vector Regression

• SVMs can be extended to handle multi-class classification problems using strategies such as:
  • One-vs-One (OVO) classification: Trains $\binom{n}{2}$ binary classifiers for each pair of classes and uses majority voting to determine the final class label
  • One-vs-All (OVA) classification: Trains $n$ binary classifiers, each distinguishing one class from the rest, and assigns the class label based on the classifier with the highest score
• Support Vector Regression (SVR) extends SVMs to regression tasks
  • In SVR, the goal is to find a hyperplane that fits the data within a specified epsilon-insensitive tube while minimizing the model complexity
  • The objective function in SVR includes a penalty term for points outside the epsilon-tube and a regularization term to control the model complexity

Kernel Functions and Hyperparameter Tuning for SVMs

Selecting Appropriate Kernel Functions

• The choice of kernel function is crucial for the performance of non-linear SVMs, as different kernel functions capture different types of relationships between the features
• Polynomial kernel is suitable when the data has polynomial relationships
  • The degree of the polynomial, $d$, is a hyperparameter that needs to be tuned to capture the appropriate level of complexity
• RBF kernel is a popular choice for non-linear SVMs due to its ability to capture complex non-linear relationships
  • The gamma parameter, $\gamma$, of the RBF kernel controls the width of the Gaussian function and determines the influence of individual training examples
• Sigmoid kernel is less commonly used but can be effective in certain scenarios, particularly when the data has a sigmoidal structure
  • The kernel coefficient, $\gamma$, and the bias term, $r$, are hyperparameters that need to be tuned for optimal performance

Hyperparameter Tuning Techniques

• Hyperparameter tuning is essential to find the optimal combination of kernel function and hyperparameters that maximize the model's performance on unseen data
• The regularization parameter, $C$, controls the trade-off between maximizing the margin and minimizing the classification error
  • A smaller $C$ allows for a larger margin but may lead to more misclassifications, while a larger $C$ emphasizes correct classification at the expense of a smaller margin
• Grid search is a common hyperparameter tuning technique that exhaustively searches over a specified grid of hyperparameter values
  • It evaluates the model's performance for each combination of hyperparameters using cross-validation and selects the best combination based on a chosen metric (accuracy, F1-score, etc.)
• Random search is an alternative to grid search that randomly samples hyperparameter values from a specified distribution
  • It can be more efficient than grid search when the search space is large or when some hyperparameters are more important than others
• Bayesian optimization is a more advanced hyperparameter tuning technique that uses a probabilistic model to guide the search process
  • It iteratively updates the probabilistic model based on the observed performance and suggests the next set of hyperparameters to evaluate

Interpreting SVM Results and Decision Boundaries

Decision Boundaries and Support Vectors

• The decision boundary of an SVM is determined by the hyperplane that maximally separates the classes
  • In linear SVMs, the decision boundary is a straight line in the feature space, given by $w^Tx + b = 0$
  • In non-linear SVMs, the decision boundary is a non-linear surface in the original feature space but corresponds to a linear hyperplane in the transformed higher-dimensional space
• Support vectors are the data points that lie closest to the decision boundary and have the most influence on the position and orientation of the hyperplane
  • They are the critical points that define the margin and the decision boundary of the SVM
• The magnitude of the Lagrange multipliers associated with the support vectors indicates their importance in determining the decision boundary
  • Support vectors with larger Lagrange multipliers have a stronger influence on the model and contribute more to the decision function

Interpreting Predictions and Confidence Measures

• The sign of the decision function for a given input determines the predicted class label
  • Positive values indicate one class (positive class), while negative values indicate the other class (negative class)
• The distance of a data point from the decision boundary can be interpreted as a measure of the confidence or margin of the prediction
  • Points further away from the decision boundary are classified with higher confidence, as they have a larger margin
  • Points closer to the decision boundary have lower confidence and are more susceptible to misclassification
• The absolute value of the decision function can be used as a measure of the confidence or certainty of the prediction
  • Larger absolute values indicate higher confidence, while smaller absolute values suggest lower confidence
• Visualizing the decision boundary and the support vectors can provide insights into the behavior and performance of the SVM model
  • In lower-dimensional feature spaces (2D or 3D), the decision boundary can be plotted along with the training examples to visualize the separation between classes
  • In higher-dimensional feature spaces, techniques such as dimensionality reduction (PCA, t-SNE) can be used to project the data onto a lower-dimensional space for visualization purposes