サポートベクトルマシンとは

高い認知性能があり、クラス分類、回帰などの分野で盛んに実用される識別関数であるサポートベクトルマシン (SVM) について話を進めていきます。詳しい解説は例によって Wikipedia 辺りを読んだほうが早いでしょう。

SVM ではモデルパラメータがある凸最適化問題の解として求まるため、局所解があればそれが大域解にもなるという点が大きな特徴として挙げられます。

SVM は疎な解 (sparse solution) を持ち、訓練データの一点だけに対してカーネル関数を計算することで新しい入力データの予測をするアルゴリズムです。機械学習の分野で高い認識性能を誇り、パターン認識や回帰分析などに応用されます。

最大マージン分類

訓練データ点が特徴空間 Φ(x) において線形分離可能である場合に、線形モデルを用いて二値分類問題を解くことを考えます。 SVM においては分類境界はマージンを最大化するものが選ばれます。

線形モデルの式は

y(x) = w^T{\phi}(x)+b

Φ(x) はある固定された特徴空間変換関数、 b をバイアスパラメータとします。 W はあるひと組のパラメータです。

超平面 y(x) = 0 から点 x までの距離は |y(x)|/||w|| で与えられます。分類境界から点 Xn までの距離は次式で表されます。

\frac {t_ny(Xn)} {||w||} = \frac {t_n(w^T{\phi}(X_n) + b)} {||w||}

マージンは訓練データと分類境界の最短距離です。マージンを最大化する w と b を求めますので、次の最適化問題を解くことでこれらが得られます。

arg max(w,b) \{\frac {1} {||w||} min(n)[t_n(w^T{\phi}(x_n) + b)] \}

この最適化問題を解くのは複雑なので式を変形します。過程は教科書に譲るとして、結局のところ最適化問題は単に ||w||^-1 を最大化する問題に帰着します。この最大化問題は ||w||^2 を最小化する問題と等価です。

マージンを最大化する解は次式で求まります。

argmax(w,b) \frac {1} {2} ||w||^2 \\
ただし \\
t_n(w^t{\phi}(x_n) + b) {\ge} 1\\
n = 1, ..., N

重なりのあるクラス分布、多クラス SVM といった問題は今は考えないことにします。次回はカーネル関数と実際に分類器を実装して動かす流れを説明します。