パーセプトロンアルゴリズムをPythonコードを交えて紹介

はじめに

PRML(Pattern Recognition and Machine Learning)でパーセプトロンアルゴリズム（単純パーセプトロン）について学んだ内容をまとめて、実際のデータを使って学習しました。主に4.1.7の内容です。このアルゴリズムはニューラルネットワークの分野に影響を与えましたが、現在は実用的でないです。

パーセプトロンアルゴリズム

変数一覧と概要

• 訓練データの数 $N$
• 基底関数の数 $M$
• 訓練データの説明変数 $\mathbf{X} = \left\{\mathbf{x}_1, \mathbf{x}_2, \cdots \mathbf{x}_N\right\}, \mathbf{x}_n = (x_{n, 1}, x_{n, 2}, \cdots, x_{n_D})^T$
• 訓練データの目的変数 $\mathbf{t} = \left\{t_1, t_2, \cdots t_N\right\}$
• 基底関数 $\mathbf{\phi}(\cdot) = (\phi_0(\cdot), \phi_1(\cdot), \cdots \phi_{M-1}(\cdot))^T$
• 特徴量 $\mathbf{\phi}_n = \mathbf{\phi}(\mathbf{x}_n) = (\phi_0(\mathbf{x}_n), \phi_1(\mathbf{x}_n), \cdots \phi_{M-1}(\mathbf{x}_n))^T$
• 重みパラメータ $\mathbf{w} = (w_0, w_1, \cdots, w_{M-1})^T$

今回は2値分類を行います。入力$\mathbf{x}$を離散的なクラス$C_1$又は$C_2$に正しく割り当てる問題です。$t_n = +1$がクラス$C_1$に対応し、$t_n = -1$がクラス$C_2$に対応します。

線形分離可能とは

あるデータの入力空間の次元を$D$とします。$D-1$次元の超平面の中で、片側に$C_1$のデータのみが、もう片側に$C_2$のデータのみが分布するようなものが存在する時、そのデータは線形分離可能といいます。また、そのような超平面によって未知の入力$\mathbf{x}$に対する正しいクラスを予測します。

パーセプトロンアルゴリズムの理論

パーセプトロンアルゴリズムの性質は以下の通りです。

• 全てのデータを正しく2つのクラスに分類する解（先ほど述べた超平面）を求めるアルゴリズム
• 線形分離可能ならば、有限回の計算でその超平面が求まることが保証されている
• 線形分離可能でないならば、解が求まることはない
• 3つ以上のクラスの分類には使えない

以下のような一般化線形モデルを用います。

$$\begin{aligned} y(\mathbf{x}, \mathbf{w}) = \begin{cases} +1, \quad &\mathbf{w}^T\mathbf{\phi}(\mathbf{x}) \geq 0 \\ -1, \quad &\mathbf{w}^T\mathbf{\phi}(\mathbf{x}) < 0 \end{cases} \end{aligned}$$

誤差関数は以下の通りです。

$$\begin{aligned} E(\mathbf{w}) = - \sum_{n\in W}\mathbf{w}^T\mathbf{\phi}_nt_n \end{aligned}$$

ここで、$W$は間違った分類をされたデータの集合です。
確率的勾配降下法によって最適な$\mathbf{w}$を求めます。

$$\begin{aligned} \mathbf{w}^{(\tau+1)} &= \mathbf{w}^{(\tau)} - \eta\nabla E(\mathbf{w}) \\ &= \mathbf{w}^{(\tau)} + \eta\mathbf{\phi}_nt_n \end{aligned}$$

ここで、$\tau$はこのアルゴリズムのステップ数で、$\eta$は学習率パラメータです。$y(\mathbf{x}, \mathbf{w})$の値は$\mathbf{w}$に定数をかけても変化しないので、$\eta=1$としても一般性を失いません（なので今回は$\eta=1$とします）。

重みパラメータの更新をわかりやすく

以下のチャートに重みパラメータの更新の挙動をまとめました。

画像を用いて具体的に見ていきます。青い点が$t=+1$、赤い点が$t=-1$の特徴量を、黒い矢印が重みパラメータ$\mathbf{w}$を表しています。緑色の円は、更新に使う特徴量を表しています。

• まずは、$t=+1$かつ特徴量と黒い矢印が同じ向きの場合です。この時は何もしません。
  
• 次に、$t=+1$かつ特徴量と黒い矢印が反対の向きの場合です。この時は黒い矢印に特徴量を足します。黒い矢印に自分の方を向いて欲しいわけです。
  
  
• 次は、$t=-1$かつ特徴量と黒い矢印が反対の向きの場合です。この時は何もしません。
  
• 最後は、$t=+1$かつ特徴量と黒い矢印が同じ向きの場合です。この時は黒い矢印から特徴量を引きます。黒い矢印に自分と反対の方を向いて欲しいわけです。
  
  

この状態がデータを正しく分類できた状態です。これ以降重みパラメータ$\mathbf{w}$の値が更新されることはありません。

アヤメデータセットで学習

import文

import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
import seaborn as sns

np.random.seed(28)

使用するデータセット

iris_df_vanilla = sns.load_dataset('iris')
sns.pairplot(iris_df_vanilla, hue = "species", diag_kind="kde")

3種類のアヤメのデータセットです。説明変数は4つです。オレンジ色で示されたversicolorと緑色で示されたvirginicaのデータが混ざり合っていることがわかります。なので、今回はこの2つの種類のアヤメを分類します。

# setosa, virginicam, versicolorの順に50ずつのデータ
iris_df = iris_df_vanilla[50:].sample(frac=1)

y_df = iris_df.loc[:, 'species']
y_df = y_df.replace({'versicolor': 1, 'virginica': -1})
x_vanilla_df = iris_df.loc[:, ['sepal_length', 'sepal_width', 'petal_length', 'petal_width']]
x_df = (x_vanilla_df - x_vanilla_df.mean()) / x_vanilla_df.std()

N = 50
train_x = x_df[:N].to_numpy(copy=True)
train_y = y_df[:N].to_numpy(copy=True)
test_x = x_df[N:].to_numpy(copy=True)
test_y = y_df[N:].to_numpy(copy=True)

100のデータの内、訓練データを50、テスト用データを50に分けました。versicolorがクラス$C_1(t=+1)$、virginiaがクラス$C_2(t=-1)$に対応しています。

基底関数

M = 5

def Phi_n_m(xs):
    ret = np.ones((len(xs), M))
    for n in range(len(xs)):
        for m in range(M-1):
            ret[n][m+1] = xs[n][m]
    return ret

phi_nm = Phi_n_m(train_x)
phi_test = Phi_n_m(test_x)

基底関数は、以下のようにしました。

• $\phi_0(\mathbf{x}_n) = 1$
• $\phi_1(\mathbf{x}_n) = sepal\_length$
• $\phi_2(\mathbf{x}_n) = sepal\_width$
• $\phi_3(\mathbf{x}_n) = petal\_length$
• $\phi_4(\mathbf{x}_n) = petal\_width$

今回は基底関数として線形の関数のみを選びましたが、非線形の関数を用いても問題ないです。

確率的勾配降下法

w_m = np.zeros(M)

for iter in range(1000):
    correct_flg = True
    for n in range(N):
        if np.dot(w_m, phi_nm[n]) * train_y[n] <= 0:
            correct_flg = False
            w_m = w_m + phi_nm[n] * train_y[n]
    if correct_flg:
        print(f'end_iteration, w_m | {iter+1}, {w_m}')
        break

end_iteration, w_m | 10, [ 1.          0.50993126  0.68519703 -3.27770178 -4.4165233 ]

10回目のループで全ての訓練データが正しく分類されたため、アルゴリズムが止まりました。出力されている$\mathbf{w}$が決定する超平面によって、データが2つに分けられています。

結果

error_count = 0
for i in range(len(test_y)):
    error_count += ( np.dot(w_m, phi_test[i]) * test_y[i] <= 0 )

print(error_count)

5

テストデータ50個の内、5個のデータが間違って分類されました。訓練データは全て正しく分類されていることが保証されていますが、テストデータはこのように間違って分類されることがあります。