Passive-Aggressive学習と適応正則化オンライン学習を解説して実装してみる

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。

オンライン学習の手法の一つである適応正則化を解説してPythonで実装してみます。

今回は損失を二乗ヒンジ損失として分類を試してみますが、損失関数を二乗損失とかに変えれば回帰にも使えます。
モデルは線形モデルを考えることにします。

$$
f_\theta(x) =  (\theta_1,\theta_2,\theta_3)(1,x_1,x_2)^T
$$

### PA(Passive Aggressive)学習とは

PA学習はオンライン学習の手法なので、一部のデータを使ってパラメータを徐々に更新していくという流れになります。

勾配法などでは現在のパラメータの位置で勾配を計算して、lossが小さくなる方向へ固定のステップサイズ(あるいはlearning rate)の分だけ更新する、という方法をとりますが、

PA学習はこの方向やステップサイズを適応的に決めて更新していく手法です。

勾配法ではlearning rateの大小の調整が面倒です。大きすぎれば最適値付近をいったりきたりしてしまうし、かといって小さすぎればなかなか最適値に近づいてくれません。適切なlearning rateを決めることが肝要です。

PA学習は、lossを小さくすることに加えて、パラメータの更新による変化量にペナルティを与えることで適切な分量の更新を行うようにモデルを組んだ手法です。

具体的には次のように更新式を構築します。
現在のパラメータ$\tilde \theta$が与えられたとき、次のパラメータ$\theta$を

$$
 \min_{\theta} loss(f_\theta(x),y)+ \gamma|\theta-\tilde \theta|^2
$$
の解として更新します。

$\gamma$はハイパーパラメータで、パラメータの更新による変化量のペナルティとlossの重みのバランスを司ります。

上の問題は単純に$\theta$を微分して0とすれば更新式が導出できます。

損失を二乗ヒンジ損失とした場合の更新式は以下のようになります。

$$
\theta \leftarrow \theta + \frac{y\max(0,1-y\theta^Tx)}{|x|^2+\gamma} x 
$$

データ$(x,y)$一つを受け取って更新する式です。ミニバッチにする場合は第二項はそれらの平均にします。

勾配法の更新部分と比較すると、learning rateに当たる部分がデータごとに適応的に決まることがわかります。

### 適応正則化とは

モデルの学習ではモデルの決めるパラメータの値を学習データから推定するわけですが、適応正則化ではパラメータの従う分布をなんらかの分布と仮定して、その分布のパラメータを学習します。

今回でいうと学習したいモデルのパラメータ$\theta$がガウス分布$N(\mu,\Sigma)$に従うと仮定して、このガウス分布のパラメータ$\mu,\Sigma$を学習しよう、という考え方です。

パラメータの信頼度を考慮することで異常値に強い分類を実現しよう、という気持ちが入っています。
パラメータの分布を仮定するのでベイズっぽいですが、ベイズではないです。

適応正則化はPA学習を異常値に強くなるように改良したものになっています。

なのでステップサイズが適応的に決まることなどはPA学習を受け継いでいます。

更新部分は以下の問題を解いて導出します。PA学習と同じく$\tilde\mu,\tilde\Sigma$を受け取って次のパラメータに更新します。

$$
\min loss(f_\mu(x),y) + 2 \gamma\mathrm{KL}(N(\mu,\Sigma)||N(\tilde\mu,\tilde\Sigma))+x^T\Sigma x
$$

一つ目の項はlossで、二項目はカルバックライブラーダイバージェンス(KLダイバージェンス)です。
KLダイバージェンスは分布間の距離を測る指標であり、今回は現在のパラメータの分布からの変化量を抑制する項として機能しています。

三つ目は予測の分散を表しています(これは簡単に確認できるので省略です。。。)。予測の分散が小さくなるようにパラメータを更新しよう、という部分がPA学習からの差分です。

これの最小化ですが、$\mu$と$\Sigma$それぞれ別で更新することができます。
KLダイバージェンスはガウス分布間の際は解析的に書くことができる(これも他の記事等参照してください)

PA学習のようにまた上のlossを$\mu,\Sigma$で微分して0になるとして更新式を導出できます。
二乗ヒンジ誤差を用いた場合は

$$
\mu \leftarrow \mu + \frac{y\max(0,1-\mu^T xy)}{x^T \Sigma x + \gamma}\Sigma x
$$

$$
\Sigma \leftarrow \Sigma - \frac{\Sigma xx^T\Sigma}{x^T\Sigma x+\gamma}
$$

となります。
二乗ヒンジ損失を二乗誤差に変えた場合、$\mu$の更新式を変えればいいので気になる方は導出してみるといいかもしれません。($\Sigma$の方は変わりません。)

### 実装

適応正則化の実装がこちら。

```python
class AdaptiveRegularizerHingeClassifier:
    """線形モデル + 二乗ヒンジ誤差 + 適応正則化model.
    ラベルは正例が1,負例は-1
    オンライン学習
    """

def __init__(self, gamma, seed=None):
        self.gamma = gamma
        self.seed = seed

def fit(self, X, y, epochs, batch_size):
        X = self.add_const(X)
        N = X.shape[0]
        batch_num = N // batch_size
        mu, sigma = self.init_params(X.shape[1])
        for epoch in range(epochs):
            if (epoch + 1) % 100 == 0:
                print(f"epoch {epoch+1}")
            for batch in range(batch_num):
                X_batched = X[batch * batch_size:(batch + 1) * batch_size, :]
                y_batched = y[batch * batch_size:(batch + 1) * batch_size]
                sigma = self.update_sigma(sigma, X_batched, y_batched)
                mu = self.update_mu(mu, sigma, X_batched, y_batched)
            if N % batch_size != 0:
                X_batched = X[batch_num * batch_size:, :]
                y_batched = y[batch_num * batch_size:]
                sigma = self.update_sigma(sigma, X_batched, y_batched)
                mu = self.update_mu(mu, sigma, X_batched, y_batched)
        self.coef_ = mu
        return

def init_params(self, d):
        """入力次元d"""
        np.random.seed(self.seed)
        mu = np.random.randn(d)
        A = np.random.uniform(-1, 1, (d, d))
        sigma = np.dot(A, A.T)
        return np.reshape(mu, (d, 1)), sigma

def update_mu(self, prev_mu, prev_sigma, X, y):
        update_vecs = []
        for i in range(X.shape[0]):
            x = np.reshape(X[i], (len(X[i]), 1))
            bunsi = y[i] * max(0, 1.0 - y[i] * prev_mu.T @ x)
            bunbo = x.T @ prev_sigma @ x + self.gamma
            update_vecs.append((bunsi / bunbo) * (prev_sigma @ x))
        return prev_mu + np.mean(np.array(update_vecs), axis=0)

def update_sigma(self, prev_sigma, X, y):
        update_mats = []
        for i in range(X.shape[0]):
            x = np.reshape(X[i], (len(X[i]), 1))
            bunsi = prev_sigma@x @ x.T @ prev_sigma
            bunbo = x.T @ prev_sigma @ x
            update_mats.append(bunsi / bunbo)
        return prev_sigma - np.mean(np.array(update_mats), axis=0)

def predict(self, X):
        """return 1 or -1"""
        check_is_fitted(self, 'coef_')
        scores = self.add_const(X)@ self.coef_
        return np.where(scores.flatten() > 0, 1, -1)

def evaluate(self, X, y):
        pred_y = self.predict(X)
        return accuracy_score(y, pred_y)

def add_const(self, X):
        """add const to X"""
        const = np.ones((len(X), 1))
        return np.hstack((const, X))

```

PA学習の方はこちら。updateする部分だけ異なるので差分だけ載せます。

```python

def update_theta(self, X, y, theta):
        updates = []
        for i in range(X.shape[0]):
            x = np.reshape(X[i], (len(X[i]), 1))
            delta_theta = (y[i] * max(0, 1 - y[i] * theta.T@x) /
                           (np.linalg.norm(x)**2 + self.gamma)) * x
            updates.append(delta_theta)
        return theta + np.mean(np.array(updates), axis=0)

def init_theta(self, d):
        """入力次元d"""
        np.random.seed(self.seed)
        theta = np.random.randn(d)
        return np.reshape(theta, (d, 1))
```

共分散行列の初期化の部分をどうするか悩みました。
共分散行列は半正定なので、それを満たした行列で初期化する必要があります。

今回の実装では
```python
A = np.random.uniform(-1, 1, (d, d))
sigma = np.dot(A, A.T)
```
として、-1から1の一様分布から適当に(d,d)行列をサンプルして、
$$
\Sigma = A A^T
$$
として初期化しました。

$AA^T$は正定値行列であることを利用しています。

あとは、今回初めて@演算子を使ってみました。
いままで`np.dot`を使っていたのですがこちらの方が可読性が高くて良さげです。

次に人工データを作ります。50点生成して2点だけ異常値を混ぜ込んで生成します。

生成したデータをplotした図がこちら。

### 結果

passive aggressiveと適応正則化それぞれ学習したあとの分類境界線をデータのplotとともに表示した図がこちらです。

PAモデルの方は異常値の影響を受けて境界の傾きが0に近づき一部分類に失敗しているのに対し、適応正則化は異常値に対してロバストな結果になっているように見えます。

### まとめ

今回はオンライン学習の手法であるPassive-Aggressive学習と適応正則化を解説し、線形モデルでヒンジ二乗損失を使った分類器を実装しました。

回帰とかもできるみたいなので時間があれば取り組んでみようと思います。

このブログを検索

ぐぐりらにっき

Passive-Aggressive学習と適応正則化オンライン学習を解説して実装してみる

コメント

コメントを投稿

Passive-Aggressive学習と適応正則化オンライン学習を解説して実装してみる

この記事をシェアする

コメント

コメントを投稿