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

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

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

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

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

$f({\boldsymbol {a}}_{j})={\boldsymbol {a}}_{j}^{T}{\boldsymbol {w}}-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\,$　　　　$(1)\,$

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

　一般的には, 与えられた点全てに対して式 (1) を満たす${\boldsymbol {w}},b\,$が存在するとは限らないので, 非負の変数$\xi _{j}\ (j=1,2,\ldots ,M)\,$を導入し, 次の制約条件

${\begin{array}{lll}{\displaystyle {\boldsymbol {a}}_{j}^{T}{\boldsymbol {w}}-b+\xi _{j}\geq 1}&{\mbox{if}}&y_{j}=1,\\{\displaystyle {\boldsymbol {a}}_{j}{\boldsymbol {w}}-b-\xi _{j}\leq -1}&{\mbox{if}}&y_{j}=-1\end{array}}\,$　　　　$(2)\,$

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

$\left|{\begin{array}{l}\\\\\\\\\\\end{array}}\right.$ 最大化 $\textstyle {\frac {1}{2}}\|{\boldsymbol {w}}\|_{2}^{2}+C\ {\sum }_{j=1}^{M}\xi _{j}$ 　　　　$(3)\,$ 制約 $\textstyle {\boldsymbol {a}}_{j}^{T}{\boldsymbol {w}}-b+\xi _{j}\geq 1,\quad {\mbox{if }}y_{j}=1,$ $\textstyle {\boldsymbol {a}}_{j}^{T}{\boldsymbol {w}}-b-\xi _{j}\leq -1,\quad {\mbox{if }}y_{j}=-1,$ $\textstyle \xi _{j}\geq 0,\quad j=1,2,\ldots ,M$

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

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

$\left|{\begin{array}{l}\\\\\\\\\end{array}}\right.$ 最大化 $\textstyle -{\frac {1}{2}}\sum _{i=1}^{M}\sum _{j=1}^{M}y_{i}y_{j}{\boldsymbol {a}}_{i}^{T}{\boldsymbol {a}}_{j}\alpha _{i}\alpha _{j}+\sum _{j=1}^{M}\alpha _{j}$ 　　　　$(4)\,$ 制約 $\textstyle \sum _{j=1}^{M}y_{j}\alpha _{j}=0,$ $0\leq \alpha _{j}\leq C,\quad j=1,2,\ldots ,M$

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

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

$f({\boldsymbol {x}})={\boldsymbol {x}}^{T}{\boldsymbol {w}}^{*}-b^{*}=\sum _{j\in SV}\alpha _{j}^{*}y_{j}{\boldsymbol {x}}^{T}{\boldsymbol {a}}_{j}-b^{*}\,$　　　　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (5)\, }

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

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

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

　カーネル関数の値構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathcal{K} ( \boldsymbol{a}_{i}, \boldsymbol{a}_{j} ) \, } を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i-j\, } 成分とする構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle M\, } 次の対称行列を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle K\, } とすれば, $K\,$が半正定値行列となるようなカーネル関数をMercerカーネル(あるいは半正定値カーネル)と呼び, このようなカーネル関数であれば,構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathcal{K} ( \boldsymbol{a}_{i}, \boldsymbol{a}_{j} )=\phi(\boldsymbol{a}_{i})^{T}\phi(\boldsymbol{a}_{j})\, } となる特徴空間への変換構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \phi(\cdot)\, } が存在することが保証される. 多項式カーネルやRBFカーネルはMercerカーネルである [5].また, Mercerカーネルを用いるのであれば, 対応した双対問題は常に凹二次関数の最大化となり, 通常の二次計画問題の解法を用いれば大域的に最適化が可能である.

　すなわち, 双対問題の最適解を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha_{j}^{*}\, } とすれば, カーネル関数を用いた場合には, 次の非線形な判別関数が求められることとなる.

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(\boldsymbol{x}) = \sum_{j \in SV}\alpha_{j}^{*} y_{j} \mathcal{K} ( \boldsymbol{x}, \boldsymbol{a}_{j} )- b^{*}.\, } 　　　　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (6)\, }

　すなわち, 判別関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(\cdot)\, } は, サポート・ベクター ${\boldsymbol {a}}_{j}\ (j\in SV)\,$に対応するカーネル関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathcal{K} (\boldsymbol{x}, \boldsymbol{a}_{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.