About connecting the dots.

data science related trivial things

実装して理解するオンライン学習器(1) - PassiveAggresive

一言でいうと,最近流行のオンライン学習器を,アルゴリズムを理解しながら実装して動かして挙動を眺めてみようというシリーズです.例によって飽きたらいつのまにかフェードアウトしますが,気長にやっていこうと思っています.だいたいいつもRばっかり使ってますが,ちょっと込み入った処理を書こうとするとRだと辛いので今回はPythonです.

元ネタは以下の論文になります.レビューがコンパクトにまとまっていてわかりやすいです.

Jialei Wang, Peilin Zhao, and Steven C. Hoi. Exact soft confidence-weighted learning. In Proc. of ICML 2012, pages 121–128, 2012.

オンライン学習器

普通の機械学習は,訓練データをモデルに食わせてパラメタを学習します.学習済みのモデルは,もう一度モデル組み直しをしない限り変化しません.これに対してオンライン学習器は,毎試行毎に得られたサンプルとその判定結果を用いてモデルを更新します.そのため環境の変化に追従することができるという特徴があります.

PassiveAggressive

Gmailの優先トレイで使っているということでも有名なこのアルゴリズム,基本的には単なる線形識別器です.というより,だいたいのオンライン学習器は線形で,非線形のモデルはあまりみかけません.正確な理由は私自身もよくわかってないですが,オンライン学習器の場合,逐次学習のため高速処理が求められがちというのと,環境変化に適応してパラメタが変化するという意味で,無理やり非線形モデルにする必然性がそんなに高くない,といったあたりが理由なのかなと思っています*1

モデル

数式的には,割とシンプルで以下のとおりです.Xを素性ベクトル,yを識別変数(今回の例だと,1または-1の2値になります).そしてW_tが時刻tにおける重みベクトルです.

W_{t+1}=W_t+\eta_t y_t X_t \\
\eta_t=\frac{l(W_t; (X_t,y_t))}{\| X_t \|^2} \\
 l(W_t; (X_t,y_t))=\left\{\begin{array}{l} if y_t(W \cdot X_t) \geq 1: \ \ \  0 \\ otherwise: \ \ \ 1-y_t(W \cdot Xt)\end{array}\right.

式をすべて並べてみるとちょっとごちゃっとしてしまいますが,基本的には一番上の式にあるように,時刻tの重みベクトルW_t\eta_tを用いて学習して,次の重みを決定しているだけです.線形識別器ですので,この重みベクトルが学習できればモデルの学習が完了するというわけです.

\eta_tの中身をみると,第2式のようになっています.分母の\| X_t \|^2は単なる正規化項なので,実際は分子だけをみてあげれば十分です.この分子は第3式にあるように,正解だったら何もせず,間違いのときは当該サンプルを正解にするように識別直線を移動する,という損失関数です.つまり,PAは基本的に線形分離可能なデータを想定したモデルだといえます*2

ソフトマージンの導入による拡張

とはいえ,完璧に線形分離可能なデータなんて,実際にはほとんど存在しないものなので,実用上はもう少し柔軟な仕組みにする必要があります.このPAも,SVMみたいな形でソフトマージンを用いた拡張を行うことができます.定数Cの与え方によって,以下の2種類のモデルがあります.

\eta_t^{PA-I} = \rm{min} \{C, \frac{l(W_t; (X_t,y_t))}{\| X_t \|^2} \} \\
\eta_t^{PA-I\hspace{-.1em}I} = \frac{l(W_t; (X_t,y_t))}{\| X_t \|^2+\frac{1}{2C}}

どちらもCの与え方が違うだけで,しようとしていることは同じです.このあたりの詳しい説明は,echizen_tmさんの説明がわかりやすいので,そちらを参照いただければと思います.また数式的な部分をきちんと追うのであれば,jetbeadさんのまとめがわかりやすいです*3

実装

さて,ようやく実装に移ります.といっても,モデル式自体は非常にシンプルで,全部で27行しかありません.

#!/usr/bin/env python
#-*-coding:utf-8-*-

import numpy as np

class PassiveAggressive:
    def __init__(self, feat_dim):
        self.t = 0
        self.w = np.ones(feat_dim)

    def _get_eta(self, l, feats):
        return l/np.dot(feats, feats)

    def train(self, y_vec, feats_vec):
        for i in range(len(y_vec)):
            self.update(y_vec[i], feats_vec[i,])

    def predict(self, feats):
        return np.dot(self.w, feats)

    def update(self, y, feats):
        l = max([0, 1-y*np.dot(self.w, feats)])
        eta = self._get_eta(l, feats)
        self.w += eta*y*feats
        self.t += 1
        return 1 if l == 0 else 0

PA-ⅠとPA-Ⅱ,いずれもこのクラスを継承して損失関数部分をちょっと変えただけです.その分初期化時にCを与えてあげる必要が出てきます*4

#!/usr/bin/env python
#-*-coding:utf-8-*-

import numpy as np
from passive_aggressive import PassiveAggressive

class PassiveAggressive1(PassiveAggressive):
    def __init__(self, feat_dim, c=0.1):
        self.c = c
        PassiveAggressive.__init__(self, feat_dim)

    def _get_eta(self, l, feats):
        return min(self.c, l/np.dot(feats, feats))
#!/usr/bin/env python
#-*-coding:utf-8-*-

import numpy as np
from passive_aggressive import PassiveAggressive

class PassiveAggressive2(PassiveAggressive):
    def __init__(self, feat_dim, c=0.1):
        self.c = c
        PassiveAggressive.__init__(self, feat_dim)

    def _get_eta(self, l, feats):
        return l/(np.dot(feats, feats)+1/(2*self.c))

検証

ということで,実際にモデル性能を確認してみましょう.使用したデータは,libsvmのテストデータから,a1aの訓練データテストデータを持ってきて使いました*5.データの素性ベクトルはは123個の要素を持ちます.訓練データには30956個,テストデータには1605個のサンプルがあります*6

まずは訓練データを用いて,オンライン学習をさせていった結果がこちらです.割とすぐに収束してしまい,そんなに動きがありません.PAPA-ⅠはどちらもAccuracyが60%程度,その一方でPA-Ⅱは40%台とだいぶ低いです.もっと差がつくかと思っていたのですが,かなり意外な結果です.ぐぬぬ...

http://f.st-hatena.com/images/fotolife/S/SAM/20141013/20141013123220_original.png

気を取り直して,オンライン学習で求めたモデルを元に,テストデータで(今度はオンライン学習ではなく単なる線形識別器として)識別をしてみましょう.結果は以下のとおり,今度はPA-ⅠとPA-Ⅱの両方が,ほぼ同じ精度で80%越えの識別率を出しました.これに対して,PAのAccuracyは70%程度と大きく差がつきました.

http://f.st-hatena.com/images/fotolife/S/SAM/20141013/20141013123221_original.png

このあたりは,ソフトマージン化することで汎化性能を高めたモデルの方が,ベースのモデルよりも新規データでの予測率が高いという,ごく当たり前の結果なのかなぁと思います.とはいえ元のオンライン学習でPA-Ⅱの結果がだいぶ悪いのはよくわからないですが...

まとめ

ということで,PAを作って試してみたよというお話でした.次はCWとSCWをやりたいなぁと考えています.いつになるかはわかりませんが...

*1:ちょっとググったら,こちらでオンラインの非線形識別器を実装してますね.別の記事には「分散オンライン学習も実装されているけど,(オーバーヘッドが大きかったり,収束が遅くなったりで)実用上はほとんど役に立たないと思う」とも書かれており,まぁ分散までいくとだいぶ難儀だろうなぁと思ったりします.

*2:第3式をみればわかるように,判別に間違えたら,間違えたサンプルを正しく判定できるように重みを更新するので,はずれ値が1つ入るだけで,大きく重みが更新されてしまいます.この性質は,識別器の汎化性能を考えると大きな問題になると考えられます.

*3:冒頭でパーセプトロンについて触れてますが,PAパーセプトロンって似てますよね...

*4:ここではデフォルト値として0.1を置いちゃってますが.

*5:前処理等のためにヘルパークラスをいくつか作ってgithubにあげてあります.

*6:今回の実験では,いくつかパラメタを変えて試した上で,それぞれPA-Ⅰ,PA-Ⅱとしています.