【論文紹介】Collaborative Metric Learning (WWW2017)

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。

今回は、協調フィルタリングとmetric learningを組み合わせたCollaborative Metric Learning (CML)の論文を読んで要点をまとめました。

## 概要

従来の協調フィルタリングでは、内積によりuser-itemの交互作用を考慮することでuserの好みを潜在表現として獲得していたが、内積では三角不等式を必ずしも満たさないので、良い表現が得られない可能性があります。
本研究では協調フィルタリングとMetric Learningを組み合わせたCollaborative Metric Learning (CML)を提案し、user-userやitem-itemの類似度も考慮した空間に埋め込み、近似最近傍探索に応用することでtop-k推薦を高速化しました。

## 協調フィルタリングの問題点

Matrix Factorizationなどの手法では、userとitemをある空間に埋め込み、
それらの内積によりuserがitemを好むかどうかを表現しています。

このようにして得られるuser,itemのembeddingは、正しく学習されれば近い場所に埋め込まれるはずです。
userがitemを好めば内積が大きくなるように学習するので、当然ですね。

では、似たようなuser同士や、似たようなitem同士は近くに埋め込まれるのでしょうか？
なんとなく近くに埋め込まれる気もしますが、必ずしもそうはならない、というのが本論文の主張です。

論文中にある次の図を見るとわかりやすいです。

左がMatrix Factorizationなどの内積を用いた場合のembedding,右が今回提案するようなmetic learningを使って得られる(得られてほしい)embeddingを可視化した図です。

User group $U_1$はitem $v_1$を、User group $U_2$はitem $v_2$を、
User group $U_3$はitem $v_1, v_2$の両方を好む場合です。

内積を使った場合は、確かにuserがitemを好んでいる場合は内積が2で、好んでいない場合は0なので、学習はできています。

しかし、user $U_3$がitem $v_1, v_2$の両方を好んでいるのである程度$v_1, v_2$は似ているはずなのに、$v_1, v_2$の内積を計算してみると0となってしまい、類似していないことになります。
図的には$v_1, v_2$が離れた場所に埋め込まれていることに対応します。

これは、内積が三角不等式を必ずしも満たさないために、user $U_3$が両方のitem $v_1, v_2$を好むという情報が$v_1, v_2$同士の類似度まで伝搬していないということです。

本当に欲しいembeddingは右のように、$v_1, v_2$のembedding同士が近くなるようなものであるはずだよね、というのが本研究のモチベーションになります。

## Collaborative Metric Learning (CML)

提案するCMLモデルはimplicit feedbackを扱うモデルです。

implicit feedbackはuserによるクリックや購入などのフィードバックを指し、レーティングなどのexplicit feedbackと対比されます。
implicit feedbackは正例のみ観測され、観測されないデータは本当に興味がないのか、ただuserがitemを認知していないだけなのか、が切り分けられないことが難しさの原因となっています。

CMLでは

* 観測された(user $i$, item $j$)よりも観測されていない(user $i$, item $k$)の方が距離が離れているべき

と考えます。

こんな感じですね。

観測されていない組にはもちろんrelevant(本当はuserがitemを好む)なものがあるはずですが、その強度は観測されたものと同等かそれ以下だろう、という仮定が(暗黙的にですが)置かれているように思えます。

この辺りはBPRに似ていると感じました。

ただ、BPRは外した時のpenaltyのかかり方がrankによって偏っていないという問題があるので、
WARPのように

* 予測した順位に応じてpenaltyを大きくする

という工夫をしています。

BPRやWARPについては論文紹介記事を書いたので、こちらも合わせて読んでいただけると理解いただけるかと思います。

【論文紹介】BPR: Bayesian Personalized Ranking from Implicit Feedback (UAI 2009) 【論文紹介】WSABIE: Scaling Up To Large Vocabulary Image Annotation (IJCAI 2011)

これらを合わせて次のようなlossを提案しています。

$w_{ij}$がuser $i$についてランキングを作った時のitem $j$にかかるpenalty(どれだけ大きく外しているか)で,残りの項が観測された(user $i$, item $j$)よりも観測されていない(user $i$, item $k$)の方が距離が離れるように設計されています。($m$はマージンでハイパーパラメータ)

$w_{ij}$は$\log (rank_d(i,j)+1)$のように定義していて、ランキング(user $u$に近い順にitemを並べている)を計算する必要があります。

WARPの元論文では、未観測データ集合からitem $j$よりもuser $u$に近いitemが出るまでサンプリングしてきて、出るまでにかかった回数を用いてrankを推定します(幾何分布の要領)

今回は、並列化できるようにということで、並列に$U$個negative samplingしてきて、そのうちitem $j$より近かったitemの個数から逆算してrankを推定しています。

他にも

* embeddingの共分散について正則化 ([参考](https://arxiv.org/abs/1511.06068))
* item featureをMLPにかけてitemのembeddingに近づける

という項をlossに加えているのですが、少し肝からそれるので割愛します。

item featureをMLPにかけて出てきたembeddingをそのまま使えばいいと思うんだけど、なぜそれとは別にembeddingを学習するのかがよくわかりませんでした。

正則化についてはそういうテクニックがあるのねふーんと思いました。
embeddingがなるべく独立になるように、というのはより効率的に空間を使ってembeddingを得たい、という気持ちが現れているようです。
参考にしている論文を読むとよりわかるかもしれません。

制約の部分は、embeddingのノルムが1以下という制約をいれています。
単純な$l$2正則化にしていないのは、今回の問題設定では原点には特に意味がないから、だそうです。

## 実験

### データセット

* CiteULike 
* BookCX 
* Flickr 
* Medium 
* MovieLens20M 
* EchoNest

### 比較手法

item featureなし(これらとCMLを比較)

* Weighted Regularized Matrix Factorization (WRMF)
* Bayesian Personalized Ranking (BPR)
* Weighted Approximate-Rank Pairwise (WARP)

item featureあり(これらとCML+Fを比較)

* Factorization Machine (FM) 
* Visual BPR (VBPR) (参考: <a href="https://www.smartbowwow.com/2019/09/vbpr-visual-bayesian-personalized.html">【論文紹介】VBPR: Visual Bayesian Personalized Ranking from Implicit Feedback (AAAI2016)</a>)
* Collaborative Deep Learning (CDL)

### 評価指標

recall@k

### 結果

* 精度向上!
* 近似最近傍探索と組み合わせると高速!
* 画像の類似度だけでなくuserの好みを反映した表現が獲得できた！

最後のだけ、論文の図(t-SNEで可視化したもの)を見てみると

元のembeddingでも鳥や花、風景といった画像が固まって配置されていますが、それぞれのクラスターは離れています。

一方、CMLによって得られるembeddingでは似た画像がクラスターを作る点は同じで、それぞれのクラスターの配置が変わっています。鳥や花、風景画像のクラスターが近くに配置されていることがわかります。

画像の類似度だけでなく、同じuserが複数種類の画像を好むという情報が伝搬してembeddingが得られていることが見て取れます。

## まとめ

協調フィルタリングとmetric learinigを組み合わせたCMLの論文を読んで紹介しました。

CML関連の研究は最近もちょこちょこ出ているので読んでみようと思います。

最後まで読んでいただきありがとうございました。

otara2020年5月7日 16:19
始めまして。
コメント失礼します。
元論の2.2節で「マハラノビス距離のグローバル最適化は常に実現可能とは限らないが、Weinberger等は～」という文脈があるのですが、これは何を言っているのでしょうか？
お時間ありましたら、ご教授お願い致します。
返信削除
返信
otara2020年5月11日 12:12
度々申し訳ありません。
自分でも考えたのですが、分からなかったのでいくつか質問させていただきます。

①元論2.3.2節で、BPRの問題点として、「低ランクアイテムにペナルティが十分にかからないので、TopK推薦で適切でない」とありますが、低ランクアイテムにペナルティをかけなければならなのは、低ランクのほうが外しやすいからでしょうか？

②元論3.4節で、「次元の呪いを解消するために、単位超球内にすべてのデータポイントをバインドする」とありますが、こうしても依然として単位超球の表面近くにデータが集まるだけなのでは？と思うのですが、どうでしょうか？

③元論3.2節のランク近似の方法は、ある程度納得できたのですが、近似式がガウス記号だとしたら、ランクが被る可能性はないのでしょうか？
また、U固定だとMが０になる可能性はないのでしょうか？

④この論文のモチベーションの原点は、「Implict Feedbackを用いてkNNでTopK推薦をしたい」であっているでしょうか？

長々とすみません。よろしくお願いします。m(__)m
返信削除
返信
otara2020年5月20日 17:04
このコメントは投稿者によって削除されました。
返信削除
返信