因果推論で検索システムを問い直す(1)

はじめに

ランキング学習のシリーズ記事の第一弾です.

検索システムで達成したいのは, あるqueryに対してよりrelevantなdocumentを上位に提示することです. queryとdocumentのペアに対して, relevanceが大きければ大きいほど, 大きいスコアをつけるような関数を学習することができれば, 効果的にdocumentを並べることができるでしょう. このような関数を学習するためのアルゴリズムがRanking SVMやLambdaMARTなどのランキングアルゴリズムです.

これらのランキングアルゴリズムは, 当然ながら教師ラベルとしてrelevanceを必要とします. 推薦システム的に言えばexplicit feedbackを必要とします. しかし, 学習のたびにannotationするのは高コストなので, clickというimplict feedbackからどうにかスコアリング関数を学習したいというお決まりの動機が湧き上がります. 本記事では, 因果推論で使われる手法を用いてclick情報からrelevance情報を抜き出しつつスコアリング関数を学習する研究を紹介します.

Position-Based Model (PBM)

さて, 現実的には先に定義した $\mathcal{L}_{U}$ のようなexplicit feedbackに基づくデータは得られないはずです. よって, ここからはより現実的なimplicit feedback (click情報) に基づいたデータ集合 $\mathcal{L}=\{(q, d, k, c) \}$ を用いた損失関数の設計方法を考えます. ここで, $k$ は $q$ に対して $d$ を提示した時のpositionを表し, $c$ はその時にclickが発生したか否かを表します.

さて, ナイーブに考えると既存のアルゴリズムを用いるために, 次のようなrelevanceをclickに入れ替えただけの損失関数を用いることが選択肢の一つとして思いつきます.

$\begin{aligned} \hat{M}_{naive}=\sum_{(q, d, k, c) \in \mathcal{L}} c \cdot f\left(q, d, \Omega_{q}\right) \end{aligned}$

前章で定義した損失関数 $M$ におけるrelevanceをclickに入れ替えただけです. しかし, このようなNaive損失をランキングアルゴリズムで最適化してもrelevanceについて最適なランキングを出力するスコアリング関数を得ることはできません. この事実を, 最も単純なclick生成モデルの一つであるPosition-Based Model (PBM)を引き合いに出して説明します.

PBMでは, clickとrelevanceの間に次のような関係性を仮定します.

$\begin{aligned} (1) \quad & C =E \cdot R \\ \\ (2) \quad & \underbrace{ \mathbb{P}(C=1 | q, d, k)}_{Click} =\underbrace{ \mathbb{P}(E=1 | k)}_{Examination} \cdot \underbrace{ \mathbb{P}(R=1 | q, d)}_{Relevance} = \theta_{k} \cdot \gamma_{q, d} \end{aligned}$

ここで, $E$ はexaminationを表す2値確率変数です. このモデル化により, 私たちは次の3つの仮定を置いたことになります.

Queryとdocumentがrelevantかつexaminedのときにのみ, またその時は必ずclickが発生
Relevanceはqueryとdocumentのみに依存し, positionには依存しない
Examinationはpositionのみに依存し, queryとdocumentには依存しない

非常にきつい仮定のように思う一方で, ある程度現実を反映しているかつ単純であるがゆえに思考の整理を助けるモデル化だと思います. このモデル化によって起こる事象を視覚的に説明したのが次の図になります.

f:id:usaito:20190521051747p:plain

この例によると, 1と2番目に提示されたdocumentはexamineされているので, clickはすなわちrelevanceを表しています. 一方で, 9と10番目に提示されたdocumentはもはやexamineされないので, clickはrelevanceを意味しません. つまり, clickされていなくてもrelevantなqueryとdocumentのペアは存在するはずで, 先ほどのナイーブな損失の設計ではそのようなペアの存在を無視してしまうのです.

(この状況ではclickしなかったとしてもそれはirrelevanceを意味しないので, まさにimplicit feedbackといっていい状況でしょう.)

Inverse Propensity Weighting (IPW)

さて, PBMに基づいた議論によりNaive損失を最適化していても, 私たちが本当に得たいスコアリング関数を得ることはできないことがわかりました. しかし, 因果推論の文脈で多用されるInverse Propensity Weighting (IPW)と呼ばれる方法で損失関数を補正することで, 使用可能なデータから真の損失関数をよりよく近似することが可能になります.

IPWに基づいた損失関数は次のように定義されます.

$\begin{aligned} \hat{M}_{I P W} &=\sum_{(q, d, k, c) \in \mathcal{L}} \frac{c}{\theta_{k}} \cdot f\left(q, d, \Omega_{q}\right) =\sum_{(q, d, k, c=1) \in \mathcal{L}} \frac{1}{\theta_{k}} \cdot f\left(q, d, \Omega_{q}\right) \end{aligned}$

つまり, 各データに対する局所損失をそのデータのexamination parameter ( $\theta_k$ )の逆数で重み付けすることで得られる損失関数のことです. また, 損失の最後の表現を見ると, $c=1$ についてsummationを取っているためimplict feedbackに基づくデータ集合から計算可能であることがわかります. さて, IPWに基づいた損失関数 ( $\hat{M}_{IPW}$ )は次のように真の損失に対してunbiasedであることが示されます.

$\begin{aligned} \mathbb{E}\left[ \hat{M}_{I P W}\right] &=\sum_{(q, d, k, c) \in \mathcal{L}} \frac{\mathbb{E} [C ]}{\theta_{k}} \cdot f\left(q, d, \Omega_{q}\right) \\ &=\sum_{(q, d, k, c) \in \mathcal{L}} \frac{\theta_{k} \cdot \gamma_{q, d}}{\theta_{k}} \cdot f\left(q, d, \Omega_{q}\right) \\ &=\sum_{(q, d, k, c) \in \mathcal{L}} \gamma_{q, d} \cdot f\left(q, d, \Omega_{q}\right) \\ &=\sum_{(q, d, k, c) \in \mathcal{L}} \mathbb{P}(R=1 | q, d) \cdot f\left(q, d, \Omega_{q}\right) = \mathbb{E}_{R} \left[ M \right] \end{aligned}$

よって, IPW損失は少なくともbiasの意味でナイーブな損失を用いるよりも真の損失をよく近似するということがわかります.

補足
試しに, Naive損失の期待値を取ってみると,

$\begin{aligned} \mathbb{E}\left[ \hat{M}_{naive}\right] &=\sum_{(q, d, k, c) \in \mathcal{L}} \mathbb{E} [C ] \cdot f\left(q, d, \Omega_{q}\right) \\ &=\sum_{(q, d, k, c) \in \mathcal{L}} \theta_{k} \cdot \gamma_{q, d} \cdot f\left(q, d, \Omega_{q}\right) \\ &=\sum_{(q, d, k, c) \in \mathcal{L}} \; \underbrace{ \mathbb{P}(E=1 | k)}_{(a)} \cdot \mathbb{P}(R=1 | q, d) \cdot f\left(q, d, \Omega_{q}\right) \end{aligned}$

ここで, (a)の部分は過去のデータのexamination parameterでrelevance最適化を考える上では不要な重みと言えます. そして, この重みは過去のランキング方策に依存します. なぜなら, examinaiton parameterはdocumentの提示positionのみに依存し, positionはデータが集められたときに走っていたランキング方策によって決められているからです. したがって, Naive損失を用いることはすなわち暗黙のうちに過去のランキング方策に似せるような重みを含んだ損失を最適化していることになります.

Examination Parameterの推定方法

前章では, IPW損失を用いることでNaive損失よりも良い損失関数を設計できることを示しました. しかし, IPW損失を計算するためには, $\theta_k$ が必要です. そして, このパラメータは残念ながら未知です*2. よって, データから推定する必要があります. 本記事では一番率直な方法として, Result Randomizationと呼ばれる方法を紹介します.

ここで, $\mathcal{R}_k$ を上位N番目までの提示結果をランダムにしたときに得られた $k (\leqq N)$ 番目のpositionのqueryとdocumentの集合とします. このとき,

$\begin{aligned} \mathbb{E} \left[ C \, | \, k \right] &=\int_{q, d \in \mathcal{R}_{k}} \mathbb{E} \left[ C | q, d, k \right] \, P(q, d) \\ &=\int_{q, d \in \mathcal{R}_{k}} \theta_{k} \cdot \gamma_{q, d} \, P(q, d) \\ &=\theta_{k} \cdot \int_{q, d \in \mathcal{R}_{k}} \gamma_{q, d} \, P(q, d) \\ & \propto \theta_{k} \end{aligned}$

したがって, randomizationによって得られたデータにおいてk番目のpositionのclick確率はexamination確率に比例します. よって, IPW損失を計算する前段でResult Randomizationによって得られたデータのclick確率からexamination parameterの比がわかるのでそれを重みづけに使用すれば良いということになります.

補足
とは言え, Result Randomizationなんかできないよ, という方がほとんどだと思います. この点に関しては,

近日中に, Result Randomizationを経ていないデータからexamination parameterを推定する方法について記事を書く予定です.
何もやらないよりも, 例えば過去のデータにおいてclickが発生したポジションの逆数でNaive損失を補正するだけでも結果が変わってくると思います. 過去のランキング方策が提示したポジションを保存しましょう！

実験結果

補正がうまくいった結果の例を一つ掲載しておきます. 詳しくは[Joachims et al. (2017)]をお読みください. WSDM2017のBest Paper Awardを受賞した論文です. この論文では, PBMに従う人工データを生成し, Naive損失とIPW損失をそれぞれRanking SVMで最適化したときに得られたスコアリング関数の性能をテストデータにおけるARPで評価しました. 結果は次の通りです.

f:id:usaito:20190521050153p:plain — [Joachims et al. (2017)]のFigure 2

横軸が大きな値をとるほど, Positionごとのexamination確率の変化が激しくなっています. 赤線がIPWによる補正を用いた時のARPですので, 特にexamination確率の変化が激しいときにNaive損失を用いたbaselineを大きく上回っていることがわかります. 実験的にもIPWによる補正は効果的であることがわかる例となっています.

まとめ

本記事では, 因果推論的なアプローチでclickしか得られていないimplicit feedbackデータからrelevanceに対して最適化されたスコアリング関数を得るための損失を設計する方法について書きました. 記事中にも書きましたが, 近日中に補正に必要なexaminaiton parameterをデータから推定する方法についての記事を書こうと思っています. また, 記事中に何か変なことを書いていたらご指摘いただけると幸いです.

参考

[Joachims et al. (2017)]: Thorsten Joachims, Adith Swaminathan, and Tobias Schnabel. 2017. Unbiased learning-to-rank with biased feedback. In Proceedings of the 10th ACM International Conference on Web Search and Data Mining (WSDM ’17).
[Wang et al. (2018)]: Xuanhui Wang, Nadav Golbandi, Michael Bendersky, Donald Metzler, and Marc Najork. 2018. Position Bias Estimation for Unbiased Learning to Rank in Personal Search. In Proceedings of the 11th ACM International Conference on Web Search and Data Mining (WSDM ’18).
[Agarwal et al. (2019)]: Aman Agarwal, Xuanhui Wang, Cheng Li, Mike Bendersky, and Marc Najork. 2019. Addressing Trust Bias for Unbiased Learning-to-Rank. In Proceedings of the 2019 World Wide Web Conference (WWW ’19)

*1:全てのqueryとdocumentのペアについてrelevanceが得られている状況

*2:あるポジションに提示したdocumentは何%の確率でexamineされるかを知ることはできません, よね.