y_uti のブログ

統計、機械学習、自然言語処理などに興味を持つエンジニアの技術ブログです

パーセプトロンの実装

『オンライン機械学習』を参考にしてパーセプトロンを実装し、その動作の様子を確認してみました。
www.kspub.co.jp

[2017-02-19 修正] 記事中の「学習データの線形変換」の内容について、プログラムの実装に誤りがあったので修正して実験結果を差し替えました。

データの準備

はじめに、分類の対象とするデータを作成します。今回は Iris データセットを利用することにしました。scikit-learn を利用してデータを読み込み、Pandas のデータフレームに格納します。また、アヤメの「種」を species カラムとしてデータフレームに追加しておきます。

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

from sklearn.datasets import load_iris

iris = load_iris()
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df['species'] = iris.target

作成したデータフレームは以下のような内容になっています。species は 0, 1, 2 の値を取り、それぞれ "setosa", "versicolor", "virginica" に対応します。

>>> df.head()
   sepal length (cm)  sepal width (cm)  petal length (cm)  petal width (cm)  \
0                5.1               3.5                1.4               0.2
1                4.9               3.0                1.4               0.2
2                4.7               3.2                1.3               0.2
3                4.6               3.1                1.5               0.2
4                5.0               3.6                1.4               0.2

   species
0        0
1        0
2        0
3        0
4        0

今回はパーセプトロンを用いて二値分類を試したいので、データフレームから "virginica" を除外して "setosa" と "versicolor" を分類することにします。また、パーセプトロンはオンライン学習のアルゴリズムなので、ここでデータをシャッフルしておきます*1

df = df[df['species'].isin([0, 1])]
df = df.reindex(np.random.permutation(df.index)).reset_index(drop=True)

特徴量は 4 種類すべて利用しても問題ありませんが、グラフ描画の都合上 "sepal length (cm)" と "sepal width (cm)" の 2 種類だけを利用することにします。バイアス項もまとめて取り扱えるように行列 X の第 3 列目に定数 1 を追加します。ラベル y は "setosa" を正例 (+1)、"versicolor" を負例 (-1) としました。

X = df[[0, 1]].as_matrix()
X = np.c_[X, np.ones(X.shape[0])]
y = [1 if i == 0 else -1 for i in df['species']]

n_samples, n_features = X.shape

ここまでの作業で得られたデータをグラフに描画してみます。次のようになります。

plt.scatter(X[:, 0], X[:, 1], c=np.asarray(y), cmap=plt.cm.bwr)
plt.show()

f:id:y_uti:20170218210152p:plain

パーセプトロンによる決定境界の学習

それでは、パーセプトロンを用いてデータの決定境界を学習します。教科書 3.3 節にアルゴリズムの説明があるので、そのとおりに実装します。重みベクトルの更新部分は関数に分離しました。

def update_weight(w, x, y):
    if y * w.dot(x) <= 0:
        return w + y * x
    else:
        return w

w = np.zeros(n_features)
for t in range(n_samples):
    w = update_weight(w, X[t, :], y[t])

学習によって得られた重みベクトルを用いて、学習データに対する正解率を計算します。以下の関数で、正しく分類されたデータの個数を数え上げます。

def calc_accuracy(w):
    return np.count_nonzero(y * X.dot(w) > 0)

今回の実験では、100 個中 99 個のデータを正しく分類できました。

>>> print('Accuracy = %d/%d' % (calc_accuracy(w), n_samples))
Accuracy = 99/100

学習された重みベクトルによる決定境界をプロットします。計算結果のとおり、1 個のデータを除いて正しく分類できています。

plt.scatter(X[:, 0], X[:, 1], c=np.asarray(y), cmap=plt.cm.bwr)

xmin, xmax = plt.xlim()
ymin, ymax = plt.ylim()
grid_x, grid_y = np.meshgrid(np.linspace(xmin, xmax, 100), np.linspace(ymin, ymax, 100))
grid_z = w[0] * grid_x + w[1] * grid_y + w[2]
plt.contour(grid_x, grid_y, grid_z, colors='k', levels=[0])

plt.show()

f:id:y_uti:20170218212405p:plain

パーセプトロンの学習の収束

教科書 5.2 節に書かれている「パーセプトロンの学習定理」によると、パーセプトロンは線形分離可能なデータについては有限の反復回数で収束するようです。すべてのデータを正しく分類できるまで学習を続けることで、このことを確認してみます。

今回の学習データは全体で 100 個しかないので、各反復で学習データの中からランダムに 1 個を選ぶことにします*2。以下の関数でこの処理を実現します。

from random import randint

def get_training_sample():
    i = randint(0, n_samples - 1)
    return X[i, :], y[i]

この関数を利用してパーセプトロンによる学習を行います。反復回数の上限を 100 万回に設定したうえで、全てのデータを正しく分類できるまで反復します*3。学習の過程を確認できるように、重みベクトルが更新されたときの反復回数 (t), 重みベクトル (w), 正解データ数 (accuracy) を models に保存します。

models = []
w = np.zeros(n_features)
for t in range(1000000):
    Xt, yt = get_training_sample()
    wn = update_weight(w, Xt, yt)
    if np.any(wn != w):
        w = wn
        accuracy = calc_accuracy(w)
        models.append({'t': t + 1, 'w': w, 'accuracy': accuracy})
        if accuracy == n_samples:
            break

今回の実験では、47,709 回の反復で計算が終了し、それまでの重みベクトルの更新回数は 1,306 回でした。

>>> print('Iteration count = %d' % models[-1]['t'])
Iteration count = 47709

>>> print('Update count = %d' % len(models))
Update count = 1306

このときの重みベクトルと決定境界は以下のとおりです。

>>> w
array([ -63.9,   81. ,  102. ])

f:id:y_uti:20170219072324p:plain

保存した models をグラフに描画して、パーセプトロンの学習の様子を詳細に見てみます。以下は学習中の重みベクトルによる正解数をプロットしたものです。最初のうちは重みベクトルの更新によって正解数が大きく変動しますが、反復が進むにつれて、極端に正解数が落ちることが少なくなっていくようです。

from matplotlib.font_manager import FontProperties

fp14 = FontProperties(fname=r'C:\Windows\Fonts\YuGothic.ttf', size=14)
fp11 = FontProperties(fname=r'C:\Windows\Fonts\YuGothic.ttf', size=11)

ts = [m['t'] for m in models]
accuracies = [m['accuracy'] for m in models]

plt.figure(figsize=(16, 6))
plt.plot(ts, accuracies, marker='.', markersize=3, linewidth=0.05)
plt.title(u'各反復での重みベクトルによる正解数の変化', fontproperties=fp14)
plt.xlabel(u'反復回数', fontproperties=fp11)
plt.ylabel(u'正解数', fontproperties=fp11)

plt.show()

f:id:y_uti:20170219094542p:plain

重みベクトルが変化していく様子は以下のとおりです。反復が進むにつれて、各要素の絶対値が大きくなっていく傾向があります。パーセプトロンでは学習率を 1 に固定して反復処理を行うため、重みベクトルの最小単位が学習データの精度に依存します。たとえば今回のデータでは、各特徴量の精度が 0.1 (cm) なので、重みベクトルの w0, w1 も 0.1 が最小単位になります。バイアス項については特徴行列に定数値 1 を加えたので、w2 は常に整数になります。したがって、決定境界を微調整するためにはベクトルの各要素の値を大きくすることが必要になり、グラフのような挙動を示したと考えられます*4

ts = [m['t'] for m in models]
w0 = [m['w'][0] for m in models]
w1 = [m['w'][1] for m in models]
w2 = [m['w'][2] for m in models]

plt.figure(figsize=(16, 6))
plt.plot(ts, w0, linewidth=0.5, label='w0 (sepal length)')
plt.plot(ts, w1, linewidth=0.5, label='w1 (sepal width)')
plt.plot(ts, w2, linewidth=0.5, label='w2 (bias)')
plt.title(u'各反復での重みベクトルの変化', fontproperties=fp14)
plt.xlabel(u'反復回数', fontproperties=fp11)
plt.ylabel(u'重みベクトルの各要素の値', fontproperties=fp11)
plt.legend()

plt.show()

f:id:y_uti:20170219094823p:plain

グラフの w0 と w1 が似たような形状になっていることから、決定境界の法線ベクトル*5の傾き (w1 / w0) は大きく変動していないことを読み取れます。このことを以下のグラフで確認します。なお、反復の初期段階では値が大きく変動するので、最初の 50 回の反復を除外して描画しました。

ts = [m['t'] for m in models if m['t'] >= 50]
grad = [m['w'][1] / m['w'][0] for m in models if m['t'] >= 50]

plt.figure(figsize=(16, 6))
plt.plot(ts, grad, linewidth=0.5)
plt.title(u'各反復での傾きの変化 (t < 50 を除外)', fontproperties=fp14)
plt.xlabel(u'反復回数', fontproperties=fp11)
plt.ylabel(u'傾き (w1 / w0)', fontproperties=fp11)

plt.show()

f:id:y_uti:20170219100836p:plain

学習データの線形変換

最後に、学習データを座標原点の周りに移動することで収束が速くなることを確認します。「パーセプトロンの学習定理」(教科書 5.2 節の定理 5.3) によると、半径  R の学習データがマージン  \gamma で線形分離可能なとき、パーセプトロンの更新回数の上限は  (R/\gamma)^2 になるということです。したがって、データを原点の周りに移動して半径を小さくすれば、収束が速くなると期待できます。

手軽な方法として、各特徴量の平均が 0 になるように学習データを平行移動します。バイアス項は変換されないように除外しています*6

X[:, 0:2] = X[:, 0:2] - np.mean(X[:, 0:2], axis=0)

変換されたデータを学習させたところ、たしかに元のデータよりも少ない反復回数で収束していることを確認できました。学習された重みベクトルによる決定境界も合わせて示します*7

>>> print('Iteration count = %d' % models[-1]['t'])
Iteration count = 319

>>> print('Update count = %d' % len(models))
Update count = 12

>>> w
array([-2.7,  2.3,  0. ])

f:id:y_uti:20170219160730p:plain

*1:元々の状態では、データフレームの先頭から 50 行が "setosa", 次の 50 行が "versicolor", 最後の 50 行が "virginica" と種ごとにまとめられています。

*2:つまり、同じデータを何度も繰り返し学習することになります。

*3:パーセプトロンは、データを誤分類した場合のみ重みベクトルを更新するので、すべてのデータを正しく分類できた時点で処理を終了して問題ありません。

*4:今回の実験では、バイアス項として定数値 1 を設定したのが適切ではなかったのかもしれません。教科書 3.2 節「線形分類器」によると、バイアス項は特殊なので別途最適化する方がよい場合があるということです。

*5:[2017-03-18 訂正] 本記事の公開時には「決定境界の傾き」と記載していましたが、誤りです。決定境界の直線の傾きは -(w0 / w1) で表されます。

*6:[2017-02-19 修正] 本記事の公開時のコードでは、誤って 0:1 と書いていたため、特徴量の第一次元 (sepal length) のみを移動していました。この修正にともない、これ以降の結果も公開時の内容と数値が変わっています。

*7:[2017-02-19 修正] 本記事公開時の誤った実装による実験では、反復回数 1,644 回、更新回数 190 回、重みベクトルは [-12.054, 7.8, -26] という結果でした。