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

はじめに

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

前回の記事ではUnbiased Learning-to-Rankと呼ばれる, clickというimplicit feedbackを用いて relevanceに対して最適なスコアリング関数を学習するための損失関数を設計する方法について議論しました. その中で紹介したのがexamination parameter $\theta_k$ の逆数によって損失を重み付けするInverse Propensity Weighting (IPW)と呼ばれる方法でした.

IPWはclickデータのみから真の損失関数を不偏推定することができるという嬉しさがあった反面, 肝心のexamination parameterの推定方法に関しては Result Randomizationの紹介のみに留まっていました.

本記事では, ユーザー体験を著しく害したり, KPIに大きな打撃をもたらすため実務的にはなかなか行うことができないRandomizaitonではなくて offlineのclickデータからexamination parameterを推定する方法を2つ紹介します.

Unbiased Learning-to-Rankのおさらい

Notationの導入の意味も込めて, 簡単にUnbiased LTRの定式化とIPW損失のおさらいをします. 前回記事を読んでいただいている方は流していただいて大丈夫かと思います.

$\mathcal{L}_{U}=\{(q, d, r) \}$ を各queryとdocumentにrelevance labelが付与されたデータ集合とします. また, あるqueryとデータ集合において共起しているdocumentの集合を $\Omega_{q}=\left\{d |(q, d) \in \mathcal{L}_{U} \right\}$ で表しておきます.

ここで, ランキングアルゴリズムが最小化したい理想的な損失は次の通りでした.

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

ここで, $f$ はランキングに関連する関数で, 例えばARPやDCGが用いられます. しかし, 通常はrelevance labelが得られないので, 代わりにより安価に手に入るclickを用いて損失を設計することを考えます.

Position-Based Modelに基づくとrelevanceとclickの関係はexaminationという変数を媒介する形で次のように表せます.

$\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}$

ここで, 両辺をexamination parameter $\theta_k$ で割ることによって右辺にrelevance parameter $\gamma_{q, d}$ が分離されることを利用して 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}$

IPWに基づいた損失関数 ( $\hat{M}_{IPW}$ )は真の損失に対してunbiasedであることが示されるため, 真の損失の代替として正当性を持つという話をしました.

EM Algorithm

$\theta_{k}$ を推定するための一つ目のアプローチは, $\theta_k$ と $\gamma_{q, d}$ を潜在変数と見てEMアルゴリズムでパラメータを推定するというアプローチです.

Naive EM

まず, パラメータ推定に際して最大化したい対数尤度は次のように表されます.

$\begin{aligned} \log P(\mathcal{L})=\sum_{(q, d, k, c) \in \mathcal{L}} c \log \theta_{k} \gamma_{q, d}+(1-c) \log \left(1-\theta_{k} \gamma_{q, d}\right) \end{aligned}$

$\theta_k \cdot \gamma_{q, d}$ がclick確率を表すというPBMを思い出せば直感的なはずです.

このまま愚直にE-step, M-stepを書き下すと次のようになります.

E-step: その時点までに得られているパラメータを用いてclickが発生する・しない場合のrelevanceとexaminationの条件付き確率を推定します.

$\begin{aligned} & \mathbb{P}(E=1, R=1 | C=1, q, d, k)=1 \\ & \mathbb{P}(E=1, R=0 | C=0, q, d, k)=\frac{\theta_{k}^{(t)}\left(1-\gamma_{q, d}^{(t)}\right)}{1-\theta_{k}^{(t)} \gamma_{q, d}^{(t)}} \\ & \mathbb{P}(E=0, R=1 | C=0, q, d, k)=\frac{\left(1-\theta_{k}^{(t)}\right) \gamma_{q, d}^{(t)}}{1-\theta_{k}^{(t)} \gamma_{q, d}^{(t)}} \\ & \mathbb{P}(E=0, R=0 | C=0, q, d, k) = \frac{\left(1-\theta_{k}^{(t)} \right) \left(1-\gamma_{q, d}^{(t)}\right)}{1-\theta_{k}^{(t)} \gamma_{q, d}^{(t)}} \end{aligned}$

M-step: E-stepで推定された条件付き確率を用いて, パラメータを更新します.

$\begin{aligned} & \theta_{k}^{(t+1)}=\frac{\sum_{c, q, d, k^{\prime}} \mathbb{I}_{k^{\prime}=k} \cdot(c+(1-c) P(E=1 | c, q, d, k))}{\sum_{c, q, d, k^{\prime}} \mathbb{I}_{k^{\prime}=k}} \\ \\ & \gamma_{q, d}^{(t+1)}=\frac{\sum_{c, q^{\prime}, d^{\prime}, k} \mathbb{I}_{q^{\prime}=q, d^{\prime}=d} \cdot(c+(1-c) P(R=1 | c, q, d, k))}{\sum_{c, q^{\prime}, d^{\prime}, k} \mathbb{I}_{q^{\prime}=q, d^{\prime}=d}} \end{aligned}$

とEMの更新式を書き下しましたが, 最後の $\gamma_{q, d}$ の更新式で問題が発生します. この更新は, 同じqueryとdocumentのペアについてのデータが一定数存在しないとうまくいきませんが, データ数の少ないペアが大半で更新はあまりうまくいかないと考えられます. また, プライバシーの問題であるqueryについてどのdocumentをclickしたかの情報が手に入らないこともあるらしいです (論文にそう書いてありました.).

Regression-based EM

この $\gamma_{q, d}$ はqueryとdocumentの組み合わせ分だけ存在し, M-stepでの更新がうまくいかない問題に対し, Wang et al. (2018) はRegression-EMと呼ばれるテクニックでこの問題を解消しました.

Regression-EMは, M-stepでのrelevance parameterの推定を一つの学習器で行ってしまおうというアイデアです. 手順の理解には, 擬似コードを見るのが良いと思います.

f:id:usaito:20190525070334p:plain — [Wang et al. (2018)]のAlgorithm 1

擬似コード中の重要な手順の説明をします.

(1). 学習器 $F(\cdot)$ を初期化
(3). E-step: それまでに得られている $\{ \theta_k \}$ と $\{ \gamma_{q, d} \}$ を用いて条件付きclick確率を推定
(4)-(8). E-stepで得られた条件付き確率を用いてrelevance labelをサンプリングし, relevance推定器の学習用のデータを生成
(9). 一回前の推定結果とcontextをinputとして, サンプリングしたrelevance labelに対してfit
(10)-(11). $\theta_k$ はNaive EMと同じ式で更新, $\gamma_{q, d}$ は予測器の出力によって更新

このようにRegression-based EMでは, M-stepにおけるqueryとdocumentの膨大な組み合わせのパラメータ更新式を一つの学習器(論文では, GBDT)で代替することで解決を図っています. 事実, このRegression-based EMを用いることにより前回紹介したResult Randomizationを用いた時よりも良い検索ランキングを提示できるようになったという実験結果が出ました ([Wang et al. (2018)]).

Dual Learning Algorithm

Examination parameter $\theta_k$ をofflineで推定するもう一つの方法に, Dual Learning Algorithm (DLA)と呼ばれる手法があります. これは, IPWと同じようなアイデアによってExamination parameterの推定のためのunbiasedな損失をclickデータから作れるというアイデアに基づいています.

PBMの仮定のもとで, IPWは次のように両辺を $\theta_k$ で割った形を活用していました.

$\begin{aligned} \frac{\mathbb{P}(C=1 | q, d, k)}{\mathbb{P}(E=1 | k)} = \underbrace{\mathbb{P}(R=1 | q, d)}_{Relevance} \end{aligned}$

[Ai et al. (2018) ]では, これと同じことが両辺を $\gamma_{q, d}$ で割った形にも活用できるよね, というアイデアをIRW (Inverse Relevance Weighting)と名付けました.

$\begin{aligned} \frac{\mathbb{P}(C=1 | q, d, k)}{\mathbb{P}(R=1 | q, d)} = \underbrace{\mathbb{P}(E=1 | k)}_{Examination} \end{aligned}$

この操作により, 右辺にexamination parameterを分離できています. 今, examination推定のための真の損失を次のように設定するとします.

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

しかし, ユーザーがdocumentをexamineしたかどうかなんてデータに残っておらず $e$ (Examinationの実現値) がわからないため, この損失は計算不可能です. ここで, 先のIRWを用いると, clickしたかどうかの情報から, Examination parameter推定のための損失に対する不偏推定量を作ることができます.

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

実際, IPWの時と同様にして,

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

であることから不偏性が確かめられます.

さて, DLAはこの事実を活用して次のlist-wiseな損失関数をもつ2つの関数 $f_{\phi}, \, g_{\psi}$ を学習します.

$\begin{aligned} \hat{M}_{I P W} & =-\sum_{(q, d, k, c=1) \in \mathcal{L}_{U}} \frac{1}{\theta_{k}} \cdot \log \frac{e^{f_{\phi}\left(x_{q, d}\right)}}{\sum_{d' \in \Omega_{q}} e^{f_{\phi}\left(x_{q, d'}\right)}} \\ \hat{M}_{I R W} & =-\sum_{(q, d, k, c=1) \in \mathcal{L}_{U}} \frac{1}{\gamma_{q, d}} \cdot \log \frac{e^{g_{\psi}(k)}}{\sum_{k'} e^{g_{\psi}(k')}} \end{aligned}$

これらの損失を最小化することで, $f_{\phi}, \, g_{\psi}$ をソフトマックス関数に通すことで, 各パラメータを推定するように学習してほしいという気持ちが込められています.

$\begin{aligned} \gamma_{q, d} \approx \frac{e^{f_{\phi}\left(x_{q, d}\right)}}{\sum_{d' \in \Omega_{q}} e^{f_{\phi}\left(x_{q, d'}\right)}}, \; \theta_{k} \approx \frac{e^{g_{\psi}(k)}}{\sum_{k'} e^{g_{\psi}(k')}} \end{aligned}$

したがって, $f_{\phi}, \, g_{\psi}$ はお互いの損失の重み付け部分がお互いに依存する形の損失を持っています ( $f$ の損失は $\theta_k$ に依存しており, $g$ の損失は, $\gamma_{q, d}$ に依存していますね). これを同時に最適化することにより, end-to-endにExamination parameterの推定と検索ランキング提示のためのスコアリング関数を学習することが可能になります. （ただし, かなり初期値依存が激しそうな印象を持っています）

Dual Learning Algorithmについては以前勉強会(MLPRP)で発表させていただきました. その時のスライドを貼っておきます. 擬似コードや実験結果についてはこちらの資料に掲載してあるので, 参考にしていただけたらと思います.

speakerdeck.com

まとめ

今回は, IPWによって損失を補正するために必要なexamination parameterをofflineで推定する方法を紹介しました. Regression EMなどは推定したいパラメータ数が多い別の問題にも応用できそうな気がしています. 次回は, Position-Based Modelをより現実的なモデル化に拡張した研究について紹介しようと思っています.

参考

[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).
[Ai et al. (2018)]: Qingyao Ai, Keping Bi, Cheng Luo, Jiafeng Guo, and W. Bruce Croft. Unbiased learning to rank with unbiased propensity estimation. In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval (SIGIR’18).

*1:たぶん第三弾まである.

Counterfactualを知りたい