Why must a 40-class SVM product router be built from many binary SVMs?
answer
- one hyperplane, two sides
- the objective is written over plus-one and minus-one
- decompose into binary subproblems
- count pairs of classes, not classes
- 40 times 39 divided by 2
basics
~20 sA support vector machine optimises one hyperplane, which has exactly two sides, so its objective can only express a positive and a negative class. Forty categories are covered by training one SVM per class pair: 780 models.
solid answer
~50 sAn SVM's whole objective is written over a single weight vector `w` and offset `b`, with labels of `+1` and `-1`; the prediction is `sign(w·x + b)`. There is no slot in that formulation for "category 17 of 40", so multiclass is reached by decomposition rather than natively. For SVMs the usual choice is one classifier per unordered pair of classes — `40*39/2 = 780` models for a 40-class router — because each pairwise problem only sees rows from its two categories. That matters when the learner's cost grows faster than linearly in rows: 780 small problems on roughly `2n/40` rows each are cheaper in total than 40 problems on all `n` rows. The bill you pay instead is at prediction time — 780 decision functions to evaluate and a vote to aggregate — and in storage, since every pairwise model keeps its own support vectors.
go deeper
Be ready to state that an SVM is binary by construction and that many classes are handled by training several binary models, and to compute the pairwise count for a given number of classes on the spot.
Explain why the pairwise scheme is the SVM-friendly one: each subproblem sees only two classes' rows, so a learner whose cost grows quadratically in rows does less total work than training every class against all the data.
Show you have served one of these. Talk about prediction cost growing quadratically in categories, storing hundreds of support-vector sets, and which models you retrain when the taxonomy gains a category.
Own the point at which the decomposition stops paying. Frame it as taxonomy growth rate against serving latency, and be able to argue for a formulation with a shared representation when categories are numerous and churn often.
## The objective only knows two sides A support vector machine learns a single hyperplane described by a weight vector `w` and an offset `b`. The prediction rule is `sign(w·x + b)` — one number, and the answer is which side of zero it lands on. The training objective is written the same way: minimise `0.5*||w||^2 + C * sum_i max(0, 1 - y_i*(w·x_i + b))`, where each label `y_i` is `+1` or `-1`. There is nowhere in that expression to say "category 17 of 40". A model that handles many classes natively emits one score per class and compares them; an SVM emits one score and reads its sign. This is not a gap someone forgot to implement — it is a property of the max-margin formulation itself. ## The two decompositions, and why SVMs prefer pairs With 40 categories you can either train one classifier per category against all the others (40 models, each trained on every row), or one classifier per unordered pair of categories (`k(k-1)/2 = 40*39/2 = 780` models, each trained only on the rows of its two categories). 780 looks like the more expensive option and usually is not, precisely because a kernel SVM's training cost grows superlinearly in the number of rows. Suppose a marketplace has 400,000 labelled listings across 40 roughly balanced categories, and that training cost grows about quadratically in rows. - Pairwise: each problem sees about `2n/k = 20,000` rows. Cost per model is proportional to `(2n/k)^2 = 4n^2/k^2`. Times `k^2/2` models, the total is about `2n^2` — and notice `k` has cancelled. - One-against-the-rest: each of the `k` models sees all `n = 400,000` rows, so the total is about `k*n^2` — forty times more work. So the model *count* is quadratic in classes while the total training *work* is roughly flat in classes. Candidates who answer "780 models, that must be slower" have the arithmetic backwards. ## What the decomposition actually costs **Prediction.** Every one of the 780 decision functions must be evaluated for each incoming listing, each over its own set of support vectors, and the 780 outcomes aggregated by voting. Prediction cost grows quadratically in the number of categories, which is the real scaling wall for a router whose taxonomy keeps expanding. **Memory.** Each pairwise model stores its own support vectors — for a kernel SVM those are actual training rows, not a compact weight vector — so the served artefact is 780 small models rather than one. **Aggregation is a heuristic.** Voting can tie, and cyclic outcomes are possible: pair A-B prefers A, B-C prefers B, C-A prefers C. There is no principled single score to fall back on, because the pairwise decision values live on different scales. **Taxonomy churn.** Adding a 41st category means training 40 new pairwise models and leaving the existing 780 untouched. Under the one-against-the-rest scheme the "rest" has changed, so all 41 models must be retrained. For a catalogue whose taxonomy is edited monthly, that operational difference matters more than the training arithmetic. **No shared statistical strength.** Each pairwise model is fit independently, so a rare category is only ever learned from the 39 problems it appears in, with no representation shared across classes. ## Are there true multiclass SVMs? Yes. The Crammer-Singer and Weston-Watkins formulations pose a single optimisation with one weight vector per class and a multiclass margin constraint requiring the correct class's score to exceed every other class's score by a margin. They are genuinely native and avoid the voting problem entirely, but they solve one large quadratic program instead of many small ones, are harder to optimise, and in practice rarely buy enough accuracy to justify the trouble. Knowing they exist is a good marker in an interview; claiming decomposition is the *only* possibility is a small error. ## What to say in the room Lead with the formulation — one hyperplane, two sides — then give the count and the cancellation argument that makes 780 cheaper to train than 40, then name the real cost: prediction time, storage, and an aggregation step that has no principled score behind it.
- 780 models sounds worse than 40. Why is the pairwise scheme usually cheaper to train for a kernel SVM?Because each pairwise problem sees only the rows of its two classes. With balanced classes that is about `2n/k` rows, and for a learner whose cost grows quadratically in rows the total across `k(k-1)/2` models comes out around `2n^2` — independent of the number of classes. Training one model per class against all the rest costs about `k*n^2`, since every model sees the full dataset.
- Is there a support vector machine that handles all 40 classes in one optimisation?Yes — the Crammer-Singer and Weston-Watkins multiclass formulations keep one weight vector per class and require the true class's score to beat every rival's by a margin, all in a single objective. They remove the voting step, but they solve one large quadratic program that is harder to optimise, and the accuracy gain over decomposition is usually small, so they are uncommon in practice.
- The catalogue adds a 41st category next week. What has to be retrained under each scheme?Under pairwise decomposition, only the 40 new pairs involving the new category — the existing 780 models are untouched. Under one-against-the-rest, the negative class has changed for every model, so all 41 must be retrained on the full dataset. For a taxonomy that is edited regularly, that incremental property is often the deciding argument.
A single SVM is a fence: it separates a field into two parts and nothing more. Forty plots need many fences, and each fence only knows about the two plots it sits between.
saying these in an interview costs you the question
- Says one SVM fits 40 hyperplanes simultaneously
- Counts 40 pairwise models instead of 780
- Assumes more models always means longer total training
- Confuses the number of classes with the number of support vectors
- Claims decomposition is the only possible multiclass SVM