のんびり読書日記

日々の記録をつらつらと

確率的勾配降下法による行列分解を試してみた

Programming

前々回のNMF(Non-negative Matrix Factorization)に続いて行列分解ネタです。言語処理学会全国大会のチュートリアル「推薦システム -機械学習の視点から-」で紹介されていた、確率的勾配降下法による行列分解を試してみました。チュートリアルの資料は公開されていないようでしたので、元論文の方のリンクを張っておきます。実際には同じ著者の別の論文を引用されてましたが、僕には下の論文の方が分かりやすかったのでこっちで。

作成したコードは以下に置いてあります。行列演算にEigenを使用しているので、実行する場合は事前にEigenをインストールしておいてください。また入力データにはMovieLensの100Kのデータを使用したので、こちらも合わせてダウンロードしてください。

比較と勉強を兼ねて、以下の3つの手法で行列を分解するクラスを入れています。手法の切り替え用オプションは用意してないので、適宜ソースコードを修正して下さい。

  • 勾配降下法(gradient descent)
    • データ全体から勾配を計算。大規模データには向かない
  • 確率的勾配降下法(stochastic gradient descent)
    • データ全体ではなくデータ1個ずつ行列の更新を実行。省メモリ
  • 確率的勾配降下法にバイアス項を追加(stochastic gradient descent)
    • 評価値のゆらぎをバイアスとして補正
      • ユーザAは高評価をつけやすい、アイテムBは低評価ばかりつけられているなど。
    • 今回は全体の平均、ユーザごとの評価の揺らぎ、アイテムごとの評価のゆらぎを使用

数式など詳細については上記の論文をご参照下さい。

実行する時は以下のようにします。MovieLensの100kのデータは交差検定用に初めからトレーニング・テストのペアが5セット用意されているので、それを使って5分割交差検定を実行します。またレートの予測の評価にはNetflix Prizeでも使用されている、二乗平均平方根誤差(RMSE)を表示しました。ちなみにNetflix Prizeの2009年度の優勝チームのRMSEは0.8558だったようです(元のデータが違うので単純に比較できないでしょうが)。

% g++ -Wall -O3 factorize_sgd.cc -o factorize_sgd
% ./factorize_sgd
Usage: ./factorize_sgd dir ncluster niter eta lambda

% ./factorize_sgd /path/movilens 10 100 0.1 0.1
Training data: /path/movielens/u1.base
Test data:     /path/movielens/u1.test
Factorizing input matrix ...
RMSE=0.975

Training data: /path/movielens/u2.base
Test data:     /path/movielens/u2.test
Factorizing input matrix ...
RMSE=0.968

Training data: /path/movielens/u3.base
Test data:     /path/movielens/u3.test
Factorizing input matrix ...
RMSE=0.967

Training data: /path/movielens/u4.base
Test data:     /path/movielens/u4.test
Factorizing input matrix ...
RMSE=0.964

Training data: /path/movielens/u5.base
Test data:     /path/movielens/u5.test
Factorizing input matrix ...
no data: row:863 col:1680
no data: row:896 col:1681
no data: row:916 col:1682
RMSE=0.960

Result of cross validation: RMSE=0.967

各手法での結果を比較すると、こんな感じになりました。

手法 RMSE クラスタ数 反復数 eta lambda
勾配降下法 1.012 10 100 0.001 0.001
確率的勾配降下法 0.967 10 100 0.1 0.1
確率的勾配降下法(バイアス項つき) 0.981 10 100 0.1 0.1

バイアス項を加えたときが一番精度がよくなるはずなのですが、普通の確率的勾配降下法よりも結果が悪くなってますね。。。うーん、理解が間違ってるのかバグってるのか。それと今回は全体の平均、ユーザごとの評価の揺らぎ、アイテムごとの評価のゆらぎをバイアス項として加えたのですが、論文にはこれ以外に、ユーザの行動履歴(映画なら鑑賞した映画のリストなど)を組み合わせる話や、評価時刻を考慮したモデルなども書かれていましたので、次回はその辺を試したいと思います。

あとeta, lambdaパラメータの設定がちょっと面倒で、適切に変更してやらないとすぐに値が膨れ上がって、正しい結果が得られなくなってしまいました。更新時にどうにか抑えることはできないのかなぁ。あとパラメータいじって最適なものを自分で探すってのはちょっとイヤですね。自動で最適なものを探すようにしたい。

行列演算部分はEigenを使ったのですが、今回ぐらいのだと大したことをしていないので、別に自前で書いても良さそう。無駄に他のライブラリへの依存しない方がいいかなぁ。いずれ修正してみます。

とりあえず次回はユーザの行動履歴を加えたバージョンに続きます。たぶん。

追記(2010/4/13)

コメント欄にてご指摘いただき、ソースコードを一部修正しました。ありがとうございます！＞しましまさん

修正内容は以下の通りです。

  • ユーザ、アイテムのバイアス項の設定部分の修正
  • 元のコードでは各バイアス項(全体の平均、ユーザごとの評価のゆらぎ、アイテムごとの評価のゆらぎ)を初めに設定してその値をそのまま使っていたのを、行列の更新時に同時にバイアス項も更新させる手法を追加

変更後の各手法の結果は以下の通りです。

手法 RMSE クラスタ数 反復数 eta lambda
勾配降下法 1.012 10 100 0.001 0.001
確率的勾配降下法 0.967 10 100 0.1 0.1
確率的勾配降下法(バイアス項つき・更新なし) 0.979 10 100 0.1 0.1
確率的勾配降下法(バイアス項つき・更新あり) 0.962 10 200 0.1 0.1

バイアス項を各ループで更新するバージョンが一番結果がよくなりました！論文どおりでほっとしました^^; もっとしっかりサーベイしないとダメですねぇ…。