マージン最大化

分離超平面は1つに決まらない

2つのクラスのデータを1枚の超平面(2次元なら直線、3次元なら平面)で完全に分けられるとき、そのように分ける超平面は1つではなく、無限に存在します。ある分離超平面を少しだけ上下に動かしたり回転させたりしても、多くの場合どの訓練データにも触れないためです。データを分けられることは分かっても、無数にある候補の中からどれを選ぶかという問題が残ります。

マージンとは何か

各訓練データから超平面までの垂直な距離を測り、そのうち最も小さいものをマージン(margin)と呼びます。つまりマージンは、超平面にいちばん近い訓練データまでの距離です。全データの距離の合計や平均ではありません。

最も離れた超平面を選ぶ

マージン最大化は、分離超平面の候補のうち、このマージンが最大になるものを選ぶという考え方です。選ばれた超平面は訓練データから最も離れた分離超平面であり、最大マージン超平面(maximal margin hyperplane)または最適分離超平面と呼ばれます。この超平面を境界にして分類する分類器が、最大マージン分類器(maximal margin classifier)です。

どちらのクラスのデータからもできるだけ遠い位置に境界を引くと決めることで、無数にあった候補から1つを選ぶ明確な基準が得られます。

超平面を支えるサポートベクター

最大マージン超平面から等しい距離にあり、マージンの幅を決めている訓練データをサポートベクター(support vectors)と呼びます。これらの点が超平面を支えているという意味で、この名前が付いています。

サポートベクターが動けば、最大マージン超平面も動きます。一方、それ以外の訓練データは、マージンの境界を越えない限り、動かしても超平面に影響しません。最大マージン超平面は、全データではなく、境界にいちばん近い一部の訓練データだけで決まるということです。

最適化問題としての書き方

p個の特徴量 x_i1, ..., x_ip と、クラスを +1 か -1 で表したラベル y_i を持つ n 個の訓練データを考えます。マージン最大化は、次の最適化問題として書けます。

maximize M(beta_0, beta_1, ..., beta_p と M を動かす)
制約1: sum(beta_j^2) = 1 (j = 1, ..., p)
制約2: y_i * (beta_0 + beta_1*x_i1 + beta_2*x_i2 + ... + beta_p*x_ip) >= M (すべての i = 1, ..., n)

制約2は、各訓練データが超平面の正しい側にあることを保証します。制約1は係数の大きさをそろえる正規化で、これがあることで y_i * (beta_0 + beta_1*x_i1 + ... + beta_p*x_ip) の値が、i番目の訓練データから超平面までの垂直な距離そのものになります。2つの制約がそろうと、どの訓練データも超平面から M 以上離れていることになり、M はその超平面のマージンを表します。この問題は、M を最大にする beta_0, ..., beta_p を選ぶ問題になります。

使うときの注意

最大マージン分類器は、特徴量の数 p が大きいと訓練データに過学習することがあります。また、ここで説明した考え方は、データが超平面で完全に分離できることを前提にしています。完全には分離できないデータの扱いや、カーネルを使った境界の広げ方は、サポートベクターマシンやカーネルの項目で扱います。