【論文紹介】Improving Ad Click Prediction by Considering Non-displayed-ぐぐりらにっき

## はじめに

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。

本記事はアドベントカレンダー「<a href="https://adventar.org/calendars/4489">#今年読んだ一番好きな論文2019</a>」の21日目の記事です。
本ブログでのアドベントカレンダー参加は初めてなので、頑張りたいと思います。

普段はM2の学生をやっていて、機械学習やプログラミングを勉強しています。
機械学習における公平性や、レコメンド、因果推論、アドテクなどが興味のある分野です。

今回はWeb広告配信の最適化についての論文を紹介していきます！よろしくお願いします。

## 紹介論文

本記事は、以下の論文の紹介記事となっています。

題名 : Improving Ad Click Prediction by Considering Non-displayed([pdf](https://www.csie.ntu.edu.tw/~cjlin/papers/occtr/ctr_oc.pdf))

著者 : Bowen Yuan, Hong Zhu, Jui-Yang Hsia, Chih-Yao Chang, Meng-Yuan Yang, Zhenhua Dong, Chih-Jen Lin

出典 : CIKM'19 Proceedings of the 28th ACM International Conference on Information and Knowledge Management Pages 329-338

本記事はこの分野に明るくない方も多く見ていただくことになると思うので、厳密にというよりかは簡潔にして書いていきたいと思います。詳しい方でもっと知りたい！となった方はぜひ論文を読んでみてください。

(また、本記事の画像は上記論文からの引用になります。)

## 論文概要
Web広告配信の最適化を行う際、過去に配信した広告とクリックされたかどうかのフィードバックを元に学習したモデルを用いてWebページ閲覧者にクリックされそうな広告を予測するという手法が主流である。
しかし、過去に配信した広告もそれ自体クリックされやすそうな広告を予測して配信するロジックによって配信されているため、これらの配信結果を学習に用いるとバイアスが生じてしまう。
本研究では「過去に配信された」というバイアスを除去して真の「広告がクリックされる確率」を予測する手法を提案した。

## Web広告配信
本論文の紹介の前に、研究の背景を話していきたいと思います。

まず、Web広告配信についてです。
Webページを見ていると、よく広告が表示されると思います。僕のブログにも広告が貼ってあります。

この広告は多くの場合無造作に表示されているわけではなく、Web閲覧者の性質などからどの広告を表示するかを計算してから表示されています。
あるワードを調べていたら、それ以降広告に同様のジャンルの商品がよく表示されるようになった、という経験がある方も多いと思います。

広告配信者側としては、なるべく広告をクリックしてもらうことで、広告を入稿してくれた会社からお金をもらいたい、というモチベがあります。一回クリックしてもらう(もしくは購入、成約など)といくら、という単価が決まっていたりします。

広告配信者の期待収入は クリック確率 × 単価で決まり、単価は既知なのでクリック確率を正しく推定できれば、推定した期待収入の高い広告を表示すれば一番儲けが大きくなります。
ここで、クリック確率をClick Through Rate (CTR)と呼びます。

この理由から、CTR予測を正確に行えると嬉しい、ということがわかると思います。

## 従来手法の問題点

従来、CTR予測は次のような手法を用いて行われてきました。

実際に日々広告を配信する中で、そのログデータがたまっていきます。具体的には、このユーザーがこのページを訪れて、この広告を表示したところクリックしてくれた/くれなかった、などのデータです。

従来のCTR予測は、これらのデータを用いて教師あり学習を行い、学習したモデルを用いて新しく来たユーザーとWebページの組に対してどの広告が一番クリックしてくれそうかを予測しています。一番クリックしてくれそうな広告を表示する、という流れです。

しかし、この手法には問題があります。
従来の手法では、実際に配信した広告のログを用いて新しくモデルを学習しますが、このログには実際に配信したデータしか含まれていません。

つまり、ラベルが得られるデータは、そもそも配信していることが前提となります。当たり前ですが、配信していないデータに対してはクリックされた/されなかったというフィードバックが得られません。

このように、私たちが手に入れるラベルのついたデータは、実際に配信した広告のみですが、このシステム自体があるロジックのもとで配信しているので、観測されるログデータはバイアスを含んでいます。

完全にランダムに広告を表示した場合と、なんらかのロジック(閲覧者に合わせてクリックされそうな広告を出すというロジック)にしたがって広告を表示した場合では、データの分布が変わってしまう、ということです。

直感的には、ランダムに表示した場合はロジックにしたがって表示した場合よりもクリックされる率が下がりそうですね。

論文中では、ランダムに表示した場合とロジックにしたがって表示した場合の分布の違いを次の図で可視化しています。

各ドットは各広告を表します。

横軸がロジックにしたがって配信した場合に表示された割合を表し、縦軸は「ロジック配信時のCTR/ランダム配信時のCTR」の対数をとったものです。

全て縦軸が0以上なので、ロジック配信時の方がランダム配信時よりもCTRが高くなっています。
さらに、ロジック配信では表示されにくい広告ほどその比が大きいことがわかります。

このように、配信しているロジックによって選ばれた広告に対してのみフィードバックが観測され、そのデータをもとに学習すると、実際よりも高めにCTRを予測してしまいそうです。そしてそのギャップは表示割合が小さいほど深刻です。

ランダム配信したデータを用いて学習してはどうか、という疑問を持たれる方もいらっしゃるかもしれませんが、データをとるためだけにランダムに配信してしまうとクリック率が下がって著しく収益が落ちるので、なるべくランダム配信はしたくないです。

本論文ではこの配信によるバイアスを除去した予測を行うモデルを提案しています。

## 提案手法

提案手法では、少量のランダム配信したログデータがあるという前提で作られています。
(え、ずるくない？と思うかもしれないですが、一部の企業ではランダム配信を少量混ぜていることもあるみたいです。またこれがないと仮にバイアスが除去できる手法ができてもオフラインで評価することが難しいです。)

提案手法では、まずランダム配信したデータのみを用いて本体のモデルとは異なるモデルを学習します。

次に、このモデルを用いて手持ちのデータのラベルを予測します。
配信したログデータ、配信していないデータについて、「ランダム配信したとしたときの」ラベルを作ります。

で、本体のモデルの学習は、配信したデータに対する通常の損失関数に加えて、ランダム配信した時のラベルと本体モデルの予測の二乗誤差を正則化項のように追加します。

最終的な損失関数の形はこちら。

本体のモデルはなんでもいいわけではなくいくつかの条件を満たす必要がありますが、ここでは割愛します。詳しくは論文を読んでみてください。
論文中ではField-aware Factorization Machines (FFM)を使用しています。

損失関数のお気持ちは、「普通にログデータに対してfitするように学習しつつ、ランダム配信した場合のラベルから離れた予測をするとペナルティが課される」というイメージです。

実験でも示されていますが、ランダム配信データは少量でもワークするそうです。

## 実験

実験にはYahoo!R3とCPCという二つのデータセットを用いています。

CPCはCTR予測で、Yahoo!R3はmusic recomendationのデータセットです。Yahooの方はCTRではないですが、広告を曲にしたら同じ問題なので使っているようです。

評価はもちろんランダム配信した方のログデータのみで行います。
もし通常の配信ログを用いて評価してしまうと、今回やりたいこととずれてしまうので、これは当然ですね。

余談ですが、
オンラインでの評価は新手法と既存手法でA/Bテストをすればできますね。
オフラインでの評価では、ランダム配信した結果があるのならそれを用いれば問題ないです。今回はここに該当します。

問題はランダム配信した結果がない場合にバイアスのない評価をオフラインで行う場合で、ここはいろいろ各所工夫を凝らしている段階ではないかと感じています。

以下、結果の表を二つ示します。

一つ目は、通常の場合での比較です。
Newが提案手法です。New(hoge) のhogeの部分は、ランダム配信したデータから真のラベルを作る部分の手法を表していて、

* avg: 平均CTR
* item-avg: アイテムごとの平均CTR
* complex: FFM

が対応しています。
データのサイズなどに依存してどのバリエーションが強いかは多少変わりますが、提案手法が良い性能を出していることがわかります。

二つ目の実験では、ランダム配信したデータのサイズを減らした場合にどう性能が変化するかを調べています。
こちらでも、提案手法が良い性能を記録しています。

割と少量のランダム配信データでも改善することが示されていますね。

## まとめ

本研究では、配信して得られるログデータのみからCTR予測モデルを学習するとバイアスが生じることを示し、少量のランダム配信データを利用することでこのバイアスを取り除いた手法を提案しました。

ログデータから生じてしまうバイアスを除去した予測、オフライン評価を行う方法の検討はホットな話題だと感じる今日この頃だったので、こちらの論文を紹介しました。興味を持っていただけたら嬉しいです。

【論文紹介】Improving Ad Click Prediction by Considering Non-displayed

0 件のコメント:

コメントを投稿

このブログを検索

POPULAR POSTS

SPONSORED LINK

RECENT POSTS

TWEETS

ARCHIVES

LABEL

CONTACT