- 傾向スコアにより，検索エンジンの表示順序バイアスを取り除いて，検索エンジンのクリックログから関連性を学習する手法を提案
論文
1 概要
インタラクティブなシステムでは暗黙的なフィードバック（クリックや滞在時間）は豊富なデータのソースである． 暗黙的なフィードバックは多くのメリットを持つ一方で，暗黙的なフィードバック固有のバイアスのため効率的に使う上での障害になる． 例えば，検索結果のランキングによるポジションバイアスはどのくらい多くのクリック結果が得られるかに強く影響する． だから，直接ランク学習の学習データとして直接クリックデータを使うと最適な解を得られない． このバイアスの問題を乗り越えるために，反事実推論フレームワークを示す． このフレームワークはバイアスの乗ったデータであるにもかかわらず経験リスク最終化によってバイアスのないランク学習のための理論的なバイアスを提供する． このフレームワークを用いて，暗黙的なフィードバックからの分類問題のための傾向スコアにより重みづけをしたランキングSVM(Propensity-weighted ranking SVM)を導出した． そのランキングSVMではクリックモデルが傾向スコア推定器の役割を果たす． 理論的な裏付けの上に，提案手法はバイアスを効率的に扱うことを実験的に示した． また，提案手法はノイズや不正確な傾向スコアモデルに対して頑健であり，効率的にスケールすることを示した． 加えて，利用できる検索エンジンを用いて提案手法が実世界に適用できることを示した． そして，実質的に情報取得のパフォーマンスを改善した．
導入
背景
検索システムのバッチ訓練にはアノテーションされたテストデータが必要だが，ウェブ検索システムにおいて専門家から関連性のアノテーションを得るのは非現実的で不可能である．
ユーザの振る舞いによる暗黙的なフィードバックはたくさんある．
課題 & 関連研究
- クリックされたかされていないかを関連性の正例負例に使うナイーブなアプローチはひどくバイアスが乗ってしまう．特に，表示する順番がユーザのクリックする場所に強く影響する[Joachims et al., 2007]. この表示された位置のバイアスによって一様分布からかけ離れた不完全で歪んだ関連性のサンプルを生み出してしまう．
- クリックされた文章とスキップされた文章の間にあるクリックを好みとして扱うことは正確だとわかっている[Joachims,2002; Joachims et al., 2007]が，表示された順序に対して好きではないという好みを推測できるだけである． これは深刻なバイアスを生み，これらの好みによって鍛えられたアルゴリズムは表示する順序を（本来望ましいものと）逆向きにしがちだ．
- クリックの生成モデル[Chuklin et al. 2015]は同じクエリを複数回必要とするが，これは非現実的だ．
- オンライン学習アルゴリズムのようにランク学習がユーザに提示するものを乱択することを許しs [Raman et al., 2013; Hofmann et al., 2013]，バンディットフィードバックからバッチ学習すること[Swaminathan and Joachims, 2015]で，原則的な方法でクリックのバイアスの問題を克服できる．しかし，訓練データを集めるとき常に検索のとき動的に並び変える必要があるのはランキングの質を下げ，観察データ（ランダムな割付を行ったものは実験データ？）を集めるのに比べてコストが高い．
貢献
上記課題を解決する理論的な原則に基づいていて，経験的に効率的な手法を示す．
- 因果推論の手法から反事実推定の技術[Imbens and Rubin, 2015] を借用し，クエリレベルのサンプリングバイアスを補正すること[Wang et al.,2016]で，バイアスの乗ったフィードバックデータを利用して検索ランキングのパフォーマンスを評価するバイアスのない（ことを証明可能な）推定器を開発する．
- 上記推定器をもとにランク学習のための傾向スコアで重み付けされた経験リスク最小化を提案する．Propensity SVM-Rankという学習法を実装する．
- クリックモデルはクリック結果を傾向スコアの計算のために用いて関連性の評価を必要としないので，クエリーが繰り返し観測される必要はない（課題３）．
- 傾向スコアを求める小さな社会実験を除いて，提案手法はランダム化を必要としない．
2 関連研究
3 FULL-INFO LEARNING TO RANK
ランク学習の問題設定と従来の課題を見る．
- 独立同分布から引かれたクエリ$\mathbf{x}_i\sim P(\mathbf{x})$のサンプル$\mathbf{X}$が与えられているとする．
- すべてのドキュメント$y$に対する関連性$rel(\mathbf{x},y)$は既知であると仮定する（関連性が全て既知だと仮定されているのでFull−Info設定という）．
- クエリ$\mathbf{x}$に対する任意のランキング$\mathbf{y}$の損失(e.g. DCG) $\ell(\mathbf{y}|\mathbf{x})$も計算できる．
- クエリ分布に対して期待値を取ることで，ランキング$S(\mathbf{x})$を返すランキングシステム$S$のリスクを$$R(S)=\int\Delta(S(\mathbf{x})|\mathbf{x})dP(\mathbf{x})\tag{1}$$ を定義できる．
- 経験リスクは$$\hat{R}(S)=\frac{1}{|\mathbf{X}|}\sum_{x_i\in\mathbf{X}}\Delta(S(\mathbf{x}_i)|\mathbf{x}_i)$$
- 経験リスク最小化により$$\hat{X}=\arg\min_{S\in\mathcal{S}}\left\{\hat{R}(S)\right\}$$を取得する．
２つの課題がある．
- すべてのドキュメントにラベル付を行うのは不可能であり， pooling technique(?)[Sparck-Jones and van Rijsbergen, 1975]はバイアスを導入してしまう．
- 専門家の判断$rel(\mathbf{x},y)$は同じクエリの根底にあるすべての意図について集約されている必要がある．また，クエリの分布を適切に予想する判断によって適切な関連性$rel(\mathbf{x},y)$を割り当てることは困難だ．
4 PARTIAL-INFO LEARNING TO RANK
-
暗黙的フィードバックから学習することは上記のFull−Infoのランク学習設定の課題を克服できうる．
-
ユーザの特定の文脈や必要な情報に従う関連性の判断人基づきユーザが行動するので，ユーザのシグナルを利用することでユーザの意図を反映できるからだ．
-
クエリ$\mathbf{x}_i$に対するユーザ固有の関連性$y$を$r_i(\mathbf{y})$と記す．
-
しかし，暗黙的なフィードバックを用いたとき観測されなかったフィードバックの問題はpooling settingの問題よりずっと大きい．
-
特に表示順序によるバイアスによって暗黙的なバイアスは歪められ，非ランダムに欠損している[Little and Rubin, 2002].
-
我々は[Schnabel et al., 2016]と似た以下の反事実モデルを採用する
-
関連性を$r_i(y)\in\{0,1\}$とし，関心のパフォーマンスを関連性のランキングの和$$\Delta(\mathbf{y}|\mathbf{x}_i,t_i)=\sum_{y\in\mathbf{y}}rank(y|\mathbf{y})\cdot r_i(y)\tag{2}$$によって測るとする．
-
式１の類推からシステムのリスクを$$R(S)=\int\Delta(S(\mathbf{x}|\mathbf{x},r))dP(\mathbf{x},r)\tag{3}$$ と定義する．
-
提案する反事実モデルでは各クエリ$(\mathbf{x}_i,r_i)\sim P(\mathbf{x},r)$に対して，真の関連性ベクトル$r_i$が存在すると考える．
-
関連性のシグナル（クリック等）は表示されたランキング$\overline{\mathbf{y}}_i$のもとで，上位のもののほうが下位のものよりも観測されやすい．
-
明らかになった関連性を指し示す0/1のベクトルを$o_i\sim P(o_i|\mathbf{x}_i,\overline{\mathbf{y}_i},r_i)$と記す．
-
各$o_i$の要素について，$Q(o_i(y)=1|\mathbf{x}_i,\overline{\mathbf{y}_i},r_i)$はクエリ$\mathbf{x}$に対して結果$y$の関連性$r_i(y)$を観測したことの周辺確率を表している．
-
この観測確率値を観測の傾向スコアと呼ぶ
-
この反事実モデルの設定を用いて新しいランキング$\mathbf{y}$に対しての$\Delta(\mathbf{y}|\mathbf{x}_i,r_i)$のバイアスのない推定量$$\hat{\Delta}_{IPS}(\mathbf{y}|\mathbf{x}_i,\overline{\mathbf{y}}_i,o_i) = \sum_{y:o_i(y)=1}\frac{rank(y|\mathbf{y})\cdot r_i(y)}{Q(o_i(y) = 1|\mathbf{x}_i,\overline{\mathbf{y}}_i,r_i)} = \sum_{y:o_i(y)=1\land r_i(y)=1}\frac{rank(y|\mathbf{y})}{Q(o_i(y) = 1|\mathbf{x}_i,\overline{\mathbf{y}}_i,r_i)}$$をinverse propensity score (IPS) [Horvitz and Thompson, 1952; Rosenbaum and Rubin, 1983; Imbens and Rubin, 2015]を用いて得る．
-
すべての$r(y)=1$である$y$に対して（関連のない$y$については必要でない），$Q(o_i(y) = 1|\mathbf{x}_i,\overline{\mathbf{y}}_i,r_i)>0$が成り立つならば，任意の$\mathbf{y}$に対して，$\hat{\Delta}_{IPS}(\mathbf{y}|\mathbf{x}_i,\overline{\mathbf{y}}_i,o_i)$は$\Delta(\mathbf{y}|\mathbf{x}_i,r_i)$のバイアスのない推定量である． $$ \mathbb{E}_{o_i}[\hat{\Delta}_{IPS}(\mathbf{y}|\mathbf{x}_i,\overline{\mathbf{y}}_i,o_i)]=\mathbb{E}\left[\sum_{y:o_i(y)=1}\frac{rank(y|\mathbf{y})\cdot r_i(y)}{Q(o_i(y)=1|\mathbf{x}_i,\overline{\mathbf{y}}_i,r_i)}\right]\\\
=\sum_{y\in\mathbf{y}}\mathbb{E}_{o_i}\left[\frac{o_i(y)\cdot rank(y|\mathbf{y})\cdot r_i(y)}{Q(o_i(y)=1|\mathbf{x}_i,\overline{\mathbf{y}}_i,r_i)}\right] \\\
=\sum_{y\in\mathbf{y}}\frac{Q(o_i(y)=1|\mathbf{x}_i,\overline{\mathbf{y}}_i,r_i)\cdot rank(y|\mathbf{y})\cdot r_i(y)}{Q(o_i(y)=1|\mathbf{x}_i,\overline{\mathbf{y}}_i,r_i)}\\\
=\sum_{y\in\mathbf{y}}rank(y|\mathbf{y})r_i(y)\\\
=\Delta(\mathbf{y}|\mathbf{x}_i,r_i) $$ -
$\hat{\Delta}_{IPS}$は推定に$o_i(y)=1\land r_i(y)=1$（クリックされたデータ等）だけが貢献する．
-
他の値は観測されているので，あとは傾向スコア$Q(o_i(y) = |\mathbf{x}_i,\overline{\mathbf{y}}_i,r_i)$を推定できれば良い（つまり，他の交絡因子はない[Imbens and Rubin, 2015]）．
-
システムの経験リスクはクエリについて平均を取ったIPS推定量となる$$\hat{R}_{IPS}(S)=\frac{1}{N}\sum_{i=1}^N\sum_{y:o_i(y)=1\land r_i(y)=1}\frac{rank(y|S(\mathbf{x}_i))}{Q(o_i(y)=1|\mathbf{x}_i,\overline{\mathbf{y}}_i,r_i)}\tag{4}$$
-
IPS推定量をクエリについて平均を取った経験リスクはバイアスが乗っていないので期待値を取ればリスクに一致するので，十分なデータがあれば$S$の中で最適なシステムが学習できる
5 FEEDBACK PROPENSITY MODELS
傾向スコアの求め方について具体例を示す．
5.1 Position-Based Propensity Model
- 観測したクリックの傾向を導くためにクリック傾向モデルとして用いる．
- 検索エンジンのログから検索クエリ$\mathbf{x}_i$，表示されたランキング$\overline{\mathbf{y}}_i$，$y$がクリックされたかどうかを表すベクトル$c(y_i)\in\{0,1\}$が得られる．
- ユーザが$y$を吟味したかを表す$e_i(y)$とし，吟味モデル$$P(e_i(y)=1|rank(y|\overline{\mathbf{y}}))\cdot P(c_i(y)=1|r_i(y),e_i(y)=1)$$を考える．
- 吟味モデルではユーザが吟味するかは$\overline{\mathbf{y}}$の中の$y$のランクのみに依存する（傾向スコアは$p_{rank}(y|\overline{\mathbf{y}})$）．
- まず，簡単なクリックのノイズがないモデルを考える．ノイズフリーモデルでは，「クリック＝関連があるかつ吟味した」が成り立っている($c_i(y)=1 \iff r_i(y)=1 \land e_(y)=1$)．
- よってアンバイアスな経験リスクは$$R_{IPS}(S)=\frac{1}{n}\sum_{i=1}^n\sum_{y:c_i(y)=1}\frac{rank(y|S(\mathbf{x}_i))}{p_{rank}(y|\overline{\mathbf{y}})}\tag{5}$$
5.2 Incorporating Click Noise
- 次に，クリックの生成分布にノイズが乗っている設定を考える．$1\ge\epsilon_+>\epsilon_-\ge0$ $$P(c_i(y)=1|r_i(y)=1, e_i(y)=1)=\epsilon_+,\\\ P(c_i(y)=1|r_i(y)=0, e_i(y)=1)=\epsilon_-$$
- これは関連するものをユーザがクリックする確率が$\epsilon_+$であり，関連しないものを誤ってクリックしてしまう確率が$\epsilon_-$であることを表している
- これにより正しい$r_i(y)$でなくノイズの乗った$\tilde{r}_i(y)$になる．
- このとき，経験リスクとリスクの大小関係が一致する．
$$
\mathbb{E}[\hat{R}_{IPS}(S_1)]>\mathbb{E}[\hat{R}_{IPS}(S_2)]\\\
\iff \mathbb{E}_{\mathbf{x},r,\hat{\mathbf{y}}}\left[ \mathbb{E}_o\mathbb{E}_{c|o}\left[ \sum_{y:c(y)=1}\frac{rank(y|S_1(\mathbf{x}))-rank(y|S_2(\mathbf{x}))}{p_{rank}(y|\mathbf{\hat{y}})}\right]\right]>0\\\
\iff\mathbb{E}_{\mathbf{x},r}\left[ \sum_{y}P(c(y)=1|o(y)=1,r(y))\delta rank(y|\mathbf{x})\right]>0 \\\
\iff \mathbb{E}_{\mathbf{x},r}\left[ \sum_{y}(\epsilon_+r(y)+\epsilon_-(1-r(y)))\cdot\delta rank(y|\mathbf{x})\right]>0 \\\
\iff \mathbb{E}_{\mathbf{x},r}\left[ \sum_{y}((\epsilon_+-\epsilon_-)\cdot r(y)+\epsilon_-)\cdot\delta rank(y|\mathbf{x})\right]>0 \\\
\iff \mathbb{E}_{\mathbf{x},r}\left[ \sum_{y}(\epsilon_+-\epsilon_-)\cdot r(y)\cdot\delta rank(y|\mathbf{x})\right]>0 \\\
\iff \mathbb{E}_{\mathbf{x},r}\left[ \sum_{y}r(y)\cdot\delta rank(y|\mathbf{x})\right]>0 \\\
\iff R(S_1) > R(S_2) $$ ここで，$\delta rank(y|\mathbf{x})=rank(y|S_1(\mathbf{x}))-rank(y|S_2(\mathbf{x}))$，$\epsilon_-\sum_{y\in\mathbf{\hat{y}}}\delta rank(y|\mathbf{x})=0$である． - 上記より経験リスクとリスクの一致性があるので最適解を得られる．
5.3 Propensity Estimation
最後のステップとして，$p_r$の推定法を考える．
- 単純な方法はランダム化（この場合，$p_r$を推定するためにユーザに対してランダムに並び替えた検索結果を見せる）だが，コストが高い．
- そこで，ランク$r$と「ランドマーク」となる$k$番目のランクと入れ替える． $$ P(c_i(y')=1|no-swap)=p_k\cdot P(c_i(y')=1|e_i(y')=1)\\\ P(c_i(y')=1|swap-k-and-r)=p_r\cdot P(c_i(y')=1|e_i(y')=1) $$
- 式５の$p_r$は係数に定数がかかっていても経験リスクの大小関係に変化はないので，このスワップによる介入により推定された確率を傾向スコアとして用いることができる．
5.4 Alternative Feedback Propensity Models
- この手法は様々なバイアスに適用できる (e.g.trust bias, saliency biases)
- この手法は２値分類だけでなく回帰でも使える．
6. PROPENSITY-WEIGHTED SVM-RANK
7. EMPIRICAL EVALUATION
7.1 Synthetic Data Experiments
- 傾向スコアとして$$Q(o(y)=1|\mathbf{x},y,r)=p_{rank}(y|\overline{\mathbf{y}})=\left(\frac{1}{rank(y|\overline{\mathbf{y}})}\right)^\eta$$
7.2 How does ranking performance scale with training set size?
How much presentation bias can be tolerated?
7.4 How robust are the methods to click noise?
7.5 How robust is Propensity SVM-Rank to misspecified propensities?
7.6 Real-World Experiment
Arxiv Full-Text Search http://search.arxiv.org:8081/で比較を行う．
