統計的機械学習の数理100問（18/20） - 「大人の教養・知識・気付き」を伸ばすブログ

　いい加減時代の潮流に乗ろうということで機械学習を学びたいと思う。またRはともかくとしてPythonは未経験であるため、丁度良い書籍として

統計的機械学習の数理100問 with R (with R) (機械学習の数理100問シリーズ)

作者:讓, 鈴木
共立出版

Amazon

統計的機械学習の数理100問 with Python (機械学習の数理100問シリーズ)

作者:讓, 鈴木
共立出版

Amazon

を用いることにする。

8.　サポートベクトルマシン
- 8.1　最適な境界
- 8.2　最適化の理論

8.　サポートベクトルマシン

サポートベクトルマシンは $y_i\pm1$ のサンプル $(\boldsymbol{x}_1,y_1),\cdots,(\boldsymbol{x}_n,y_n)$ が与えられたときに $\boldsymbol{x}_i$ と境界の距離( $i=1,\cdots n$ ])の最小値を最大にする分類の方法である。

$y_i=\pm1$ となるサンプルがある平面で分類されていない場合にも一般化される。境界が平面でない場合にも一般化される。

一般の $K$ クラスの場合にも、回帰の場合にも適用される。

8.1　最適な境界

　クラス数が $K=2$ で $y_1,\cdots,y_n\in\{-1,1\}$ と仮定する。

平面と点の距離　 $(x,y)\in\mathbb{R}^2$ と平面 $l:aX+bY+c=0,$ $a,b,\in\mathbb{R}$ の距離は

$\begin{aligned} \displaystyle{\frac{|ax+by+c|}{\sqrt{a^2+b^2}}} \end{aligned}$

で与えられる。

( $\because$ 　 $(x,y)$ から直線 $l$ に下した垂線の足を $(x_0,y_0)$ と書くと、その垂線 $l^{\prime}$ は $l$ の法線であって、 $t\in\mathbb{R}$ を用いて

$\begin{aligned} l^{\prime}:\displaystyle{\frac{X-x_0}{a}}=\displaystyle{\frac{Y-y_0}{b}}=t \end{aligned}$

と書ける。垂線の足 $(x_0,y_0)$ は $l$ 上の点であり、 $(x,y)$ は $l^{\prime}$ 上の点であるから、

$\begin{aligned} \begin{cases} ax_0+by_0+c=0\\ \displaystyle{\frac{x-x_0}{a}}=\displaystyle{\frac{y-y_0}{b}}=t \end{cases} \end{aligned}$

が成立し、ここから $x_0,y_0$ を消去することで $x_0=x-at,y_0=y-bt,$ $a(x-at)+b(y-bt)+c=0$ を得る。したがって

$\begin{aligned} t=\displaystyle{\frac{ax+by+c}{a^2+b^2}} \end{aligned}$

を得、これを用いることで求める距離は

$\begin{aligned} \sqrt{(x-x_0)^2+(y-y_0)^2}=\sqrt{(a^2+b^2)t^2}=\displaystyle{\frac{|ax+by+c|}{\sqrt{a^2+b^2}}} \end{aligned}$

である。　 $\blacksquare$ )

　これは一般の $p$ 次元に拡張することができ、 $\boldsymbol{x}\in\mathbb{R}^p$ と平面 $\beta_0+\beta_1X_1+\cdots+\beta_pX_p=0$ の距離は、 $\boldsymbol{x}={}^{t}(x_1,\cdots,x_p)$ として、

$\begin{aligned} d(\boldsymbol{x})=\displaystyle{\frac{\left|\beta_0+\beta_1x_1+\cdots+\beta_px_p\right|}{\sqrt{\displaystyle{\sum_{i=1}^{p}\beta_i^2}}}} \end{aligned}$

である。 $\|\boldsymbol{\beta}\|_2=1$ となるように $\beta_0\in\mathbb{R},\boldsymbol{\beta}={}^{t}(\beta_1,\cdots,\beta_p)\in\mathbb{R}^p$ を同じ定数で割ることにより正規化することで

$\begin{aligned} d(\boldsymbol{x})=\left|\beta_0+\beta_1x_1+\cdots+\beta_px_p\right| \end{aligned}$

と書ける。
　次の議論のために、

$\begin{aligned} y_1(\beta_0+\boldsymbol{x}_1\boldsymbol{\beta}),\cdots,y_n(\beta_0+\boldsymbol{x}_1\boldsymbol{\beta})\geq0 \end{aligned}$

が成立するような $\beta_0\boldsymbol{\beta}$ が存在するとき、その標本は平面によって分離可能であるとする。
　サンプルが分離可能のとき、 $y_i\pm1$ のサンプルを分離する平面は無数にある。まず分離可能なサンプルに対して、両者の間にどのサンプルも含まないような2つの平面のうち、その距離が最大になるものを求める。そして新しいデータに対しての境界は平行な両者のちょうど中間にある平面だとする。そのためにはサンプル $(\boldsymbol{x}_1,y_1),\cdots,(\boldsymbol{x}_n,y_n)$ に対して、各点 $\boldsymbol{x}_i$ と平面 $\beta_0+X_1\beta_1+\cdots+X_p\beta_p=0$ の距離の最小値 $M=\displaystyle{\min_{i}d(\boldsymbol{x}_i)}$ を最大にすればよい。
　一般性を失うことなく、平面の係数が $\|\beta\|_2=1$ だと仮定すれば、 $d(\boldsymbol{x}_i)=y_i(\beta_0+{}^{t}\boldsymbol{x}_i\boldsymbol{\beta})$ となるから、最終的に

$\begin{aligned} M=\displaystyle{\min_{i=1,\cdots,n}y_i(\beta_0+{}^{t}\boldsymbol{x}\boldsymbol{\beta})} \end{aligned}$

を最大にするような $\beta_0,\boldsymbol{\beta}$ を求める問題になる。その場合には $M=y_i(\beta_0+{}^{t}\boldsymbol{x}\boldsymbol{\beta})$ の等号が成立するような $\{1,\cdots,n\}$ の部分集合が境界 $\beta_0,\boldsymbol{\beta}$ およびマージン $M$ を決定づける。

　サンプルが分離可能であったとしても、同じ分布にしたがう $n$ 組の別のサンプルに対しても分離可能であるとは限らない。むしろ一般的な分離可能でないサンプルに対しての最適化問題の定式化が必要になる。これまでの定式化を一般化して $\gamma\geq0$ として

$\begin{aligned} \displaystyle{\sum_{i=1}^{n}\varepsilon_i }\leq\gamma \end{aligned}$

および

$\begin{aligned} y_i\left(\beta_0+{}^{t}\boldsymbol{\beta}\boldsymbol{x}_i \right)\geq M(1-\varepsilon_i),i=1,\cdots,n \end{aligned}$

を満足する範囲で $(\beta_0,\boldsymbol{\beta})\in\mathbb{R}^p\times\mathbb{R}$ および $\varepsilon_i\geq0,i=1,\cdots,n$ を動かして、 $M$ の最大値を求める。
　分離可能なサンプルに対しては、 $\varepsilon_1=\cdots=\varepsilon_n=0$ 、すなわち $\gamma=0$ についての問題を解けばよい。 $M=y_i$ $(\beta_0+{}^{t}\boldsymbol{x}_i)\boldsymbol{\beta}$ となるような $i$ 以外にも $\varepsilon_i\gt0$ であるような $i$ も、マージン $M$ のサポートベクトルになる。このとき最適な境界の $\beta_0,\boldsymbol{\beta}$ の決定がより多くのサンプルでなされるようになる。ただし推定が鈍感になるため、 $\gamma$ はクロスバリデーションなどで適正に設定する必要がある。
　分離可能でない場合、 $\gamma$ の値を小さくしすぎると解が存在しなくなる。実際 $\gamma=0$ であれば $\varepsilon_i=0$ で

$\begin{aligned} y_i\left(\beta_0+{}^{t}\boldsymbol{\beta}\boldsymbol{x}_i \right)\geq M(1-\varepsilon_i),i=1,\cdots,n \end{aligned}$

を満たさないものが1個はあるため、解が無くなる。また境界の反対側にある $i$ の個数が $\gamma$ を超えれば $\beta_0,\boldsymbol{\beta}$ の解が存在しなくなる。
　サポートベクトルマシンの問題は、

$\begin{aligned} L_P=\displaystyle{\frac{1}{2}\left\|\boldsymbol{\beta}\right\|_2}+C\displaystyle{\sum_{i=1}^{n}\varepsilon_i}-\displaystyle{\sum_{i=1}^{n}\alpha_i\left\{y_i(\beta_0+{}^{t}\boldsymbol{x}_i\boldsymbol{\beta})-(1-\varepsilon_i)\right\} }-\displaystyle{\sum_{i=1}^{n}\mu_i\varepsilon_i} \end{aligned}$

を最小にするような $\beta_0,\boldsymbol{\beta},\varepsilon_i,i=1,2,\cdots,n$ を見出す問題として定式化される。 $\|\boldsymbol{\beta}\|$ を最小にすることは $\boldsymbol{\beta}$ を $\displaystyle{\frac{\boldsymbol{\beta}}{M}}$ に正規化する前の $M$ を最大化することに相当する。ここで $C$ はコストを意味し、これを $\gamma$ の代わりに用いる。最後の2項が制約、 $\alpha_i,\mu_i\geq0,i=1,2,\cdots,n$ が $\mathrm{Langrange}$ 係数である。

8.2　最適化の理論

　 $f_j(\boldsymbol{\beta})\leq0,j=1,\cdots,m$ のもとで $f_0(\boldsymbol{\beta})$ を最小にするような $\boldsymbol{\beta}\in\mathbb{R}^p$ を求める問題で、そのような解が存在することを仮定し、そのような $\boldsymbol{\beta}=\boldsymbol{\beta}^{*}$ だとする。
　まず $\boldsymbol{\alpha}={}^{t}(\alpha_1,\cdots,\alpha_n)\in\mathbb{R}^m$ に対して

$\begin{aligned} L(\boldsymbol{\alpha},\boldsymbol{\beta})=f_0(\boldsymbol{\beta})+\displaystyle{\sum_{j=1}^{m}\alpha_jf_j(\boldsymbol{\beta})} \end{aligned}$

を定義すると、任意の $\boldsymbol{\beta}\in\mathbb{R}^p$ について

$\begin{aligned} \displaystyle{\sup_{\alpha\geq\boldsymbol{0}}L(\boldsymbol{\alpha},\boldsymbol{\beta})}=\begin{cases} f_0(\boldsymbol{\beta}),&f_1(\boldsymbol{\beta})\leq0,\cdots,f_m(\boldsymbol{\beta})\leq0,\\ \ +\infty,&\mathrm{otherwise} \end{cases} \end{aligned}$

が成立する。
　また

$\begin{aligned} \displaystyle{\inf_{\boldsymbol{\beta}}\sup_{\boldsymbol{\alpha}\geq\boldsymbol{0}}L(\boldsymbol{\alpha},\boldsymbol{\beta}) }\geq \displaystyle{\sup_{\boldsymbol{\beta}}\inf_{\boldsymbol{\alpha}\geq\boldsymbol{0}}L(\boldsymbol{\alpha},\boldsymbol{\beta}) } \end{aligned}$

が成り立つ。
　 $f_i(\boldsymbol{\beta})\leq0,i=1,\cdots,m$ のもとで $f_0(\boldsymbol{\beta})$ を最小にする問題を主問題、 $\boldsymbol{\alpha}\geq\boldsymbol{0}$ のもとで $g(\boldsymbol{\alpha})=\displaystyle{\inf_{\boldsymbol{\beta}}}L(\boldsymbol{\alpha},\boldsymbol{\beta})$ を最大にする問題をその双対問題という。

8. サポートベクトルマシン

8.1 最適な境界

8.2 最適化の理論

8.　サポートベクトルマシン

8.1　最適な境界

8.2　最適化の理論