Contrastive Learning for Debiased Candidate Generation in Large-Scale Recommender Systems
by DAMO Academy, Alibaba group
Authors: Chang Zhou, Jianxin Ma, Jianwei Zhang, Jingren Zhou, Hongxia Yang
key words: contrastive learning, cadidate generation, recommender system
選ぶ理由:Contrastive learningに興味があり、candidate generationにどう応用するのかを知りたい
TL; DR
従来のレコメンドシステムのCandidate generationタスクのbias問題を取り扱っている
特に最尤推定(MLE)は観測したサンプルのSelection biasを強化していく
論理上提案手法がInverse propensity weightingとの関係
IPWは観測したサンプルのSelection biasと一部のデータポイントがトリートメントを得やすいTreatment biasを考慮した手法である
とても大きいサイズの候補セットからbiasを抑えて公平的・効率的なContrastive learning手法CLRecを提案した
さらに多様なbiasを考慮したmulti-CLRecを提案した
Taobaoにデプロイし、4ヶ月以上にABテストを行い、マタイ効果を抑えた
Motivation
Youtubeの論文以来、百万や億単位のCorpusから関連する数十件のアイテムを選出することが、推薦システムの重要課題である(Deep candidate generation) DCG問題に対しての一番使われているのが最尤推定(Maximum likelihood estimation)であるが、Softmaxを計算する時百万〜数十億以上のアイテムがあり、難しくなる
https://gyazo.com/19d858945d202f0d7a5311df309be404
$ xはあるユーザが予測しようとする時点$ t前でのクリックシーケンス、はその時点のアイテム$ yへのクリック
$ \phi_\theta(x,y)は$ \langle f_\theta(x), g_\theta(y) \rangleである。
$ f_\theta(x)はユーザ行動のエンコーダであり、$ g_\theta(y)はアイテムのエンコーダである
$ \phi_\theta(x,y)は内積、あるいはcosine similarity
MLEのゴールは観測したテキストに忠実的にfitしても問題ないが、推薦システムの収集したデータは既存の推薦に依存があり、Popularアイテムに偏っている
最初に観測不足のアイテムが推薦されなくなり、ますますデータが減っていて悪循環になる
推薦の候補セットのサイズは、NLPよりはるかに大きい(100M商品対100k単語)ので、候補セット全体のいい表現を学習するのに難しい
(Contrastive learning はもともと画像系のunsupervised手法であり、同じ画像とAugumented画像がポジティブサンプルとし、他の画像をネガティブサンプルとして学習する)
論理的証明
まずsampled softmaxを紹介します。そしてContrastive learningを紹介し、IPWとの関係を明らかにする
Sampled softmax
https://gyazo.com/33d200715973839ac6065a9206fe5bcd
ここの$ p_n(y|x)は事前定義されたnegative sampling分布である。ここは$ L個のネガティブサンプル$ y_iが選ばれてトレーニングする
$ log_{p_n}(y|x)を減る部分が、式(1)と同じ解に収束することに必要である
大抵の実装は$ p_n(y|x) \approx p_n(y)とし、一つのポジティブサンプルに数千のネガティブサンプルが選ばれる
Contrastive learning
https://gyazo.com/5d2ce38a92f25910f38fbdc82e9cfe1b
上のようなネガティブサンプルを含むcontrastive損失関数を使った
同じく、ネガティブサンプルは事前定義された$ p_n(y|x)から抽出された
Sampled softmaxより$ log_{p_n}(y|x)の部分が消えており、ネガティブサンプリングのバイアスを修正されていない
DeepMindの先行研究によると、もし$ p_n(y|x)をデータセットのアイテム分布$ P_{data}(y)に置き換えると、式(3)が相関情報の下限を最大化している Contrastive learningとExposure bias reduction
上の式(3)がサンプリングに基づいたIPWであることを証明する
Inverse propensity weighting(IPW)の式は以下である
https://gyazo.com/120481cd32450f2f2f4d72120446e7de
$ q(y|x)はpropensity scoreと呼ばれ、impression (exposure) の分布を意味する。つまりトレーニングセットを作る際、ユーザ$ xにアイテム$ yをレコメンドする確率である。
IPWのアイディアはこのpropensity scoreを重みとして用い、ランダムではないexposure biasによって数が少ないサンプルにもっと重みをつける
この損失関数はexposure biasがあってもユーザの好み$ p_\theta(y|x)をキャッチすることが証明できる
本研究はこの定義を証明した:もし$ p_n(y|x)を$ q(y|x)に同じとすると、 式(3)と式(4)はと共に$ p_\theta(y|x)と$ r(y|x)のKL Divergenceを最適解を解いている。$ r(y|x) = \frac{P_{data}(y|x)/q(y|x)}{\Sigma_{y'\in Y}P_{data}(y'|x)/q(y'|x)}、 証明は論文のAppendixへ
ここの$ P_{data}(y|x)はデータの分布、つまりデータセット$ Dで条件$ xの場合$ yの発生頻度
上の定義からみると、Contrastive learningにて$ p_n(y|x)をpropensity scoreを設定すれば、exposure biasを抑える方向に近似できる
CLRecの提案
IPW手法のpropensity score$ q(y|x)はimpression (exposure) の分布であり、トレーニングセットを作る時のシステムがユーザ$ xにアイテム$ yをレコメンドする確率である
実際の推薦システムが様々の要素があり、データもスパースのため、正確な$ q(y|x)を計算することが難しい
本研究では$ q(y|x) \approx q(y)の前提をする。さらに$ q(y)は、現在のシステムの推薦によってアイテム$ yがあるユーザにクリックされる確率$ P_{data}(y)と高度な相関関係を持っている:$ q(y|x) \approx P_{data}(y)
上の定義によると、$ P_{data}(y)からネガティブサンプリングを行う、Contrastive lossがExposure biasを抑えられる
しかし、分散の環境で通信のオーバーヘッドや、Epoch内全てのサンプルが選ばれる保証がない問題もある
故に、キューに基づいたContrastive learningを提案した:
WorkerにFIFOキューを持って、ネガティブサンプルを保存していく
学習したサンプルをネガティブサンプルとしてEnqueueする
さらに、なまのネガティブサンプルより、エンコーディングしたアイテムの特徴$ g_\theta(y)をキャッシュすればトレーニング時間を大幅に減らせる
https://gyazo.com/d42efd11c0deb235e7282405ca6bb208
Multi-CLRecの提案
Taobaoの中、商品アイテムのカテゴリが数万あるため、カテゴリをクラスタリングしてIntentionでまとめたい
$ q(y|x)を$ q(y|user's\ current\ intention\ is\ h)で近似し、学習する
そしてH個のキューを作って、それぞれのIntentionを対応する
全体アーキテクチャ
https://gyazo.com/4bbc8118805c26c1c54455184dd5a210
$ x = \{y_{1:(T-1)}\}はユーザ過去のクリック履歴、$ y_Tは予測しようとする時のground truth
アイテムのEmbeddingは:
https://gyazo.com/f2c0125ec85789f8198c1d74abe1112e
MLP:multi-layer perceptron
ユーザが過去クリックしたアイテム$ y_t \in \{y_t\}_{t=1}^{T-1}の重要度をモデリングし、$ p_tとする:
https://gyazo.com/609d2c7c4fc25e0080d74d3b4a219201
アイテム$ y_tごとのIntention別確率を計算する↓
$ c_tは$ y_tのカテゴリIDのEmbeddingであり、$ \mu_hはトレーニング可能なパラメタである
先行研究に従って$ \rho = 0.07
https://gyazo.com/998b14d7754ea6eed137133cc3b33b20
上の結果をまとめ、ユーザのH個のIntentionベクトル$ \{z_h\}_{h=1}^Hを得られる
$ \beta_hはトレーニング可能のIntentionバイアスを表現するベクトル:
https://gyazo.com/5529d978ef4d0c97555aa1ce4b523a27
しかし、一部のユーザが一部ののIntentionベクトルだけあるので、下のようにユーザの最も興味を持っているIntentionベクトルを選択する。そのベクトルもユーザEmbeddingとして使われる:
https://gyazo.com/d6523929df055d85a2feb151b357b8da
推論の時、H個のIntentionベクトルからtop-Kを選び、アイテムの推薦をする(トレーニング時K=1)
解釈性向上するための損失関数
希望通りにIntentionルーティングのメカニズムが効かせるために、三つのAuxiliary Lossesを導入した
一番目は$ p_{h^+|T} \rarr 1と$ p_{h'|T} \rarr 0\ for\ h'\ \neq\ h^+するためのもの:
https://gyazo.com/e7f9b909db821448fc6eb260c8e87463
二番目は正しいIntentionベクトル$ z_{h^+}をもっとターゲットアイテム$ y_Tと近づくための損失関数:
https://gyazo.com/6818137b399c0bd1e2294ab1d9fb7692
三番目の損失関数は、H個Intentionのバランスを調整し、それぞれほぼ同じ数のアイテムを持つように調整する:
https://gyazo.com/6ef235f1b6f7c00a51142966a6b86f9c
ここの$ E_Bは前のmini batchで計算した期待値
Multi-Queue Contrastive Loss
主な損失関数は以下:
https://gyazo.com/e002c4c21ea2def379b6ab4fd131a038
$ cosはCosine類似度
$ \ddot w_hは式(9)straight-throughで近似した$ h^*:$ \ddot w_h = stop\_gradient(I_{h=h^*}-w_h)+w_h
$ Q_0はメインキューである
$ Q_{h^+}はセカンダリーキューであり、H個がある。それぞれのIntentionに対応する
$ Q_0と$ Q_{h^+}のはネガティブサンプルとして使われる
Enqueueのステップ:
まずポジティブサンプル$ y_Tが $ Q_0にenqueueする
一つのベガティブサンプル $ y^-を $ Q_0からdequeueし、セカンダリーキュー$ Q_{h^-}にenqueueする($ h^- = \argmax_h p_{h^-|y})
セカンダリーキュー$ Q_{h^-} からdequeueしたアイテムを捨てる
実験
Production環境の実験
オフライン実験でCLRecとsampled-softmaxと比較した。より多様性のあるレコメンドできている。Sampled-softmaxがtrainingデータの分布を忠実に再現しているが、CLRecはよりimpされていないアイテムをレコメンドしている
https://gyazo.com/ad7ce00084ba3217b51d30538612ac3c
SamplingメソッドとのCTR比較、CLRecが多様性のレコメンドができて、さらにオンライン実験でより高いCTR得られている
エンコーダは同じもので使われている
https://gyazo.com/dcd4aa3c52bd9d2ec4bd8b1233ebd0bc
オンライン実験でMulti-CLRecがCLRecよりいい精度が出ている
https://gyazo.com/77ca6cd491c498e813f5992210b44488
数ヶ月のオンライン実験で、前のSOTAと比較した結果。多様性のあるレコメンドができているほか、CTRと滞在時間も増えている https://gyazo.com/a6c97c33469c13a8f014f6bdaf14da0b
CLRecの計算効率
CLRecとsampled-softmaxのトレーニング時のthroughput
ネガティブサンプルの特徴をキャッシュしたら効率が上がり、より良い精度までトレーニングできる
https://gyazo.com/ea3d579d3261c6e6aae043c409a58a37
https://gyazo.com/21eb379659bddcaa91df3173a7426320
特徴をキャッシュしたら、より複雑な損失関数を取り込むことができ、制度をさらに改善できる
https://gyazo.com/50f7b10e7e02b91d568fff1f3b510091
公開されるデータセットでの実験結果
HPMNでの実験結果、SOTAのAUC結果になった
https://gyazo.com/e06f526548c8b9215f1f30512fb16f8d
一人のユーザごと10個のアイテムをレコメンドするが、CLRecがsampled-softmaxより多くのアイテムをレコメンドできている
https://gyazo.com/13720b214efc02d4be5c2460b5c5ea67
Sampled-softmaxが忠実にtrainingセットの分布を再現しているが、CLRecの方がよりimpされていないアイテムを推薦している。マタイ効果を抑えている
https://gyazo.com/9b5ce254a247ba81891c81acadd08b5f
個人感想
レコメンドシステムのバイアス問題をまじめに取り扱っている
既存システムのimpされにくいサンプルもちゃんとレコメンドができて、ユーザ滞在時間とCTRも改善したのはすごい
既存レコメンドシステムの大半がMLEベースで作られているので、確かにマタイ効果がよく観測されているように思う。
Contrastive learningが画像系で流行っているが、レコメンドシステムへの応用はまだ早い段階である。もし本当にこのペインポイントを解決できたら流行っていくと思う。他のチーム・企業からの検証と今後の関連研究を追っていていいかも
Gunosyの広告レコメンドが一部に集中している問題があるので、本研究は参考になる