III-32 · Maximum-Margin Classification
Find the widest defensible gap
Solve a separating hyperplane from labeled observations, then measure its margins and recognize when no hard separation exists.
Part VII · margin laboratory
Solve the widest separating gap
Hand-authored synthetic labeled observations; no seed or random draws. Edits change the fitted data. The same numerical result drives the plot, equations, ledger and diagnostics.
Drag a handle; arrows move 0.1, Shift + arrow 0.5. Pointer edits snap to 0.1 within ±5. Numeric entries keep finer precision. Select coincident points to bring their handles forward. Scroll outside handles.
Hard fit certified within displayed diagnostics.
Frame 1 / 1. Editing starts from this displayed frame.
- X / y / α shapesBatch rows; individual x and linear w are 2 × 1 columns.
- 4 × 2 / 4 × 1 / 4 × 1
- StatusHard fit certified within displayed diagnostics.
- solved
- w / b
- [0.66667, −0.33333] / 2.776e-17
- Norm² / half-marginNonlinear norms/margins refer to feature space; zero norm has no distance.
- 0.55556 / 1.34164
- Primal / dual / gapSum hinge convention; no division by n. Training accuracy is a different metric.
- 0.27778 / 0.27778 / 0
- KKT / equality / bounds residual
- 0 / 1.388e-17 / 0
- Pair steps / capHard fit is geometric, not iterative. Soft/kernel solutions are approximate.
- 0 / 1200
| ID / label | f(x) | Decision | y f(x) | ξ = hinge | Signed distance | α | Support / on margin |
|---|---|---|---|---|---|---|---|
| a / -1 | −1 | -1 | 1 | 0 | −1.34164 | 0 | No / Yes |
| b / -1 | −1 | -1 | 1 | 0 | −1.34164 | 0.27778 | Yes / Yes |
| c / 1 | 1 | 1 | 1 | 0 | 1.34164 | 0.16667 | Yes / Yes |
| d / 1 | 1 | 1 | 1 | 0 | 1.34164 | 0.11111 | Yes / Yes |
solved. Hard fit certified within displayed diagnostics. Objective 0.27778, KKT residual 0, gap 0. Weights 0.66667, −0.33333, intercept 2.776e-17.
Start with the gap, not a guessed line
Drag point b toward the positive class. The line is recomputed from the observations: its normal w, intercept b, constraints and distances change together. The point ID b and the intercept b are different objects; the ledger labels each explicitly. Select anchor data for the simplest exact example. Select overlap data or coincident data to see a failed assumption: opposite classes cannot always be separated.
Many lines can separate two clouds. Maximum-margin classification chooses the one with the largest clearance to the nearest labeled observations. Clearance measures robustness to movement in the supplied feature metric; it is not a probability, a guarantee of future accuracy, or a claim about causal importance. Scaling a feature changes that metric and can change the answer.
Define the model and its shapes
A sample x and weight w are mathematical 2×1 columns. The laboratory stores n samples as rows of X, an n×2 matrix, and labels y as an n×1 column with entries −1 and +1. The scalar intercept is separate from w:
Positive scores predict +1, negative scores −1. Exactly zero is an explicit tie, recorded as decision 0. The zero set is the model boundary. For nonzero w, it is a line perpendicular to w. We do not penalize the intercept. Training accuracy counts correct signs; the optimization objective controls margin geometry instead.
The functional margin of observation i is yi f(xi). It has no fixed unit: multiplying w and b by a positive constant preserves the boundary and predictions while multiplying functional margins. Fix the model’s scale by requiring the nearest functional margins to equal one. The geometric signed distance to the boundary is f(x)/‖w‖, and the label-adjusted geometric margin is yi f(xi)/‖w‖.
Derive the maximum-margin objective
The parallel lines f=−1 and f=+1 are each 1/‖w‖ away from f=0. Their total separation is 2/‖w‖. Maximizing this gap is equivalent to minimizing the squared normal length under the normalized constraints:
The factor 1/2 simplifies derivatives. It is not a mean over samples. A solution needs strict linear separability before scale normalization; overlapping class convex hulls make the constraints infeasible. Opposite labels at the same coordinate directly require f(x)≥1 and f(x)≤−1 at once. No finite w,b can satisfy both.
Introduce nonnegative multipliers αi and form the Lagrangian. Stationarity with respect to w and the unpenalized intercept gives
Substitution gives the concave dual:
Complementarity is αi(yi f(xi)−1)=0. A positive multiplier requires an active margin constraint at an optimum. The converse need not hold: duplicate or redundant active constraints can have zero multiplier in one optimal representation. The ring shows by the solver’s diagnostic convention; the ledger’s on-margin flag independently tests |yi f−1|≤2×10⁻⁵. These numerical classifications do not redefine mathematical support.
Work the two-point optimum by hand
Take negative x−=[−1,0]ᵀ and positive x+=[1,0]ᵀ. The constraints are w1−b≥1 and w1+b≥1. Adding gives w1≥1. Choosing w2=0 minimizes the norm; w1=1 forces b=0.
The scores are −1 and +1, signed distances −1 and +1, and both label-adjusted margins are one. The half-margin is one and full gap two. The primal is 1/2. The dual is α−+α+−‖w‖²/2=1−1/2=1/2. Equality holds because −α−+α+=0. This is an independently hand-derived fixture, not output copied from the program.
If the samples move to [−2,0] and [2,0], w=[1/2,0], b=0, half-margin two, and each α=1/8. Coordinate scale and geometric margin change, while functional margins remain one under normalization.
How the bounded laboratory solves hard margins
The implementation first builds the two class convex hulls in the input plane. If they intersect, including crossing edges, containment or coincident opposite points, it reports infeasibility and draws no fitted model. If they are disjoint, let n and p be their closest points, with δ=p−n. Supporting planes perpendicular to δ touch those hulls, so
Endpoint-to-segment projections enumerate the shortest hull distance. Barycentric weights of the closest segment points distribute the common dual mass 2/‖δ‖² among their observations. This gives an explicit dual certificate; it is not merely a visually plausible separator. The result reconstructs all training scores, constraints, primal and dual values and checks KKT, equality, nonnegative coefficients and gap before allowing a line to be displayed.
The API is intentionally two-dimensional and limited to 2–12 rows with both labels and coordinates in [−5,5]. This geometric method does not extend automatically to higher dimensions. Orientation signs use an exact dyadic fallback on the original binary64 coordinates. Closest-point projections and fitted coefficients still round; even an exactly separable configuration can yield numerical unavailability or diagnostic failure. A distance that cannot be squared or inverted representably is unavailable. No failed hard solution is displayed as fitted.
Execute the actual Python and NumPy
The imported source is the canonical reference. With no piped JSON, its CLI uses the exact anchor above. A full request supplies mode, points with unique IDs/x/y, C and kernel configuration; hard/soft modes force the linear kernel but validate all fields. JSON errors, malformed shapes, Booleans and unrepresentable arithmetic return a structured error and nonzero exit.
"""Canonical bounded two-feature SVM, Python + NumPy. Owner executes checks.
X stores n×2 rows; y/alpha are serialized columns. No randomness. Hard margin
uses closest convex hulls; soft/kernel uses exact feasible pair dual steps.
"""
import json
from fractions import Fraction
import math
import sys
import numpy as np
EPS = 1e-9
KKT_TOL = 2e-5
GAP_TOL = 1e-5
MAX_STEPS = 1200
def real(v, lo=-math.inf, hi=math.inf):
if isinstance(v, (bool, np.bool_)) or not isinstance(v, (int, float, np.integer, np.floating)):
raise ValueError("Expected a finite real number, not a Boolean.")
try:
x = float(v)
except (OverflowError, ValueError) as error:
raise ValueError("Number cannot be represented in binary64.") from error
if not math.isfinite(x) or not lo <= x <= hi:
raise ValueError("Number outside the finite supported range.")
return x
def finite(v):
if not math.isfinite(v):
raise ValueError("Computed arithmetic is not representable.")
return v
def mul(a, b):
v = finite(a * b)
if a != 0 and b != 0 and v == 0:
raise ValueError("Nonzero product underflows binary64.")
return v
def dot(a, b):
return finite(mul(a[0], b[0]) + mul(a[1], b[1]))
def sub(a, b):
return [finite(a[0] - b[0]), finite(a[1] - b[1])]
def validate(s):
if not isinstance(s, dict) or s.get("mode") not in ("hard", "soft", "kernel"):
raise ValueError("Choose hard, soft or kernel mode.")
points = s.get("points")
if not isinstance(points, list) or not 2 <= len(points) <= 12:
raise ValueError("Use 2–12 dense observations.")
ids = set()
for p in points:
if not isinstance(p, dict) or not isinstance(p.get("id"), str) or not p["id"].strip() or p["id"] in ids:
raise ValueError("Observations require unique nonempty IDs.")
ids.add(p["id"])
if not isinstance(p.get("x"), (list, tuple)) or len(p["x"]) != 2:
raise ValueError("Each observation needs exactly two coordinates.")
for x in p["x"]:
real(x, -5, 5)
if real(p.get("y")) not in (-1, 1):
raise ValueError("Labels must be −1 or +1.")
if len({p["y"] for p in points}) != 2:
raise ValueError("Both labels are required.")
real(s.get("C"), .01, 20)
k = s.get("kernel")
if not isinstance(k, dict) or k.get("kind") not in ("linear", "polynomial", "rbf"):
raise ValueError("Unknown kernel.")
real(k.get("gamma"), .05, 2)
real(k.get("coef0"), 0, 2)
d = real(k.get("degree"), 1, 4)
if not d.is_integer():
raise ValueError("Polynomial degree must be integral.")
return dict(s, points=[dict(id=p["id"], x=[real(x) for x in p["x"]], y=real(p["y"])) for p in points],
C=real(s["C"]), kernel=dict(k, gamma=real(k["gamma"]), coef0=real(k["coef0"]), degree=int(d)))
def kernel_value(a, b, k):
"""Validate both dense query vectors and all parameters before family dispatch."""
if not isinstance(a, (list, tuple)) or not isinstance(b, (list, tuple)) or len(a) != 2 or len(b) != 2:
raise ValueError("Kernel vectors need two dense coordinates.")
a, b = [real(v, -6, 6) for v in a], [real(v, -6, 6) for v in b]
if not isinstance(k, dict) or k.get("kind") not in ("linear", "polynomial", "rbf"):
raise ValueError("Unknown kernel.")
gamma, coef0, degree = real(k.get("gamma"), .05, 2), real(k.get("coef0"), 0, 2), real(k.get("degree"), 1, 4)
if not degree.is_integer():
raise ValueError("Polynomial degree must be integral.")
k = dict(k, gamma=gamma, coef0=coef0, degree=int(degree))
if k["kind"] == "linear":
return dot(a, b)
if k["kind"] == "polynomial":
base = finite(mul(k["gamma"], dot(a, b)) + k["coef0"])
result = 1.0
for _ in range(k["degree"]):
result = mul(result, base)
return result
delta = sub(a, b)
value = math.exp(-mul(k["gamma"], dot(delta, delta)))
if value == 0:
raise ValueError("RBF similarity underflows binary64.")
return finite(value)
def hinge(margin):
m = real(margin)
return {"loss": max(0, finite(1 - m)), "subgradient": -1 if m < 1 else 0}
def orientation(a, b, c):
"""Filtered sign, with exact fallback from original binary64 coordinates."""
ux, uy = b[0] - a[0], b[1] - a[1]
vx, vy = c[0] - a[0], c[1] - a[1]
left, right = ux * vy, uy * vx
determinant = left - right
error = 8 * sys.float_info.epsilon * (abs(left) + abs(right))
if abs(left) >= sys.float_info.min and abs(right) >= sys.float_info.min and abs(determinant) > error:
return 1 if determinant > 0 else -1
ax, ay, bx, by, cx, cy = (Fraction.from_float(float(v)) for p in (a, b, c) for v in p)
exact = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)
return (exact > 0) - (exact < 0)
def hull(points, label):
indices = sorted((i for i, p in enumerate(points) if p["y"] == label), key=lambda i: tuple(points[i]["x"]))
unique = []
for i in indices:
if not unique or points[i]["x"] != points[unique[-1]]["x"]:
unique.append(i)
def chain(seq):
out = []
for i in seq:
while len(out) >= 2 and orientation(points[out[-2]]["x"], points[out[-1]]["x"], points[i]["x"]) <= 0:
out.pop()
out.append(i)
return out
return unique if len(unique) <= 2 else chain(unique)[:-1] + chain(unique[::-1])[:-1]
def edges(h):
return [(i, h[(j + 1) % len(h)]) for j, i in enumerate(h)]
def inside(x, h, points):
return len(h) >= 3 and all(orientation(points[i]["x"], points[j]["x"], x) >= 0 for i, j in edges(h))
def on_segment(x, a, b):
return orientation(a, b, x) == 0 and all(min(a[j], b[j]) <= x[j] <= max(a[j], b[j]) for j in range(2))
def intersects(a, b, c, d):
u, v = orientation(a, b, c), orientation(a, b, d)
r, t = orientation(c, d, a), orientation(c, d, b)
return ((u < 0 < v or v < 0 < u) and (r < 0 < t or t < 0 < r)) or any((on_segment(c, a, b), on_segment(d, a, b), on_segment(a, c, d), on_segment(b, c, d)))
def hard_fit(points):
neg, pos = hull(points, -1), hull(points, 1)
if any(inside(points[i]["x"], pos, points) for i in neg) or any(inside(points[i]["x"], neg, points) for i in pos):
return None
best = None
for ni, nj in edges(neg):
for pi, pj in edges(pos):
a, b, c, d = [points[i]["x"] for i in (ni, nj, pi, pj)]
if intersects(a, b, c, d):
return None
for source, i, j in ((ni, pi, pj), (nj, pi, pj), (pi, ni, nj), (pj, ni, nj)):
x, u, v = points[source]["x"], points[i]["x"], points[j]["x"]
delta = sub(v, u)
length = dot(delta, delta)
t = max(0, min(1, dot(sub(x, u), delta) / length)) if length else 0
q = [finite(u[z] + mul(t, delta[z])) for z in range(2)]
diff = sub(q, x)
distance2 = dot(diff, diff)
if best is None or distance2 < best[0]:
best = (distance2, source, i, j, t, q)
distance2, source, i, j, t, q = best
if distance2 == 0:
raise ValueError("Closest hull distance is numerically unresolved.")
mass = finite(2 / distance2)
y = points[source]["y"]
direction = sub(points[source]["x"], q) if y == 1 else sub(q, points[source]["x"])
w = [mul(mass, d) for d in direction]
midpoint = [finite((points[source]["x"][z] + q[z]) / 2) for z in range(2)]
alpha = [0.0] * len(points)
alpha[source] += mass
alpha[i] += mul(mass, 1 - t)
alpha[j] += mul(mass, t)
return alpha, -dot(w, midpoint), w
def soft_fit(points, K, C):
n = len(points)
y = [p["y"] for p in points]
alpha, g = [0.0] * n, [0.0] * n
iterations = 0
for step in range(MAX_STEPS):
best = None
for i in range(n):
for j in range(i + 1, n):
di, dj = y[i], -y[j]
li, ui = (-alpha[i], C - alpha[i]) if di == 1 else (alpha[i] - C, alpha[i])
lj, uj = (-alpha[j], C - alpha[j]) if dj == 1 else (alpha[j] - C, alpha[j])
lo, hi = max(li, lj), min(ui, uj)
if hi <= lo:
continue
slope = finite(y[i] - y[j] - (g[i] - g[j]))
curvature = finite(K[i][i] + K[j][j] - 2 * K[i][j])
if curvature < -1e-10:
raise ValueError("Kernel curvature contradicts PSD within the numerical allowance.")
candidates = [lo, hi] if curvature <= 0 else [max(lo, min(hi, slope / curvature))]
for t in candidates:
gain = finite(mul(slope, t) - .5 * mul(curvature, mul(t, t)))
if gain > 1e-12 and (best is None or gain > best[0]):
best = (gain, i, j, t)
if best is None:
break
_, i, j, t = best
alpha[i] = finite(alpha[i] + y[i] * t)
alpha[j] = finite(alpha[j] - y[j] * t)
for z in range(n):
g[z] = finite(g[z] + mul(t, K[z][i] - K[z][j]))
iterations = step + 1
# Reconstruct instead of letting accumulated gradient rounding own diagnostics.
g = [finite(sum(mul(alpha[j] * y[j], K[i][j]) for j in range(n))) for i in range(n)]
free = [y[i] - g[i] for i in range(n) if EPS < alpha[i] < C - EPS]
if free:
b = finite(sum(free) / len(free))
else:
lower, upper = -math.inf, math.inf
for i in range(n):
target = y[i] - g[i]
if (y[i] == 1 and alpha[i] <= EPS) or (y[i] == -1 and alpha[i] >= C - EPS):
lower = max(lower, target)
else:
upper = min(upper, target)
b = finite((lower + upper) / 2)
return alpha, b, iterations
def svm(request):
s = validate(request)
points, C = s["points"], s["C"]
n = len(points)
k = s["kernel"] if s["mode"] == "kernel" else dict(s["kernel"], kind="linear")
K = np.array([[kernel_value(a["x"], b["x"], k) for b in points] for a in points], dtype=float).tolist()
if s["mode"] == "hard":
fitted = hard_fit(points)
if fitted is None:
return dict(status="infeasible", reason="Class convex hulls intersect; hard-margin constraints are infeasible.", gram=K, rows=[], alpha=[], w=None, b=None, norm2=None, halfMargin=None, primal=None, dual=None, gap=None, kkt=None, equality=None, bounds=None, iterations=0)
alpha, b, w = fitted
iterations = 0
else:
alpha, b, iterations = soft_fit(points, K, C)
w = [finite(sum(mul(alpha[i] * p["y"], p["x"][z]) for i, p in enumerate(points))) for z in range(2)] if k["kind"] == "linear" else None
scores = [finite(sum(mul(alpha[j] * points[j]["y"], K[i][j]) for j in range(n)) + b) for i in range(n)]
norm2 = finite(sum(mul(alpha[i] * points[i]["y"], finite(scores[i] - b)) for i in range(n)))
if norm2 < 0:
raise ValueError("Computed feature norm is negative; numerical fit unavailable.")
norm = math.sqrt(norm2)
rows, residual = [], 0.0
for i, p in enumerate(points):
margin = mul(p["y"], scores[i])
xi = max(0, finite(1 - margin))
bound = s["mode"] != "hard" and alpha[i] >= C - EPS
r = max(0, 1 - margin) if alpha[i] <= EPS else max(0, margin - 1) if bound else abs(margin - 1)
residual = max(residual, r)
rows.append(dict(id=p["id"], score=scores[i], decision=1 if scores[i] > 0 else -1 if scores[i] < 0 else 0, margin=margin, slack=xi, hinge=xi, signedDistance=finite(scores[i] / norm) if w is not None and norm > 0 else None, support=alpha[i] > EPS, onMargin=abs(margin - 1) <= KKT_TOL, alpha=alpha[i]))
primal = finite(.5 * norm2 + (0 if s["mode"] == "hard" else C * sum(r["hinge"] for r in rows)))
dual = finite(sum(alpha) - .5 * norm2)
gap = finite(primal - dual)
equality = abs(finite(sum(alpha[i] * p["y"] for i, p in enumerate(points))))
bounds = max([0] + [-a for a in alpha] + ([] if s["mode"] == "hard" else [a - C for a in alpha]))
feasible = s["mode"] != "hard" or max(r["slack"] for r in rows) <= KKT_TOL
good = feasible and residual <= KKT_TOL and abs(gap) <= GAP_TOL * (1 + primal) and equality <= 1e-7 and bounds <= EPS
return dict(status=("solved" if s["mode"] == "hard" else "approximate") if good else "failed", reason="Hard fit certified within displayed diagnostics." if good and s["mode"] == "hard" else "Approximate dual fit; inspect KKT and primal–dual gap." if good else "Diagnostic failure or iteration cap; no fitted boundary is displayed.", gram=K, rows=rows, alpha=alpha, w=w, b=b, norm2=norm2, halfMargin=finite(1 / norm) if norm > 0 else None, primal=primal, dual=dual, gap=gap, kkt=residual, equality=equality, bounds=bounds, iterations=iterations)
def decision(request, result, x):
"""Actual kernel decision; never input-space distance for nonlinear kernels."""
s = validate(request)
if result.get("status") not in ("solved", "approximate") or result.get("b") is None or len(result.get("alpha", [])) != len(s["points"]):
raise ValueError("A successful fit is required for a decision.")
k = s["kernel"] if s["mode"] == "kernel" else dict(s["kernel"], kind="linear")
return finite(sum(mul(real(a) * p["y"], kernel_value(p["x"], x, k)) for a, p in zip(result["alpha"], s["points"])) + real(result["b"]))
DEFAULT = dict(mode="hard", C=1, kernel=dict(kind="linear", gamma=1, coef0=1, degree=2), points=[dict(id="a", x=[-1, 0], y=-1), dict(id="b", x=[1, 0], y=1)])
if __name__ == "__main__":
try:
raw = sys.stdin.read()
print(json.dumps(svm(json.loads(raw) if raw.strip() else DEFAULT), allow_nan=False))
except (ValueError, TypeError, KeyError, OverflowError) as error:
print(json.dumps({"error": str(error)}), file=sys.stderr)
sys.exit(2)Investigate the explorer
Reset, then replay the feasibility cases. Each frame is an immutable input snapshot and selects its own rederived numerical result. At the overlap frame, choose a point and edit it: the next experiment starts from that displayed snapshot and exits replay. The numeric editor preserves finer precision than the pointer’s 0.1 lattice. Arrow keys give an equivalent path, and the point selector makes coincident observations independently reachable.
Common mistakes and limits
A large raw f(x) is not a large geometric distance unless you divide by the normal length. A point on f=0 is a decision tie, not a support margin point. A ring is a coefficient property, not simply a location on a drawn line. Maximizing training clearance alone does not establish generalization. Outliers can dominate hard separation, and one conflicting label can destroy feasibility.
Five graded investigations
Connections and summary
Book II’s norms, dot products and projections explain the distance formula; convex constraints explain the optimization. You can now distinguish scores, functional margins, distances, support coefficients and feasibility. III-33 permits violations at an explicit cost and shows why a classifier can be useful even when hard constraints cannot hold.