SVM(サポートベクトルマシン法)

本研究では村田の研究[13]を参考に 教師あり機械学習にSVM(サポートベクトルマシン法)を利用する.

サポートベクトルマシン法は， 空間を超平面で分割することにより 2つの分類からなるデータを分類する手法である． このとき，2つの分類が正例と負例からなるものとすると， 学習データにおける正例と負例の間隔(マージン)が 大きいもの(図3.2参照^3.2)ほど オープンデータで誤った分類をする可能性が低いと考えられ， このマージンを最大にする超平面を求め それを用いて分類を行なう． 基本的には上記のとおりであるが，通常， 学習データにおいてマージンの内部領域に 少数の事例が含まれてもよいとする手法の拡張や， 超平面の線形の部分を非線型にする拡張(カーネル関数の導入)がなされたものが 用いられる． この拡張された方法は，以下の識別関数を用いて分類することと等価であり， その識別関数の出力値が正か負かによって 二つの分類を判別することができる[14][10]．

$$f({\bf x}) = sgn \left( \sum^{l}_{i=1} \alpha_i y_i K({\bf x}_i,{\bf x}) + b \right)$$ (3.1)

$$b = -\frac{max_{i,y_i=-1}b_i + min_{i,y_i=1}b_i}{2}$$

$$b_i = \sum^l_{j=1} \alpha_j y_j K({\bf x}_j,{\bf x}_i)$$

ただし，${\bf x}$ は識別したい事例の文脈(素性の集合)を， ${\bf x}_{i}$と $y_i(i=1,...,l, y_i\in\{1,-1\})$は 学習データの文脈と分類先を意味し，関数 $sgn$ は，

$$sgn(x) \, = 1 (x \geq 0)$$ (3.2)

$$-1 (otherwise)$$

であり，また，各$\alpha_i$は式(3.4)と式(3.5)の制約のもと 式(3.3)の$L(\alpha )$を最大にする場合のものである．

$$L({\alpha}) = \sum^l_{i=1} \alpha_i - \frac{1}{2} \sum^l_{i,j=1} \alpha_i \alpha_j y_i y_j K({\bf x_i},{\bf x_j})$$ (3.3)

$$0 \leq \alpha_i \leq C \, \, (i=1,...,l)$$ (3.4)

$$\sum^l_{i=1} \alpha_i y_i = 0$$ (3.5)

また，関数$K$ はカーネル関数と呼ばれ，様々なものが 用いられるが本稿では以下の多項式のものを用いる．

$$K({\bf x},{\bf y}) = ({\bf x}\cdot{\bf y} + 1)^d$$ (3.6)

$C,d$は実験的に設定される定数である． 本稿ではすべての実験を通して$C$,$d$はそれぞれ1と2に固定した． ここで，$\alpha_i > 0$ となる ${\bf x}_i$ は， サポートベクトルと呼ばれ，通常，式(3.1)の和をとっている部分は この事例のみを用いて計算される． つまり，実際の解析には学習データのうちサポートベクトルと 呼ばれる事例のみしか用いられない．

サポートベクトルマシン法は 分類の数が2個のデータを扱うもので，通常これに ペアワイズ手法を組み合わせて用いることで， 分類の数が3個以上のデータを扱うことになる[15]．

ペアワイズ手法とは，N個の分類を持つデータの場合， 異なる二つの分類先のあらゆるペア(N(N-1)/2 個)を作り， 各ペアごとにどちらがよいかを2値分類器(ここでは サポートベクトルマシン法^3.3)で求め， 最終的にN(N-1)/2個の2値分類器の分類先の多数決により， 分類先を求める方法である．

本稿のサポートベクトルマシン法は， 上記のようにサポートベクトルマシン法とペアワイズ手法を 組み合わせることによって実現される． ただし, 本論文での実験では2値分類しか行っていないため, ペアワイズ手法は利用していない.

図: マージン最大化