ハードマージンの双対問題をSMOで解く

SMOとは

SMO(逐次最小問題最適化法)はサポートベクトルマシンの訓練で生じる2次計画問題を解くためのアルゴリズムです。
1998年にマイクロソフトリサーチのJohn Plattによって発明されました。

SMO概要

以下を繰り返します。
1: ある基準にもとづきインデックス $i,j$ を選択します。
2: $a_i,a_j$ だけを動かして最適化します。
※以下で、2から先に説明します。

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,\ a_n\geq0\tag{1} \end{eqnarray}$

目的関数をインデックス $i,j$ とそれ以外に分離します。

$\begin{eqnarray} L({\bf a})&=&\sum_{n=1}^Na_n-\frac{1}{2}\left(\sum_{m=1}^Na_mt_m{\boldsymbol\phi}({\bf x}_m)^\top\right)\left(\sum_{n=1}^Na_nt_n{\boldsymbol\phi}({\bf x}_n)\right)\\ &=&\sum_{n=1}^Na_n-\frac{1}{2}\left(a_it_i{\boldsymbol\phi}({\bf x}_i)^\top+a_jt_j{\boldsymbol\phi}({\bf x}_j)^\top+\sum_{m=1,m\not=i, j}a_mt_m{\boldsymbol\phi}({\bf x}_m)^\top\right)\left(a_it_i{\boldsymbol\phi}({\bf x}_i)^\top+a_jt_j{\boldsymbol\phi}({\bf x}_j)^\top+\sum_{n=1,n\not=i, j}a_nt_n{\boldsymbol\phi}({\bf x}_n)\right)\\ &=&\sum_{n=1}^Na_n-\frac{1}{2}(a_i^2t_i^2{\boldsymbol\phi}({\bf x}_i)^\top{\boldsymbol\phi}({\bf x}_i)+a_j^2t_j^2{\boldsymbol\phi}({\bf x}_j)^\top{\boldsymbol\phi}({\bf x}_j)+2a_ia_jt_it_j{\boldsymbol\phi}({\bf x}_i)^\top{\boldsymbol\phi}({\bf x}_j)\\ &&+2\sum_{n=1,n\not=i,j}a_ia_nt_it_n{\boldsymbol\phi}({\bf x}_i)^\top{\boldsymbol\phi}({\bf x}_n)+2\sum_{n=1,n\not=i,j}a_ja_nt_jt_n{\boldsymbol\phi}({\bf x}_j)^\top{\boldsymbol\phi}({\bf x}_n)+\sum_{n=1,n\not=i,j}^N\sum_{m=1,m\not=i,j}^Na_na_mt_nt_m{\boldsymbol\phi}({\bf x}_n)^\top{\boldsymbol\phi}({\bf x}_m))\\ &=&-\frac{1}{2}a_i^2{\boldsymbol\phi}({\bf x}_i)^\top{\boldsymbol\phi}({\bf x}_i)-\frac{1}{2}a_j^2{\boldsymbol\phi}({\bf x}_j)^\top{\boldsymbol\phi}({\bf x}_j)-a_ia_jt_it_j{\boldsymbol\phi}({\bf x}_i)^\top{\boldsymbol\phi}({\bf x}_j)\\ &&+a_i\left(1-t_i{\boldsymbol\phi}({\bf x}_i)^\top\sum_{n=1,n\not=i,j}^Na_nt_n{\boldsymbol\phi}({\bf x}_n)\right)+a_j\left(1-t_j{\boldsymbol\phi}({\bf x}_j)^\top\sum_{n=1,n\not=i,j}^Na_nt_n{\boldsymbol\phi}({\bf x}_n)\right)\\ &&+\sum_{n=1,n\not=i,j}^Na_n-\frac{1}{2}\sum_{n=1,n\not=i,j}^N\sum_{m=1,n\not=i,j}^Na_na_mt_nt_m{\boldsymbol\phi}({\bf x})^\top{\boldsymbol\phi}({\bf x}_m)\tag{2} \end{eqnarray}$

$(2)$ の3行目から4行目の式変形で $t_n^2=1$ を用いました。
$(2)$ を $a_i,a_j$ の２次式とみて、次のようにおきます。

$\begin{eqnarray} Aa_i^2+Ba_j^2+Ca_ia_j+Da_i+Ea_j+F\tag{3} \end{eqnarray}$

$(2),(3)$ より、

$\begin{eqnarray} &&A=-\frac{1}{2}a_i^2{\boldsymbol\phi}({\bf x}_i)^\top{\boldsymbol\phi}({\bf x}_i)\tag{4}\\ &&B=-\frac{1}{2}a_j^2{\boldsymbol\phi}({\bf x}_j)^\top{\boldsymbol\phi}({\bf x}_j)\tag{5}\\ &&C=-a_ia_jt_it_j{\boldsymbol\phi}({\bf x}_i)^\top{\boldsymbol\phi}({\bf x}_j)\tag{6}\\ &&D=1-t_i{\boldsymbol\phi}({\bf x}_i)^\top\sum_{n=1,n\not=i,j}^Na_nt_n{\boldsymbol\phi}({\bf x}_n)\tag{7}\\ &&E=1-t_j{\boldsymbol\phi}({\bf x}_j)^\top\sum_{n=1,n\not=i,j}^Na_nt_n{\boldsymbol\phi}({\bf x}_n)\tag{8}\\ &&F=\sum_{n=1,n\not=i,j}^Na_n-\frac{1}{2}\sum_{n=1,n\not=i,j}^N\sum_{m=1,n\not=i,j}^Na_na_mt_nt_m{\boldsymbol\phi}({\bf x})^\top{\boldsymbol\phi}({\bf x}_m)\tag{9}\\ \end{eqnarray}$

となります。

制約条件 $\sum_{n=1}^Na_nt_n=0$ を分離します。

$\begin{eqnarray} &&\sum_{n=1}^Na_nt_n=0\\ &&\Leftrightarrow a_it_i+a_jt_j+\sum_{n=1,n\not=i,j}^Na_nt_n=0\\ &&\Leftrightarrow a_j=\frac{1}{t_j}\left(-a_it_i-\sum_{n=1,n\not=i,j}^Na_nt_n\right)\\ &&\Leftrightarrow a_j=t_j\left(-a_it_i-\sum_{n=1,n\not=i,j}^Na_nt_n\right)\\ &&\Leftrightarrow a_j=t_j\left(-a_it_i-G\right)\tag{10}\\ \end{eqnarray}$

$(10)$ で $G=\sum_{n=1,n\not=i,j}^Na_nt_n$ とおきました。

$(10)を(3)$ に代入して、 $a_i$ についてまとめます。

$\begin{eqnarray} L({\bf a})&=&Aa_i^2+B(t_j(-a_it_i-G))^2+Ca_i(t_j(-a_it_i-G))+Da_i^2+E(t_j(-a_it_i-G))+F\\ &=&Aa_i^2+Bt_j^2(a_i^2t_i^2+2Ga_it_i)-Ct_jt_ia_i^2+Da_i-Et_jt_ia_i+\cdots\\ &=&Aa_i^2Ba_i^2+2t_iBGa_i-t_it_jCa_i^2-t_jCGa_iDa_i-t_it_jEa_i+\cdots\\ &=&(A+B+t_it_jC)a_i^2+(2t_iBG-t_jCG+D-t_it_jE)a_i+\cdots\tag{11} \end{eqnarray}$

$(11)$ の $a_i^2$ の係数を計算します。

$\begin{eqnarray} A+B+t_it_jC&=&-\frac{1}{2}{\boldsymbol\phi}({\bf x}_i)^\top{\boldsymbol\phi}({\bf x}_i)-\frac{1}{2}{\boldsymbol\phi}({\bf x}_j)^\top{\boldsymbol\phi}({\bf x}_j)+t_i^2t_j^2{\boldsymbol\phi}({\bf x}_i)^\top{\boldsymbol\phi}({\bf x}_j)\\ &=&-\frac{1}{2}{\boldsymbol\phi}({\bf x}_i)^\top{\boldsymbol\phi}({\bf x}_i)-\frac{1}{2}{\boldsymbol\phi}({\bf x}_j)^\top{\boldsymbol\phi}({\bf x}_j)+{\boldsymbol\phi}({\bf x}_i)^\top{\boldsymbol\phi}({\bf x}_j)\\ &=&-\frac{1}{2}\left({\boldsymbol\phi}({\bf x}_i)^\top{\boldsymbol\phi}({\bf x}_i)+{\boldsymbol\phi}({\bf x}_j)^\top{\boldsymbol\phi}({\bf x}_j)-2{\boldsymbol\phi}({\bf x}_i)^\top{\boldsymbol\phi}({\bf x}_j)\right)\\ &=&-\frac{1}{2}||{\boldsymbol\phi}({\bf x}_i)-{\boldsymbol\phi}({\bf x}_j)||^2\tag{12} \end{eqnarray}$

$(11)$ の $a_i$ の係数を計算します。

$\begin{eqnarray} 2t_iBG-t_jCG+D-t_it_jE&=&2t_i\left(-\frac{1}{2}a_j^2{\boldsymbol\phi}({\bf x}_j)^\top{\boldsymbol\phi}({\bf x}_j)\right)G-t_j(-a_ia_jt_it_j{\boldsymbol\phi}({\bf x}_i)^\top{\boldsymbol\phi}({\bf x}_j))G\\ &&+\left(1-t_i{\boldsymbol\phi}({\bf x}_i)^\top\sum_{n=1,n\not=i,j}^Na_nt_n{\boldsymbol\phi}({\bf x}_n)\right)-t_it_j\left(1-t_j{\boldsymbol\phi}({\bf x}_j)^\top\sum_{n=1,n\not=i,j}^Na_nt_n{\boldsymbol\phi}({\bf x}_n)\right)\\ &=&-t_i{\boldsymbol\phi}({\bf x}_j)^\top{\boldsymbol\phi}({\bf x}_j)G+t_i{\boldsymbol\phi}({\bf x}_i)^\top{\boldsymbol\phi}({\bf x}_j)G\\ &&+1-t_i{\boldsymbol\phi}({\bf x}_i)^\top\sum_{n=1,n\not=i,j}^Na_nt_n{\boldsymbol\phi}({\bf x}_n)-t_it_j+t_i{\boldsymbol\phi}({\bf x}_j)^\top\sum_{n=1,n\not=i,j}^Na_nt_n{\boldsymbol\phi}({\bf x}_n)\\ &=&t_i({\boldsymbol\phi}({\bf x}_i)^\top-{\boldsymbol\phi}({\bf x}_j)^\top){\boldsymbol\phi}({\bf x}_j)G+1+t_it_j-t_i({\boldsymbol\phi}({\bf x}_i)^\top-{\boldsymbol\phi}({\bf x}_j)^\top)H\\ &=&1-t_it_j+t_i({\boldsymbol\phi}({\bf x}_i)^\top-{\boldsymbol\phi}({\bf x}_j)^\top)({\boldsymbol\phi}({\bf x}_j)G-H)\\ &=&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)\tag{13} \end{eqnarray}$

$(13)$ の3行目で式を一時的に見やすくするために $H=\sum_{n=1,n\not=i,j}^Na_nt_n{\boldsymbol\phi}({\bf x})$ とおきました。

$A'=A+B-t_it_jC,B'=2t_i-t_jCG+D-t_it_jE$ とおくと、 $(11)$ は以下のようになります。

$\begin{eqnarray} L({\bf a})=A'a_i^2+B'a_i+\cdots\tag{14} \end{eqnarray}$

$(14)$ を $a_i$ で微分して $=0$ とおきます。

$\begin{eqnarray} &&\frac{\partial}{\partial a_i}L=0\\ &&\Leftrightarrow2A'a_i+B'=0\\ &&\Leftrightarrow a_i=-\frac{B'}{2A'}\tag{15} \end{eqnarray}$

$(10),(15)$ より、 $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\\ &&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\tag{16} \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{17}\\ &&j=\argmax_{k\in I_+({\bf t},{\bf a})}t_k\nabla L({\bf a})_k\tag{18}\\ \end{eqnarray}$

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

$\begin{eqnarray} &&I_-({\bf t},{\bf a})=\{t|t_k=-1またはa_k>0\}\tag{19}\\ &&I_+({\bf t},{\bf a})=\{t|t_k=1またはa_k>0\}\tag{20}\\ \end{eqnarray}$

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

$\begin{eqnarray} L({\bf a})+\lambda\sum_{n=1}^Na_nt_n+{\boldsymbol\mu}^\top{\bf a}\tag{21} \end{eqnarray}$

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

$\begin{eqnarray} a_n\geq0,\mu_na_n=0,\mu_n\geq0\tag{22} \end{eqnarray}$

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

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

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

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

$a_k=0$ のとき、 $(24)$ の不等式より

$\begin{eqnarray} &&t_k=-1\Rightarrow t_k\nabla L({\bf a})_k\geq-\lambda\tag{25}\\ &&t_k=1\Rightarrow t_k\nabla L({\bf a})_k\leq-\lambda\tag{26}\\ \end{eqnarray}$

が成り立ちます。

また、 $a_k>0$ のとき、KKT条件 $\mu_ka_k=0$ より、 $\mu_k=0$ が成り立つので、 $(23)$ より

$\begin{eqnarray} t_k\nabla L({\bf a})_k=-\lambda\tag{27} \end{eqnarray}$

が成り立ちます。
$(25),(26),(27)$ をまとめると、以下のようになります。

$\begin{eqnarray} &&t_k=-1 または a_k>0\Rightarrow t_k\nabla L({\bf a})_k\geq-\lambda\tag{28}\\ &&t_k=1 または a_k>0\Rightarrow t_k\nabla L({\bf a})_k\leq-\lambda\tag{29} \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{30} \end{eqnarray}$

となります。

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

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

偉人の名言

f:id:olj611:20210413140216p:plain:w300
たどり来て、未だ山麓
 升田幸三

参考文献

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

動画

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

機械学習基礎理論独習

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

ハードマージンの双対問題をSMOで解く

SMOとは

SMO概要

2: $a_i,a_j$ の最適化

1: $i,j$ の決定方法

偉人の名言

参考文献

動画

SMOとは

SMO概要

2: の最適化

1: の決定方法

偉人の名言

参考文献

動画

2: $a_i,a_j$ の最適化

1: $i,j$ の決定方法