Implementing a linear, binary SVM support vector machine

machine learning

support vector machine

SVM implementation

binary classification

linear models

Implementing a linear, binary SVM support vector machine

Master System Design with Codemia

Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.

Start Practicing Learn More

Introduction

A linear binary SVM (Support Vector Machine) finds the hyperplane that maximizes the margin between two classes. The "support vectors" are the data points closest to the decision boundary — they alone determine the hyperplane's position. SVMs are effective for high-dimensional data and work well when classes are linearly separable. scikit-learn's LinearSVC and SVC(kernel='linear') provide production-ready implementations, while understanding the math behind the margin and the hinge loss helps you tune the model and interpret results.

SVM with scikit-learn

python

1from sklearn.svm import SVC
2from sklearn.datasets import make_classification
3from sklearn.model_selection import train_test_split
4from sklearn.metrics import accuracy_score, classification_report
5
6# Generate binary classification data
7X, y = make_classification(n_samples=200, n_features=2, n_redundant=0,
8                           n_clusters_per_class=1, random_state=42)
9
10X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
11
12# Linear SVM
13model = SVC(kernel='linear', C=1.0)
14model.fit(X_train, y_train)
15
16y_pred = model.predict(X_test)
17print(f"Accuracy: {accuracy_score(y_test, y_pred):.4f}")
18print(classification_report(y_test, y_pred))

SVC(kernel='linear') trains a linear SVM using the SMO (Sequential Minimal Optimization) algorithm. The C parameter controls the trade-off between maximizing the margin and minimizing classification errors.

Using LinearSVC (Faster for Large Datasets)

python

1from sklearn.svm import LinearSVC
2from sklearn.preprocessing import StandardScaler
3from sklearn.pipeline import Pipeline
4
5pipeline = Pipeline([
6    ('scaler', StandardScaler()),
7    ('svm', LinearSVC(C=1.0, max_iter=10000))
8])
9
10pipeline.fit(X_train, y_train)
11y_pred = pipeline.predict(X_test)
12print(f"Accuracy: {accuracy_score(y_test, y_pred):.4f}")

LinearSVC uses the liblinear library and scales to millions of samples. It is significantly faster than SVC(kernel='linear') for large datasets because it uses a different optimization algorithm that avoids computing the kernel matrix.

Understanding the Math

python

1import numpy as np
2
3# The decision function: f(x) = w · x + b
4# w = weight vector (normal to the hyperplane)
5# b = bias (intercept)
6
7model = SVC(kernel='linear', C=1.0)
8model.fit(X_train, y_train)
9
10# Extract weights and bias
11w = model.coef_[0]
12b = model.intercept_[0]
13print(f"Weights: {w}")
14print(f"Bias: {b}")
15
16# Decision function for a new point
17x_new = np.array([[1.0, 2.0]])
18decision = np.dot(w, x_new[0]) + b
19print(f"Decision value: {decision:.4f}")
20print(f"Predicted class: {1 if decision >= 0 else 0}")
21
22# Support vectors
23print(f"Number of support vectors: {len(model.support_vectors_)}")
24print(f"Support vectors per class: {model.n_support_}")

The SVM finds w and b that maximize the margin 2/||w|| while correctly classifying training points. Points with |w·x + b| = 1 lie on the margin boundary and are the support vectors.

Visualizing the Decision Boundary

python

1import matplotlib.pyplot as plt
2import numpy as np
3
4model = SVC(kernel='linear', C=1.0)
5model.fit(X_train, y_train)
6
7# Create mesh grid
8x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
9y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
10xx, yy = np.meshgrid(np.linspace(x_min, x_max, 200),
11                      np.linspace(y_min, y_max, 200))
12
13Z = model.decision_function(np.c_[xx.ravel(), yy.ravel()])
14Z = Z.reshape(xx.shape)
15
16plt.contourf(xx, yy, Z, levels=[-1, 0, 1], alpha=0.3, colors=['blue', 'white', 'red'])
17plt.contour(xx, yy, Z, levels=[-1, 0, 1], colors='black', linestyles=['--', '-', '--'])
18plt.scatter(X_train[:, 0], X_train[:, 1], c=y_train, cmap='bwr', edgecolors='k')
19plt.scatter(model.support_vectors_[:, 0], model.support_vectors_[:, 1],
20            s=100, facecolors='none', edgecolors='green', linewidths=2)
21plt.title("Linear SVM Decision Boundary")
22plt.show()

The solid line is the decision boundary (w·x + b = 0). The dashed lines are the margin boundaries (w·x + b = +/-1). Green circles mark the support vectors.

Effect of C Parameter

python

1from sklearn.svm import SVC
2import numpy as np
3
4for C in [0.01, 0.1, 1.0, 10.0, 100.0]:
5    model = SVC(kernel='linear', C=C)
6    model.fit(X_train, y_train)
7    train_acc = model.score(X_train, y_train)
8    test_acc = model.score(X_test, y_test)
9    n_sv = len(model.support_vectors_)
10    print(f"C={C:6.2f}  Train: {train_acc:.4f}  Test: {test_acc:.4f}  SVs: {n_sv}")

C value	Margin	Tolerance for errors	Risk
Small (0.01)	Wide	High (soft margin)	Underfitting
Medium (1.0)	Balanced	Moderate	Good default
Large (100)	Narrow	Low (hard margin)	Overfitting

Small C allows more margin violations for a wider margin. Large C penalizes violations heavily, fitting the training data more tightly.

SVM from Scratch (Gradient Descent)

python

1import numpy as np
2
3class LinearSVM:
4    def __init__(self, C=1.0, lr=0.001, epochs=1000):
5        self.C = C
6        self.lr = lr
7        self.epochs = epochs
8
9    def fit(self, X, y):
10        # Convert labels to {-1, +1}
11        y_svm = np.where(y == 0, -1, 1)
12        n_samples, n_features = X.shape
13        self.w = np.zeros(n_features)
14        self.b = 0
15
16        for _ in range(self.epochs):
17            for i in range(n_samples):
18                margin = y_svm[i] * (np.dot(X[i], self.w) + self.b)
19                if margin >= 1:
20                    # Correctly classified, outside margin
21                    self.w -= self.lr * self.w  # Regularization only
22                else:
23                    # Misclassified or inside margin
24                    self.w -= self.lr * (self.w - self.C * y_svm[i] * X[i])
25                    self.b += self.lr * self.C * y_svm[i]
26
27    def predict(self, X):
28        decision = np.dot(X, self.w) + self.b
29        return np.where(decision >= 0, 1, 0)
30
31# Usage
32svm = LinearSVM(C=1.0, lr=0.001, epochs=1000)
33svm.fit(X_train, y_train)
34y_pred = svm.predict(X_test)
35print(f"Accuracy: {accuracy_score(y_test, y_pred):.4f}")

This implements the hinge loss SVM using stochastic gradient descent. The loss function is max(0, 1 - y*(w·x + b)) plus L2 regularization ||w||^2. Production code should use scikit-learn, but this shows the core algorithm.

Common Pitfalls

Not scaling features: SVMs are sensitive to feature scales because the margin depends on distances. A feature with range [0, 100000] dominates one with range [0, 1]. Always standardize with StandardScaler before fitting.
Using SVC for large datasets: SVC has O(n^2) to O(n^3) time complexity. For datasets over 10,000 samples, use LinearSVC or SGDClassifier(loss='hinge') which scale linearly.
Ignoring the C parameter: The default C=1.0 may not be optimal. Use GridSearchCV or RandomizedSearchCV to find the best C value for your data, typically searching over [0.001, 0.01, 0.1, 1, 10, 100].
Expecting probability outputs: SVC does not compute probabilities by default. Set probability=True to enable predict_proba(), but this adds computation time (Platt scaling) and may slow training.
Using linear SVM for non-linearly separable data: If classes overlap or have non-linear boundaries, a linear SVM will underfit. Use SVC(kernel='rbf') for non-linear decision boundaries, or engineer polynomial features.

Summary

SVC(kernel='linear') and LinearSVC implement linear binary SVMs in scikit-learn
The SVM finds the hyperplane that maximizes the margin between two classes
C controls the margin width: small C = wide margin (may underfit), large C = narrow margin (may overfit)
Always scale features with StandardScaler before fitting an SVM
Use LinearSVC for datasets over 10,000 samples (faster than SVC)
Support vectors are the training points closest to the decision boundary — they define the model