機械学習基礎理論独習

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

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

ソフトマージンの双対問題をSMOで解く

サポートベクトルマシン

ハードマージンの双対問題をSMOで解くと似通った記事になりますので、違いを中心に説明します。

2: a_i,a_jの最適化

ソフトマージンの双対問題は以下でした。

\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{1} \end{eqnarray}

ハードマージンとの違いは0 < a_n < Cの制約条件を考慮することです。

a_i,a_jの更新式は以下のようになります。

\begin{eqnarray} &&\hat{a}_i=\frac{1}{||{\boldsymbol\phi}({\bf x}_i)-{\boldsymbol\phi}({\bf x}_j)||^2}\left(1-t_it_j+t_i({\boldsymbol\phi}({\bf x}_i)^\top-{\boldsymbol\phi}({\bf x}_j)^\top)\left({\boldsymbol\phi}({\bf x}_j)\sum_{n=1,n\not=i,j}^Na_nt_n-\sum_{n=1,n\not=i,j}^Na_nt_n{\boldsymbol\phi}({\bf x})\right)\right)\\ &&\hat{a}_i<0\Rightarrow \hat{a}_i=0\\ &&\hat{a}_i>C\Rightarrow \hat{a}_i=C\\ &&a_j=t_j\left(-a_it_i-\sum_{n=1,n\not=i,j}^Na_nt_n\right)\\ &&\hat{a}_j<0\Rightarrow \hat{a}_j=0\\\ &&\hat{a}_j>C\Rightarrow \hat{a}_j=C\tag{2} \end{eqnarray}

1: i,jの決定方法

先にi,jの決定方法を紹介します。

\newcommand{\argmax}{\mathop{\rm arg~max}\limits}\newcommand{\argmin}{\mathop{\rm arg~min}\limits}\begin{eqnarray} &&i=\argmin_{k\in I_-({\bf t},{\bf a})}t_k\nabla L({\bf a})_k\tag{3}\\ &&i=\argmax_{k\in I_+({\bf t},{\bf a})}t_k\nabla L({\bf a})_k\tag{4}\\ \end{eqnarray}

ただし、I_-({\bf t},{\bf a}),I_+({\bf t},{\bf a})は、以下であるとします。

\begin{eqnarray} &&I_-({\bf t},{\bf a})=\{t|(a_k>0かつt_k=1)または(a_k< 0かつt_k=-1)\}\tag{5}\\ &&I_+({\bf t},{\bf a})=\{t|(a_k>0かつt_k=-1)または(a_k< 0かつt_k=1)\}\tag{6}\\ \end{eqnarray}

制約条件0 \leq a_n\leq Cを変形します。

\begin{eqnarray} \left\{ \begin{array}{l} {\bf a}\geq{\bf 0}\\ C{\bf e}-{\bf a}\geq{\bf 0} \end{array}\tag{5} \right. \end{eqnarray}

(5)で{\bf e}=(1,\ldots,1)^\topです。

目的関数にラグランジュの未定乗数法を適用します。

\begin{eqnarray} L({\bf a})+\lambda\sum_{n=1}^Na_nt_n+{\boldsymbol\mu}^\top{\bf a}+{\boldsymbol\nu}^\top(C{\bf e}-{\bf a})\tag{6} \end{eqnarray}

KKT条件は以下のようになります。

\begin{eqnarray} &&\mu_k\geq0,a_k\geq0,\mu_ka_k=0,\\ &&\nu_k\geq0,C-a_k\geq0,\nu_k(C-a_k)=0\tag{7}\\ \end{eqnarray}

(6)を{\bf a}で偏微分して={\bf 0}とおきます。

\begin{eqnarray} &&\nabla L({\bf a})+\lambda{\bf t}+{\boldsymbol\mu}-{\boldsymbol\nu}={\bf 0}\\ &&\Leftrightarrow\nabla L({\bf a})+\lambda{\bf t}=-{\boldsymbol\mu}+{\boldsymbol\nu}\tag{8} \end{eqnarray}

(8)をk成分に着目します。

\begin{eqnarray} \nabla L({\bf a})_k+\lambda t_k=-\mu_k+\nu_k\tag{9} \end{eqnarray}

KKT条件\mu_ka_k=0よりa_k > 0\Rightarrow\mu_k=0です。
KKT条件\nu_k(C-a_k)=0よりa_k < C\Rightarrow\nu_k=0です。

よって以下が成り立ちます。

\begin{eqnarray} \nabla L({\bf a})_k+\lambda t_k=-\mu_k+\nu_k \left\{ \begin{array}{l} \geq 0 \hspace{10px} (a_k > 0)\\ \leq 0 \hspace{10px} (a_k < C) \end{array}\tag{10} \right. \end{eqnarray}

以上をまとめると、以下のようになります。

\begin{eqnarray} &&a_k > 0かつt_k=1\Rightarrow t_k\nabla L({\bf a})_k\geq-\lambda\tag{11}\\ &&a_k < Cかつt_k=-1\Rightarrow t_k\nabla L({\bf a})_k\geq-\lambda\tag{12}\\ &&a_k > 0かつt_k=-1\Rightarrow t_k\nabla L({\bf a})_k\leq-\lambda\tag{13}\\ &&a_k < Cかつt_k=1\Rightarrow t_k\nabla L({\bf a})_k\leq-\lambda\tag{14}\\ \end{eqnarray}

さらにまとめると、

\begin{eqnarray} \min_{k\in I_-({\bf t},{\bf a})}t_k\nabla L({\bf a})_k\geq\max_{k\in I_+({\bf t},{\bf a})}t_k\nabla L({\bf a})_k\tag{15} \end{eqnarray}

となります。

最適解は(15)を満たします。(15)の不等式を満たす場合、処理終了します。
(15)の不等式を満たさない場合は、(3),(4)によって、i,jを決定し、a_i,a_jを更新します。

{\bf a}が求まったら、こちらの記事よりbが求まります。

偉人の名言

f:id:olj611:20210413215841p:plain:w300
一生懸命だと知恵が出る。
中途半端だと愚痴が出る。
いい加減だと、言い訳が出る。
武田信玄

参考文献

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

動画

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

目次へ戻る