今回は前回に引き続き、推薦の話をしようと思います。
前回はアクセスログを使って関連するアイテム ( 芸能人 ) を推薦するという話だったのですが、今回は明示的な評価データがある場合に、それを使って、ユーザーの未評価アイテムの評価予測をするという話をします。
例えば、世の中の大半のレビューサイトにはユーザーの5つ星評価を投稿できるしくみがあります。Amazon、食べログ、PlayStation Network ( ゲームレビュー ) などなど例をあげればキリがありませんが、そういったユーザーがつけてくれた５つ星のデータを使って、ユーザーの好みのアイテムを推薦しようという話です。
実はこういった話は学術的には典型的なテーマになっていて、手法もほぼ確立されています。具体的には "協調フィルタリング" という技術を使うのですが、最近ではWEBサイトの一機能として普通に導入されているケースも多いので、単語くらいは聞いた事がある人は結構いるのではないかと思います。
この協調フィルタリングには、非常に多くの種類が存在しているのですが、その中でも精度が良くて使いやすいと最近言われているのが、表題にある Matrix Factorization という手法でして、今回はこれを紹介したいと思います。
尚、本エントリは、先月末に株式会社 GREE 様との合同勉強会で発表させていただいた内容の補足エントリになります。よろしければ下記のスライドも斜め読みして頂ければと思います。
■ Matrix Factorization と SVD
Matrix Factorization という言葉はいろんな分野で使われているのですが、推薦の分野に限っていうと、
『 SVD( singular value decomposition:特異値分解 )を元にしたモデルベースのレコメンド手法 』 というのが個人的な認識です。
こう書くと SVD* とはなんぞや？という話になるのですが、Matrix Factorization のベースになる考えなので、絵に書いて説明してみましょう。
( * 一般の SVD というのは wikipedia にあるように、固有値の対角行列を含む3つの行列に分解する手法なので、本エントリにおける SVD の定義はあくまでここだけの話と考えてください。2011/8/12 修正 )
まず与えられた5つ星のレビューのデータは一般的に以下のような行列で書く事ができます。
そしてこのレビューのデータセットを 評価行列 R とすると、Matrix Factorization における SVD というのはこの R を以下のように二つの行列 U と I に分解する手法全般のことをさします。
行列 R はユーザーのアイテムの評価行列、U はユーザーの属性を表した行列、I はアイテムの属性を表した行列です。
図に出てくる K という変数は、隠れ変数 z ( 0 <= z < k ) の総数を表しているのですが、この隠れ変数 z は、手元にあるユーザーの評価情報から読み取れる、ユーザーとアイテムの共通属性みたいなモノです。
具体例を挙げていきましょう。例えば、元の5つ星のデータが映画のレビューデータだったとします。この場合の SVD の z は映画の属性という意味に解釈できるので、例えば "アクション"、"恋愛"、"3D"、"洋画"、"邦画"、"アニメ"、"xxx(俳優)"、"ハッピーエンド"、"ストーリーの緻密さ" などといったモノが考えられます。
（ 実際には、属性 z は解析者が意図的に与えるモノではなく、SVD を行った結果、様々な属性が自動的に分かります。上記のように人間に理解できる属性もあれば、人間にはよく分からない属性ができたりするケースもあります。 ）
仮に z が "アクション" 属性だった場合、U と I の行列の成分 U [ i ] [ z ] と I [ z ] [ j ] の意味は、それぞれ " ユーザー i のアクション映画に関する興味の度合い " と " 映画 j のアクション映画の度合い " になります。
一方、R の各成分、ユーザー i によるアイテム j の評価 r [ i ] [ j ] は、分解した行列の右辺を計算すると以下の通りになっているのですが、
Σの中身 U [ i ] [ z ] × I [ z ] [ i ] は、 U [ i ] [ z ] と I [ z ] [ j ] のそれぞれの値がともに大きいときにスコアが高くなります。これは先の説明をふまえると "自分が面白いと感じる属性が映画によく含まれていると評価が高い" という意味で解釈することができます。
またこの U [ i ] [ z ] × I [ z ] [ i ] を z 毎に足して行くという部分は、ユーザーやアイテムには属性が複数存在しているという事を意味していますが、これは実世界であっても自然に理解できる仮定なので、両者を鑑みると、SVD による評価予測のモデルは人間にとって非常に分かり易いという事が分かります。
■ SVD の問題点
前節で説明したように、SVD は人間にとって非常に分かり易いモデルなのですが、実際には大きく分けて二つの問題から、そのままでは推薦にうまく適用することができません。
一つ目は欠損値の問題です。
ユーザーが全てのアイテムに対してレビューをしてくれればありがたいのですが、現実にはそうしたケースはほぼ確実にありません。よってその未評価部分は欠損値として扱われ、評価行列 R はほとんどが未評価で穴だらけの行列になっています。
理想としては、評価されている部分だけをうまく使って SVD を実行して U と I を求め、今度は逆に、その U と I を使って、未評価部分の値を推測したいところですが、一般的な SVD には欠損値がある場合に対応した手法が存在しません。
そのためこのような場合には欠損値補完 [1] という技術を使うのが一般的なのですが、これは補完精度が悪く、あまりうまくいかない事が分かっています。
( やや話はずれますが、PLSA [2, 3] を使った協調フィルタリングは SVD 同様に隠れ属性をモデルに組み込んだ非常に良く似た手法ですが、PLSA は SVD とは違い、欠損値の有無に関わらず使える手法だったので利便性がよく、精度も良かったので推薦方法としてよく流行りました。Google News の推薦 [4] などで使われていたそうです。 )
次に二つ目の問題ですが、それは SVD のモデルだけでは現実の現象をそこまでうまく捉える事ができないという根本的な問題です。
実際、人間によるアイテムの評価というのは、いろんな要素で決まるモノです。
例えば、レビューを投稿する際にそのアイテムに対する周りの評判が高い事をユーザーが知っていれば、ユーザーが評価をより高く設定する心理が働く可能性がありますし、そもそもレビューに投稿する時点である程度好きか嫌いかに偏っている可能性もあります。
またレビュアーがかなり批判的な場合はユーザーの興味云々に関係なく評価が下ぶれしやすいでしょうし、そもそも論ユーザーの興味やアイテムの評価なんて時間と共に変わる可能性が高い気がします。
このように、評価には様々なファクターが無数に考えられるのですが、前節で説明した SVD ではこういった効果をうまく捉えるのにはあまり向いてはいないのです。
以上の二つが大きな問題点なのですが、これらをうまく解決したモノが Matrix Factorization の基本的な推薦手法になります。
■ Matrix Factorization とは？
もっとも基本的な Matrix Factorization とは以下のような評価予測モデルと学習方法を指します。
まず評価値の予測モデルですが、各項を順番に説明していくと、
μ → 全評価データの平均評価得点
b_user → ユーザーの影響による平均得点からの偏差。例えば批判的なユーザーかどうかなど。
b_item → アイテムの影響による平均得点からの偏差。例えば世間的に評判が良いかどうかなど。
U × I → ユーザーの興味とアイテムの属性の近しさ。SVD と同じ。
となります。このように Matrix Factorization では SVD の項に加えて μ, b_user, b_item などを考慮した拡張モデルになっています。これにより前節で上がっていた問題点のうちの後者の部分を幾分解決する事が可能で、これによって大幅な精度アップができます。
ところで μは評価データセットが当たられた時点でわかるので、学習すべきパラメータとしては、b_user、b_item、U、I の計４つになります。
さてこれらのパラメータの学習方法ですが、上図の下にあるような目的関数の最小化によってパラメータを決めます。目的関数の第1項は、実際の評価値との二乗誤差の総和を表し、第2項は学習パラメータの過学習を避けるための正則化項になっています。
この目的関数で肝になるのは、Σを何でとっているか？という部分です。実際、Σの和はユーザーのアイテムの評価の組 (u,i) のみを使用しているのですが、欠損値の部分の評価は一切していません。このおかげで、従来では欠損値問題でうまく解けなかった SVD が解けるようになっているのです。
( 狭義の意では評価予測にb などを付け加えた時点で、SVD とはもはや関係ないモデルだと思うのですが、推薦分野界隈では、慣習的にこのようなモデルでも SVD と呼ぶらしいです。 )
さて、実際のパラメータの学習方法ですが、これには 確率的勾配法(SGD)を使った方法 [5]と、ALS [6, 7]を使った方法の２種類があります。
メモリに収まらないような超巨大データを扱わない限り、一般的にはSGDを使った方が速度的に優位です。文章量の関係で詳細は [8, 9] に譲りますが、具体的なパラメータの更新方法はそちらを参照してください。
■ 性能評価・精度評価
公開されているテストデータを用いて、Matrix Factorization ( SVD ) がどの程度優れているのか 性能・精度評価試験を行ってみました。
今回比較するアルゴリズムとして、無作為評価、SlopeOne [10] 、PLSA ( continuous forced model )
[2, 3] の3つで 比較してみました。また今回説明はできなかったのですが、SVDの発展版の SVD++ [9] の結果も併せて載せておきます。
【データ】 ： MovieLens 100k ( 映画の5段階評価データ )
- データ数 ： 100,000
- ユーザー数 ： 943
- アイテム数 ： 1,682
【評価方法】 ： 5-fold-cross validation で以下を計測
精度 → MAE( mean absolute error ) 、RMSE ( root mean square error )
時間 → 5-fold-cross validation を行ったトータルの時間コスト
【環境】 ： OS : Winows7(64bit)、CPU : Core i7-2620M、2.7GHz、 メモリ : 8G
【実装言語】 ： Java
結果は以下のようになりました。
まず初めに前提を話しておくと、精度は小さい方が良い事を意味します。例えば MAE は "評価予測値と実際の5段階評価の値が平均で上下にどの程度ずれるのか？" という事を表していますので、そういう目で結果を眺めてもらえればと思います。
さて実際の結果ですが、精度を見ると Matrix Factorization(SVD) 系が一番良く、計算時間では SlopeOne には負けましたが Matrix Factorization も殆ど遜色ないレベルの速度でした。
( SVD++は遅いですが…実装に問題があったのかもしれません。 )
SlopeOne は Mahout [11] にも実装が存在しますし、巷のブログではどこぞのサービスで使っているとかいう話も耳にするので割と実践的な手法だと個人的思っているのですが、今回紹介した Matrix Factorization ( SVD ) は十分その代替になるのではないかと思うのですが、どうでしょうか？
ちなみに今回の検証で使ったコードは Google Code でOSSとして公開しておりますので、良かったら自由に使ってみてください。
mf_predictor
■ 雑記・感想など
昨今 Ameba のサービスの中にもユーザーに評価データを付けてもらう箇所があったり、疑似的に5段階評価データとして扱えるデータがいくつも存在しているので、これをうまく利用できないか？と思い立ち、最近ではこんな事をやっています。
文書量的に書けなかったのですが、今回 Matrix Factorization に注目したのは timeSVD++ [9] というダイナミクス(時間発展)を加味したモデルを試してみたかったのがそもそもの理由でした。
推薦する対象にもよるのですが、定性的に考えて時間軸が関係しているだろうなぁという推薦対象というのは割とある気がしていて、今、想定する実データでうまく嵌るのかどうか試している最中です。
後、今回意図的に "推薦" という言葉を使わず、"評価予測" という言葉を積極的に使っているのですが、これは評価予測と推薦は別モノだと考えておいた方がよさそうだからです。
これはどういう事かというと、レコメンド屋の理想？としては、ユーザー毎にその人の特徴にあった推薦リストが出来上がってほしい所ですが、実際に協調フィルタリングを用いてアイテムの予測値の高いモノを順に列挙する推薦リストを作成しても、誰の推薦リストにも有名なアイテムだけが並ぶ、非個性的な推薦結果になってしまうというパターンが結構あります。
これは映画を例に挙げると、タイタニックとかアバターとかいった有名な映画は、自分の趣味趣向には関係なく誰が評価しても高い評価になるという事なのですが、別に面白いんだったらそういった無個性な推薦リストを提示してもいいじゃないか？という話もある一方で、それだったら最初から推薦アルゴリズムなど使わず、今流行りのアイテムや売上上位のアイテムを推薦すればいい気がします。
ではそもそも協調フィルタリングは無意味なのか？というとそうでもなく、要は使い方の問題だと思っています。
例えばサービスで推薦によって併売を進めるようなシーンでは、前回紹介したような関連アイテム推薦のアルゴリズムでリストを作成した後に、評価予測の結果を使ってそのリストをリランキングするといった方法や、
個性をより強調した推薦をしたいのなら、単純に評価予測の絶対値を使うのではなくて、アイテムの平均評価予測値からの偏差が大きいモノを推薦リストの上位に挙げてみるなど、評価予測から推薦に昇華する方法はいろいろあると思います。
これがいい！といった推薦手法などは、正直よくわからないのですが、少なくとも精度の良い評価予測ができる事は面白い推薦リストを作る上で強力な武器になるはづなので、身につけておいて損はないと思います。
以上、今回はこれで終わりです。
長々とおつき合い頂きましてありがとうございました。
■ Reference
[1] B.M Sarwar etal ： Application of Dimensionality Reduction in Recommender System ― A Case Study, (2000)
[2] Thomas Hofmann ： Latent Semantic Models for Collaborative Filtering (2004)
[3] Thomas Hofmann ： Collaborative Filtering via Gauusian Probabilistic Latent Semantic Analysis (2003)
[4] A.Das et al ： Google News Personalization : Scalable Online Collaborative Filtering (2007)
[5] S.Funk ： Netflix Update : Try This at Home (2006)
[6] Y.Zhou et al： Large-scale Parallel Collaborative Filtering for the Netflix Prize (2008)
[7] Y.F.Hu、 Y.Koren and C. Volinsky ： Collaborative Filtering for Implicit Feedback Datasets (2008)
[8] Y.Koren、R.Bell、C.Volinsky ： MATRIX FACTORIZATION TECHNIQUES FOR RECOMMENDER SYSTEM (2009)
[9] Y.Koren、R.Bell ： Advances in Collaborative Filtering (2011)
[10] Y.Koren、R.Bell ： Slope One Predictors for Rating-Based Collaborative Filtering (2005)
[11] Mahout