甲斐性のない男が機械学習とか最適化とかを綴るブログ

うどんくらいしか食べる気がしない

情報推薦の論文

明けましておめでとうございます。

ブログ開設当初は、月1ペースの更新を目標にしてたんですが、
案の定、2ヶ月以上放置。
気がつけば年が明けてました・・・
こんな感じで、今年もテキトーにやっていこうと思うので、
よろしくお願いします。

というわけで、今回は情報推薦です。
amazonの「この商品を買った人はこんな商品も買っています」や、
聴いた曲の履歴からお勧めのアーティストを推薦してくれるLastFM等々
世の中、情報推薦サービスが増えてきています。
研究トピックとしても結構盛り上がってる分野で、
ACM主催のrecsysのように情報推薦の国際会議もあります。
学生のころ所属していた研究室でも、情報推薦の研究をしている人がいて、
評価実験の被験者になったりもしました。
こういう評価実験の被験者をやってても、何が推薦されるか結構楽しみだったりするので、
自分もちょっと挑戦してみたい分野でした。

といった興味も、最近は忘れかけていたのですが、
先日こんなwikiを発見して、情報推薦熱がちょっとだけ再燃。
ということで、適当に最近の論文をチラ見してみたり、
リファレンス論文を追ってみたりして、以下の論文を発見しました。

S. Rendle, C. Freudenthaler, Z. Gantner, and L. Schmidt-Thieme
BPR: Bayesian Personalized Ranking from Implicit Feedback (UAI2009)

いつものように、細かい説明や手法の正当性なんかの説明は論文に委ねるとして、
ここでは、手法の大まかな考え方と流れだけ述べていこうと思います。
タイトルにある「Implicit Feedback」とは、
クリック情報や商品を購入したという情報などのような、
数値的には0以上の値であるユーザの振る舞いの情報と言えます。
以降は、ユーザがある商品を購入した/しないという情報を基に推薦する
システムを例に挙げて、話を進めていきます。

まず、従来のMatrix Factorizationに基づく推薦手法を述べます。
ユーザuの商品iに対する嗜好度を\hat{x}_{uj}
また、\hat{X}\hat{x}_{ui} 要素に持つ\| U \| \times \| I \|の行列とします。
なお、ユーザの集合をU、商品の集合をIとしています。
更に、W\| U \| \times kの行列、H\| I \| \times kと定義し、
\hat{X} = WH^T
とします。\hat{x}_{ui} =<{\bf w}_u , {\bf h}_i>です。
既に分かっているユーザの嗜好度情報\hat{x}_{uj}を基に、
\hat{X}を近似するWHを求めて、推薦を行おうというのが、
従来のMatrix Factorizationによる推薦手法のようです。
正則化なしの最小二乗近似の場合、特異値分解によりWHを得られますが、
オーバフィッティングにより、うまくいかないようです。
そもそも、この論文のタスクImplicit Feedbackの場合、
商品を購入した/していないの情報だけしかないので、
ある商品に対するユーザの嗜好度\hat{x}_{ui}が分かっているわけではありません。
(嗜好度はユーザの商品に対する評価(amazonで言う星の数)などのExplicit Feedbackといえます。)

というわけで、この論文の提案手法です。
まず、この論文では「既に購入した商品は、購入していない商品に比べて嗜好度合いは高い」
という仮定を置き、モデルパラメータをMAP推定する手法となっています。
この手法で肝となるのは、アイテム(商品)のペアがあり、ユーザはそのうちのどちらが好みであるか
という情報を学習することです。
「商品のペアのうち、どちらが好みであるか」というのは、仮定より
ユーザが既に購入している商品の方が好みで、購入していない方は好みでないということになります。
両方の商品を購入済みの場合は、嗜好度に差をつけません。
従って、このペアに関しては学習に用いません。
逆に、商品のペアのうち両方とも購入していないとき、
このユーザはどちらの商品が好みであるか、
これを予測して最終的には推薦まで持っていくわけですね。

ユーザuが購入した商品の集合をI_u^+とします。
ここで、ユーザuは、商品iの方が商品jより好みだ、
と言う三つ組を集めた集合をDsとします。
Ds = \left\{ \left(u , i , j\right) \| i \in I_u^+ \wedge j \in I  \backslash I_u^+  \right\}です。
このDsからモデルパラメータを推定します。

この論文では、求めたいパラメータ\Thetaの事後分布をp \left( \Theta \| >_u \right)としています。
>_uは、ユーザuの好みの構造を表しているようです。
事後分布は尤度と事前分布の積に比例するので、
p \left( \Theta \| >_u \right) \propto p \left( >_u \| \Theta \right) p \left( \Theta \right)
となります。

ユーザの好みは、それぞれ独立としています。従って、
\displaystyle  p \left( >_u \| \Theta \right) = \prod_{\left(u , i , j\right) \in Ds}  p \left( i >_u j \| \Theta \right)
となります(途中計算は省いているので、詳細は論文の方をご覧ください)。
ここで、シグモイド関数\sigma \left(x \right) = 1/\left(1 +e^{-x} \right) を用いて、
 p \left( i >_u j \| \Theta \right) = \sigma\left(\hat{x}_{uij} \left( \Theta \right) \right)
となります。\hat{x}_{uij} \left( \Theta \right)は、どのようなモデルを適用するかによって変わる関数です。
具体的なモデルについては、Matrix Factorizationに基づくものと、
k-nearest neighborの2つが論文内で示されています。
具体的なモデルはちょっと置いておいて、今度はp \left( \Theta \right)を考えます。
こちらは、おなじみ(?)平均0、共分散行列\lambda {\bf I}正規分布としています。
ということで、目的関数は、
 \displaystyle BPR-Opt = \max_{\Theta}  \ln p \left( >_u \| \Theta \right) p \left( \Theta \right)
です。これと上記の式から、以下の最適化問題を得ます。

\displaystyle BPR-Opt = \max_{\Theta} \sum_{\left(u , i , j\right) \in Ds} \ln \sigma\left(\hat{x}_{uij} \left( \Theta \right) \right) - \lambda || \Theta ||^2

この最適化問題を解くことで、パラメータを推定し、推薦を行うというのが
この論文で提案しているBayesian Personalized Ranking(BPR)の枠組みとなります。

 BPR-Opt微分を計算すると以下のようになります。

\displaystyle \frac{\partial}{\partial \Theta} BPR-Opt \propto \sum_{\left(u , i , j\right) \in Ds} \frac{-e^{-\hat{x}_{uij}}}{1+e^{-\hat{x}_{uij}}} \cdot \frac{\partial}{\partial \Theta} \hat{x}_{uij} - \lambda \Theta
(2012/2/3追記
 自分で計算してみたら、eの前のマイナスが出ませんでした。
 詳しくは、この記事の一番下参照)


ここでは、\hat{x}_{uij}(\Theta)を略して\hat{x}_{uij}と書いています。
通常の最急勾配法は、
\Theta \leftarrow \Theta + \alpha \frac{\partial}{\partial \Theta} BPR-Opt
という更新式になるのですが、
一般的に\left(u , i , j\right) \in Dsは膨大な数であり、
その数だけの合計を更新のたびに計算しなければいけないのは、
計算量や収束性の面でかなり難があります。

そこで、最急勾配法ではなく、以下のような確率的勾配法を用いて最適解を推定します。

1.\left(u , i , j\right) \in Dsから1組をランダムにサンプリングする。
2.この選択した1組を用いて、以下式で\Thetaを更新する。
\Theta \leftarrow \Theta + \alpha \left( \frac{-e^{-\hat{x}_{uij}}}{1+e^{-\hat{x}_{uij}}} \cdot \frac{\partial}{\partial \Theta} \hat{x}_{uij} - \lambda \Theta \right)
(2012/2/3 追記
 ごめんなさい!!ここも間違えて書いちゃってます。
 詳しくは下記参照。)

収束するまで、これを繰り返すのが、BPRの学習アルゴリズムです。

ここまで来ると、じゃあ\Theta\frac{\partial}{\partial \Theta} \hat{x}_{uij}は何ぞやとなってきます。
その具体的な形の1つがMatrix Factorizationです。
まず、Matrix Factorizationで求めたいのは、
\hat{X}WH^Tの形で近似するWHです。
従って、\Theta = \left(W , H \right)です。
次に、\hat{x}_{uij} \left( \Theta \right)は、
\hat{x}_{uij} \left( \Theta \right) = \hat{x}_{ui} \left( \Theta \right) - \hat{x}_{uj} \left( \Theta \right) = <{\bf w}_u , {\bf h}_i> - <{\bf w}_u , {\bf h}_j>
とみなせます。
これにより、\frac{\partial}{\partial \Theta} \hat{x}_{uij}は次のように場合分けができます。

サンプリングにより、 \left( u , i , j \right)を選択したとして、

{\bf w}_uの更新
\frac{\partial}{\partial \Theta} \hat{x}_{uij} = {\bf h}_i - {\bf h}_j

{\bf h}_iの更新
\frac{\partial}{\partial \Theta} \hat{x}_{uij} = {\bf w}_u

{\bf h}_jの更新
\frac{\partial}{\partial \Theta} \hat{x}_{uij} = - {\bf w}_u

それ以外
\frac{\partial}{\partial \Theta}  \hat{x}_{uij} = {\bf 0}

つまり、 \left(W , H \right)のうち、1回のステップで更新されるのは、
サンプリングされた \left( u , i , j \right)に対応する{\bf w}_u , {\bf h}_i , {\bf h}_jの計3行のみです。

これがBPRによるMatrix Factorizationアルゴリズムですが、
正直、本当に収束するんかいな?って感じです。
確かめるためには、実装して試してみるのが1番なんで、
早いうちに実装したいなと思いますが、
とりあえず、今日のところはここまで。
この実装結果は、別の記事に書きたいと思います。
なるべく今年中に・・・

2012/2/3追記
収束しない!?
と思ったら、いくつか間違いを発見。

まず、BPR-Opt微分ですが、
自分で計算してみたら、
\displaystyle  \frac{\partial}{\partial \Theta} BPR-Opt \propto \sum_{\left(u , i , j\right) \in Ds} \frac{e^{-\hat{x}_{uij}}}{1+e^{-\hat{x}_{uij}}} \cdot \frac{\partial}{\partial \Theta} \hat{x}_{uij} - \lambda \Theta
になりました。
 
ということで、更新式は
\Theta \leftarrow \Theta + \alpha \left( \frac{e^{-\hat{x}_{uij}}}{1+e^{-\hat{x}_{uij}}} \cdot \frac{\partial}{\partial \Theta} \hat{x}_{uij} - \lambda \Theta \right)
になる。
と思いきや、論文をもう一度読み直してみると、
\Theta \leftarrow \Theta + \alpha \left( \frac{e^{-\hat{x}_{uij}}}{1+e^{-\hat{x}_{uij}}} \cdot \frac{\partial}{\partial \Theta} \hat{x}_{uij} + \lambda \Theta \right)
と、正則化項のところがプラスになってます。

自分の計算が間違えてるのかなと思いましたが、
同じ研究グループの別の論文
Learning Attribute-to-Feature Mappings for Cold-Start Recommendations (ICDM2010)
内でもBPRのアルゴリズムが記述されており、
そちらでは、更新式が
\Theta \leftarrow \Theta + \alpha \left( \frac{e^{-\hat{x}_{uij}}}{1+e^{-\hat{x}_{uij}}} \cdot \frac{\partial}{\partial \Theta} \hat{x}_{uij} - \lambda \Theta \right)
になってるので、これが正解のようです。