Last modified: 2026-10-26
# The Python chunks on this page import numpy; reticulate provisions it.
# The Julia chunks run through JuliaCall.
library(reticulate)
py_require(c("numpy", "pandas"))
fmt2 <- function(v) formatC(v, format = "f", digits = 2)
fmt1 <- function(v) formatC(v, format = "f", digits = 1)
fmt3s <- function(v) formatC(signif(v, 3), format = "fg", digits = 3)Source
Adapted from Brian Hutchinson’s Fall 2025 lecture notes, and drawing on Logan Sizemore’s Spring 2025 lecture on support vector machines. Where this chapter goes past that lecture — the 1995 soft margin, and crediting Alexey Chervonenkis alongside Vapnik for the 1964 paper, which the lecture attributes to Vapnik alone — it follows the cited papers rather than the lecture. The lecture’s gradient-descent derivation of the representer theorem for a general loss appears in the dual-problem section, as Theorem 5.
Support vector machines come from the maximal-margin classifier Vladimir Vapnik and Alexey Chervonenkis published jointly in 1964 [1]. The kernel trick that extends them to non-linear classification arrived in 1992 [2], and the soft margin that lets them tolerate non-separable data shortly after [3].
SVMs were the dominant classifier of the late 1990s and early 2000s. Two things drove that: they are unusually easy to analyze in theory, and they performed well on the data sets of that time. Neural networks have since replaced them in most applications, but SVMs are still the right tool for some, and two of the ideas they introduce — the max-margin objective and the kernel trick — stayed in use after the method that introduced them faded.
We build the method up by starting with the most restrictive version and removing one assumption at a time. The starting point is a supervised, linear, binary classifier for separable classes, and we will drop three of those four assumptions in this order:
Separable, which soft-margin SVMs drop.
Linear, which the kernel trick drops.
Binary, which multiclass SVMs drop.
Supervised is the one assumption that stays.
Exercise 1 (Reuse a fitted linear classifier)
Exercise 1 (Reuse a fitted linear classifier) Everything in this lecture is built on a linear classifier these notes have already fit. A logistic regression on two inputs \(x = (x_1, x_2)\) returned \(w = (2, -1)\) and \(b = 1\).
Write the equation of its separating line in terms of \(x_1\) and \(x_2\), and give two points on it.
Solution 1. The separating line of that fitted classifier is the set where \(\modmemf{x}\) vanishes,
\[\{x : \modmemf{x} = \dprod{w}{x} + b = 2x_1 - x_2 + 1 = 0\}.\]
Setting \(x_1 = 0\) gives \(x_2 = 1\), so \((0, 1)\) is on the line. Setting \(x_1 = 1\) gives \(x_2 = 3\), so \((1, 3)\) is on it too.
Exercise 2 (Reuse a fitted linear classifier (part 2))
Exercise 2 (Reuse a fitted linear classifier (part 2)) Use the setup of Exercise 1.
Predict the class of each point \((1, 1)\), \((-1, 2)\) and \((0, -1)\), taking the positive class when \(\modmemf{x} > 0\).
Solution 2. Evaluate \(\modmemf{x} = 2x_1 - x_2 + 1\) at each point:
Exercise 3 (Reuse a fitted linear classifier (part 3))
Exercise 3 (Reuse a fitted linear classifier (part 3)) Use the setup of Exercise 1.
A support vector machine will use a function of the same form. Which of these does it keep from logistic regression, and which does it replace: the parameters, the separating hyperplane, the prediction rule, the objective that picks \(w\) and \(b\)?
Solution 3. The SVM keeps the parameters \(w\) and \(b\), the separating hyperplane \(\{x : \dprod{w}{x} + b = 0\}\), and the prediction rule based on the sign of \(\modmemf{x}\). It replaces the objective. Logistic regression picks \(w\) and \(b\) by minimizing the average cross-entropy over the training set. The SVM picks them by making the margin as large as possible, which is a different style of optimization problem.
Everything about the model carries over; only the objective changes.
Definition 1 (Decision boundary)
Definition 1 (Decision boundary) A classifier’s decision boundary is the set of inputs where its prediction changes from one class to another [4]. For a linear classifier it is the hyperplane \(\{x : \modmemf{x} = 0\}\).
Definition 2 (Decision region)
Definition 2 (Decision region) The decision boundaries divide the input space into decision regions, each the set of inputs the classifier assigns to one class. For a linear binary classifier there are two: \(\{x : \modmemf{x} > 0\}\) and \(\{x : \modmemf{x} < 0\}\).
Example 1 (A linear classifier for fuel economy)
Example 1 (A linear classifier for fuel economy) In the Auto data [5], label a car \(+1\) if its mpg is above the median and \(-1\) otherwise. Classify it from its standardized weight and horsepower with the linear rule \(\modmemf{x} = \dprod{w}{x} + b\), where \(w\) is the difference of the two class means and the hyperplane \(\modmemf{x} = 0\) is the perpendicular bisector of the segment joining them. Count how many cars fall on each side of that hyperplane, by actual label:
import numpy as np
import pandas as pd
auto_dr = pd.read_csv("data/auto.csv").dropna().reset_index(drop=True)
# Standardize, so that weight and horsepower are on comparable scales.
Z_dr = auto_dr[["weight", "horsepower"]].to_numpy(float)
Z_dr = (Z_dr - Z_dr.mean(axis=0)) / Z_dr.std(axis=0, ddof=1)
y_dr = np.where(auto_dr["mpg"] > auto_dr["mpg"].median(), 1.0, -1.0)
# The boundary passes through the midpoint of the class means and is perpendicular to their difference.
mean_hi_dr, mean_lo_dr = Z_dr[y_dr > 0].mean(axis=0), Z_dr[y_dr < 0].mean(axis=0)
w_dr = mean_hi_dr - mean_lo_dr
b_dr = -w_dr @ (mean_hi_dr + mean_lo_dr) / 2
h_dr = Z_dr @ w_dr + b_dr # the sign of h says which decision region a car is in
print(pd.crosstab(np.where(h_dr > 0, "h > 0", "h < 0"), np.where(y_dr > 0, "high mpg", "low mpg"),
rownames=["region"], colnames=["actual"]))actual high mpg low mpg
region
h < 0 8 151
h > 0 188 45auto_dr <- tidyr::drop_na(read.csv("data/auto.csv"))
# Standardize, so that weight and horsepower are on comparable scales.
Z_dr <- scale(as.matrix(auto_dr[, c("weight", "horsepower")]))
y_dr <- ifelse(auto_dr$mpg > median(auto_dr$mpg), 1, -1)
# The boundary passes through the midpoint of the class means and is perpendicular to their difference.
mean_hi_dr <- colMeans(Z_dr[y_dr > 0, ])
mean_lo_dr <- colMeans(Z_dr[y_dr < 0, ])
w_dr <- mean_hi_dr - mean_lo_dr
b_dr <- -sum(w_dr * (mean_hi_dr + mean_lo_dr)) / 2
h_dr <- drop(Z_dr %*% w_dr) + b_dr # the sign of h says which decision region a car is in
table(region = ifelse(h_dr > 0, "h > 0", "h < 0"),
actual = ifelse(y_dr > 0, "high mpg", "low mpg")) actual
region high mpg low mpg
h < 0 8 151
h > 0 188 45The line \(\modmemf{x} = 0\) is the decision boundary of Definition 1, and it cuts the plane into the two decision regions of Definition 2. The region \(\modmem > 0\) holds 233 cars, 81% of them high-mpg; the region \(\modmem < 0\) holds 159 cars, 95% of them low-mpg. The 53 cars on the wrong side of the line are the classifier’s errors.
Exercise 4 (Say which training sets a hyperplane can split)
Exercise 4 (Say which training sets a hyperplane can split) Logistic regression returns a hyperplane for any training set, but on some training sets every hyperplane misclassifies a point.
Sketch a two-class training set in \(\reals^2\) that some line classifies with no mistakes.
Solution 4. Any two clouds of points that sit on opposite sides of some line, such as one class clustered at the upper right and the other at the lower left (Figure 1).
Exercise 5 (Say which training sets a hyperplane can split (part 2))
Exercise 5 (Say which training sets a hyperplane can split (part 2)) Use the setup of Exercise 4.
Sketch one that no line can.
Solution 5. The four points of the XOR problem from logistic regression: one class at \((1, 1)\) and \((-1, -1)\), the other at \((1, -1)\) and \((-1, 1)\). Any line that puts both points of one class on the same side also puts at least one point of the other class there (Figure 2).
Exercise 6 (Say which training sets a hyperplane can split (part 3))
Exercise 6 (Say which training sets a hyperplane can split (part 3)) Use the setup of Exercise 4.
In one sentence, say what distinguishes the first from the second.
Solution 6. In the first set, some linear boundary puts each class entirely on its own side; in the second, no linear boundary does.
Definition 3 (Linearly separable)
Definition 3 (Linearly separable) A two-class dataset is linearly separable if there exists a linear decision boundary that separates the classes with no misclassifications [6].
Example 2 (Ten cars that a line separates)
Example 2 (Ten cars that a line separates) Take the extremes of the Auto data [5]: the first five cars in the file with mpg at most 14 (label \(-1\)) and the first five with mpg at least 30 (label \(+1\)). Picking the extremes makes this set separable, and it is a toy example in that sense. Use weight in thousands of pounds and horsepower in hundreds as the two inputs, and check whether the perpendicular bisector of the two class means classifies all ten cars correctly:
auto_ls = pd.read_csv("data/auto.csv").dropna().reset_index(drop=True)
cars_ls = pd.concat([auto_ls[auto_ls["mpg"] <= 14].head(5), auto_ls[auto_ls["mpg"] >= 30].head(5)])
# Rescaling the units keeps both inputs near 1.
X_sep = np.column_stack([cars_ls["weight"] / 1000, cars_ls["horsepower"] / 100])
y_sep = np.where(cars_ls["mpg"] >= 30, 1.0, -1.0)
print(cars_ls[["name", "mpg", "weight", "horsepower"]].to_string(index=False)) name mpg weight horsepower
chevrolet impala 14.0 4354 220
plymouth fury iii 14.0 4312 215
pontiac catalina 14.0 4425 225
plymouth 'cuda 340 14.0 3609 160
buick estate wagon (sw) 14.0 3086 225
peugeot 304 30.0 2074 70
fiat 124b 30.0 2065 76
toyota corolla 1200 31.0 1773 65
datsun 1200 35.0 1613 69
datsun b210 31.0 1950 67[4.07 3.92 4.29 1.7 1.53 2.72 2.66 3.41 3.69 3.02]auto_ls <- tidyr::drop_na(read.csv("data/auto.csv"))
cars_ls <- rbind(head(auto_ls[auto_ls$mpg <= 14, ], 5), head(auto_ls[auto_ls$mpg >= 30, ], 5))
# Rescaling the units keeps both inputs near 1.
X_sep <- cbind(cars_ls$weight / 1000, cars_ls$horsepower / 100)
y_sep <- ifelse(cars_ls$mpg >= 30, 1, -1)
cars_ls[, c("name", "mpg", "weight", "horsepower")]# y * h(x) > 0 means the car is on the side of the hyperplane that matches its label.
mean_hi_ls <- colMeans(X_sep[y_sep > 0, ])
mean_lo_ls <- colMeans(X_sep[y_sep < 0, ])
w_ls <- mean_hi_ls - mean_lo_ls
b_ls <- -sum(w_ls * (mean_hi_ls + mean_lo_ls)) / 2
round(y_sep * (drop(X_sep %*% w_ls) + b_ls), 2) [1] 4.07 3.92 4.29 1.70 1.53 2.72 2.66 3.41 3.69 3.02All ten products \(y_{(i)} \modmemf{x_{(i)}}\) are positive, the smallest being 1.53, so this hyperplane classifies every car correctly and the set is linearly separable in the sense of Definition 3. Existence is all the definition asks for. Many other hyperplanes separate these ten cars too, which is why the next examples ask which one is best.
“SVM” names three models
“Support vector machine” is used loosely, for three models rather than one [5, Ch. 9]:
A maximal margin classifier applies only to linearly separable data. This chapter calls it the hard-margin SVM.
A support vector classifier also handles data that is not separable; its decision boundary is still linear. This chapter calls it the soft-margin SVM.
A support vector machine, in the strict sense, has a non-linear decision boundary. The kernel trick turns either of the other two into one.
In practice all three get called support vector machines, so the name on its own does not tell you which of them is meant. This chapter uses “SVM” for all three, and says which one when it matters.
One thing does change before we start, and it is only a change of notation. From here on the binary labels are
\[y_{(i)} \in \{-1, +1\},\]
rather than the \(\{0, 1\}\) that logistic regression used.
Every constraint in this lecture is written in terms of the single product
\[y_{(i)} \, \modmemf{x_{(i)}},\]
which is positive on a correct prediction and negative on a wrong one. The notation choices page gives the reason for the switch and explains how to read a source that uses the other coding.
Exercise 7 (Say what makes one separating hyperplane better than another)
Exercise 7 (Say what makes one separating hyperplane better than another) Sketch two linearly separable clouds of points in \(\reals^2\), one class each, and draw three different hyperplanes that separate them. One of the three should be the one logistic regression would have returned.
Solution 7. Any three lines that leave one class entirely on each side will do.
Exercise 8 (Say what makes one separating hyperplane better than another (part 2))
Exercise 8 (Say what makes one separating hyperplane better than another (part 2)) Use the setup of Exercise 7.
How many separating hyperplanes does a linearly separable training set admit?
Solution 8. Infinitely many. Separability says at least one exists, and any sufficiently small tilt or shift of a separating hyperplane still separates.
Exercise 9 (Say what makes one separating hyperplane better than another (part 3))
Exercise 9 (Say what makes one separating hyperplane better than another (part 3)) Use the setup of Exercise 7.
Every one of them classifies the training set perfectly, so training accuracy cannot choose between them. Name a property that can, and say why you would want it.
Solution 9. How much room it leaves. A hyperplane that passes very close to a training point classifies that point correctly and would misclassify a new point drawn a tiny distance to its other side. One that sits well clear of both classes tolerates that small variation. Training accuracy cannot tell them apart because it only asks which side of the boundary each point is on, never how far.
Exercise 10 (Say what makes one separating hyperplane better than another (part 4))
Exercise 10 (Say what makes one separating hyperplane better than another (part 4)) Use the setup of Exercise 7.
Using that property, state in one sentence which hyperplane you want.
Solution 10. Take the hyperplane that is as far as possible from the nearest point of each class.
Exercise 11 (Say what makes one separating hyperplane better than another (part 5))
Exercise 11 (Say what makes one separating hyperplane better than another (part 5)) Use the setup of Exercise 7.
Move one of the points far away from the boundary. Does your answer to Exercise 9 change?
Solution 11. It does not change. Solution 9 maximizes the distance to the nearest point, and a point that was not nearest to begin with does not become nearest by moving further away.
Exercise 12 (Say what makes one separating hyperplane better than another (part 6))
Exercise 12 (Say what makes one separating hyperplane better than another (part 6)) Use the setup of Exercise 7.
Which points, then, actually determine where the hyperplane lies?
Solution 12. Only the closest points fix where the hyperplane lies, and the rest of the training set could be deleted without moving the hyperplane at all.
That is a strong claim, and it is the property the method is named for. Definition 4, Definition 5 and Definition 6 make it precise.
Definition 4 (Margin)
Definition 4 (Margin) The margin of a separating hyperplane is the distance from it to the nearest training point.
Definition 5 (Support vector)
Definition 5 (Support vector) A support vector is a training point lying at distance exactly \(M\) from the hyperplane, where \(M\) is the margin of Definition 4.
Definition 6 (Max-margin hyperplane)
Definition 6 (Max-margin hyperplane) The max-margin hyperplane is the separating hyperplane whose margin is largest [7].
Example 3 (The margin, support vectors and max-margin hyperplane of ten cars)
Example 3 (The margin, support vectors and max-margin hyperplane of ten cars) For the ten cars of Example 2, find the max-margin hyperplane, its margin, and the support vectors. The helper dual_svm below solves the dual problem of the next section by repeatedly improving the two multipliers that violate its optimality conditions the most; treat it as a black box for now, since only its answer matters here. It returns the multipliers alpha and the offset b, and the weight vector is \(w = \sumiN \dualvar_i y_{(i)} x_{(i)}\).
def dual_svm(K, y, C=np.inf, tol=1e-6, max_iter=100_000):
"""Maximize the dual over alpha, given the kernel matrix K and labels y in {-1, +1}."""
alpha, grad = np.zeros(len(y)), -np.ones(len(y)) # grad = Q alpha - 1, with Q = y y' * K
Q = np.outer(y, y) * K
for _ in range(max_iter):
score = -y * grad
up = ((y > 0) & (alpha < C)) | ((y < 0) & (alpha > 0))
low = ((y > 0) & (alpha > 0)) | ((y < 0) & (alpha < C))
i, j = np.flatnonzero(up)[np.argmax(score[up])], np.flatnonzero(low)[np.argmin(score[low])]
if score[i] - score[j] < tol:
break
# Move alpha_i and alpha_j together, so that sum(alpha * y) stays 0 and the box 0 <= alpha <= C holds.
step = (score[i] - score[j]) / (K[i, i] + K[j, j] - 2 * K[i, j])
step = min(step, C - alpha[i] if y[i] > 0 else alpha[i], alpha[j] if y[j] > 0 else C - alpha[j])
alpha[i] += y[i] * step
alpha[j] -= y[j] * step
grad += (Q[:, i] * y[i] - Q[:, j] * y[j]) * step
free = (alpha > 1e-7) & (alpha < C - 1e-7)
return alpha, np.mean((y - (alpha * y) @ K)[free]) # b from the points strictly inside the boxK_mm = X_sep @ X_sep.T # inner products of the ten cars
alpha_mm, b_mm = dual_svm(K_mm, y_sep)
w_mm = (alpha_mm * y_sep) @ X_sep
# The distance from a car to the hyperplane is |w.x + b| / ||w||.
dist_mm = np.abs(X_sep @ w_mm + b_mm) / np.linalg.norm(w_mm)
margin_mm = dist_mm.min() # the margin is the smallest of these
is_sv_mm = dist_mm < margin_mm + 1e-4 # support vectors sit at exactly that distance
print(pd.DataFrame({"name": cars_ls["name"].to_numpy(), "distance": dist_mm.round(3), "support_vector": is_sv_mm})) name distance support_vector
0 chevrolet impala 1.821 False
1 plymouth fury iii 1.757 False
2 pontiac catalina 1.908 False
3 plymouth 'cuda 340 0.865 True
4 buick estate wagon (sw) 0.865 True
5 peugeot 304 0.895 False
6 fiat 124b 0.865 True
7 toyota corolla 1200 1.161 False
8 datsun 1200 1.261 False
9 datsun b210 1.011 False0.8648 0.6134dual_svm <- function(K, y, C = Inf, tol = 1e-6, max_iter = 1e5) {
# Maximize the dual over alpha, given the kernel matrix K and labels y in {-1, +1}.
alpha <- numeric(length(y))
grad <- rep(-1, length(y)) # grad = Q alpha - 1, with Q = y y' * K
Q <- outer(y, y) * K
for (iter in seq_len(max_iter)) {
score <- -y * grad
up <- which((y > 0 & alpha < C) | (y < 0 & alpha > 0))
low <- which((y > 0 & alpha > 0) | (y < 0 & alpha < C))
i <- up[which.max(score[up])]
j <- low[which.min(score[low])]
if (score[i] - score[j] < tol) break
# Move alpha_i and alpha_j together, so that sum(alpha * y) stays 0 and the box 0 <= alpha <= C holds.
step <- (score[i] - score[j]) / (K[i, i] + K[j, j] - 2 * K[i, j])
step <- min(step, if (y[i] > 0) C - alpha[i] else alpha[i], if (y[j] > 0) alpha[j] else C - alpha[j])
alpha[i] <- alpha[i] + y[i] * step
alpha[j] <- alpha[j] - y[j] * step
grad <- grad + (Q[, i] * y[i] - Q[, j] * y[j]) * step
}
free <- alpha > 1e-7 & alpha < C - 1e-7
list(alpha = alpha, b = mean((y - drop((alpha * y) %*% K))[free])) # b from the points strictly inside the box
}K_mm <- X_sep %*% t(X_sep) # inner products of the ten cars
fit_mm <- dual_svm(K_mm, y_sep)
alpha_mm <- fit_mm$alpha
b_mm <- fit_mm$b
w_mm <- drop((alpha_mm * y_sep) %*% X_sep)
# The distance from a car to the hyperplane is |w.x + b| / ||w||.
dist_mm <- abs(drop(X_sep %*% w_mm) + b_mm) / sqrt(sum(w_mm^2))
margin_mm <- min(dist_mm) # the margin is the smallest of these
is_sv_mm <- dist_mm < margin_mm + 1e-4 # support vectors sit at exactly that distance
data.frame(name = cars_ls$name, distance = round(dist_mm, 3), support_vector = is_sv_mm)max_margin bisector
0.8647659 0.6133909 The margin of Definition 4 of the max-margin hyperplane is 0.865, in the units of the scaled inputs. The 3 support vectors of Definition 5, which are the plymouth ’cuda 340, buick estate wagon (sw), fiat 124b, lie at exactly that distance, and every other car is farther away. By Definition 6 no separating hyperplane has a larger margin; the bisector of the class means has 0.613.
# HTML formats get an interactive plotly figure (hover for the values, click the
# legend to hide a line); the handout and other formats get the same figure
# drawn with ggplot2.
# The ten cars as points, with the support vectors of the max-margin fit flagged.
cars_df <- tibble::tibble(
weight = X_sep[, 1],
horsepower = X_sep[, 2],
mpg_group = ifelse(y_sep > 0, "mpg at least 30", "mpg at most 14"),
support = is_sv_mm
)
# The set w.x + b = c is a line, so write it as horsepower = intercept + slope * weight.
# The margin lines sit at c = -m and c = m, where m = margin * ||w||.
line_at <- function(w, b, c, kind) {
tibble::tibble(intercept = (c - b) / w[2], slope = -w[1] / w[2], kind = kind)
}
m_mm <- margin_mm * sqrt(sum(w_mm^2))
lines_df <- rbind(
line_at(w_mm, b_mm, 0, "max-margin hyperplane"),
line_at(w_mm, b_mm, -m_mm, "margin"),
line_at(w_mm, b_mm, m_mm, "margin"),
line_at(w_ls, b_ls, 0, "bisector of the class means")
)
x_range <- range(cars_df$weight) + c(-0.2, 0.2)
y_range <- range(cars_df$horsepower) + c(-0.2, 0.2)
if (knitr::is_html_output()) {
library(plotly)
# Draw line i of lines_df across the plotted weight range.
add_line <- function(widget, i, name, dash, color, legend = TRUE) {
widget |>
add_trace(
x = x_range, y = lines_df$intercept[i] + lines_df$slope[i] * x_range,
type = "scatter", mode = "lines", name = name, showlegend = legend,
line = list(color = color, dash = dash), hoverinfo = "skip"
)
}
widget <- plot_ly() |>
add_line(1, "max-margin hyperplane", "solid", "#222222") |>
add_line(2, "margin", "dash", "#222222") |>
add_line(3, "margin", "dash", "#222222", legend = FALSE) |>
add_line(4, "bisector of the class means", "dot", "#7570b3")
# One trace per class, with a different symbol as well as a different color.
for (group in unique(cars_df$mpg_group)) {
high_mpg <- group == "mpg at least 30"
widget <- widget |>
add_trace(
data = cars_df[cars_df$mpg_group == group, ],
x = ~weight, y = ~horsepower, type = "scatter", mode = "markers",
name = group,
marker = list(
size = 9, color = if (high_mpg) "#1f77b4" else "#d95f02",
symbol = if (high_mpg) "circle" else "triangle-up"
)
)
}
# An open circle around each support vector.
widget <- widget |>
add_trace(
data = cars_df[cars_df$support, ], x = ~weight, y = ~horsepower,
type = "scatter", mode = "markers", name = "support vector",
marker = list(
size = 18, symbol = "circle-open", color = "#222222",
line = list(width = 2)
)
) |>
layout(
xaxis = list(title = "weight (thousands of pounds)", range = x_range),
yaxis = list(title = "horsepower (hundreds)", range = y_range),
legend = list(orientation = "h", y = -0.25),
margin = list(t = 10)
) |>
config(displaylogo = FALSE, responsive = TRUE)
# The alt text: a plotly widget has none of its own.
htmltools::div(
role = "img",
`aria-label` = paste(
"Interactive scatter plot of horsepower against weight for ten cars in",
"two groups, with the max-margin hyperplane, its two margin lines, the",
"circled support vectors, and the differently tilted bisector of the",
"class means."
),
widget
)
} else {
library(ggplot2)
ggplot(cars_df, aes(weight, horsepower)) +
geom_abline(aes(intercept = intercept, slope = slope, linetype = kind),
data = lines_df, show.legend = FALSE) +
geom_point(aes(shape = mpg_group), size = 2) +
# A larger open circle around each support vector.
geom_point(data = cars_df[cars_df$support, ], shape = 1, size = 5) +
scale_shape_manual(
values = c("mpg at least 30" = 16, "mpg at most 14" = 17)
) +
scale_linetype_manual(values = c(
"max-margin hyperplane" = "solid",
"margin" = "dashed",
"bisector of the class means" = "dotted"
)) +
coord_cartesian(xlim = x_range, ylim = y_range) +
labs(x = "weight (thousands of pounds)", y = "horsepower (hundreds)",
shape = NULL) +
theme(legend.position = "bottom")
}Read
GeeksforGeeks explains support vector machines [8].
Knowing what we want is not the same as being able to compute it, so the rest of this lecture turns Definition 6 into an optimization problem.
Two warnings about the form of that problem. It will not be “minimize average loss over the training set”, which is the only form these notes have used so far; it will be a maximization subject to one constraint per training point. And actually solving such a problem is beyond the scope of this class. We will state it, understand what it asks for, and give it to a solver.
Exercise 13 (Write the margin in terms of the parameters, in one dimension)
Exercise 13 (Write the margin in terms of the parameters, in one dimension) Draw a real line with a few positive points to the right and a few negative points to the left. We want a linear function \(\modmemf{x} = wx + b\), with \(w, b \in \reals\), that separates them. There is an easier way to do this in one dimension; we are doing it the way that generalizes to \(\ninputvars\).
Let \(x\) be the training point nearest the hyperplane, let \(y\) be its label, and let \(M\) be the margin of Definition 4.
What shape is a separating hyperplane in one dimension?
Solution 13. A point. A hyperplane is one dimension short of the space it sits in, so in \(\reals^1\) it is a single location on the line.
Exercise 14 (Write the margin in terms of the parameters, in one dimension (part 2))
Exercise 14 (Write the margin in terms of the parameters, in one dimension (part 2)) Use the setup of Exercise 13.
Where on the line does \(\modmem\) vanish?
Solution 14. At \(x_0 = -b/w\), the root of \(wx + b\).
Exercise 15 (Write the margin in terms of the parameters, in one dimension (part 3))
Exercise 15 (Write the margin in terms of the parameters, in one dimension (part 3)) Use the setup of Exercise 13.
Take \(\outvar = 1\) and \(w > 0\). Reading \(w\) as rise over run between that point and the hyperplane, write \(w\) in terms of \(\modmemf{\predvar}\) and \(M\).
Solution 15. The rise from the hyperplane to the point is \(\modmemf{x} - \modmemf{x_0} = \modmemf{x}\), since \(\modmemf{x_0} = 0\). With \(y = 1\) and \(w > 0\) the positive points sit to the right of \(x_0\), so the run is \(x - x_0 = M\), and
\[w = \frac{\modmemf{x}}{M}.\]
Exercise 16 (Write the margin in terms of the parameters, in one dimension (part 4))
Exercise 16 (Write the margin in terms of the parameters, in one dimension (part 4)) Use the setup of Exercise 13.
Now take \(\outvar = -1\), still with \(w > 0\), and do the same.
Solution 16. With \(y = -1\) and \(w > 0\) the point sits to the left, so the run is \(x - x_0 = -M\) and the same ratio gives
\[w = \frac{-\modmemf{x}}{M}.\]
Exercise 17 (Write the margin in terms of the parameters, in one dimension (part 5))
Exercise 17 (Write the margin in terms of the parameters, in one dimension (part 5)) Use the setup of Exercise 13.
Combine Exercise 15 and Exercise 16 into a single equation covering both labels, and rearrange it to solve for \(M\).
Solution 17. In both cases the numerator is \(y \, \modmemf{x}\), because multiplying by \(y\) flips the sign exactly when the point is on the negative side. So the two combine into
\[\frac{y \, \modmemf{x}}{M} = w \quad\text{that is}\quad y \, \modmemf{x} = wM \quad\text{that is}\quad \frac{y \, \modmemf{x}}{w} = M.\]
Exercise 18 (Write the margin in terms of the parameters, in one dimension (part 6))
Exercise 18 (Write the margin in terms of the parameters, in one dimension (part 6)) Use the setup of Exercise 13.
Check your equation when \(w < 0\). Does it still hold?
Solution 18. It fails. If \(w < 0\) then \(\modmem\) is decreasing, so the positive points are the ones to the left of \(\predvar_0\) and both runs in Solution 15 and Solution 16 flip sign. Redoing Solution 15 with \(\outvar = 1\) and \(w < 0\) gives run \(\predvar - \predvar_0 = -M\) and so \(w = -\modmemf{x}/M\), whence \(y \, \modmemf{x} = -wM\), which is a positive number only because \(w\) is negative.
Exercise 19 (Write the margin in terms of the parameters, in one dimension (part 7))
Exercise 19 (Write the margin in terms of the parameters, in one dimension (part 7)) Use the setup of Exercise 13.
If it fails, repair it.
Solution 19. The repair is to take the size of \(w\) rather than its signed value:
\[\frac{y \, \modmemf{x}}{M} = |w| \quad\text{that is}\quad y \, \modmemf{x} = |w| \, M \quad\text{that is}\quad \frac{y \, \modmemf{x}}{|w|} = M.\]
Both sides are now non-negative for a correctly classified point, whichever way \(\modmem\) slopes. Note that third form: the distance from a point to the hyperplane is the value of the linear function divided by the size of the slope. That ratio carries over to \(\ninputvars\) dimensions.
Theorem 1 (The margin of a point, in one dimension)
Theorem 1 (The margin of a point, in one dimension) Let \(\modmemf{x} = wx + b\) with \(w \neq 0\), and let \(x\) be a training point with label \(y \in \{-1, +1\}\) that lies on its own side of the hyperplane \(\modmemf{x} = 0\), at distance \(M\) from it. Then
\[ \frac{y \, \modmemf{x}}{M} = |w|, \qquad\text{that is}\qquad y \, \modmemf{x} = |w| \, M, \qquad\text{that is}\qquad \frac{y \, \modmemf{x}}{|w|} = M. \]
Proof
Proof. This is the solution to Exercise 13.
Exercise 20 (Turn “largest margin” into a constrained optimization problem)
Exercise 20 (Turn “largest margin” into a constrained optimization problem) Theorem 1 measured the margin of one point. Training has to choose \(w\) and \(b\) so that the smallest such measurement over the whole training set is as large as possible.
Write “every training point is at least \(M\) from the hyperplane, on its own side” as one inequality, indexed by \(i = 1, 2, \ldots, N\).
Solution 20. Apply the third form of Theorem 1 to every point at once, with \(\geq\) in place of \(=\) because only the nearest point attains \(M\):
\[\frac{y_{(i)}\paren{w x_{(i)} + b}}{|w|} \geq M, \qquad i = 1, 2, \ldots, N.\]
Exercise 21 (Turn “largest margin” into a constrained optimization problem (part 2))
Exercise 21 (Turn “largest margin” into a constrained optimization problem (part 2)) Use the setup of Exercise 20.
Write the full problem: what is maximized, over which variables, subject to what.
Solution 21. Maximize the margin over the parameters and the margin itself:
\[\begin{aligned} \mathop{\argmax}_{w,\,b,\,M} \quad & M \\ \text{s.t.} \quad & \frac{y_{(i)}\paren{w x_{(i)} + b}}{|w|} \geq M, \quad i = 1, 2, \ldots, N. \end{aligned}\]
Note the form. There is no sum over the training set and no average; each training point contributes a constraint rather than a term.
Exercise 22 (Turn “largest margin” into a constrained optimization problem (part 3))
Exercise 22 (Turn “largest margin” into a constrained optimization problem (part 3)) Use the setup of Exercise 20.
The problem you wrote is convex, so it has a unique optimal value \(M^*\). It does not have a unique optimal \((w^*, b^*)\). Explain why, and describe the set of optima.
Solution 22. Because the constraints only ever see \(w\) and \(b\) through the ratio \(\paren{w x_{(i)} + b} / |w|\), and that ratio is unchanged when \(w\) and \(b\) are both multiplied by the same positive constant \(c\):
\[ \begin{aligned} \frac{y_{(i)}\paren{cw x_{(i)} + cb}}{|cw|} &= \frac{c \, y_{(i)}\paren{w x_{(i)} + b}}{c \, |w|} \\ &= \frac{y_{(i)}\paren{w x_{(i)} + b}}{|w|}. \end{aligned} \]
So if \((w^*, b^*)\) is optimal then so is \((cw^*, cb^*)\) for every \(c > 0\), and the optima form a ray. Geometrically all of these describe the same hyperplane: they cross the axis at the same place and slope the same way, differing only in how steeply \(\modmem\) climbs away from it.
The problem is asking about the hyperplane, and \(\modmem\)’s steepness is a detail of how we wrote the hyperplane down.
Proposition 1 (The max-margin program has a ray of optima)
Proposition 1 (The max-margin program has a ray of optima) Consider the program, over \(w \neq 0\), \(b\) and \(M\), for a linearly separable training set \((x_{(i)}, y_{(i)})\), \(i = 1, 2, \ldots, N\),
\[\begin{aligned} \mathop{\argmax}_{w,\,b,\,M} \quad & M \\ \text{s.t.} \quad & \frac{y_{(i)}\paren{w x_{(i)} + b}}{|w|} \geq M, \quad i = 1, 2, \ldots, N. \end{aligned}\]
If \((w^*, b^*, M^*)\) is optimal, with \(M^* > 0\), then so is \((cw^*, cb^*, M^*)\) for every \(c > 0\). The optima therefore form a ray, and all of its members describe the same hyperplane.
Proof
Proof. This is the solution to Exercise 20.
Exercise 23 (Pick one representative from the ray of optima)
Exercise 23 (Pick one representative from the ray of optima) An infinite family of solutions is a nuisance for a solver, and by Proposition 1 every member of it describes the same hyperplane. So we are free to add one equation that selects a single member, provided it does not change which hyperplane comes out.
We choose this one: at the optimum, the support vectors satisfy
\[y_{(i)} \, \modmemf{x_{(i)}} = 1.\]
Explain why adding this equation loses no hyperplanes.
Solution 23. Take any optimal \((w^*, b^*)\), with margin \(M^*\). Its support vectors satisfy \(y_{(i)} \modmemf{x_{(i)}} = |w^*| M^*\) by Theorem 1, and that quantity is positive, so we may set \(c = 1 / \paren{|w^*| M^*} > 0\). Rescaling by \(c\) makes the support vectors’ value exactly \(1\).
So every hyperplane in the feasible set still has a representative, and now it has exactly one. The equation picks a member of the ray; it does not rule any ray out.
Exercise 24 (Pick one representative from the ray of optima (part 2))
Exercise 24 (Pick one representative from the ray of optima (part 2)) Use the setup of Exercise 23.
Under it, what is \(M\) in terms of \(|w|\)?
Solution 24. At a support vector \(\outvar_{(i)} \modmemf{\predvar_{(i)}} = |w| M\), and we have just declared that value to be \(1\), so
\[\frac{1}{M} = |w| \quad\text{that is}\quad 1 = |w| \, M \quad\text{that is}\quad \frac{1}{|w|} = M.\]
Exercise 25 (Pick one representative from the ray of optima (part 3))
Exercise 25 (Pick one representative from the ray of optima (part 3)) Use the setup of Exercise 23.
Substitute that into the problem of Proposition 1. What is now being maximized, and over which variables?
Solution 25. \(M\) is no longer a free variable — it is now determined by \(w\) — so it leaves the problem and its value takes the objective’s place:
\[\begin{aligned} \mathop{\argmax}_{w,\,b} \quad & \frac{1}{|w|} \\ \text{s.t.} \quad & \frac{y_{(i)}\paren{w x_{(i)} + b}}{|w|} \geq \frac{1}{|w|}, \quad i = 1, 2, \ldots, N. \end{aligned}\]
Exercise 26 (Pick one representative from the ray of optima (part 4))
Exercise 26 (Pick one representative from the ray of optima (part 4)) Use the setup of Exercise 23.
Simplify the objective and the constraints into the simplest form you can.
Solution 26. Maximizing \(1/|w|\) is minimizing \(|w|\), and every constraint may be multiplied through by \(|w| > 0\):
\[\begin{aligned} \mathop{\argmin}_{w,\,b} \quad & |w| \\ \text{s.t.} \quad & y_{(i)}\paren{w x_{(i)} + b} \geq 1, \quad i = 1, 2, \ldots, N. \end{aligned}\]
This form has a picture. Put a spike of height \(1\) at every positive point and a spike of height \(-1\) at every negative point. The constraints say the graph of \(\modmem\) must reach or pass the tip of every spike, and the objective says to do it with the shallowest slope available. A shallow line takes a long horizontal distance to climb from \(-1\) to \(1\), and that distance is the empty band around the boundary.
A line that breaks a constraint crosses a spike, dipping below the tip of an upward spike or rising above the tip of a downward one. That point is then either on the wrong side of the boundary or inside the margin, and the hard margin allows neither.
The picture also shows what separability is doing. If a positive point sits between two negative points, no line reaches all three spikes at once: the constraint set is empty and the problem has no solution. Separability is the condition that keeps it non-empty.
Theorem 2 (Fixing the scale of the max-margin program)
Theorem 2 (Fixing the scale of the max-margin program) Let \((w^*, b^*, M^*)\) be optimal for the program of Proposition 1, with \(w^* \neq 0\) and \(M^* > 0\). Then \((cw^*, cb^*)\), with \(c = 1 / \paren{|w^*| M^*}\), describes the same hyperplane and has \(y_{(i)}\paren{cw^* x_{(i)} + cb^*} = 1\) at every support vector \(x_{(i)}\). For any \(w \neq 0\) and \(b\) with \(y_{(i)}\paren{w x_{(i)} + b} = 1\) at every support vector, the margin is \(M = 1/|w|\), and the program becomes
\[\begin{aligned} \mathop{\argmin}_{w,\,b} \quad & |w| \\ \text{s.t.} \quad & y_{(i)}\paren{w x_{(i)} + b} \geq 1, \quad i = 1, 2, \ldots, N. \end{aligned}\]
Proof
Proof. This is the solution to Exercise 23.
What this chapter’s symbols are called elsewhere
Almost every symbol in this chapter is spelled differently somewhere else, and two of the substitutions reuse symbols that we use for something else.
| Here | Also written |
|---|---|
| \(\modmemf{x}\), the linear function | \(y(x)\) in Bishop; \(g(y)\) in Duda, Hart and Stork |
| \(w\), the weight vector | \(\beta\) in ESL and ISL; \(a\) in Duda, Hart and Stork, with the intercept included |
| \(b\), the intercept | \(\beta_0\) in ESL and ISL |
| \(M\), the margin | \(M\) in ESL and ISL; \(\gamma\) in Stanford’s CS229 notes; \(b\) in Duda, Hart and Stork |
| \(y_{(i)}\), the labels | \(t_n\) in Bishop; \(z_k\) in Duda, Hart and Stork |
| \(\alpha_i\), the dual variables | \(a_n\) in Bishop |
The two clashes are worth stating clearly. Duda, Hart and Stork write \(b\) for the margin, not the intercept, and their \(y\) is the feature-mapped input rather than the label, so two of their symbols mean something this chapter uses a different symbol for. Their margin satisfies \(b = 1/\norm{a}\), which is this chapter’s \(M = 1/\norm{w}_2\) written entirely in symbols we use for other things. Bishop’s \(y(x)\) is likewise the decision function, not the label.
Functional and geometric margin are the one pair of names worth adopting even though this chapter does not use them. CS229 calls \(y_{(i)} \modmemf{x_{(i)}}\) the functional margin, \(\hat\gamma\), and calls \(y_{(i)} \modmemf{x_{(i)}} /\norm{w}_2\) the geometric margin, \(\gamma\). This chapter’s \(M\) is the geometric one. The distinction is exactly what Solution 20 turns on: the functional margin scales when you scale \(w\) and \(b\), the geometric margin does not, and the ray of optima exists because only the geometric one is fixed.
Sources then use that freedom in two different ways. This chapter, CS229 and Bishop all set the support vectors’ functional margin to \(1\) — Bishop calls the result the canonical representation of the hyperplane. ESL instead requires \(\norm{\beta}_2 = 1\), which makes the functional and geometric margins equal and lets it keep \(M\) in the objective rather than trading it for \(1/\norm{w}_2\). Both pick one point on the same ray.
Exercise 27 (Carry the one-dimensional result up to \(\ninputvars\) dimensions)
Exercise 27 (Carry the one-dimensional result up to \(\ninputvars\) dimensions) Now let \(x, w \in \reals^{\ninputvars}\) and \(\modmemf{x} = \dprod{w}{x} + b\). The equations of Theorem 1 no longer make sense: \(|w|\) was the size of a number, and \(w\) is now a vector.
\(|w|\) measured the length of the slope. What function gives the length of a vector?
Solution 27. The \(\lpnorm{2}\) norm, \(\norm{w}_2 = \sqrt{w_1^2 + \cdots + w_{\ninputvars}^2}\). In one dimension it is exactly \(|w|\), so this is a generalization rather than a replacement.
Exercise 28 (Carry the one-dimensional result up to \(\ninputvars\) dimensions (part 2))
Exercise 28 (Carry the one-dimensional result up to \(\ninputvars\) dimensions (part 2)) Use the setup of Exercise 27.
Rewrite the three forms of Theorem 1 with that substitution.
Solution 28. \[\frac{y \, \modmemf{x}}{M} =\norm{w}_2 \quad\text{that is}\quad y \, \modmemf{x} =\norm{w}_2 \, M \quad\text{that is}\quad \frac{y \, \modmemf{x}}{\norm{w}_2} = M.\]
Exercise 29 (Carry the one-dimensional result up to \(\ninputvars\) dimensions (part 3))
Exercise 29 (Carry the one-dimensional result up to \(\ninputvars\) dimensions (part 3)) Use the setup of Exercise 27.
Check Exercise 28 geometrically. Draw the contour lines \(\modmemf{\predvar} = 0\), \(\modmemf{\predvar} = 1\), \(\modmemf{\predvar} = 2\) and so on, and say what value \(\modmem\) takes at a point sitting a distance \(M\) from the hyperplane on the positive side, then on the negative side.
Solution 29. The contours of \(\modmem\) are hyperplanes parallel to the boundary, evenly spaced, and \(\modmem\) climbs fastest in the direction of \(w\). Moving a distance \(M\) from the boundary along that direction raises \(\modmem\) by \(\norm{w}_2 M\), so a point sitting \(M\) away on the positive side has
\[\modmemf{x} =\norm{w}_2 \, M,\]
and one sitting \(M\) away on the negative side has \(\modmemf{x} = -\norm{w}_2 M\). Multiplying by the label gives \(\outvar \, \modmemf{\predvar} =\norm{w}_2 M\) in both cases, which is Solution 28.
Exercise 30 (Carry the one-dimensional result up to \(\ninputvars\) dimensions (part 4))
Exercise 30 (Carry the one-dimensional result up to \(\ninputvars\) dimensions (part 4)) Use the setup of Exercise 27.
Rewrite the problem of Theorem 2 in \(\ninputvars\) dimensions.
Solution 30. \[\begin{aligned} \mathop{\argmin}_{w,\,b} \quad &\norm{w}_2 \\ \text{s.t.} \quad & y_{(i)}\paren{\dprod{w}{x_{(i)}} + b} \geq 1, \quad i = 1, 2, \ldots, N. \end{aligned}\]
Nothing about the derivation used \(\ninputvars = 1\) except the notation for length. We therefore solved the easy case by the method that extends to higher dimensions.
Theorem 3 (The margin of a point, in \(\ninputvars\) dimensions)
Theorem 3 (The margin of a point, in \(\ninputvars\) dimensions) Let \(\modmemf{x} = \dprod{w}{x} + b\) with \(w \in \reals^{\ninputvars}\) and \(w \neq \vzero\), and let \(x\) be a training point with label \(y \in \{-1, +1\}\) that lies on its own side of the hyperplane \(\modmemf{x} = 0\), at distance \(M\) from it. Then
\[ \frac{y \, \modmemf{x}}{M} = \norm{w}_2, \qquad\text{that is}\qquad y \, \modmemf{x} = \norm{w}_2 \, M, \qquad\text{that is}\qquad \frac{y \, \modmemf{x}}{\norm{w}_2} = M. \]
Proof
Proof. This is the solution to Exercise 27.
Exercise 31 (Put the objective into the form a solver wants)
Exercise 31 (Put the objective into the form a solver wants) The \(\ninputvars\)-dimensional version of the program in Theorem 2, which Exercise 30 asks for, minimizes \(\norm{w}_2\). The form everyone actually writes down minimizes \(\tfrac{1}{2}\norm{w}_2^2\) instead.
Show that the two objectives have the same minimizer.
Solution 31. \(t \mapsto \tfrac{1}{2}t^2\) is strictly increasing on \(t \geq 0\), and \(\norm{w}_2 \geq 0\) always. A strictly increasing transformation of the objective reorders nothing, so the feasible point that minimizes one minimizes the other. The optimal value changes; the optimal \((w, b)\) does not.
Exercise 32 (Put the objective into the form a solver wants (part 2))
Exercise 32 (Put the objective into the form a solver wants (part 2)) Use the setup of Exercise 31.
Give two reasons to prefer the squared form.
Solution 32. The square root is gone, and with it the point of non-differentiability at \(w = 0\). \(\norm{w}_2\) has no gradient there, whereas \(\tfrac{1}{2}\norm{w}_2^2\) is a polynomial in the entries of \(w\) and is differentiable everywhere. And the squared form is quadratic, which together with the linear constraints puts the problem in a class solvers are built for.
Exercise 33 (Put the objective into the form a solver wants (part 3))
Exercise 33 (Put the objective into the form a solver wants (part 3)) Use the setup of Exercise 31.
What is the \(\tfrac{1}{2}\) for?
Solution 33. Convenience of the gradient: \(\grad_w \tfrac{1}{2}\norm{w}_2^2 = w\) rather than \(2w\). It changes nothing about the solution.
Exercise 34 (Put the objective into the form a solver wants (part 4))
Exercise 34 (Put the objective into the form a solver wants (part 4)) Use the setup of Exercise 31.
Write the resulting problem out in full.
Solution 34. The hard-margin primal problem:
\[\begin{aligned} \mathop{\mathrm{arg\,min}}_{w,\,b} \quad & \frac{1}{2}\norm{w}_2^2 \\ \text{s.t.} \quad & y_{(i)}\paren{w^\top x_{(i)} + b} \geq 1, \quad i = 1, 2, \ldots, N. \end{aligned}\]
Exercise 35 (Put the objective into the form a solver wants (part 5))
Exercise 35 (Put the objective into the form a solver wants (part 5)) Use the setup of Exercise 31.
Classify it: what is the objective as a function of \((w, b)\), and what are the constraints?
Definition 7 (Hard-margin primal problem)
Definition 7 (Hard-margin primal problem) The hard-margin primal problem for a linearly separable training set is
\[\begin{aligned} \mathop{\argmin}_{w,\,b} \quad & \frac{1}{2}\norm{w}_2^2 \\ \text{s.t.} \quad & y_{(i)}\paren{\dprod{w}{x_{(i)}} + b} \geq 1, \quad i = 1, 2, \ldots, N. \end{aligned}\]
Its solution is the max-margin hyperplane of Definition 6, scaled so that the support vectors of Definition 5 satisfy \(y_{(i)}\paren{\dprod{w}{x_{(i)}} + b} = 1\).
Example 4 (Checking the primal problem on the ten cars)
Example 4 (Checking the primal problem on the ten cars) For the ten cars of Example 2, compare two feasible points of Definition 7: the max-margin \((w, b)\) of Example 3, and the bisector of the class means, rescaled by the smallest factor that makes every constraint \(y_{(i)}\paren{\dprod{w}{x_{(i)}} + b} \geq 1\) hold. For each, find the tightest constraint and the objective \(\frac{1}{2}\norm{w}_2^2\):
# Constraint values y (w.x + b); the primal requires every one to be at least 1.
cons_mm = y_sep * (X_sep @ w_mm + b_mm)
# Dividing the bisector by its smallest constraint value makes that constraint exactly 1.
rescale_hp = 1 / (y_sep * (X_sep @ w_ls + b_ls)).min()
w_hp, b_hp = rescale_hp * w_ls, rescale_hp * b_ls
cons_hp = y_sep * (X_sep @ w_hp + b_hp)
print(pd.DataFrame({
"candidate": ["max-margin", "rescaled bisector"],
"tightest_constraint": [cons_mm.min(), cons_hp.min()],
"objective": [0.5 * w_mm @ w_mm, 0.5 * w_hp @ w_hp],
}).round(4)) candidate tightest_constraint objective
0 max-margin 1.0 0.6686
1 rescaled bisector 1.0 1.32893# Constraint values y (w.x + b); the primal requires every one to be at least 1.
cons_mm <- y_sep * (drop(X_sep %*% w_mm) + b_mm)
# Dividing the bisector by its smallest constraint value makes that constraint exactly 1.
rescale_hp <- 1 / min(y_sep * (drop(X_sep %*% w_ls) + b_ls))
w_hp <- rescale_hp * w_ls
b_hp <- rescale_hp * b_ls
cons_hp <- y_sep * (drop(X_sep %*% w_hp) + b_hp)
data.frame(
candidate = c("max-margin", "rescaled bisector"),
tightest_constraint = c(min(cons_mm), min(cons_hp)),
objective = c(0.5 * sum(w_mm^2), 0.5 * sum(w_hp^2))
) |> dplyr::mutate(dplyr::across(where(is.numeric), \(v) round(v, 4)))[1] 3Both candidates satisfy every constraint, and each has a tightest constraint equal to 1, so both are feasible. The objective separates them: 0.669 for the max-margin hyperplane against 1.329 for the rescaled bisector. Minimizing \(\frac{1}{2}\norm{w}_2^2\) is the same as maximizing the margin, since the margin is \(1/\norm{w}_2\) when the tightest constraint is 1: 0.865 here, which is the margin found in Example 3. The 3 constraints that hold with equality belong to the support vectors.
Exercise 36 (Compare the margins of three training sets)
Exercise 36 (Compare the margins of three training sets) Three training sets in \(\reals^2\):
A positive point at \((1, 1)\) and a negative point at \((-1, -1)\).
A positive point at \((0, 5)\) and a negative point at \((0, -5)\).
All four of those points at once.
Write \(M_i\) for the largest margin that any separating hyperplane achieves in scenario \(i\). Which of \(M_1\), \(M_2\) and \(M_3\) are equal, and which is the smallest? Then name the support vectors in scenario 3.
Solution 36. \[ \begin{aligned} M_1 &= M_3 \\ &= \sqrt{2} \\ &\approx 1.414 \\ &< M_2 \\ &= 5. \end{aligned} \]
Scenarios 1 and 2 have one point per class, so the max-margin hyperplane is the perpendicular bisector of the segment joining them and the margin is half that segment’s length. In scenario 1 the points are \(\sqrt{2^2 + 2^2} = 2\sqrt{2}\) apart, giving \(M_1 = \sqrt{2}\) with the hyperplane \(x_1 + x_2 = 0\). In scenario 2 they are \(10\) apart, giving \(M_2 = 5\) with the hyperplane \(x_2 = 0\).
Scenario 3 adds constraints without removing any. Adding a constraint can never enlarge a feasible set, so \(M_3 \leq \min(M_1, M_2) = \sqrt{2}\). And the hyperplane \(x_1 + x_2 = 0\) achieves \(\sqrt{2}\) on all four points: \((\pm 1, \pm 1)\) sit at distance \(\sqrt{2}\) and \((0, \pm 5)\) at distance \(5/\sqrt{2} \approx 3.54\). So \(M_3 = \sqrt{2}\) exactly.
The support vectors in scenario 3 are \((1, 1)\) and \((-1, -1)\). The points at \((0, 5)\) and \((0, -5)\) sit at distance \(5/\sqrt{2} > \sqrt{2}\), so by Definition 5 they are not support vectors, and deleting them would leave the solution untouched — even though on their own they admit a margin more than three times as large.
Two points follow from this. A training set’s margin is set by its worst pair, not by its typical spacing, so one point near the boundary is enough to make a widely spaced data set behave like a closely spaced one. And the solution depends on very few of the training points, a property the dual formulation of the same problem makes explicit.
Watch
Andrew Ng introduces SVMs in CS229, from 43:27, and defines the functional and geometric margins, from 54:15 [9], Lecture 6.
Watch
Every convex optimization problem has a paired problem, called its dual, built from the constraints rather than from the objective. Solving one solves the other. A full treatment belongs in a convex optimization course; we need only to see what the dual of Definition 7 looks like and why anyone would prefer it.
Three facts make the dual worth the extra work. It is the form in which the support vectors appear explicitly, so solving it is how you find them. It trades a problem in \(\ninputvars + 1\) unknowns for one in \(N\), which is better whenever the features outnumber the examples. And it is the only one of the two that survives the step to non-linear classifiers, where \(\ninputvars\) can be infinite.
Exercise 37 (Read the dual problem before deriving anything)
Exercise 37 (Read the dual problem before deriving anything) Here is the dual of Definition 7. Deriving it needs Lagrange multipliers and is out of scope; reading it is not.
\[\begin{aligned} \mathop{\argmax}_{\dualvar \in \reals^N} \quad & \sumiN \dualvar_i - \frac{1}{2}\sumiN\sumto{j}{N} \dualvar_i \dualvar_j \, y_{(i)} y_{(j)} \, \dprod{x_{(i)}}{x_{(j)}} \\ \text{s.t.} \quad & \dualvar_i \geq 0, \quad i = 1, 2, \ldots, N \\ & \sumiN \dualvar_i \, y_{(i)} = 0. \end{aligned}\]
How many unknowns does it have, and what does each one attach to?
Solution 37. \(N\) unknowns, one per training example: \(\dualvar_i\) belongs to the point \(x_{(i)}\).
Exercise 38 (Read the dual problem before deriving anything (part 2))
Exercise 38 (Read the dual problem before deriving anything (part 2)) Use the setup of Exercise 37.
Compare that with the primal’s count.
Exercise 39 (Read the dual problem before deriving anything (part 3))
Exercise 39 (Read the dual problem before deriving anything (part 3)) Use the setup of Exercise 37.
Where did \(w\) and \(b\) go?
Solution 39. Out of the problem entirely. They come back afterwards, computed from the \(\dualvar_i\).
Exercise 40 (Read the dual problem before deriving anything (part 4))
Exercise 40 (Read the dual problem before deriving anything (part 4)) Use the setup of Exercise 37.
The training inputs appear in exactly one place. Where, and in what form?
Solution 40. Only inside the inner products \(\dprod{\predvar_{(i)}}{\predvar_{(j)}}\). Every one of the \(N^2\) coefficients of the objective is one such number, and the inputs appear nowhere else.
Exercise 41 (Read the dual problem before deriving anything (part 5))
Exercise 41 (Read the dual problem before deriving anything (part 5)) Use the setup of Exercise 37.
What does the problem therefore need to know about the data?
Solution 41. A solver therefore does not need the points themselves — it needs the matrix of pairwise inner products, and nothing more.
Exercise 42 (Read the dual problem before deriving anything (part 6))
Exercise 42 (Read the dual problem before deriving anything (part 6)) Use the setup of Exercise 37.
Name one situation in which you would rather solve this than the primal, using only your answers to Exercise 37 and Exercise 39.
Solution 42. Whenever \(N < \ninputvars\), by Solution 38: fewer unknowns to solve for. Or whenever the inner products are cheap to compute but the coordinates are expensive to store, by Solution 39 — which is where the kernel trick applies.
Definition 8 (Hard-margin dual problem)
Definition 8 (Hard-margin dual problem) The hard-margin dual problem is
\[\begin{aligned} \mathop{\argmax}_{\dualvar \in \reals^N} \quad & \sumiN \dualvar_i - \frac{1}{2}\sumiN\sumto{j}{N} \dualvar_i \dualvar_j \, y_{(i)} y_{(j)} \, \dprod{x_{(i)}}{x_{(j)}} \\ \text{s.t.} \quad & \dualvar_i \geq 0, \quad i = 1, 2, \ldots, N \\ & \sumiN \dualvar_i \, y_{(i)} = 0, \end{aligned}\]
whose solution determines the same hyperplane as Definition 7.
Definition 9 (Dual variable)
Definition 9 (Dual variable) The dual variable \(\dualvar_i\) is the unknown Definition 8 attaches to training example \(x_{(i)}\), constrained to be non-negative.
Example 5 (Dual variables of the ten cars)
Example 5 (Dual variables of the ten cars) The solver of Example 3 maximizes Definition 8 over the dual variables \(\dualvar_1, \ldots, \dualvar_{10}\), one per car. Print them, check the constraints of the dual, and compare the dual objective with the primal objective \(\frac{1}{2}\norm{w}_2^2\):
ay_dm = alpha_mm * y_sep # alpha_i * y_i, which also builds w
# The dual objective: sum of alphas minus a quadratic form in alpha * y.
dual_obj_dm = alpha_mm.sum() - 0.5 * ay_dm @ K_mm @ ay_dm
primal_obj_dm = 0.5 * w_mm @ w_mm
print(pd.DataFrame({"name": cars_ls["name"].to_numpy(), "alpha": alpha_mm.round(4)})) name alpha
0 chevrolet impala 0.0000
1 plymouth fury iii 0.0000
2 pontiac catalina 0.0000
3 plymouth 'cuda 340 0.4174
4 buick estate wagon (sw) 0.2512
5 peugeot 304 0.0000
6 fiat 124b 0.6686
7 toyota corolla 1200 0.0000
8 datsun 1200 0.0000
9 datsun b210 0.0000smallest alpha: 0.0sum of alpha * y: 2.7755575615628914e-16dual and primal objectives: 0.6686099330013634 0.6686096260601547ay_dm <- alpha_mm * y_sep # alpha_i * y_i, which also builds w
# The dual objective: sum of alphas minus a quadratic form in alpha * y.
dual_obj_dm <- sum(alpha_mm) - 0.5 * drop(t(ay_dm) %*% K_mm %*% ay_dm)
primal_obj_dm <- 0.5 * sum(w_mm^2)
data.frame(name = cars_ls$name, alpha = round(alpha_mm, 4))smallest alpha: 0 sum of alpha * y: 2.775558e-16 dual and primal objectives: 0.6686099 0.6686096 Every dual variable is non-negative, and \(\sumiN \dualvar_i y_{(i)}\) is 3e-16 in absolute value, which is zero up to rounding, so the solution satisfies the constraints of Definition 8. Only 3 of the ten dual variables are positive, and they belong to the support vectors of Example 3; the other cars have \(\dualvar_i = 0\). The dual objective is 0.6686 and the primal objective is 0.6686, so the dual problem recovers the same hyperplane at the same optimal value.
Exercise 43 (Show that the optimal \(w\) is a weighted sum of the training inputs)
Exercise 43 (Show that the optimal \(w\) is a weighted sum of the training inputs) Definition 7 searches over every \(w \in \reals^{\ninputvars}\). You can show that its solution lies in a much smaller set using nothing more than inner products.
Split any weight vector \(w\) into two pieces,
\[w = w_\parallel + w_\perp,\]
where
Every \(w\) splits this way: \(w_\parallel\) is the orthogonal projection of \(w\) onto the set of weighted sums of the training inputs, and \(w_\perp = w - w_\parallel\) is the remainder.
Show that \(\dprod{w}{\predvar_{(i)}} = \dprod{w_\parallel}{\predvar_{(i)}}\) for every \(i\).
Solution 43. Substitute the split and distribute the inner product:
\[\begin{aligned} \dprod{w}{x_{(i)}} &= \pt{w_\parallel + w_\perp} x_{(i)} && \text{(split } w \text{)} \\ &= \dprod{w_\parallel}{x_{(i)}} + \dprod{w_\perp}{x_{(i)}} && \text{(inner product distributes over a sum)} \\ &= \dprod{w_\parallel}{x_{(i)}} + 0 && \text{(} w_\perp \text{ is orthogonal to } x_{(i)} \text{)} \\ &= \dprod{w_\parallel}{x_{(i)}}. \end{aligned}\]
Exercise 44 (Show that the optimal \(w\) is a weighted sum of the training inputs (part 2))
Exercise 44 (Show that the optimal \(w\) is a weighted sum of the training inputs (part 2)) Use the setup of Exercise 43.
Suppose \((w, b)\) satisfies every constraint of Definition 7. Does \((w_\parallel, b)\)?
Solution 44. Yes. The \(i\)th constraint sees \(w\) only through \(\dprod{w}{x_{(i)}}\), so by Solution 43
\[y_{(i)}\paren{\dprod{w}{x_{(i)}} + b} = y_{(i)}\paren{\dprod{w_\parallel}{x_{(i)}} + b},\]
and each constraint holds for \((w_\parallel, b)\) exactly when it holds for \((w, b)\). The constraints do not depend on \(w_\perp\) at all.
Exercise 45 (Show that the optimal \(w\) is a weighted sum of the training inputs (part 3))
Exercise 45 (Show that the optimal \(w\) is a weighted sum of the training inputs (part 3)) Use the setup of Exercise 43.
Write \(\norm{w}_2^2\) in terms of \(\norm{w_\parallel}_2^2\) and \(\norm{w_\perp}_2^2\).
Solution 45. Write the squared norm as an inner product and expand:
\[\begin{aligned}\norm{w}_2^2 &= \pt{w_\parallel + w_\perp} \paren{w_\parallel + w_\perp} && \text{(squared norm as an inner product)} \\ &= \dprod{w_\parallel}{w_\parallel} + \dprod{w_\parallel}{w_\perp} + \dprod{w_\perp}{w_\parallel} + \dprod{w_\perp}{w_\perp} && \text{(distribute)} \\ &=\norm{w_\parallel}_2^2 + 2\, \dprod{w_\parallel}{w_\perp} +\norm{w_\perp}_2^2 && \text{(inner product is symmetric)}. \end{aligned}\]
The cross term vanishes, because \(w_\parallel\) is built from vectors that \(w_\perp\) is orthogonal to:
\[\begin{aligned} \dprod{w_\parallel}{w_\perp} &= \paren{\sumiN c_i \, x_{(i)}}^{\!\top} w_\perp && \text{(definition of } w_\parallel \text{)} \\ &= \sumiN c_i \, \dprod{x_{(i)}}{w_\perp} && \text{(inner product distributes over a sum)} \\ &= \sumiN c_i \cdot 0 && \text{(} w_\perp \text{ is orthogonal to each } x_{(i)} \text{)} \\ &= 0. \end{aligned}\]
So \(\norm{w}_2^2 =\norm{w_\parallel}_2^2 +\norm{w_\perp}_2^2\), which is Pythagoras’ theorem.
Exercise 46 (Show that the optimal \(w\) is a weighted sum of the training inputs (part 4))
Exercise 46 (Show that the optimal \(w\) is a weighted sum of the training inputs (part 4)) Use the setup of Exercise 43.
Suppose \((w, b)\) solves Definition 7 and \(w_\perp \neq 0\). Find a feasible point with a smaller objective.
Solution 46. \((w_\parallel, b)\) is feasible, by Solution 44. Its objective is
\[\begin{aligned} \frac{1}{2}\norm{w_\parallel}_2^2 &= \frac{1}{2}\norm{w}_2^2 - \frac{1}{2}\norm{w_\perp}_2^2 && \text{(@sol-w-from-the-inputs-part3)} \\ &< \frac{1}{2}\norm{w}_2^2 && \text{(} w_\perp \neq 0 \text{, so }\norm{w_\perp}_2^2 > 0 \text{)}, \end{aligned}\]
smaller than the objective at \((w, b)\), which contradicts \((w, b)\) being a solution.
Exercise 47 (Show that the optimal \(w\) is a weighted sum of the training inputs (part 5))
Exercise 47 (Show that the optimal \(w\) is a weighted sum of the training inputs (part 5)) Use the setup of Exercise 43.
What does that say about \(w_\perp\) at the optimum?
Solution 47. So \(w_\perp = 0\) at the optimum. \(w_\perp\) adds to the objective and changes no constraint.
Exercise 48 (Show that the optimal \(w\) is a weighted sum of the training inputs (part 6))
Exercise 48 (Show that the optimal \(w\) is a weighted sum of the training inputs (part 6)) Use the setup of Exercise 43.
What form does the optimal \(w\) take?
Solution 48. Every optimal \(w\) is therefore
\[ \begin{aligned} w &= w_\parallel \\ &= \sumiN c_i \, x_{(i)}. \end{aligned} \]
Exercise 49 (Show that the optimal \(w\) is a weighted sum of the training inputs (part 7))
Exercise 49 (Show that the optimal \(w\) is a weighted sum of the training inputs (part 7)) Use the setup of Exercise 43.
What does your argument say about the values of the weights \(c_i\)?
Theorem 4 (The optimal weight vector is a weighted sum of the training inputs)
Theorem 4 (The optimal weight vector is a weighted sum of the training inputs) If \((w, b)\) solves Definition 7, then there are real numbers \(c_1, c_2, \ldots, c_N\) with
\[w = \sumiN c_i \, x_{(i)};\]
that is, \(w\) is a linear combination of the training inputs, and lies in their span.
Proof
Proof. By Solution 43 to Solution 46.
Example 6 (The weight vector as a sum of the support vectors)
Example 6 (The weight vector as a sum of the support vectors) For the ten cars, get \(w\) in two ways. First, solve the three equations \(y_{(i)}\paren{\dprod{w}{x_{(i)}} + b} = 1\) of the support vectors for \((w_1, w_2, b)\). Second, form the weighted sum \(\sumiN c_i x_{(i)}\) of Theorem 4 with \(c_i = \dualvar_i y_{(i)}\):
sv_wi = np.flatnonzero(alpha_mm > 1e-6) # the support vectors
# Route 1: three linear equations in (w1, w2, b), one per support vector.
sol_wi = np.linalg.solve(np.column_stack([X_sep[sv_wi], np.ones(len(sv_wi))]), y_sep[sv_wi])
# Route 2: the weighted sum of the inputs.
c_wi = alpha_mm * y_sep
w_sum_wi = c_wi @ X_sep
print(pd.DataFrame({"name": cars_ls["name"].to_numpy(), "c": c_wi.round(4)}).iloc[sv_wi]) name c
3 plymouth 'cuda 340 -0.4174
4 buick estate wagon (sw) -0.2512
6 fiat 124b 0.6686[-0.90095085 -0.72491891] [-0.90095064 -0.72491875] 2.0680144907636588e-07sv_wi <- which(alpha_mm > 1e-6) # the support vectors
# Route 1: three linear equations in (w1, w2, b), one per support vector.
sol_wi <- solve(cbind(X_sep[sv_wi, ], 1), y_sep[sv_wi])
# Route 2: the weighted sum of the inputs.
c_wi <- alpha_mm * y_sep
w_sum_wi <- drop(c_wi %*% X_sep)
data.frame(name = cars_ls$name, c = round(c_wi, 4))[sv_wi, ] [,1] [,2]
equations -0.9009508 -0.7249189
weighted_sum -0.9009506 -0.7249187[1] 2.068014e-07The two routes agree to 2e-07, so \(w = (-0.901, -0.725)\) is a weighted sum of the inputs. The weights are zero for the 7 cars that are not support vectors, and nonzero only for the 3 that are. In two dimensions any vector is a combination of two non-parallel inputs, so the span claim is automatic here; what the example shows is which weights the theorem uses. The example after Theorem 5 checks the span claim with 8 inputs in 57 dimensions, where it is not automatic.
Theorem 4 proves that the hard-margin optimum is a weighted sum of the training inputs, by way of the constrained primal. The same description is available for an unconstrained empirical risk, and the argument is different. It follows what gradient descent does.
Take a linear model whose loss sees each training point only through the score \(\dprod{w}{x_{(i)}}\), and let \[ R(w) = \avgiN \lossf{\dprod{w}{x_{(i)}}, y_{(i)}} \] be its empirical risk. By the chain rule, \[ \nabla R(w) = \avgiN g_i \, x_{(i)}, \qquad g_i = \loss'\paren{\dprod{w}{x_{(i)}}, y_{(i)}}, \] where \(\loss'\) is the derivative of the loss with respect to its first argument. Whatever the loss is, this gradient is a weighted sum of the training inputs. Each \(x_{(i)}\) reaches the loss only through the scalar \(\dprod{w}{x_{(i)}}\), so differentiating that scalar leaves \(x_{(i)}\) behind as the outer factor.
Theorem 5 (Gradient descent from zero stays in the span of the training inputs)
Theorem 5 (Gradient descent from zero stays in the span of the training inputs) Let \(\loss\) be differentiable in its first argument. Run gradient descent on \(R\) from \(w^{(0)} = 0\) with step size \(\learnrate\): \[ w^{(t+1)} = w^{(t)} - \learnrate\,\nabla R\paren{w^{(t)}}. \] Then, for every \(t\), there are real numbers \(c_1^{(t)}, \dots, c_N^{(t)}\) with \[ w^{(t)} = \sumiN c_i^{(t)} \, x_{(i)}. \]
Proof
Proof. By induction on \(t\).
Base step. \(w^{(0)} = 0 = \sumiN 0 \cdot x_{(i)}\), a weighted sum with every coefficient zero.
Inductive step. Assume \(w^{(t)} = \sumiN c_i^{(t)} x_{(i)}\). Substituting the gradient into the update, with \(g_i^{(t)}\) the value of \(g_i\) at \(w^{(t)}\), \[ w^{(t+1)} = \sumiN c_i^{(t)} x_{(i)} - \frac{\learnrate}{N}\sumiN g_i^{(t)} x_{(i)} = \sumiN \underbrace{\paren{c_i^{(t)} - \frac{\learnrate}{N} g_i^{(t)}}}_{c_i^{(t+1)}} x_{(i)}, \] which is again a weighted sum of the training inputs.
Example 7 (Gradient descent on spam emails)
Example 7 (Gradient descent on spam emails) In the Spambase data [14], take the first four spam and the first four non-spam emails, so \(N = 8\) inputs with \(\ninputvars = 57\) standardized features. Run gradient descent from \(w^{(0)} = 0\) on the logistic loss, with step size \(\learnrate = 0.5\) for 200 steps, and update the coefficients \(c_i^{(t)}\) of the proof alongside the weights. Then compare \(w^{(t)}\) with \(\sumiN c_i^{(t)} x_{(i)}\):
spam_gs = pd.read_csv("data/spambase.csv")
feat_gs = spam_gs.drop(columns="Class").to_numpy(float)
feat_gs = (feat_gs - feat_gs.mean(axis=0)) / feat_gs.std(axis=0, ddof=1)
lab_gs = np.where(spam_gs["Class"] == 1, 1.0, -1.0)
pick_gs = np.r_[np.flatnonzero(lab_gs > 0)[:4], np.flatnonzero(lab_gs < 0)[:4]]
X_gs, y_gs = feat_gs[pick_gs], lab_gs[pick_gs]
h_gs = 0.5
w_gs, c_gs = np.zeros(X_gs.shape[1]), np.zeros(len(y_gs))
for _ in range(200):
# g_i: derivative of the logistic loss with respect to the score w.x_i.
g_gs = -y_gs / (1 + np.exp(y_gs * (X_gs @ w_gs)))
w_gs = w_gs - h_gs * (g_gs @ X_gs) / len(y_gs) # gradient descent on the weights
c_gs = c_gs - h_gs * g_gs / len(y_gs) # the same step, on the coefficients
print(X_gs.shape, np.linalg.matrix_rank(X_gs))(8, 57) 83.2999845761032036 3.219646771412954e-15spam_gs <- read.csv("data/spambase.csv")
feat_gs <- scale(as.matrix(spam_gs[, names(spam_gs) != "Class"]))
lab_gs <- ifelse(spam_gs$Class == 1, 1, -1)
pick_gs <- c(head(which(lab_gs > 0), 4), head(which(lab_gs < 0), 4))
X_gs <- feat_gs[pick_gs, ]
y_gs <- lab_gs[pick_gs]
h_gs <- 0.5
w_gs <- numeric(ncol(X_gs))
c_gs <- numeric(length(y_gs))
for (step in 1:200) {
# g_i: derivative of the logistic loss with respect to the score w.x_i.
g_gs <- -y_gs / (1 + exp(y_gs * drop(X_gs %*% w_gs)))
w_gs <- w_gs - h_gs * drop(g_gs %*% X_gs) / length(y_gs) # gradient descent on the weights
c_gs <- c_gs - h_gs * g_gs / length(y_gs) # the same step, on the coefficients
}
c(dim(X_gs), rank = qr(X_gs)$rank) rank
8 57 8 norm_w max_diff
3.299985e+00 2.220446e-15 The weight vector lives in \(\reals^{57}\), but the 8 training inputs span only 8 of those dimensions. After 200 steps \(w\) has norm 3.30, and it differs from the weighted sum \(\sumiN c_i^{(200)} x_{(i)}\) by at most 2e-15, which is rounding error. So Theorem 5 holds here: \(w^{(200)}\) lies in the 8-dimensional span of the inputs, though nothing forced it to in \(\reals^{57}\).
So every iterate lies in the span of the training inputs, and so does anything the iterates converge to, since a span is closed. The argument did not use the particular loss, such as squared error. It used only that the loss sees each input through \(\dprod{w}{x_{(i)}}\), and that the starting point was in the span. This is the representer theorem in its simplest form [13]. With \(N\) coefficients rather than \(\ninputvars\), it matters whenever \(\ninputvars\) is the larger of the two.
Remark 1 (What we still assume without proof)
Remark 1 (What we still assume without proof). Theorem 4 says weights \(c_i\) exist; the derivation of Definition 8, which needs Lagrange multipliers and is out of scope, supplies a particular choice of them:
\[c_i = \dualvar_i \, y_{(i)},\]
with \(\dualvar\) the solution of Definition 8. Theorem 4 is proved; that identification is not, and the rest of this section assumes it without proof.
Writing \(c_i\) as \(\dualvar_i y_{(i)}\) is always possible: set \(\dualvar_i = c_i y_{(i)}\), and then
\[ \begin{aligned} \dualvar_i y_{(i)} &= c_i y_{(i)}^2 \\ &= c_i, \end{aligned} \]
since \(y_{(i)}^2 = 1\). What the dual derivation adds is that, for its choice of weights, the \(\dualvar_i\) are non-negative, so each non-zero weight has the sign of its own point’s label, and that they solve Definition 8.
Exercise 50 (Check that the dual objective is the primal objective in disguise)
Exercise 50 (Check that the dual objective is the primal objective in disguise) The dual’s two terms look unrelated to anything in Definition 7. They are not. Theorem 4 makes the optimal weight vector a weighted sum of the training inputs, and Remark 1 supplies the weights, without proof:
\[w = \sumiN \dualvar_i \, y_{(i)} \, x_{(i)},\]
each training input weighted by its own \(\dualvar_i\) and signed by its label.
Substitute that into \(\tfrac{1}{2}\norm{w}_2^2\) and expand. What do you get?
Solution 50. Write the squared norm as an inner product and substitute both copies of \(w\):
\[\begin{aligned} \frac{1}{2}\norm{w}_2^2 &= \frac{1}{2} \dprod{w}{w} \\ &= \frac{1}{2}\paren{\sumiN \dualvar_i y_{(i)} x_{(i)}}^{\!\top} \paren{\sumto{j}{N} \dualvar_j y_{(j)} x_{(j)}} \\ &= \frac{1}{2}\sumiN\sumto{j}{N} \dualvar_i \dualvar_j \, y_{(i)} y_{(j)} \, \dprod{x_{(i)}}{x_{(j)}}. \end{aligned}\]
The second index has to be renamed, because the two sums run independently. That is where the double sum comes from, and why the training inputs meet each other pairwise.
Exercise 51 (Check that the dual objective is the primal objective in disguise (part 2))
Exercise 51 (Check that the dual objective is the primal objective in disguise (part 2)) Use the setup of Exercise 50.
The dual maximizes the negative of that quantity. What is it therefore doing to \(\norm{w}_2\), and how does that compare with the primal?
Solution 51. Maximizing the negative of \(\tfrac{1}{2}\norm{w}_2^2\) is minimizing \(\tfrac{1}{2}\norm{w}_2^2\), which is exactly the primal’s objective. So the dual’s second term is the primal’s whole objective with its sign flipped, and the constraints contribute the first term.
Exercise 52 (Check that the dual objective is the primal objective in disguise (part 3))
Exercise 52 (Check that the dual objective is the primal objective in disguise (part 3)) Use the setup of Exercise 50.
Using \(\dualvar_i \geq 0\), rewrite \(\sumiN \dualvar_i\) as a norm of the vector \(\dualvar\).
Solution 52. A non-negative number is its own absolute value, so
\[ \begin{aligned} \sumiN \dualvar_i &= \sumiN |\dualvar_i| \\ &= \norm{\dualvar}_1. \end{aligned} \]
Exercise 53 (Check that the dual objective is the primal objective in disguise (part 4))
Exercise 53 (Check that the dual objective is the primal objective in disguise (part 4)) Use the setup of Exercise 50.
Minimizing that norm is the standard way to make a vector sparse. The dual maximizes it. Should you expect \(\dualvar\) to be sparse or dense?
Solution 53. Dense, on that reasoning. An \(\lpnorm{1}\) penalty sparsifies when it is minimized; here it is being maximized, which pushes the \(\dualvar_i\) up rather than down.
The reasoning is sound and the conclusion is wrong: \(\dualvar\) is sparse, usually very sparse. Theorem 6 says why, and the cause has nothing to do with the \(\lpnorm{1}\) norm. Treat this as a warning about reading an objective’s shape and inferring a property of its solution.
Exercise 54 (Find out why \(\dualvar\) is sparse)
Exercise 54 (Find out why \(\dualvar\) is sparse) Solution 50 predicted a dense \(\dualvar\) and was wrong. The real cause is a condition every solution of a problem like this satisfies, called complementary slackness:
\[\dualvar_i \paren{y_{(i)}\paren{\dprod{w}{x_{(i)}} + b} - 1} = 0, \qquad i = 1, 2, \ldots, N.\]
A product is zero when one of its factors is. Each \(i\) therefore has at most one non-zero factor, and the condition says which combinations are allowed.
Suppose \(\dualvar_i > 0\). What must be true of \(\outvar_{(i)} \modmemf{\predvar_{(i)}}\), and where does that put \(\predvar_{(i)}\)?
Solution 54. If \(\dualvar_i > 0\) then the first factor is non-zero, so the second must vanish:
\[y_{(i)}\paren{\dprod{w}{x_{(i)}} + b} = 1.\]
By the normalization of Theorem 2 that is exactly the condition for sitting on the margin, at distance \(M\) from the hyperplane.
Exercise 55 (Find out why \(\dualvar\) is sparse (part 2))
Exercise 55 (Find out why \(\dualvar\) is sparse (part 2)) Use the setup of Exercise 54.
Suppose \(\predvar_{(i)}\) sits strictly outside the margin, so that \(\outvar_{(i)} \modmemf{\predvar_{(i)}} > 1\). What must \(\dualvar_i\) be?
Solution 55. If \(y_{(i)} \modmemf{x_{(i)}} > 1\) then the second factor is strictly positive, so \(\dualvar_i = 0\).
Exercise 56 (Find out why \(\dualvar\) is sparse (part 3))
Exercise 56 (Find out why \(\dualvar\) is sparse (part 3)) Use the setup of Exercise 54.
Parts 1 and 2 each state an implication. Write down the converse of Exercise 54 and decide whether it follows from complementary slackness.
Solution 56. The converse of Solution 54 is: if \(\predvar_{(i)}\) lies on the margin then \(\dualvar_i > 0\). It does not follow. Complementary slackness only forbids the combination “\(\dualvar_i > 0\) and off the margin”; it permits “\(\dualvar_i = 0\) and on the margin”, since then both factors are zero and the product is zero for two reasons.
Such points exist. They are unusual, and they are the reason the two definitions of a support vector in use are not quite the same: Definition 5 calls a point a support vector when it lies at distance \(M\), and many sources instead call it one when \(\dualvar_i \neq 0\). The second set is contained in the first and can be strictly smaller.
Exercise 57 (Find out why \(\dualvar\) is sparse (part 4))
Exercise 57 (Find out why \(\dualvar\) is sparse (part 4)) Use the setup of Exercise 54.
Most points in a training set sit strictly outside the margin. Combine that with Exercise 55 to explain the sparsity of \(\dualvar\).
Solution 57. Solution 55 gives \(\dualvar_i = 0\) for every point strictly outside the margin. That is almost all of them, so almost all \(\dualvar_i\) are zero and \(\dualvar\) is sparse. The sparsity comes from the constraints being slack, not from the objective’s shape. The \(\lpnorm{1}\) reasoning in Solution 50, correct about \(\lpnorm{1}\) norms, said nothing about this problem.
Exercise 58 (Find out why \(\dualvar\) is sparse (part 5))
Exercise 58 (Find out why \(\dualvar\) is sparse (part 5)) Use the setup of Exercise 54.
Using \(w = \sum_i \dualvar_i \outvar_{(i)} \predvar_{(i)}\), say which training points the fitted hyperplane actually depends on.
Solution 58. Only the points with \(\dualvar_i \neq 0\) contribute a term to the sum, so \(w\) is a combination of those points alone. Every other training example could be deleted and the same \(w\) would result. That is Solution 11’s claim, now proved rather than argued from a picture, and the method is named after it.
Theorem 6 (Only points on the margin carry weight)
Theorem 6 (Only points on the margin carry weight) Suppose \(w\), \(b\) and \(\dualvar\) satisfy complementary slackness [15],
\[\dualvar_i \paren{y_{(i)}\paren{\dprod{w}{x_{(i)}} + b} - 1} = 0, \qquad i = 1, 2, \ldots, N,\]
for a hard-margin training set scaled as in Definition 7, where \(\modmemf{x} = \dprod{w}{x} + b\). If \(\dualvar_i > 0\), then \(y_{(i)} \modmemf{x_{(i)}} = 1\), so \(x_{(i)}\) lies on the margin. Equivalently, \(\dualvar_i = 0\) for every point strictly outside the margin, where \(y_{(i)} \modmemf{x_{(i)}} > 1\).
Proof
Proof. This is the solution to Exercise 54 and Exercise 55.
Exercise 59 (Get \(w\) and \(b\) back out of \(\dualvar\))
Exercise 59 (Get \(w\) and \(b\) back out of \(\dualvar\)) A solver gives you the optimal \(\dualvar\). You still have to classify a new point, which needs \(w\) and \(b\).
Write \(w\) in terms of \(\dualvar\) and the training set.
Solution 59. \[w = \sumiN \dualvar_i \, y_{(i)} \, x_{(i)},\]
which by Theorem 6 is really a sum over the support vectors, the other terms being zero.
Exercise 60 (Get \(w\) and \(b\) back out of \(\dualvar\) (part 2))
Exercise 60 (Get \(w\) and \(b\) back out of \(\dualvar\) (part 2)) Use the setup of Exercise 59.
Take any \(i\) with \(\dualvar_i \neq 0\). Theorem 6 says what \(\outvar_{(i)}\paren{\dprod{w}{\predvar_{(i)}} + b}\) equals. Solve that for \(b\), using \(\outvar_{(i)} \in \{-1, +1\}\).
Solution 60. Complementary slackness gives \(y_{(i)}\paren{\dprod{w}{x_{(i)}} + b} = 1\). Multiply both sides by \(y_{(i)}\). Since \(y_{(i)} \in \{-1, +1\}\) we have \(y_{(i)}^2 = 1\), so the left side simplifies and
\[\dprod{w}{x_{(i)}} + b = y_{(i)}, \qquad\text{that is}\qquad b = y_{(i)} - \dprod{w}{x_{(i)}}.\]
Exercise 61 (Get \(w\) and \(b\) back out of \(\dualvar\) (part 3))
Exercise 61 (Get \(w\) and \(b\) back out of \(\dualvar\) (part 3)) Use the setup of Exercise 59.
Your formula for \(b\) names a particular \(i\). Would a different choice of \(i\) give a different \(b\)?
Solution 61. No. Every \(i\) with \(\dualvar_i \neq 0\) satisfies the same equation, so each returns the same \(b\). In floating-point arithmetic they return nearly the same \(b\), so implementations average over all of them rather than picking one.
Exercise 62 (Get \(w\) and \(b\) back out of \(\dualvar\) (part 4))
Exercise 62 (Get \(w\) and \(b\) back out of \(\dualvar\) (part 4)) Use the setup of Exercise 59.
Is the set of support vectors determined by the training data?
Solution 62. The support vectors need not be. Sitting on the margin is a geometric fact about a point and is determined, but which points carry non-zero \(\dualvar_i\) can fail to be unique when more points lie on the margin than are needed to fix the hyperplane: the surplus weight can be shared among them in more than one way. So two runs of a solver may return different \(\dualvar\) and the same classifier.
Exercise 63 (Get \(w\) and \(b\) back out of \(\dualvar\) (part 5))
Exercise 63 (Get \(w\) and \(b\) back out of \(\dualvar\) (part 5)) Use the setup of Exercise 59.
Are \(w\) and \(b\)?
Solution 63. \(w\) and \(b\) are determined — the primal is a strictly convex problem in \(w\) with a unique solution, and Solution 60 then fixes \(b\).
Proposition 2 (Recovering \(w\) and \(b\) from the dual)
Proposition 2 (Recovering \(w\) and \(b\) from the dual) Let \(\dualvar\) solve the hard-margin dual of Definition 8, and let \((w, b)\) be the corresponding solution of Definition 7. Then
\[w = \sumiN \dualvar_i \, y_{(i)} \, x_{(i)},\]
and, for every \(i\) with \(\dualvar_i \neq 0\),
\[b = y_{(i)} - \dprod{w}{x_{(i)}}.\]
Proof
Proof. This is the solution to Exercise 59. The formula for \(b\) uses Theorem 6.
Example 8 (Recovering \(w\) and \(b\) for the ten cars)
Example 8 (Recovering \(w\) and \(b\) for the ten cars) The solver of Example 3 returns the dual variables \(\dualvar_i\) and the intercept \(b\). Rebuild \(w = \sumiN \dualvar_i y_{(i)} x_{(i)}\) from the dual variables alone, then apply the formula \(b = y_{(i)} - \dprod{w}{x_{(i)}}\) of Proposition 2 at every car with \(\dualvar_i \neq 0\), and compare each result with the solver’s \(b\):
0.0 name b
0 plymouth 'cuda 340 3.411401
1 buick estate wagon (sw) 3.411401
2 fiat 124b 3.4114013.4114010199672364[1] 0[1] 3.411401The weight vector rebuilt from the dual variables matches the solver’s \(w\), with largest difference 0. Every one of the 3 support vectors gives the same \(b\) to six decimals, 3.4114, and it is the solver’s \(b\), so any one of them recovers the intercept.
Watch
Andrew Ng derives the dual problem in the CS229 lecture on kernels, from 26:31 [9], Lecture 7.
Read
GeeksforGeeks explains the dual problem of the SVM [16].
Exercise 64 (Find out what breaks when the classes overlap)
Exercise 64 (Find out what breaks when the classes overlap) Every problem so far assumed the training set is linearly separable. Real data usually is not.
Look at Definition 7 and say precisely what goes wrong when no hyperplane separates the classes. It is not that the answer is bad.
Solution 64. The feasible set is empty. Every point has to satisfy \(y_{(i)}\paren{\dprod{w}{x_{(i)}} + b} \geq 1\), and if no hyperplane gets all of them on the right side then no \((w, b)\) satisfies all \(N\) constraints at once. The problem has no solution to return, good or bad. A solver reports infeasibility rather than a poor classifier.
Exercise 65 (Find out what breaks when the classes overlap (part 2))
Exercise 65 (Find out what breaks when the classes overlap (part 2)) Use the setup of Exercise 64.
A fix has to let a point sit closer to the boundary than the margin, or even on the wrong side, while still costing something. Propose a way to write that into the constraint \(\outvar_{(i)}\paren{\dprod{w}{\predvar_{(i)}} + b} \geq 1\).
Exercise 66 (Find out what breaks when the classes overlap (part 3))
Exercise 66 (Find out what breaks when the classes overlap (part 3)) Use the setup of Exercise 64.
Your fix introduces a new unknown per training point. What should it be when the point is correct and far from the boundary?
Solution 66. Zero. A point at or beyond the margin already satisfies the original constraint, so it needs no allowance, and charging it for one it does not use would be arbitrary.
Exercise 67 (Find out what breaks when the classes overlap (part 4))
Exercise 67 (Find out what breaks when the classes overlap (part 4)) Use the setup of Exercise 64.
What would a negative \(\slack_i\) represent?
Solution 67. A negative \(\slack_i\) would describe a point sitting beyond the margin by \(|\slack_i|\).
Exercise 68 (Find out what breaks when the classes overlap (part 5))
Exercise 68 (Find out what breaks when the classes overlap (part 5)) Use the setup of Exercise 64.
Should \(\slack_i\) be allowed to go negative?
Solution 68. No, and the reason matters more than the rule. Since the objective charges \(\sum_i \slack_i\) and we are minimizing, a negative allowance pays a bonus. The sum would stop measuring how badly the data violate the margin and start measuring how far every point sits from the boundary, so a correctly classified point far from the boundary would go on affecting the solution forever. That is precisely the behaviour Solution 8 removed. Requiring \(\slack_i \geq 0\) keeps the quantity a penalty.
Definition 10 (Slack variable)
Definition 10 (Slack variable) The slack variable \(\slack_i \geq 0\) is the amount by which \(y_{(i)} \modmemf{x_{(i)}}\) is allowed to be smaller than \(1\) [7].
The letter is a lower-case xi, said “zai”, “k-sai” or “k-see” depending on whom you ask.
Example 9 (Slack of the fuel-economy classifier)
Example 9 (Slack of the fuel-economy classifier) Return to the classifier \(\modmem\) of Example 1. Rescale \((w, b)\) so that the two class means sit on the margin hyperplanes, \(\modmem = +1\) and \(\modmem = -1\), then compute the slack \(\slack_i = \maxf{0,\; 1 - y_{(i)} \modmemf{x_{(i)}}}\) that each car needs, and count the cars by how much slack they use:
# The mean of the high-mpg cars has h = (w.w)/2 before rescaling, so this factor makes it exactly +1.
scale_sl = 2 / (w_dr @ w_dr)
w_sl, b_sl = scale_sl * w_dr, scale_sl * b_dr
f_sl = Z_dr @ w_sl + b_sl
xi_sl = np.maximum(0, 1 - y_dr * f_sl) # the smallest slack that satisfies y h >= 1 - slack
print(pd.DataFrame({
"slack": ["xi = 0", "0 < xi <= 1", "xi > 1"],
"cars": [(xi_sl == 0).sum(), ((xi_sl > 0) & (xi_sl <= 1)).sum(), (xi_sl > 1).sum()],
})) slack cars
0 xi = 0 202
1 0 < xi <= 1 137
2 xi > 1 53cadillac eldorado 23.0 2.158013540143878# The mean of the high-mpg cars has h = (w.w)/2 before rescaling, so this factor makes it exactly +1.
scale_sl <- 2 / sum(w_dr^2)
w_sl <- scale_sl * w_dr
b_sl <- scale_sl * b_dr
f_sl <- drop(Z_dr %*% w_sl) + b_sl
xi_sl <- pmax(0, 1 - y_dr * f_sl) # the smallest slack that satisfies y h >= 1 - slack
data.frame(
slack = c("xi = 0", "0 < xi <= 1", "xi > 1"),
cars = c(sum(xi_sl == 0), sum(xi_sl > 0 & xi_sl <= 1), sum(xi_sl > 1))
)[1] "cadillac eldorado" "23" "2.15801354014388" Cars with \(\slack_i = 0\) are on or beyond their own margin hyperplane, and need no slack. The 137 cars with \(0 < \slack_i \leq 1\) are on the correct side of the boundary but inside the margin, and the 53 with \(\slack_i > 1\) are misclassified. The worst offender is the cadillac eldorado, at 23 mpg, with slack 2.16. The total slack is \(\sumiN \slack_i =\) 143.6, the quantity that the soft-margin objective penalizes.
Exercise 69 (Assemble the soft-margin program)
Exercise 69 (Assemble the soft-margin program) Solution 64 has the relaxed constraint and Definition 10 names the new unknown. Turn them into a complete optimization problem.
Write down every constraint the problem now carries, and count them.
Solution 69. Two families, \(N\) constraints each:
\[y_{(i)}\paren{\dprod{w}{x_{(i)}} + b} \geq 1 - \slack_i, \qquad \slack_i \geq 0, \qquad i = 1, 2, \ldots, N,\]
so \(2N\) in all, against the \(N\) of Definition 7.
Exercise 70 (Assemble the soft-margin program (part 2))
Exercise 70 (Assemble the soft-margin program (part 2)) Use the setup of Exercise 69.
The objective has to trade a wide margin against small violations. Write it, introducing a constant \(C\) for the trade-off between the two.
Solution 70. \[\mathop{\argmin}_{w,\,b,\,\slack} \quad \frac{1}{2}\norm{w}_2^2 + C\sumiN \slack_i.\]
The first term is the one Solution 20 arrived at, and minimizing it widens the margin. The second counts the violations. \(C > 0\) says how many units of \(\frac{1}{2}\norm{w}_2^2\) one unit of violation is worth.
Exercise 71 (Assemble the soft-margin program (part 3))
Exercise 71 (Assemble the soft-margin program (part 3)) Use the setup of Exercise 69.
Suppose we treated \(C\) as one more unknown and let the solver minimize over it as well. What value would it choose, and what classifier would come back?
Solution 71. It would choose \(C = 0\). Whenever \(\sum_i \slack_i > 0\) the objective is strictly increasing in \(C\), so a solver free to pick \(C\) drives it to the smallest value the constraints allow. At \(C = 0\) the violations cost nothing, so each \(\slack_i\) can grow until its constraint is satisfied no matter what \((w, b)\) is, and the objective is then minimized by \(w = 0\) — a classifier with no decision boundary at all.
So \(C\) cannot be fitted on the training data. It is a hyperparameter, fixed before the fit and chosen by comparing held-out performance across candidate values.
Exercise 72 (Assemble the soft-margin program (part 4))
Exercise 72 (Assemble the soft-margin program (part 4)) Use the setup of Exercise 69.
How many unknowns does the problem have now, and is it still a convex problem?
Solution 72. \(\ninputvars + 1 + N\): the \(\ninputvars\) entries of \(w\), the intercept \(b\), and one \(\slack_i\) per training point.
It is still convex. The objective is a convex quadratic in \(w\) plus a linear function of \(\slack\), and every constraint is affine. It is strictly convex in \(w\) but not in \(b\) or \(\slack\), so \(w\) is unique and the rest need not be — the same situation as Solution 59 describes for the hard margin.
Definition 11 (C-SVM primal problem)
Definition 11 (C-SVM primal problem) The C-SVM primal problem, for a constant \(C > 0\), is
\[\begin{aligned} \mathop{\argmin}_{w,\,b,\,\slack} \quad & \frac{1}{2}\norm{w}_2^2 + C\sumiN \slack_i \\ \text{s.t.} \quad & y_{(i)}\paren{\dprod{w}{x_{(i)}} + b} \geq 1 - \slack_i, \quad i = 1, 2, \ldots, N \\ & \slack_i \geq 0, \quad i = 1, 2, \ldots, N. \end{aligned}\]
Unlike Definition 7 it is feasible for every training set, separable or not.
Example 10 (Evaluating the C-SVM primal objective)
Example 10 (Evaluating the C-SVM primal objective) Each choice of \(C\) gives a different Definition 11 on the fuel-economy data of Example 1. Minimize it for \(C = 0.1\) and \(C = 1\) with the dual_svm helper of Example 3, which finds the same hyperplane through the dual problem, and evaluate the objective at the result. Compare with its value at the rescaled class-mean classifier of Example 9, which is feasible with its slacks \(\slack_i\):
K_cp = Z_dr @ Z_dr.T
rows_cp = []
for C_cp in (0.1, 1.0):
alpha_cp, b_cp = dual_svm(K_cp, y_dr, C_cp, tol=1e-8)
w_cp = (alpha_cp * y_dr) @ Z_dr
xi_cp = np.maximum(0, 1 - y_dr * (Z_dr @ w_cp + b_cp)) # optimal slack for this (w, b)
rows_cp.append([C_cp, 0.5 * w_cp @ w_cp, C_cp * xi_cp.sum(),
0.5 * w_cp @ w_cp + C_cp * xi_cp.sum(),
0.5 * w_sl @ w_sl + C_cp * xi_sl.sum(), int((xi_cp > 1e-6).sum())])
print(pd.DataFrame(rows_cp, columns=["C", "margin_term", "slack_term", "objective",
"objective_class_means", "cars_with_slack"]).round(3)) C margin_term ... objective_class_means cars_with_slack
0 0.1 1.377 ... 14.851 144
1 1.0 2.543 ... 144.081 117
[2 rows x 6 columns]K_cp <- Z_dr %*% t(Z_dr)
rows_cp <- t(sapply(c(0.1, 1), function(C_cp) {
fit_cp <- dual_svm(K_cp, y_dr, C_cp, tol=1e-8)
w_cp <- drop((fit_cp$alpha * y_dr) %*% Z_dr)
xi_cp <- pmax(0, 1 - y_dr * (drop(Z_dr %*% w_cp) + fit_cp$b)) # optimal slack for this (w, b)
c(C = C_cp, margin_term = 0.5 * sum(w_cp^2), slack_term = C_cp * sum(xi_cp),
objective = 0.5 * sum(w_cp^2) + C_cp * sum(xi_cp),
objective_class_means = 0.5 * sum(w_sl^2) + C_cp * sum(xi_sl),
cars_with_slack = sum(xi_cp > 1e-6))
}))
round(rows_cp, 3) C margin_term slack_term objective objective_class_means cars_with_slack
[1,] 0.1 1.377 11.853 13.231 14.851 144
[2,] 1.0 2.543 114.005 116.547 144.081 117The objective has two terms: \(\frac{1}{2}\norm{w}_2^2\) rewards a wide margin and \(C\sumiN \slack_i\) charges for violations. At \(C = 0.1\) the minimizer has objective 13.2, against 14.9 for the class-mean classifier; at \(C = 1\) it is 116.5 against 144.1. Raising \(C\) from 0.1 to 1 changes the number of cars with positive slack from 144 to 117, because the slack term is now weighted ten times as heavily.
Exercise 73 (Work out what \(C\) controls)
Exercise 73 (Work out what \(C\) controls) \(C\) is the only parameter Definition 11 adds. Find out what changing it does.
Which value of \(C\) recovers Definition 7: \(0\), \(-\infty\), or \(\infty\)?
Solution 73. \(C \to \infty\), read as a limit rather than as a value.
Exercise 74 (Work out what \(C\) controls (part 2))
Exercise 74 (Work out what \(C\) controls (part 2)) Use the setup of Exercise 73.
Say what happens to the \(\slack_i\) at that value.
Solution 74. Every unit of violation then costs without limit, so the minimizer sets \(\slack_i = 0\) for every \(i\) whenever that is feasible, and the constraints collapse back to \(y_{(i)}\paren{\dprod{w}{x_{(i)}} + b} \geq 1\). At \(C = \infty\) the objective is undefined as soon as any \(\slack_i > 0\), and on a training set that is not separable no finite \(C\) ever forces \(\slack = 0\) — the violations shrink as \(C\) grows but never reach zero.
Exercise 75 (Work out what \(C\) controls (part 3))
Exercise 75 (Work out what \(C\) controls (part 3)) Use the setup of Exercise 73.
Take the two values you rejected in Exercise 73 in turn and say what goes wrong with each.
Solution 75. At \(C = 0\) the violations are free. Each \(\slack_i\) can grow until its constraint holds regardless of \((w, b)\), so nothing stops \(w = 0\), which is Solution 69’s classifier with no boundary.
At \(C = -\infty\), and indeed at any \(C < 0\), the objective rewards violations. Sending a single \(\slack_i \to \infty\) sends the objective to \(-\infty\), so the problem has no minimum at all. This is Solution 64’s penalty-into-bonus reversal arising through the cost \(C\) rather than through the sign of \(\slack_i\).
Exercise 76 (Work out what \(C\) controls (part 4))
Exercise 76 (Work out what \(C\) controls (part 4)) Use the setup of Exercise 73.
Is \(C\) positively correlated with the margin, negatively correlated, or neither? Argue from which of the two terms in the objective dominates.
Solution 76. Negatively correlated. A large \(C\) makes the violation term dominate, so the solver accepts a large \(\frac{1}{2}\norm{w}_2^2\) to avoid violations: \(\norm{w}_2\) grows and the margin \(M = 1/\norm{w}_2\) shrinks. A small \(C\) makes the margin term dominate, so the solver widens the margin and accepts the violations that come with it.
Exercise 77 (Work out what \(C\) controls (part 5))
Exercise 77 (Work out what \(C\) controls (part 5)) Use the setup of Exercise 73.
Exercise 75 makes \(C\) sound like a scale between two extremes. Name the two failure modes at the ends of that scale, in the vocabulary of A First Model and Generalization.
Solution 77. Large \(C\) overfits and small \(C\) underfits. A large \(C\) gives a narrow margin twisted to get the training points right, including the mislabelled ones, which is high variance. A small \(C\) gives a wide margin that ignores much of the data, which is high bias. Choosing \(C\) is choosing a point on the bias-variance trade-off, so it is settled on held-out data rather than on the training set.
Exercise 78 (Prove that the margin shrinks as \(C\) grows)
Exercise 78 (Prove that the margin shrinks as \(C\) grows) Solution 74 argued from which term dominates. The claim can be proved outright, with no calculus and no differentiation of the solution.
Choose a training set and write \(S = \sumiN \slack_i\) for the total violation. Take two values \(0 < C_1 < C_2\) of the penalty weight \(C\) and let \((w_1, b_1, \slack_1)\) and \((w_2, b_2, \slack_2)\) solve Definition 11 at \(C_1\) and \(C_2\), with totals \(S_1\) and \(S_2\).
Each solution is optimal at its own value of \(C\), so it scores at least as well there as the other solution does. Write these two facts as inequalities.
Solution 78. The point \((w_2, b_2, \slack_2)\) is feasible for the problem at \(C_1\), and \((w_1, b_1, \slack_1)\) is optimal there, so
\[\frac{1}{2}\norm{w_1}_2^2 + C_1 S_1 \;\leq\; \frac{1}{2}\norm{w_2}_2^2 + C_1 S_2.\]
Swapping the roles gives
\[\frac{1}{2}\norm{w_2}_2^2 + C_2 S_2 \;\leq\; \frac{1}{2}\norm{w_1}_2^2 + C_2 S_1.\]
The feasible set does not depend on \(C\), so each solution can be tested at the other’s value of \(C\).
Exercise 79 (Prove that the margin shrinks as \(C\) grows (part 2))
Exercise 79 (Prove that the margin shrinks as \(C\) grows (part 2)) Use the setup of Exercise 78.
Add them and cancel. Deduce the sign of \((C_2 - C_1)(S_2 - S_1)\), and state how the total violation changes with \(C\).
Solution 79. Adding the two and cancelling \(\frac{1}{2}\norm{w_1}_2^2 + \frac{1}{2}\norm{w_2}_2^2\) from both sides:
\[C_1 S_1 + C_2 S_2 \;\leq\; C_1 S_2 + C_2 S_1,\]
that is \((C_2 - C_1)(S_2 - S_1) \leq 0\). Since \(C_2 > C_1\) the first factor is positive, so \(S_2 \leq S_1\): the total violation never increases as \(C\) increases.
Exercise 80 (Prove that the margin shrinks as \(C\) grows (part 3))
Exercise 80 (Prove that the margin shrinks as \(C\) grows (part 3)) Use the setup of Exercise 78.
Put Exercise 79 back into the first inequality of Exercise 78 to compare \(\norm{w_1}_2\) with \(\norm{w_2}_2\).
Solution 80. From Solution 79, \(S_2 - S_1 \leq 0\), and \(C_1 > 0\), so \(C_1(S_2 - S_1) \leq 0\). The first inequality of Solution 78 rearranges to
\[\frac{1}{2}\norm{w_1}_2^2 \;\leq\; \frac{1}{2}\norm{w_2}_2^2 + C_1(S_2 - S_1) \;\leq\; \frac{1}{2}\norm{w_2}_2^2,\]
so \(\norm{w_1}_2 \leq\norm{w_2}_2\).
Exercise 81 (Prove that the margin shrinks as \(C\) grows (part 4))
Exercise 81 (Prove that the margin shrinks as \(C\) grows (part 4)) Use the setup of Exercise 78.
State what Exercise 79 and Exercise 80 together say about the margin, and say which word in Solution 76 they justify and which they do not.
Solution 81. \(\norm{w}_2\) never decreases as \(C\) increases, so the margin \(M = 1/\norm{w}_2\) never increases: raising \(C\) gives a narrower margin and less total violation, exactly the trade Solution 74 described.
What is justified is the direction. What is not is the word “correlated”, which suggests a strict relationship: these are non-strict inequalities, so a range of \(C\) values can share one solution and leave the margin unchanged. Monotone is the accurate word.
Lemma 1 (The total violation never increases with \(C\))
Lemma 1 (The total violation never increases with \(C\)) Choose a training set, and take two values \(0 < C_1 < C_2\) of the penalty weight \(C\). Let \((w_1, b_1, \slack_1)\) and \((w_2, b_2, \slack_2)\) solve Definition 11 at \(C_1\) and \(C_2\), with total violations \(S_1 = \sumiN \slack_{1,i}\) and \(S_2 = \sumiN \slack_{2,i}\). Then \(S_2 \leq S_1\).
Proof
Proof. This is the solution to Exercise 78 and Exercise 79.
Example 11 (The total violation of the fuel-economy classifier as \(C\) grows)
Example 11 (The total violation of the fuel-economy classifier as \(C\) grows) Fit Definition 11 on the fuel-economy data of Example 1 at three values of \(C\) with the dual_svm helper, as in Example 10, and compute the total violation \(S = \sumiN \slack_i\) of each fit:
K_vm = Z_dr @ Z_dr.T
rows_vm = []
for C_vm in (0.01, 0.1, 1.0):
alpha_vm, b_vm = dual_svm(K_vm, y_dr, C_vm, tol=1e-8)
w_vm = (alpha_vm * y_dr) @ Z_dr
S_vm = np.maximum(0, 1 - y_dr * (Z_dr @ w_vm + b_vm)).sum() # total violation at the optimal slack
rows_vm.append([C_vm, S_vm, np.linalg.norm(w_vm)])
print(pd.DataFrame(rows_vm, columns=["C", "total_violation", "norm_w"]).round(3)) C total_violation norm_w
0 0.01 150.942 0.842
1 0.10 118.533 1.660
2 1.00 114.005 2.255K_vm <- Z_dr %*% t(Z_dr)
rows_vm <- t(sapply(c(0.01, 0.1, 1), function(C_vm) {
fit_vm <- dual_svm(K_vm, y_dr, C_vm, tol = 1e-8)
w_vm <- drop((fit_vm$alpha * y_dr) %*% Z_dr)
S_vm <- sum(pmax(0, 1 - y_dr * (drop(Z_dr %*% w_vm) + fit_vm$b))) # total violation at the optimal slack
c(C = C_vm, total_violation = S_vm, norm_w = sqrt(sum(w_vm^2)))
}))
round(rows_vm, 3) C total_violation norm_w
[1,] 0.01 150.942 0.842
[2,] 0.10 118.533 1.660
[3,] 1.00 114.005 2.255The total violation falls from 150.94 at \(C = 0.01\) to 118.53 at \(C = 0.1\) and 114.00 at \(C = 1\), so it never increases as \(C\) increases, as Lemma 1 says.
Proof
Proof. This is the solution to Exercise 80 and Exercise 81.
Exercise 82 (Predict the soft-margin dual)
Exercise 82 (Predict the soft-margin dual) Definition 8 has three ingredients: an objective, a sign constraint on each \(\dualvar_i\), and one equality constraint. Definition 11 changed the primal in one way only, by letting each point use an allowance of slack at cost \(C\) per unit.
Which of the three ingredients do you expect to change?
Solution 82. Only the sign constraint. The objective and the equality constraint \(\sum_i \dualvar_i y_{(i)} = 0\) come through unchanged, which is worth noticing: the soft margin adds one bound and nothing else.
Exercise 83 (Predict the soft-margin dual (part 2))
Exercise 83 (Predict the soft-margin dual (part 2)) Use the setup of Exercise 82.
The change is a second bound on each \(\dualvar_i\). Write the constraint you expect, and say which number bounds it.
Solution 83. \[0 \leq \dualvar_i \leq C, \qquad i = 1, 2, \ldots, N.\]
The cost \(C\) is the bound. It is the same constant, doing the same job seen from the other side: in the primal it is the cost of a unit of violation, and in the dual it is the most any one point may pay.
A constraint of this shape, holding a variable between two constants, is called a box constraint.
Exercise 84 (Predict the soft-margin dual (part 3))
Exercise 84 (Predict the soft-margin dual (part 3)) Use the setup of Exercise 82.
Your constraint caps how large any single \(\dualvar_i\) can be. Given \(w = \sum_i \dualvar_i \outvar_{(i)} \predvar_{(i)}\), say what that cap stops one badly placed training point from doing.
Solution 84. It stops that point from dominating \(w\). In Definition 8 nothing bounds \(\dualvar_i\) above, so a single point in the wrong place can carry an arbitrarily large weight and pull the hyperplane toward it. Capping every \(\dualvar_i\) at \(C\) bounds one point’s contribution to \(w\) by \(C\norm{x_{(i)}}_2\), so a mislabelled example can move the solution only so far.
That is the robustness the soft margin gives, and the dual is where it is visible as a single inequality.
Exercise 85 (Predict the soft-margin dual (part 4))
Exercise 85 (Predict the soft-margin dual (part 4)) Use the setup of Exercise 82.
Check Exercise 83 against Exercise 73: what does your constraint become as \(C \to \infty\)?
Solution 85. The upper bound disappears and \(0 \leq \dualvar_i \leq C\) becomes \(\dualvar_i \geq 0\), which is Definition 8. The two problems agree in the limit in the dual exactly as they do in the primal.
Definition 12 (C-SVM dual problem)
Definition 12 (C-SVM dual problem) The C-SVM dual problem, for a constant \(C > 0\), is
\[\begin{aligned} \mathop{\argmax}_{\dualvar \in \reals^N} \quad & \sumiN \dualvar_i - \frac{1}{2}\sumiN\sumto{j}{N} \dualvar_i \dualvar_j \, y_{(i)} y_{(j)} \, \dprod{x_{(i)}}{x_{(j)}} \\ \text{s.t.} \quad & 0 \leq \dualvar_i \leq C, \quad i = 1, 2, \ldots, N \\ & \sumiN \dualvar_i \, y_{(i)} = 0, \end{aligned}\]
whose solution determines the same hyperplane as Definition 11.
Example 12 (Solving the C-SVM dual: American versus other cars)
Example 12 (Solving the C-SVM dual: American versus other cars) In the Auto data [5], label a car \(+1\) if its origin is 1 (American) and \(-1\) otherwise, and use the standardized weight and horsepower of Example 1 as inputs. Maximize Definition 12 with the dual_svm helper of Example 3 for \(C = 0.1\) and \(C = 1\). Check the constraints, sort the dual variables into \(\dualvar_i = 0\), \(0 < \dualvar_i < C\) and \(\dualvar_i = C\), and compare the dual objective with the primal objective of Definition 11 at the \(w\) and slacks that the dual variables imply:
y_cd = np.where(auto_dr["origin"] == 1, 1.0, -1.0)
rows_cd = []
for C_cd in (0.1, 1.0):
alpha_cd, b_cd = dual_svm(K_cp, y_cd, C_cd, tol=1e-8)
w_cd = (alpha_cd * y_cd) @ Z_dr # w from the dual variables
xi_cd = np.maximum(0, 1 - y_cd * (Z_dr @ w_cd + b_cd)) # optimal slack for this (w, b)
at_zero, at_C = alpha_cd < 1e-7, alpha_cd > C_cd - 1e-7
rows_cd.append([C_cd, alpha_cd.sum() - 0.5 * (alpha_cd * y_cd) @ K_cp @ (alpha_cd * y_cd),
0.5 * w_cd @ w_cd + C_cd * xi_cd.sum(), abs((alpha_cd * y_cd).sum()),
at_zero.sum(), (~at_zero & ~at_C).sum(), at_C.sum()])
print(pd.DataFrame(rows_cd, columns=["C", "dual_objective", "primal_objective", "abs_sum_alpha_y",
"alpha_0", "alpha_between", "alpha_C"])) C dual_objective primal_objective ... alpha_0 alpha_between alpha_C
0 0.1 19.952291 19.952291 ... 181 3 208
1 1.0 187.594365 187.594365 ... 201 3 188
[2 rows x 7 columns]y_cd <- ifelse(auto_dr$origin == 1, 1, -1)
rows_cd <- t(sapply(c(0.1, 1), function(C_cd) {
fit_cd <- dual_svm(K_cp, y_cd, C_cd, tol=1e-8)
ay_cd <- fit_cd$alpha * y_cd
w_cd <- drop(ay_cd %*% Z_dr) # w from the dual variables
xi_cd <- pmax(0, 1 - y_cd * (drop(Z_dr %*% w_cd) + fit_cd$b)) # optimal slack for this (w, b)
at_zero <- fit_cd$alpha < 1e-7
at_C <- fit_cd$alpha > C_cd - 1e-7
c(C = C_cd, dual_objective = sum(fit_cd$alpha) - 0.5 * drop(t(ay_cd) %*% K_cp %*% ay_cd),
primal_objective = 0.5 * sum(w_cd^2) + C_cd * sum(xi_cd), abs_sum_alpha_y = abs(sum(ay_cd)),
alpha_0 = sum(at_zero), alpha_between = sum(!at_zero & !at_C), alpha_C = sum(at_C))
}))
rows_cd C dual_objective primal_objective abs_sum_alpha_y alpha_0 alpha_between
[1,] 0.1 19.95229 19.95229 1.179612e-16 181 3
[2,] 1.0 187.59436 187.59436 1.110223e-16 201 3
alpha_C
[1,] 208
[2,] 188The constraint \(\sumiN \dualvar_i y_{(i)} = 0\) holds up to rounding, at most 1e-16 in absolute value, and the box constraint \(0 \leq \dualvar_i \leq C\) holds by construction. At \(C = 1\) the dual objective is 187.59 and the primal objective is 187.59: the two problems have the same optimal value, as Definition 12 states. Of the 392 cars, 201 have \(\dualvar_i = 0\) at \(C = 1\), and so play no part in \(w\); 3 lie strictly between 0 and \(C\), on the margin, and 188 are at the cap \(C\), inside the margin or misclassified. Raising \(C\) from 0.1 to 1 raises the cap on each \(\dualvar_i\) and lowers the number of cars at it from 208 to 188.
Exercise 86 (Sort the training points by their \(\dualvar_i\))
Exercise 86 (Sort the training points by their \(\dualvar_i\)) Theorem 6 sorted the hard-margin training points into two kinds using one complementary-slackness condition. The soft-margin problem has two conditions, one per family of constraints in Definition 11:
\[\dualvar_i \paren{y_{(i)} \modmemf{x_{(i)}} - 1 + \slack_i} = 0, \qquad \paren{C - \dualvar_i} \slack_i = 0.\]
The box constraint \(0 \leq \dualvar_i \leq C\) leaves three cases. Take each in turn and say what the two conditions force, and where the point sits.
\(\dualvar_i = 0\).
Solution 86. \(\dualvar_i = 0\). The second condition has \(C - \dualvar_i = C \neq 0\), so \(\slack_i = 0\); the first holds whatever the bracket is. With no slack, the original constraint \(y_{(i)} \modmemf{x_{(i)}} \geq 1\) applies, so the point sits on or outside the margin. It contributes no term to \(w = \sum_i \dualvar_i y_{(i)} x_{(i)}\) and could be deleted without changing the fit. These are the non-support vectors, and they are the majority.
Exercise 87 (Sort the training points by their \(\dualvar_i\) (part 2))
Exercise 87 (Sort the training points by their \(\dualvar_i\) (part 2)) Use the setup of Exercise 86.
\(0 < \dualvar_i < C\).
Solution 87. \(0 < \dualvar_i < C\). Both factors outside the brackets are non-zero, so both brackets must vanish: \(\slack_i = 0\) from the second, and then \(y_{(i)} \modmemf{x_{(i)}} = 1\) from the first. The point sits exactly on the margin, unviolated, and carries weight. These are the margin support vectors.
Exercise 88 (Sort the training points by their \(\dualvar_i\) (part 3))
Exercise 88 (Sort the training points by their \(\dualvar_i\) (part 3)) Use the setup of Exercise 86.
\(\dualvar_i = C\). This case does not fix \(\slack_i\); say what values it allows and what each of them means, including the boundary between a point that is still classified correctly and one that is not.
Solution 88. \(\dualvar_i = C\). The second condition reads \(0 \cdot \slack_i = 0\) and so says nothing; \(\slack_i\) is free to be any non-negative number. The first gives \(y_{(i)} \modmemf{x_{(i)}} = 1 - \slack_i\).
\(\slack_i = 1\) is therefore the boundary between a violation that is merely inside the margin and one that is an error. The points with \(\slack_i > 0\) are the non-margin support vectors.
The vocabulary is worth stating carefully: the three names partition by \(\dualvar_i\), so a point with \(\dualvar_i = C\) and \(\slack_i = 0\) lies on the margin while being a non-margin support vector by name. It is a boundary case rather than a contradiction, and it is the soft-margin version of the mismatch Solution 54 found between the two definitions of a support vector.
Exercise 89 (Sort the training points by their \(\dualvar_i\) (part 4))
Exercise 89 (Sort the training points by their \(\dualvar_i\) (part 4)) Use the setup of Exercise 86.
Proposition 2 found \(b\) from a single training point. Which of your three kinds can still be used for that, and why do the other two fail?
Solution 89. Only the margin support vectors of case 2. Proposition 2 gives \(b = y_{(i)} - \dprod{w}{x_{(i)}}\), which solves \(y_{(i)} \modmemf{x_{(i)}} = 1\) for \(b\), and case 2 is the only one that supplies that equation. Case 3 gives \(y_{(i)} \modmemf{x_{(i)}} = 1 - \slack_i\), one equation in the two unknowns \(b\) and \(\slack_i\), and \(\slack_i\) is not known until \(b\) is. Case 1 gives an inequality, which fixes nothing.
Both kinds of support vector contribute to \(w\); only one kind can give \(b\).
Exercise 90 (Sort the training points by their \(\dualvar_i\) (part 5))
Exercise 90 (Sort the training points by their \(\dualvar_i\) (part 5)) Use the setup of Exercise 86.
Read \(\dualvar_i\) as how hard \(\predvar_{(i)}\) is pushing on the decision boundary, and describe each of the three kinds in those terms.
Solution 90. \(\dualvar_i\) is the force \(\predvar_{(i)}\) exerts on the boundary, capped at \(C\).
Exercise 91 (Measure the slack of one point that violates the margin)
Exercise 91 (Measure the slack of one point that violates the margin) Work in one dimension again, as Exercise 13 did, and under the scale Theorem 2 fixed. Take \(\modmemf{x} = 2x - 6\), so that \(w = 2\) and \(b = -6\).
Where is the hyperplane, and where are the two margin boundaries, the places where \(\modmemf{\predvar} = 1\) and \(\modmemf{\predvar} = -1\)?
Solution 91. The hyperplane is the root of \(\modmem\), at \(x = 3\). The margin boundaries are at \(\modmemf{x} = 1\), so \(x = 3.5\), and at \(\modmemf{x} = -1\), so \(x = 2.5\).
Exercise 92 (Measure the slack of one point that violates the margin (part 2))
Exercise 92 (Measure the slack of one point that violates the margin (part 2)) Use the setup of Exercise 91.
What is the margin \(M\)?
Solution 92. By Theorem 2,
\[ \begin{aligned} M &= 1/|w| \\ &= 1/2, \end{aligned} \]
which is the distance from \(x = 3\) to either boundary.
Exercise 93 (Measure the slack of one point that violates the margin (part 3))
Exercise 93 (Measure the slack of one point that violates the margin (part 3)) Use the setup of Exercise 91.
A training point with \(\outvar = +1\) sits at \(\predvar = 3.4\). Find the smallest \(\slack\) that satisfies its constraint in Definition 11.
Solution 93. \[ \begin{aligned} \modmemf{3.4} &= 2(3.4) - 6 \\ &= 0.8, \end{aligned} \]
and \(y = +1\), so \(y \, \modmemf{x} = 0.8\). The constraint \(y \, \modmemf{x} \geq 1 - \slack\) needs \(\slack \geq 0.2\), so the smallest admissible slack is \(\slack = 0.2\).
Exercise 94 (Measure the slack of one point that violates the margin (part 4))
Exercise 94 (Measure the slack of one point that violates the margin (part 4)) Use the setup of Exercise 91.
Is the point classified correctly?
Solution 94. The point is classified correctly: \(\modmemf{3.4} = 0.8 > 0\) puts it on the positive side. It has merely moved inside the margin.
Exercise 95 (Measure the slack of one point that violates the margin (part 5))
Exercise 95 (Measure the slack of one point that violates the margin (part 5)) Use the setup of Exercise 91.
Do the same for a point with \(\outvar = +1\) at \(\predvar = 2.8\).
Solution 95. \(\modmemf{2.8} = -0.4\), so \(\outvar \, \modmemf{\predvar} = -0.4\) and \(\slack = 1.4\). This point is on the negative side of the hyperplane and carries a positive label, so it is misclassified.
Exercise 96 (Measure the slack of one point that violates the margin (part 6))
Exercise 96 (Measure the slack of one point that violates the margin (part 6)) Use the setup of Exercise 91.
In each of Exercise 92 and Exercise 93, measure the distance along the line from the point to the margin boundary it should have reached. Compare each distance with the slack you found, and state the relationship between the two.
Solution 96. In Solution 92 the point should have reached \(\predvar = 3.5\) and stopped at \(x = 3.4\), a shortfall of \(0.1\), against a slack of \(0.2\). In Solution 93 the shortfall is \(3.5 - 2.8 = 0.7\), against a slack of \(1.4\). Both times the slack is the shortfall divided by \(M = 1/2\):
\[\slack_i = \frac{\text{distance short of the margin boundary}}{M}.\]
Equivalently \(\slack_i = |w| \times \text{shortfall}\), which is the same statement because Theorem 2 makes \(M\) and \(|w|\) reciprocal.
Exercise 97 (Measure the slack of one point that violates the margin (part 7))
Exercise 97 (Measure the slack of one point that violates the margin (part 7)) Use the setup of Exercise 91.
Your answer to Exercise 94 says what a slack variable is measured in. Use it to explain why \(\slack_i = 1\) is the value Solution 86 treats as special.
Solution 97. A slack variable is a distance measured in margins rather than in the units of \(x\). So \(\slack_i = 1\) says that the point falls exactly one margin short of its margin boundary — and one margin back from the margin boundary is the hyperplane itself. So \(\slack_i = 1\) separates a point still on the right side from a misclassified one, and the threshold is \(1\) for every dataset and every scaling of the features.
The \(\svfrac\)-SVM, and why we might use \(\svfrac\) instead of \(C\)
\(C\) has one practical drawback: its useful range depends on the data. It is a cost in units of \(\frac{1}{2}\norm{w}_2^2\) per unit of violation, so a rescaling of the features moves the range of sensible values, and there is no interval you can search that is right for every problem.
The \(\svfrac\)-SVM replaces \(C\) with a parameter \(\svfrac \in [0, 1]\) that has a direct meaning for the training set. At the optimum, \(\svfrac\) is
So \(\svfrac = 0.1\) asks for at most 10% of the training points inside the margin and guarantees at least 10% of them are support vectors. The margin widens as \(\svfrac\) grows, which is the opposite direction from \(C\).
The two formulations fit the same family of classifiers; \(\svfrac\) only changes which one you ask for and how you ask. The reason to know both is that software offers both, and a value of \(\svfrac\) transfers between datasets in a way a value of \(C\) does not.
Watch
Read
GeeksforGeeks explains hard and soft margins [18].
Exercise 98 (Solve for the slack)
Exercise 98 (Solve for the slack) The C-SVM primal problem of Definition 11 is a constrained problem, which looks like it needs a quadratic-programming solver.
Choose values of the weights \(w\) and the intercept \(b\). Which value of \(\slack_i\) satisfies both constraints on it and makes the objective as small as possible?
Solution 98. Both constraints bound \(\slack_i\) from below: the first by \(1 - y_{(i)}\paren{\dprod{w}{x_{(i)}} + b}\), and the second by \(0\). The objective grows with \(\slack_i\), since \(C > 0\), so the best choice is the larger of the two bounds:
\[\slack_i = \maxf{0,\; 1 - y_{(i)}\paren{\dprod{w}{x_{(i)}} + b}}\]
Exercise 99 (Remove the slack from the problem)
Exercise 99 (Remove the slack from the problem) Make the assumptions of Exercise 98, and use the value of \(\slack_i\) found there. Substitute that value back, and write the primal problem as an unconstrained problem in \(w\) and \(b\) alone.
Solution 99. Substituting it for each \(\slack_i\) leaves
\[\mathop{\argmin}_{w,\,b}\; \frac{1}{2}\norm{w}_2^2 + C\sumiN \maxf{0,\; 1 - y_{(i)}\paren{\dprod{w}{x_{(i)}} + b}}\]
with no constraints left.
Exercise 100 (Does the problem still need a quadratic-programming solver?)
Exercise 100 (Does the problem still need a quadratic-programming solver?) Make the assumptions of Exercise 98, and consider the unconstrained problem of Exercise 99. Does it still need a quadratic-programming solver?
Solution 100. No. An unconstrained convex objective can be minimized by (sub)gradient descent (Gradient Descent), which is how the svm_subgradient function fits it.
Proposition 3 (The optimal slack is the hinge loss)
Proposition 3 (The optimal slack is the hinge loss) Choose values of the weights \(w\) and the intercept \(b\) in Definition 11. The slack that satisfies both of its constraints and minimizes the objective is
\[\slack_i = \maxf{0,\; 1 - y_{(i)}\paren{\dprod{w}{x_{(i)}} + b}}.\]
Substituting it, the C-SVM primal problem is the unconstrained problem
\[\mathop{\argmin}_{w,\,b}\; \frac{1}{2}\norm{w}_2^2 + C\sumiN \maxf{0,\; 1 - y_{(i)}\paren{\dprod{w}{x_{(i)}} + b}}.\]
Proof
Proof. This is the solution to Exercise 98 and Exercise 99.
Example 13 (The optimal slack of the class-mean classifier)
Example 13 (The optimal slack of the class-mean classifier) Take the rescaled class-mean classifier \((w, b)\) of Example 9 and \(C = 1\). Evaluate the objective of Definition 11 twice: once with the slack \(\slack_i = \maxf{0,\; 1 - y_{(i)} \modmemf{x_{(i)}}}\) of Proposition 3, and once with every slack increased by \(0.1\), which still satisfies both constraints. Then evaluate the unconstrained objective of Proposition 3:
C_os = 1.0
margin_os = 0.5 * w_sl @ w_sl
obj_opt_os = margin_os + C_os * xi_sl.sum() # objective at the optimal slack
obj_pad_os = margin_os + C_os * (xi_sl + 0.1).sum() # a feasible but larger slack
obj_unc_os = margin_os + C_os * np.maximum(0, 1 - y_dr * (Z_dr @ w_sl + b_sl)).sum()
print(obj_opt_os, obj_pad_os, obj_unc_os)144.08114431320323 183.2811443132032 144.08114431320323C_os <- 1
margin_os <- 0.5 * sum(w_sl^2)
obj_opt_os <- margin_os + C_os * sum(xi_sl) # objective at the optimal slack
obj_pad_os <- margin_os + C_os * sum(xi_sl + 0.1) # a feasible but larger slack
obj_unc_os <- margin_os + C_os * sum(pmax(0, 1 - y_dr * (drop(Z_dr %*% w_sl) + b_sl)))
c(obj_opt_os, obj_pad_os, obj_unc_os)[1] 144.0811 183.2811 144.0811The optimal slack gives objective 144.08. Adding \(0.1\) to each of the 392 slacks raises it to 183.28, so any larger slack is worse, and the unconstrained objective, 144.08, equals the constrained one at the optimal slack.
Definition 13 (Hinge loss)
Definition 13 (Hinge loss) The hinge loss of a classifier \(\modmem\) at a training point \((x_{(i)}, y_{(i)})\), with \(y_{(i)} \in \{-1, +1\}\), is
\[\maxf{0,\; 1 - y_{(i)} \modmemf{x_{(i)}}}.\]
It is \(0\) for a point on the correct side of the margin, and grows linearly as the point moves past it [19]. It is the optimal slack \(\slack_i\) of Proposition 3, and logistic regression compared it with the logistic loss in an earlier exercise.
Example 14 (Hinge loss on three cars)
Example 14 (Hinge loss on three cars) For the rescaled classifier \(\modmem\) of Example 9, compute the hinge loss \(\maxf{0,\; 1 - y_{(i)} \modmemf{x_{(i)}}}\) and the misclassification loss (1 if \(y_{(i)} \modmemf{x_{(i)}} < 0\), else 0) of the first car in each of three groups: beyond its margin, inside its margin on the correct side, and misclassified. Then average each loss over all cars:
yh_hl = y_dr * f_sl # y h(x): positive when correct, at least 1 beyond the margin
hinge_hl = np.maximum(0, 1 - yh_hl)
zero_one_hl = (yh_hl < 0).astype(float)
first_hl = [np.flatnonzero(yh_hl >= 1)[0], np.flatnonzero((yh_hl >= 0) & (yh_hl < 1))[0], np.flatnonzero(yh_hl < 0)[0]]
print(pd.DataFrame({"name": auto_dr["name"], "y_h": yh_hl.round(2), "hinge": hinge_hl.round(2),
"misclassified": zero_one_hl}).iloc[first_hl]) name y_h hinge misclassified
1 buick skylark 320 1.66 0.00 0.0
0 chevrolet chevelle malibu 0.90 0.10 0.0
15 plymouth duster -0.29 1.29 1.00.3662992006749351 0.13520408163265307yh_hl <- y_dr * f_sl # y h(x): positive when correct, at least 1 beyond the margin
hinge_hl <- pmax(0, 1 - yh_hl)
zero_one_hl <- as.numeric(yh_hl < 0)
first_hl <- c(which(yh_hl >= 1)[1], which(yh_hl >= 0 & yh_hl < 1)[1], which(yh_hl < 0)[1])
data.frame(name = auto_dr$name, y_h = round(yh_hl, 2), hinge = round(hinge_hl, 2),
misclassified = zero_one_hl)[first_hl, ]mean_hinge error_rate
0.3662992 0.1352041 The first car costs nothing, since it is beyond its margin. The second is classified correctly but sits inside the margin, so the hinge loss charges it 0.10 where the misclassification loss charges 0. The third is misclassified, and the hinge loss of 1.29 exceeds the misclassification loss of 1. Averaged over all 392 cars, the hinge loss is 0.366 and the error rate is 0.135. The hinge loss is never below the misclassification loss, so it is an upper bound on the error rate, and it equals the slack \(\slack_i\) of Example 9.
# HTML formats get an interactive plotly figure (hover for the values); the
# handout and other formats get the same figure drawn with ggplot2.
# Both losses on a fine grid of y h(x), so the step of the misclassification loss looks vertical.
grid_yh <- seq(min(-1, yh_hl[first_hl]) - 0.5, max(2, yh_hl[first_hl]) + 0.5,
length.out = 801)
loss_df <- rbind(
tibble::tibble(yh = grid_yh, loss = pmax(0, 1 - grid_yh), kind = "hinge loss"),
tibble::tibble(yh = grid_yh, loss = as.numeric(grid_yh < 0), kind = "misclassification loss")
)
# The first car of each group from the example, at its own y h(x) and hinge loss.
cars_hl <- tibble::tibble(yh = yh_hl[first_hl], loss = hinge_hl[first_hl])
if (knitr::is_html_output()) {
library(plotly)
# Dotted vertical lines at the decision boundary (0) and the margin (1).
vline <- function(x) {
list(
type = "line", x0 = x, x1 = x, y0 = 0, y1 = 1, yref = "paper",
line = list(color = "#999999", dash = "dot")
)
}
widget <- plot_ly() |>
add_trace(
data = loss_df[loss_df$kind == "hinge loss", ], x = ~yh, y = ~loss,
type = "scatter", mode = "lines", name = "hinge loss",
line = list(color = "#1f77b4")
) |>
add_trace(
data = loss_df[loss_df$kind == "misclassification loss", ],
x = ~yh, y = ~loss, type = "scatter", mode = "lines",
name = "misclassification loss", line = list(color = "#d95f02", dash = "dash")
) |>
add_trace(
data = cars_hl, x = ~yh, y = ~loss, type = "scatter", mode = "markers",
name = "the cars", marker = list(color = "#222222", size = 10)
) |>
layout(
xaxis = list(title = "Margin, y h(x)"),
yaxis = list(title = "loss"),
shapes = list(vline(0), vline(1)),
legend = list(orientation = "h", y = -0.25),
margin = list(t = 10)
) |>
config(displaylogo = FALSE, responsive = TRUE)
# The alt text: a plotly widget has none of its own.
htmltools::div(
role = "img",
`aria-label` = paste(
"Interactive plot of the hinge loss and the misclassification loss against",
"y h(x). The misclassification loss is a step at zero; the hinge loss falls",
"linearly from 1 at zero to 0 at one and lies on or above the step. Three",
"dots mark the three cars of the example."
),
widget
)
} else {
library(ggplot2)
ggplot(loss_df, aes(yh, loss, linetype = kind)) +
geom_vline(xintercept = c(0, 1), colour = "grey60", linetype = "dotted") +
geom_line() +
geom_point(aes(yh, loss), data = cars_hl, inherit.aes = FALSE, size = 2.5) +
scale_linetype_manual(values = c("hinge loss" = "solid", "misclassification loss" = "longdash")) +
labs(x = "Margin, y h(x)", y = "loss", linetype = NULL) +
theme(legend.position = "bottom")
}Read
GeeksforGeeks explains the hinge loss [20].
Exercise 101 (Step across the hinge’s corner)
Exercise 101 (Step across the hinge’s corner) Proposition 3 turned Definition 11 into one unconstrained objective,
\[J(w, b) = \frac{1}{2}\norm{w}_2^2 + C\sumiN \maxf{0,\; 1 - y_{(i)}\paren{\dprod{w}{x_{(i)}} + b}},\]
which gradient descent could minimize but for one problem.
Where, as a function of \(w\) and \(b\), is \(J\) not differentiable?
Solution 101. Point \(i\)’s hinge term has a corner where \(y_{(i)}(w^\top x_{(i)} + b) = 1\), that is, where the point sits exactly on the margin. For each \(i\) that is one hyperplane in \((w, b)\) space, and \(J\) is not differentiable on the union of those \(N\) hyperplanes.
Exercise 102 (Step across the hinge’s corner (part 2))
Exercise 102 (Step across the hinge’s corner (part 2)) Use the setup of Exercise 101.
Away from those points, give the gradient of one point’s hinge term with respect to \(w\) and \(b\), and then the gradient of \(J\).
Solution 102. Where \(\outvar_{(i)}(w^\top \predvar_{(i)} + b) > 1\) the term is \(0\), and so is its gradient. Where \(y_{(i)}(w^\top x_{(i)} + b) < 1\) the term is \(C\paren{1 - y_{(i)}(w^\top x_{(i)} + b)}\), with gradient \(-C y_{(i)} x_{(i)}\) in \(w\) and \(-C y_{(i)}\) in \(b\). Writing \(V\) for the set of points that violate the margin,
\[\grad_w J = w - C\sum_{i \in V} y_{(i)} x_{(i)}, \qquad \frac{\partial J}{\partial b} = -C\sum_{i \in V} y_{(i)}.\]
A subgradient method steps against these, recomputing \(V\) at every step.
Exercise 103 (Step across the hinge’s corner (part 3))
Exercise 103 (Step across the hinge’s corner (part 3)) Use the setup of Exercise 101.
At a point where \(J\) is not differentiable, a subgradient method uses the derivative from either side. Explain why the choice makes no practical difference.
Solution 103. Each iterate is a deterministic function of the data, so landing exactly on a corner means the data satisfy one particular equation, which data drawn from a continuous distribution do with probability zero. And should it happen, either one-sided derivative is a valid subgradient; treating a point exactly on the margin as inactive picks one of them.
The corners still matter near the optimum. A support vector that sits exactly on the margin has \(\outvar_{(i)}\modmemf{\predvar_{(i)}} = 1\), so the optimum itself lies on the corner set, and the iterates keep crossing corners around it rather than landing on one. That crossing limits the step size.
Proposition 4 (The gradient of the C-SVM objective away from its corners)
Proposition 4 (The gradient of the C-SVM objective away from its corners) Let \(J(w, b)\) be the objective of Proposition 3, and let \(V = \{ i : y_{(i)}\paren{\dprod{w}{x_{(i)}} + b} < 1 \}\) be the set of points that violate the margin. At every \((w, b)\) with no training point exactly on the margin, \(J\) is differentiable, and
\[\grad_w J = w - C\sum_{i \in V} y_{(i)} x_{(i)}, \qquad \frac{\partial J}{\partial b} = -C\sum_{i \in V} y_{(i)}.\]
Proof
Proof. This is the solution to Exercise 101 and Exercise 102.
Exercise 104 (Write the loop)
Exercise 104 (Write the loop) Using the gradient of Proposition 4, write a function svm_subgradient(X, y, C, h, steps) that starts from \(w = 0\) and \(b = 0\) and takes steps subgradient steps of size \(\learnrate\), treating a point exactly on the margin as inactive.
Then simulate two overlapping classes to try it on: 100 points labelled \(-1\) around \((-1.5, 0)\) and 100 labelled \(+1\) around \((1.5, 0)\), each coordinate normal with standard deviation \(1\).
Solution 104.
import numpy as np
def svm_subgradient(X, y, C, h=1e-4, steps=20_000):
w = np.zeros(X.shape[1])
b = 0.0
for _ in range(steps):
offside = y * (X @ w + b) < 1 # where the hinge is active
w = w - h * (w - C * (y[offside] @ X[offside]))
b = b + h * C * y[offside].sum()
return w, b
rng = np.random.default_rng(0)
n = 100
X = np.vstack([rng.normal([-1.5, 0], 1.0, (n, 2)),
rng.normal([1.5, 0], 1.0, (n, 2))])
y = np.repeat([-1.0, 1.0], n)svm_subgradient <- function(X, y, C, h = 1e-4, steps = 20000) {
w <- rep(0, ncol(X))
b <- 0
for (step in seq_len(steps)) {
offside <- y * drop(X %*% w + b) < 1 # where the hinge is active
w <- w - h * (w - C * colSums(X[offside, , drop = FALSE] * y[offside]))
b <- b + h * C * sum(y[offside])
}
list(w = w, b = b)
}
set.seed(0)
n <- 100
X <- rbind(cbind(rnorm(n, -1.5), rnorm(n, 0)),
cbind(rnorm(n, 1.5), rnorm(n, 0)))
y <- rep(c(-1, 1), each = n)using Random, LinearAlgebra
function svm_subgradient(X, y, C; h = 1e-4, steps = 20_000)
w = zeros(size(X, 2))
b = 0.0
for _ in 1:steps
offside = y .* (X * w .+ b) .< 1 # where the hinge is active
w = w .- h .* (w .- C .* vec(sum(X[offside, :] .* y[offside], dims = 1)))
b = b + h * C * sum(y[offside])
end
return w, b
end;
Random.seed!(0);
n = 100;
X = vcat([-1.5 0.0] .+ randn(n, 2), [1.5 0.0] .+ randn(n, 2));
y = [fill(-1.0, n); fill(1.0, n)];Exercise 105 (Predict what \(C\) does, then check)
Exercise 105 (Predict what \(C\) does, then check) Run the svm_subgradient of Solution 104 at \(C = 0.01\), \(0.1\) and \(1\). For each \(C\), find the margin width \(2/\norm{w}\), the number of support vectors (points with \(y_{(i)}\modmemf{x_{(i)}} \le 1\)), and the number of misclassified points (points with \(y_{(i)}\modmemf{x_{(i)}} < 0\)).
Before you run it, predict which way each of the three numbers moves as \(C\) grows.
Solution 105.
# Each tab's svm_subgradient at the three values of C, keeping the margin,
# support-vector and misclassified counts for the table and the prose.
svm_r <- t(sapply(c(0.01, 0.1, 1), function(cost) {
fit <- svm_subgradient(X, y, cost)
f <- y * drop(X %*% fit$w + fit$b)
c(2 / sqrt(sum(fit$w^2)), sum(f <= 1 + 1e-6), sum(f < 0))
}))# Each tab's svm_subgradient at the three values of C, keeping the margin,
# support-vector and misclassified counts for the table and the prose.
svm_py = []
for C in (0.01, 0.1, 1.0):
w, b = svm_subgradient(X, y, C)
f = y * (X @ w + b)
svm_py.append([2 / np.linalg.norm(w),
int(np.sum(f <= 1 + 1e-6)), int(np.sum(f < 0))])
svm_py = np.array(svm_py)# One row per C (0.01, 0.1, 1); columns: margin, support vectors,
# misclassified.
svm_py <- py$svm_py
svm_jl <- JuliaCall::julia_eval("svm_jl")
svm_all <- list(Py = svm_py, R = svm_r, Jl = svm_jl)
# fmt2() comes from the page's setup chunk, which lintr cannot see from this
# file.
# nolint start: object_usage_linter.
margins <- function(i) {
vals <- sapply(svm_all, function(m) fmt2(m[i, 1]))
paste0("$", vals, "$", collapse = " / ")
}
# nolint end
svs <- function(i) {
vals <- sapply(svm_all, function(m) m[i, 2])
paste0("$", vals, "$", collapse = " / ")
}
misclassified <- function(m) paste0("$", m[, 3], "$", collapse = ", ")
sv_ratio <- sapply(svm_all, function(m) m[1, 2] / m[3, 2])
# The claims the prose makes in words.
for (m in svm_all) {
stopifnot(
all(diff(m[, 1]) < 0), # margin falls as C grows
all(diff(m[, 2]) < 0), # so does the support-vector count
diff(range(m[, 3])) <= 1 # misclassified wanders by one point
)
}
stopifnot(
all(sv_ratio > 2.5 & sv_ratio < 3.5), # roughly a factor of three
# not even the same direction in all three
length(unique(sapply(svm_all, function(m) sign(m[2, 3] - m[1, 3])))) > 1
)The three languages draw their own data, so read the trends rather than the digits:
| \(C\) | margin (Py / R / Jl) | support vectors |
|---|---|---|
| \(0.01\) | \(2.90\) / \(3.01\) / \(3.00\) | \(101\) / \(94\) / \(100\) |
| \(0.1\) | \(1.50\) / \(1.68\) / \(1.56\) | \(50\) / \(49\) / \(53\) |
| \(1.0\) | \(1.06\) / \(0.99\) / \(1.11\) | \(32\) / \(35\) / \(36\) |
As \(C\) grows, the margin narrows, the support-vector count falls, and the misclassified count barely moves. Raising \(C\) makes each unit of slack more expensive, so the optimizer uses less of it, and using less slack means a narrower margin. The hard-margin case is \(C \to \infty\), where slack costs too much to use at all. A wide margin swallows more points, and every point inside the margin is a support vector, so the support-vector count follows the margin; this is the \(\svfrac\)-SVM’s lower bound on the fraction of support vectors seen from the other direction. The misclassified count does not follow either, because \(C\) trades margin width against margin violations, and a point can sit inside the margin and still be on the correct side of the boundary.
Exercise 106 (Predict what \(C\) does, then check (part 2))
Exercise 106 (Predict what \(C\) does, then check (part 2)) Use the setup of Exercise 105.
Which of those predictions does Exercise 78 already settle?
Solution 106. Only the margin. Theorem 7 proves that the margin never increases as \(C\) grows, which Solution 74 argued from which term dominates. Neither says anything about the support-vector or misclassified counts.
Exercise 107 (Predict what \(C\) does, then check (part 3))
Exercise 107 (Predict what \(C\) does, then check (part 3)) Use the setup of Exercise 105.
Run it in one language, and compare.
Solution 107. The margin and the support-vector count move as predicted in all three languages, and the support-vector count falls by roughly a factor of three — \(3.2\) in Python, \(2.7\) in R and \(2.8\) in Julia. The misclassified count changes by a single point — \(11\), \(12\), \(11\) in Python, \(11\), \(10\), \(11\) in R, \(17\), \(16\), \(16\) in Julia — with no consistent direction, and not even the same direction in all three. These classes really do overlap, so there is a minimum error that no linear boundary can go below, and \(C\) does not trade accuracy.
Exercise 108 (Choose the step size)
Exercise 108 (Choose the step size) The svm_subgradient of Solution 104 uses the step size \(\learnrate = 10^{-4}\), a thousand times smaller than the \(0.1\) that Gradient Descent uses.
The hinge terms are piecewise linear in \(w\) and \(b\). Where \(J\) is differentiable, what is its Hessian with respect to \((w, b)\)?
Solution 108.
# The step-size measurements, on the Python tab's data.
with np.errstate(over="ignore", invalid="ignore"):
step_c1 = [np.linalg.norm(svm_subgradient(X, y, 1.0, h=h)[0])
for h in (1e-4, 0.001, 0.01, 0.03, 0.1, 0.3, 2.1)]
step_c100 = [np.linalg.norm(svm_subgradient(X, y, 100.0, h=h)[0])
for h in (1e-4, 0.01)]
step_finite_19 = [bool(np.isfinite(np.linalg.norm(
svm_subgradient(X, y, C, h=1.9)[0])))
for C in (0.01, 0.1, 1.0, 100.0)]
step_finite_21 = [bool(np.isfinite(np.linalg.norm(
svm_subgradient(X, y, C, h=2.1)[0])))
for C in (0.01, 0.1, 1.0, 100.0)]Away from the corners, each hinge term is linear in \((w, b)\), so it contributes no curvature at all. The only curvature comes from \(\tfrac12\norm{w}_2^2\), so the Hessian is
\[\grad^2 J = \begin{bmatrix} I & 0 \\ 0 & 0 \end{bmatrix},\]
with the identity in the \(w\) block and \(0\) for \(b\).
Exercise 109 (Choose the step size (part 2))
Exercise 109 (Choose the step size (part 2)) Use the setup of Exercise 108.
What is \(L\), the largest eigenvalue of that Hessian, as in Gradient Descent?
Solution 109. Its largest eigenvalue is \(L = 1\).
Exercise 110 (Choose the step size (part 3))
Exercise 110 (Choose the step size (part 3)) Use the setup of Exercise 108.
What bound on \(\learnrate\) would that give?
Solution 110. With \(L = 1\), the quadratic bound \(\learnrate < 2/L\) is \(\learnrate < 2\).
Exercise 111 (Choose the step size (part 4))
Exercise 111 (Choose the step size (part 4)) Use the setup of Exercise 108.
Would that bound depend on \(C\) or \(N\)?
Solution 111. Neither \(C\) nor \(N\) appears in it. But \(\grad_w J\) jumps at the corners, so \(J\) is not a quadratic and that result does not apply directly; Solution 113 shows that the bound holds anyway.
Exercise 112 (Choose the step size (part 5))
Exercise 112 (Choose the step size (part 5)) Use the setup of Exercise 108.
Write the \(w\) update as \(w_{k+1} = a\,w_k + r_k\), where \(a\) is a number and \(r_k\) collects the hinge terms.
Solution 112. The update of Solution 104 is
\[\begin{aligned} w_{k+1} &= w_k - \learnrate\paren{w_k - C\sum_{i \in V_k} y_{(i)} x_{(i)}} \\ &= (1 - \learnrate)\,w_k + \learnrate C\sum_{i \in V_k} y_{(i)} x_{(i)}, \end{aligned}\]
where \(V_k\) is the set of points violating the margin at step \(k\). So \(a = 1 - \learnrate\) and \(r_k = \learnrate C\sum_{i \in V_k} y_{(i)} x_{(i)}\).
Exercise 113 (Choose the step size (part 6))
Exercise 113 (Choose the step size (part 6)) Use the setup of Exercise 108.
For which \(\learnrate\) do the iterates stay bounded?
Solution 113. Whichever points violate the margin, \(\norm{r_k}_2 \le R = \learnrate C\sumiN\norm{x_{(i)}}_2\). Starting from \(w_0 = 0\) and unrolling,
\[w_k = \sum_{j=0}^{k-1} a^{\,k-1-j}\, r_j, \qquad\text{so}\qquad\norm{w_k}_2 \le R\sum_{j=0}^{k-1} |a|^j \le \frac{R}{1 - |a|} \quad\text{when } |a| < 1.\]
So the iterates stay bounded when \(|1 - \learnrate| < 1\), that is, when \(0 < \learnrate < 2\).
Exercise 114 (Choose the step size (part 7))
Exercise 114 (Choose the step size (part 7)) Use the setup of Exercise 108.
Does your answer agree with Exercise 110 and Exercise 111?
Solution 114. The bound \(0 < \learnrate < 2\) agrees with Solution 110. \(C\) and \(N\) appear only in \(R\), never in \(a\), so the threshold depends on neither. When \(|a| > 1\), nothing damps the \(r_k\): svm_subgradient overflows at \(\learnrate = 2.1\) for every \(C\) tried, and at \(\learnrate = 1.9\) it never does. The intercept gets no such contraction, since its Hessian entry is \(0\); what keeps \(b\) in check is the hinge, not curvature.
Exercise 115 (Choose the step size (part 8))
Exercise 115 (Choose the step size (part 8)) Use the setup of Exercise 108.
In Gradient Descent, a step size past the bound made the iterates overflow. Say in advance what happens here at \(C = 1\) as \(\learnrate\) grows from \(0.001\) toward the bound: will the returned \(\norm{w}\) stay close to its converged value?
Solution 115. No. In Gradient Descent the iterates overflowed; here they mostly do not, but staying finite is not the same as being right, and the important failure happens well below \(\learnrate = 2\). As \(\learnrate\) grows, the iterates start jumping across the corners, changing which points violate the margin from one step to the next, and they settle into an orbit around the optimum rather than at it. The answer that comes back is finite, believable, and wrong. Measured on the Python tab’s data at \(C = 1\), where the converged \(\norm{w}\) is \(1.88\):
| \(\learnrate\) | \(0.001\) | \(0.01\) | \(0.03\) | \(0.1\) | \(0.3\) | \(2.1\) |
|---|---|---|---|---|---|---|
| \(\norm{w}\) | \(1.88\) | \(1.88\) | \(1.89\) | \(3.38\) | \(13.9\) | overflow |
Exercise 116 (Choose the step size (part 9))
Exercise 116 (Choose the step size (part 9)) Use the setup of Exercise 108.
Should the range of usable step sizes grow or shrink as \(C\) grows?
Solution 116. It shrinks as \(C\) grows, since \(C\) scales \(r_k\) and so the size of each jump. At \(C = 100\), svm_subgradient needs \(\learnrate = 10^{-4}\) to get \(\norm{w} =2.09\); at \(\learnrate = 0.01\) it returns \(14.7\), with nothing to tell you that is 7 times too large. The step size of \(10^{-4}\) avoids that silent-wrong-answer regime, rather than the overflow.
Exercise 117 (Classify fuel economy with a soft margin)
Exercise 117 (Classify fuel economy with a soft margin) The Auto data of James et al. [5] give the fuel efficiency (mpg) of 392 cars. Download auto.csv to load it in Python or R. Label a car \(+1\) if its mpg is above the median mpg of the training cars and \(-1\) otherwise. Use every third car (the 1st, 4th, 7th, and so on) as test data and the other cars as training data. Predict the label from horsepower and weight, each standardized with the mean and standard deviation of the training cars.
Fit the svm_subgradient of Solution 104 to the training cars at \(C = 0.01\), \(0.1\) and \(1\). For each \(C\), find the number of support vectors and the test misclassification rate.
Solution 117.
import pandas as pd
auto_py = pd.read_csv("data/auto.csv").dropna()
is_test_py = (np.arange(len(auto_py)) % 3 == 0)
feat = auto_py[["horsepower", "weight"]].to_numpy(dtype=float)
mu, sd = feat[~is_test_py].mean(axis=0), feat[~is_test_py].std(axis=0, ddof=1)
Xa_py = (feat - mu) / sd
mpg = auto_py["mpg"].to_numpy()
ya_py = np.where(mpg > np.median(mpg[~is_test_py]), 1.0, -1.0)
auto_svm_py = []
for C in (0.01, 0.1, 1.0):
w, b = svm_subgradient(Xa_py[~is_test_py], ya_py[~is_test_py], C)
f_train = ya_py[~is_test_py] * (Xa_py[~is_test_py] @ w + b)
f_test = ya_py[is_test_py] * (Xa_py[is_test_py] @ w + b)
auto_svm_py.append([C, int(np.sum(f_train <= 1 + 1e-6)),
float(np.mean(f_test < 0))])
pd.DataFrame(auto_svm_py, columns=["C", "support_vectors", "test_error"]) C support_vectors test_error
0 0.01 166 0.145038
1 0.10 105 0.122137
2 1.00 85 0.114504auto <- read.csv("data/auto.csv")
auto <- tidyr::drop_na(auto)
is_test <- (seq_len(nrow(auto)) - 1) %% 3 == 0
feat <- auto |>
dplyr::select(horsepower, weight) |>
as.matrix()
Xa <- scale(feat, center = colMeans(feat[!is_test, ]),
scale = apply(feat[!is_test, ], 2, sd))
ya <- ifelse(auto$mpg > median(auto$mpg[!is_test]), 1, -1)
auto_fits <- lapply(c(0.01, 0.1, 1), function(cost) {
svm_subgradient(Xa[!is_test, ], ya[!is_test], cost)
})
auto_svm <- t(sapply(auto_fits, function(fit) {
f_train <- ya[!is_test] * drop(Xa[!is_test, ] %*% fit$w + fit$b)
f_test <- ya[is_test] * drop(Xa[is_test, ] %*% fit$w + fit$b)
c(support_vectors = sum(f_train <= 1 + 1e-6),
test_error = mean(f_test < 0))
}))
tibble::tibble(C = c(0.01, 0.1, 1), tibble::as_tibble(auto_svm))# The claims the prose makes: both languages agree, and the support-vector
# count falls as C grows.
auto_py <- matrix(as.numeric(unlist(py$auto_svm_py)), ncol = 3, byrow = TRUE)
stopifnot(
all(auto_py[, 2] == auto_svm[, 1]),
all(abs(auto_py[, 3] - auto_svm[, 2]) < 1e-9),
all(diff(auto_svm[, 1]) < 0)
)Both languages read the same file and use the same standardization and the same deterministic algorithm, so they print the same table.
Exercise 118 (Classify fuel economy with a soft margin (part 2))
Exercise 118 (Classify fuel economy with a soft margin (part 2)) Use the setup of Exercise 117.
Plot the training cars with the boundary and margin for \(C = 1\).
library(ggplot2)
fit <- auto_fits[[3]]
svm_df <- tibble::tibble(
horsepower = Xa[!is_test, 1],
weight = Xa[!is_test, 2],
mpg_group = ifelse(ya[!is_test] > 0, "above median mpg", "below median mpg")
)
svm_lines <- tibble::tibble(
intercept = as.numeric((c(-1, 0, 1) - fit$b) / fit$w[2]),
slope = as.numeric(-fit$w[1] / fit$w[2]),
kind = c("margin", "boundary", "margin")
)
# The fit works in z-space; the tick labels show horsepower and pounds.
hp_center <- attr(Xa, "scaled:center")["horsepower"]
hp_scale <- attr(Xa, "scaled:scale")["horsepower"]
wt_center <- attr(Xa, "scaled:center")["weight"]
wt_scale <- attr(Xa, "scaled:scale")["weight"]
hp_ticks <- pretty(svm_df$horsepower * hp_scale + hp_center)
wt_ticks <- pretty(svm_df$weight * wt_scale + wt_center)
ggplot(svm_df, aes(horsepower, weight)) +
geom_point(aes(shape = mpg_group), size = 2) +
geom_abline(aes(intercept = intercept, slope = slope, linetype = kind),
data = svm_lines, show.legend = FALSE) +
scale_shape_manual(
values = c("above median mpg" = 1, "below median mpg" = 2)
) +
scale_linetype_manual(values = c(boundary = "solid", margin = "dashed")) +
scale_x_continuous(
breaks = (hp_ticks - hp_center) / hp_scale, labels = hp_ticks
) +
scale_y_continuous(
breaks = (wt_ticks - wt_center) / wt_scale,
labels = scales::label_comma()(wt_ticks)
) +
coord_cartesian(
xlim = range(svm_df$horsepower),
ylim = range(svm_df$weight)
) +
labs(x = "horsepower", y = "weight (lb)",
shape = NULL) +
theme(legend.position = "bottom")Exercise 119 (Classify fuel economy with a soft margin (part 3))
Exercise 119 (Classify fuel economy with a soft margin (part 3)) Use the setup of Exercise 117.
Which way does the number of support vectors move as \(C\) grows?
Solution 119. The support-vector count falls from 166 at \(C = 0.01\) to 105 at \(C = 0.1\) and 85 at \(C = 1\), as Solution 105 found for simulated data: a wider margin has more points inside it.
Exercise 120 (Classify fuel economy with a soft margin (part 4))
Exercise 120 (Classify fuel economy with a soft margin (part 4)) Use the setup of Exercise 117.
Does the test misclassification rate also move in one direction?
Watch
Exercise 121 (Ask what a linear boundary cannot do)
Exercise 121 (Ask what a linear boundary cannot do) Every classifier built so far is a hyperplane in \(x\). Linear regression’s non-linear section had the same limit and removed it with a feature transformation \(\vfeatmap: \reals^{\ninputvars} \to \reals^{\nparams}\), fitting a linear model in \(\vfeatmap(x)\) instead of in \(x\).
Sketch a training set in \(\reals^2\) that no line separates, but that a circle does.
Solution 121. A ring of positive points at radius \(2\) around the origin, and negative points scattered inside radius \(1\). No line separates near from far, but the circle \(\norm{x}_2 = 1.5\) does (Figure 8).
Exercise 122 (Ask what a linear boundary cannot do (part 2))
Exercise 122 (Ask what a linear boundary cannot do (part 2)) Use the setup of Exercise 121.
Propose a transformation \(\vfeatmap: \reals^2 \to \reals^3\) under which your two classes become linearly separable.
Solution 122. \(\vfeatmap(\predvar_1, \predvar_2) = (\predvar_1, \predvar_2, \predvar_1^2 + \predvar_2^2)\). The third coordinate is \(\norm{x}_2^2\), which is small for the inner class and large for the ring, so a horizontal plane in the third coordinate now separates the two classes.
Exercise 123 (Ask what a linear boundary cannot do (part 3))
Exercise 123 (Ask what a linear boundary cannot do (part 3)) Use the setup of Exercise 121.
What has to change in Definition 12 to fit a hyperplane in \(\vfeatmap(\predvar)\)-space instead of in \(\predvar\)-space?
Solution 123. Every \(x_{(i)}\) is replaced by \(\vfeatmap(x_{(i)})\), everywhere it appears:
\[\mathop{\argmax}_{\dualvar \in \reals^N} \quad \sumiN \dualvar_i - \frac{1}{2}\sumiN\sumto{j}{N} \dualvar_i \dualvar_j \, y_{(i)} y_{(j)} \, \vfeatmap\pt{x_{(i)}} \vfeatmap(x_{(j)}).\]
Nothing else in Definition 12 changes: the box constraint and the equality constraint are conditions on \(\dualvar\), and \(\dualvar\) still has one entry per training point regardless of what space those points lie in.
Exercise 124 (Find out what the dual actually costs)
Exercise 124 (Find out what the dual actually costs) Solution 121’s dual needs \(\vfeatmap\pt{x_{(i)}} \vfeatmap(x_{(j)})\) for every pair of training points. Take the polynomial transformation of degree \(d\) on \(\ninputvars\) input features, whose output dimension is \(\nparams = O(\ninputvars^d)\).
Computing \(\vfeatmap(\predvar)\) once costs \(O(\nparams)\) work. Computing \(\vfeatmap\pt{\predvar_{(i)}} \vfeatmap(\predvar_{(j)})\) from already-computed \(\vfeatmap(\predvar_{(i)})\) and \(\vfeatmap(\predvar_{(j)})\) costs another \(O(\nparams)\). Put the two together: what does computing one entry of the dual’s double sum cost?
Solution 124. \(O(\nparams)\) to compute \(\vfeatmap(\predvar_{(i)})\), \(O(\nparams)\) to compute \(\vfeatmap(x_{(j)})\), and \(O(\nparams)\) for the dot product itself: \(O(\nparams)\) in total, since three additive \(O(\nparams)\) terms are still \(O(\nparams)\).
Exercise 125 (Find out what the dual actually costs (part 2))
Exercise 125 (Find out what the dual actually costs (part 2)) Use the setup of Exercise 124.
MNIST digit images are \(28 \times 28\) pixels, so \(\ninputvars = 784\). Take \(d = 4\). Using \(\nparams = O(\ninputvars^d)\), is \(\nparams\) in the thousands, the millions, or the billions?
Solution 125. \(\nparams = O(784^4) \approx 3.8 \times 10^{11}\): the billions. Every one of those \(\vfeatmap(x_{(i)})\) vectors would need to be stored, and 377 billion floating-point numbers is far past what a training run keeps for one data point.
Exercise 126 (Find out what the dual actually costs (part 3))
Exercise 126 (Find out what the dual actually costs (part 3)) Use the setup of Exercise 124.
The dual objective needs this quantity for every pair \((i, j)\) among \(N\) training points. Multiply Exercise 124’s per-pair cost by the number of pairs, and say whether the bottleneck is \(\vfeatmap\) or the number of points.
Solution 126. \(O(N^2)\) pairs, each costing \(O(\nparams)\), for \(O(N^2 \nparams)\) total. With \(\nparams\) in the billions and \(N\) in the tens of thousands, the \(\nparams\) factor dominates completely: the bottleneck is computing \(\vfeatmap\) at all, not the number of points.
Exercise 127 (Find out what the dual actually costs (part 4))
Exercise 127 (Find out what the dual actually costs (part 4)) Use the setup of Exercise 124.
Exercise 125 says explicit transformation is unworkable at that \(\nparams\). Name precisely which quantity the dual needs – not \(\vfeatmap(\predvar_{(i)})\) and \(\vfeatmap(\predvar_{(j)})\) separately, but the one number they combine into – since that is the quantity worth computing a shortcut for.
Solution 127. The inner product \(\vfeatmap\pt{x_{(i)}} \vfeatmap(x_{(j)})\) itself, a single real number. The dual objective never uses \(\vfeatmap(x_{(i)})\) or \(\vfeatmap(x_{(j)})\) on their own – only their inner product enters the sum – so a method that produces that one number without first producing the two \(\nparams\)-dimensional vectors would sidestep the cost in Solution 125 entirely.
Definition 14 (Kernel function)
Definition 14 (Kernel function) A kernel function \(K(x, z)\) for a map \(\vfeatmap: \reals^{\ninputvars} \to \reals^{\nparams}\) is a function computing
\[K(x, z) = \dprod{\vfeatmap(x)}{\vfeatmap(z)}\]
in time that does not scale with \(\nparams\) [23].
Example 15 (A quadratic kernel on two cars)
Example 15 (A quadratic kernel on two cars) For \(x, z \in \reals^2\), the function \(K(x, z) = \paren{1 + \dprod{x}{z}}^2\) is a kernel for the map \(\vfeatmap(x) = \paren{1,\; \sqrt{2}\,x_1,\; \sqrt{2}\,x_2,\; x_1^2,\; \sqrt{2}\,x_1 x_2,\; x_2^2}\) into \(\reals^6\). Take the first two cars in the standardized Auto data [5] of Example 1, and compare \(K(x, z)\) with the inner product \(\dprod{\vfeatmap(x)}{\vfeatmap(z)}\) computed in the six-dimensional space:
def phi_kf(v):
# The explicit feature map: all monomials of degree at most 2, with the weights that make the kernel work.
return np.array([1, np.sqrt(2) * v[0], np.sqrt(2) * v[1], v[0] ** 2, np.sqrt(2) * v[0] * v[1], v[1] ** 2])
x_kf, z_kf = Z_dr[0], Z_dr[1]
kernel_kf = (1 + x_kf @ z_kf) ** 2 # one inner product in 2 dimensions
inner_kf = phi_kf(x_kf) @ phi_kf(z_kf) # an inner product in 6 dimensions
print(kernel_kf, inner_kf)6.579531810298261 6.5795318102982625phi_kf <- function(v) {
# The explicit feature map: all monomials of degree at most 2, with the weights that make the kernel work.
c(1, sqrt(2) * v[1], sqrt(2) * v[2], v[1]^2, sqrt(2) * v[1] * v[2], v[2]^2)
}
x_kf <- Z_dr[1, ]
z_kf <- Z_dr[2, ]
kernel_kf <- (1 + sum(x_kf * z_kf))^2 # one inner product in 2 dimensions
inner_kf <- sum(phi_kf(x_kf) * phi_kf(z_kf)) # an inner product in 6 dimensions
c(kernel = kernel_kf, feature_space = inner_kf) kernel feature_space
6.579532 6.579532 Both routes give 6.5795, as Definition 14 requires. The kernel needs one inner product of the two original coordinates and a square, however many coordinates \(\vfeatmap\) has, while the explicit route builds 6 coordinates for each car. With \(\ninputvars\) inputs the degree-2 map has \(\binom{\ninputvars+2}{2}\) coordinates, which grows like \(\ninputvars^2/2\), but the kernel still costs one inner product in \(\ninputvars\) dimensions.
Read
GeeksforGeeks explains the kernel trick [24].
Exercise 128 (Use a kernel without ever writing down \(\vfeatmap\))
Exercise 128 (Use a kernel without ever writing down \(\vfeatmap\)) Suppose \(K\) is a kernel function for some map \(\vfeatmap\), in the sense of Definition 14, and you are handed \(K\) but never told what \(\vfeatmap\) is.
Definition 12 solves for \(\dualvar\) using only inner products of training points. Rewrite it with \(K(\predvar_{(i)}, \predvar_{(j)})\) in place of \(\dprod{\predvar_{(i)}}{\predvar_{(j)}}\).
Solution 128. \[\mathop{\argmax}_{\dualvar \in \reals^N} \quad \sumiN \dualvar_i - \frac{1}{2}\sumiN\sumto{j}{N} \dualvar_i \dualvar_j \, y_{(i)} y_{(j)} \, K\paren{x_{(i)}, x_{(j)}} \quad \text{s.t.} \quad 0 \leq \dualvar_i \leq C, \quad \sumiN \dualvar_i \, y_{(i)} = 0.\]
Exercise 129 (Use a kernel without ever writing down \(\vfeatmap\) (part 2))
Exercise 129 (Use a kernel without ever writing down \(\vfeatmap\) (part 2)) Use the setup of Exercise 128.
Does solving it require knowing \(\vfeatmap\)?
Solution 129. No. Every appearance of \(\vfeatmap\) in Solution 121’s dual was inside an inner product, and \(K\) evaluates each of those directly. The optimization never asks for \(\vfeatmap(x_{(i)})\) on its own.
Exercise 130 (Use a kernel without ever writing down \(\vfeatmap\) (part 3))
Exercise 130 (Use a kernel without ever writing down \(\vfeatmap\) (part 3)) Use the setup of Exercise 128.
Solution 124 found the dual’s bottleneck is computing \(\vfeatmap\), not the number of training points. Say what Exercise 128 has done to that bottleneck.
Solution 130. It has removed it. Computing \(K(x_{(i)}, x_{(j)})\) costs whatever \(K\)’s own formula costs, with no dependence on \(\nparams\), so the \(O(\nparams)\) step Solution 124 identified as the bottleneck is gone from the calculation entirely — not made cheaper, but skipped. The classifier can now work in a space too large to write a vector down in, because no vector in that space is ever computed.
Exercise 131 (Use a kernel without ever writing down \(\vfeatmap\) (part 4))
Exercise 131 (Use a kernel without ever writing down \(\vfeatmap\) (part 4)) Use the setup of Exercise 128.
Not every function of two arguments is a kernel function for some \(\vfeatmap\). Take \(K(\predvar, z) = \dprod{\predvar}{z} - 1\) on \(\predvar, z \in \reals\), so that \(K(\predvar, \predvar) = \predvar^2 - 1\). Explain why no \(\vfeatmap\) can produce this \(K\), using only the definition \(K(\predvar, z) = \dprod{\vfeatmap(\predvar)}{\vfeatmap(z)}\).
Solution 131. For any \(x\), \(K(x, x) = \dprod{\vfeatmap(x)}{\vfeatmap(x)} =\norm{\vfeatmap(x)}_2^2\), a squared length, which is never negative. Take \(x = 0\): \(K(0, 0) = 0^2 - 1 = -1 < 0\). No real vector has a negative squared length, so no \(\vfeatmap\) satisfies \(K(x, z) = \dprod{\vfeatmap(x)}{\vfeatmap(z)}\) for this \(K\). Being a valid inner product is a real constraint on which functions qualify as kernels, not a formality.
Three kernels to know by name
Definition 14 only requires \(K\) to compute some \(\vfeatmap\)’s inner product quickly. It says nothing about what \(\vfeatmap\) is, and in practice you pick \(K\) without ever naming \(\vfeatmap\) at all. Three choices cover most uses.
The linear kernel, \(K(x, z) = \dprod{x}{z}\), is \(\vfeatmap\) = the identity. Using it in Solution 128’ dual reproduces Definition 12 exactly, and Definition 8 in the further limit \(C \to \infty\), where the box constraint’s upper bound stops binding: every SVM built so far is the special case of a kernel SVM where the kernel is linear.
The polynomial kernel, \(K(x, z) = (\dprod{x}{z} + 1)^d\), corresponds to a \(\vfeatmap\) whose coordinates are every monomial in \(x\)’s entries up to degree \(d\), the same family linear regression’s non-linear section names. \(\nparams\) for this \(\vfeatmap\) is exactly the count that exercise found, and \(K\) computes its inner product in \(O(\ninputvars)\) time regardless.
The RBF kernel (also called the Gaussian kernel), \[K(x, z) = \expf{-\frac{\norm{x - z}_2^2}{2\bandwidth^2}},\] corresponds to a \(\vfeatmap\) mapping into an infinite-dimensional space. There is no finite \(\nparams\) to be intractable here: the inner product exists only through \(K\), since no computer stores an infinite vector. \(\bandwidth\) is a hyperparameter, chosen the same way \(C\) is.
A useful, informal way to read the RBF kernel is as a similarity score: \(K(x, z)\) is largest, equal to \(1\), when \(x = z\), and decreases as \(\norm{x - z}_2\) grows. The linear and polynomial kernels do not read that way. The linear kernel gives \(K(x, x) = 1\) but \(K(x, (2, 0)) = 2\) for \(x = (1, 0)\), so moving \(z\) further along \(x\)’s direction raises \(K\), and the polynomial kernel grows the same way. The linear kernel measures how well \(x\) and \(z\) point the same way, scaled by their lengths: \(\dprod{x}{z} =\norm{x}_2\norm{z}_2 \cos\angpar\), where \(\angpar\) is the angle between them. The polynomial kernel measures the same thing for \(\vfeatmap(x)\) and \(\vfeatmap(z)\). Dividing out the lengths of \(\vfeatmap(x)\) and \(\vfeatmap(z)\), \[\frac{K(x, z)}{\sqrt{K(x, x)\, K(z, z)}},\] gives a score between \(-1\) and \(1\) for any kernel whose \(K(x, x)\) and \(K(z, z)\) are positive, by the Cauchy–Schwarz inequality, since \(K(x, z) = \dprod{\vfeatmap(x)}{\vfeatmap(z)}\) (Definition 14). For the linear kernel that score is \(\cos\angpar\). The RBF kernel already has \(K(x, x) = 1\), so dividing changes nothing, so it reads as a similarity score as it stands. Which functions can serve as a kernel at all is a large topic of its own, touched on in Exercise 131 and pursued no further here.
Read
GeeksforGeeks explains the common kernel functions [25].
Exercise 132 (Compare points with the RBF kernel)
Exercise 132 (Compare points with the RBF kernel) Let \(K(x, z) = \expf{-\norm{x - z}_2^2 / (2\bandwidth^2)}\) be the RBF kernel with bandwidth \(\bandwidth = 1\).
Which of the following is the smallest?
Solution 132. The RBF kernel depends on its inputs only through the squared distance \(\norm{x - z}_2^2\), and it decreases as that distance grows. So the smallest value belongs to the pair that is furthest apart.
# The RBF kernel with bandwidth sigma = 1, written out from its definition.
rbf <- function(x, z, sigma = 1) {
exp(-sum((x - z)^2) / (2 * sigma^2))
}
# One value per pair, in the order A, B, C, so we can compare them.
rbf_values <- c(
A = rbf(c(0, 0), c(1, 2)),
B = rbf(c(0, 0), c(-3, 0)),
C = rbf(c(2, 1), c(5, 4))
)
rbf_values A B C
0.0820849986 0.0111089965 0.0001234098 The squared distances are 5, 9 and 18, so the values are 0.0821, 0.0111 and 0.000123. The smallest is (C), the pair at the greatest distance.
Exercise 133 (Compare points with the RBF kernel (part 2))
Exercise 133 (Compare points with the RBF kernel (part 2)) Use the setup of Exercise 132.
Does your answer to Exercise 132 change if \(\bandwidth\) changes?
Solution 133. No. For any \(\bandwidth > 0\), \(K\) is a decreasing function of \(\norm{x - z}_2^2\), so the ranking of the three values is the ranking of the distances. The bandwidth changes how fast \(K\) falls off with distance, not the order.
Exercise 134 (Compare points with the RBF kernel (part 3))
Exercise 134 (Compare points with the RBF kernel (part 3)) Use the setup of Exercise 132.
The RBF kernel’s \(\vfeatmap\) maps into an infinite-dimensional space. Is that a recipe for overfitting?
Solution 134. Not by itself. \(\vfeatmap\) places the points on a surface inside the large space, so the ambient dimension is huge but the points are not free to go anywhere in it. Computing \(\dprod{\vfeatmap(x)}{\vfeatmap(z)}\) costs only \(O(\ninputvars)\) operations through \(K\) for the same reason: the data’s intrinsic dimension is still \(\ninputvars\). The max-margin objective also penalizes \(\norm{w}\), which regularizes the fit, so a larger feature space does not by itself mean a more flexible classifier. The bandwidth \(\bandwidth\) and the cost \(C\) are what control flexibility here, and they are chosen by validation, as in Solution 74.
Exercise 135 (Classify a point when \(w\) cannot be written down)
Exercise 135 (Classify a point when \(w\) cannot be written down) Solution 128 never computes \(\vfeatmap(x_{(i)})\), so \(w = \sum_i \dualvar_i y_{(i)} \vfeatmap(x_{(i)})\) from Proposition 2 is a sum of vectors you do not have, possibly infinite-dimensional ones under the RBF kernel. The trained classifier still has to predict a label for a new point \(x\), which needs the sign of \(\modmemf{x} = \tp{w} \vfeatmap(x) + b\).
Substitute \(w\)’s definition into \(\tp{w} \vfeatmap(\predvar)\) and distribute the sum over the inner product.
Solution 135. \[ \begin{aligned} \tp{w} \vfeatmap(x) &= \sumiN \dualvar_i y_{(i)} \vfeatmap\pt{x_{(i)}} \vfeatmap(x). \end{aligned} \]
Exercise 136 (Classify a point when \(w\) cannot be written down (part 2))
Exercise 136 (Classify a point when \(w\) cannot be written down (part 2)) Use the setup of Exercise 135.
Rewrite the result using \(K\).
Solution 136. \[ \begin{aligned} \tp{w} \vfeatmap(x) &= \sumiN \dualvar_i y_{(i)} K\paren{x_{(i)}, x}. \end{aligned} \]
Exercise 137 (Classify a point when \(w\) cannot be written down (part 3))
Exercise 137 (Classify a point when \(w\) cannot be written down (part 3)) Use the setup of Exercise 135.
Proposition 2 recovered \(b\) from a margin support vector \(\predvar_{(k)}\) as \(b = \outvar_{(k)} - \dprod{w}{\predvar_{(k)}}\), which solves \(\outvar_{(k)} \modmemf{\predvar_{(k)}} = 1\) for \(b\). Do the same here: substitute Exercise 136’s expression for \(\tp{w} \vfeatmap(\predvar_{(k)})\) and solve for \(b\).
Solution 137. Solution 136 with \(\predvar = \predvar_{(k)}\) gives \(\tp{w} \vfeatmap(x_{(k)}) = \sum_i \dualvar_i y_{(i)} K(x_{(i)}, x_{(k)})\). Substituting into \(y_{(k)} \modmemf{x_{(k)}} = 1\), that is \(y_{(k)}\paren{\tp{w} \vfeatmap(x_{(k)}) + b} = 1\), and dividing by \(y_{(k)} \in \{-1, +1\}\):
\[b = y_{(k)} - \sumiN \dualvar_i y_{(i)} K\paren{x_{(i)}, x_{(k)}},\]
for any margin support vector \(\predvar_{(k)}\), meaning \(0 < \dualvar_k < C\).
Exercise 138 (Classify a point when \(w\) cannot be written down (part 4))
Exercise 138 (Classify a point when \(w\) cannot be written down (part 4)) Use the setup of Exercise 135.
Write the full decision rule – the sign that is actually computed to classify a new point – using only \(K\), the training labels, the \(\dualvar_i\), and \(b\). Confirm no \(\vfeatmap\) appears anywhere in it.
Solution 138. Classify \(x\) by the sign of
\[\sumiN \dualvar_i y_{(i)} K\paren{x_{(i)}, x} + b.\]
Only \(K\), the \(y_{(i)}\), the \(\dualvar_i\), and \(b\) appear. \(\vfeatmap\) was used to derive the rule and never appears in it.
Exercise 139 (Classify a point when \(w\) cannot be written down (part 5))
Exercise 139 (Classify a point when \(w\) cannot be written down (part 5)) Use the setup of Exercise 135.
At training time the number of parameters was fixed by \(\ninputvars\) (for \(w\)) or by \(N\) (for \(\dualvar\)). Exercise 138’s rule needs \(K(\predvar, \predvar_{(i)})\) for training points \(\predvar_{(i)}\). What has to be kept around after training to make a prediction, that an ordinary parametric model would not need?
Solution 139. The training points themselves, or at least the ones with \(\dualvar_i \neq 0\) – the support vectors – together with their labels and \(\dualvar_i\) values. An ordinary parametric model, such as Definition 11’s own \(w\) and \(b\), is a fixed-size summary of the training data that can be kept without keeping the data. A kernel SVM’s decision rule instead recomputes \(K\) against stored training points every time it predicts, which makes it a non-parametric model (Kinds of Learning Problems and Features): the number of things that must be stored, and the cost of a single prediction, both grow with \(N\) rather than staying fixed.
Theorem 8 (The decision rule of a kernel SVM)
Theorem 8 (The decision rule of a kernel SVM) Let \(K\) be a kernel for the map \(\vfeatmap\) as in Definition 14, let \(\dualvar\) solve the C-SVM dual with \(K\) in place of \(\dprod{x_{(i)}}{x_{(j)}}\), and let \(w = \sumiN \dualvar_i y_{(i)} \vfeatmap(x_{(i)})\). Then, for every \(x\),
\[ \dprod{w}{\vfeatmap(x)} + b = \sumiN \dualvar_i \, y_{(i)} \, K\paren{x_{(i)}, x} + b, \]
where, for any \(k\) with \(0 < \dualvar_k < C\),
\[b = y_{(k)} - \sumiN \dualvar_i \, y_{(i)} \, K\paren{x_{(i)}, x_{(k)}}.\]
The rule classifies \(x\) by the sign of the left side. It uses \(K\), the labels, the coefficients \(\dualvar_i\) and \(b\), but never \(\vfeatmap\) itself, and only the training points with \(\dualvar_i \neq 0\) enter it.
Proof
Proof. This is the solution to Exercise 136.
Exercise 140 (Decide which problem to hand the solver)
Exercise 140 (Decide which problem to hand the solver) Definition 11 has \(\ninputvars + 1 + N\) unknowns. Definition 12 has \(N\). Neither is uniformly cheaper: which is better depends on \(\ninputvars\) against \(N\).
When \(N \gg \ninputvars\), which problem has fewer unknowns?
Solution 140. The primal problem, with its \(\ninputvars + 1\) non-slack unknowns against the dual’s \(N\).
Exercise 141 (Decide which problem to hand the solver (part 2))
Exercise 141 (Decide which problem to hand the solver (part 2)) Use the setup of Exercise 140.
Is the kernel trick useful in that regime?
Exercise 142 (Decide which problem to hand the solver (part 3))
Exercise 142 (Decide which problem to hand the solver (part 3)) Use the setup of Exercise 140.
When a kernel maps into a \(\nparams\) with \(\nparams \gg N\) – the RBF kernel’s infinite-dimensional case included – which problem is even expressible without \(\vfeatmap\)?
Solution 142. Only the dual. The primal’s unknown is \(w \in \reals^{\nparams}\), which under Definition 14’s whole premise is never written down – under the RBF kernel it is not even finite-dimensional. The dual’s unknown is \(\dualvar \in \reals^N\), which exists and is finite whatever \(\vfeatmap\) is, because Solution 129 showed the optimization only ever touches \(\vfeatmap\) through \(K\).
Exercise 143 (Decide which problem to hand the solver (part 4))
Exercise 143 (Decide which problem to hand the solver (part 4)) Use the setup of Exercise 140.
Theorem 8 found that a kernel SVM has to keep training points at prediction time. Does the primal, fit without a kernel, share that cost?
Solution 143. No. A primal fit without a kernel returns an explicit \(w \in \reals^{\ninputvars}\) and \(b\), a fixed-size summary exactly like Definition 11’s own solution, so prediction is one inner product with \(w\) and needs no training data afterward. The storage cost Theorem 8 found is specifically the cost of working through \(K\) rather than through an explicit \(w\).
Exercise 144 (Decide which problem to hand the solver (part 5))
Exercise 144 (Decide which problem to hand the solver (part 5)) Use the setup of Exercise 140.
Solution 124 found the dual’s per-pair cost scales with \(\nparams\) for an explicit \(\vfeatmap\), and \(K\) removes that dependence. What does the dual’s cost still scale with, that the primal’s does not?
Solution 144. \(N\). Both terms of the dual’s objective are sums over training points – the linear term over \(N\) points once, the quadratic term over \(N \times N\) pairs – so evaluating it costs \(O(N^2)\) kernel evaluations regardless of how cheap each one is, while the primal’s cost per iteration scales with \(\ninputvars\) and \(N\) separately rather than with their product. A large training set makes the dual expensive precisely where the kernel trick made a large \(\nparams\) cost nothing.
When to use which
Exercise 140 works out the two directions in full; this collects the conclusions.
Prefer the primal when \(N \gg \nparams\): it scales with \(N\) once per term rather than once per pair, it returns an explicit \(w\) that needs no training data to use afterward, and it has no access to kernels at all, since a kernel’s whole benefit is a \(\vfeatmap\)-space too large to fit a primal in.
Prefer the dual when \(\nparams \gg N\): it is the only form the kernel trick applies to, since only the dual touches \(\vfeatmap\) solely through inner products, it scales with \(\nparams\) not at all, and it produces the \(\dualvar_i\), which Solution 86 read off to sort the training points into support vectors and non-support vectors – a distinction \(w\) alone does not show. Its cost is the \(O(N^2)\) term Solution 140 found, and the non-parametric storage cost of Theorem 8.
Exercise 145 (Notice what every SVM built so far assumes)
Exercise 145 (Notice what every SVM built so far assumes) Every problem in this chapter has used \(y_{(i)} \in \{-1, +1\}\).
Point to the exact place that assumption enters Definition 11, and say what breaks if a training set instead has \(\outvar_{(i)} \in \{1, 2, 3\}\).
Solution 145. In every constraint, \(y_{(i)}\paren{\dprod{w}{x_{(i)}} + b} \geq 1 - \slack_i\). The product \(y_{(i)} \modmemf{x_{(i)}}\) is read as a signed margin, positive when \(\modmem\) and \(y_{(i)}\) agree in sign, and that reading needs \(y_{(i)} = \pm 1\). With \(y_{(i)} \in \{1, 2, 3\}\) the same product is not a margin at all — multiplying \(\modmemf{x_{(i)}}\) by \(2\) or \(3\) changes its scale for no geometric reason, and the constraint no longer says anything about which side of the hyperplane \(x_{(i)}\) falls on.
Exercise 146 (Notice what every SVM built so far assumes (part 2))
Exercise 146 (Notice what every SVM built so far assumes (part 2)) Use the setup of Exercise 145.
Propose the simplest possible fix: pick two of the three classes, discard every training point belonging to the third, and fit an ordinary binary SVM. What is wrong with this as a solution to the three-class problem?
Solution 146. It discards data, and it only ever answers a question between two of the three classes. Presented with a new point, a classifier fit on classes 1 and 2 has no way to say “this is class 3” — it was never shown a class 3 example and has no notion that one exists. Generalizing this idea to every pair of classes is a real strategy, one-versus-one, but picking one pair and discarding the rest is not. One-versus-one is defined later in this section, in Definition 16.
Exercise 147 (Notice what every SVM built so far assumes (part 3))
Exercise 147 (Notice what every SVM built so far assumes (part 3)) Use the setup of Exercise 145.
A less wasteful idea keeps every training point in every fit, by changing how points get their \(\pm 1\) labels rather than which points are used. Propose one.
Solution 147. Relabel the training set once per class: to fit a classifier for class \(m\), set \(y_{(i)}^{(m)} = +1\) for every point actually labelled \(m\), and \(y_{(i)}^{(m)} = -1\) for every other point, whatever its true class. Every training point takes part in every fit, just with a different label each time.
Definition 15 (One-versus-rest)
Definition 15 (One-versus-rest) One-versus-rest classification fits one binary SVM per class, \(m = 1, \ldots, C\), on the relabelling \(y_{(i)}^{(m)} = +1\) if \(y_{(i)} = m\) and \(-1\) otherwise, and classifies a new point \(x\) by
\[\mathop{\argmax}_m \; \modmem^{(m)}(x) = \mathop{\argmax}_m \; \sumiN \dualvar_i^{(m)} y_{(i)}^{(m)} K\paren{x, x_{(i)}} + b^{(m)}.\]
Example 16 (One-versus-rest on the three origins of the cars)
Example 16 (One-versus-rest on the three origins of the cars) The Auto data [5] record where each car was made: 1 American, 2 European, 3 Japanese. Standardize weight, horsepower, acceleration and year, and use a linear kernel. Fit one SVM per origin with the dual_svm helper of Example 3 at \(C = 1\), relabelling the cars \(+1\) for that origin and \(-1\) for the rest, classify each car by the largest score \(\modmem^{(m)}\), and tabulate the result against the true origin (these are training cars, so the table describes the fit, not performance on new data):
feat_ov = auto_dr[["weight", "horsepower", "acceleration", "year"]].to_numpy(float)
feat_ov = (feat_ov - feat_ov.mean(axis=0)) / feat_ov.std(axis=0, ddof=1)
K_ov = feat_ov @ feat_ov.T # linear kernel
org_ov = auto_dr["origin"].to_numpy()
score_ov = np.zeros((len(org_ov), 3))
for m in (1, 2, 3):
y_m = np.where(org_ov == m, 1.0, -1.0) # origin m versus the rest
alpha_m, b_m = dual_svm(K_ov, y_m, 1.0, tol=1e-8)
score_ov[:, m - 1] = K_ov @ (alpha_m * y_m) + b_m # h^(m)(x) = sum_i alpha_i y_i K(x, x_i) + b
pred_ov = score_ov.argmax(axis=1) + 1 # the class with the largest score
print(pd.crosstab(org_ov, pred_ov, rownames=["origin"], colnames=["predicted"]))predicted 1 2 3
origin
1 235 0 10
2 43 3 22
3 40 0 39feat_ov <- scale(as.matrix(auto_dr[, c("weight", "horsepower", "acceleration", "year")]))
K_ov <- feat_ov %*% t(feat_ov) # linear kernel
org_ov <- auto_dr$origin
score_ov <- sapply(1:3, function(m) {
y_m <- ifelse(org_ov == m, 1, -1) # origin m versus the rest
fit_m <- dual_svm(K_ov, y_m, 1, tol = 1e-8)
drop(K_ov %*% (fit_m$alpha * y_m)) + fit_m$b # h^(m)(x) = sum_i alpha_i y_i K(x, x_i) + b
})
pred_ov <- max.col(score_ov, ties.method = "first") # the class with the largest score
table(origin = org_ov, predicted = factor(pred_ov, levels = 1:3)) predicted
origin 1 2 3
1 235 0 10
2 43 3 22
3 40 0 39One-versus-rest, Definition 15, fit 3 SVMs, each on all 392 cars. It labels 70.7% of the cars with their true origin. The European cars are the hardest: only 3 of the 68 are recovered, against 235 of 245 American and 39 of 79 Japanese cars.
Read
GeeksforGeeks explains one-versus-rest classification [26].
Exercise 148 (Question the argmax rule)
Exercise 148 (Question the argmax rule) Definition 15 classifies \(x\) by which of the \(C\) classifiers gives \(\modmem^{(m)}(x)\) the largest value, not by which one returns \(+1\).
Suppose two classifiers, \(\modmem^{(1)}\) and \(\modmem^{(2)}\), both return a positive value at some point \(\predvar\): \(\predvar\) looks like class 1 to the first fit and like class 2 to the second. What would picking “the first classifier that says \(+1\)” do at such a point, and why is the argmax rule better?
Solution 148. “First classifier that says \(+1\)” would answer class 1 or class 2 depending only on which one happens to be checked first — an arbitrary tie-break presented as a decision. The argmax rule instead asks each classifier not just for a sign but for a signed distance from its own hyperplane, and picks the class whose fit is most confident. That uses information the plain sign discards.
Exercise 149 (Question the argmax rule (part 2))
Exercise 149 (Question the argmax rule (part 2)) Use the setup of Exercise 148.
Is it possible for every \(\modmem^{(m)}(\predvar)\) to be negative at some point \(\predvar\)?
Solution 149. Yes: \(x\) can sit on the wrong side of every one of the \(C\) hyperplanes, if it is genuinely hard to place.
Exercise 150 (Question the argmax rule (part 3))
Exercise 150 (Question the argmax rule (part 3)) Use the setup of Exercise 148.
If so, what does the argmax rule still return there?
Solution 150. The rule still returns whichever \(m\) is least negative — the classifier that was closest to calling \(x\) its own class, even though none of them did. The rule always returns some class; it never refuses to answer.
Exercise 151 (Question the argmax rule (part 4))
Exercise 151 (Question the argmax rule (part 4)) Use the setup of Exercise 148.
\(\modmem^{(1)}\) and \(\modmem^{(2)}\) come from two entirely separate fits, each with its own \(\dualvar^{(m)}\), \(b^{(m)}\), and even its own support vectors. Nothing in Definition 12 ties their scales together. Explain why comparing \(\modmem^{(1)}(\predvar)\) against \(\modmem^{(2)}(\predvar)\) by size is therefore a rough rule, not a guarantee, and name the training-set imbalance Definition 15’s relabelling introduces that could make the rough rule worse: for \(C = 10\) balanced classes, what fraction of the training points does each fit label \(-1\)?
Solution 151. Each \(\modmem^{(m)}\) is the solution of an independent optimization problem, so nothing forces \(\norm{w^{(m)}}_2\) to be the same across \(m\), and \(\modmem^{(m)}(x)\)’s scale depends on it: two classifiers can each be equally confident and still report different-sized numbers, or one can report a large number while being the less trustworthy fit. Picking the largest raw value therefore compares numbers that were never built to be compared, so it is a rough rule that tends to work rather than a rule that is provably correct.
With \(C = 10\) balanced classes, each fit labels \(1/10\) of the training set \(+1\) and the other \(9/10\) of it \(-1\). That imbalance grows with \(C\): at \(C = 100\) each fit sees a training set that is \(99\%\) negative. An SVM fit on such a skew has little reason to place its margin generously toward the minority class, since almost every point it is penalized for misclassifying is already on the \(-1\) side — which is the concrete mechanism behind the standard complaint that one-versus-rest is asymmetric.
Definition 16 (One-versus-one)
Definition 16 (One-versus-one) One-versus-one classification fits one binary SVM for every pair of classes, \(\binom{C}{2} = C(C-1)/2\) of them, each trained on only the points belonging to that pair. A new point is classified by evaluating all \(\binom{C}{2}\) classifiers and taking a majority vote among their predictions [27].
Example 17 (One-versus-one on the three origins of the cars)
Example 17 (One-versus-one on the three origins of the cars) Repeat Example 16 with one-versus-one classification. Fit an SVM for each of the \(\binom{3}{2} = 3\) pairs of origins, each on only the cars of that pair, let every SVM cast a vote for one of its two origins on every car, and give each car the origin with the most votes (a three-way tie, one vote each, goes to the lowest origin):
votes_ov1 = np.zeros((len(org_ov), 3))
for p, q in ((1, 2), (1, 3), (2, 3)):
idx = np.flatnonzero((org_ov == p) | (org_ov == q)) # only the cars of this pair
y_pq = np.where(org_ov[idx] == p, 1.0, -1.0)
alpha_pq, b_pq = dual_svm(K_ov[np.ix_(idx, idx)], y_pq, 1.0, tol=1e-8)
s_pq = K_ov[:, idx] @ (alpha_pq * y_pq) + b_pq # score of every car, not only the pair's
votes_ov1[s_pq > 0, p - 1] += 1
votes_ov1[s_pq <= 0, q - 1] += 1
pred_ov1 = votes_ov1.argmax(axis=1) + 1 # most votes; ties go to the lowest origin
print(pd.crosstab(org_ov, pred_ov1, rownames=["origin"], colnames=["predicted"]))predicted 1 2 3
origin
1 211 7 27
2 31 15 22
3 23 3 53votes_ov1 <- matrix(0, nrow(K_ov), 3)
for (pair in list(c(1, 2), c(1, 3), c(2, 3))) {
idx <- which(org_ov %in% pair) # only the cars of this pair
y_pq <- ifelse(org_ov[idx] == pair[1], 1, -1)
fit_pq <- dual_svm(K_ov[idx, idx], y_pq, 1, tol = 1e-8)
s_pq <- drop(K_ov[, idx] %*% (fit_pq$alpha * y_pq)) + fit_pq$b # score of every car, not only the pair's
votes_ov1[cbind(seq_along(s_pq), ifelse(s_pq > 0, pair[1], pair[2]))] <-
votes_ov1[cbind(seq_along(s_pq), ifelse(s_pq > 0, pair[1], pair[2]))] + 1
}
pred_ov1 <- max.col(votes_ov1, ties.method = "first") # most votes; ties go to the lowest origin
table(origin = org_ov, predicted = factor(pred_ov1, levels = 1:3)) predicted
origin 1 2 3
1 211 7 27
2 31 15 22
3 23 3 53One-versus-one, Definition 16, trained 3 SVMs on 313, 324 and 147 cars, fewer than the 392 that each one-versus-rest SVM used. It labels 71.2% of the cars with their true origin, against 70.7% for one-versus-rest. The vote was tied three ways for 9 cars.
Exercise 152 (Compare the two strategies’ costs)
Exercise 152 (Compare the two strategies’ costs) Definition 15 fits \(C\) classifiers. Definition 16 fits \(C(C-1)/2\).
For \(C = 3\), how many classifiers does each strategy fit?
Solution 152. At \(C = 3\): one-versus-rest fits \(3\), one-versus-one fits \(\binom{3}{2} = 3\) — equal.
Exercise 153 (Compare the two strategies’ costs (part 2))
Exercise 153 (Compare the two strategies’ costs (part 2)) Use the setup of Exercise 152.
How many classifiers does each strategy fit for \(C = 8\)?
Solution 153. At \(C = 8\): one-versus-rest fits \(8\), one-versus-one fits \(\binom{8}{2} = 28\). The two agree only at \(C = 3\); one-versus-one grows much faster afterward.
Exercise 154 (Compare the two strategies’ costs (part 3))
Exercise 154 (Compare the two strategies’ costs (part 3)) Use the setup of Exercise 152.
Definition 16’s classifiers each train on the points belonging to only two classes, while Definition 15’s train on the whole dataset every time. Assuming the \(N\) training points are spread evenly across the \(C\) classes, how many points does one one-versus-one fit see?
Solution 154. \(2N/C\): each classifier trains on the points from exactly two of the \(C\) classes, and each class contributes \(N/C\) points on average.
Exercise 155 (Compare the two strategies’ costs (part 4))
Exercise 155 (Compare the two strategies’ costs (part 4)) Use the setup of Exercise 152.
Exercise 124 found the dual’s cost scales like \(O(N^2)\) in the number of training points it is fit on. Using Exercise 153’s answer, and treating \(C\) as fixed while \(N\) grows, compare how the total cost across all classifiers scales with \(N\) for each strategy.
Solution 155. One-versus-rest fits \(C\) classifiers, each on all \(N\) points, for a total cost of \(C \cdot O(N^2) = O(N^2)\), since \(C\) is fixed.
One-versus-one fits \(\binom{C}{2}\) classifiers, each on \(2N/C\) points, for a total cost of
\[ \begin{aligned} \binom{C}{2} \cdot O\paren{(2N/C)^2} &= O\paren{C(C-1) \cdot N^2/C^2} \\ &= O(N^2) \end{aligned} \]
as well, since \(C\) is again fixed and \((C-1)/C \to 1\) contributes no growth in \(N\).
Both scale the same way in \(N\) for fixed \(C\): the \(O(N^2)\) per-fit cost dominates either way, and one-versus-one’s extra fits are exactly compensated by each one seeing fewer points. The difference in expense at a given \(C\) (Solution 153) is therefore about the constant in front, not about how either strategy scales as the dataset grows.
Exercise 156 (Compare the two strategies’ costs (part 5))
Exercise 156 (Compare the two strategies’ costs (part 5)) Use the setup of Exercise 152.
One-versus-one needs \(\binom{C}{2}\) predictions, each choosing between two specific classes, and a new point can end up with votes split across three or more classes with no clear winner. Propose a rule for breaking a tie.
Solution 156. Any tie-breaking rule has to say something when the simple vote does not decide, so a common choice is to fall back to Definition 15’s own argmax: compute \(\modmem^{(m)}(x)\) for the tied classes only, using each class’s one-versus-rest classifier, and take the largest. This uses one-versus-one’s votes when they decide the question and one-versus-rest’s confidence score only to resolve what one-versus-one left open, rather than committing to one strategy exclusively.
Exercise 157 (Fit one classifier of a one-versus-rest scheme by hand)
Exercise 157 (Fit one classifier of a one-versus-rest scheme by hand) A three-class training set has one point per class:
\[\mathcal{X} = \set{ \paren{[3, 0], 1},\; \paren{[-1, 0], 2},\; \paren{[-3, 2], 3} }.\]
Find \(w\), \(b\) and \(M\) for the hard-margin (\(C = \infty\)) classifier that Definition 15 fits for class \(1\).
Write down the relabelling this classifier trains on: which point gets \(\outvar = +1\), and which get \(\outvar = -1\)?
Solution 157. \(\outvar = +1\) for \([3, 0]\), and \(\outvar = -1\) for both \([-1, 0]\) and \([-3, 2]\), per Definition 15’s relabelling for \(m = 1\).
Exercise 158 (Fit one classifier of a one-versus-rest scheme by hand (part 2))
Exercise 158 (Fit one classifier of a one-versus-rest scheme by hand (part 2)) Use the setup of Exercise 157.
With only one positive point, the optimal separating hyperplane is the perpendicular bisector between it and whichever negative point is nearest to it. Compute the distance from the class-1 point to each negative point, and identify the two support vectors.
Solution 158. Distance from \([3, 0]\) to \([-1, 0]\):
\[ \begin{aligned} \sqrt{(3-(-1))^2 + (0-0)^2} &= \sqrt{16} \\ &= 4. \end{aligned} \]
Distance from \([3, 0]\) to \([-3, 2]\):
\[ \begin{aligned} \sqrt{(3-(-3))^2 + (0-2)^2} &= \sqrt{36 + 4} \\ &= \sqrt{40} \\ &\approx 6.32. \end{aligned} \]
\([-1, 0]\) is closer, so it and \([3, 0]\) are the two support vectors — provided the resulting hyperplane does not cut inside \([-3, 2]\)’s margin, which Solution 162 checks.
Exercise 159 (Fit one classifier of a one-versus-rest scheme by hand (part 3))
Exercise 159 (Fit one classifier of a one-versus-rest scheme by hand (part 3)) Use the setup of Exercise 157.
The margin \(M\) is half the distance between the two support vectors. Compute it.
Solution 159. \[ \begin{aligned} M &= 4/2 \\ &= 2. \end{aligned} \]
Exercise 160 (Fit one classifier of a one-versus-rest scheme by hand (part 4))
Exercise 160 (Fit one classifier of a one-versus-rest scheme by hand (part 4)) Use the setup of Exercise 157.
Theorem 3, under the scale Theorem 2 fixed, ties \(M\) to \(\norm{w}_2\) by \(M = 1/\norm{w}_2\). Use that to find \(\norm{w}_2\).
Solution 160. \[ \begin{aligned} \norm{w}_2 &= 1/M \\ &= 1/2. \end{aligned} \]
Exercise 161 (Fit one classifier of a one-versus-rest scheme by hand (part 5))
Exercise 161 (Fit one classifier of a one-versus-rest scheme by hand (part 5)) Use the setup of Exercise 157.
\(w\) points along the line joining the two support vectors, so \(w\) is a positive multiple of the vector from the negative support vector to the positive one. Use Exercise 160’s \(\norm{w}_2\) to find \(w\) itself. Then the midpoint of the two support vectors lies on the hyperplane, where \(\modmemf{\predvar} = 0\); use it to find \(b\).
Solution 161. The vector from \([-1, 0]\) to \([3, 0]\) is \([4, 0]\), so \(w = c[1, 0]\) for some \(c > 0\). Then \(\norm{w}_2 = c = 1/2\), and \(w = \sb{\tfrac{1}{2}, 0}\).
The midpoint of the two support vectors is \([1, 0]\). It lies on the hyperplane, so \(\modmemf{[1, 0]} = 0\):
\[ \begin{aligned} \tp{w} [1, 0] + b &= \tfrac{1}{2} + b \\ &= 0 \end{aligned} \quad\Longrightarrow\quad b = -\tfrac{1}{2}. \]
Checking the class-1 support vector’s constraint at equality:
\[ \begin{aligned} y \, \modmemf{[3, 0]} &= \tfrac{1}{2}(3) - \tfrac{1}{2} \\ &= 1, \end{aligned} \]
as it should.
Exercise 162 (Fit one classifier of a one-versus-rest scheme by hand (part 6))
Exercise 162 (Fit one classifier of a one-versus-rest scheme by hand (part 6)) Use the setup of Exercise 157.
Check your answer: does the class-3 point satisfy its constraint with strict inequality, confirming it is not a support vector for this classifier?
Solution 162. For \([-3, 2]\), \(y = -1\) and
\[ \begin{aligned} \modmemf{[-3, 2]} &= \tfrac{1}{2}(-3) + 0(2) - \tfrac{1}{2} \\ &= -2, \end{aligned} \qquad \begin{aligned} y \, \modmemf{x} &= \paren{-1}\paren{-2} \\ &= 2. \end{aligned} \]
Since \(2 > 1\), the constraint is satisfied with strict inequality, confirming \([-3, 2]\) is not a support vector and the choice in Solution 158 was right.
Exercise 163 (Weigh what an SVM is good at against its drawbacks)
Exercise 163 (Weigh what an SVM is good at against its drawbacks) Looking back over the chapter:
name three properties that make the SVM attractive to use;
Solution 163. In favor:
\(C\) is a direct, interpretable handle on overfitting. It is the cost of one unit of slack, and raising it narrows the margin while lowering it widens it, so a single scalar moves the model along the whole range from “tolerate nothing” to “tolerate almost anything”.
The kernel decouples the shape of the decision boundary from the cost of computing it. Swapping the linear kernel for an RBF kernel changes what the model can express without changing the optimization problem being solved.
The problem is convex, so every local optimum is a global one, and there is no dependence on where the solver started. The \(w\) that comes back is unique (Solution 69), though \(b\) and the slack need not be.
Exercise 164 (Weigh what an SVM is good at against its drawbacks (part 2))
Exercise 164 (Weigh what an SVM is good at against its drawbacks (part 2)) Use the setup of Exercise 163.
name three that make it costly or limited.
Solution 164. Against:
\(C\), the kernel, and the kernel’s own parameters (such as the RBF’s \(\bandwidth\)) are all hyperparameters with no default that works everywhere, so fitting an SVM means running a search over them rather than a single fit.
The formulation is binary. Multiclass problems have to be decomposed into binary ones, and every scheme for doing so has a drawback.
The fitted model is hard to read. With a non-linear kernel there is no \(w\) to inspect, only the support vectors and their coefficients (Theorem 8), and “this point resembles those training points” is a weaker explanation than a coefficient per feature.
James et al. [5], Chapter 9
Hastie et al. [28], Chapter 12
Zhou [29], Support Vector Machines — slides on An Introduction to Statistical Learning, Chapter 9, with an interactive demonstration and code in R
Starmer [30], on support vector classifiers and machines — an illustrated walk-through with little algebra
Lange [31], Section 17.5 — an introduction to reproducing kernel Hilbert spaces, the setting behind kernel methods