Support Vector Machines: Margins and Soft Constraints

For a linearly separable binary problem, the hard-margin SVM chooses a separating hyperplane with the largest geometric margin to the nearest training points. Those nearest points are the support vectors.

Real data is rarely perfectly separable. Soft-margin SVMs trade a wider margin against violations using a regularization parameter.

How few points end up carrying the boundary is not a promise the method makes. The data decides it, and there is a proved floor. For a universal kernel, the fraction of support vectors is asymptotically no smaller than the Bayes risk of the distribution. That is Theorem 9 of Steinwart's 2003 paper on the sparseness of support vector machines, in the Journal of Machine Learning Research. For differentiable losses the floor is the probability of the region where labels are not noise-free — always at least twice the Bayes risk. Bartlett and Tewari sharpened the result in 2007: for the L1-SVM the asymptotic support-vector fraction equals E_x[2 min(η(x), 1−η(x))]. That is twice the Bayes risk, and it is also the optimal hinge-loss risk. On a problem with 10% irreducible label noise, expect roughly 20% of the training set to end up as support vectors. Steinwart states the consequence plainly: “Therefore, when a noisy classification problem is learned we should expect that the number of support vectors increases linearly in the sample size.”

The boundary and its margin exist only after the features have been placed in a common geometry. That is why the scaling decision below changes what the word margin refers to, and not merely how the numbers look.

The parameter C controls the penalty for violations in a common SVM formulation. In published practice it is not nudged toward a sensible default. It is swept across orders of magnitude, because no default survives a change of dataset.

The LIBSVM authors' practical guide, last updated 4 September 2025, recommends an exponentially growing grid: C = 2^-5, 2^-3, …, 2^15, together with γ = 2^-15, 2^-13, …, 2^3. scikit-learn 1.9.0's worked RBF example sweeps wider still. It searches C_range = np.logspace(-2, 10, 13) and gamma_range = np.logspace(-9, 3, 13) — twelve orders of magnitude in C — evaluated with a 5-split StratifiedShuffleSplit, and it reports best parameters {'C': 1.0, 'gamma': 0.1} with a score of 0.97. Its instruction to the reader is explicit: “One is advised to use GridSearchCV with C and gamma spaced exponentially far apart to choose good values.”

The reason for the width is empirical. In Hsu and Lin's own ten-dataset study the winning (C, γ) pairs landed in different ranges on different problems, “so it is essential to test so many parameter sets”.

An SVM margin is measured in feature coordinates. A large-unit feature can dominate the geometry, and the apparent importance of other dimensions then shrinks. The LIBSVM guide puts the mechanism in one sentence: “The main advantage of scaling is to avoid attributes in greater numeric ranges dominating those in smaller numeric ranges.”

The size of the effect is on record in the guide's own reproducible runs. The astroparticle-physics set svmguide1 goes from 66.925% to 96.15% test accuracy by scaling attributes to [-1, +1] with default parameters alone, and to 96.875% after the grid search. The bioinformatics set svmguide2 goes from 56.5217% to 78.5166% five-fold cross-validation accuracy on scaling, then 85.1662% after selection. The vehicle set svmguide3 is the extreme case: 2.43902% unscaled, 12.1951% after scaling, and 87.8049% once scaled and tuned at C = 128, γ = 0.125. An unscaled SVM there is not a weaker model. It is a broken one.

scikit-learn 1.9.0 states the same requirement in its SVM user guide: “Support Vector Machine algorithms are not scale invariant, so it is highly recommended to scale your data.”

Fit scaling inside the pipeline, then inspect whether standardized units reflect meaningful variation. Binary and sparse features may need different handling from continuous measurements.

A margin objective can be effective when dimensions are numerous and examples are represented sparsely. The clearest published test of that claim is text categorization.

The representation there is about as extreme as it gets, and the margin still held. Joachims worked on the ModApte split of Reuters-21578: 9,603 training documents and 90 categories, each document a sparse vector over the vocabulary. The microaveraged precision/recall breakeven point was 86.0 for a polynomial SVM and 86.4 for an RBF SVM. Naïve Bayes reached 72.0, C4.5 79.4, Rocchio 79.9 and k-NN 82.3. He reports that “the RBF support vector machine is better than k-NN on 63 of the 90” categories, with 19 ties. On the Ohsumed collection k-NN was again the best conventional method, at 59.1, while C4.5 reached 50.0. His summary of the advantage is a statement about operation rather than about margins: the SVMs “are fully automatic, eliminating the need for manual parameter tuning”.

An independent survey put that result next to everyone else's. Sebastiani's 2002 survey of machine learning in text categorization, in ACM Computing Surveys, tabulates the published Reuters figures. On the Reuters-21578 version with 12,902 documents — 9,603 training, 3,299 test, 90 categories — SvmLight scores .864 microaveraged breakeven, against k-NN .823, Rocchio .799, C4.5 .794 and a probabilistic classifier .720. Three further SVM entries from other groups sit on the same corpus: .870 from Dumais and colleagues in 1998, .859 from Yang and Liu in 1999, .841 from Li and Yamanishi in 1999. Four independent teams land between .841 and .870. The best non-SVM entry on that corpus is .823.

The boundary condition matters as much as the scoreboard, and Sebastiani states it: “An experimental study by Joachims [1998] involving support vector machines, k-NN, decision trees, Rocchio and Naïve Bayes, showed all these classifiers to have similar effectiveness on categories with ≥ 300 positive training examples each.” The margin buys the most where the positive examples are few.

The margin is meaningful only after the representation and evaluation are valid, and step 2 is where most of the damage is done. scikit-learn 1.9.0's chapter on common pitfalls states the rule: “Although both train and test data subsets should receive the same preprocessing transformation (as described in the previous section), it is important that these transformations are only learnt from the training data.”

Both maintainers quantify what breaking it costs. scikit-learn builds a binary problem of 200 samples and 10,000 randomly generated features with random labels — a dataset with nothing in it to learn. Fitting SelectKBest(k=25) on all the data before splitting reports 0.76 accuracy. Fitting the selector on the training subset only reports 0.5, chance. The LIBSVM guide shows the same failure for scaling. The traffic-light dataset svmguide4, scaled separately for training and test, scores 69.2308% (216/312); the identical pipeline using the training set's saved scaling factors scores 89.4231% (279/312). There the leak does not inflate the score. It destroys twenty real points of it.

The rest of the sequence follows from that. Search C by the logarithmic sweep rather than by intuition. Read the support vectors as evidence about difficult rows. Evaluate the score and the threshold before any probability is claimed.

The signed decision function is useful for ranking and for distance from the boundary in the transformed coordinates. Turning it into a probability adds a second model, fitted after the fact and fallible on its own terms.

scikit-learn 1.9.0 documents what that second model is and what it costs. In the binary case the probabilities come from Platt scaling: a logistic regression on the SVM's scores, fitted by an additional cross-validation on the training data. That cross-validation is expensive on large datasets. predict and predict_proba can disagree across the 0.5 boundary. decision_function should be preferred when a score rather than a probability is what the application needs. The guide's own wording is blunt: “In addition, the probability estimates may be inconsistent with the scores”.

The calibration layer has also failed at the level of arithmetic. A 2007 note in the journal Machine Learning found that Platt's published pseudo-code does not evaluate its own objective correctly — “this pseudo code does not correctly calculate the objective value” — and measured the difference on the UCI shuttle data across 110 (C, γ) settings. Platt's Levenberg–Marquardt implementation averaged 589.30 overflow errors and 8.00 iterations per problem. The note's reformulated algorithm averaged 0 overflows and 6.66 iterations.

Calibration can also change after prevalence or feature shift even when the ranking remains stable.

Common strategies include one-vs-rest and one-vs-one comparisons. They differ in training cost, score combination, and how conflicts are resolved.

The comparison has been run rather than assumed. Hsu and Lin put one-against-all, one-against-one, DAGSVM and two single-optimisation formulations against each other on ten datasets — iris, wine, glass, vowel, vehicle, segment, dna, satimage, letter and shuttle — choosing the RBF parameters by the same search for every method. Their paper appeared in IEEE Transactions on Neural Networks in March 2002. Accuracy came out close: “except the training time, other factors are very similar for these approaches”. Training cost did not: “For the training time, one-against-one and DAG methods are the best”. Their recommendation is therefore about cost rather than correctness — “one-against-one method and DAG may be more suitable for practical use”.

Rifkin and Klautau re-read the same tables in 2004 and measured how small close actually is. Between the best and the worst of the five methods the gap is 0.028 percentage points on shuttle — about 4 of 14,500 test points — 0.300 on letter (15 of 5,000), 0.260 on segment and 1.050 on satimage (about 20 of 2,000). The training-time gap is the one that is real, and it is not stable either. On letter one-against-all trained about 6 times slower than one-against-one or DAG; on the larger shuttle the difference was only about 15%. Their conclusion inverts the emphasis: “Therefore, we must conclude that the Hsu and Lin results support the notion that at least as far as accuracy is concerned, when well-tuned binary classifiers (in this case SVMs with RBF kernels) are used as the underlying classifiers, a wide variety of multiclass classification schemes are essentially indistinguishable.”

Evaluate class-specific behavior and decision policy on your own data rather than assuming the binary margin interpretation transfers unchanged.