パーセプトロンの収束定理 - 機械学習基礎理論独習

パーセプトロンの収束定理の証明

特徴空間上の学習データ ${\boldsymbol\phi}({\bf x}_n)$ は線形分離可能とします。
${\bf x}_n\in{\mathcal C}_2$ に $-1$ を乗算します。

パーセプトロンの誤り訂正の過程で正しく識別できなかった学習パターンを順に

$\begin{eqnarray} {\bf x}^{(1)},{\bf x}^{(2)},\ldots{\bf x}^{(\tau)},\ldots\tag{1} \end{eqnarray}$

とします。
ということは、 ${\bf x}^{(\tau)}$ は正しく識別できなかった $\tau$ 番目のパターンを表します。
以下にデータ数が $4$ の場合の例を示します。

学習係数は $\eta(>0)$ は任意に設定できるので、以下では簡単のため $\eta=1$ とします。
重みベクトルの初期値 ${\bf w}^{(1)}$ を任意の設定し、正しく識別できなかったパターン ${\bf x}^{(\tau)}$ が発生したとき、
パーセプトロンの学習規則に従って、重みベクトル ${\bf w}^{(\tau)}$ は次式のように ${\bf w}^{(\tau+1)}$ に修正されます。
(※既に ${\bf x}_n\in{\mathcal C}_2$ に $-1$ が乗算されていることに注意。)

$\begin{eqnarray} {\bf w}^{(\tau+1)}={\bf w}^{\tau}+{\bf x}^{(\tau)}\tag{2} \end{eqnarray}$

ここで、解となる重みベクトルの一つを $\hat{{\bf w}}$ とすると、

$\begin{eqnarray} \hat{{\bf w}}^\top{\bf x}_n>0\tag{3} \end{eqnarray}$

が成り立ち、定数 $\alpha(>0)$ を用いると

$\begin{eqnarray} \alpha\hat{{\bf w}}^\top{\bf x}_n>0\tag{4} \end{eqnarray}$

が成り立つので、 $\alpha\hat{\bf w}$ も解です。
というのも判別関数が ${\bf w}^\top{\boldsymbol\phi}({\bf x})$ でその符号で判別するためです。

以下では、繰り返しにより重みが原点と $\hat{\bf w}$ を結ぶ直線上の点 $\alpha\hat{\bf w}$ に限りなく近づくことを示します。

式 $(2)$ の両辺から $\alpha\hat{\bf w}$ を引きます。

$\begin{eqnarray} {\bf w}^{(\tau+1)}-\alpha\hat{\bf w}={\bf w}^{(\tau)}-\alpha\hat{\bf w}+{\bf x}^{(\tau)}\tag{5} \end{eqnarray}$

式 $(5)$ の両辺のノルムを取って2乗します。

$\begin{eqnarray} ||{\bf w}^{(\tau+1)}-\alpha\hat{\bf w}||^2&=&||{\bf w}^{(\tau)}-\alpha\hat{\bf w}+{\bf x}^{(\tau)}||^2\\ &=& ||{\bf w}^{(\tau)}-\alpha\hat{\bf w}||^2+2({\bf w}^{(\tau)}-\alpha\hat{\bf w})^\top{\bf x}^{(\tau)}+||{\bf x}^{(\tau)}||^2\\ &=& ||{\bf w}^{(\tau)}-\alpha\hat{\bf w}||^2+2{{\bf w}^{(\tau)}}^\top {\bf x}^{(\tau)} -2\alpha\hat{\bf w}^\top{\bf x}^{(\tau)}+||{\bf x}^{(\tau)}||^2\tag{6} \end{eqnarray}$

${\bf x}^{(\tau)}$ は正しく識別できなかったパターンであるので、

$\begin{eqnarray} {{\bf w}^{(\tau)}}^\top {\bf x}^{(\tau)}\leq 0\tag{7} \end{eqnarray}$

が成り立ちます。
よって、式 $(6),(7)$ より

$\begin{eqnarray} ||{\bf w}^{(\tau+1)}-\alpha\hat{\bf w}||^2\leq ||{\bf w}^{(\tau)}-\alpha\hat{\bf w}||^2-2\alpha\hat{\bf w}^\top{\bf x}^{(\tau)}+||{\bf x}^{(\tau)}||^2\tag{8} \end{eqnarray}$

が得られます。ここで、

$\newcommand{\argmax}{\mathop{\rm arg~max}\limits}\begin{eqnarray} &&\beta:=\max_{n=1,\ldots,N}||{\bf x}_n||\tag{9}\\ &&\gamma:=\max_{n=1,\ldots,N}\hat{\bf w}^\top{\bf x}_n\tag{10}\\ \end{eqnarray}$

とおおくと、式 $(8)$ より、

$\begin{eqnarray} ||{\bf w}^{(\tau+1)}-\alpha\hat{\bf w}||^2\leq ||{\bf w}^{(\tau)}-\alpha\hat{\bf w}||^2-2\alpha\gamma+\beta^2\tag{11} \end{eqnarray}$

ここで、 $\alpha$ を

$\begin{eqnarray} \alpha=\frac{\beta^2}{\gamma}\tag{12} \end{eqnarray}$

と設定すると、

$\begin{eqnarray} ||{\bf w}^{(\tau+1)}-\alpha\hat{\bf w}||^2&\leq& ||{\bf w}^{(\tau)}-\alpha\hat{\bf w}||^2-\beta^2\\ &\leq&||{\bf w}^{(\tau-1)}-\alpha\hat{\bf w}||^2-2\beta^2\\ &\cdots&\\ &\leq&||{\bf w}^{(1)}-\alpha\hat{\bf w}||^2-k\beta^2\tag{13} \end{eqnarray}$