マージン分類器
マージン分類器（マージンぶんるいき、テンプレート:Lang-en-short）は機械学習における分類器の一つ。適当な空間にマップされたサンプルの集合に対し決定境界 (decision boundary) を設定して、サンプルの各要素と決定境界との距離を評価することによって統計的な分類を行う。たとえば、パーセプトロンや線形判別分析 (linear discriminant analysis; LDA) に代表される線形分類器を用いる場合、分類はサンプルがマップされている空間を分割する超平面によって行われる。この場合、超平面とサンプルの各要素との距離がそれぞれのサンプル要素に対するマージンとなる。なお超平面とサンプル要素との距離を与える距離関数は、典型的にはユークリッド距離を用いるが別の距離関数を用いることもままある。
マージンという考えは様々な機械学習における分類アルゴリズムを通じて重要であり、分類器のテンプレート:仮リンクを制限するために用いられる。この制限はしばしばテンプレート:仮リンク（ヴァプニク・チェルヴォーネンキス次元、テンプレート:Lang-en-short）によって示される。特に際立っていることはブースティングアルゴリズムやサポートベクターマシンの汎化誤差に対する制限である。
サポートベクターマシン
ブースティングアルゴリズム
与えられたサンプルを 2 つのクラスに分類する反復ブースティングアルゴリズムに対するマージンは以下のように定義できる。分類器にはサンプル要素とそれに対するラベルの組 テンプレート:Math が与えられる。テンプレート:Mvar はサンプル空間であり、テンプレート:Mvar は テンプレート:Mvar に対するラベル テンプレート:Mvar の集合を表し、テンプレート:Math である。反復ブースティングは各反復 テンプレート:Mvar で、実際の値を予言する可能な分類器 テンプレート:Math を選択する。ブースティングによって選択されたこの提案は実数 テンプレート:Math で重み付けされる。サンプル要素 テンプレート:Mvar に対するマージンは結局、次のように定義される。
この定義によって、マージンはサンプル要素に与えられたラベルが正しい場合に正値をとり、ラベルが誤っている場合には負値をとることになる。
ブースティングに対するマージンの定義の仕方は上述の方法が唯一ということはなく、他にも拡張や改変が考えられる。従って問題設定に応じて有効な定義が用いられるテンプレート:Sfn。
マージンに基づくアルゴリズム
多くの分類器はそれぞれのサンプル要素に対してマージンを設定できる。しかしながら、限られたいくつかの分類器だけがデータセットからの学習によって得られたマージンの情報を利用できる。
多くのブースティングアルゴリズムは、マージンによってサンプルに重み付けをするという発想に依拠している。凸損失関数 テンプレート:En を利用する場合（AdaBoost, テンプレート:仮リンク, また テンプレート:仮リンク 系のアルゴリズムを使うなど）、高いマージンを持つサンプルはより低いマージンのサンプルより小さな（あるいは等しい）重みがつけられる。このことからブースティングアルゴリズムはマージンの低いサンプルに対して重点的に重みをつけることとなる。 凸損失を利用しない テンプレート:仮リンク のようなアルゴリズムでは、マージンはサンプルの重みを左右し得るが、凸損失関数を利用する場合と異なり重みとマージンの間の関係は単調ではなくなる。ブースティングアルゴリズムの中には、最小マージンを最大化するようなものが存在する（たとえば テンプレート:Harvnb を参照）。
サポートベクターマシンはサンプルを分割する超平面のマージンを最大化する。（超平面によって完全にデータを分離できないような）ノイズありのデータを用いて訓練されたサポートベクターマシンはソフトマージンを最大化する（詳細はサポートベクターマシンを参照）。
多数決パーセプトロン テンプレート:En は古典的なパーセプトロンの反復適用を基礎とするマージン最大化アルゴリズムである。
汎化誤差の制限
マージン分類器の背後にある理論的な動機の一つは、アルゴリズムのパラメタとマージン項によってテンプレート:仮リンクを制限できるということにある。そのような制限の例として AdaBoost に対するものがあるテンプレート:Sfn。テンプレート:Mvar を テンプレート:Mvar 個のサンプル要素の集合とする。これらのサンプルは分布 テンプレート:Mvar から独立かつ無作為に選ばれたものである。基底の分類器に対するテンプレート:仮リンクは テンプレート:Math となる。このとき確率 テンプレート:Math で
という制限が得られる。