Support Vector Machine (SVM)

SVM aims to find the hyperplane that best seperates data points of different classes in a high dimensional space. Aim is to maximize margins between the hyperplane and closest points from the dataset.

Implementation

1. textual data represented as vectors using TF-IDF
2. equation of hyperplane given as: $w\cdot x+b=0$
3. distance between a point $x$ to a hyperplane is $\frac{|w\cdot x+b|}{||w|{|}^2}$
4. SVM aims to minimize value of $||w|{|}^2$
5. this is known as the 'primal' problem of SVMs

Opitimization

1. Hinge Loss Function

$$c(x,y,f(x))=\{\begin{array}{ll}0,& \text{if }y\ast f(x)\ge 1\\ 1-y\ast f(x),& \text{else}\end{array}$$

• if predicted value and actual value have the same sign, cost is 0
• otherwise we calculat the loss value

2. Regularisation Function

$$C\ast ||w|{|}^2$$

The regularization function is often added to discourage the model from fitting the training data too closely and overfitting.

Kernels

What is a Kernel?

A kernel is a function that compares 2 data points and returns 1 similarity score.

2 Inputs --> Kernel Function --> 1 Similarity Score

During training, the kernel compares many pairs of training points. This produces a kernel matrix, also called a gram matrix.

SVM uses these similarity scores to find the class boundary. Basically draw hyperplane.

The width of kernel represents the distance over which two points are considered similar.

• data in input space is not linearly seperable so we need to represent/map it in a higher dimensional space so that they become linearly seperable
• this representing onto a higher dimension is called the kernel trick

$$K(x_1,x_2)=\varphi (x_1)\cdot \varphi (x_2)$$

LHS represents the kernel function that takes in our lower dimensional $x1$ and $x2$ and gives us a single value. RHS represents a transformation, $\varphi$ of $x1$ and $x2$ onto a higher dimension.

• since we are dealing with a high dimensional space, we might think we have to explicitly calculate the coordinates of data points in the higher dimension
• however, instead of doing this, we can compute dot products between the data points in this space

For Example:
With $a=(1,2)$ and $b=(3,1)$:

Route	Working	Result
Kernel	$a\cdot b=3+2=5$, then $5^2=25$	25
Transform	$\varphi (a)=(1,2\sqrt{2},4)$ and $\varphi (b)=(9,3\sqrt{2},1)$, then their dot product is $9+12+4=25$	25

Types of Kernels

Type of SVM	Mercer Kernel	Description
Radial Basis Function	$K(x_1,x_2)=\exp \left(-\frac{\Vert x_1-x_2{\Vert }^2}{2{\sigma }^2}\right)$	One class learning with $\sigma$ as the width of the kernel
Linear	$K(x_1,x_2)=x_1^T{x}_2$	Two class learning
Polynomial	$K(x_1,x_2)=(x_1^T{x}_2+1{)}^{\rho }$	$\rho$ is the order of the polynomial
Sigmoid	$K(x_1,x_2)=\tanh ({\beta }_0{x}_1^T{x}_2+{\beta }_1)$	A Mercer kernel only for certain values of ${\beta }_0$ and ${\beta }_1$

Intuitive Understanding of the variables:

$\sigma$ (width of kernel): this represents the distance between 2 points at which it is still considered similar.

Another way to see it is that $\sigma$ controls how quickly that similarity decreases:

• small $\sigma$: narrow influence, therefore only very close points are similar
• large $\sigma$: wide influence, farther points are also considered similar

Code

from sklearn import svm
 
# Create a svm Classifier
clf = svm.SVC(kernel='rbf')  # RBF kernel
 
# Train the model using the training sets
clf.fit(train_review_tfidf, train_sent)
 
# Predict the response for test dataset
y_pred = clf.predict(test_review_tfidf)

from sklearn import svm
 
svm = svm.SVC(kernel='linear')
svm.fit(X_train, y_train)
 
predictions = svm.predict(X_test)
print("Predictions:", predictions)
print("Labels:", y_test)

• SVC stands for Support Vector Classifier, and it lives in sklearn.svm
• the input is already vectorised, so TfidfVectorizer must run before fit
• kernel accepts 'linear', 'rbf', 'poly' and 'sigmoid', which are the 4 available kernels
• the default kernel is 'rbf', so svm.SVC() with no argument is the RBF version
• gamma sets the kernel width for 'rbf', where a large gamma gives a narrow reach and a wiggly boundary
• C controls the penalty for training mistakes, and in sklearn a large C means less regularisation

SVM needs its text as vectors before it can find a boundary, and the usual choice is Term Frequency-Inverse Document Frequency (TF- IDF).