解の存在と学習定理

まず，解の存在条件については次の 「線形分離性」という条件が知られています。

解の存在性：線形分離性

$${\Phi}(\mbox{\boldmath$x$})= \left\{ \begin{array}{ll} 0,& ... ...& \quad \mbox{\boldmath$x$} \in {\bf X}^+ \end{array}\right.$$

なるパーセプトロン

$$z=\Phi(\mbox{\boldmath $x$})=\phi (\alpha_1 x_1 + \alpha_2 x_2 + \alpha_3 x_3- \theta)$$

が存在するための必要十分条件は $\mbox{\boldmath$R$}^3$を${\bf X}^-$と${\bf X}^+$に分離する 平面$P$が存在すること。 (線形分離性)
その平面${\bf P}$の方程式は

$${\bf P}=\{(x_1,x_2,x_3) \in \mbox{\boldmath $R$}^3 : \alpha_1 x_1+ \alpha_2 x_2+ \alpha_3 x_3- \theta=0\}$$

で定義される。

解の構成法については次の 「学習アルゴリズム」 が知られています。

学習アルゴリズム

START

$\mbox{\boldmath$\alpha$}=0$とおく。

TEST

${\bf X}^-$または${\bf X}^+$に属する $\mbox{\boldmath$x$}$を一つとる。

$\mbox{\boldmath$x$} \in {\bf X}^-$ならば $\mbox{\boldmath$x$}$に $-\mbox{\boldmath$x$}$を代入する。

$\mbox{\boldmath$\alpha$}^T \mbox{\boldmath$x$}-\theta > 0$ならば TESTへ，そうでなければ ADDへ

ADD

$\alpha$に $\mbox{\boldmath$\alpha$}+\mbox{\boldmath$x$}$を代入し， TESTへ

さらに，この学習アルゴリズムは $\alpha$の有限回の更新が行われ，解が求められることは次の定理で 示されています。

定理 2.1.1   [学習定理]
${\bf X}^-,{\bf X}^+$は有限集合とする。 問題の解 $\mbox{\boldmath$\alpha$}^*$が存在すれば（論理関数が線形分離可能ならば）上記の学習アルゴリズムは有限回で

$$\begin{eqnarray*} \mbox{\boldmath$\alpha$}^T \mbox{\boldmath$x$}-\theta &>& 0 \... ...-\theta &>& 0 \quad (\forall \mbox{\boldmath$x$} \in {\bf X}^-) \end{eqnarray*}$$

が実現される。

以上によって,構成したい論理関数が線形分離可能ならば,それを実現するパーセプトロンは,有限回の学習によって構築できます。 以下，この定理の証明を書きます。

証明

先ず，

$$L=\max \{\vert\mbox{\boldmath $x$} \vert; \mbox{\boldmath $x... ...X}^- \cup {\bf X}^+\} ,K=\vert\mbox{\boldmath $\alpha$}^*\vert$$

とおきます。 ここで，任意の $\alpha_i \quad(i = 1,2,3)$について

$$\frac {\alpha_1}{\vert\mbox{\boldmath $\alpha$}\vert} \leq 1$$

ですから

$$\frac{\mbox{\boldmath $\alpha$}^{*T}\mbox{\boldmath $\alpha$}}{\vert\mbox{\boldmath $\alpha$}\vert} \leq K$$

は常に成り立っています。
ここで $\alpha$を上記の学習強化アルゴリズムで変化する係数ベクトルとし， ADDで強化された回数を添え字$n$として $\mbox{\boldmath$\alpha$}_{n-1}$ から $\mbox{\boldmath$\alpha$}_n$に変化する場合の上式の分子を計算すると

$$\begin{eqnarray*} &&\mbox{\boldmath$\alpha$}^{*T} \mbox{\boldmath$\alpha$}_n \\ ... ...alpha$}^{*T}\mbox{\boldmath$\alpha$}_0+n \theta \\ &&= n \theta \end{eqnarray*}$$

tonarimasu となります。 次に分母を調べと

$$\begin{eqnarray*} &&\vert\mbox{\boldmath$\alpha$}_n \vert\vert\mbox{\boldmath$\a... ...h$\alpha$}_0 +n(2 \theta + L^2) \\ &&\leq n(2 \theta + L^2) \\ \end{eqnarray*}$$

です。 これから

$$\vert\mbox{\boldmath $\alpha$}_n \vert \leq \sqrt{n} \sqrt{(2 \theta + L^2)}$$

となります。これら分母，分子の評価式から

$$n < K^2 \beta ^{-2},\quad \beta = \left(\frac{\theta}{\sqrt{2\theta +L^2}} \right )$$

を得て，$n$が有限であることが示されます。$\Box$