2019/06/20 Addressing Trust Bias for Unbiased Learning-to-Rank 筆者・所属機関
Aman Agarwal Cornell University の Ph. D and Google の研究員
Xuanhui Wang
Cheng Li
Mike Bendersky
Marc Najork
ほかはグーグラー
まとめ
どんなもの?
click にノイズがあっても大丈夫なバイアスのない Learning-to-Rank
先行研究と比べてどこがすごい?
既存手法は examination bias (= 視認されたかどうかのバイアス)を扱っていた
提案手法がクリックにもノイズが含まれているということを考慮する
既存手法はクリックされている = 興味がある
技術や手法のキモはどこ?
クリックノイズを position-depend trust bias とする
クリックログからEM アルゴリズムを使って examination bias と trust bias を推定する
どうやって有効だと検証した?
プライベートな3つのデータセットで評価
Gmail
Google Drive
Gmail Expert
課題
クリックがノイズを含まないという現実的でない仮定をおいている
現実では視認されたあとに,関連する文書がクリックされなかったり,無関係な文書がクリックされることもある
検索結果は上にあるほど関連している・下にあるほど関連していないと思い込むバイアスがある(= trust bias)
クリックノイズは位置に依存する
trust bias = position bias の別の形式
trust bias は結果のランダム化を使っても推定できない
(普通の position bias は結果をランダム化することで推定できる)
TrustPBM では従来使われているような IPS な unbias LTR が使えない
貢献
位置に依存したクリックの不完全性とクリックノイズの両方を捉えたクリックモデルである TrustPBM を提案
PBM 用に設計された EM アルゴリズムを TrustPBM に拡張
推定された TrustPBM のパラメータに基づく unbias LTR のための Bayes-IPS 法を提案
大規模なクリックログに対する当社のアプローチを検証
Bayes-IPS 法はベースラインと比較して優れている
Position-Based Model
PBM おさらい
$ \underbrace{{\rm Pr}(C=1|q,d,k)}_{click} = \underbrace{{\rm Pr}(E=1|k)}_{examination} \underbrace{{\rm Pr}(R=1|q,d)}_{relevance} = \theta_k \gamma_{q,d}
Examination は位置 k に依存
Relevance はクエリ q と文書 d に依存
Examination と Relavance なときに,クリックが発生する
Trust Bias
位置に依存した bias
$ {\rm Pr}(\tilde{R}=1|R=1,E=1,k)=\epsilon^{+}_{k}
$ {\rm Pr}(\tilde{R}=1|R=0,E=1,k)=\epsilon^{-}_{k}
関連した文書は $ 1 - \epsilon^+_k でクリックされず,関連しない文書が $ \epsilon^-_k でクリックされる
trust bias は文書によらず,位置 k にのみ依存する
$ Rは真の relevance,$ \tilde{R} は観測された relevance
TrustPBM
Trust bias を用いて $ \tilde{R} =1 となる確率は
$ {\rm Pr}(\tilde{R}=1|E=1, q, d, k) = {\rm Pr}(\tilde{R}=1|R=1, E=1, k) {\rm Pr}(R=1, q, d) + {\rm Pr}(\tilde{R}=1|R=0,E=1,k){\rm Pr}(R=0, q, d) \\ = \epsilon^+_k \gamma_{q,d} + \epsilon^-_k(1-\gamma_{q,d})
より,クリックの確率は
$ {\rm Pr}(C=1|q, d, k) = {\rm Pr}(E=1|k) {\rm Pr}(\tilde{R}=1|E=1, q, d, k) = \theta_k(\epsilon^+_k \gamma_{q,d} + \epsilon^-_k(1-\gamma_{q,d}))
対数尤度を最大化するパラメータ $ (\theta_k, \epsilon^+_k, \epsilon^-_k, \gamma_{q,d}) を EM アルゴリズムで推定
$ \log {\rm Pr}({\mathcal L}) = \sum_{(q,d,k,c) \in {\mathcal L}} c \log \theta_k (\epsilon^+_k \gamma_{q,d} + \epsilon^-_k(1-\gamma_{q,d})) + (1-c) \log(1 - \theta_k (\epsilon^+_k \gamma_{q,d} + \epsilon^-_k (1 - \gamma_{q,d})))
LTR
LTR が最適化したい指標 $ Mを推定したパラメータを使って補正する
$ M = \sum_{(q,d,r) \in L_u} r \cdot f(q, d, \Omega_q)
f は Average Relevance Position(ARP) や Discounted Cumulative Gain(DCG) の最適化したい指標
r は relevance
Unbiased LTR
examination bias$ \theta_kの逆数で重み付けしてあげる
$ M_{IPS} = \sum_{(q,d,k,c) \in L} \frac{c}{\theta_k} f(q,d,\Omega_q) = \sum_{(q,d,k,c=1) \in L} \underbrace{\frac{1}{\theta_k}}_{IPS} f(q, d, \Omega_q)
Bayes-IPS Correction
TrustPBM ではクリックされたものが100%関連したものと言うわけではない
$ {\rm Pr}(R=1|C=1,k) を $ {\rm Pr}(R=1|\tilde{R}=1, E=1, k)で近似
ベイズ則から,$ {\rm Pr}(R=1|\tilde{R}=1, E=1, k) = \frac{\epsilon^+_k}{\epsilon^+_k + \epsilon^-_k}
examination bias と trust bias の2つで補正する
$ M_{Bayes-IPS} = \sum_{(q,d,k,c) \in L} \frac{1}{\theta_k} {\rm Pr}(R=1|\tilde{R}=1, E=1, k) f(q,d,\Omega_q) = \sum_{(q,d,k,c=1) \in L} \underbrace{\frac{1}{\theta_k} \frac{\epsilon^+_k}{\epsilon^+_k + \epsilon^-_k}}_{Bayes-IPS} f(q, d, \Omega_q)
Evaluation
データセット
https://gyazo.com/236914d17467db2bafaec9e8cc6a8687
評価指標
offline
loglikelihood
Mean Reciprocal Rank(MRR)
weighted MRR (IPS で重み付けした MRR)
online
CTR
MRR
結果
loglikelihood
https://gyazo.com/bc3c118191a809149cdabdc4a265cd81
examination bias
TrustPBM は tail の文書も examination する確率が高い
https://gyazo.com/a58676a4db9fff2a93f41cf600e2ddce
trust bias
関連する文書を正しくクリックする確率 >> 関連しない文書を誤ってクリックする確率
関連する文書を正しくクリックする確率 は position に依らない
関連しない文書を誤ってクリックする確率は position によって大きく変化する
https://gyazo.com/557b5b7fe12ee599ba5024b2ff2f10e1
オンラインの結果
各手法で求めた IPS を使って LambdaMART で予測すると PBM よりも TrustPBM の方が MRR・CTR が改善した
信頼区間も PBM より狭い
https://gyazo.com/6736ab010c0a1901a7f947088d0f4941
まとめ
クリックノイズを考慮した unbias な LTR を提案
バニラな PBM よりは良い IPS を得ることができる
所感
ニュース系は入れ替わりの頻度が高いけど,広告はそこそこ長いからバイアスが学習に影響するかも
素の PBM から try したい感
関連しないものをクリックすることはあるんだなぁ...