パーセプトロン収束定理の証明とPythonでの検証　深層学習のための再履修

はじめに

今のDL（Deep Learning）の中身はブラックボックスであることは周知の事実ですが、源流のパーセプトロンは 「解が存在するならば必ずそこにたどり着ける」 ことが証明されています。これは、局所解に嵌まる可能性のあるDLとは異なります。数学的に言えば 「データが線形分離可能であれば、有限回のステップで必ず解に到達する（収束する）」 ということです。

先にパーセプトロンについて今一度復習しておきます。パーセプトロンは出力値が2値、1層のみのニューラルネットワークという理解で差し支えないでしょう。重みは以下の式によって更新されます。

$$w := w + \Delta w$$

$$\Delta w = \eta (y^{(i)} - \hat{y}^{(i)}) x^{(i)}$$

ここで $\eta$ は学習率、$y^{(i)}$ は $i$ 番目の訓練データの正解値、$\hat{y}^{(i)}$ は予測値です。
この式は、直感的には「予測が外れた分だけ修正する」と読めますが、DLにおける勾配降下法と構造は全く同じです。

一般的な勾配降下法の更新式を思い出してみましょう。損失関数を $L$ とすると、重みの更新式は以下のようになります。

$$w \leftarrow w - \eta \frac{\partial L}{\partial w}$$

ここで、連鎖律（Chain Rule）を適用すると、重み $w$ に対する勾配は次のように分解できます。

$$\frac{\partial L}{\partial w} = \frac{\partial L}{\partial u} \cdot \frac{\partial u}{\partial w}$$

パーセプトロンの入力総和 $u = w \cdot x + b$ を $w$ で偏微分すると $\frac{\partial u}{\partial w} = x$ となります。つまり、勾配は必ず入力 $x$ に比例します。

$$\frac{\partial L}{\partial w} = \delta \cdot x$$

この $\delta$（誤差信号）に相当するのが、パーセプトロンにおける $(y^{(i)} - \hat{y}^{(i)})$ の項です。つまり、パーセプトロンの学習則は、「微分不可能なステップ関数の代わりに、予測誤差をそのまま誤差信号として逆伝播させている勾配降下法」 と解釈できるのです。こう考えると、基本すぎて忘れられた数式も今のニューラルネットワークと同じ文脈で理解できます。

本記事では、このアルゴリズムが「なぜ収束するのか」を数式で証明し、それをPythonで検証します。

理論編（Novikoffの定理）

では最初に述べた「解が存在するならば必ずそこにたどり着ける」ことを証明していきましょう。

仮定として、データが線形分離可能であるとします。証明を簡潔にするため、ラベル $y$ を $\{0, 1\}$ ではなく $\{-1, 1\}$ と定義し、バイアス項は重みベクトル $w$ に含めるものとします。
すなわち、データ集合 $D$ を以下のように定義します。

$$D = \{(x^{(1)}, y^{(1)}), \cdots, (x^{(n)}, y^{(n)})\} \subset \mathbb{R}^d \times \{-1, 1\}$$

線形分離可能であるため、ある理想的な重みベクトル $w^*$ が存在し、全てのデータに対して以下が成立します。

$$y^{(i)}(w^* \cdot x^{(i)}) > 0 \quad (\forall i)$$

これは、正解ラベルが $1$ のデータ群 $D_1$ と $-1$ のデータ群 $D_2$ が、$w^*$ によって完全に分離されていることを意味します。また証明のために以下の記号を定義します。

• マージン $\gamma$ :
  理想的な決定境界と、最も近いデータ点との距離に関連する値です。ここでは $||w^*||=1$ と仮定し、以下のように置きます。

  $$\gamma = \min_{i} y^{(i)} (w^* \cdot x^{(i)})$$

• データの最大ノルム $R$:
  原点から最も遠いデータの距離です。

  $$R = \max_{i} ||x^{(i)}||$$

ここから、更新回数 $k$ の上限を導きます。なお、学習率 $\eta$ はパラメータのスケールを変えるだけで更新回数の本質には影響しないため、ここでは $\eta=1$ とします。

Step 1: 内積の下限を求める

まず、重みベクトルと理想解 $w^*$ の内積に着目します。$k$ 回目の更新で誤分類したデータを $(x^{(i)}, y^{(i)})$ とすると、更新式は $w_{k+1} = w_k + y^{(i)}x^{(i)}$ となります。この両辺に $w^*$ を内積します。

$$w_{k+1} \cdot w^* = (w_k + y^{(i)}x^{(i)}) \cdot w^*$$

展開すると、

$$w_{k+1} \cdot w^* = w_k \cdot w^* + y^{(i)}(x^{(i)} \cdot w^*)$$

ここで定義より $y^{(i)}(x^{(i)} \cdot w^*) \ge \gamma$ なので、以下の不等式が成り立ちます。

$$w_{k+1} \cdot w^* \ge w_k \cdot w^* + \gamma$$

これを繰り返すと（初期値 $w_0=0$ として）、

$$w_k \cdot w^* \ge k\gamma \quad \cdots (1)$$

これは、更新するたびに重みベクトルは正解の方向へ少なくとも $\gamma$ ずつ近づいていくことを意味します。内積はベクトルの「方向の近さ（類似度）」を表すため、コサイン類似度に通ずる考え方です。

Step 2: ノルムの上限を求める

次に重みベクトル自身の大きさ（長さ）について考えます。

$$||w_{k+1}||^2 = ||w_k + y^{(i)}x^{(i)}||^2 = ||w_k||^2 + 2y^{(i)}(w_k \cdot x^{(i)}) + ||x^{(i)}||^2$$

ここで、更新が発生するのは誤分類をしたときだけなので、$y^{(i)}(w_k \cdot x^{(i)}) \le 0$ です（正解 $y^{(i)}$ と予測値の符号が逆だからです）。
また $R = \max_{i} ||x^{(i)}||$ より $R \ge ||x^{(i)}||$ なので、

$$||w_{k+1}||^2 \le ||w_k||^2 + R^2$$

これを $k$ 回繰り返すと、

$$||w_{k}||^2 \le kR^2 \quad \cdots (2)$$

Step 3: 不等式を合体させる

コーシー・シュワルツの不等式 $(w_k \cdot w^*)^2 \le ||w_k||^2 ||w^*||^2$ を使います（ここで $||w^*||^2=1$ を仮定しています）。

(1)と(2)を代入すると、

$$(k\gamma)^2 \le (w_k \cdot w^*)^2 \le ||w_k||^2 \le kR^2$$

$$k^2\gamma^2 \le kR^2$$

$k$ は更新回数であり $k>0$ であるから、両辺を $k$ で割って整理すると、

$$k \le \frac{R^2}{\gamma^2}$$

以上より、更新回数は $\frac{R^2}{\gamma^2}$ という定数以下に収まること、すなわち、有限回のステップで必ず学習は完了することが証明できました。

実装編

実装にあたっては、単に動くコードを書くだけでなく、Pythonの機械学習ライブラリのデファクトスタンダードであるScikit-learn のAPI設計を意識しました。

1. fit と predict の分離: 学習（状態の更新）と推論（結果の出力）を明確にメソッドとして分けています。

2. 属性名の末尾に_: self.w_や self.errors_ のように、ユーザーが指定したパラメータではなく「学習によって決定された値」にはアンダースコアをつけるのが、Scikit-learnの命名規則です。

3. 再現性の担保: random_state を受け取り、内部で RandomState インスタンスを生成することで、いつ誰が実行しても同じ乱数初期値で実験できるようにしています。

以下が実装コードです。

import numpy as np

class Perceptron:
    """パーセプトロン分類器
    パラメータ    
    eta: 学習率
    n_iter: 訓練回数
    random_state: 乱数シード
    
    属性
    w_: 適合後の重み
    b_: 適合後のバイアス
    errors_: 各エポックの誤分類数
    """
    def __init__(self, eta=0.01, n_iter=50, random_state=1):
        self.eta = eta
        self.n_iter = n_iter
        self.random_state = random_state
    
    def fit(self, X, y):
        """訓練データの学習
        パラメータ numpy配列
        X: shape = [n_examples, n_features]
         n_examplesは訓練データ数, n_featuresは特徴量の個数
        y: shape = [n_examples] 
        
        戻り値:self
        """
        rgen = np.random.RandomState(self.random_state) # np.random_randomStateは乱数生成器, self.random_stateでシード値設定
        # _は学習によって得られる値を指す
        self.w_ = rgen.normal(loc=0.0, scale=0.01, size=X.shape[1]) # 平均0, 分散0.01の正規分布で重みを初期化
        self.b_ = np.float_(0.) # バイアスの初期化, NumPy型にそろえるための記法
        self.errors_ = []
        for _ in range(self.n_iter): # n_iterの数だけ学習を繰り返す
            errors = 0
            for xi, target in zip(X, y): #重みの更新
                update = self.eta * (target - self.predict(xi))
                self.w_ += update * xi
                self.b_ += update
                #深層学習のチェーンルールの式のパーセプトロン(離散型)バージョンになってる
                errors += int(update != 0.0) # 誤差を追加
            self.errors_.append(errors)
        return self
    
    def net_input(self, X):
        # 総入力を計算
        return np.dot(X, self.w_) + self.b_
    
    def predict(self, X):
        #予測を返す
        return np.where(self.net_input(X) >= 0.0, 1, -1) # where(条件, 条件を満たすなら, 満たさないなら)

Python機械学習プログラミングを参考にしました。

検証編

では、理論編で示したNovikoffの定理が実際に成り立つのか検証していきましょう。ここではマージンを求めるためにsklearnのSVMを活用します。SVMの学習で得られるcoef_という値は、次の超平面(今回の場合は直線) $w\cdot x+b=0$ との距離の公式

$$d = \frac{|w\cdot x+b|}{||w||}$$

で$x$は決定境界と最も近いデータ点とし、分子$=1$とおいたときの$||w||$の値となっています。$\gamma$は決定境界と最も近いデータ点との距離のことであるので、以下の式が成り立ちます。

$$\gamma = \frac{1}{||w||}$$

このことを活用します。検証コードは以下の通りです

# パーセプトロン収束定理の実証 (線形分離可能な場合)

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.svm import SVC


X, y = make_blobs(n_samples=100, centers=2, random_state=1, cluster_std=3.0)

y = np.where(y==0, -1, 1)
# データの最大ノルム
R = np.max(np.linalg.norm(X, axis=1))

# マージンの計算
# svmはマージンの最大化を行うため応用できる
svm = SVC(kernel='linear', C=1000) #Cを大きくしてバイアスを減らす(ハードマージン)
svm.fit(X, y)

# svmの重みノルムの逆数がマージンになる
w_norm = np.linalg.norm(svm.coef_)
gamma = 1 / w_norm

# 理論上の更新回数の上限
k_limit =(R /gamma) ** 2

print(f"R: {R:.4f}")
print(f"gamma: {gamma:.4f}")
print(f"k_limit: {k_limit:.2f}")

# パーセプトロンの学習
ppn = Perceptron(eta=1.0, n_iter=100, random_state=1)
ppn.fit(X, y)

# 実際の更新回数
k_real = sum(ppn.errors_)

print(f"k_real: {k_real}")

if (k_real < k_limit):
    print("実証成功")
else:
    print("実証失敗")

データ点は線形分離可能

結果は、理論的上限が1478.60回、実際の実行回数は15回となりました。

次に線形分離不可能な場合を考えてみましょう。以下のデータ点を作るコードで、cluster_stdすなわち分散を3.0から4.0に変化させました。

X, y = make_blobs(n_samples=100, centers=2, random_state=1, cluster_std=4.0)

これにより以下の図のようにデータ点が線形分離不可能になりました。

データ点の分散以外同じコードを実行してみます。すると理論的上限が88.79回、実際の実行回数は842回となりました。

以上の実験から、線形分離可能なデータに対してパーセプトロンは理論的上限内で収束することが確かめられました。

終わりに

パーセプトロンは確かに強力な収束定理があります。しかし現実において線形分離可能なデータというものはほとんどないと言ってよいでしょう。AI研究の冬の時代を招いたこの限界を突破するために必要だった工夫が

1. 多層化

2. 微分可能な関数の導入

すなわち現代のDLへの進化です。しかし、誤差を計算し、重みを調整するというアイデアは既に今回実装したパーセプトロンに現れています。数学的な面白さを堪能できるレベルの基礎に立ち返ることも、この現代を彩る技術と戯れるために必要なことではないでしょうか。