Margin classifier

See support vector machines and maximum-margin hyperplane for details.

The margin for an iterative boosting algorithm given a set of examples with two classes can be defined as follows. The classifier is given an example pair ${\displaystyle (x,y)}$ where ${\displaystyle x\in X}$ is a domain space and ${\displaystyle y\in Y=\{-1,+1\}}$ is the label of the example. The iterative boosting algorithm then selects a classifier ${\displaystyle h_{j}\in C}$ at each iteration ${\displaystyle j}$ where ${\displaystyle C}$ is a space of possible classifiers that predict real values. This hypothesis is then weighted by ${\displaystyle \alpha _{j}\in R}$ as selected by the boosting algorithm. At iteration ${\displaystyle t}$, the margin of an example ${\displaystyle x}$ can thus be defined as

${\displaystyle {\frac {y\sum _{j}^{t}\alpha _{j}h_{j}(x)}{\sum |\alpha _{j}|}}.}$

By this definition, the margin is positive if the example is labeled correctly and negative if the example is labeled incorrectly.

This definition may be modified and is not the only way to define margin for boosting algorithms. However, there are reasons why this definition may be appealing.[1]

Many classifiers can give an associated margin for each example. However, only some classifiers utilize information of the margin while learning from a data set.

Many boosting algorithms rely on the notion of a margin to give weights to examples. If a convex loss is utilized (as in AdaBoost, LogitBoost, and all members of the AnyBoost family of algorithms) then an example with higher margin will receive less (or equal) weight than an example with lower margin. This leads the boosting algorithm to focus weight on low margin examples. In nonconvex algorithms (e.g. BrownBoost), the margin still dictates the weighting of an example, though the weighting is non-monotone with respect to margin. There exists boosting algorithms that probably maximize the minimum margin (e.g. see [2]).

Support vector machines probably maximize the margin of the separating hyperplane. Support vector machines that are trained using noisy data (there exists no perfect separation of the data in the given space) maximize the soft margin. More discussion of this can be found in the support vector machine article.

The voted-perceptron algorithm is a margin maximizing algorithm based on an iterative application of the classic perceptron algorithm.

One theoretical motivation behind margin classifiers is that their generalization error may be bound by parameters of the algorithm and a margin term. An example of such a bound is for the AdaBoost algorithm.[1] Let ${\displaystyle S}$ be a set of ${\displaystyle m}$ examples sampled independently at random from a distribution ${\displaystyle D}$. Assume the VC-dimension of the underlying base classifier is ${\displaystyle d}$ and ${\displaystyle m\geq d\geq 1}$. Then with probability ${\displaystyle 1-\delta }$ we have the bound

${\displaystyle P_{D}\left({\frac {y\sum _{j}^{t}\alpha _{j}h_{j}(x)}{\sum |\alpha _{j}|}}\leq 0\right)\leq P_{S}\left({\frac {y\sum _{j}^{t}\alpha _{j}h_{j}(x)}{\sum |\alpha _{j}|}}\leq \theta \right)+O\left({\frac {1}{\sqrt {m}}}{\sqrt {d\log ^{2}(m/d)/\theta ^{2}+\log(1/\delta )}}\right)}$

for all ${\displaystyle \theta >0}$.