《サポート・ベクター・マシン》

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

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

　今, $$N$$個の属性を持ったデータが$$M$$個与えられており,これを,$$N$$次元空間$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathbb{R}^{N}$の点$\Va_{1},} $$構文解析に失敗 (不明な関数「\Va」): {\displaystyle \Va_{2},\ldots,} $ $構文解析に失敗 (不明な関数「\Va」): {\displaystyle \Va_{M} \in \mathbb{R}^{N}} $と考える. 各点$構文解析に失敗 (不明な関数「\Va」): {\displaystyle \Va_{j}\ (j=1,2,\ldots,M)} $は2種類のクラスのいづれか一方に属しており, 対応する2値のラベル$$y_{j}\in \{-1,+1\}$$が与えられているとする. このとき, ラベルの値にしたがって点を判別する2クラスの判別問題を考える.

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

構文解析に失敗 (不明な関数「\begin{equation}」): {\displaystyle \begin{equation} 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}} 　　　　$(1)$

となるベクトル構文解析に失敗 (不明な関数「\Vw」): {\displaystyle $\Vw} $とスカラ$$b$$を次に示す最適化問題を解くことで算出する.

　一般的には, 与えられた点全てに対して式 (1) を満たす$構文解析に失敗 (不明な関数「\Vw」): {\displaystyle \Vw,b} $が存在するとは限らないので, 非負の変数$$\xi _{j}\ (j=1,2,\ldots ,M)$$を導入し, 次の制約条件

構文解析に失敗 (不明な関数「\begin{equation}」): {\displaystyle \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}\$$の和と構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle $\Vw} $のノルムができるだけ小さくなる線形関数を考える. すなわち, 次の二次計画問題を解き$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \Vw,b} $を算出する [2].

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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」): {\displaystyle \|\Vw\|^{2}_{2}$と$\sum_{j=1}^{M} \xi_{j}$} とのバランスをコントロールするパラメータである. また, $構文解析に失敗 (不明な関数「\Vw」): {\displaystyle \|\Vw\|^{2}_{2}} $は正則化項とも呼ばれ, これを小さくすることは判別関数に用いるデータの属性を少なくし, 過学習を防ぐ役割があるとされる [6]. 問題 (3) は, 1ノルムソフトマージンSVMと呼ばれる定式化である.

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

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

　双対問題 (4) の最適解を$$\alpha _{1}^{*},\alpha _{2}^{*},\ldots ,\alpha _{M}^{*}$$とすれば,KKT条件より主問題 (3) の最適解$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \Vw^{*},b^{*}$とは,$ \Vw^{*} = \sum_{j=1}^{M} \alpha_{j}^{*} y_{j} \Va_{j}} $となる関係があり, さらに$$0<\alpha _{k}^{*}<C$$となる添え字を$\$k$$とすれば, $構文解析に失敗 (不明な関数「\Va」): {\displaystyle b^{*} = \Va^{T}_{k}\Vw^{*}-y_{k}} $となることが示される. また, 特に添え字の集合$$SV=\{j|\alpha _{j}^{*}\not =0\}$$を定義すれば,$$j\in SV$$に対応するデータ$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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}

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

　SVMの最大の特徴は, 双対問題(4)を応用することで非線形な判別関数を構成できる点にある.非線形な判別関数を構成するためには, まず, 適当な非線形変換$$\phi :\mathbb {R} ^{N}\to {\mathcal {F}}\$$を使い各データ$構文解析に失敗 (不明な関数「\Va」): {\displaystyle \Va_{j}$} をより高い次元の特徴空間$\${\mathcal {F}}\$$の元へと射影する. 射影された$${\mathcal {F}}\$$の元$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \phi(\Va_{1}),\phi(\Va_{2}),\ldots,\phi(\Va_{M})} $に対して, $${\mathcal {F}}$$上での線形な判別関数を求めれば, 元の空間で見れば非線形な判別関数を求めたこととなる.

　ここで, 双対問題 (4) に注目すれば,$${\mathcal {F}}\$$上の内積$構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \phi(\Va_{i})^{T}\phi(\Va_{j})} $の値のみが得られれば定式化が可能であり, 特徴空間での点$構文解析に失敗 (不明な関数「\Va」): {\displaystyle \phi(\Va_{j})$} の座標を必ずしも必要としないことが分かる. そこで, SVMではカーネル関数と呼ばれる特殊な関数$構文解析に失敗 (不明な関数「\kernel」): {\displaystyle \kernel{\cdot}{\cdot}} $を用い元のデータ$構文解析に失敗 (不明な関数「\Vx」): {\displaystyle \Vx,\Vx' \in \mathbb{R}^{N}} $から直接$\${\mathcal {F}}\$$の元$構文解析に失敗 (不明な関数「\Vx」): {\displaystyle \phi(\Vx),\phi(\Vx')} $の内積$構文解析に失敗 (不明な関数「\Vx」): {\displaystyle \phi(\Vx)^{T}\phi(\Vx')$} を算出し, 双対問題の最適化により非線形の判別関数が求められる [1]. よく用いられる代表的なカーネル関数として, 多項式カーネル$構文解析に失敗 (不明な関数「\kernel」): {\displaystyle \kernel{\Vx}{\Vx'} = \left( \Vx^{T} \Vx' + c \right)^{d}} $やRBFカーネル$ 構文解析に失敗 (不明な関数「\kernel」): {\displaystyle \kernel{\Vx}{\Vx'} = \exp\left( -\| \Vx - \Vx' \|^{2}/ \sigma^{2} \right )} $,(ただし$$d$$は自然数のパラメータ, $$c,\sigma$$ は実数のパラメータである)などがある.

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

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

構文解析に失敗 (不明な関数「\Vx」): {\displaystyle f(\Vx) = \sum_{j \in SV}\alpha_{j}^{*} y_{j} \kernel{\Vx}{\Va_{j}} - b^{*}. } 　　　　　$(6)$

　すなわち, 判別関数$$f(\cdot )\$$は, サポート・ベクター $構文解析に失敗 (不明な関数「\Va」): {\displaystyle \Va_{j}\ (j \in SV)} $に対応するカーネル関数$構文解析に失敗 (不明な関数「\kernel」): {\displaystyle \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ö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ö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.