【論文紹介】Collaborative Metric Learning (WWW2017) - 1月 09, 2020 こんにちは、ぐぐりら(@guglilac)です。 今回は、協調フィルタリングと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) (参考: 【論文紹介】VBPR: Visual Bayesian Personalized Ranking from Implicit Feedback (AAAI2016)) * Collaborative Deep Learning (CDL) ### 評価指標 recall@k ### 結果 * 精度向上! * 近似最近傍探索と組み合わせると高速! * 画像の類似度だけでなくuserの好みを反映した表現が獲得できた! 最後のだけ、論文の図(t-SNEで可視化したもの)を見てみると 元のembeddingでも鳥や花、風景といった画像が固まって配置されていますが、それぞれのクラスターは離れています。 一方、CMLによって得られるembeddingでは似た画像がクラスターを作る点は同じで、それぞれのクラスターの配置が変わっています。鳥や花、風景画像のクラスターが近くに配置されていることがわかります。 画像の類似度だけでなく、同じuserが複数種類の画像を好むという情報が伝搬してembeddingが得られていることが見て取れます。 ## まとめ 協調フィルタリングとmetric learinigを組み合わせたCMLの論文を読んで紹介しました。 CML関連の研究は最近もちょこちょこ出ているので読んでみようと思います。 最後まで読んでいただきありがとうございました。 この記事をシェアする Twitter Facebook Google+ B!はてブ Pocket Feedly コメント otara2020年5月7日 16:19始めまして。コメント失礼します。元論の2.2節で「マハラノビス距離のグローバル最適化は常に実現可能とは限らないが、Weinberger等は~」という文脈があるのですが、これは何を言っているのでしょうか?お時間ありましたら、ご教授お願い致します。返信削除返信ぐぐりら2020年5月8日 13:54元の最適化問題では(制約が強すぎて)実行可能でない場合があるが、kNN classificationに使うmetricを学習するだけなら、あるデータ点のk近傍だけを同じclassにするだけでよく、最適化問題が扱いやすくなるので、このCMLの論文でも緩和した問題に沿って考える、ということだと認識しています。削除返信返信otara2020年5月8日 15:57ご返答ありがとうございます。理解できました。ちなみに、同じ節に出てくる「target neighbor」は、k近傍と同じ意味でしょうか?削除返信返信ぐぐりら2020年5月9日 14:37そうだと思います。削除返信返信otara2020年5月9日 17:36ありがとうございます。削除返信返信返信otara2020年5月11日 12:12度々申し訳ありません。自分でも考えたのですが、分からなかったのでいくつか質問させていただきます。①元論2.3.2節で、BPRの問題点として、「低ランクアイテムにペナルティが十分にかからないので、TopK推薦で適切でない」とありますが、低ランクアイテムにペナルティをかけなければならなのは、低ランクのほうが外しやすいからでしょうか?②元論3.4節で、「次元の呪いを解消するために、単位超球内にすべてのデータポイントをバインドする」とありますが、こうしても依然として単位超球の表面近くにデータが集まるだけなのでは?と思うのですが、どうでしょうか?③元論3.2節のランク近似の方法は、ある程度納得できたのですが、近似式がガウス記号だとしたら、ランクが被る可能性はないのでしょうか?また、U固定だとMが0になる可能性はないのでしょうか?④この論文のモチベーションの原点は、「Implict Feedbackを用いてkNNでTopK推薦をしたい」であっているでしょうか?長々とすみません。よろしくお願いします。m(__)m返信削除返信ぐぐりら2020年5月11日 14:29コメントありがとうございます。以下、自分の解釈ですので正しい保証はありません。参考程度にお願いいたします。1 について本来高ランクに予測すべきものを低ランクと予測した場合により大きくペナルティをかけた方が自然、という解釈でした。2について僕もそう思います。ノルムで割ってクリップするというのは原始的で本当にうまくいくのかなあと読んだときは疑問でした。3についてランクは被る可能性歯あると思います。重みを作るためなので大まかな大小がつかめればいいのかなと思っています。Mが0になることはもちろんあると思います。wの定義を見るとlogの中身に1足されているのはrankが0になることを考慮したものでしょう。4についてそう思います。削除返信返信otara2020年5月11日 15:10ありがとうございます。大変参考になりました。削除返信返信返信otara2020年5月20日 17:04このコメントは投稿者によって削除されました。返信削除返信返信コメントを追加もっと読み込む... コメントを投稿
始めまして。
返信削除コメント失礼します。
元論の2.2節で「マハラノビス距離のグローバル最適化は常に実現可能とは限らないが、Weinberger等は~」という文脈があるのですが、これは何を言っているのでしょうか?
お時間ありましたら、ご教授お願い致します。
元の最適化問題では(制約が強すぎて)実行可能でない場合があるが、kNN classificationに使うmetricを学習するだけなら、あるデータ点のk近傍だけを同じclassにするだけでよく、最適化問題が扱いやすくなるので、このCMLの論文でも緩和した問題に沿って考える、ということだと認識しています。
削除ご返答ありがとうございます。
削除理解できました。
ちなみに、同じ節に出てくる「target neighbor」は、k近傍と同じ意味でしょうか?
そうだと思います。
削除ありがとうございます。
削除度々申し訳ありません。
返信削除自分でも考えたのですが、分からなかったのでいくつか質問させていただきます。
①元論2.3.2節で、BPRの問題点として、「低ランクアイテムにペナルティが十分にかからないので、TopK推薦で適切でない」とありますが、低ランクアイテムにペナルティをかけなければならなのは、低ランクのほうが外しやすいからでしょうか?
②元論3.4節で、「次元の呪いを解消するために、単位超球内にすべてのデータポイントをバインドする」とありますが、こうしても依然として単位超球の表面近くにデータが集まるだけなのでは?と思うのですが、どうでしょうか?
③元論3.2節のランク近似の方法は、ある程度納得できたのですが、近似式がガウス記号だとしたら、ランクが被る可能性はないのでしょうか?
また、U固定だとMが0になる可能性はないのでしょうか?
④この論文のモチベーションの原点は、「Implict Feedbackを用いてkNNでTopK推薦をしたい」であっているでしょうか?
長々とすみません。よろしくお願いします。m(__)m
コメントありがとうございます。
削除以下、自分の解釈ですので正しい保証はありません。参考程度にお願いいたします。
1 について
本来高ランクに予測すべきものを低ランクと予測した場合により大きくペナルティをかけた方が自然、という解釈でした。
2について
僕もそう思います。ノルムで割ってクリップするというのは原始的で本当にうまくいくのかなあと読んだときは疑問でした。
3について
ランクは被る可能性歯あると思います。重みを作るためなので大まかな大小がつかめればいいのかなと思っています。Mが0になることはもちろんあると思います。wの定義を見るとlogの中身に1足されているのはrankが0になることを考慮したものでしょう。
4について
そう思います。
ありがとうございます。
削除大変参考になりました。
このコメントは投稿者によって削除されました。
返信削除