3.5 - Noah's Notes - Support vector machines (SVM) from scratch

A logistic regression draws a boundary between the two classes and turns the distance to that boundary into a probability. A support vector machine (SVM) also draws a boundary, but it chooses it with a different criterion: among all the lines that separate the classes, it looks for the one that leaves the widest margin, the widest "street" with no points inside. The points on the edge of the street, the support vectors, are the only ones that decide where the boundary goes.

In this notebook we implement a linear SVM ourselves, following the formulation in Martha's notes (section 3.4):

1. Import the libraries.
2. The book's example: two classes in the plane.
3. The cost function: the hinge loss.
4. Training with gradient descent.
5. Soft margin: the role of $\lambda$.
6. Back to the Physiotherapy no-shows.
7. Choosing $\lambda$ with k-fold cross-validation.
8. Evaluation and comparison with logistic regression.

Step 1: Import the libraries

---

As in the other from-scratch notebooks, we only use scikit-learn to split the data. Everything else is NumPy.

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split  # only to split the data

np.set_printoptions(precision=3, suppress=True)

Step 2: The book's example

---

We start with the 14 points of the linear SVM figure in section 3.4: seven of the positive class and seven of the negative class. An SVM labels the classes as $y = +1$ and $y = -1$ (instead of 1 and 0), because that makes the formulas simpler.

positive = np.array([[1, 5], [1.5, 4], [2, 5.5], [2.5, 4.5], [3, 5], [3.5, 3.75], [4, 4.8]])
negative = np.array([[3, 2], [3.5, 1.5], [4, 2.75], [4.5, 1.8], [5, 2.3], [5.5, 1.6], [6, 2]])

X_toy = np.vstack([positive, negative])
y_toy = np.array([1] * len(positive) + [-1] * len(negative))

plt.figure(figsize=(6, 5))
plt.scatter(*positive.T, color='tab:blue', s=60, label='class +1')
plt.scatter(*negative.T, color='tab:red', marker='s', s=60, label='class -1')
plt.xlabel('$x_1$')
plt.ylabel('$x_2$')
plt.title('Two linearly separable classes')
plt.legend()
plt.grid(True)
plt.show()

Infinitely many lines separate these two groups. The SVM looks for the boundary $f(x) = w \cdot x + b = 0$ that satisfies

$$y_i \, (w \cdot x_i + b) \geq 1 \quad \text{for every point } i$$

that is, positive points must have $f(x) \geq 1$ and negative points $f(x) \leq -1$. The two dashed lines $f(x) = +1$ and $f(x) = -1$ are the edges of the margin, and the distance between them is $\frac{2}{\|w\|}$. That is why minimizing $\frac{1}{2}\|w\|^2$ maximizes the margin.

Step 3: The cost function

---

Real data are rarely perfectly separable, so the book introduces the soft margin: each point may violate the condition by an amount $\xi_i \geq 0$ (its slack), and each violation is paid for:

$$\min_{w, b} \quad \frac{1}{2}\|w\|^2 + \lambda \sum_{i=1}^{m} \xi_i \qquad \text{with} \qquad \xi_i = \max\big(0,\; 1 - y_i (w \cdot x_i + b)\big)$$

The expression $\max(0, 1 - y_i f(x_i))$ is the hinge loss. It is zero for a point that is on the right side and outside the margin, and it grows linearly as the point enters the margin or crosses to the wrong side. Let's compare it with the log loss of logistic regression, as a function of $y \cdot f(x)$ (positive when the point is well classified):

def hinge_loss(y, f):
    return np.maximum(0, 1 - y * f)

yf = np.linspace(-2, 3, 200)
plt.figure(figsize=(7, 4))
plt.plot(yf, hinge_loss(1, yf), label='hinge loss (SVM)')
plt.plot(yf, np.log(1 + np.exp(-yf)), label='log loss (logistic regression)')
plt.axvline(0, color='gray', linewidth=0.8)
plt.axvline(1, color='gray', linestyle='--', linewidth=0.8)
plt.xlabel('y · f(x)   (negative = wrong side, above 1 = outside the margin)')
plt.ylabel('Cost of the point')
plt.title('Hinge loss and log loss')
plt.legend()
plt.grid(True)
plt.show()

Both punish the points on the wrong side, but there is a key difference: the hinge loss is exactly zero beyond the margin. The points that are comfortably well classified do not contribute anything, so only the points on the margin or inside it (the support vectors) shape the boundary. The log loss never reaches zero: in logistic regression every point pulls a little.

Step 4: Training with gradient descent

---

The hinge loss has a corner at $y f(x) = 1$, but apart from that point its slope is simple. For each point inside the margin ($y_i f(x_i) < 1$) the derivative of its term is $-y_i x_i$ with respect to $w$ and $-y_i$ with respect to $b$; the points outside the margin contribute zero. So the gradient of the cost is:

$$\frac{\partial J}{\partial w} = w - \lambda \sum_{i:\, y_i f(x_i) < 1} y_i x_i \qquad\qquad \frac{\partial J}{\partial b} = -\lambda \sum_{i:\, y_i f(x_i) < 1} y_i$$

Three practical details, all of which appeared in the previous notebooks:

• We divide the cost by $\lambda m$. This does not move the minimum, but it keeps the size of the gradient similar for any $\lambda$ and any number of points, so the same learning rate works everywhere.
• Because of the corner, gradient descent bounces around the minimum. We reduce the learning rate as the iterations go by: $\alpha_t = \frac{\alpha}{1 + t/1000}$.
• We center the features (subtract their mean) inside the function, which makes convergence much faster. At the end, we convert the bias back to the original units.

def svm_cost(X, y, w, b, lam):
    """The book's soft-margin cost: 1/2 ||w||^2 + lambda * sum of the hinge losses."""
    return 0.5 * w @ w + lam * hinge_loss(y, X @ w + b).sum()

def train_svm(X, y, lam, learning_rate=1.0, num_iterations=50000, decay=1000):
    m, n = X.shape
    mu = X.mean(axis=0)
    Xc = X - mu                      # centred features
    w = np.zeros(n)
    b = 0.0
    for t in range(num_iterations):
        inside = y * (Xc @ w + b) < 1                       # points inside the margin (or on the wrong side)
        grad_w = w / (lam * m) - (y[inside, None] * Xc[inside]).sum(axis=0) / m
        grad_b = -y[inside].sum() / m
        alpha = learning_rate / (1 + t / decay)             # decreasing learning rate
        w = w - alpha * grad_w
        b = b - alpha * grad_b
    return w, b - w @ mu                                     # bias in the original units

w, b = train_svm(X_toy, y_toy, lam=10)

print(f"w = {w.round(3)},  b = {b:.3f}")
print(f"Boundary:       x2 = {-w[0] / w[1]:.3f} x1 + {-b / w[1]:.3f}")
print(f"Margin width:   2 / ||w|| = {2 / np.linalg.norm(w):.3f}")
print(f"Final cost:     {svm_cost(X_toy, y_toy, w, b, lam=10):.3f}")

w = [-0.801  1.602],  b = -2.203
Boundary:       x2 = 0.500 x1 + 1.375
Margin width:   2 / ||w|| = 1.117
Final cost:     1.604

The boundary we have found is the line of the book's figure, $x_2 = 0.5\,x_1 + 1.375$. Which points are the support vectors? The ones with $y_i f(x_i) \approx 1$, exactly on the edge of the margin:

f_toy = X_toy @ w + b
support = y_toy * f_toy < 1 + 1e-2
for x, label, f in zip(X_toy[support], y_toy[support], f_toy[support]):
    print(f"Support vector {x}, class {label:+d}: f(x) = {f:+.3f}")

def plot_svm(X, y, w, b, title, ax):
    xs = np.linspace(0, 7, 2)
    ax.scatter(*X[y == 1].T, color='tab:blue', s=60, label='class +1')
    ax.scatter(*X[y == -1].T, color='tab:red', marker='s', s=60, label='class -1')
    ax.plot(xs, -(w[0] * xs + b) / w[1], 'k-', label='boundary f(x) = 0')
    for level in (1, -1):
        ax.plot(xs, -(w[0] * xs + b - level) / w[1], 'k--', linewidth=1)
    sv = y * (X @ w + b) < 1 + 1e-2
    ax.scatter(*X[sv].T, s=250, facecolors='none', edgecolors='k', label='support vectors')
    ax.set_xlim(0, 7)
    ax.set_ylim(0, 7)
    ax.set_xlabel('$x_1$')
    ax.set_ylabel('$x_2$')
    ax.set_title(title)
    ax.grid(True)

fig, ax = plt.subplots(figsize=(6, 5))
plot_svm(X_toy, y_toy, w, b, f'Maximum margin: {2 / np.linalg.norm(w):.3f}', ax)
ax.legend(loc='upper right')
plt.show()

Support vector [3.5  3.75], class +1: f(x) = +1.000
Support vector [4.   2.75], class -1: f(x) = -1.002

Only two points hold the boundary in place. We could move or remove any of the other twelve (without entering the margin) and the solution would not change at all.

Step 5: Soft margin, the role of $\lambda$

---

The parameter $\lambda$ sets the price of each violation of the margin. The book puts it this way: if $\lambda$ is large, the model penalizes errors more and fits the data more closely; if $\lambda$ is small, it allows a wider margin and tolerates some errors in exchange for better generalization.

To see it, we add a single suspicious point: one of class $+1$ placed among the negative ones, which could be a labelling mistake or a rare case. We train with $\lambda = 100$ and $\lambda = 1$:

X_out = np.vstack([X_toy, [4.5, 3.0]])
y_out = np.append(y_toy, 1)

fig, axes = plt.subplots(1, 2, figsize=(12, 5))
for lam, ax in zip([100, 1], axes):
    w_l, b_l = train_svm(X_out, y_out, lam=lam)
    f = X_out @ w_l + b_l
    errors = np.sum(np.sign(f) != y_out)
    margin = 2 / np.linalg.norm(w_l)
    print(f"lambda = {lam:>3}: margin = {margin:.3f}, misclassified points = {errors}, "
          f"boundary x2 = {-w_l[0] / w_l[1]:.3f} x1 + {-b_l / w_l[1]:.3f}")
    plot_svm(X_out, y_out, w_l, b_l, f'lambda = {lam}: margin {margin:.2f}, errors: {errors}', ax)
    ax.scatter(4.5, 3.0, s=500, marker='*', color='gold', edgecolors='k', zorder=3, label='new point')
axes[1].legend(loc='center left', bbox_to_anchor=(1.02, 0.5))
plt.show()

lambda = 100: margin = 0.395, misclassified points = 0, boundary x2 = -0.333 x1 + 4.291

lambda =   1: margin = 1.655, misclassified points = 1, boundary x2 = 0.149 x1 + 2.393

With $\lambda = 100$ an error is so expensive that the model tilts the boundary to classify the new point correctly, and the margin shrinks to a narrow street: the model has bent over backwards for a single point. With $\lambda = 1$ it accepts one error and keeps a much wider margin, supported by more points. Which one is better? It depends on whether that point is a real pattern or noise, and the way to find out is the same as with regularization: cross-validation.

Note that $\lambda$ in the SVM works the other way round from the $\lambda$ of regularization in logistic regression: there, a larger $\lambda$ meant a simpler model; here, a larger $\lambda$ means a model that fits the training data more closely.

Step 6: Back to the Physiotherapy no-shows

---

We now apply our SVM to the problem of the chapter, with the same synthetic appointments as in the logistic regression notebooks:

Column	Meaning
age	Age of the patient (18–85 years)
days_since_last_visit	Days since the patient's previous appointment
distance_km	Distance from home to the hospital, in km (Minermont serves a rural area)
hour	Time of the appointment (8 to 19 h)
first_visit	1 if it is a first visit, 0 if it is a follow-up
previous_no_shows	Number of appointments the patient has missed before
no_show	Target: 1 if the patient did not attend, 0 if they did

def generate_appointments(n, seed):
    """Synthetic Physiotherapy appointments at Minermont: one row per appointment."""
    rng = np.random.default_rng(seed)
    age = rng.integers(18, 86, n)                                  # years
    days = rng.integers(1, 181, n)                                 # days since the previous appointment
    distance = np.round(rng.gamma(2.0, 6.0, n).clip(0.5, 60), 1)   # km to the hospital (a rural area)
    hour = rng.integers(8, 20, n)                                  # appointment time, from 8:00 to 19:00
    first = rng.binomial(1, 0.35, n)                               # 1 = first visit, 0 = follow-up
    previous = rng.poisson(0.6, n).clip(0, 6)                      # no-shows in the patient's history
    late = np.where(hour >= 17, hour - 16, 0)                      # late-afternoon slots are missed more

    # The hidden rule behind the data. We only use it to generate the appointments:
    # the model never sees it and has to discover the pattern from the examples.
    z = (-1.55 - 0.069 * (age - 50) + 0.026 * (days - 90) + 0.11 * (distance - 12)
         + 1.5 * (previous - 0.6) + 0.56 * (late - 0.75) + 0.63 * (first - 0.35))
    no_show = rng.binomial(1, 1 / (1 + np.exp(-z)))                # 1 = did not attend

    return pd.DataFrame({
        'age': age, 'days_since_last_visit': days, 'distance_km': distance, 'hour': hour,
        'first_visit': first, 'previous_no_shows': previous, 'no_show': no_show,
    })

df = generate_appointments(1200, seed=42)
feature_names = ['age', 'days_since_last_visit', 'distance_km', 'hour', 'first_visit', 'previous_no_shows']
X = df[feature_names].to_numpy(dtype=float)
y = np.where(df['no_show'] == 1, 1, -1)          # +1 = no-show, -1 = attends

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.25, random_state=42, stratify=y)

print(f"Training set: {len(y_train)} appointments ({np.mean(y_train == 1):.1%} no-shows)")
print(f"Test set:     {len(y_test)} appointments ({np.mean(y_test == 1):.1%} no-shows)")

Training set: 900 appointments (26.2% no-shows)
Test set:     300 appointments (26.3% no-shows)

The SVM measures distances, so, as with logistic regression, the features must be scaled, using the mean and standard deviation of the training data only.

Step 7: Choosing $\lambda$ with k-fold cross-validation

---

Here we implement by hand the procedure described in Noah's notes (section 3.5):

1. Split the training set into $k = 5$ stratified groups: each keeps the proportion of no-shows.
2. For each value of $\lambda$ in a logarithmic grid, train 5 times, each time with 4 groups, and validate with the remaining one.
3. Keep the $\lambda$ with the best mean validation accuracy.

To be rigorous, the scaling is also recomputed inside each round with the 4 training groups only, so the validation group does not influence anything. The test set is not used at all in this step.

def scale(X_fit, *others):
    """Standardize with the mean and standard deviation of X_fit."""
    mean, std = X_fit.mean(axis=0), X_fit.std(axis=0)
    return [(A - mean) / std for A in (X_fit, *others)]

def predict(X, w, b):
    return np.where(X @ w + b >= 0, 1, -1)

def stratified_folds(y, k, seed=0):
    """Indices of k groups, each with the same proportion of every class."""
    rng = np.random.default_rng(seed)
    folds = [[] for _ in range(k)]
    for label in np.unique(y):
        idx = rng.permutation(np.where(y == label)[0])
        for j, part in enumerate(np.array_split(idx, k)):
            folds[j].extend(part)
    return [np.array(f) for f in folds]

def cross_val_accuracy(X, y, lam, k=5):
    scores = []
    for val_idx in stratified_folds(y, k):
        train_idx = np.setdiff1d(np.arange(len(y)), val_idx)
        X_tr, X_val = scale(X[train_idx], X[val_idx])
        w, b = train_svm(X_tr, y[train_idx], lam, num_iterations=3000, decay=100)
        scores.append(np.mean(predict(X_val, w, b) == y[val_idx]))
    return np.mean(scores)

lambdas = [0.001, 0.01, 0.1, 1, 10, 100]
cv_scores = [cross_val_accuracy(X_train, y_train, lam) for lam in lambdas]
for lam, score in zip(lambdas, cv_scores):
    print(f"lambda = {lam:<6}  mean validation accuracy = {score:.3f}")

best_lambda = lambdas[int(np.argmax(cv_scores))]
print(f"\nBest lambda: {best_lambda}")

lambda = 0.001   mean validation accuracy = 0.738
lambda = 0.01    mean validation accuracy = 0.818
lambda = 0.1     mean validation accuracy = 0.846
lambda = 1       mean validation accuracy = 0.837
lambda = 10      mean validation accuracy = 0.837
lambda = 100     mean validation accuracy = 0.834

Best lambda: 0.1

With a very small $\lambda$ errors are almost free, so the weights stay close to zero and the model predicts that nearly everybody attends: its accuracy is that of always answering "attends". From $\lambda = 0.1$ upwards the accuracy barely changes: with 900 appointments and only six variables there is little room to overfit, so the exact value matters much less than in the small example.

Step 8: Evaluation on the test set

---

We train with the chosen $\lambda$ on the whole training set and evaluate once on the test set, with the same metrics as in the logistic regression notebook. A point is predicted as a no-show when $f(x) \geq 0$.

X_train_s, X_test_s = scale(X_train, X_test)
w, b = train_svm(X_train_s, y_train, best_lambda, num_iterations=3000, decay=100)

def evaluate(y_true, scores, threshold=0.0):
    """Confusion matrix and clinical metrics; positive class = no-show (+1)."""
    y_pred = np.where(scores >= threshold, 1, -1)
    tp = np.sum((y_pred == 1) & (y_true == 1))
    fn = np.sum((y_pred == -1) & (y_true == 1))
    fp = np.sum((y_pred == 1) & (y_true == -1))
    tn = np.sum((y_pred == -1) & (y_true == -1))
    return {
        'threshold': threshold, 'TP': tp, 'FN': fn, 'FP': fp, 'TN': tn,
        'accuracy': (tp + tn) / len(y_true),
        'sensitivity': tp / (tp + fn),
        'specificity': tn / (tn + fp),
        'PPV': tp / (tp + fp),
        'NPV': tn / (tn + fn),
    }

scores_test = X_test_s @ w + b
r = evaluate(y_test, scores_test)

print("Confusion matrix (test set):")
print(f"                  Predicted no-show   Predicted attends")
print(f"  Did not attend  TP = {r['TP']:<14} FN = {r['FN']}")
print(f"  Attended        FP = {r['FP']:<14} TN = {r['TN']}")
print()
for k in ['accuracy', 'sensitivity', 'specificity', 'PPV', 'NPV']:
    print(f"{k:>12}: {r[k]:.3f}")
print(f"\nBaseline (always predict 'attends'): accuracy = {np.mean(y_test == -1):.3f}")

Confusion matrix (test set):
                  Predicted no-show   Predicted attends
  Did not attend  TP = 46             FN = 33
  Attended        FP = 17             TN = 204

    accuracy: 0.833
 sensitivity: 0.582
 specificity: 0.923
         PPV: 0.730
         NPV: 0.861

Baseline (always predict 'attends'): accuracy = 0.737

The SVM reaches an accuracy of 0.833, very close to the 0.827 of the logistic regression from scratch (same data, same split). With its default threshold it is a little more cautious: it raises fewer false alarms (higher specificity and PPV) but detects fewer no-shows (lower sensitivity).

What has the SVM learned? The features are scaled, so we can compare the weights with each other. The sign says in which direction each variable pushes: positive towards a no-show, negative towards attendance.

weights = pd.Series(w, index=feature_names).sort_values(key=np.abs, ascending=False)
print(weights.round(3).to_string())

inside = y_train * (X_train_s @ w + b) < 1 + 1e-6
print(f"\nSupport vectors (points on or inside the margin): {inside.sum()} of {len(y_train)}")

age                     -0.769
previous_no_shows        0.713
days_since_last_visit    0.709
distance_km              0.571
first_visit              0.222
hour                     0.208

Support vectors (points on or inside the margin): 366 of 900

The four variables that weigh most are the same as in logistic regression: age (negative: older patients miss fewer appointments), previous no-shows, days since the last visit and distance. The hour and the first visit weigh less. The weights are smaller than those of logistic regression because the two models work on different scales, so only their relative sizes can be compared.

Look also at the number of support vectors. In the book's clean example there were two; here, where the classes overlap, 366 of the 900 appointments are on the margin or inside it, and all of them take part in placing the boundary.

Moving the threshold. An SVM does not return a probability, only a score $f(x)$: its sign gives the class and its size, how far the appointment is from the boundary. But, as with the probability of logistic regression, we can move the threshold to detect more no-shows:

rows = [evaluate(y_test, scores_test, t) for t in [0.0, -0.25, -0.5]]
table = pd.DataFrame(rows)[['threshold', 'TP', 'FN', 'FP', 'accuracy', 'sensitivity', 'specificity']]
print(table.round(3).to_string(index=False))

 threshold  TP  FN  FP  accuracy  sensitivity  specificity
      0.00  46  33  17     0.833        0.582        0.923
     -0.25  53  26  26     0.827        0.671        0.882
     -0.50  60  19  40     0.803        0.759        0.819

Lowering the threshold to −0.5 detects 60 of the 79 no-shows (sensitivity 0.759), at the cost of 40 false alarms. The trade-off is the same as with logistic regression, and it is the hospital that decides where to put it. If a probability is needed, for instance to warn reception that a patient is very likely not to come, the SVM scores have to be calibrated; scikit-learn can do it, as we will see in the next notebook.

Conclusion

---

• A linear SVM looks for the boundary with the widest margin. Minimizing $\frac{1}{2}\|w\|^2$ widens the margin, and the hinge loss charges for the points that enter it.
• Only the support vectors decide the boundary: the points that are clearly well classified contribute nothing to the cost.
• $\lambda$ sets the price of each error: a large $\lambda$ fits the training data closely (narrow margin), a small $\lambda$ tolerates errors (wide margin). We chose it with k-fold cross-validation, without touching the test set.
• On the no-show data the linear SVM and the logistic regression reach a very similar result. Its advantage appears when the boundary is not a straight line: the kernel trick, which we will use with scikit-learn in the next notebook.