はじめに

こんにちは、supercellです。ここでは、自分が学習した機械学習の知識をアウトプットして行こうと思います。
そのため、間違っていることも多々あると思いますので、その際は教えてくれると助かります。
※ここで紹介するコードはすべて以下のリンクから参照することができます。

python-machine-learning-book-2nd-edition

目次

1．パーセプトロン
2．ADALINE
3．確率的勾配降下法

1.パーセプトロン

パーセプトロンは、ニューロンの働きをもととしたアルゴリズムです。2つのクラスを１、－１として、それらを分類する決定関数 $\phi(z)$を求めることが目的です。$z$は入力 $\mathbf{x}$ 、重み $\mathbf{w}$ の行列積として表されます。
つまり、

\mathbf{w} = 
\begin{pmatrix}
w_1\\
\vdots\\
w_n
\end{pmatrix},
\mathbf{x} = 
\begin{pmatrix}
x_1\\
\vdots\\
x_n
\end{pmatrix}

として、

z = 
\mathbf{w^Tx} =
\sum_{i=1}^{n}x_i\omega_i

とあらわされます。
そして、決定関数 $\phi(z)$ は総入力$z$がしきい値$\theta$をこえたら1、こえなかったら―1を返します。

\phi(z) = \left\{
\begin{array}{ll}
1 & (z \geq \theta)\\
－1 & (z \lt \theta)
\end{array}
\right.

このように、パーセプトロンのアルゴリズムでは、$\phi(z)$が単位ステップ関数となっています。
式を簡単にするために、$\theta=-w_0$、$x_0=1$とおきます。すると、$\phi(z),z$は次のように表されます。

\phi(z) = \left\{
\begin{array}{ll}
1 & (z \geq 0)\\
-1 & (z \lt 0)
\end{array}
\right.\\

z = x_0w_0 + \cdots + x_nw_n

パーセプトロンでは、決定関数$\phi(z)$を最適化するために重みを更新します。各重みの更新は次の式で表されます。

\omega_j = \omega_j + \eta(y^{(i)} - \hat{y}^{ (i)})x_j^{(i)}\tag{1}

ここで、$\eta$は学習率、$y^{(i)}$は$i$番目の真のクラスラベル、$\hat{y}^{ (i)}$は予測したクラスラベルです。
重みは同時に更新されるためにすべての重みが更新されるまで$\hat{y}^{(i)}$は再計算されないことに注意です。

では、Pythonでパーセプトロンのモデルを実装していきます。

import numpy as np


class Perceptron(object):
    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

etaを学習率、n_iterを訓練回数、random_stateを重みを初期化するための乱数シードとします。

    def fit(self, X, y):
        rgen = np.random.RandomState(self.random_state)
        self.w_ = rgen.normal(loc=0.0, scale=0.01, size=1 + X.shape[1])
        self.errors_ = []

        for _ in range(self.n_iter):
            errors = 0
            for xi, target in zip(X, y):
                update = self.eta * (target - self.predict(xi))
                self.w_[1:] += update * xi
                self.w_[0] += update
                errors += int(update != 0.0)
            self.errors_.append(errors)
        return self

fitメソッドでは、トレーニングモデルを適合させます。まず、重みを初期化してw_に収納して、誤差を収納するリストerrors_を作成します。errors_はモデルが収束するかどうかを確認するために用います。
次に、重みを更新していきます。(1)式にしたがって計算して、その後、誤差をerrors_へ収納します。

    def net_input(self, X):
        """総入力を計算"""
        return np.dot(X, self.w_[1:]) + self.w_[0]

    def predict(self, X):
        """1ステップ後のクラスラベルを返す"""
        return np.where(self.net_input(X) >= 0.0, 1, -1)

net_inputメソッドは総入力$z$の計算、predictメソッドは予測ラベルを計算しています。

以上がパーセプトロンの実装となります。

2.ADALINE（ADAptive LInear NEuron)

ADALINEはパーセプトロンのモデルを少し改良したアルゴリズムです。$\phi(z)$が単位ステップ関数ではなく、線形活性化関数となり、次の式で表されます。

\phi(z) = z

そのため、誤差の計算では、真のクラスラベルと$z$を比較します。

教師あり学習では、目的関数が設定されて、それを最小化する場合、コスト関数と呼ばれます。
ADALINEのコスト関数は、誤差平方和として定義されて、次の式で表されます。

\mathbf{J}(\mathbf{w}) =  \frac{1}{2}\sum(y^{(i)}-\phi(z^{(i)}))^2

パーセプトロンとは異なり、$\phi(z)$が連続値であるため、コスト関数を微分可能となっています。また、凸関数であることから、勾配降下法を用いることができます。

勾配降下法による重み$w_j$の更新は以下の式で表されます。

\begin{align}
w_j &= w_j - \eta\nabla\mathbf{J}(\mathbf{w})\\
&=w_j - \eta\sum_{i}^{n}(y^{(i)}-\phi(z^{(i)}))x_j^{(i)}
\end{align}

この方法では、各重みの更新で全入力が考慮されています。

では、PythonでADALINEを実装します。
パーセプトロンのモデルのfitメソッド、predictメソッドを改良し、activationメソッドを追加します。

  def fit(self, X, y):
    rgen = np.random.RandomState(self.random_state)
    self.w_ = rgen.normal(loc=0.0, scale=0.01, size=1 + X.shape[1])
    self.cost_ = []

    for i in range(self.n_iter):
      net_input = self.net_input(X)
      output = self.activation(net_input)
      errors = (y - output)
      self.w_[1:] += self.eta * X.T.dot(errors)
      self.w_[0] += self.eta * errors.sum()
      cost = (errors**2).sum() / 2.0
      self.cost_.append(cost)
    return self

インデックス1～mの重みの更新では、行列積を計算しています。その後、誤差をcost_へ収納しています。

  def net_input(self, X):
    #総入力を計算
    return np.dot(X, self.w_[1:]) + self.w_[0]

  def activation(self, X):
    #活性化関数の出力
    return X

  def predict(self, X):
    return np.where(self,activation(self.net_inuput(X)) >= 0.0, 1, -1)

activationメソッドを加えています。

以上がADALINEの実装となります。

3.確率的勾配降下法(stochastic gradient descent)

ADALINEでは、重みの更新の際にすべての入力に対して計算するため、時間がかかります。そのため、大規模なデータを扱うには向いていません。しかし、確率的勾配降下法は、入力ごとに重みを随時更新していきます。それによって、浅い極小値を抜け出しやすくなっています。しかし、トレーニングが循環する恐れがあるため、トレーニングデータをシャッフルすることが必要となります。

\eta(y^{(i)}-\phi(z^{(i)}))x^{(i)}

では、Pythonで確率的勾配法を実装していきます。
ADALINEですでに勾配降下法が実装されているため、少し改良するだけでよいです。

from numpy.random import seed

class AdalineSGD(object):

     def __init__(self, eta=0.01, n_iter=10, shuffle=True, random_state=None):
        self.eta = eta
        self.n_iter = n_iter
        self.w_initialized = False
        self.shuffle = shuffle
        self.random_state = random_state

shuffleはブール値で、Trueの時にトレーニングデータをシャッフルします。w_initializedについては、後程説明します。

"""トレーニングデータに適合"""
    def fit(self, X, y):
        self._initialize_weights(X.shape[1])
        self.cost_ = []
        for i in range(self.n_iter):
            if self.shuffle:
                X, y = self._shuffle(X, y)
            cost = []
            for xi, target in zip(X, y):
                cost.append(self._update_weights(xi, target))
            avg_cost = sum(cost) / len(y)
            self.cost_.append(avg_cost)
        return self

     def partial_fit(self, X, y):
        """重みを再初期化することなくトレーニングデータに適合"""
        if not self.w_initialized:
            self._initialize_weights(X.shape[1])
        if y.ravel().shape[0] > 1:
            for xi, target in zip(X, y):
                self._update_weights(xi, target)
        else:
            self._update_weights(X, y)
        return self

    def _shuffle(self, X, y):
        """データをシャッフル"""
        r = self.rgen.permutation(len(y))
        return X[r], y[r]

    def _initialize_weights(self, m):
        """重みを初期化"""
        self.rgen = np.random.RandomState(self.random_state)
        self.w_ = self.rgen.normal(loc=0.0, scale=0.01, size=1 + m)
        self.w_initialized = True

    def _update_weights(self, xi, target):
        """重みを更新"""
        output = self.activation(self.net_input(xi))
        error = (target - output)
        self.w_[1:] += self.eta * xi.dot(error)
        self.w_[0] += self.eta * error
        cost = 0.5 * error**2
        return cost

    def net_input(self, X):
        """総入力を計算"""
        return np.dot(X, self.w_[1:]) + self.w_[0]

    def activation(self, X):
        """活性化関数を出力"""
        return X

    def predict(self, X):
        """1ステップごとにクラスラベルを返す"""
        return np.where(self.activation(self.net_input(X)) >= 0.0, 1, -1)

_shuffleメソッドは、numpyのpermutation関数を用いて0～99までの整数の順列を作成して、インデックスとして利用しています。
_initialize_weightsメソッドは重みを初期化して、w_initializedの値をTrueにすることで重みを再初期化することがないようにしています。
_update_weightsメソッドでは、ADALINEの学習規則に従った後、誤差を返しています。
partial_fitメソッドは、目的変数$y$の要素数によって更新方法を変えています。要素数が2以上の場合は各入力の特徴量xiとyで重みを更新します。要素数が1の場合は、すべての特徴量Xとyで重みを更新しています。

以上が確率的勾配降下法の実装となります。

おわりに

初めてのqiita投稿でしたが、非常に勉強になりました。アウトプットのおかげで、自分のわかっているところとわからないところが明瞭になり、情報の整理をおこなうことができました。現在の自分の課題として、確率的勾配降下法がまだ完全にはわかっていないところがあります。その課題を克服できるよう頑張りたいと思います。

参考文献

Python機械学習プログラミング