「Python Machine Learning」Ch. 2（PerceptronとAdaline）まとめ

Ch. 2は線形分類器としてPerceptronとAdalineを実装する話です。Adalineの学習の方法としてバッチ勾配降下法と確率的勾配降下法、さらにその中間としてミニバッチ勾配降下法が紹介されています。

問題

散らばっているデータを２つのクラス（$+1$と$-1$）に分類したいとする。教科書ではn次元空間で考えているが、以下ではすべて2次元空間で考える。つまり、以下のような明らかに２種類に分類できるようなデータを、ラベルがついていない状態からでもうまく分類できるような境界線を見つけたい。

Perceptron

考え方

Perceptronはベクトル$\boldsymbol{w}$を持つとし、直線

$$\boldsymbol{w}^{T} \boldsymbol{x} = w_{1} x_{1} + w_{2} x_{2} = \theta$$

を境界としてデータを分類してラベル$y$をつけることにする。簡単のため言い換えると、$w_{0} = -\theta, x_{0} = 1$と置き直して、

$$z = \boldsymbol{w}^{T} \boldsymbol{x}$$

を入力として、ステップ状の活性化関数

$$\phi(z) = 1 (if z \ge 0), \phi(z) = -1 (otherwise)$$

の出力をラベルの予測値$\hat{y} = \phi(z)$として分類することにする。学習の手続きは以下。

1. $\boldsymbol{w}$を0に初期化する
2. サンプル$\boldsymbol{w}^{(i)}$について、一つずつ出力$\hat{y}^{(i)}$を計算する。この出力値と正解のラベル$y^{(i)}$から、$\boldsymbol{w}$を更新していく

問題は具体的にどうやって$\boldsymbol{w}$を更新するかである。$w_{j} := w_{j} + \Delta w_{j}$として、以下のようにする。

$$\Delta w_{j} = \xi (y^{(i)} - \hat{y}^{(i)}) x_{j}^{(i)}$$

ここで、$\xi$は学習率である（ふつうは学習率は\etaだと思うけどなぜかはてなブログで変換されないので\xiで）。なぜこれでいいのかを考える。例えば、$(y^{(i)} , \hat{y}^{(i)}) = (1, -1)$のときは、$z$を大きくしたいはずなので、そのためには結局$w_j x_j$を大きくしたいことになる。その場合、上記の式により$\Delta w_{j} = \xi (1 - (-1)) x_{j}^{(i)}$となり、$\Delta w_{j}$は$x_{j}$と同符号になるので、$\Delta w_{j} x_{j}$が正になって$w_j x_j$が大きくなる。その他にも、いろいろな場合について同様に考えていくと上記の式でうまくいくことがわかる。ちなみに、ラベルが合っている場合は$y^{(i)} = \hat{y}^{(i)}$なので$\Delta w_{j} = 0$となり、重みベクトルは変化しない。

実装

class Perceptron:
    def __init__(self, eta = 0.01, n_iter = 10):
        self.eta = eta
        self.n_iter = n_iter
    
    def predict(self, Xi):
        net_input = np.dot(Xi, self.w_[1:]) + self.w_[0]
        return np.where(net_input >= 0, 1, -1)
    
    def fit(self, X, Y):
        self.w_ = np.zeros(1 + X.shape[1])
        self.errs = []
        
        for _ in range(self.n_iter):
            err = 0
            for Xi, Yi in zip(X, Y):
                Yi_pred = self.predict(Xi)
                if Yi_pred != Yi:
                    err += 1
                    
                update = self.eta * (Yi - Yi_pred)
                self.w_[1:] += update * Xi
                self.w_[0] += update
                
            self.errs.append(err)

# データX, Yを学習
ppn = Perceptron()
ppn.fit(X, Y)

Adaline (Adaptive linear neurons)

Perceptronには、もしデータが線形分類できないとき永遠に収束しないという問題がある。これは、原理からわかるようにひとつでも$y^{(i)} \neq \hat{y}^{(i)}$となる$i$が存在する限り重みベクトルが更新されるからである。この点を解決した別の分類器がAdalineである。

Adalineの原理や学習プロセスはほとんどPerceptronと同じである。違いは以下の２点。

1. 活性化関数として、ステップ関数ではなく入力をそのまま返す$\phi(z) = z$を用い、重みベクトルの更新には$y$と$\phi(z)$の差分を使う
2. perceptronでは、重みベクトルの更新をそれぞれのサンプルのそれぞれの成分について独立に行っていたのに対して、Adalineではすべてのサンプルの分類の良さを反映したエラー関数を計算し、まとめて更新を行う

具体的な更新のプロセスとしては、まずすべてのサンプルについて活性化関数$\phi(z^{(i)})$を計算する。その結果からさらに、すべてのサンプルの予測結果と正解を反映したエラー関数

$$J(\boldsymbol{w}) = \frac{1}{2} \sum_{i} (y^{(i)} - \phi(z^{(i)}))^{2}$$

を計算する。このエラー関数は予測の悪さを表しているから、当然小さくしたい。そのために、重みベクトルの計算を以下のように行う。

$$ \boldsymbol{w} := \boldsymbol{w} + \Delta \boldsymbol{w} \ \Delta \boldsymbol{w} = -\xi \nabla J(\boldsymbol{w}) $$

ここで、$\Delta \boldsymbol{w}$の各成分は以下のように計算できる。

$$ \Delta w_j = - \xi \frac{\partial J}{\partial w_j} = \xi \sum_{i} (y^{(i)} - \phi(z^{(i)})) x_{j}^{(i)} $$

これを見るとわかるように、Adalineの重みベクトルの更新の式はPerceptronのものと非常に似ている。違いは、$y^{(i)}$ではなく$\phi(z^{(i)})$を使っていることと、すべての$i$についてまとめて更新するところである。

実装

class AdalineGD:
    def __init__(self, eta = 0.01, n_iter = 50):
        self.eta = eta
        self.n_iter = n_iter
        
    def activation(self, X):
        return np.dot(X, self.w_[1:]) + self.w_[0]
        
    def predict(self, X):
        return np.where(self.activation(X) >= 0., 1, -1)
    
    def fit(self, X, Y):
        self.w_ = np.zeros(1 + X.shape[1])
        self.cost_ = []
        
        for i in range(self.n_iter):
            act = self.activation(X)
            errors = Y - act
            
            self.w_[1:] += self.eta * np.dot(X.T, errors)
            self.w_[0] += self.eta * np.sum(errors)
            
            cost = np.sum(errors**2)
            self.cost_.append(cost)

# 
adl = AdalineGD()
adl.fit(X, Y)

$\xi$と標準化

学習率$\xi$が大きすぎると$\boldsymbol{w}$が発散してしまうので注意。といっても、本来$\boldsymbol{w}$の更新の度合いを決めるのは$\xi$だけではなく$\xi$と$x$の積なので、$x$の大きさがわからないと$\xi$の決めようがない。そこで、$x$を

$$x_{j} = \frac{x_{j} - \mu_{j}}{s_{j}}$$

としておくと、$x$の各成分が平均0、標準偏差1に標準化されるので良い。

学習の方法

上記の、すべてのサンプルをまとめて学習に使う方法をバッチ勾配降下法と言うが、サンプル数が大きくなるとどう考えても大変なことになる。この点を解決するために１つのサンプル$i$を選んで、重みベクトルを

$$ \Delta w_j = \xi (y^{(i)} - \phi(z^{(i)})) x_{j}^{(i)} $$

のようにいちいち更新する方法を確率的勾配降下法と言う。この方法の方が一般に収束が早いことが知られている。その他のメリットとしては、１つのデータが入ってきた時に重みベクトルを更新できることからオンライン学習に使えることがある。注意点として、確率的勾配降下法を行う時は、１エポックごとにデータをランダムに並べ替えてから行う必要がある。

さらに別の方法としては、ミニバッチ勾配降下法がある。これは、バッチ勾配降下法と確率的勾配降下法の中間のような方法で、少数のデータ（たとえば50個など）で重みベクトルの更新をする方法である。バッチ勾配降下法よりも収束が早く、また確率的勾配降下法と違って計算をベクトル化できるというメリットがある。