margin
In plain wordsHow far, and on which side, an example lies from a classifier's dividing line. A wide gap between the line and the nearest examples suggests the classifier will handle new data well.
- 1
Classification
The distance between a classifier's decision boundarydecision boundary, n.: The dividing line, or surface, where a classifier switches from predicting one category to another. Simple models draw straight lines; flexible ones draw curves. and the training examples closest to it. For a linear classifier with weights w and offset b, the geometric margin of a dataset is the minimum over examples of yᵢ(w·xᵢ + b)/‖w‖. Maximizing it is the principle of support vector machinessupport vector machine, n.: A classic method that separates two groups of examples with the widest possible gap — like laying the broadest possible road between them. A mathematical shortcut lets it draw curved boundaries too.: a hard margin requires every example to lie outside it, while a soft margin tolerates violations at a cost. Learning theory links large margins to better generalizationgeneralization, n.: How well a model copes with new examples it has never seen, rather than just memorizing its training data, like a student who understands the method, not just the answers., because margin-based error bounds depend on the margin relative to the spread of the data rather than on the number of features.
Rescaling the features changed the margin, so we standardized everything before training the SVM.
- 2
Per-example and in loss functions
The signed score y·f(x) of a single example, with labels ±1: positive when the example is classified correctly and larger the more confidently so. Margin-based losses such as the hinge losshinge loss, n.: A way of scoring a classifier's mistakes that charges nothing for answers that are right with room to spare, and charges more and more the further an answer falls on the wrong side., logistic loss and AdaBoost's exponential loss are functions of it, and the distribution of margins helps explain why boostingboosting, n.: Building a strong predictor from many weak ones trained one after another, where each new model concentrates on the mistakes the previous ones made. keeps improving test error after training error reaches zero. In ranking and metric learning, a margin is also a fixed gap, set as a hyperparameter, by which a matching pair's score must exceed a non-matching pair's in triplet or contrastive losses.
Origin
The maximum-margin principle comes from Vladimir Vapnik's work with Alexander Lerner and Alexey Chervonenkis in the 1960s and was popularized by support vector machines in the 1990s ('optimal margin classifiers', Boser, Guyon and Vapnik, 1992). Robert Schapire, Yoav Freund, Peter Bartlett and Wee Sun Lee used margins to explain boosting's resistance to overfitting in 1998.
Related
- support vector machinesupport vector machine, n.: A classic method that separates two groups of examples with the widest possible gap — like laying the broadest possible road between them. A mathematical shortcut lets it draw curved boundaries too.
- hinge losshinge loss, n.: A way of scoring a classifier's mistakes that charges nothing for answers that are right with room to spare, and charges more and more the further an answer falls on the wrong side.
- decision boundarydecision boundary, n.: The dividing line, or surface, where a classifier switches from predicting one category to another. Simple models draw straight lines; flexible ones draw curves.
- AdaBoostAdaBoost, prop. n.: One of the first practical boosting methods: it trains simple models in turn, giving extra weight to examples the earlier models got wrong, then lets all the models vote, weighted by accuracy.
- linear separabilitylinear separability, n.: When two groups of points can be perfectly divided by a single straight line or, in more dimensions, a flat surface. Many simple learning methods only fully succeed in this case.
- contrastive learningcontrastive learning, n.: A way to learn without labels by comparison: the model learns to pull together two versions of the same thing, such as two crops of one photo, and push apart unrelated things.
Sources
- Schapire, R. E., Freund, Y., Bartlett, P. & Lee, W. S. (1998). Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods. The Annals of Statistics, 26(5), 1651–1686.
Mentioned in
AdaBoostAdaBoost, prop. n.: One of the first practical boosting methods: it trains simple models in turn, giving extra weight to examples the earlier models got wrong, then lets all the models vote, weighted by accuracy., decision boundarydecision boundary, n.: The dividing line, or surface, where a classifier switches from predicting one category to another. Simple models draw straight lines; flexible ones draw curves., inductive biasinductive bias, n.: The assumptions built into a learning method that decide how it fills the gaps between the examples it was shown, such as that similar inputs get similar answers. Every learner needs some to cope with new cases., linear separabilitylinear separability, n.: When two groups of points can be perfectly divided by a single straight line or, in more dimensions, a flat surface. Many simple learning methods only fully succeed in this case., support vector machinesupport vector machine, n.: A classic method that separates two groups of examples with the widest possible gap — like laying the broadest possible road between them. A mathematical shortcut lets it draw curved boundaries too., Vladimir VapnikVladimir Vapnik, prop. n.: A Soviet-born American mathematician who built the statistical theory of how machines learn from examples and co-invented support vector machines, a leading method before deep learning., hinge losshinge loss, n.: A way of scoring a classifier's mistakes that charges nothing for answers that are right with room to spare, and charges more and more the further an answer falls on the wrong side.