マージン分類器

マージン分類器（マージンぶんるいき、英: margin classifier）は機械学習における分類器の一つ。適当な空間にマップされたサンプルの集合に対し決定境界 (decision boundary) を設定して、サンプルの各要素と決定境界との距離を評価することによって統計的な分類を行う。たとえば、パーセプトロンや線形判別分析 (linear discriminant analysis; LDA) に代表される線形分類器を用いる場合、分類はサンプルがマップされている空間を分割する超平面によって行われる。この場合、超平面とサンプルの各要素との距離がそれぞれのサンプル要素に対するマージンとなる。なお超平面とサンプル要素との距離を与える距離関数は、典型的にはユークリッド距離を用いるが別の距離関数を用いることもままある。

マージンという考えは様々な機械学習における分類アルゴリズムを通じて重要であり、分類器の汎化誤差を制限するために用いられる。この制限はしばしばVC次元（ヴァプニク・チェルヴォーネンキス次元、英: Vapnik–Chervonenkis dimension）によって示される。特に際立っていることはブースティングアルゴリズムやサポートベクターマシンの汎化誤差に対する制限である。

サポートベクターマシン

詳細は「サポートベクターマシン」を参照

ブースティングアルゴリズム

与えられたサンプルを 2 つのクラスに分類する反復ブースティングアルゴリズムに対するマージンは以下のように定義できる。分類器にはサンプル要素とそれに対するラベルの組 (x, y), (x ∈ X, y ∈ Y) が与えられる。X はサンプル空間であり、Y は x に対するラベル y の集合を表し、Y = {−1, +1} である。反復ブースティングは各反復 j で、実際の値を予言する可能な分類器 h_j ∈ C を選択する。ブースティングによって選択されたこの提案は実数 α_j ∈ R で重み付けされる。サンプル要素 x に対するマージンは結局、次のように定義される。

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

この定義によって、マージンはサンプル要素に与えられたラベルが正しい場合に正値をとり、ラベルが誤っている場合には負値をとることになる。

ブースティングに対するマージンの定義の仕方は上述の方法が唯一ということはなく、他にも拡張や改変が考えられる。従って問題設定に応じて有効な定義が用いられる。

マージンに基づくアルゴリズム

多くの分類器はそれぞれのサンプル要素に対してマージンを設定できる。しかしながら、限られたいくつかの分類器だけがデータセットからの学習によって得られたマージンの情報を利用できる。

多くのブースティングアルゴリズムは、マージンによってサンプルに重み付けをするという発想に依拠している。凸損失関数 (convex loss function) を利用する場合（AdaBoost, LogitBoost, また AnyBoost 系のアルゴリズムを使うなど）、高いマージンを持つサンプルはより低いマージンのサンプルより小さな（あるいは等しい）重みがつけられる。このことからブースティングアルゴリズムはマージンの低いサンプルに対して重点的に重みをつけることとなる。 凸損失を利用しない BrownBoost のようなアルゴリズムでは、マージンはサンプルの重みを左右し得るが、凸損失関数を利用する場合と異なり重みとマージンの間の関係は単調ではなくなる。ブースティングアルゴリズムの中には、最小マージンを最大化するようなものが存在する（たとえば Warmuth, Glocer & Rätsch 2007 を参照）。

サポートベクターマシンはサンプルを分割する超平面のマージンを最大化する。（超平面によって完全にデータを分離できないような）ノイズありのデータを用いて訓練されたサポートベクターマシンはソフトマージンを最大化する（詳細はサポートベクターマシンを参照）。

多数決パーセプトロン (voted perceptron) は古典的なパーセプトロンの反復適用を基礎とするマージン最大化アルゴリズムである。

汎化誤差の制限

マージン分類器の背後にある理論的な動機の一つは、アルゴリズムのパラメタとマージン項によって汎化誤差を制限できるということにある。そのような制限の例として AdaBoost に対するものがある。S を m 個のサンプル要素の集合とする。これらのサンプルは分布 D から独立かつ無作為に選ばれたものである。基底の分類器に対するVC次元は d, (1 ≤ d ≤ m) となる。このとき確率 1 − δ で

$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$

という制限が得られる。

参考文献

• Schapire, Robert E.; Freund, Yoav; Bartlett, Peter; Lee, Wee Sun (1998). “Boosting the margin: A new explanation for the effectiveness of voting methods”. The Annals of Statistics 26 (5): 1651–1686. doi:10.1214/aos/1024691352. 
• Warmuth, Manfred; Glocer, Karen; Rätsch, Gunnar (2007). “Boosting Algorithms for Maximizing the Soft Margin”. Proceedings of Advances in Neural Information Processing Systems 20: pp. 1585–1592.