next up previous contents
次へ: データ作成 上へ: 提案手法 戻る: 教師あり機械学習法   目次

SVM

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

図: マージン最大化
\includegraphics[width=10cm]{svm.eps}

$\displaystyle f({\bf x})$ $\displaystyle =$ $\displaystyle sgn \left( \sum^{l}_{i=1} \alpha_i y_i K({\bf x}_i,{\bf x}) + b \right)$ (4.1)
$\displaystyle b$ $\displaystyle =$ $\displaystyle -\frac{max_{i,y_i=-1}b_i + min_{i,y_i=1}b_i}{2}$  
$\displaystyle b_i$ $\displaystyle =$ $\displaystyle \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$ は,

$\displaystyle sgn(x) \, =$ $\displaystyle 1$ $\displaystyle (x \geq 0)$ (4.2)
  $\displaystyle -1$ $\displaystyle (otherwise)$  

であり,また,各$ \alpha_i$ は式(4.4)と式(4.5)の制約のもと 式(4.3)の $ L(\alpha )$ を最大にする場合のものである.

$\displaystyle L({\alpha})$ $\displaystyle =$ $\displaystyle \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})$ (4.3)


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


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

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

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

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


next up previous contents
次へ: データ作成 上へ: 提案手法 戻る: 教師あり機械学習法   目次
平成25年2月12日