サポートベクトルマシン(SVM)とは、2クラス線形識別関数の学習法のこと。
サポートベクトルマシンの導出
SVMでは標準座標系を用いて考える。 クラスラベル付き学習データの集合をとする。 は教師データ、マージンをとすると、 $$ |w^{T}x_{i} + b| \geq K $$ が成り立つ。係数ベクトルとバイアス項をで正規化すると、 $$ \left\{ \begin{array}{} w^{T}x_{i} + b \geq +1 & ( t_{i} = +1) \\ w^{T}x_{i} + b \leq -1 & ( t_{i} = -1) \end{array} \right. $$ となる。この場合分けは、 $$ t_{i} (w^{T}x_{i} + b) \geq 1 $$ のようにまとめることができる。
クラス間マージンは、各クラスのデータをの方向へ射影した長さの最小値、 $$ \rho(w,b) = \frac{1-b}{||w||} - \frac{-1-b}{||w||} $$ で与えられる。 最適な超平面の式をとすれば、この超平面は最大クラス間マージン、 $$ \rho(w_{0}, b_{0}) = max \, \rho (w, b) $$ を与える。最大マージンは最大クラス間マージンの1/2で与えられる。 したがって、最適識別超平面は、のノルムを最小にする解、 $$ w_{0} = min \, ||w|| $$ として求めることができる。
線形分離不可能な場合
線形分離が不可能な場合、変数を導入し、 $$ t_{i} (x^{T}x_{i} + b) -1 + \xi_{i} \geq 0 \\ \left\{ \begin{array} \xi_{i} = 0 & (マージン内で正しく識別できる場合) \\ 0 < \xi_{i} \leq 1 & (マージン境界を越えるが正しく識別できる場合) \\ \xi_{i} > 1 & (識別境界を越えて誤識別される場合) \end{array} \right. $$ とすると制約条件を満たすことができる。 変数をスラック変数と呼び、このような手法をソフトマージン識別器という。
非線形特徴写像
SVMは解が学習データの線形結合で表される識別超平面となる. 識別境界が学習の線形関数では表せないような場合には,誤差逆伝播法のように非線形識別関数を直接構成するのも1つの方法である. 別の方法としては,非線形特徴写像を用いて非線形特徴空間に写像し,その空間内での線形識別関数を用いる方法がある. しかし,どのような非線形特徴写像を用いるかは試行錯誤で決める必要がある. そこで,線形分離可能でない学習データは,非線形変換で高次元特徴空間へ写像することにより線形分離可能となる可能性がある,という予測を頼りに非線形写像を考える.
d次元の学習データと,その非線形写像の集合を考える. 線形写像空間のベクトルを $$ \varphi(x) = (\varphi_{0}(x)=1, \varphi_{1}(x), \dots, \varphi_{M}(x))^{T} $$ で表す.はバイアス項である.非線形特徴空間での線形識別関数を, $$ h(\varphi(x)) = \sum_{j=0} w_{j} \varphi_{j}(x) = w^{T}\varphi(x) $$ で表す.この非線形空間内でSVMを考えれば,最適識別超平面は, $$ w_{0} = \sum_{i=1} \alpha_{i} t_{i} \varphi(x_{i}) $$ となるが,このとき,識別関数が, $$ \begin{align} h(\varphi(x)) &= w_{0}^{T} \varphi(x) \\ &= \sum_{i=1} \alpha_{i} t_{i} \varphi(x_{i}) \varphi(x) \\ &= \sum_{i=1} \alpha_{i} t_{i} K(x_{i}, x) \end{align} $$ のように元の空間のベクトルの関数を用いて表せれば都合が良い. このようなを核関数という. 核関数はカーネル関数とも呼ばれる.
よく使われるカーネル関数に,多項式カーネルや動径基底関数カーネルがある.
v-サポートベクトルマシン
誤識別率は、学習データ数が変わると変わってしまう。 これを誤識別率にすることで、一般性を持たせることができる。 そこで、マージン誤りであるを導入したv-サポートベクトルマシンが考案された。