マージン分類器
マージン分類器の背後にある理論的な動機の一つは、アルゴリズムのパラメタとマージン項によって汎化誤差(英語版)を制限できるということにある。そのような制限の例として AdaBoost に対するものがある。S を m 個のサンプル要素の集合とする。これらのサンプルは分布 D から独立かつ無作為に選ばれたものである。基底の分類器に対するVC次元(英語版)は d, (1 ≤ d ≤ m) となる。このとき確率 1 − δ で
P D ( y ∑ j = 1 t α j h j ( x ) ∑ | α j | ≤ 0 ) ≤ P S ( y ∑ j = 1 t α j h j ( x ) ∑ | α j | ≤ θ ) + O ( 1 m d log 2  ( m / d ) / θ 2 + log  ( 1 / δ ) ) , for~all θ > 0 {\displaystyle P_{D}\left({\frac {y\sum _{j=1}^{t}\alpha _{j}h_{j}(x)}{\sum |\alpha _{j}|}}\leq 0\right)\leq P_{S}\left({\frac {y\sum _{j=1}^{t}\alpha _{j}h_{j}(x)}{\sum |\alpha _{j}|}}\leq \theta \right)+{\mathcal {O}}\left({\frac {1}{\sqrt {m}}}{\sqrt {d\log ^{2}(m/d)/\theta ^{2}+\log(1/\delta )}}\right),~~{\textrm {for~all}}~~\theta >0}
という制限が得られる。