2012年1月3日火曜日

NIPALSとかPLSとか

昨今の認識アルゴリズムは,マシンパワーにものを言わせて判別に使う情報量をどんどんと増やしていく傾向にあると思うのです. 例えばHOGとかがいい例ではないでしょうか.私の5年前のノートPCでは遅すぎて使いもになりません.

そもそも自分が学習機ならとても覚えられないような情報量を無理やり食わせて,性能をだすことができるんでしょうか. もっとシンプルにやる方法が必ずあるに違いないと心の奥底で私は信じているのですが,今は具体案を提案できている状態ではないので私の主張には説得力はありません.

実際に人間の脳みそは,体重比率で大きなウエイトを占めているわけで,生物の知能が発達すると共に脳みそは大きくなってきたのを鑑みると,高度な情報を処理するためには複雑な仕組みが必要なのだと,暗に示唆されているようにも思えます.高度な知性を実現するには脳みそのような複雑なハードが必要なのだという証だといわれれば反論するのが難しいです.

だけれどもほんの一部でもいいから,シンプルな手法によって人間の知性を計算機の上で実行できないものだろうかと思うのです. 映像から人がどこを歩いているのかだけでも人並みに判別できれば,悲惨な交通事故をもっと減らすことのできる役立つ機械を作ることが出来るはずです.
もしシンプルに計算量の少ないアルゴリズムでそれが実現できれば,安いハードウエアで製品を構成することができるようになり,普及が期待されます.

そこで手っ取り早い方法として性能は保証されているけれど膨大な情報を収集する必要のあるアルゴリズムを使いつつ,その中からあまり重要ではない情報をふるいにかけて情報量を減らして,計算量を減らすアプローチを考えます.このようなことをやる代表的な手法として主成分分析(PCA)があります.PCA-SIFTなどが応用例としていい例でしょう.

でも実際にPCAを分類器に入力するデータの次元圧縮手段として使ってみると,期待したほど性能は良くないんじゃないかという印象を持っています. もちろんそれはケースバイケースなんだと思いますが,画像認識に使うようなデータでは判別結果に使うパラメータの線形独立性を期待できないことがほとんではないでしょうか.

そのようないい加減なデータでもパワフルに働いてくれる次元圧縮方法がないものかと探していたら,先日PLSという手法(Partial Least Square)を見つけました.化学分析分野でよく用いられる方法のようで,例えば,サンプルの各波長における吸光度から,どのような物質がどのような割合で含まれているかなどを分析するために開発された手法のようです.

日本語で書かれたフリーで読める文献がありました.こちらです「PLS 回帰におけるモデル選択」.でも日本語で読んでもなんだかよく分かんなかったです.ちょっと苦しいけれど英語の文献の方が丁寧に書かれていて,理解しやすかったりすることも多いです.これもいいかも知れません「A Beginner’s Guide to Partial Least Squares Analysis
実は自分が参考にした最もわかりやすかった文献のリンクが今探せないです.どこいっちゃったものだか.あとで見つけたら追記しておきます.

このPLSをお手軽にためすには,「R」のplsパッケージを使うのが良いみたいで,PLSの紹介論文などでは,Rに付属のgasolineという吸光度とオクタン価の関係を測定したデータが良く紹介さrています.Rはあんまり好きじゃないので,早速,ガソリンデータを使ってPLSアルゴを試すpythonコードを書いてみました.
01def NIPALS_internal(X, Y, n, M, N, u, epsilon):
02    u0 = u
03    while True:
04        w = X.T * u / (u.T * u)
05        w = w / norm(w)
06        t = X * w
07        c_ = Y.T * t / (t.T * t)
08        c = c_ / norm(c_)
09        u = Y * c
10        if norm(u0 - u) < epsilon: break
11        u0 = u
12    p = X.T * t / (t.T * t)
13    q = Y.T * u / (u.T * u)
14    Xnew = X - t * p.T
15    Ynew = Y - t * c_.T
16    return Xnew, Ynew, t, u, p, q, w
17 
18def NIPALS(X, Y, k = 1, epsilon = 1e-12):
19    n, N = X.shape
20    M = Y.shape[1]
21    X_mean = X.mean(axis=0)
22    X_std = X.std(axis=0)
23    Y_mean = Y.mean(axis=0)
24    Y_std = Y.std(axis=0)
25    X_ = (X - X_mean) / X_std
26    Y_ = (Y - Y_mean) / Y_std
27    X__, Y__ = X_, Y_
28    W = matrix(zeros( (N, k), float32))
29    T = matrix(zeros( (n, k), float32))
30    U = matrix(zeros( (n, k), float32))
31    P = matrix(zeros( (N, k), float32))
32    Q = matrix(zeros( (M, k), float32))
33    for i in range(k):
34        u = Y_[:,0]
35        Xnew, Ynew, t, u, p, q, w = NIPALS_internal(X__, Y__, n, M, N, u, epsilon)
36        X__, Y__ = Xnew, Ynew
37        W[:,i], T[:,i], U[:,i], P[:,i],Q[:,i] = w,t,u,p,q
38    B = X_.T * U * (T.T * X_ * X_.T * U).I * T.T * Y_
39    return (B, X_mean, X_std, Y_mean, Y_std)
Rのplsに付属のガソリンデータの読み込みと,既述のNIPALS(), NIPALS_predict()の利用シーンは次のような感じです.
01def load_gasoline():
02    f = open("gasoline.txt")
03    reader = csv.reader(f, delimiter=' ', quoting=csv.QUOTE_NONE)
04    octane, NIR = [], []
05    for i, row in enumerate(reader):
06        if i > 0:
07            octane.append(int(row[0].strip('\"')))
08            NIR.append([float(j) for j in row[1:]])
09    return matrix(octane).T, matrix(NIR)
10 
11if __name__ = '__main__':
12    Y, X = load_gasoline()
13    tt = []
14    t_y0, t_y1 = [],[]
15    for h in range(2,26):
16        s = 0
17        for i in range(60):
18            p = NIPALS(X, Y, h)
19            Y_ = NIPALS_predict(p, X[i,:])
20            t_y0.append(Y[i,0])
21            t_y1.append(Y_[0,0])
22            s += abs(Y[i, 0] - Y_[0,0])
23        tt.append(s/60)
24 
25    gp = Gnuplot.Gnuplot(debug = 1)
26    gp.xlabel('X')
27    gp.ylabel('Y')
28    gp('set grid')
29    s = Gnuplot.Data(range(len(tt)), tt, title='error',with_='points 3 3')
30    s1 = Gnuplot.Data(range(len(t_y0)), t_y0, title='raw',with_='line')
31    s2 = Gnuplot.Data(range(len(t_y1)), t_y1, title='predict',with_='line')
32    gp.plot(s, s1, s2)
33    raw_input()
これを足がかりにして認識アルゴリズムに応用して性能を試すようなことを正月休みにやってみたいと思っていたけど,子供たちの喧騒の中でブログに書くのが精一杯でした.

休みも残すところ今日の半日と明日1日になってしまいました. そろそろ家出ゴロゴロしているのがだるくなってきたので,これからどこかへ出かけてみたいと思っていますが,人ごみは嫌いであり,はて どこへ行こうか,子供たちは雪遊びできるところへ行けば喜ぶに違いありませんが,心の底から雪遊びを楽しむ心を忘れてしまった私は,寒いばかりなので他にいいところは無いものかと考えるのですが,人ごみも苦手だし,あてもなく困ったものです.