📂機械学習

パーセプトロン収束定理

$X^{+}$, $X^{-}$が線形分離可能なトレーニングセットだとしよう。$y$を以下のラベルとする。

$$ y_{i} = \pm 1\ (\mathbf{x}_{i} \in X^{\pm}) $$

トレーニングセット全体$X = X^{+} \cup X^{-}$に$N$個のデータがあるとすると、以下の順序で入力値を代入するとする。

$$ \mathbf{x}(1), \mathbf{x}(2), \cdots \mathbf{x}(N), \mathbf{x}(1), \mathbf{x}(2), \cdots \mathbf{x}(N),\mathbf{x}(1), \mathbf{x}(2), \cdots $$

つまり、最後のデータまで学習プロセスが終わったら、初めから再開するということだ。

定理¹

予測に失敗した入力値が出たたびに、以下のようにするとしよう。

$$ \mathbf{x}_{1}, \mathbf{x}_{2}, \cdots, \mathbf{x}_{n}, \cdots $$

重みの初期値を$\mathbf{w}_{1}=\mathbf{0}$としよう。$n$回目に予測に失敗した入力データに対して、以下のように重みをアップデートするとする。

$$ \mathbf{w} _{n+1} = \mathbf{w}_{n} + y_{n}\mathbf{x}_{n} $$

すると、以下の式を満たす$n_{o}$が存在する。

$$ \mathbf{w}_{n_{o}} = \mathbf{w}_{n_{o} + 1} = \mathbf{w}_{n_{o} + 2} = \cdots $$

$$ \begin{cases} \mathbf{w}_{n_{o}}^{T}\mathbf{x} > 0 & \text{if } \mathbf{x} \in X^{+} \\ \mathbf{w}_{n_{o}}^{T}\mathbf{x} \le 0 & \text{if } \mathbf{x} \in X^{-} \end{cases} $$

説明

上記の要約を一言でまとめると、「パーセプトロンは有限回の学習で完了する」ということだ。$n_{o}$以降では重みがアップデートされないということであり、これは全ての$\mathbf{x}$に対して$y = \hat{y}$ということを意味する。

重みをアップデートする方式が単に間違ったデータを足すだけでよいという点と、有限回の回数で学習が終了することを数式的に示すことがポイントだ。

証明

入力データの予測に失敗した回数を$n$とすると、上記のように重みをアップデートする時$n$の上限があることを示す。

---

$\mathbf{x}_{n}$の予測に失敗したため、次のように重みをアップデートする。

$$ \begin{equation} \mathbf{w} _{n+1} = \mathbf{w}_{n} + y_{n}\mathbf{x}_{n} \label{eq3} \end{equation} $$ そして、$X^{+}$と$X^{-}$が分離可能であると仮定したので、次の式を満たすソリューション$\mathbf{w}_{\ast}$が存在する。

$$ \begin{cases} \mathbf{w}_{\ast}^{T}\mathbf{x} > 0 & \text{if } \mathbf{x} \in X^{+} \\ \mathbf{w}_{\ast}^{T}\mathbf{x} \le 0 & \text{if } \mathbf{x} \in X^{-} \end{cases} \quad \text{and} \quad \| \mathbf{w}_{\ast} \| = 1 $$

すると、次が成り立つ。

$$ \mathbf{w}_{\ast}^{T}\mathbf{w} _{n+1} = \mathbf{w}_{\ast}^{T}\mathbf{w}_{n} + y_{n}\mathbf{w}_{\ast}^{T}\mathbf{x}_{n} $$

そして、$\alpha>0$を次のように定義する。

$$ \alpha := \min \limits_{\mathbf{x} \in X} y \mathbf{w}_{\ast}^{T}\mathbf{x} $$

すると、次の不等式が成立する。

$$ \mathbf{w}_{\ast}^{T}\mathbf{w} _{n+1} \ge \mathbf{w}_{\ast}^{T}\mathbf{w}_{n} + \alpha $$

しかし、重みの初期値が$\mathbf{w}_{1}=\mathbf{0}$だったので、次の式が成り立つ。

$$ \begin{equation} \begin{aligned} \\ \mathbf{w}_{\ast}^{T}\mathbf{w} _{n+1} &\ge \mathbf{w}_{\ast}^{T}\mathbf{w}_{n} + \alpha \\ &\ge \mathbf{w}_{\ast}^{T}\mathbf{w}_{n-1} + 2\alpha \\ &\cdots \\ &\ge \mathbf{w}_{\ast}^{T}\mathbf{w}_{1} + n\alpha \\ &= n\alpha \end{aligned} \label{eq1} \end{equation} $$

そして、コーシー・シュワルツの不等式によって、次の式が成り立つ。

$$ \begin{equation} \| \mathbf{w}_{n+1} \|^{2} = \| \mathbf{w}_{\ast} \|^{2} \| \mathbf{w}_{n+1} \|^{2} \ge | \mathbf{w}_{\ast}^{T} \mathbf{w}_{n+1} |^{2} \label{eq2} \end{equation} $$

$\eqref{eq1}$と$\eqref{eq2}$によって、次の式が成り立つ。

$$ \begin{equation} \| \mathbf{w}_{n+1} \|^{2} \ge n^{2}\alpha^{2} \label{eq4} \end{equation} $$

再び$\eqref{eq3}$から下記の式を得る。

$$ \| \mathbf{w}_{n+1} \|^{2} = \| \mathbf{w}_{n} \| ^{2} + \| \mathbf{x} _{n} \| ^{2} + 2 y_{n}\mathbf{w}^{T}_{n}\mathbf{x}_{n} $$

しかし$y_{n}\mathbf{w}^{T}_{n} \mathbf{x}_{n} \le 0$であるため、次の不等式を得る。

$$ \| \mathbf{w}_{n+1} \|^{2} \le \| \mathbf{w}_{n} \| ^{2} + \| \mathbf{x} _{n} \| ^{2} \le \| \mathbf{w}_{n} \| ^{2} + \beta $$

この時、$\beta = \max \limits_{\mathbf{x} \in X} \| \mathbf{x} \|^{2}$である。すると、重みの初期値が$\mathbf{w}_{1}=\mathbf{0}$だったので、次の式が成り立つ。

$$ \begin{equation} \begin{aligned} \| \mathbf{w}_{n+1} \|^{2} &\le \| \mathbf{w}_{n} \| ^{2} + \beta \\ &\le \| \mathbf{w}_{n-1} \| ^{2} + 2\beta \\ &\le \| \mathbf{w}_{n-2} \| ^{2} + 3\beta \\ &\vdots \\ &\le \| \mathbf{w}_{1} \|^{2} + n\beta \\ &= n\beta \end{aligned} \label{eq5} \end{equation} $$

二つの不等式$\eqref{eq4}, \eqref{eq5}$を一緒にまとめると、次のようになる。

$$ n^{2} \alpha^{2} \le \| \mathbf{w}_{n+1} \|^{2} \le n\beta $$

$n$について整理すると、次のようになる。

$$ \begin{align*} && n^{2} \alpha^{2} &\le n\beta \\ \implies && n &\le \dfrac{\beta}{\alpha^2} \end{align*} $$

したがって、次を得る。

$$ n_{\text{max}} = \dfrac{\beta}{\alpha^{2}} $$

これは、パーセプトロンが予測に失敗する回数が多くても$\dfrac{\beta}{\alpha^{2}}$回であり、その後は全てのトレーニングデータに対して予測を成功させるという意味である。

■