Texが使えるようになったらしいので、SVMをしたためてみる

公開日:2018-11-28
最終更新:2018-11-28

はじめに

少し前からQrunchでTexが使えるようになったみたいですね。使っているのはMathJaxのようです。試しにということで、今さらながらではありますが、最近勉強したSVMの理論でもしたためてみることにします。間違っていたらそっと教えてください。

概要

分類したいデータ点を分ける分離面を引くのだが、仮に正しく分離できるとして、そのような面は無数に存在する。 そのとき、引いた分離面から最も近い点との距離(マージン)をなるべく遠くなるような分離面を引こうという思想で分離面を選ぶ。

点と直線の距離

点$(x_0,y_0)$と直線$ax+by+c=0$との距離$d$は $$d=\cfrac{|ax_0+by_0+c|}{\sqrt{a^2+b^2}}$$ で表される。 高校数学(多分数IIぐらい)でやったやつ。

マージン最大化

直線で分離するとき、分離面$\boldsymbol{w}^T \boldsymbol{x} - h=0$と点$\boldsymbol{x}_i$との距離$d_i$は点と直線の距離より、 $$ d_i = \cfrac{|\boldsymbol{w}^T \boldsymbol{x}_i + h|}{|\boldsymbol{w}|}$$ となる。$i$はデータ点のインデックスである。 ここで、符号関数を用いると、 \begin{eqnarray} {\rm sgn}(\boldsymbol{w}^T \boldsymbol{x} + h) = \begin{cases} 1 & ( \boldsymbol{w}^T\boldsymbol{x} + h > 0 ) \\ -1 & ( \boldsymbol{w}^T\boldsymbol{x} + h \le 0 ) \end{cases} \end{eqnarray} と表せる。これを分類ラベルに使えないかと考える。 ${\boldsymbol t}$を正解ラベルとすると、100%正しく分離できるなら少なくとも、

\begin{eqnarray} \begin{cases} t_i = 1 & \boldsymbol{w}^T\boldsymbol{x}_i + h \ge 1 \\ t_i = -1 & \boldsymbol{w}^T\boldsymbol{x}_i + h \le -1 \end{cases} \end{eqnarray} となっていれば十分条件を満たす。たぶんハードマージンと呼ばれるやつ。 すなわち、 $$t_i (\boldsymbol{w}^T \boldsymbol{x}_i + h) \ge 1$$ となればよい。 なお、$|\boldsymbol{w}^T \boldsymbol{x} + h|$ の最小値は1としている。 このとき、分離面に最も近い点${\boldsymbol x}_i$と分離面との距離$d_i$は \begin{align} \mathop{\rm arg\,min}\limits_i\ d_i &= \mathop{\rm arg\,min}\limits_i\ \cfrac{|\boldsymbol{w}^T \boldsymbol{x}_i + h|}{\boldsymbol{|w|}} \\ &= \cfrac{1}{|\boldsymbol{w}|} \quad(\because |\boldsymbol{w}^T \boldsymbol{x}_i + h| \ge 1) \end{align} となる。 分離面と分離面との最近接点との距離(マージン)を最大化したいので$$\mathop{\rm arg\,min}\limits_i d_i$$を最大化すればよい。 よって、 \begin{align} \mathop{\rm arg\,max}\limits_{{\boldsymbol w},h} \mathop{\rm arg\,min}\limits_i d_i &= \mathop{\rm arg\,max}\limits_{{\boldsymbol w},h} \cfrac{1}{|{\boldsymbol w}|} \\ &= \mathop{\rm arg\,min}\limits_{{\boldsymbol w},h} |{\boldsymbol w}| \end{align} となる。これを満たすような$\boldsymbol w, h$を求めれば分離面が定まる。 そして、この最適化問題は双対問題に置き換えて解く。

非線形計画問題(双対問題)の最適化

ある関数$f,g$に対して、以下のような問題を考える。 \begin{align} \min_{\boldsymbol x} f({\boldsymbol x}) \quad s.t.\ g_i({\boldsymbol x}) \le 0 \quad(i=1,\cdots,m) \end{align} $g$は制約条件などと呼ばれる。 この問題のラグランジュ関数は \begin{align} {\cal L}({\boldsymbol x},{\boldsymbol \lambda}) = f({\boldsymbol x}) + \sum^m_{i=1} \lambda_i g_i({\boldsymbol x}) \end{align} となる。ここで、ある${\boldsymbol x} = {\boldsymbol x}^\ast$に対して \begin{align} \max_{\boldsymbol \lambda} {\cal L}({\boldsymbol x}^\ast,{\boldsymbol \lambda}) \quad s.t.\ \lambda_i \ge 0 \end{align} を満たすと考える。先ほどのラグランジュ関数を代入すると、 \begin{align} \max_{\boldsymbol \lambda} {\cal L}({\boldsymbol x}^\ast,{\boldsymbol \lambda}) &= \max_{\boldsymbol \lambda} f({\boldsymbol x}^\ast) + \sum^m_{i=1} \lambda_i g_i({\boldsymbol x}^\ast) \\ &= \begin{cases} f({\boldsymbol x}^\ast) &({\rm when}\ g({\boldsymbol x}^\ast) \le 0\ {\rm for}\ \forall i) & \mathop{\rm arg\,max}\limits_{\boldsymbol \lambda}{\cal L} = 0\\ \infty &({\rm when}\ g({\boldsymbol x}^\ast) > 0\ {\rm for}\ \forall i) & \mathop{\rm arg\,max}\limits_{\boldsymbol \lambda}{\cal L} = \infty \end{cases} \end{align} よって、$g_i({\boldsymbol x}^\ast)\le0$のとき $$ \min_{\boldsymbol x} \max_{\boldsymbol \lambda} {\cal L}({\boldsymbol x},{\boldsymbol \lambda}) =\min_{{\boldsymbol x}^\ast} f({\boldsymbol x}^\ast) $$ となる。 ここで、最大最小不等式 $$ \min_{\boldsymbol x} \max_{\boldsymbol \lambda \ge 0} {\cal L}({\boldsymbol x},{\boldsymbol \lambda}) = \max_{\boldsymbol \lambda \ge 0} \min_{\boldsymbol x} {\cal L}({\boldsymbol x},{\boldsymbol \lambda}) $$ より、 \begin{align} \min_{\boldsymbol x} f({\boldsymbol x}) &= \min_{\boldsymbol x} \max_{\boldsymbol \lambda}{\cal L}({\boldsymbol x},{\boldsymbol \lambda}) \ge \max_{\boldsymbol \lambda \ge 0} \min_{\boldsymbol x} {\cal L}({\boldsymbol x},{\boldsymbol \lambda}) \end{align} となる。 等号成立条件は$f({\boldsymbol x})$が凸関数かつ$g({\boldsymbol x})$が線形の時である。

SVMを双対問題で解く

話を再びSVMに戻す。$\mathop{\rm arg\,max}\limits_{{\boldsymbol w},h} |{\boldsymbol w}|$を解きたかった。$|{\boldsymbol w}|\ge0$なので、$|{\boldsymbol w}|$が最小のとき$|{\boldsymbol w}|^2$も最小となる。 また、条件として$t_i ({\boldsymbol w}^T{\boldsymbol x}_i + h)\ge1$を課していた。 よって、SVMにおけるラグランジュ関数を以下のように定義する。 $$ {\cal L}({\boldsymbol w},h,{\boldsymbol \lambda}) = \cfrac{1}{2} |{\boldsymbol w}|^2 + \sum^N_{i=1} \lambda_i [1-t_i({\boldsymbol w}^T{\boldsymbol x}_i+h)] $$ $f = |w|^2/2$は下に凸な関数であり、$g = 1-t_i({\boldsymbol w}^T{\boldsymbol x}_i+h)$は線形なので等号成立条件を満たす。 ゆえに、双対問題 $$ \max_{\boldsymbol \lambda \ge 0} \min_{\boldsymbol w, h} {\cal L}({\boldsymbol w},h,{\boldsymbol \lambda}) $$ を解けばよい。 なお、 $$ \min_{\boldsymbol w, h} {\cal L} ({\boldsymbol w},h,{\boldsymbol \lambda}) $$ はラグランジュの未定乗数法と呼ばれる。 ラグランジュの未定乗数法では、${\boldsymbol w},h$に対する極値を求めればよい。 すなわち、$\boldsymbol w$に対する偏微分 \begin{align} \cfrac{\partial \cal L}{\partial w_k} &= \cfrac{\partial}{\partial w_k} \left\{ \cfrac{1}{2}(w^2_1+\cdots+w^2_N) + \sum^N_{i=1} \lambda_i [1-t_i(w_1x_{i,1}+\cdots+w_Nx_{i,N}+h)]\right\} \\ &= w_k + \sum^N_{i=1} \lambda_i (-t_i x_{i,k}) \\ &= w_k - \sum^N_{i=1} \lambda_i t_i x_{i,k} \end{align} が極値となればよいから $$ \cfrac{\partial {\cal L}}{\partial {\boldsymbol w}} = 0 \Rightarrow {\boldsymbol w} = \sum^N_{i=1} \lambda_i t_i {\boldsymbol x}_i $$ となる。 したがって、$\boldsymbol \lambda$が求まれば$\boldsymbol w$が求まる。 また、$h$に対する極値を求める。 \begin{align} \cfrac{\partial {\cal L}}{\partial h} &= \cfrac{\partial}{\partial h} \left\{ \cfrac{1}{2} |{\boldsymbol w}|^2 + \sum^N_{i=1} \lambda_i [1-t_i({\boldsymbol w}^T {\boldsymbol x}_i + h)]\right\}\\ &= - \sum^N_{i=1} \lambda_i t_i \end{align} これが極値となればよいから、 $$ \cfrac{\partial {\cal L}}{\partial h} = 0 \Rightarrow 0 = \sum^N_{i=1} \lambda_i t_i $$ となる。 これを先ほどのラグランジュ関数に代入すると、 \begin{align} {\cal L}({\boldsymbol w},h,{\boldsymbol \lambda}) &= \cfrac{1}{2}\left|\sum^N_{i=1} \lambda_i t_i {\boldsymbol x}_i \right|^2 + \sum^N_{i=1} \lambda_i - \sum^N_{i=1} \lambda_i t_i {\boldsymbol w}^T {\boldsymbol x}_i -h \sum^N_{i=1} \lambda_i t_i \\ &= \cfrac{1}{2}\left(\sum^N_{i=1} \lambda_i t_i {\boldsymbol x}_i \right) \cdot \left(\sum^N_{j=1} \lambda_j t_j {\boldsymbol x}_j \right) + \sum^N_{i=1} \lambda_i \\ &- \sum^N_{i=1} \lambda_i t_i \left(\sum^N_{j=1} \lambda_j t_j {\boldsymbol x}_j \right) \cdot x_i \left(\because \sum^N_{i=1}\lambda_i t_i = 0\right)\\ &= \sum^N_{i=1} \lambda_i + \cfrac{1}{2} \sum^N_{i=1} \sum^N_{j=1} \lambda_i \lambda_j t_i t_j {x}_i \cdot {x}_j - \sum^N_{i=1} \sum^N_{j=1} \lambda_i \lambda_j t_i t_j {x}_i \cdot {x}_j\\ &= \sum^N_{i=1} \lambda_i - \cfrac{1}{2} \sum^N_{i=1} \sum^N_{j=1} \lambda_i \lambda_j t_i t_j {x}_i \cdot {x}_j \end{align} となる。よって、 \begin{align} \mathop{\rm arg\,max}\limits_{\boldsymbol \lambda \ge 0} {\cal L}({\boldsymbol w},h,{\boldsymbol \lambda}) = \mathop{\rm arg\,max}\limits_{\boldsymbol \lambda \ge 0} \left\{ \sum^N_{i=1} \lambda_i - \cfrac{1}{2} \sum^N_{i=1} \sum^N_{j=1} \lambda_i \lambda_j t_i t_j {\boldsymbol x}_i \cdot {\boldsymbol x}_j \right\} \end{align} ただし、 $$ \sum^N_{i=1} \lambda_i t_i = 0 \quad, \quad 1 - t_i({\boldsymbol w}^T {\boldsymbol x}_i+h) \le 0 $$ を満たす。

以上より、${\boldsymbol w}$と$h$の最適値は $$ {\boldsymbol w}^\ast = \sum_{i\in S} \lambda^\ast_i t_i {\boldsymbol x}_i $$ となる。制約条件${\boldsymbol w}^T{\boldsymbol x}-h=\pm 1$上の$h$が最適解となるから、 $$ h^\ast = ({\boldsymbol w}^\ast)^T {\boldsymbol x}_s - t_s \quad({\boldsymbol x}_s,\ s\in S : {\rm support\ vector}) $$ よって、マージン最大となる識別器(SVM)は \begin{align} y &= \mathop{\rm sgn}\limits \left[ ({\boldsymbol w}^\ast)^T {\boldsymbol x} - h^\ast \right]\\ &=\mathop{\rm sgn}\limits \left( \sum_{i \in S}\lambda_i^\ast t_i {\boldsymbol x}_i^T {\boldsymbol x} - h^\ast \right) \end{align} となる。$y$は予測ラベルである。 なお、 $$ \mathop{\rm arg\,max}\limits_{{\boldsymbol \lambda} \ge 0} {\cal L}({\boldsymbol \lambda}) $$ は解析的に解くのは困難なため、最急降下法やSMOアルゴリズムなどの最適化アルゴリズムによって求める。

最大最小不等式

$$ g(z) \equiv \inf_w f(z,w) $$ とする。 このとき、 $$ g(z) \le f(z,w) \quad {\rm for}\ \forall z,w $$ 両辺の$\sup_z$を取ると、 $$ \sup_z g(z) \le \sup_z f(z,w) \quad {\rm for}\ \forall w $$ 定義より、 $$ \sup_z \inf_w f(z,w) \le \sup_z f(z,w) \quad {\rm for}\ \forall w $$ 任意のについて成立するため $$ \sup_z \inf_w f(z,w) \le \inf_w \sup_z f(z,w) $$

記事が少しでもいいなと思ったらクラップを送ってみよう!
36
+1
@sashimimochiの技術ブログ

よく一緒に読まれている記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう
目次をみる

技術ブログをはじめよう

Qrunch(クランチ)は、ITエンジニアリングに携わる全ての人のための技術ブログプラットフォームです。

技術ブログを開設する

Qrunchでアウトプットをはじめよう

Qrunch(クランチ)は、ITエンジニアリングに携わる全ての人のための技術ブログプラットフォームです。

Markdownで書ける

ログ機能でアウトプットを加速

デザインのカスタマイズが可能

技術ブログ開設

ここから先はアカウント(ブログ)開設が必要です

英数字4文字以上
.qrunch.io
英数字6文字以上
ログインする