Bansilal Ramnath Agarwal Charitable Trust’s
Vishwakarma Institute of Technology, Pune-37
(An autonomous Institute of Savitribai Phule Pune University)
Department of Artificial Intelligence
Machine Learning Practicals
Division AI-C
Batch 3
GR No 12420212
Roll No 67
Name Gayatri Bhurguda
Implement Linear SVM from scratch on a dataset of your
choice.
Implement Non-Linear SVM using sk learn. Experiment
with different kernels and find the best suited kernel for a
perticular dataset.
Theory:
1. Concept:
Support Vector Machine (SVM) is a supervised machine learning algorithm mainly used for
classification and regression tasks. It works by finding the optimal separating boundary —
called a hyperplane — that best divides data points of different classes in a feature space. The
goal is to maximize the margin, which is the distance between the hyperplane and the nearest
data points from each class. These nearest points are called support vectors, as they are the
most critical elements in determining the decision boundary.
2. Working Principle:
SVM tries to solve an optimization problem where it maximizes the margin while minimizing
classification errors. For linearly separable data, SVM finds a straight hyperplane. For non-
linear data, it uses a kernel function (like polynomial, radial basis function (RBF), or
sigmoid) to map data into a higher-dimensional space where it becomes linearly separable.
This “kernel trick” allows SVM to handle complex, non-linear decision boundaries efficiently
without explicitly increasing dimensionality.
3. Advantages and Applications:
SVMs are effective in high-dimensional spaces and are robust against overfitting, especially
when the number of features is greater than the number of samples. They perform well for
image recognition, text categorization, and bioinformatics problems like gene classification.
However, SVMs can be computationally expensive for large datasets and require careful
parameter tuning (like choosing the right kernel and regularization parameter) to achieve
optimal performance.
Code:
1)
import numpy as np
import [Link] as plt
# Generate dummy linearly separable data
[Link](42)
# Class -1
X1 = [Link](20, 2) - [2, 2]
y1 = -1 * [Link](20)
# Class +1
X2 = [Link](20, 2) + [2, 2]
y2 = +1 * [Link](20)
# Combine
X = [Link]((X1, X2))
y = [Link]((y1, y2))
# SVM parameters
alpha = 0.001 # learning rate
lambda_param = 0.01 # regularization strength
n_epochs = 1000
w = [Link]([Link][1])
b=0
# Training loop (gradient descent on hinge loss)
for epoch in range(n_epochs):
for i, x_i in enumerate(X):
condition = y[i] * ([Link](x_i, w) - b)
if condition >= 1:
# Only regularization gradient
w -= alpha * (2 * lambda_param * w)
else:
# Misclassified -> update rule
w -= alpha * (2 * lambda_param * w - y[i] * x_i)
b -= alpha * y[i]
print("Weights:", w)
print("Bias:", b)
# Prediction function
def predict(X):
return [Link]([Link](X, w) - b)
# Plot decision boundary + margins + support vectors
[Link](figsize=(8,6))
[Link](X[:,0], X[:,1], c=y, cmap='bwr', alpha=0.7)
# Decision boundary
a = -w[0]/w[1]
xx = [Link](-5, 5)
yy = a * xx + b/w[1]
[Link](xx, yy, 'k--', label="Decision boundary")
# Margins (parallel lines at distance 1/||w||)
margin = 1 / [Link]([Link](w**2))
yy_margin_up = a * xx + (b + 1)/w[1]
yy_margin_down = a * xx + (b - 1)/w[1]
[Link](xx, yy_margin_up, 'g-', label="Margin +1")
[Link](xx, yy_margin_down, 'g-', label="Margin -1")
# Highlight support vectors (close to margin)
pred_dist = ([Link](X, w) - b) / [Link](w)
support_vector_idx = [Link]([Link](pred_dist) <= 1 + 1e-2)[0]
[Link](X[support_vector_idx, 0], X[support_vector_idx, 1],
s=200, facecolors='none', edgecolors='k', linewidths=2,
label="Support Vectors")
[Link]()
[Link]("SVM with Decision Boundary, Margins, and Support Vectors")
[Link]()
2)
import numpy as np
import [Link] as plt
# Kernel functions
def linear_kernel(x1, x2):
return [Link](x1, x2)
def polynomial_kernel(x1, x2, degree=3, coef0=1):
return ([Link](x1, x2) + coef0) ** degree
def rbf_kernel(x1, x2, gamma=0.5):
diff = x1 - x2
return [Link](-gamma * [Link](diff, diff))
def sigmoid_kernel(x1, x2, coef0=1, gamma=0.5):
return [Link](gamma * [Link](x1, x2) + coef0)
# Compute kernel matrix
def compute_kernel_matrix(X, kernel_func, **kwargs):
n_samples = [Link][0]
K = [Link]((n_samples, n_samples))
for i in range(n_samples):
for j in range(n_samples):
K[i, j] = kernel_func(X[i], X[j], **kwargs)
return K
# Train using dual form SGD
def train_svm(X, y, kernel_func, kernel_params={}, alpha=0.001, lambda_param=0.01,
n_epochs=500):
n_samples = [Link][0]
alphas = [Link](n_samples)
b=0
K = compute_kernel_matrix(X, kernel_func, **kernel_params)
for epoch in range(n_epochs):
for i in range(n_samples):
decision = [Link](alphas * y * K[:, i]) + b
if y[i] * decision < 1:
alphas[i] += alpha * (1 - y[i] * decision) - alpha * lambda_param * alphas[i]
else:
alphas[i] -= alpha * lambda_param * alphas[i]
# Update bias occasionally
b += alpha * [Link](y - ([Link](alphas * y * K, axis=1) + b))
return alphas, b
# Prediction
def predict(X_train, y_train, alphas, b, X_test, kernel_func, kernel_params={}):
y_pred = []
for x in X_test:
result = 0
for i in range(len(X_train)):
result += alphas[i] * y_train[i] * kernel_func(X_train[i], x, **kernel_params)
result += b
y_pred.append([Link](result))
return [Link](y_pred)
# Plotting function
def plot_svm(X, y, alphas, b, kernel_func, kernel_params, ax, title):
[Link](X[:, 0], X[:, 1], c=y, cmap='bwr', alpha=0.7)
xx, yy = [Link]([Link](-5, 5, 200), [Link](-5, 5, 200))
grid = np.c_[[Link](), [Link]()]
Z = predict(X, y, alphas, b, grid, kernel_func, kernel_params)
Z = [Link]([Link])
[Link](xx, yy, Z, alpha=0.3, levels=[Link](-1, 1, 3), colors=['blue', 'red'])
support_vector_idx = [Link](alphas > 1e-4)[0]
[Link](X[support_vector_idx, 0], X[support_vector_idx, 1],
s=200, facecolors='none', edgecolors='k', linewidths=2,
label="Support Vectors")
ax.set_title(title)
[Link]()
# Prepare datasets for each kernel
def generate_datasets():
[Link](42)
# Linear Kernel: Overlapping blobs
X1 = [Link](20, 2) - [1, 1]
y1 = -1 * [Link](20)
X2 = [Link](20, 2) + [1, 1]
y2 = +1 * [Link](20)
X_linear = [Link]((X1, X2))
y_linear = [Link]((y1, y2))
# Polynomial Kernel: XOR pattern
X1 = [Link](20, 2) * 0.5 + [1, 1]
X2 = [Link](20, 2) * 0.5 + [-1, -1]
X3 = [Link](20, 2) * 0.5 + [-1, 1]
X4 = [Link](20, 2) * 0.5 + [1, -1]
X_poly = [Link]((X1, X2, X3, X4))
y_poly = [Link]((+1*[Link](20), +1*[Link](20), -1*[Link](20), -1*[Link](20)))
# RBF Kernel: Concentric circles
r_inner = 2
r_outer = 4
theta_inner = 2 * [Link] * [Link](20)
X1 = np.c_[r_inner * [Link](theta_inner), r_inner * [Link](theta_inner)] + 0.5 *
[Link](20, 2)
y1 = -1 * [Link](20)
theta_outer = 2 * [Link] * [Link](20)
X2 = np.c_[r_outer * [Link](theta_outer), r_outer * [Link](theta_outer)] + 0.5 *
[Link](20, 2)
y2 = +1 * [Link](20)
X_rbf = [Link]((X1, X2))
y_rbf = [Link]((y1, y2))
# Sigmoid Kernel: Two blobs with some overlap
X1 = [Link](20, 2) - [2, 0]
y1 = -1 * [Link](20)
X2 = [Link](20, 2) + [2, 0]
y2 = +1 * [Link](20)
X_sigmoid = [Link]((X1, X2))
y_sigmoid = [Link]((y1, y2))
return (X_linear, y_linear), (X_poly, y_poly), (X_rbf, y_rbf), (X_sigmoid, y_sigmoid)
# Main execution
datasets = generate_datasets()
fig, axs = [Link](2, 2, figsize=(12, 10))
# Linear Kernel
X, y = datasets[0]
alphas, b = train_svm(X, y, linear_kernel)
plot_svm(X, y, alphas, b, linear_kernel, {}, axs[0, 0], "Linear Kernel")
# Polynomial Kernel
X, y = datasets[1]
alphas, b = train_svm(X, y, polynomial_kernel, kernel_params={'degree':3, 'coef0':1})
plot_svm(X, y, alphas, b, polynomial_kernel, {'degree':3, 'coef0':1}, axs[0, 1], "Polynomial
Kernel")
# RBF Kernel
X, y = datasets[2]
alphas, b = train_svm(X, y, rbf_kernel, kernel_params={'gamma':0.5})
plot_svm(X, y, alphas, b, rbf_kernel, {'gamma':0.5}, axs[1, 0], "RBF Kernel")
# Sigmoid Kernel
X, y = datasets[3]
alphas, b = train_svm(X, y, sigmoid_kernel, kernel_params={'coef0':1, 'gamma':0.5})
plot_svm(X, y, alphas, b, sigmoid_kernel, {'coef0':1, 'gamma':0.5}, axs[1, 1], "Sigmoid
Kernel")
plt.tight_layout()
[Link]()
Output: