パーセプトロン - 人工知能に関する断創録

今回は、4.1.7のパーセプトロンアルゴリズムを実装します。パーセプトロンは、2クラスの識別モデルで、識別関数は式（4.52）です。

$(4.52) \hspace{50pt} \displaystyle y(\bf{x}) = f(\bf{w}^T \phi(\bf{x}))$
$(4.53) \hspace{50pt} \displaystyle f(a) = \{ +1 \hspace{10pt} \mathrm{if} \hspace{5pt} a \geq 0 \hspace{10pt} -1 \hspace{10pt} \mathrm{if} \hspace{5pt} a < 0 \}$

パーセプトロンは、下の条件を満たすような重みベクトルwを学習します。教師信号は、クラス1のとき教師信号+1、クラス2のとき-1（0じゃない）なので注意。

$\bf{w}^T \phi(\bf{x_n}) > 0 \hspace{50pt} \bf{x_n} \in C_1$
$\bf{w}^T \phi(\bf{x_n}) < 0 \hspace{50pt} \bf{x_n} \in C_2$

上の条件をまとめるとxnが正しく分類されているときは、

$\bf{w}^T \phi(\bf{x_n}) t_n > 0$

を満たします。この条件はあとでプログラム中で使います。パーセプトロンは、正しく分類されているパターンに対してはペナルティ0を割り当て、誤分類されたパターンにペナルティ

$-\bf{w}^T \phi(\bf{x_n}) t_n$

を割り当てます。上の式の値はxnが誤分類されたデータの場合、必ず正になるので注意。なのでパーセプトロンの誤差関数（パーセプトロン基準）は、

$(4.54) \hspace{50pt} \displaystyle E_p(\bf{w}) = - \sum_{n \in M} \bf{w}^T \phi(\bf{x_n}) t_n$

で与えられます。ここで、Mは誤分類されたパターンの集合です。この誤差関数は誤分類のパターンが多いほど値が大きくなるので誤差関数を最小化するようなwを求めたいってことですね。誤差関数の最小化には確率的最急降下法というのを用いて重みベクトルを式（4.55）で逐次的に更新します

$(4.55) \hspace{50pt} \displaystyle \bf{w}^{\tau+1} = \bf{w}^{\tau} - \eta \nabla E_p(\bf{w}) = \bf{w}^{\tau} + \eta \phi(\bf{x_n}) t_n$

ここで、ηは学習率パラメータで、τはステップ数を表します。では、プログラムを書いてみます。収束判定ですが、今回は完全に線形分離可能なデータなのですべてのデータが正しく分類できたら終了としています。誤差関数の値がある小さな値を下回ったら終了でもいいかもしれないです。また、簡単のため

$\phi(\bf{x}) = \bf{x}$

としています。別の基底関数を使うとどういう影響があるのか興味あります。

#coding:utf-8

# パーセプトロン
# 確率分布からデータを生成

import numpy as np
from pylab import *

N = 100
ETA = 0.1

if __name__ == "__main__":
    # 訓練データを作成
    cls1 = []
    cls2 = []
    t = []
    
    # データは正規分布に従って生成
    mean1 = [-2, 2]    # クラス1の平均
    mean2 = [2, -2]    # クラス2の平均
    cov = [[1.0, 0.0], [0.0, 1.0]]  # 共分散行列（全クラス共通）
    
    # データ作成
    cls1.extend(np.random.multivariate_normal(mean1, cov, N/2))
    cls2.extend(np.random.multivariate_normal(mean2, cov, N/2))
    
    # 教師データ
    for i in range(N/2):
        t.append(+1)  # クラス1
    for i in range(N/2):
        t.append(-1)  # クラス2

    # 訓練データを描画
    # クラス1
    x1, x2 = np.transpose(np.array(cls1))
    plot(x1, x2, 'bo')
    
    # クラス2
    x1, x2 = np.transpose(np.array(cls2))
    plot(x1, x2, 'ro')
    
    # クラス1とクラス2のデータをマージ
    x1, x2 = np.array(cls1+cls2).transpose()
    
    # 確率的最急降下法でパラメータwを更新
    w = array([1.0, 1.0, 1.0])  # 適当な初期値
    
    turn = 0
    correct = 0  # 分類が正解したデータ数
    while correct < N:  # 全部のデータが正しく分類できるまで続ける
        correct = 0
        for i in range(N):  # 全データについて検討
            if np.dot(w, [1, x1[i], x2[i]]) * t[i] > 0:  # 分類が正しいときは何もしない
                correct += 1
            else:  # 分類が間違っているときは重みを調整
                w += ETA * array([1, x1[i], x2[i]]) * t[i]
        turn += 1
        print turn, w
    
    # 決定境界を描画
    x = linspace(-6.0, 6.0, 1000)
    y = -w[1]/w[2] * x - w[0]/w[2]
    plot(x, y, 'g-')
    
    xlim(-6, 6)
    ylim(-6, 6)
    show()

結果は、

f:id:aidiary:20100429101250p:plain

となります。もう1つ異なるデータ生成法で試してみます。今度は、あらかじめ正解の分類境界を決めてからデータを生成しています。

#coding:utf-8

# パーセプトロン
# データの生成を正解パラメータから作成（図4.7に近い）

import numpy as np
from pylab import *

N = 100
ETA = 0.1

if __name__ == "__main__":
    # 正解パラメータから訓練データを作成
    true_w = array([-0.3, 1.3, -2.0])  # 正解パラメータ w
    x1 = -1 + np.random.random_sample(N) * 2  # (-1,+1)の乱数をN個
    x2 = -1 + np.random.random_sample(N) * 2  # (-1,+1)の乱数をN個
    t = (true_w[0] + x1*true_w[1] + x2*true_w[2] >= 0) * 2 - 1  # ラベル
    
    # 訓練データを描画
    for i in range(N):
        if t[i] == 1:
            plot([x1[i]], [x2[i]], 'ro')
        elif t[i] == -1:
            plot([x1[i]], [x2[i]], 'bo')
    
    # 確率的最急降下法でパラメータwを更新
    w = array([1.0, 1.0, 1.0])  # 適当な初期値
    
    turn = 0
    correct = 0  # 分類が正解したデータ数
    while correct < N:  # 全部のデータが正しく分類できるまで続ける
        correct = 0
        for i in range(N):  # 全データについて検討
            if np.dot(w, [1, x1[i], x2[i]]) * t[i] > 0:  # 分類が正しいときは何もしない
                correct += 1
            else:  # 分類が間違っているときは重みを調整
                w += ETA * array([1, x1[i], x2[i]]) * t[i]
        turn += 1
        print turn, w
    
    # 決定境界を描画
    x = linspace(-1.0, 1.0, 1000)
    y = -w[1]/w[2] * x - w[0]/w[2]
    plot(x, y, 'g-')
    
    # 正解の決定境界を描画
    y = -true_w[1]/true_w[2] * x - true_w[0]/true_w[2]
    plot(x, y, 'r--')
    
    xlim(-1.0, 1.0)
    ylim(-1.0, 1.0)
    show()

結果は、

f:id:aidiary:20100429101251p:plain

となります。赤い点線が正解の分類境界、緑がパーセプトロンから求めた分類境界です。正解とは微妙に違いますが、パーセプトロンでも正しく分離できています。基本的にデータを正しく分類できる分類境界はたくさんあるので正解と一致しないのは仕方ないですね。

パーセプトロンの特徴は、データが入って重みベクトルwを更新したらデータ自体は捨ててしまってよいことにあります。こういうアルゴリズムはオンライン学習または逐次学習と呼ばれていて、パーセプトロンはそのもっとも基本的なアルゴリズムです。朱鷺の杜によると、オンライン学習の長所として、

全てのデータを一時的に蓄積しなくて良いので，少ないメモリで大規模なデータを扱える
データが増加したときに，増加した分だけ学習し直せば良いので，全部計算し直す一括学習より計算は少ない

また、短所として

実用的には，学習の早さと，正しい解への収束性のトレードオフがあり，パラメータの更新の係数の設定はなかなか難しい．

とあります。パーセプトロンには、パーセプトロン収束定理というのがあって学習データが線形分離可能ならば必ず有限回の繰り返しで厳密解に収束することが保証されています（尊敬するミンスキー教授が証明しました）。ただ、実用的には、分離できない問題だったのか単に収束が遅いだけなのか収束するまで分からないってのが欠点のようです。

まあ、上のサンプルのように2次元のグラフに描ければともかく、文書分類などの応用ではもっと高次元なデータなので試す前に線形分離可能かどうかなんてわからないんでしょうね・・・高次元空間ならまず問題なく線形分離できそうですけど。

ちなみにいじわるしてパーセプトロンに線形分離不可能なデータを渡すと収束判定条件がいつまでたっても満たせず無限ループします。