《サポート・ベクター・マシン》のソースを表示

'''【さぽーと・べくたー・ましん (support vector machine) 】'''

　サポート・ベクター・マシン (SVM) は, 判別関数を求める教師付き学習法のひとつである. 

　今, $N$個の属性を持ったデータが$M$個与えられており,これを,$N$次元空間$\mathbb{R}^{N}$の点$\Va_{1},$$\Va_{2},\ldots,$ $\Va_{M} \in \mathbb{R}^{N}$と考える.各点$\Va_{j}\ (j=1,2,\ldots,M)$は2種類のクラスのいづれか一方に属しており,対応する2値のラベル$y_{j} \in \{-1,+1\}$が与えられているとする.このとき, ラベルの値にしたがって点を判別する2クラスの判別問題を考える.

　SVMでは線形関数を用いた判別を行う.$N$次元の法線ベクトル$\Vw$および実数$b$で定まる線形関数を$f(\Vx) = \Vx^{T} \Vw - b$ とすれば,与えられたデータおよびラベルにしたがって,


\begin{equation}
\label{eq:線形分離可能}
f(\Va_{j}) = \Va_{j}^{T}\Vw - b \left\{
\begin{array}{ll}
 > 0 & \mbox{if}\ \  y_{j} = 1,\\
 < 0 & \mbox{if}\ \  y_{j} = -1,
\end{array}
\right.\quad j=1,2,\ldots,M
\end{equation}


となるベクトル$\Vw$とスカラ$b$を次に示す最適化問題を解くことで算出する.

　一般的には, 与えられた点全てに対して式\,(\ref{eq:線形分離可能})を満たす$\Vw,b$が存在するとは限らないので,非負の変数$\xi_{j}\ (j=1,2,\ldots,M)$を導入し, 次の制約条件


\begin{equation}
 \begin{array}{lll}
 {\displaystyle  \Va_{j}^{T} \Vw - b + \xi_{j} \geq 1 }
   & \mbox{if}& y_{j} = 1, \\
 {\displaystyle  \Va_{j} \Vw - b - \xi_{j} \leq -1 }
   & \mbox{if}& y_{j} = -1
\end{array}
\label{eq:ConstraintsWithSlack}
\end{equation}


のもと,$\xi_{j}$の和と$\Vw$のノルムができるだけ小さくなる線形関数を考える.すなわち,次の二次計画問題を解き$\Vw,b$を算出する [?].


\begin{equation}
 \left|
\begin{array}{ll}
 \mbox{最小化} 
  & { % \displaystyle 
      \frac{1}{2}\|\Vw\|_{2}^{2} + C \sum_{j=1}^{M} \xi_{j}
    }\\
 \mbox{制約}
   &{ % \displaystyle 
      \Va_{j}^{T} \Vw - b + \xi_{j} \geq 1,
         \quad \mbox{if } y_{j} = 1,}\\
   & { % \displaystyle
      \Va_{j}^{T} \Vw - b - \xi_{j} \leq -1,
         \quad \mbox{if } y_{j} = -1,}\\
   & { % \displaystyle
      \xi_{j} \ge 0, \quad j=1,2,\ldots,M}
\end{array}


ここで,$C$はあらかじめ設定された正の定数で,$\|\Vw\|^{2}_{2}$と$\sum_{j=1}^{M} \xi_{j}$とのバランスをコントロールするパラメータである.また,$\|\Vw\|^{2}_{2}$は正則化項とも呼ばれ,これを小さくすることは判別関数に用いるデータの属性を少なくし,過学習を防ぐ役割があるとされる [?].問題(??)は,1ノルムソフトマージンSVMと呼ばれる定式化である.

　通常は,この問題の双対問題を考え最適化を行う [?].$\alpha_{1},\alpha_{2},\ldots,\alpha_{M}$ を双対変数とすれば,問題(??)の双対問題は


\begin{equation}
\left|
\begin{array}{ll}
 \mbox{最大化}
  & { %\displaystyle 
      - \frac{1}{2} \sum_{i=1}^{M}\sum_{j=1}^{M}
         y_{i}y_{j}\Va_{i}^{T}\Va_{j}\alpha_{i}\alpha_{j}
      + \sum_{j=1}^{M} \alpha_{j}
    }\\
 \mbox{制約}
   & { %\displaystyle
       \sum_{j=1}^{M} y_{j} \alpha_{j}= 0,
    }\\
   & { 0 \leq \alpha_{j} \leq C,\quad j=1,2,\ldots,M
     }
\end{array}
\right.
\label{eq:StandradWolfeDualwithQ}
\end{equation}


と書くことができ,これは1本の等式制約と各変数の上下限制約のみの凹二次関数の最大化となる.この特殊構造を用いた最適化アルゴリズム [?, ?] が知られており,データ数$(M)$が数10万を超えるような大規模問題であっても,高速に最適化が可能である.

　双対問題(??)の最適解を$\alpha^{*}_{1},\alpha^{*}_{2},\ldots,\alpha^{*}_{M}$とすれば,KKT条件より主問題(??)の最適解$\Vw^{*},b^{*}$とは,$ \Vw^{*} = \sum_{j=1}^{M} \alpha_{j}^{*} y_{j} \Va_{j}$となる関係があり,さらに$0<\alpha_{k}^{*}<C$となる添え字を$k$とすれば,$b^{*} = \Va^{T}_{k}\Vw^{*}-y_{k}$となることが示される.また,特に添え字の集合$SV=\{j|\alpha_{j}^{*} \not = 0 \}$を定義すれば,$j \in SV$に対応するデータ$\Va_{j}$をサポート・ベクターと呼ぶ.したがって,判別関数は双対問題の最適解とサポート・ベクターにより次のように表されることとなる.


\begin{equation}
\label{eq:線形判別関数}
 f(\Vx) = \Vx^{T} \Vw^{*} - b^{*}
        = \sum_{j \in SV} \alpha_{j}^{*} y_{j}
                       \Vx^{T} \Va_{j} - b^{*} 
\end{equation}


さらに,双対問題(??)や主問題(??)は,サポート・ベクター以外を全て取り除いても最適解は不変であり,これらの点はSVMでの判別にはまったく寄与していないことになる.

　SVMの最大の特徴は,双対問題(??)を応用することで非線形な判別関数を構成できる点にある.非線形な判別関数を構成するためには,まず,適当な非線形変換$\phi: \mathbb{R}^{N} \to {\cal F}$を使い各データ$\Va_{j}$をより高い次元の特徴空間${\cal F}$の元へと射影する.射影された${\cal F}$の元$\phi(\Va_{1}),\phi(\Va_{2}),\ldots,\phi(\Va_{M})$に対して,${\cal F}$上での線形な判別関数を求めれば,元の空間で見れば非線形な判別関数を求めたこととなる.

　ここで,双対問題(??)に注目すれば,${\cal F}$上の内積$\phi(\Va_{i})^{T}\phi(\Va_{j})$の値のみが得られれば定式化が可能であり,特徴空間での点$\phi(\Va_{j})$の座標を必ずしも必要としないことが分かる.そこで, SVMではカーネル関数と呼ばれる特殊な関数$\kernel{\cdot}{\cdot}$を用い元のデータ$\Vx,\Vx' \in \mathbb{R}^{N}$から直接${\cal F}$の元$\phi(\Vx),\phi(\Vx')$の内積$\phi(\Vx)^{T}\phi(\Vx')$を算出し,双対問題の最適化により非線形の判別関数が求められる [?].よく用いられる代表的なカーネル関数として,多項式カーネル$\kernel{\Vx}{\Vx'} = \left( \Vx^{T} \Vx' + c \right)^{d}$やRBFカーネル$ \kernel{\Vx}{\Vx'} = \exp\left( -\| \Vx - \Vx' \|^{2}/ \sigma^{2} \right )$,(ただし$d$は自然数のパラメータ,$c,\sigma$ は実数のパラメータである)などがある.

　カーネル関数の値$\kernel{\Va_{i}}{\Va_{j}}$を$i-j$成分とする$M$次の対称行列を$K$とすれば,$K$が半正定値行列となるようなカーネル関数をMercerカーネル(あるいは半正定値カーネル)と呼び,このようなカーネル関数であれば,$\kernel{\Va_{i}}{\Va_{j}}=\phi(\Va_{i})^{T}\phi(\Va_{j})$となる特徴空間への変換$\phi(\cdot)$が存在することが保証される.多項式カーネルやRBFカーネルはMercerカーネルである [?].また,Mercerカーネルを用いるのであれば,対応した双対問題は常に凹二次関数の最大化となり,通常の二次計画問題の解法を用いれば大域的に最適化が可能である.

　すなわち,双対問題の最適解を$\alpha_{j}^{*}$とすれば,カーネル関数を用いた場合には,次の非線形な判別関数が求められることとなる.


\begin{equation}
 f(\Vx) = \sum_{j \in SV}\alpha_{j}^{*} y_{j}
                       \kernel{\Vx}{\Va_{j}} - b^{*}.
\end{equation}


　すなわち,判別関数$f(\cdot)$は,サポート・ベクター $\Va_{j}\ (j \in SV)$に対応するカーネル関数$\kernel{\Vx}{\Va_{j}}$の重ね合せとして算出されると見ることができる.



----

'''参考文献'''

[1] B. E. Boser, I. M. Guyon, and V. N. Vapnik, "A training algorithm for optimal margin classifiers," in ''Proceedings of the fifth annual workshop on Computationa learning theory'', USA, 144-152, 1992.

[2] C. Cortes and V. Vapnik, "Support-vector networks," ''Machine learning'', '''20''' (1995), 273-297.

[3] T. Joachims, "Making large-scale support vector machine learning practical," in ''Advances in Kernel Methods'', B. Sch&ouml;lkopf, C. Burges, and A. Smola, eds., The MIT Press, 169-184, 1999.

[4] J. C. Platt, "Fast training of support vector machines using sequential minimal optimization," in ''Advances in Kernel Methods'', B. Sch&ouml;lkopf, C. Burges, and A. Smola, eds., The MIT Press, 185-208. 1999.

[5] J. Shawe-Taylor and N. Cristianini, ''Kernel Methods for Pattern Analysis'', Cambridge University Press, 2004.

[6] V. N. Vapnik, ''The nature of statistical learning theory'', Statistics for Engineering and Information Science, Springer-Verlag, 2000.