PRML演習問題 6.2(標準) - 機械学習基礎理論独習

問題

この演習問題では、パーセプトロンの学習アルゴリズムの双対表現を導く。
パーセプトロンでの更新則 $(4.55)$ を用いて、訓練後の重みベクトル $\bf w$ が、ベクトル $t_n{\boldsymbol\phi}({\bf x}_n)$
(ただし $t_n\in\{-1,+1\}$ )の線形結合で表されることを示せ。
この線形結合の係数を $\alpha_n$ として、パーセプトロンの学習アルゴリズムを導き、
また、 $\alpha_n$ を用いてパーセプトロンの予測関数を示せ。
また、特徴ベクトル ${\boldsymbol\phi}({\bf x})$ は、カーネル関数 $k({\bf x},{\bf x}')={\boldsymbol\phi}({\bf x})^\top{\boldsymbol\phi}({\bf x})$ の形でのみ現れることを示せ。

参照

$\begin{eqnarray} y({\bf x})=f({\bf w}^\top{\boldsymbol\phi}({\bf x}))\tag{4.52} \end{eqnarray}$

$\begin{eqnarray} f(a)= \left\{ \begin{array}{l} +1,\ a\geq 0\\ -1,\ a<0 \end{array}\tag{4.53} \right. \end{eqnarray}$

$\begin{eqnarray} E_{\rm P}({\bf w})=-\sum_{n\in{\mathcal M}}{\bf w}^\top{\boldsymbol\phi}_nt_n\tag{4.54} \end{eqnarray}$

$\begin{eqnarray} {\bf w}^{(\tau+1)}={\bf w}^{(\tau)}-\eta\nabla E_{\rm P}({\bf w})={\bf w}^{(\tau)}+\eta{\boldsymbol\phi}_nt_n\tag{4.55} \end{eqnarray}$

解答

パラメータの初期値 ${\bf w}^{(0)}$ を $={\bf 0}$ とすると、 $(4.55)$ より、 $t_n{\boldsymbol\phi}({\bf x}_n)$ の線形結合で表せることが分かります。
この線形結合の係数を $\alpha_n$ とすると、学習後の ${\bf w}$ は以下のように表せます。

$\begin{eqnarray} {\bf w}=\sum_{n=1}^N\alpha_nt_n{\boldsymbol\phi}_n\tag{1} \end{eqnarray}$

$(1)$ を $(4.54)$ に代入します。

$\begin{eqnarray} E_{\rm P}({\bf w})&=&-\sum_{n\in{\mathcal M}}\left(\sum_{i=1}^N\alpha_it_i{\boldsymbol\phi}_i\right)^\top{\boldsymbol\phi}_nt_n\\ &=&-\sum_{n\in{\mathcal M}}\sum_{i=1}^N\alpha_it_i{\boldsymbol\phi}_i^\top{\boldsymbol\phi}_nt_n\\ &=&-\sum_{n\in{\mathcal M}}\sum_{i=1}^N\alpha_it_ik({\bf x}_i,{\bf x}_n)t_n\tag{2} \end{eqnarray}$

$(1)$ を $(4.52)$ に代入します。

$\begin{eqnarray} y({\bf x})&=&f\left(\left(\sum_{n=1}^N\alpha_nt_n{\boldsymbol\phi}_n\right)^\top{\boldsymbol\phi}({\bf x})\right)\\ &=&f\left(\sum_{n=1}^N\alpha_nt_n{\boldsymbol\phi}({\bf x}_n)^\top{\boldsymbol\phi}({\bf x})\right)\\ &=&f\left(\sum_{n=1}^N\alpha_nt_nk({\bf x}_n,{\bf x})\right)\tag{3}\\ \end{eqnarray}$

$(2),(3)$ より、特徴ベクトル ${\boldsymbol\phi}({\bf x})$ は、カーネル関数 $k({\bf x},{\bf x}')={\boldsymbol\phi}({\bf x})^\top{\boldsymbol\phi}({\bf x})$ の形でのみ現れることが示せました。

$(4.55)$ に $(1)$ を代入します。

$\begin{eqnarray} \sum_{n=1}^N\alpha_n^{(\tau+1)}t_n{\boldsymbol\phi}_n=\sum_{n=1}^N\alpha_n^{(\tau)}t_n{\boldsymbol\phi}_n+\eta{\boldsymbol\phi}_nt_n\tag{4} \end{eqnarray}$

$(4)$ より、 $\alpha_n$ の更新式は以下となります。

$\begin{eqnarray} \alpha_n^{(\tau+1)}=\alpha_n^{(\tau)}+\eta\tag{5} \end{eqnarray}$