School year 2025-2026/ Second Semester/ FET / Computer Engineering
CEF444: Artificial Intelligence and machine learning
Chapter 7: Support Vector machine: SVM
I. Introduction
I guess by now you would’ve accustomed yourself with supervised machine learning
algorithm such as simple linear regression, multi linear regression and KNN algorithms.
Support vector machine is another simple algorithm that every machine learning expert
should have in his/her arsenal. Support vector machine is highly preferred by many as it
produces significant accuracy with less computation power. Support Vector Machine,
abbreviated as SVM can be used for both regression and classification tasks. But, it is widely
used in classification objectives.
What is Support Vector Machine?
To separate the two classes of data points, there are many possible hyperplanes that could be
chosen. Our objective is to find a plane that has the maximum margin, i.e the maximum
Proposed by Dr. SOP DEFFO Lionel L. Page 1
School year 2025-2026/ Second Semester/ FET / Computer Engineering
distance between data points of both classes. Maximizing the margin distance provides some
reinforcement so that future data points can be classified with more confidence.
Hyperplanes and Support Vectors
Hyperplanes are decision boundaries that help classify the data points. Data points falling on either
side of the hyperplane can be attributed to different classes. Also, the dimension of the hyperplane
depends upon the number of features. If the number of input features is 2, then the hyperplane is just a
line. If the number of input features is 3, then the hyperplane becomes a two-dimensional plane. It
becomes difficult to imagine when the number of features exceeds 3.
Support vectors are data points that are closer to the hyperplane and influence the position and
orientation of the hyperplane. Using these support vectors, we maximize the margin of the classifier.
Proposed by Dr. SOP DEFFO Lionel L. Page 2
School year 2025-2026/ Second Semester/ FET / Computer Engineering
Deleting the support vectors will change the position of the hyperplane. These are the points that help
us build our SVM.
So, How to find this hyperplane?
Let’s point out what exactly do we want.
1. We need a line that should separate the blue and red points
2. and that line should have a maximum margin.
3. It should be easy to calculate.
Consider a line (hyperplane) which separates the points optimally as shown below. The points
on the inner side of the line are red and on the outer side is the blue one. This line is optimal
hyperplane ie it has a maximum margin. We have the point u which is unknown to us and we
want to decide whether it is red or blue. A vector w̅ has drawn such that it is perpendicular to
our line while the vector u̅ is point vector to u. x̅r and x̅b are vectors for a red and blue point
respectively.
Proposed by Dr. SOP DEFFO Lionel L. Page 3
School year 2025-2026/ Second Semester/ FET / Computer Engineering
The dot product of w̅ and u̅ decides whether the point u is red or blue. If it is greater than
certain value then it is blue else it is red.
To simplify things we are introducing a new symbol y in the equation so that these two
conditions can be merged. Let us consider y = +1 for blue and -1 for red. After multiplying y
with both equations we get the following equation.
We have constraints about our point as shown in Equation 1. Next thing we want to do is to
find the width of our margin.
Width
To find the width, we can use the dot product of unit vector in direction of w̅ and (x̅b- x̅r) as
shown in our 2D space.
This equation exactly represents the margin. We can fit the Equation 2 into this equation and
we will get the following result.
We want our points to be as separated as possible ie we want this width to be maximum.
Here, w̅ can be minimised to increase the width. In other words we can write this as below
Proposed by Dr. SOP DEFFO Lionel L. Page 4
School year 2025-2026/ Second Semester/ FET / Computer Engineering
Recap 1
Let’s just recap what we just did. First, we made some assumptions about our points. We
considered one red and one blue point which is closest to our hyperplane. After performing
vector operations, we found the Equation 2 that is satisfied by every point in space. We then
focused on finding our margin. The width can be calculated just by finding the distance
between selected points. The dot product of distance and a unit vector gives us the width. We
are trying to maximise this width so that we get better results from out of this algorithm. Nice!
Lagrange Multiplier
We have some rules in the form of Equation 2 and we want to maximise the margin. This is
exactly where we can use one of constraint optimisation technique called Lagrange Multiplier
technique. To find the optimal value of any parameters x and y we can use the following
equation
Here we have width as function R and Equation 2 as function B. So, in the end we get
something like this
In Equation 4, α represents the lagrange multiplayer and the b represents the constant. In our
case, as the constrain applies to each point in space, we take summation of constraint on each
point. To know more about lagrange multiplayers you can follow this course.
To maximise the width we need to prove that ∇ L = 0. After doing some calculation we can
get the following interesting things
Proposed by Dr. SOP DEFFO Lionel L. Page 5
School year 2025-2026/ Second Semester/ FET / Computer Engineering
Great! after putting the corresponding values in equation 4 we can get the following equation
Recap 2
After finding the width and all of the constraints we want to maximise the width. In simple
terms we want to separate red points as blue as far as possible. To do that we used a technique
which helped us to maximise the width. ∇ L ie is the gradient of L is zero when we achieve
that maximum width. While proving ∇ L = 0 we found two more equations which helped us to
simplify our equation 4.
Kernel Trick
Notice our final equation, we can see that while obtaining the ∇ L =0 ie while maximising the
margin the only term matters is (x̅i .x̅j ) ie dot product of pair of points. In a same way if we
put the values obtained in equation 5 and 6 we get the following equation.
In constraint we found the same pattern. The value of the u depends on the dot product with
the point in that class. We can further extend this analogy and apply it not just in 2D space but
also in multidimensional space. This technique is called kernel trick.
Proposed by Dr. SOP DEFFO Lionel L. Page 6
School year 2025-2026/ Second Semester/ FET / Computer Engineering
We can use this trick in any no of dimensions without needing the lot of computation. This
makes the SVM very aggressive in image classification.
There are lot of kernels in SVM. In most cases we can use linear kernel. While calculating the
SVM is bit hard, there is very simple implementation of SVM in python’s Scikit-learn library
II. SVM Implementation in Python
Now, we’re ready to write some code. We’ll start off by importing the necessary libraries.
import numpy as np
import cvxopt
from [Link].samples_generator import make_blobs
from sklearn.model_selection import train_test_split
from matplotlib import pyplot as plt
from [Link] import LinearSVC
from [Link] import confusion_matrix
Proposed by Dr. SOP DEFFO Lionel L. Page 7
School year 2025-2026/ Second Semester/ FET / Computer Engineering
Then, we define our SVM class. Instead of using gradient descent to find the best fitting line
as in the case of Linear Regression, we can directly solve for w and b using the Lagrangian.
class SVM:
def fit(self, X, y):
n_samples, n_features = [Link]
# P = X^T X
K = [Link]((n_samples, n_samples))
for i in range(n_samples):
for j in range(n_samples):
K[i,j] = [Link](X[i], X[j])
P = [Link]([Link](y, y) * K)
# q = -1 (1xN)
q = [Link]([Link](n_samples) * -1)# A = y^T
A = [Link](y, (1, n_samples))# b = 0
b = [Link](0.0)# -1 (NxN)
G = [Link]([Link]([Link](n_samples) * -1))# 0 (1xN)
h = [Link]([Link](n_samples))
solution = [Link](P, q, G, h, A, b)# Lagrange
multipliers
a = [Link](solution['x'])# Lagrange have non zero lagrange
multipliers
sv = a > 1e-5
ind = [Link](len(a))[sv]
self.a = a[sv]
[Link] = X[sv]
self.sv_y = y[sv]# Intercept
Proposed by Dr. SOP DEFFO Lionel L. Page 8
School year 2025-2026/ Second Semester/ FET / Computer Engineering
self.b = 0
for n in range(len(self.a)):
self.b += self.sv_y[n]
self.b -= [Link](self.a * self.sv_y * K[ind[n], sv])
self.b /= len(self.a)# Weights
self.w = [Link](n_features)
for n in range(len(self.a)):
self.w += self.a[n] * self.sv_y[n] * [Link][n]
def project(self, X):
return [Link](X, self.w) + self.b
def predict(self, X):
return [Link]([Link](X))
To keep things simple, we’ll use the scikit-learn library to generate linearly separable data.
We label the negative samples as -1 instead of 0. cvxopt expects the data to be in a specific
format which is why we take an intermediate step.
figure, axis = [Link](2, 2)
X, y = make_blobs(n_samples=250, centers=2,random_state=0,
cluster_std=0.60)
y[y == 0] = -1
tmp = [Link](len(X))
y = tmp * y
Let’s get a feel for the data by plotting it.
axis[0, 0].scatter(X[:, 0], X[:, 1], c=y, cmap='winter')
Proposed by Dr. SOP DEFFO Lionel L. Page 9
School year 2025-2026/ Second Semester/ FET / Computer Engineering
We split the data into training and testing sets.
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0)
Then, we create and train an instance of our support vector machine class.
svm = SVM()
[Link](X_train, y_train)
Next, we plot the decision boundary and support vectors.
def f(x, w, b, c=0):
return (-w[0] * x - b + c) / w[1]
axis[1, 0].scatter(X_train[:, 0], X_train[:, 1], c=y_train, cmap='winter')#
w.x + b = 0
a0 = -4; a1 = f(a0, svm.w, svm.b)
b0 = 4; b1 = f(b0, svm.w, svm.b)
axis[1, 0].plot([a0,b0], [a1,b1], 'k')# w.x + b = 1
a0 = -4; a1 = f(a0, svm.w, svm.b, 1)
b0 = 4; b1 = f(b0, svm.w, svm.b, 1)
axis[1, 0].plot([a0,b0], [a1,b1], 'k--')# w.x + b = -1
a0 = -4; a1 = f(a0, svm.w, svm.b, -1)
b0 = 4; b1 = f(b0, svm.w, svm.b, -1)
axis[1, 0].plot([a0,b0], [a1,b1], 'k--')
Proposed by Dr. SOP DEFFO Lionel L. Page 10
School year 2025-2026/ Second Semester/ FET / Computer Engineering
We use our model to predict the classes of the samples in the testing set. Given that we’re
using our model to classify data, we use a confusion matrix to evaluate its accuracy.
y_pred = [Link](X_test)
confusion_matrix(y_test, y_pred)
Let’s attempt the same thing using the scikit-learn implementation of the support vector
classifier.
svc = LinearSVC()
[Link](X_train, y_train)
After training our model, we plot the decision boundary and support vectors.
axis[1, 1].scatter(X_train[:, 0], X_train[:, 1], c=y_train, cmap='winter');
ax = [Link]()
xlim = ax.get_xlim()
w = svc.coef_[0]
a = -w[0] / w[1]
xx = [Link](xlim[0], xlim[1])
yy = a * xx - svc.intercept_[0] / w[1]
[Link](xx, yy)
yy = a * xx - (svc.intercept_[0] - 1) / w[1]
[Link](xx, yy, 'k--')
Proposed by Dr. SOP DEFFO Lionel L. Page 11
School year 2025-2026/ Second Semester/ FET / Computer Engineering
yy = a * xx - (svc.intercept_[0] + 1) / w[1]
[Link](xx, yy, 'k--')
[Link]()
Again, we predict which sample belongs to what class based off which side of the line they
fall.
y_pred = [Link](X_test)
confusion_matrix(y_test, y_pred)
print (confusion_matrix)
As we can see, the classifier correctly classified every sample.
III. Conclusion
We saw how we could go about using the Lagrangian to determine the line that best separates
our data. In the real world, most problems are not linear separable. Thus, we make use of
something called the kernel trick to separate the data using something other than a straight
line.
Proposed by Dr. SOP DEFFO Lionel L. Page 12