機械学習基礎理論独習

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

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

ソフトマージンの双対問題を最急降下法で解く

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

\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}

制約条件 \sum_{n=1}^Na_n t_n=0のみに着目して、目的関数にラグランジュの未定乗数法を適用します。

\begin{eqnarray}
\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)+\lambda\sum_{n=1}^Na_nt_n\tag{2}
\end{eqnarray}

(2)a_i微分します。

\begin{eqnarray}
&&\sum_{n=1}^N\frac{\partial}{\partial a_i}a_n-\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^N\frac{\partial}{\partial a_i}a_na_mt_nt_m{\boldsymbol\phi}({\bf x}_n)^\top{\boldsymbol\phi}({\bf x}_m)+\lambda\sum_{n=1}^N\frac{\partial}{\partial a_i}a_nt_n\\
&=&1+\lambda t_i-t_i\sum_{n=1}^Na_nt_n{\boldsymbol\phi}({\bf x}_i)^\top{\boldsymbol\phi}({\bf x}_n)\tag{3}
\end{eqnarray}

(2)\lambda微分します。

\begin{eqnarray}
\frac{\partial}{\partial \lambda}\lambda\sum_{n=1}^Na_nt_n=\sum_{n=1}^Na_nt_n\tag{4}
\end{eqnarray}

アルゴリズム

1: {\bf a}^{(0)},\lambda^{(0)}を初期化します。t\leftarrow 0と設定します。\epsilonを設定します。

2: すべてのiに対して次の式でa_iを更新します。

\begin{eqnarray}
a_i^{(t+1)}\leftarrow a_i^{(t)}+\epsilon\left(1+\lambda^{(t)} t_i-t_i\sum_{n=1}^Na_n^{(t)}t_n{\boldsymbol\phi}({\bf x}_i)^\top{\boldsymbol\phi}({\bf x}_n)\right)\tag{5}
\end{eqnarray}

3: すべてのa_iに対して、もしa_i^{(t+1)}<0ならばa_i^{(t+1)}\leftarrow 0a_i^{(t+1)} > Cならばa_i^{(t+1)}\leftarrow Cとします。

4: 次の式で\lambda^{(t+1)}を更新します。

\begin{eqnarray}
\lambda^{(t+1)}\leftarrow\lambda^{(t)}-\epsilon\sum_{n=1}^Na_n^{(t+1)}t_n\tag{6}
\end{eqnarray}

5: 収束していたら終了し、そうでないならt\leftarrow t+1として2に戻る。

偉人の名言

f:id:olj611:20210413225620p:plain:w300
簡単すぎる人生に、生きる価値などない。
ソクラテス

参考文献

入門 機械学習パターン認識

動画

未作成

目次へ戻る