Predicting Clicks: Estimating the Click-Through Rate for New Ads - WWW2007

Microsoft Researchの論文

1. Introduction

2. Motivation

検索連動型広告のタスクはどのクエリに対してどの広告を表示するかを決定すること
=> 多くの場合は広告側がターゲットとしたいクエリは既に決まっている.
=> 検索エンジン側は広告をランク付けするだけでよい

検索結果と同様に広告は表示位置によってクリック率が90%近く下落する
=> 検索エンジンは収益最大化のために最も効果の良い広告を最も上に表示しなければならない

表示に適した広告は表示の枠よりも遥かに多くある．
ほとんどのユーザは２ページ目以降にいかないため，１ページ目に載せることができる広告の数には制限がある（5-8個)

ほとんどの検索エンジンは広告を期待収益順に並べる

CPCはbid(in a first price auction)かthe next-highest bidder(in a second price auction)によって決まる
この論文ではCPCとbitは重要ではないが，それに関する研究も存在する．[8][12]

理想的に広告を並べるにはp(click)を正確に見積もることである．
多くの回数ユーザに提示された広告は単純に #click/#impressionとすれば見積もることが出来る．
しかし，CTRは基本的に低いため分散は非常に大きい．
真のCTRが5%の広告ではCTRを85%の信頼度で1%の範囲内見積もるためには1000回表示されなくてはならない．
一般的な検索連動型広告のCTRは2.6%と言われている
CTRを以下に早く収束させるかが検索エンジンのマネタイズに大きく影響する

毎日新しいキャンペーンがどんどん追加される
さらに既に存在するキャンペーンに新しいクエリが割り当てられることもままある
検索エンジンはなんの事前情報もない広告を大量に抱えることになる
この新しい広告と既存の広告を適切にランク付けしなくてはならず，
このランク付けを誤ると広告主に不満を抱かせるだけでなく，検索エンジンの収益を悪化させることにもなる
本研究の目的は新規の広告・広告主に対して広告がクリックされる確率を予測することである

Regelson and Fain[19]
同じbid termまたは同じトピッククラスタに所属する既に存在する広告のCTRを用いて新規のCTRを見積もった．
本研究の実験では同じtermというだけでは分散が非常に大きいことが明らかになっている

キーワードによる分散を扱うために，bid term以外のfeatureも組み合わせなければならない．
本研究で提案するモデルは自然にそれらのfeatureを組み合わせることが出来る．

3. Search Advertising Framework

場所によって広告が見られる確率は変わる
本研究では簡単化のために広告のクリックを２つの要素に分ける

• その広告が見られる確率
• その広告が見られた時にクリックされる確率

さらに簡単化のために以下の２つを定義する

• 広告がクリックされたかは広告のみに依存し表示位置には関係しない
• 広告が見られるかどうかは表示位置にのみ依存し広告には関係しない

CTRはp(click|ad,seen)で定義され， CTRとp(seen|pos)の減衰曲線から広告がどの位置でどの程度クリックされるのかを見積もることができる

広告がたくさん表示されればCTRは簡単に見積もることができる．
=>クリックされたときはseenである
=>クリックされなかったときは表示位置によってある程度の確率でseenになる

本研究の目標は新規の広告に対してCTRを見積もることである

4. Dataset

Microsoft Web Search Engineの広告情報を用いる．

• Landing page: アドをクリックした時の遷移先URL
• Bid term: 広告を表示するクエリ
• Title: ユーザに見える広告のタイトル
• Body: 広告の説明文
• Display URL: ユーザに表示されているURL
• Clicks: アドがクリックされた回数
• Views: 広告が表示された回数

10,000の広告主
1,000,000の広告
500,000以上のキーワード

広告とクエリを一致させる仕組みには"exact match"と"broad match"の２通りがある．
exact matchはクエリとbid termが完全に一致しなくてはならない
broad matchは部分集合のように緩い一致でも関連付けられる
本研究では双方に対してCTRを推定することを試みる

データセットは広告主をベースに分離する．

70%の広告主を訓練データに
10%をvaludartionデータに
20%をテストデータとして用いる

"premium"な広告主をデータセットから取り除く

彼らの出す広告のCTRは一般の傾向と大きく乖離しており、本研究ではデータのない広告主を対象にしているため
加えて広告主ごとに1000件のデータのみをサンプリングする．

本研究の目的はtrue CTRを推定することであるが，クリック数とView数から分かるのはempirical CTRである
view数が少なければempirical CTRはtrue CRTと大きく異る
本研究では用いるデータをview数100以上のもののみとした

5. Model

CTRを予測するというタスクを回帰問題として考える．
つまり与えられたfeaturesからCTRを予測する．
ロジスティック回帰を用いた．
ロジスティック回帰は予測値が常に0-1に収まるため確率の予測に適している．

fi(ad): the value of i-th feature for the ad
wi: learned weight for that fearyre

ロジスティック回帰はL-BFGS法を使って学習する
そして標準偏差σのzero-means Gausian wightによるクロスエントロピー誤差関数を用いる
σは[0.01, 0.03, 0.1, 0.3, 1.3, 10, 30, 100]から最適なものを選択することとし，今回は0.1を選択した
さらに常に１をとるバイアスフィーチャーを加える（切片項）

それぞれのフィーチャーfiに対して，log(fi+1), fi^2を加える
さらにそれぞれのフィーチャーを平均0, 標準偏差1(unit standard deviation)を持つように正規化する
幾らかのフィーチャーは外れ値を持つ．平均から5σ以上の値をもつ素性は排除する．

予測CTRと真のCTR間のavrage KL-divergenceを用いてパフォーマンスを計る．
KL-divergenceは単純にモデルのlog-likelihoodからtest-setのエントロピーを引いたものである．
完璧なモデルであればスコアは0になる．
Baselineはtraining setのCTRを単純に平均化したもの．
Mean Squared Errorも測定し，KL-divergenceを最適化することで，誤差をどれほど減らす事ができたかを計る．
本研究で報告されるimprovementは統計的に1%で優位である．

事前の実験で，boosted regression treesを用いてパフォーマンスを測定したが，ロジスティック回帰から優位な改善は得られなかった．
解釈の容易さと単純化のため今後の実験ではロジスティック回帰を用いる

6 Estimating Term CTR

6.1 Term CTR

同じbid termを持つ広告のCTRを用いる
そのbid termが過去のデータセットになかった時の為に，平均CTRを用いてスムージングを行う

N(term): the number of ads with the given bid term
CTR(term): the average CTR for thorse ads
ave-CTR: the mean CTR for all ads in the train set
α: the strength of prior (実験から今回は1にする)

f0とN(term)をロジスティック回帰のfeatureとして用いる．
この２つのフィーチャーをTerm CTR Featurを呼ぶ

6.2 Related Term CTR

bid termのsubsetを用いてCTRをより高精度に予測する．

Rmn(t)上記の条件を満たすtを持つ広告集合

例："red shoes"
R01=> "buy red shoes"
R10=> "shoes"
R11=> "blue shoes"

R00: exact match
Rm0: missing m words(vs t)
R0n: n extra words

R0*: any ad whoose terms are a superset of t

term CTRと同様にave-CTRを用いてスムージングを行う
更にフィーチャーとしてad数も用いる

これらのフィーチャーをm, n = {0, 1, 2, 3, *}に対して計算する

それぞれの実行結果が以下の通り

TermCTRを用いることで13%の改善， Related term CTRsを用いることで6%, 全体で19%の改善を果たした

7. Estimating Ad Quality

ここまで語の情報のみでCTRを推定することを試みたが，
これまでも述べた通り語の情報だけでは非常に分散が大きい

Featureの情報を用いてクリック率の予測をよりよくすることはできるだろうか？
Jansen and Resnickは検索者は概要文、タイトル、遷移先のURLを見てクリックするかを決めているという．
本当にユーザがクリックするか否かを決定づけているのは何なのか、仮説を粗くカテゴリ分けした

• Appearance: 広告が美しく魅力的か？
• Attention Capture: その広告はユーザを引きつけたか？
• Reputation: その広告主はknownもしくはreputable brandか？またユーザがその広告主をよく知らなくても、良いブランドであると推測することができるか？
• Landing page quality: 広告をクリックしたユーザの多くは既にその広告主をよく知っているのではないかという仮説を持っている．そのため良いランディングページは広告のクリックを高めるのではないかと考えられる．加えて新しいプロダクトを探してユーザが再度訪れる可能性もある．
• Relevance: 広告とクエリがどれだけ関連づいているか？

これらを表すと期待されるフィーチャーを列挙する

• Appearance:
  • titleにいくつ語が使われたか？
  • 本文にいくつ語がつかわれたか？
  • 大文字が使われているか？
  • "！"がいくつつかわれているか？
  • "$"がいくつ使われているか？
  • その他の句読点は？
  • 短い語を使っているか長い語を使っているか？
• Attention Capture
  • "buy", "join", "subscribe"などのaction wordを含んでいるか？
  • 数が含まれているか？(値段・割引率など)
• Reputation
  • urlが.comで終わっているか？
  • 長さは？
  • urlのsegmentの数は？
  • dash(-)や数はいくつ含まれているか？
• Landing Page Quality
  • Flashを含んでいるか？
  • どれだけ画像で覆われているか？
  • W3Cに則っているか？
  • style sheetは使われているか？
  • adで覆われているか？
• Relevance:
  • bid termがタイトルに使われているか？
  • 語の一部が現れているか？
  • 本文のどのぐらいの割合か

このようなフィーチャーを81個定義した．いくつかのフィーチャーは複数のカテゴリにわたっている．
さらにユニグラムフィーチャーとして訓練データの広告に頻出する10,000wordsが広告に出現すれば1, しなければ0を持つフィーチャーとして加えた．

この図はユニグラムフィーチャーが平均CTRの半分以下の広告より、平均CTRの2倍以上の広告によく現れていることを示している（本当かよ…？）

AdQuality Featuresを加えることで4%改善することができている．
unigram featureをRelated termからの改善はわずか1%にとどまった．
この結果は沢山のmanual featuresが効果をもたらすと考えていた私達をとても驚かせた．（原文ママ）

8. Measuring Other Specificity

この２つの広告、前者のほうがターゲットが絞りこまれており，
一般に前者のような広告のほうがCTRが高いとされている．
ここでは広告がどれだけ良くターゲティングされているかをフィーチャーとして取り入れることを試みる．

bid termをカテゴライズするためにそれらを用いて検索し、検索結果のスニペットを用いてテキスト分類を行った．
テキスト分類にはナイーブベイズを用いて，trigramでフィーチャーを作りLook Smart Directory structureで訓練した．
（LookSmart Directoryはこれのこと？ http://ja.wikipedia.org/wiki/LookSmart)
これにより74カテゴリにtermを分類し，広告が入札しているbid termのカテゴリに対する分布のエントロピーを計測しフィーチャーとして加えた．
同時にいくつのbid termを持つかも加える．

その結果5.5%の改善が見られた
カテゴリエントロピーのみでは26.37%であったため，両方のフィーチャーが改善をもたらしたと言える

9. External Sources Data

検索エンジンの検索結果が何ページあったかをフィーチャーとして用いる．
Regelson and Fainはad termの検索件数とCTRに関連があることを示している

またad termがどのぐらいユーザに検索されているかを過去3ヶ月のクエリログから得る．
これを20のカテゴリにわける．それぞれのカテゴリで同じ数の広告が含まれるようにする

Baselineに加えると3%改善したが，これまでの結果に加えると0.5%しか改善しなかった
このことから他のフィーチャーによってカバーされているとも考えられる

10 Discussion of Results

10.1 Utility of Features

Ad TermとRelated Termを除いてフィーチャーの影響力を調べる

• ad quality feature 12%(うちunigram featureだけで10.2%)
• エントロピーで8.9%
• Search Dataで3.1%

ロジスティック回帰の重みのTop10とBottom10

重みがフィーチャーの重要度を必ずしも表すわけではない．
それぞれのフィーチャーが独立であるとは限らないからである

unigram featureのtop10,bottom10

どのフィーチャーが一番いいとか、どのフィーチャーがどのフィーチャーとオーバーラップしているかを決定することも興味深いが
それを明らかにしてしまうと広告主から広告システムへの攻撃を許すことになってしまう
重複するフィーチャーが含まれることでこの攻撃を防ぐことができるのではと考えている

10.2 Evolution After Initialization

何回表示されたら計測したCTRに移すべきか、どのようにウツしていけばいいのか？

予測値と実測値を組み合わせる簡単な式を仮定する

誤りの期待値を以下のように定義する

その結果が以下の図

このことから100回見られるまでは提案手法が有効であるといえる
100回seenになるためには2-300回pageに出る必要がある．

10.3 Ads with Many Views

学習をよりよくするためにはノイズを減らす必要がある．
そのためにはより多く表示された広告のデータのみを用いることが望ましい．
今回は新規の広告に対する最適化問題だったため閾値を100としているが、
それが多くなった時どうなるかを調べる

このように改善率が非常に高まる．
ただview数が少ない広告を無視してしまうとパフォーマンスが低い広告を含むことができない
1000回以上表示されている広告の平均CTRは100以上のそれより40%以上高い

11. Discussion and Future Work

この分野の研究は比較的初期の段階にあり，基準となるデータセットの構築や評価フレームワークの設計が強く望まれる

Future Work

• ユーザのクエリを用いたCTR予測
• Regelson and Fainによるterm clusteringのfeatureへの組み込み