Support Vector Machine

SVM is a model, which can do linear classification as well as regression.

SVM is based on the concept of a surface, called a hyperplane, which draws a boundary between data instances
plotted in the multi-dimensional feature space. The output prediction of an SVM is one of two conceivable
classes which are already defined in the training data.

In summary, the SVM algorithm builds an N-dimensional hyperplane model that assigns future instances into
one of the two possible output classes.

Classification using hyperplanes

In SVM, a model is built to discriminate the data instances belonging to different classes. Let us assume for
the sake of simplicity that the data instances are linearly separable.

In this case, when mapped in a two-dimensional space, the data instances belonging to different classes fall in
different sides of a straight line drawn in the two-dimensional space as depicted in Figure 7.15a.

If the same concept is extended to a multidimensional feature space, the straight-line dividing data instances
belonging to different classes transforms to a hyperplane as depicted in Figure 7.15b.

Thus, an SVM model is a representation of the input instances as points in the feature space, which are mapped
so that an apparent gap between them divides the instances of the separate classes

In summary, in the overall training process, the SVM algorithm analyses input data and identifies a surface
in the multi-dimensional feature space called the hyperplane. There may be many possible hyperplanes, and
one of the challenges with the SVM model is to find the optimal hyperplane.
Training data sets which have a substantial grouping periphery will function well with SVM. Generalization
error in terms of SVM is the measure of how accurately and precisely this SVM model can predict values for
previously unseen data (new data). A hard margin in terms of SVM means that an SVM model is inflexible in
classification and tries to work exceptionally fit in the training set, thereby causing overfitting.

Support Vectors: Support vectors are the data points (representing classes), the critical component in a data
set, which are near the identified set of lines (hyperplane). If support vectors are removed, they will alter the
position of the dividing hyperplane.

Hyperplane and Margin: For an N-dimensional feature space, hyperplane is a flat subspace of dimension (N
−1) that separates and classifies a set of data. For example, if we consider a two-dimensional feature space
(which is nothing but a data set having two features and a class variable), a hyperplane will be a one-
dimensional subspace or a straight line.

In the same way, for a three-dimensional feature space (data set having three features and a class variable),
hyperplane is a two-dimensional subspace or a simple plane. However, quite understandably, it is difficult to
visualize a feature space greater than three dimensions, much like for a subspace or hyperplane having more
than three dimensions.

Mathematically, in a two-dimensional space, hyperplane can be defined by the equation:

C0 + C1 X1 + C2 X2 = 0,

which is nothing but an equation of a straight line.

Extending this concept to an N-dimensional space, hyperplane can be defined by the equation:

C0 + C1 X1 + C2 X2 + … + Cn Xn = 0
which, in short, can be represented as follows:

Spontaneously, the further (or more distance) from the hyperplane the data points lie, the more confident we
can be about correct categorization. So, when a new testing data point/data set is added, the side of the
hyperplane it lands on will decide the class that we assign to it. The distance between hyperplane and data
points is known as margin.

Identifying the correct hyperplane in SVM

We need to identify which one will result in the best classification.

Let us examine a few scenarios before

For the sake of simplicity of visualization, the hyperplanes have been shown as straight lines in most of the
diagrams. arriving to that conclusion.
Scenario 1

Three hyperplanes: A, B, and C. Now, we need to identify the correct hyperplane which better segregates the
two classes represented by the triangles and circles. As we can see, hyperplane ‘A’ has performed this task
quite well.

FIG. 7.16 Support vector machine: Scenario 1

Scenario 2
In Figure 7.17 Three hyperplanes: A, B, and C. We have to identify the correct hyperplane which classifies
the triangles and circles in the best possible way.

Here, maximizing the distances between the nearest data points of both the classes and hyperplane will help
us decide the correct hyperplane. This distance is called as margin.
 FIG. 7.17 Support vector machine: Scenario 2

In Figure 7.17b the margin for hyperplane A is high as compared to those for both B and C. Hence,
hyperplane A is the correct hyperplane. Another quick reason for selecting the hyperplane with higher margin
(distance) is robustness. If we select a hyperplane having a lower margin (distance), then there is a high
probability of misclassification.

Scenario 3

In Figure 7.18. Some of you might have selected hyperplane B as it has a higher margin (distance from the
class) than A. But here is the catch; SVM selects the hyperplane which classifies the classes accurately before
maximizing the margin. Here, hyperplane B has a classification error, and A has classified all data instances
correctly. Therefore, A is the correct hyperplane.

FIG. 7.18 Support vector machine: Scenario 3

In this scenario, in Figure 7.19a, it is not possible to distinctly segregate the two classes by using a straight
line, as one data instance belonging to one of the classes (triangle) lies in the territory of the other class (circle)
as an outlier. One triangle at the other end is like an outlier for the triangle class. SVM has a feature to ignore
outliers and find the hyperplane that has the maximum margin (hyperplane A, as shown in Fig. 7.19b).

Hence, we can say that SVM is robust to outliers.

FIG. 7.19 Support vector machine: Scenario 4

1. The hyperplane should segregate the data instances belonging to the two classes in the best possible
way.
2. It should maximize the distances between the nearest data points of both the classes, i.e. maximize the
margin.
3. If there is a need to prioritize between higher margin and lesser misclassification, the hyperplane should
try to reduce misclassifications.

Maximum Margin Hyperplane

The maximum margin hyperplane is a key concept in Support Vector Machines (SVMs), a supervised
machine learning algorithm used for classification (and regression). It refers to the optimal decision
boundary that separates two classes in the dataset with the largest possible margin.

MMH for a linearly separable data set.

Key Concepts:

1. Support vectors, as can be observed in Figure 7.20, are data instances from the two classes which are
closest to the MMH. Quite understandably, there should be at least one support vector from each class.
The identification of support vectors requires intense mathematical formulation.

1. Hyperplane

o In an *n*-dimensional space, a hyperplane is a flat affine subspace of dimension *n-1*.

o For a 2D space, it's a line; in 3D, it's a plane.

2. Margin

o The distance between the hyperplane and the closest data points (called support vectors) from
each class.

o A larger margin improves generalization and reduces overfitting.

3. Maximum Margin Hyperplane

o The hyperplane that maximizes the distance to the nearest training examples (support vectors)
of both classes.

o It is the solution to the optimization problem in SVM.

Mathematical Formulation:

For a linearly separable dataset with labels:

wT x + b=0
𝟐
that maximizes the margin subject to the constraints:
∥𝒘∥

Yi (wTxi+b) ≥ 1 ∀i
This is equivalent to minimizing:

𝟏
∥w∥2
𝟐

Identifying the MMH for non-linearly separable data

Soft Margin for Non-Linearly Separable Data

If data is not perfectly separable, a soft-margin SVM allows some misclassifications using slack variables ξi,
which provides some soft margin for data instances in one class that fall on the wrong side of the hyperplane.

Figure7.22, a data instance belonging to the circle class falls on the side of the hyperplane designated for the
data instances belonging to the triangle class. The same issue also happens for a data instance belonging to
the triangle class.

FIG. 7.22 Drawing the MMH for non-linearly separable data

where C controls the trade-off between margin width and classification errors.

Kernel trick

Kernel Trick for Non-Linear Separation

If data is not linearly separable, SVM can use kernel functions (e.g., RBF, polynomial) to map data into a
higher-dimensional space where a linear hyperplane can separate classes.