機械学習基礎理論独習

誤りがあればご指摘いただけると幸いです。数式が整うまで少し時間かかります。リンクフリーです。

勉強ログです。リンクフリーです
目次へ戻る

ソフトマージン

ハードマージンとの違い

2値分類について考えます。
訓練データが{\bf x}_1,\ldots,{\bf x}_NN個の入力ベクトルと
それぞれに対応する目標値t_1,\ldots,t_N(t_n\in\{-1,1\})からなり、
未知のデータ点{\bf x}y({\bf x})={\bf w}^\top{\boldsymbol\phi}({\bf x})+bの符号について分類されるとします。

と、ここまではハードマージンと同じですが、違いは
訓練データは特徴空間で線形分離可能と仮定しないことです。

下図のようにマージンの内側に点が入り込んでいます。

f:id:olj611:20210413122944p:plain:w300

ハードマージンの主問題と比較

ハードマージンの主問題は以下です。

\newcommand{\argmin}{\mathop{\rm arg~min}\limits}\begin{eqnarray}
&&\argmin_{{\bf w},b}\frac{1}{2}||{\bf w}||^2,\\
&&{\rm s.t.}\ \ t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b\geq1\tag{1}
\end{eqnarray}

ソフトマージンの主問題は以下です。

\newcommand{\argmin}{\mathop{\rm arg~min}\limits}\begin{eqnarray}
&&\argmin_{{\bf w},b,{\boldsymbol\xi}}\frac{1}{2}||{\bf w}||^2+C\sum_{n=1}^N\xi_i,\\
&&{\rm s.t.}\ \ t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)\geq1-\xi_n,\hspace{10px}\xi_n\geq0\tag{2}
\end{eqnarray}

(2)\xi_nはスラック変数と呼ばれます。
\xiは日本語では「グザイ」、「クシー」と呼ぶことが多いようです。

主問題を考察


・マージンの外側
 t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)>1が成立し、\xi_n=0です。

・マージン上
 t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)=1が成立し、\xi_n=0です。

・マージンの内側
 t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)<1が成立し、\xi_n>0です。
 特に誤分類時は
 t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)<0が成立し、\xi_n>1です。


f:id:olj611:20210413124050p:plain:w300


よって、\sum_{n=1}^N\xi_nをなるべく小さく保つとご分類が抑制できることが分かります。

ですので、ハードマージンの目的関数にC\sum_{n=1}^N\xi_nを加えた式になっています。

正則化係数を考察

(2)C正則化係数と呼ばれます。

Cが大きくなると誤分類しにくくなります。
なぜなら、C=\inftyのとき、{\boldsymbol\xi}が値を持つと目的関数がになるので、{\boldsymbol\xi}={\bf 0}となるためです。

Cが小さくなると、誤分類しやすくなります。
なぜなら、Cが小さくなると、{\boldsymbol\xi}が大きな値を持っても目的関数に影響を与えなくなるためです。

下図にCを変えた結果を示しました。

f:id:olj611:20210413125251p:plain:w700

双対問題

主問題(2)はハードマージン同様、二次計画問題です。

不等式制約のラグランジュ未定乗数法を用いて双対問題に置き換えます。

\begin{eqnarray}
L({\bf w},b, {\bf a},{\boldsymbol\xi},{\boldsymbol\mu})=\frac{1}{2}||{\bf w}||^2+C\sum_{n=1}^N\xi_n-\sum_{n=1}^Na_n(t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)-1+\xi_n)-\sum_{n=1}^N\mu_n\xi_n\tag{3}
\end{eqnarray}

ここで、{\bf a}=(a_1,\ldots,a_N)^\top,a_n\geq0,{\boldsymbol\mu}=(\mu_1,\ldots,\mu_n)^\top,\mu_n\geq0です。
{\bf w},b,{\boldsymbol\xi}が主変数、{\bf a},{\boldsymbol\mu}が双対変数です。

双対問題の導出

L({\bf w},b, {\bf a},{\boldsymbol\xi},{\boldsymbol\mu})を主変数について最小化し、双対変数について最大化します。

L({\bf w},b, {\bf a},{\boldsymbol\xi},{\boldsymbol\mu}){\bf w}微分して={\bf 0}とおきます。

\begin{eqnarray}
&&\frac{\partial L}{\partial {\bf w}}={\bf 0}\\
&&\Leftrightarrow -\sum_{n=1}^N\frac{\partial}{\partial{\bf w}}a_n(t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)-1+\xi_n)={\bf 0}\\
&&\Leftrightarrow{\bf w}=\sum_{n=1}^Na_n t_n{\boldsymbol\phi}({\bf x}_n)\tag{4}
\end{eqnarray}


L({\bf w},b, {\bf a},{\boldsymbol\xi},{\boldsymbol\mu})b微分して=0とおきます。

\begin{eqnarray}
&&\frac{\partial L}{\partial b}=0\\
&&\Leftrightarrow -\sum_{n=1}^N\frac{\partial}{\partial b}a_n(t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)-1+\xi_n)=0\\
&&\Leftrightarrow\sum_{n=1}^Na_n t_n=0\tag{5}
\end{eqnarray}

L({\bf w},b, {\bf a},{\boldsymbol\xi},{\boldsymbol\mu})\xi_n微分して=0とおきます。

\begin{eqnarray}
&&\frac{\partial L}{\partial \xi_n}=0\\
&&\Leftrightarrow C\sum_{n=1}^N\frac{\partial}{\partial\xi_n}\xi_n-\sum_{n=1}^N\frac{\partial}{\partial \xi_n}a_n(t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)-1+\xi_n)-C\sum_{n=1}^N\frac{\partial}{\partial\xi_n}\mu_n\xi_n=0\\
&&\Leftrightarrow C-a_n-\mu_n=0\tag{6}
\end{eqnarray}

(6)C=a_n+\mu_nと変形して、L({\bf w},b, {\bf a},{\boldsymbol\xi},{\boldsymbol\mu})に代入します。

\begin{eqnarray}
L({\bf w},b, {\bf a},{\boldsymbol\xi},{\boldsymbol\mu})&=&\frac{1}{2}||{\bf w}||^2+(a_n+\mu_n)\sum_{n=1}^N\xi_n-\sum_{n=1}^Na_n(t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)-1+\xi_n)-\sum_{n=1}^N\mu_n\xi_n\\
&=&\frac{1}{2}||{\bf w}||^2-\sum_{n=1}^Na_n(t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)-1)\tag{7}\\
\end{eqnarray}

(7)(4)を代入するのですが、ハードマージンの記事と計算が全く同じになりますので、省略します。

\begin{eqnarray}
L({\bf w},b, {\bf a},{\boldsymbol\xi},{\boldsymbol\mu})=\sum_{n=1}^Na_n-\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^Na_na_mt_nt_m{\boldsymbol\phi}({\bf x}_n)^\top{\boldsymbol\phi}({\bf x}_m)\tag{8}
\end{eqnarray}

また、(6)より、

\begin{eqnarray}
&&C-a_n=\mu_n\geq0\\
&&\Leftrightarrow a_n\leq C\tag{9}
\end{eqnarray}

となります。

よって、(8),(9)より双対問題は以下のようになります。

\newcommand{\argmax}{\mathop{\rm arg~max}\limits}\begin{eqnarray}
&&\argmax_{{\bf a}}\left(\sum_{n=1}^Na_n-\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^Na_na_mt_nt_m{\boldsymbol\phi}({\bf x}_n)^\top{\boldsymbol\phi}({\bf x}_m)\right)\\
&&{\rm s.t.}\ \ \sum_{n=1}^Na_n t_n=0,\ 0\leq a_n\leq C\tag{10}
\end{eqnarray}

この双対問題も二次計画問題になっています。

マージンと特徴ベクトルの位置関係

・マージンの外側
 マージンの外側に位置する{\bf x}_nでは、t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)-1>0が成立しているため\xi_n=0になります。
 KKT条件a_n(t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)-1+\xi_n)=0より、a_n=0が成り立つ。

・マージンの内側(上限に達したサポートベクトル)
 マージンの外側に位置する{\bf x}_nでは、t_n({\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+b)-1<0が成立しているため\xi_n>0になります。
 KKT条件\mu_n\xi_n=0より、\mu_n=0が成り立つ。
 よって、\mu_n=C-a_n=0より、a_n=C

・マージン上(上限に達していないサポートベクトル)
 0 < a_n < Cが成り立つ。

f:id:olj611:20210413154434p:plain:w600

バイアスパラメータbの導出

{\bf a}が求まると、次にbを求めることができます。
0 < a_n < Cのサポートベクトルは\xi_n=0であり、t_ny({\bf x}_n)=1であるので、

\begin{eqnarray}
t_n\left(\sum_{m\in\mathcal{S}}a_mt_m{\boldsymbol\phi}({\bf x}_m)^\top{\boldsymbol\phi}({\bf x}_n)+b\right)=1\tag{11}
\end{eqnarray}

です。
\mathcal{S}0 < a_m < Cとなるサポートベクトルの添え字からなる集合です。
(11)からbが求まりますが、
数値誤差の影響を減らすために全てのサポートベクトルに対して、
平均を求めることによってbを求めることが多いようです。

\begin{eqnarray}
b=\frac{1}{N_{\mathcal M}}\sum_{n\in{\mathcal M}}\left(t_n-\sum_{m\in\mathcal{S}}a_mt_m{\boldsymbol\phi}({\bf x}_m)^\top{\boldsymbol\phi}({\bf x}_n)\right)\tag{12}
\end{eqnarray}

{\mathcal M}0 < a_n < Cとなるサポートベクトルの添え字からなる集合です。
N_{\mathcal M}0 < a_n < Cとなるサポートベクトルの総数です。

偉人の名言

f:id:olj611:20210413160538p:plain:w300
人にできて、きみだけにできないことなんてあるもんか。
ドラえもん

参考文献

機械学習プロフェッショナルシリーズ サポートベクトルマシン
パターン認識機械学習 下巻

動画

本記事作成前に作成した動画なので、内容が異なる可能性があります。

目次へ戻る