「大人の教養・知識・気付き」を伸ばすブログ

※今月(8月)は一部コンテンツを隔週更新にします(夏休みです…)。 一流の大人(ビジネスマン、政治家、リーダー…)として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。

MENU

統計的機械学習の数理100問(18/20)

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

を用いることにする。

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=2y_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})を最大にする問題をその双対問題という。

プライバシーポリシー お問い合わせ