Support Vector Machines and Classification Methods

Introduction to Machine Learning AI 305: Support Vector Machines (SVM)

• Support Vector Machines (SVMs) are a classification approach developed in the 1990s.
• They are popular because they often perform well in various settings and are considered a strong "off-the-shelf" classifier.
• The core concept is a simple, intuitive classifier called the maximal margin classifier.

Types of SVM Classifiers

• Maximal Margin Classifier: A fundamental classifier that aims to find the optimal separation between data classes.
• Support Vector Classifier: An extension of the maximal margin classifier suited for a wider range of datasets.
• Support Vector Machine (SVM): A further extension of the support vector classifier, enabling non-linear class boundaries.

Two Class Classification

• A direct approach to two-class classification involves finding a plane that separates the classes in feature space.
• If such a plane cannot be found, alternative strategies can be employed. These include softening the "separation" criteria and enlarging the feature space to allow for separation.

Hyperplanes

• A hyperplane in p-dimensional space is a flat affine subspace of dimension p-1.
• The general equation for a hyperplane in p dimensions is: β₀ + β₁x₁ + β₂x₂ + ... + βₚxₚ = 0
• In two dimensions, a hyperplane is a line, while in three dimensions it is a plane.
• The vector β = (β₁, β₂, ..., βₚ) is the normal vector, perpendicular to the hyperplane.

Classification Using a Separating Hyperplane

• Given a data matrix X with n training observations in p-dimensional space, the observations fall into two classes (e.g., -1 and +1).
• The goal is to create a classifier that correctly classifies a test observation using its feature measurements.
• Existing classification techniques like logistic regression, classification trees, bagging, and boosting are alternatives.
• A new strategy involves using a separating hyperplane.

Separating Hyperplanes

• f(X) = β₀ + β₁x₁ + β₂x₂ + ... + βₚxₚ
• For points on one side of the hyperplane, f(X) > 0, while for points on the other side, f(X) < 0.
• If classes are coded as Yᵢ = +1 and Yᵢ = -1, then Yᵢ f(xᵢ) > 0 for all i.
• A separating hyperplane is defined by f(X) = 0.

Maximal Margin Classifier

• Among all separating hyperplanes, the maximal margin classifier aims to create the maximum separation (or margin) between two classes.
• This margin maximization problem translates to a constraint optimization problem.
• The solution involves maximizing the margin M, subject to each observation being at least a distance M from the hyperplane.
• This problem can be solved explicitly using a convex quadratic program.

Non-separable Data

• In many cases, data are not linearly separable.
• The maximal margin solution cannot guarantee perfect classification in this condition.
• A new method, termed the support vector classifier, aims to maximize a soft margin for a near-perfect separation with tolerance in misclassification.

Noisy Data

• In some cases, the data may be separable, but noisy.
• Maximal margin classifiers can be sensitive to noise, causing poor solutions due to small margin size fluctuations.

Drawbacks of Maximal Margin Classifier

• Classifiers based on separating hyperplanes are extremely sensitive to individual observations, with even minor changes affecting the position .
• This is evident from maximal margin hyperplanes, which may not be a satisfactory solution, often displaying very narrow margins.

Support Vector Classifiers

• Support vector classifiers (SVCs) provide a solution for cases where complete separation might not be achievable.
• These classifiers prioritize classifying most observations correctly while accepting moderate misclassification for a few observations.
• The goal is enhanced robustness with respect to individual observations, aiming for better classification outcomes.

Support Vector Classifier - Continued

• The solution to the optimization problem is highly insightful.
• A noteworthy property is that the support vector classifier's decision is insensitive to points positioned strictly on the correct side of the margin, effectively ignoring them.
• Critically, only points directly on or touching the margin planes (support vectors) influence classifier behavior.

Support Vector Classifier - Continued (Data sets)

• Illustrations demonstrating the behavior of classifiers on both separable and non-separable data sets are essential and vital.
• Specific examples illustrate how certain observations (support vectors) define the margin planes.

Support Vector Classifier - Continued (Optimization Problem)

• The optimization problem for the Support Vector classifier has a specific structure, involving a regularization parameter (C) that controls the tolerance for margin violations.
• This parameter is a value that acts as an upper bound on the sum of slack variables.
• The parameter effectively controls the degree of tolerance permitted in misclassifications.

The Regularization Parameter C

• The parameter C, acting as a regularization parameter, balances the desire for maximal margin with the tolerance for misclassifications.
• A larger C indicates higher tolerance and a wider margin. Conversely, a smaller C corresponds to lower tolerance and a narrower margin.
• Practical application commonly relies on cross-validation for optimal C selection. Large C values mean many observations are involved in determining the hyperplane (high variance, low bias) Small C values mean fewer support vectors, resulting in a classifier with low variance and high bias.

Robustness of Support Vector Classifiers

• The decision rule of an SVM is usually determined by a small subset of training observations (support vectors).
• This feature makes it fairly less sensitive to variations in observations—especially those far from the hyperplane—thus showcasing high robustness to outlier effects.
• This characteristic differentiates SVM from other classification methods.

Linear Boundary Failures

• In some scenarios, a linear decision boundary may prove inadequate, irrespective of C values.
• This necessitates a different strategy, such as augmenting the initial feature space through higher-order polynomial extensions.

Feature Expansion

• Existing datasets are augmented to incorporate transformations.
• For instance, if the data are represented by two features X1 and X2, then higher-order features like X₁², X₂², or X₁X₂ can provide better non-linear separation.
• This extension transforms the original feature space dimensions effectively accommodating nonlinearity to find a suitable hyperplane.

Cubic Polynomials

• Employing a cubic polynomial approach allows further enlargement of the feature space, going from two dimensions to nine dimensions for example.

SVMs: More than 2 Classes

• The inherent binary nature of SVM's can be adapted to handling the multiclass classification (where K > 2 classes).
• Two common strategies are One-Versus-All (often denoted as OVA) and One-Versus-One (often denoted as OVO.
• SVMs, through these approaches, are applicable to multiclass classification problems extending their applicability beyond binary classification.

SVM versus Logistic Regression

• SVMs and logistic regression, despite their superficial similarities, have distinct optimization formulations.
• The hinge loss function, a common element in SVM optimization, plays a role comparable to the negative log-likelihood used in logistic regression.
  • SVM's hinge loss measures the degree of misclassification of the prediction from the desired outcome (a concept closely associated with misclassification error), and is quite similar to negative log-likelihood used in a logistic regression loss function.

Which to use: SVM or Logistic Regression

• SVM performs better than LR (and LDA) for datasets where classes are (almost) separable.
• Logistic regression with a ridge penalty and SVM are often very similar when data are not separable.
• For probability estimation tasks, only logistic regression emerges as a clear preference