サポートベクトルマシーン回帰 (SVR) メモ

サポートベクトルは分類機としてもちいられてきた(SVC)が、回帰にも応用できる。 ここでは、PRMLテキストの7章をもとに、SVRについて簡単に解説する。

目的変数$y$、説明変数$\{\boldsymbol{x_n}\}$の関係を、非線形関数$\boldsymbol{\phi}(\boldsymbol{x_n})$を用いて (ここで$n$はn番目のデータを表す) $$ y_n = y(\boldsymbol{x_n}) = \boldsymbol{\omega}^T\boldsymbol{\phi(\boldsymbol{x})} $$ と表されるとする。$\boldsymbol{\omega}$, $\boldsymbol{\phi}$の次元(要素数)は場合による。

観測値$t_n$と予測値$y_n$との差が小さくなるように$\boldsymbol{w_n}$をきめる。つまり、 $$ \frac{1}{2}\sum_{n=1}^N \{y_n -t_n\}^2 + \frac{\lambda}{2} || \boldsymbol{w} ||^2 $$ 「疎な解」を得るため(ほとんどのデータは予測値とほぼ同じと考え)、第１項の2乗関数を次のような$\epsilon$許容誤差関数($\epsilon$-insensitive error function)で置き換える(図7.6)。 $$ E_e (y(\boldsymbol{x})-t) = \left\{ \begin{array}{ll} 0 & |y(\boldsymbol{x}) - t| < \epsilon \\\\ |y(\boldsymbol{x}) - t| - \epsilon & {\rm other} \end{array} \right. $$

つまり、 $$ C\sum_{n=1}^N E_e(y(\boldsymbol{x_n})-t_n) + \frac{1}{2}||\boldsymbol{w}||^2 $$ を最小にする$\boldsymbol{w}$をもとめる。

許容誤差関数を使う代わりに、スラック変数を導入して表現する。$\pm \epsilon$のチューブの外側に高いコストを与えるように、$\xi$と$\hat{\xi}$を定義する。図に示すように、 $t_n > y(\boldsymbol{x_n}) + \epsilon$ に対しては$\xi_n > 0$を、 $t_n < y(\boldsymbol{x_n}) + \epsilon$ に対しては,$\hat{\xi}_n < 0$を対応させる。

制約条件として $$ t_n \le y(\boldsymbol{x_n}) + \epsilon + \xi_n,\quad t_n \ge y(\boldsymbol{x_n}) - \epsilon - \hat{\xi}_n \tag{1} $$ を課す。このようなスラック変数を用いると、SVRの誤差関数は $$ C\sum_{n=1}^N (\xi_n + \hat{\xi}_n) + \frac{1}{2}||\boldsymbol{w}||^2 \tag{2} $$ と表される。また、条件 $$\xi_n \ge 0, \quad \hat{\xi}_n \ge 0 \tag{3}$$ も必要である。誤差関数(2)を条件(1)と(3)のもとで最小化する係数を求める。

ラグランジュの未定定数$a_n\ge 0$, $\hat{a}_n \ge 0$, $\mu \ge 0$, $\hat{\mu} \ge 0$を使って

$$ L = C\sum_{n=1}^{N} (\xi_n + \hat{\xi}_n) + \frac{1}{2}||\boldsymbol{w}|| - \sum_{n=1}^N a_n (\epsilon + \xi_n + y_n - t_n) - \sum_{n=1}^N \hat{a}_n (\epsilon + \hat{\xi}_n + y_n - t_n) $$

の極値問題を解く。極値条件は $$ \frac{\partial L}{\partial \boldsymbol{w}} = 0\quad {\rm より}\quad \boldsymbol{w} = \sum_{n=1}^N (a_n - \hat{a}_n)\boldsymbol{\phi}(\boldsymbol{x_n}) \tag{4} $$ $$ \frac{\partial L}{\partial b} = 0\quad {\rm より}\quad \sum_{n=1}^N (a_n - \hat{a}_n) = 0 \tag{5} $$ $$ \frac{\partial L}{\partial \xi_n} = 0\quad {\rm より}\quad a_n + \hat{\mu}_n = 0 \tag{6} $$ $$ \frac{\partial L}{\partial \hat{\xi}_n} = 0\quad {\rm より}\quad \hat{a}_n + \hat{\mu}_n =0 \tag{7} $$ これらの条件を用いて$L$を変形すると、$\{a_n\}$と$\{\hat{a}_n\}$を変数とした$L$の極値問題に帰着できる。

$$ C\sum (\xi_n + \hat{\xi}_n) - \sum (\mu_n\xi_n + \hat{\mu}_n\hat{\xi}_n) - \sum a_n\xi_n - \sum \hat{a}_n\hat{\xi}_n = 0 $$$$ ||\omega ||^2 = \sum_{n=1}^N\sum_{m=1}^N (a_n -\hat{a}_n)(a_m -\hat{a}_m) k(\boldsymbol{x}_n, \boldsymbol{x}_m) $$

であるから

$$ \hat{L} (\boldsymbol{a}, \hat{\boldsymbol{a}}) = -\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^N (a_n -\hat{a}_n)(a_m -\hat{a}_m) k(\boldsymbol{x}_n, \boldsymbol{x}_m) - \epsilon\sum_{n=1}^N (a_n + \hat{a}_n) + \sum_{n=1}^N (a_n - \hat{a}_n)t_n \tag{8} $$

ここで、カーネルの定義

$$ k(\boldsymbol{x}_n, \boldsymbol{x'}_m) = \boldsymbol{\phi}(\boldsymbol{x})^T \boldsymbol{\phi}(\boldsymbol{x'}) \tag{9} $$

を用いた。 $a_n \ge 0$, $\hat{a}_n \ge 0$と$\mu_n \ge 0$, $\hat{\mu}_n\ge 0$および(6),(7)の条件を合わせると矩形制約(box constraint)

$$ 0\le a_n \le C,\quad 0\le \hat{a}_n \le C $$

が成り立つ。これと(5)式の条件のもとで$L$を最大にする問題になる。

得られた$a_n$, $\hat{a}_n$から、予測値は $$ y(\boldsymbol{x}) = \sum_{n=1}^N (a_n - \hat{a}_n)k(\boldsymbol{x}, \boldsymbol{x}_n) + b \tag{10} $$ により計算される。

不等式制約下での極値条件(KKT条件)、つまりラグランジュ未定乗数と対応する制約式の積がゼロという条件は $$ a_n (\epsilon + \xi_n + y_n - t_n) =0 \tag{11} $$ $$ \hat{a}_n (\epsilon + \hat{\xi}_n + y_n - t_n) =0 \tag{12} $$ $$ (C - a_n)\xi_n = 0 \tag{13} $$ $$ (C - \hat{a}_n)\hat{\xi}_n = 0 \tag{14} $$ これらの式から、$a_n$がゼロ以外の値をとるのは、$()$の中がゼロのとき、すなわちデータ点がチューブの上境界上か外側上にあるときであり、$\hat{a}_n$がゼロでないのは、チューブの下境界上か外側下にある場合である。

また、この2つが同時に成り立つことはないので、すべてのデータ点$\boldsymbol{x}_n$に対して$a_n$, $\hat{a}_n$のどちらかはゼロである。

よって、予測に寄与するのは、チューブの外側の点である。つまり、チューブの外側の点がサポートベクトルであるといえる。データが非常にばらついていて、チューブの外のデータ点がたくさんあるときはあまり良い推定が得られない(と思う。かえって線形回帰の方が良い場合もあるだろう)。

パラメータ$b$について

$0 < a_n <C$のとき、(11)より$\xi_n = 0$。(11)式より$\epsilon + y_n - t_n=0$である。これを $$ y(\boldsymbol{x})= \boldsymbol{\omega}^T\boldsymbol{\phi}(\boldsymbol{x}) + b $$ (テキストでは(7.1)式)に代入すると、(4)式も使って $$ b = t_n - \epsilon - \boldsymbol{\omega}^T\boldsymbol{\phi}(\boldsymbol{x}) = t_n - \epsilon - \sum_{m=1}^N (a_m - \hat{a}_m)k(\boldsymbol{x_n}, \boldsymbol{x}_m) $$ が得られる。実際には、このようにして得られた$b$の平均値を用いる。

チューブの幅$\epsilon$はパラメータであるが、これの代わりに、チューブの外にあるデータ数の割合の上限$\nu$を指定する方法もある。(Scholkoph, et.al. (2000))

パラメータ$\nu$, $C$は交差検定によりセットすることが多い。

scikit-learnでは、グリッドサーチやランダムサーチにより決定している。