How to implement SVM algorithm from scratch in a programming language?

I'm a computer scientist who's studying support vector machines (SVMs) in a machine learning course. I have some understanding of how SVMs are designed, thanks to 16. Learning: Support Vector Machines - MIT. However, what I'm not understanding is the transition from the optimization problem of the Lagrangian function to its implementation in any programming language. Basically, what I need to understand is how to build, from scratch, the decision function, given a training set. In particular, how do I find Lagrange multipliers in order to know which points are to be considered to define support vectors and the decision function?

Can anyone explain this to me?

• We're you ever able to answer your question because I have arrived at a similar point? Feb 16 '20 at 5:41

Based on this repository:

https://github.com/arkm97/svm-from-scratch/blob/master/SVM_from_scratch.ipynb

I will try to reverse engineering that concept:

So firstly there is issue for DataCleaning(removing 0,values, serialize, normalize)

normalizing dataset (replaced by its difference from the mean)

credit_df_norm = (credit_df - credit_df.mean())/(credit_df.std())

Divide dataset into Train & Test:

train_df = credit_df_norm.drop(target, axis=1).loc[:training_points]
train_target = credit_df_norm[target].replace(0, -1).loc[:training_points]

And here is starting the clue of that algorithms (with maths etc.)

given data points $$\vec x_j \in \mathbb{R}^{1 \times N}$$ and targets $$y_j = \pm 1$$, where $$j = 1, \dots, M$$, find the maximum-margin hyperplane that separates the two classes ($$y_j = 1$$ and $$y_j = -1$$).

Let $$\vec w$$ be the vector normal to the hyperplane. We want to find $$\vec w$$ that satisfies

$$y_j (\vec w \cdot \vec x_j + b) \geq 1$$ The dual formulation of the above is equivalent to maximizing the following over the multipliers $$\vec \alpha$$:

$$L(\vec \alpha) = \vec y \cdot \vec \alpha - \frac 1 2 \vec \alpha > K \vec \alpha^T$$ subject to the constraints $$\sum_{j=1}^M \alpha_j = > 0$$ and $$y_j \alpha_j \geq 0$$. The matrix $$K$$ defines the kernel of the SVM; I've chosen $$K_{jk} = k(\vec x_j, \vec x_k) = \vec x_j \cdot \vec > x_k$$. The parameters of the plane are recovered from $$\vec w = \vec > \alpha \cdot \vec x$$ and $$b = y_j = \vec w \cdot \alpha_j$$ for $$j$$ such that $$\alpha_j \neq 0$$

Let's divide it to the single factors:

we need to find maximum-margin-hyperplane for separate into two classes: Separation cause SVN is classification - so we need to classify elements into categories.

𝑦𝑗 = 1

𝑦𝑗 = −1

This pattern allow to find hyperplane(?)

𝑦𝑗(𝑤⃗ ⋅𝑥⃗ 𝑗+𝑏)≥1

The next pattern:

𝐿(𝛼⃗ )=𝑦⃗ ⋅𝛼⃗ −12𝛼⃗ >𝐾𝛼⃗ 𝑇

The author for kernel SVN choose those pattern:

𝐾𝑗𝑘=𝑘(𝑥⃗ 𝑗,𝑥⃗ 𝑘)=𝑥⃗ 𝑗⋅>⃗ 𝑥𝑘

And the parameters for plane are here:

𝑤⃗ =>⃗ 𝛼⋅𝑥⃗ and 𝑏=𝑦𝑗=𝑤⃗ ⋅𝛼𝑗 for 𝑗 such that 𝛼𝑗≠0

Reference: https://arxiv.org/pdf/1307.0471.pdf

In this line are added the kernel

Popular kernels are:

• Polynomial Kernel,

• Gaussian Kernel,

• Laplace RBF Kernel,

• Sigmoid Kernel,

• Anove RBF Kernel

k_value = np.array(train_df @ train_df.T + np.identity(len(train_target))*1e-12)

The structure of k_value (kernel matrix) is an array. Next there is use of cholesky decomposition—cholesky - which is next complicated concept.

np.linalg.cholesky(k_value)

Next some bits of data converting:

alpha = cp.Variable(shape=train_target.shape)

beta = cp.multiply(alpha, train_target) # to simplify notation

K = cp.Parameter(shape=k_value.shape, PSD=True, value=k_value)

# objective function
obj = .5 * cp.quad_form(beta, K) - np.ones(alpha.shape).T @ alpha

# constraints
const = [np.array(train_target.T) @ alpha == 0,
-alpha <= np.zeros(alpha.shape),
alpha <= 10*np.ones(shape=alpha.shape)]
prob = cp.Problem(cp.Minimize(obj), const)

The next step is recreate the hyperplane:

w = np.multiply(train_target, alpha.value).T @ train_df
S = (alpha.value > 1e-4).flatten()
b = train_target[S] - train_df[S] @ w
b = b
# b = np.mean(b)

And finally - the classification and evaluation:

def classify(x):
result = w @ x + b
return np.sign(result)

correct = 0
incorrect = 0
validation_set = credit_df_norm.drop(target, axis=1)
predictions = []
for i, x in validation_set.iterrows():
my_svm = classify(x)
if my_svm==credit_df_norm[target].replace(0, -1)[i]: correct +=1
else: incorrect +=1
predictions.append(my_svm)
predictions = np.array(predictions)

print(f"fraction correct: {correct/(correct + incorrect)}")

That was the more detailed implementation - for shorcut there is an interesting article:

https://towardsdatascience.com/svm-and-kernel-svm-fed02bef1200

There are existing function from another library - that can be reused in simple manner:

# Fitting SVM to the Training set
from sklearn.svm import SVC
classifier = SVC(kernel = 'rbf', C = 0.1, gamma = 0.1)
classifier.fit(X_train, y_train)

%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
from scipy import stats

# use seaborn plotting defaults
import seaborn as sns; sns.set()

Visualized Dataset: Dataset after apply hyperplanes: 