Unbiased Ad Click Prediction for Position-aware Advertising Systems
https://gyazo.com/363a80917518f87320ac0f36fd01f57b
最近面白かった発表
1. どんなもの
表示位置の影響がある広告システムにおける様々なバイアスを特定し、それらを取り除くようなクリック予測モデルを構築する
2. 先行研究と比べてどこがすごいの?
一般的なシステム、position-independent/aware、positional/non-positional approach について説明する。
https://gyazo.com/dfa9e10585348249d0237c5481bc5b55
前提: 一般的な広告システム
システムはリクエスト$ iにおける広告$ jを位置$ kに表示する
その時にクリックされる確率は $ P_{ijk}
広告$ jに対するbid $ {\rm bid}_jを元に、システムは売上が最大になるように広告を選んで表示したい
$ P_{ijk} \times {\rm bid}_j
各リクエスト $ iに対して、期待収益が最大になるようにシステムは$ K個の表示位置を選びながら表示する
$ S_i は発生するイベント列 $ (i, j_1, 1), \cdots, (i, j_K, K)
$ \max_{S_i} \sum_{(i, j, k) \in S_i} P_{ijk} \times {\rm bid}_j
前提: Position-independent と Position-aware
Position-independent
広告の表示位置によって結果が変わらないモデル・システム
研究論文で採用されている設定
positionは考慮されていない
$ P_{ijk} = {\rm Pr}({\rm click} = 1|{\rm request} = i, {\rm ad} = j)
Position-aware
広告の表示位置によって結果が変わるモデル・システム
実世界のアプリケーションの設定
positionを考慮している
おそらく全人類みなこれを正確に予測したい、「真の」クリック確率
以後常にこれをいい感じに予測することを考えていきます
$ P_{ijk} = {\rm Pr}({\rm click} = 1 | {\rm request} = i, {\rm ad} = j, {\rm position} = k)
前提: Positional approach と Non-positional approach
Position-awareなシステムでは大きく2つのアプローチによるモデルの学習が行われている:
Positional approach
広告が表示された位置情報を入力に加えてCTRモデルを学習させる
Non-positional approach
positionに独立な項 $ \tilde{P}_{ij}とクリック確率を考慮する項を分けてCTRモデルを学習させる
本研究の貢献点
position-awareなシステムにおけるセレクションバイアスを調査
2つのセレクションバイアスがあることを指摘
non-positionalなアプローチによるCTRモデルはさらなるバイアスを導入していることを指摘
位置 $ kに不変な$ \tilde{P}_{ij}ではなく位置 $ kにおける$ P_{ijk}だけを使って評価してしまっている点を指摘
conterfactual learningの枠組みを利用したバイアスを取り除くような予測モデルを構築
position-awareなシステムに対するunbiased CTRモデルは本研究が初めて
3. 技術や手法の"キモ"はどこにある?
Position-awareなシステムにおける2つのセレクションバイアスの発見
Retrieval bias
各リクエストにおいて、いくつかの広告は偏ったretrieveがなされているためバイアスが生まれる
Placement bias
retrievedされた広告は偏っているため、それを用いてplacementを決定するとバイアスが生まれる
Non-positionalなアプローチにおけるバイアス
ある位置で表示されてclickされた広告に対して違う位置で表示されてnon-clickであった状態を考慮できていない
位置$ kに不変な確率 $ \tilde{P}_{ij}ではなく位置$ kにおいて観測された$ P_{ijk}のみ考慮してしまっている
Unbiased CTRモデルの構築
Unbiased positional approach
考えられるアプローチ
Randomization
$ K個の広告をランダムに取得して、ランダムな位置に配置することで、偏りのないデータ$ Sを収集する方法
Imutation of non-displayed events
データ $ Sで表示された (displayed) イベントを用いて、この反実仮想 (non-displayed) を推定するモデル $ a(\cdot)を学習する方法
Inverse-propensity scores (IPS) of displayed events
傾向スコアを用いて補正する方法
$ z_{ijk} = {\rm Pr}(\mathcal{O}=1 | {\bf \mathcal{U}} = {\bf u_i}, {\bf \mathcal{V}} = {\bf v_i}, {\bf \mathcal{P}} = {\bf p_k})
システムは期待収益を最大化するように動いているため、求められる $ z_{ijk} はあまり実用的ではない
本研究では上記の3つのアプローチを doubly robust method で拡張した手法を提案
doubly robust method/estimation: IPSを用いた重み付けと回帰分析を組み合わせて因果の効果を推定するような方法
Unbiased non-positional approach
一般的にnon-positional approachは$ g(\cdot)を以下のように分解して扱う
position-independentな$ f(\cdot)とクリックされる確率$ h(\cdot)
上記で導入したunbiased positional approachを使えばバイアスを除けるかといったら、そうではない
クリックされる確率が観測できても、$ \tilde{P}_{ij}は観測できないため、以下のバイアス$ c_1が含まれた式 $ f^*(\cdot)と$ h^*(\cdot)に分解されてしまう
$ g({\bf u_i}, {\bf v_j}, {\bf p_k}) = f^*({\bf u_i}, {\bf v_j}) + h^*({\bf p_k}) = (f^*({\bf u_i}, {\bf v_j}) - c_1) + (h^*({\bf p_k}) + c_1)
$ f(\cdot)に着目してunbiased positional approachを解くことでunbiasedな結果を得ることができる(らしい)
このtheoremに対する証明は論文のsupplementを参照してください。
4. どうやって有効だと検証した?
リサーチクエスチョン
RQ1: retrieval/placement biasがどれくらいposition-awareなシステムのCTRモデルに悪影響を及ぼしているか?
RQ2: 提案法であるunbiased positional approachがどれくらい正確に真のクリック確率を推定できているか?
RQ3: 提案法であるunbiased non-positional approachがどれくらい正確に真のクリック確率を推定できているか?
RQ4: 提案法であるnon-positional approachに対するunbiased offline evaluationは正確に性能を推定できているか?
評価用データセット
8.4M リクエスト、300 ads を選択
2.6M リクエスト、100 ads を選択
for RQ1: バイアスの有無による性能の違い
比較方法
$ K個の広告や並び順を以下の方法でサンプリング(選択)した際のデータ$ Sの偏りを比較
比較手法
Greedy
期待収益の上位$ K個の広告を選んで、期待収益が大きい順に$ K個ある位置に配置する
これは retrieval bias と placement bias が含まれている
RG (Random - Greedy)
ランダムに$ K個の広告を選んで、期待収益が大きい順に $ K個ある位置に配置する
これは placement bias が含まれている
GR (Greedy - Random)
期待収益上位 $ K個の広告を選んで、ランダムに$ K個ある位置に配置する
これは retrieval bias が含まれている
Random
ランダムに$ K個広告を選んで、ランダムに$ K個ある位置に配置する
unbiased されている方法
$ \epsilon-greedy
Greedy と Random の比較
殆どのリクエストではGreedyに広告が選ばれるが、小さい比率$ \epsilonでRandomに広告を選ぶ
直感的には、少し unbiased なサブセットが選ばれている感じ
for RQ2: unbiased positional approachの性能
比較方法
TFM-XXX の XXX は上記のサンプリング手法
比較手法
biasedなモデル
TFM-Greedy
TFM-RG
TFM-GR
TFM-EE
unbiasedなモデル
TFM-Random
TFM-CF($ \epsilon) (提案手法を適用下モデル)
$ \epsilon-greedy でデータをサンプリングして $ S_{\rm unbiased} を得る
$ S_{\rm unbiased}データを元に学習したTFMを利用してimputation model $ a(\cdot)を得る
反実仮想なCTRモデル $ A_{ijk} = a({\bf u_i}, {\bf v_j}, {\bf p_k})を得る
このとき傾向スコアは $ z_{ijk} = 1 として設定
for RQ3: unbiased non-positional approachの性能
比較方法
比較手法
直接 $ f(\cdot)を推定できる設定にした理想的 (ideal) なアプローチ
FFM-Ideal
$ f(\cdot)から$ g(\cdot)を推定するアプローチ
FFM-Greedy-A
$ g({\bf u_i}, {\bf v_j}, {\bf p_k}) = f({\bf u_i}, {\bf v_j}) + h({\bf p_k})
FFM-Greedy-P
$ \sigma(g({\bf u_i}, {\bf v_j}, {\bf p_k})) = \sigma(f({\bf u_i}, {\bf v_j}))\sigma(h({\bf p_k}))
unbiasdなアプローチ
FFM-Random
FFM-CF($ \epsilon) (提案手法を適用したモデル)
for RQ4: unbiased non-positional approachのoffline evaluation
比較方法
trainとは異なる期間のデータをrandomにサンプルしたデータを使ってオフライン評価を行う
比較データ
$ S_{\rm te}: trainとは異なる期間のデータに対してrandomにサンプリングしたもの
$ S_{\rm te}(\alpha): $ S_{\rm te}と同様の設定で、$ C_{ijk} = Y_{ij} E_{ijk}に従った確率でサンプリングしたもの
$ Y_{ij}は$ \tilde{P}_{ij}におけるground-truth
$ E_{ijk}は$ B(\beta_k)に従った観測
$ \beta_k = 0.5^{k-1}として設定
5. 議論はあるか
for RQ1: データのサンプリング方法によるバイアスの有無
https://gyazo.com/494cbdca74227169164899d0aa5fb361
$ Sにおいてclickのあるデータを$ |S^+|、non-clickのデータを $ |S^-|
データサンプリング手法によってclickのあるデータ数がかなり多様
GreedyはRandomに比べて $ |S^+|が非常に多い
Greedyはclickが多いやつを選択するため
RGやGRはそれぞれ retrieve と placement をrandomにしている
Greedyよりだいぶ $ |S^+|が少なくなっている
Greedyと比べて売上の面で損失が起こりやすくなっていることに注意
randomにするためunbiasedではあるが、売上は少なくなる可能性
$ \epsilon-greedyは売上損失を抑えることができる
for RQ2: unbiased positional approachの性能
https://gyazo.com/b5bf6ebebf3714e3fe83a5ebf02b1b87
TFM-Greedy は retrieval bias と placement bias を学習してしまっている
性能は一番悪い
TFM-RG や TFM-GR は retrieval bias や placement bias をそれぞれ取り除いている
性能は少し向上
TFM-Random が性能面では一番良かった
unbiasedなデータからunbiasedな予測モデルを学習できているため
TFM-EE($ \epsilon) や TFM-CF ($ \epsilon)はTFM-Greedyより良かった
TFM-EEとTFM-CFにおいて$ \epsilonが同じ場合は提案法であるTFM-CFのほうが良かった
提案法であるTFM-CF($ \epsilon)は売上の損失を抑えつつ、unbiasedなTFM-Randomと同程度の性能を示している
unbiasedか、売上か、このあたりはトレードオフである
しかし、unbiasedと売上にうまく折り合いをつけた良いモデルである
for RQ3 & RQ4: unbiased non-positional approachの性能とunbiased offline evaluation
https://gyazo.com/97b983351164191251b99ced785b89e7
$ S_{\rm te}と$ S_{\rm te}(\alpha)の組み合わせについて
これらのデータセットにおいて性能の差は見られなかったため、unbiasedされていることが確認できた
一番精度が悪かった FFM-Greedy について
FFM-Greedyの設定は一般的なposition-independentなシステムと同等
位置情報とセレクションバイアスについて考慮すべきである
FFM-Greedy と FFM-Greedy-A / FFM-Greedy-P について
$ f(\cdot)から$ g(\cdot)を推定するような賢いやり方でも向上幅は少ない
セレクションバイアスによって $ g(\cdot)はバイアスを学習しており、結果的に $ f(\cdot)もバイアスの影響を受けている
FFM-Ideal と FFM-Random について
一番良い性能を示した
FFM-Idealは推定したい$ f(\cdot)を予め設定したunbiasedなデータから直接推定できるためにそれはそう
FFM-Randomはデータをunbiasedにすると理想的な状態に近いスコアを出すことができる
FFM-CF($ \epsilon) と FFM-EE($ \epsilon) について
unbiasedなサブセットである $ S_{\rm unbiased}が加わっているだけでFFM-Ideal/FFM-Randomと同等程度の性能を示した
impuationにより反実仮想 (non-display) を考慮可能であり、結果的にFFM-EE($ \epsilon)よりよい性能を示した
TFM-CF($ \epsilon)は売上損失が少ないモデルである
TFM-Randomと比べてrandom性が少ないunbiasedなデータを使っているため
6. 所感
実世界レベルと比べて研究レベルだと無視している条件がかなりあり、読むと痛いところを疲れまくっている論文だった
一般的に知られているpositionのバイアスや、それを更に分解した retrieve/placement biasなどを感じた
グノシー等でも表示される広告の位置やその決定プロセスから偏りが生まれる可能性は無視できない
逆にこうした偏りをより適切に扱うことで非常に大きな効果を得ることができそうではある
年末年始にcounterfactual MLまわりを勉強したので、いままで読めなそうだったタイプの論文を読めてよかった
セレクションバイアスや傾向スコアによる補正、doubly robust法といった有名所を感じることができた