情報推薦の論文 - 甲斐性なしのブログ

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

ブログ開設当初は、月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}$ を近似する $W$ と $H$ を求めて、推薦を行おうというのが、
従来のMatrix Factorizationによる推薦手法のようです。
正則化なしの最小二乗近似の場合、特異値分解により $W$ と $H$ を得られますが、
オーバフィッティングにより、うまくいかないようです。
そもそも、この論文のタスク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}$ は何ぞやとなってきます。
その具体的な形の１つがMatrix Factorizationです。
まず、Matrix Factorizationで求めたいのは、
$\hat{X}$ を $WH^T$ の形で近似する $W$ と $H$ です。
従って、 $\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)$ のうち、１回のステップで更新されるのは、
サンプリングされた $\left( u , i , j \right)$ に対応する ${\bf w}_u$ , ${\bf h}_i$ , ${\bf h}_j$ の計３行のみです。

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

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)$
になってるので、これが正解のようです。