Skip to content
Computational Lab.

Support Vector Machine

The widest street between the classes.

Advanced / classification / optimization / kernel-method

A linear classifier chooses the boundary that leaves the widest margin; the kernel trick lets that same trainer draw curved boundaries in the original space. This one trains online with kernelized Pegasos - subgradient descent on the hinge loss - so accuracy, the margin, and the ringed margin-active points evolve as you add labeled points.

Tagged: SVM, hinge loss, Pegasos, RBF kernel, margin

Live simulation

Click to add labeled points (tool selector); the margin retrains online.

Speed

Click to add labeled points (tool selector); the margin retrains online.

Mathematics

A linear classifier separates classes with the hyperplane that maximizes the margin: minimize ½‖w‖² subject to yᵢ(w·xᵢ + b) ≥ 1. The soft-margin version allows violations with a hinge penalty, and the kernel trick replaces inner products with κ(x, z) so the same trainer draws non-linear boundaries.

minimize ½‖w‖² + C Σ max(0, 1 − yᵢ f(xᵢ))

kernelized: f(x) = Σⱼ αⱼ yⱼ κ(xⱼ, x), κ_RBF = exp(−γ‖x − z‖²)

Pegasos: on violation, αᵢ ← αᵢ + 1/(λt); project ‖α‖ ≤ 1/√λ

The trainer is kernelized Pegasos: stochastic subgradient steps on the hinge loss with a projection, one pass per epoch over a seeded shuffle. Under a subgradient method there are no exact support vectors, so the ringed points are the honest equivalent - the margin-active set |y f(x)| < 1, the samples the hinge still cares about. Toggle linear to RBF on overlapping blobs and watch the boundary bend without a single change to the trainer.

How it works

Points live in arrays; the dual coefficients α live in one float array and the decision function sums the kernel-weighted labels on the fly. A constant is absorbed into the kernel (κ + 1) so no separate bias is needed. The decision field re-evaluates on a 96×48 grid every twelve ticks and after any data edit; accuracy and the margin-active count come from the same pass.

The pointer adds labeled points (tool selector) or erases the nearest - training continues online, so the boundary answers immediately.

Implementation

src/engine/experiments/svm.ts · 292 lines · the module running above

TypeScript · fixed-timestep engine

1import { BaseExperiment } from "../core/base-experiment";
2import type { ColorLUT } from "../render/colormaps";
3import type { ParameterDef, PointerState, ThemeColors } from "../core/types";
4import { divergingFor } from "../render/diverging-cache";
5
6const CAPACITY = 220;
7const FIELD_W = 96;
8
9/**
10 * Max-margin classification trained online with kernelized Pegasos
11 * (subgradient descent on the hinge loss). Linear and RBF kernels share the
12 * exact same trainer - only the inner product changes - and the margin-active
13 * points (|y f(x)| < 1) are the honest stand-in for support vectors under a
14 * subgradient method.
15 */
16export class SvmExperiment extends BaseExperiment {
17 readonly id = "support-vector-machine";
18
19 private xs = new Float32Array(CAPACITY);
20 private ys = new Float32Array(CAPACITY);
21 private labels = new Float32Array(CAPACITY);
22 private alphas = new Float64Array(CAPACITY);
23 private count = 0;
24 private rounds = 0;
25 private field = new Float32Array(FIELD_W * Math.floor(FIELD_W / 2));
26 private fieldValid = false;
27 private fieldTick = 0;
28 private accuracy = 0;
29 private marginActive = 0;
30 private pointer = { x: 0, y: 0, down: false, inside: false };
31 private lastCell = { x: -1, y: -1 };
32 private image: ImageData | null = null;
33 private scratch: HTMLCanvasElement | null = null;
34
35 protected params(): ParameterDef[] {
36 return [
37 {
38 key: "kernel",
39 label: "Kernel",
40 options: [
41 { value: "linear", label: "Linear" },
42 { value: "rbf", label: "RBF (Gaussian)" },
43 ],
44 defaultValue: "linear",
45 },
46 { key: "gamma", label: "RBF gamma", min: 1, max: 30, step: 0.5, defaultValue: 8 },
47 { key: "lambda", label: "Regularization lambda", min: 0.001, max: 0.1, step: 0.001, defaultValue: 0.01 },
48 { key: "epochs", label: "Epochs per tick", min: 1, max: 10, step: 1, defaultValue: 2 },
49 {
50 key: "tool",
51 label: "Pointer tool",
52 options: [
53 { value: "classA", label: "Add class A (+)" },
54 { value: "classB", label: "Add class B (-)" },
55 { value: "erase", label: "Erase nearest" },
56 ],
57 defaultValue: "classA",
58 },
59 ];
60 }
61
62 protected onReset(): void {
63 this.count = 0;
64 this.rounds = 0;
65 this.alphas.fill(0);
66 // Two seeded, slightly overlapping blobs.
67 const blobs = [
68 { cx: 0.32, cy: 0.36, label: 1 },
69 { cx: 0.68, cy: 0.64, label: -1 },
70 ];
71 for (const blob of blobs) {
72 for (let i = 0; i < 26; i++) {
73 this.addPoint(blob.cx + (this.rng() - 0.5) * 0.3, blob.cy + (this.rng() - 0.5) * 0.3, blob.label);
74 }
75 }
76 this.fieldValid = false;
77 }
78
79 private addPoint(x: number, y: number, label: number): void {
80 if (this.count >= CAPACITY) return;
81 this.xs[this.count] = Math.min(1, Math.max(0, x));
82 this.ys[this.count] = Math.min(1, Math.max(0, y));
83 this.labels[this.count] = label;
84 this.alphas[this.count] = 0;
85 this.count += 1;
86 this.fieldValid = false;
87 }
88
89 protected onParameterChange(key: string): void {
90 // Kernel and lambda change the geometry: reset the dual, keep the data.
91 if (key === "kernel" || key === "lambda" || key === "gamma") {
92 this.alphas.fill(0);
93 this.rounds = 0;
94 this.fieldValid = false;
95 } else if (key !== "epochs" && key !== "tool") {
96 this.reset();
97 }
98 }
99
100 resize(width: number, height: number): void {
101 this.width = width;
102 this.height = height;
103 this.fieldValid = false;
104 }
105
106 onPointer(state: PointerState): void {
107 this.pointer = state;
108 if (!state.inside || !state.down) {
109 this.lastCell = { x: -1, y: -1 };
110 return;
111 }
112 const x = state.x / Math.max(1, this.width);
113 const y = state.y / Math.max(1, this.height);
114 const cell = { x: Math.round(x * 50), y: Math.round(y * 50) };
115 if (cell.x === this.lastCell.x && cell.y === this.lastCell.y) return;
116 this.lastCell = cell;
117 const tool = this.str("tool");
118 if (tool === "erase") {
119 let best = -1;
120 let bestDist = 0.06;
121 for (let i = 0; i < this.count; i++) {
122 const d = Math.hypot(this.xs[i] - x, this.ys[i] - y);
123 if (d < bestDist) {
124 bestDist = d;
125 best = i;
126 }
127 }
128 if (best >= 0) {
129 // Swap-remove keeps arrays dense; order does not affect the dual.
130 this.count -= 1;
131 this.xs[best] = this.xs[this.count];
132 this.ys[best] = this.ys[this.count];
133 this.labels[best] = this.labels[this.count];
134 this.alphas[best] = this.alphas[this.count];
135 this.fieldValid = false;
136 }
137 } else {
138 this.addPoint(x, y, tool === "classA" ? 1 : -1);
139 }
140 }
141
142 private kernel(i: number, j: number): number {
143 if (this.str("kernel") === "linear") {
144 return this.xs[i] * this.xs[j] + this.ys[i] * this.ys[j] + 1;
145 }
146 const dx = this.xs[i] - this.xs[j];
147 const dy = this.ys[i] - this.ys[j];
148 return Math.exp(-this.num("gamma") * (dx * dx + dy * dy)) + 1;
149 }
150
151 private decision(i: number): number {
152 let sum = 0;
153 for (let j = 0; j < this.count; j++) {
154 if (this.alphas[j] === 0) continue;
155 sum += this.alphas[j] * this.labels[j] * this.kernel(i, j);
156 }
157 return sum;
158 }
159
160 private decisionAt(x: number, y: number): number {
161 let sum = 0;
162 for (let j = 0; j < this.count; j++) {
163 if (this.alphas[j] === 0) continue;
164 const dx = x - this.xs[j];
165 const dy = y - this.ys[j];
166 const k =
167 this.str("kernel") === "linear"
168 ? this.xs[j] * x + this.ys[j] * y + 1
169 : Math.exp(-this.num("gamma") * (dx * dx + dy * dy)) + 1;
170 sum += this.alphas[j] * this.labels[j] * k;
171 }
172 return sum;
173 }
174
175 protected onUpdate(): void {
176 if (this.count < 2) return;
177 const lambda = Math.max(1e-4, this.num("lambda"));
178 const epochs = this.num("epochs");
179 for (let epoch = 0; epoch < epochs; epoch++) {
180 this.rounds += 1;
181 const eta = 1 / (lambda * this.rounds);
182 // Seeded shuffle: deterministic epochs.
183 const order = Array.from({ length: this.count }, (_, i) => i);
184 for (let i = this.count - 1; i > 0; i--) {
185 const j = Math.floor(this.rng() * (i + 1));
186 [order[i], order[j]] = [order[j], order[i]];
187 }
188 for (const i of order) {
189 const margin = this.labels[i] * this.decision(i);
190 if (margin < 1) {
191 this.alphas[i] += eta;
192 }
193 // Pegasos projection keeps the dual bounded.
194 const scale = Math.min(1, 1 / Math.sqrt(lambda * this.rounds * this.alphas[i] ** 2 || 1));
195 if (scale < 1) {
196 for (let j = 0; j < this.count; j++) this.alphas[j] *= scale;
197 }
198 }
199 }
200 this.fieldTick += 1;
201 if (!this.fieldValid || this.fieldTick % 12 === 0) this.evaluate();
202 }
203
204 private evaluate(): void {
205 const fieldH = Math.floor(FIELD_W / 2);
206 let correct = 0;
207 let marginActive = 0;
208 for (let i = 0; i < this.count; i++) {
209 const prediction = this.decision(i) >= 0 ? 1 : -1;
210 if (prediction === this.labels[i]) correct += 1;
211 if (Math.abs(this.labels[i] * this.decision(i)) < 1) marginActive += 1;
212 }
213 this.accuracy = this.count > 0 ? correct / this.count : 0;
214 this.marginActive = marginActive;
215 for (let gy = 0; gy < fieldH; gy++) {
216 for (let gx = 0; gx < FIELD_W; gx++) {
217 this.field[gy * FIELD_W + gx] = this.decisionAt(gx / FIELD_W, gy / fieldH);
218 }
219 }
220 this.fieldValid = true;
221 }
222
223 render(ctx: CanvasRenderingContext2D, theme: ThemeColors): void {
224 ctx.fillStyle = theme.bg;
225 ctx.fillRect(0, 0, this.width, this.height);
226 const diverging = divergingFor(theme);
227 const fieldH = Math.floor(FIELD_W / 2);
228 // Decision field, softly
229 if (this.fieldValid) {
230 let maxAbs = 1e-6;
231 for (let i = 0; i < this.field.length; i++) maxAbs = Math.max(maxAbs, Math.abs(this.field[i]));
232 const cellW = this.width / FIELD_W;
233 const cellH = this.height / fieldH;
234 for (let gy = 0; gy < fieldH; gy++) {
235 for (let gx = 0; gx < FIELD_W; gx++) {
236 const value = this.field[gy * FIELD_W + gx] / maxAbs;
237 const banded = Math.round(value * 8) / 8;
238 if (Math.abs(value) < 0.02) continue; // boundary band stays background
239 ctx.fillStyle = this.divergingCss(diverging, 0.5 + banded * 0.45);
240 ctx.fillRect(gx * cellW, gy * cellH, cellW + 0.5, cellH + 0.5);
241 }
242 }
243 }
244 // Points: class A accent, class B sky; margin-active get a ring.
245 // (The banded field above is the decision boundary; with the implicit
246 // +1 bias absorbed into the kernel, an explicit line would be noise.)
247 for (let i = 0; i < this.count; i++) {
248 const px = this.xs[i] * this.width;
249 const py = this.ys[i] * this.height;
250 ctx.fillStyle = this.labels[i] > 0 ? theme.accent : theme.viz[1];
251 ctx.beginPath();
252 ctx.arc(px, py, 3.4, 0, Math.PI * 2);
253 ctx.fill();
254 if (this.fieldValid && Math.abs(this.labels[i] * this.decision(i)) < 1) {
255 ctx.strokeStyle = theme.fg;
256 ctx.lineWidth = 1;
257 ctx.beginPath();
258 ctx.arc(px, py, 5.5, 0, Math.PI * 2);
259 ctx.stroke();
260 }
261 }
262 }
263
264 private divergingCache: Record<string, string> = {};
265 private divergingCss(lut: ColorLUT, t: number): string {
266 const key = t.toFixed(3);
267 if (this.divergingCache[key]) return this.divergingCache[key];
268 const index = Math.min(255, Math.max(0, Math.round(t * 255)));
269 const css = `rgb(${lut.r[index]}, ${lut.g[index]}, ${lut.b[index]})`;
270 this.divergingCache[key] = css;
271 return css;
272 }
273
274 getMetrics() {
275 return {
276 points: this.count,
277 epochs: this.rounds,
278 accuracy: `${(this.accuracy * 100).toFixed(1)} %`,
279 marginActive: this.marginActive,
280 kernel: this.str("kernel") === "linear" ? "Linear" : "RBF",
281 };
282 }
283
284 describe(): string {
285 return `${this.count} labeled points, ${(this.accuracy * 100).toFixed(0)}% training accuracy after ${this.rounds} Pegasos epochs with the ${this.str("kernel")} kernel; ringed points sit on or inside the margin.`;
286 }
287
288 entities(): number {
289 return this.count;
290 }
291}
292

Performance

Time per tick
O(points) per sample update; field O(grid · support points)
Space
One dual coefficient per point
Notes
Linear versus RBF is literally a one-line kernel swap - the margin objective stays identical, which is the kernel trick's whole point.

Live numbers (FPS, frame time, steps per second, microseconds per step, entity count) are in the performance overlay on the simulation above: the pulse icon in its top-right corner.