PRML演習問題 7.7(基本) - 機械学習基礎理論独習

問題

SVM回帰モデルのラグランジュ関数 $(7.56)$ について考える。
$(7.56)$ の ${\bf w},b,\xi_n,\hat{\xi}_n$ に対する偏微分をそれぞれ零とおき、
その結果を代入することで双対ラグランジュ関数 $(7.61)$ が得られることを示せ。

参照

$\begin{eqnarray} y({\bf x})={\bf w}^\top{\boldsymbol\phi}({\bf x})+b\tag{7.1} \end{eqnarray}$

$\begin{eqnarray} L&=&C\sum_{n=1}^N(\xi_n+\hat{\xi}_n)+\frac{1}{2}||{\bf w}||^2-\sum_{n=1}^N(\mu_n\xi_n+\hat{\mu}_n\hat{\xi}_n)\\ &-&\sum_{n=1}^Na_n(\epsilon+\xi_n+y_n-t_n)-\sum_{n=1}^N\hat{a}_n(\epsilon+\hat{\xi}_n-y_n+t_n)\tag{7.56} \end{eqnarray}$

$\begin{eqnarray} \frac{\partial L}{\partial{\bf w}}={\bf 0}\ \Rightarrow\ {\bf w}=\sum_{n=1}^N(a_n-\hat{a}_n){\boldsymbol\phi}({\bf x}_n)\tag{7.57} \end{eqnarray}$

$\begin{eqnarray} \frac{\partial L}{\partial b}=0\ \Rightarrow\ \sum_{n=1}^N(a_n-\hat{a}_n)=0\tag{7.58} \end{eqnarray}$

$\begin{eqnarray} \frac{\partial L}{\partial \xi_n}=0\ \Rightarrow\ a_n+\mu_n=C\tag{7.59} \end{eqnarray}$

$\begin{eqnarray} \frac{\partial L}{\partial \hat{\xi}_n}=0\ \Rightarrow\ \hat{a}_n+\hat{\mu}_n=C\tag{7.60} \end{eqnarray}$

$\begin{eqnarray} \widetilde{K}({\bf a},\hat{\bf a})=&-&\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^N(a_n-\hat{a}_n)(a_m-\hat{a}_m)k({\bf x}_n,{\bf x}_m)\\ &-&\epsilon\sum_{n=1}^N(a_n+\hat{a}_n)-\sum_{n=1}^N(a_n-\hat{a}_n)t_n\tag{7.61} \end{eqnarray}$

解答

式 $(7.56)$ に式 $(7.1)$ を代入します。

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

式 $(1)$ を ${\bf w}$ を微分して、 $={\bf 0}$ とおきます。

$\begin{eqnarray} &&\frac{\partial}{\partial{\bf w}}L={\bf 0}\\ &&\Leftrightarrow\frac{1}{2}\frac{\partial}{\partial{\bf w}}||{\bf w}||^2-\sum_{n=1}^Na_n\frac{\partial}{\partial{\bf w}}{\bf w}^\top{\boldsymbol\phi}({\bf x}_n)+\sum_{n=1}^N\hat{a}_n\frac{\partial}{\partial{\bf w}}{\bf w}^\top{\boldsymbol\phi}({\bf x}_n)={\bf 0}\\ &&\Leftrightarrow{\bf w}-\sum_{n=1}^Na_n{\boldsymbol\phi}({\bf x}_n)+\sum_{n=1}^N\hat{a}_n{\boldsymbol\phi}({\bf x}_n)={\bf 0}\\ &&\Leftrightarrow{\bf w}=\sum_{n=1}^N(a_n-\hat{a}_n){\boldsymbol\phi}({\bf x}_n)\tag{2} \end{eqnarray}$

式 $(2)$ と式 $(7.57)$ は同じです。

式 $(1)$ を $b$ を微分して、 $=0$ とおきます。

$\begin{eqnarray} &&\frac{\partial}{\partial b}L=0\\ &&\Leftrightarrow-\sum_{n=1}^Na_n\frac{\partial}{\partial b}b+\sum_{n=1}^N\hat{a}_n\frac{\partial}{\partial b}b=0\\ &&\Leftrightarrow-\sum_{n=1}^Na_nb+\sum_{n=1}^N\hat{a}_nb=0\\ &&\Leftrightarrow\sum_{n=1}^N(a_n-\hat{a}_n)=0\tag{3} \end{eqnarray}$

式 $(3)$ と式 $(7.58)$ は同じです。

式 $(1)$ を $\xi_n$ を微分して、 $=0$ とおきます。

$\begin{eqnarray} &&\frac{\partial}{\partial \xi_n}L=0\\ &&\Leftrightarrow C\sum_{m=1}^N\frac{\partial}{\partial \xi_n}\xi_m-\sum_{m=1}^N\mu_m\frac{\partial}{\partial \xi_n}\xi_m-\sum_{m=1}^Na_m\frac{\partial}{\partial \xi_n}\xi_m=0\\ &&\Leftrightarrow C-\mu_n-a_n=0\\ &&\Leftrightarrow a_n+\mu_n=C\tag{4} \end{eqnarray}$

式 $(4)$ と式 $(7.59)$ は同じです。

式 $(1)$ を $\hat{\xi}_n$ を微分して、 $=0$ とおきます。

$\begin{eqnarray} &&\frac{\partial}{\partial \hat{\xi}_n}L=0\\ &&\Leftrightarrow C\sum_{m=1}^N\frac{\partial}{\partial \hat{\xi}_n}\hat{\xi}_m-\sum_{m=1}^N\hat{\mu}_m\frac{\partial}{\partial \hat{\xi}_n}\hat{\xi}_m-\sum_{m=1}^N\hat{a}_m\frac{\partial}{\partial \hat{\xi}_n}\hat{\xi}_m=0\\ &&\Leftrightarrow C-\hat{\mu}_n-\hat{a}_n=0\\ &&\Leftrightarrow \hat{a}_n+\hat{\mu}_n=C\tag{5} \end{eqnarray}$

式 $(5)$ と式 $(7.60)$ は同じです。

式 $(2),(3),(4),(5)$ を式 $(1)$ に代入します。

$\begin{eqnarray} L&=&C\sum_{n=1}^N\xi_n+C\sum_{n=1}^N\hat{\xi}_n+\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^N(a_n-\hat{a}_n)(a_m-\hat{a}_m){\boldsymbol\phi}({\bf x}_n)^\top{\boldsymbol\phi}({\bf x}_m)-\sum_{n=1}^N\mu_n\xi_n-\sum_{n=1}^N\hat{\mu}_n\hat{\xi}_n\\ &&-\epsilon\sum_{n=1}^Na_n-\sum_{n=1}^Na_n\xi_n-\sum_{n=1}^Na_n\sum_{m=1}^N(a_m-\hat{a}_m){\boldsymbol\phi}({\bf x}_m)^\top{\boldsymbol\phi}({\bf x}_n)-b\sum_{n=1}^Na_n+\sum_{n=1}^Na_nt_n\\ &&-\epsilon\sum_{n=1}^N\hat{a}_n-\sum_{n=1}^N\hat{a}_n\hat{\xi}_n+\sum_{n=1}^N\hat{a}_n\sum_{m=1}^N(a_m-\hat{a}_m){\boldsymbol\phi}({\bf x}_m)^\top{\boldsymbol\phi}({\bf x}_n)+b\sum_{n=1}^N\hat{a}_n-\sum_{n=1}^N\hat{a}_nt_n\\ &=&\left(C\sum_{n=1}^N\xi_n-\sum_{n=1}^N\mu_n\xi_n-\sum_{n=1}^Na_n\xi_n\right)+\left(C\sum_{n=1}^N\hat{\xi}_n-\sum_{n=1}^N\hat{\mu}_n\hat{\xi}_n-\sum_{n=1}^N\hat{a}_n\hat{\xi}_n\right)\\ &&+\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^N(a_n-\hat{a}_n)(a_m-\hat{a}_m){\boldsymbol\phi}({\bf x}_n)^\top{\boldsymbol\phi}({\bf x}_m)\\ &&-\sum_{n=1}^N\sum_{m=1}^Na_n(a_m-\hat{a}_m){\boldsymbol\phi}({\bf x}_m)^\top{\boldsymbol\phi}({\bf x}_n)+\sum_{n=1}^N\sum_{m=1}^N\hat{a}_n(a_m-\hat{a}_m){\boldsymbol\phi}({\bf x}_m)^\top{\boldsymbol\phi}({\bf x}_n)\\ &&-\epsilon\sum_{n=1}^N(a_n+\hat{a}_n)-b\underbrace{\sum_{n=1}^N(a_n-\hat{a}_n)}_{=0\ (7.58)}-\sum_{n=1}^N(a_n-\hat{a}_n)t_n\\ &=&\sum_{n=1}^N\underbrace{(C-\mu_n-a_n)}_{=0\ (7.59)}\xi_n+\sum_{n=1}^N\underbrace{(C-\hat{\mu}_n-\hat{a}_n)}_{=0\ (7.60)}\hat{\xi}_n\\ &&+\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^N(a_n-\hat{a}_n)(a_m-\hat{a}_m){\boldsymbol\phi}({\bf x}_n)^\top{\boldsymbol\phi}({\bf x}_m)-\sum_{n=1}^N\sum_{m=1}^N(a_n-\hat{a}_n)(a_m-\hat{a}_m){\boldsymbol\phi}({\bf x}_n)^\top{\boldsymbol\phi}({\bf x}_m)\\ &&-\epsilon\sum_{n=1}^N(a_n+\hat{a}_n)-\sum_{n=1}^N(a_n-\hat{a}_n)t_n\\ &=&-\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^N(a_n-\hat{a}_n)(a_m-\hat{a}_m){\boldsymbol\phi}({\bf x}_n)^\top{\boldsymbol\phi}({\bf x}_m)\\ &&-\epsilon\sum_{n=1}^N(a_n+\hat{a}_n)-\sum_{n=1}^N(a_n-\hat{a}_n)t_n\tag{6} \end{eqnarray}$

式 $(6)$ より、式 $(7.61)$ が示せました。