今回の話は検索エンジンの検索連動広告についてである。どの広告をどの順番で表示すれば検索エンジン側の収益の最大化、ユーザの満足度の向上が図れるかという問題についてが書かれてある。クリック率が分かっているならば話は早いのであるが新しい広告に対してはクリック率は過去のデータがないのでわからない。そこで新しい広告に対するクリック率を様々な手法を用いて推定してやるというのが本論文の核となるところである。ちなみにこれはマイクロソフトからの研究発表であるがビジネス要素が強いこのような研究を表に出してもいいのか？と疑問が残る・・・まあ取り合えず貴重な論文ということで・・・邦訳・要約しておいたのでブログに載せときます。論文の詳細はhttp://delivery.acm.org/10.1145/1250000/1242643/p521-richardson.pdf?key1=1242643&key2=0763889911&coll=GUIDE&dl=GUIDE&CFID=49087471&CFTOKEN=54138199です。具体的な表や計算式はこちらを参照願います。またまた図や式が汚くて申し訳ないです。ワードからグーグルdocに移してそこからブログに投稿しているので汚くなるわけです。もう少し互換性をどうにかして欲しいものです。ちなみに検索連動広告を考えている人に一言いっておくと、この論文のような内容が既に検索エンジン側で実装しているとしたら、たとえ個人運営のサイトが大手の会社より多くのクリック単価を払ったとしても大手より検索順位が低くなってしまう事がかなりありそうです。クオリティの低いサイトはお金を払っても認めてもらえないということですね、頑張ってコンテンツの充実などを図りましょう！
１．イントロダクション
ほとんどの主要な検索エンジン会社は今日検索結果の隣に配置されるテキスト広告によって利益を得ている。これはクリックがユーザによってされる度に料金が広告主から検索エンジン会社へ支払われるという仕組みをとっている。このモデルをクリック単価型成果主義と呼ぶ。検索エンジン側の収入とユーザの満足度を最大にするためには、システムがそれぞれの広告に対するユーザの挙動を予測して、可能な限りユーザにクリックを促さなければならない。サーチエンジンは過去に広告がクリックされたかでユーザの挙動を予測することができる。例えば100回広告が表示されてクリックが5回されたならば、その広告のCTR(click-through rate)は０．０５と推測することができる。しかしこの予測は新しい広告が入ってきた場合、すなわち過去のデータが利用できない場合は使うことができないという問題がある。
この論文では、私たちは新しく作られた広告がクリックされる可能性を予測する。我々は広告それ自体（広告の長さ、使用されている単語）、広告が指し示すページ、関連する広告の統計情報などを用いて新しい広告の将来的なCTRを合理的に予想する。
２．モチベーション
検索エンジン広告システムの主要な仕事は、サーチエンジンが受け取ったそれぞれのクエリに対してどんな広告を表示するかと、その順番をどうするかを決定することである。大抵広告主は広告が現れる状況をクエリ指定などにより既に指定してしまっているのでサーチエンジン側はマッチした広告を減らすことさえ考えれば良い。
ユーザが広告をクリックする確率は広告の表示位置によって大きく変わってしまうので、サーチエンジンにとって最も効果的な広告を最も目立つ位置に持ってくることが収入増を考える上で非常に重要な要素になる。しかも広告数が増加傾向にあり、与えられたクエリに対して適合する広告の数は効果的な広告表示枠の数を大きく上回ってしまうことが多くさらに広告の表示位置決定は重要さを増してきている。
広告の質（ユーザのクリックによって計測される）と総収益を最大にするためにほとんどの検索エンジンは期待収益（クリック率とクリック単価の積）の順に広告を並べ替えている。例外としてYahooはクリック単価の順番のみで並び替えているが今後期待収益の順に並び替びかえる事を検討している。それゆえ理想的な広告の並び替えを実現するには広告のクリック率を推定することが必要となる。
表示回数が多い広告ではクリック率は単純にクリック数を表示回数で割ったものと推測できる。ところが広告のクリック率は基本的にかなり低い（２．６％程度）ため推定の誤差が非常に大きくなってしまう。例えば真のクリック率が５％であるとして８５％の信頼区間でクリック率が４％～６％だと判断するには１０００回広告が表示されなければならない。
不正確な広告掲載順位のランキングはユーザと広告主の満足度を低下させ、収益もダウンする。それゆえ新しくて広告表示回数が少ない広告に対して我々は過去履歴を見る以外の手段でクリック率を予測する方法を発見しなければならない。新しい広告や広告主のために広告がクリックされる確率推定することがこの論文で述べられるシステムの目的である。
先行研究としてRegelsonとFain[19]が同じ入札語や同じトピックのクラスタによって新しい広告のクリック率を推定するというものがある。しかし我々の経験上同じ語であっても広告のパフォーマンスは大きく異なると言う事を知っている。このことを説明するために入札語以外の特徴を取り入れて考える必要がある。後述するが我々のモデルではそのような特徴を自然な形で取り入れている。
３．検索広告の骨組み
広告がクリックされるには
ユーザが広告を見る
ユーザが広告をクリックする
の２つの段階を経る必要がある。ここでユーザが広告を見るかどうかは広告の掲載位置のみに依存し、見られた上で広告がクリックされるかは広告の掲載位置に依存しないと仮定すると、あるポジションである広告がクリックされる確率は次のように表される。
ここでCTRを
と定義する。
CTRと
の減衰曲線からすべての場所での広告のクリック率を推定することができる。
何度も表示された広告に対しては簡単にCTRを予測することができる。
広告が見られた回数＝広告がクリックされた回数＋クリックはされていないが見られたと思われる回数であり、広告掲載位置ごとの広告が見られる確率は実験で調べることができ、クリックされていないが見られたと思われる回数は推定することができる。最後にクリック数を広告が見られた回数で割るとCTRを求める事が出来る。
我々の目的は新しい広告に対してこのCTRを予測することである。次のセクションではモデルの学習・テスト用のデータについて述べて、その後モデルの詳細について述べていく。
データセット
我々はマイクロソフトのサーチエンジンで実際に使われている広告についての情報を集めた。それぞれの広告には以下の情報が含まれている。
Landing page：クリック先のURLの情報
Bid term(“keywords”):広告が表示されるのに必要なクエリ（広告主が事前に入力しておく）
Title:広告のタイトル
Body:広告についてのテキストの説明
Display URL:広告下に表示されるURL
Clicks:広告が何度クリックされたか
Views:広告が何度閲覧されたか（第３章で述べた仮定を用いる、広告の表示回数ではなく、閲覧回数は表示回数に広告掲載位置による減衰係数を掛けたものになる。）
広告主は１万、５０万を超えるキーワードに対して広告の数は１００万以上、１０万を超える広告のテキスト
トレーニングセットとして広告主の７０％、検証用として広告主の１０％、テスト用として広告主の２０％を選んだ。
広告のViewがあまりに少ないと実験で求めたCTRと真のCTRがかなりずれてしまうのでViewが１００以下の広告は除くことにした。（トレーニングセットで学習するにあたりView数が大きい方がCTRの予測精度はノイズが少なくなるため良いが、一定のView数を獲得できなかった広告を排除してしまうため偏ったデータとなってしまう。そこでバランスを考えて100という数字を設定した。）
モデル
我々はCTRを予測するためにロジスティック回帰を使うことを考える。ロジスティック回帰は値を０～１の間で予測するため本質的に確率の問題に適している。
（モデルのここからははっきり言って良くわからない取り合えず様々なツールを使い、情報を精度が出やすいように正規化している）
ここで
は広告のi番目の特徴の値であり、
は特徴の学習した重みである。
特徴はある単語が含まれているかどうかやタイトル中の単語の数などであるが詳しくは後述する。
ロジスティック回帰はL-BFGS手法[16]を用いて訓練された。我々はゼロ平均ガウス重みを用いてクロスエントロピー損失関数を使い最適な標準偏差σの値を求めた。（よくわからない）最適なσの値は検証セットからσ＝０．１であった。よく行われることだが我々はいつも１にセットされるようなバイアス特徴を加えた。
それぞれの特徴に対して我々は
の生成された特徴と、
を加えた。１を加えた理由は最低の値を０にするためである、我々は特徴をゼロ平均になり、単位標準偏差を持つように正規化した。異常値を持つ特徴もあったので、偏差値５５以上のものは５５、偏差値４５以下のものは４５となるように調整した。これらの調整により制度の向上が見られた。
我々の計測方法は、モデルにより予測されたCTRと真のCTRのKL-divergenceをとるというものである（KL-divergenceは低いほうが良い）。この場合KL-divergenceは一回の広告のビューの結果をエンコードするために必要となるビット数を示している。我々のベースラインモデルは単純にトレーニングセットの平均のCTRを予測することである。（トレーニングセットのCTRの平均 ＝ テストセットの広告のCTR とする？）
入札語のCTRの予測
全体の平均のCTRとある入札語のCTRの間にはかなりの差異がある。よって広告のCTRを予測するに当たって、他の同じ入札語、あるいは関連した語のCTRを用いるのが有効である。
6.1 語のCTR
最初の特徴は、同じ入札語の他の広告のCTRである。これをトレーニングセットの広告の平均とうまく組み合わせると次のような式になる。
ここで
はある入札語を与えている広告主の数で
はそれらの広告の平均のCTRである。また
はすべてのトレーニングセットの平均のCTRを表している。
我々はロジスティック回帰に
（の事だと思う）も特徴として加えた。この２つの特徴をTerm CTR feature setと呼ぶことにする。結果はテーブル１のようになり、誤差を１３％減らすことが出来た。
関連語のCTR
RegelsonとFain[19]の場合と同様に、ある広告の入札語と関連した入札語を持つ広告のを利用したい。そこで入札語の部分集合と上位集合を考える。広告集合
を考える、広告の入札語をtとすると、tにm語付け加えたものを
と表し、tからn語を取り除いたものを
と表し、t からm語付け加えてn語取り除いたものをと表す、これらの集合の総数は
で与えられる。ここでこれらの集合のCTRの平均値を次の式により取る
これが関連広告の平均クリック率となり、6.1のを
で置き換えて同様の計算をしたところさらに６％の精度の向上が見られた。
広告の質を予測する
前章ではCTRを入札した語だけに基づいて推測したが、それだけでは十分ではなく、入札語が同じでも図３のようにCTRにはかなりの差が生じていることが分かる。そこでこの章
では広告そのものの特徴がよりよいCTRの予測に使えるのかを試したい。そこで広告をクリックするかどうかの判定基準となるような要因を考えてみた。その結果次のようなものが挙がった。
Appearance | 広告が審美的に喜ばしいか | title,body内のの単語数、効果的に大文字を取り入れているか？、エクスクラメーションが多すぎないかなど |
Attention Capture | 広告がユーザを引き込むかどうか | title,body内にbuy,join, subscribeなど行動を示す言葉が入っているか、値段が書かれているかなど |
Reputation | 広告主が知られているか？または有名なブランドであるか？ | ファーストドメイン(.comなど)、ドメイン長、セグメント数(books.comだと２セグント,books.something.comだと３セグメント)、短くて良い.comドメインは広告主が大きくて一流である場合が多い |
Landing page quality | クリック先のページの質 | フラッシュを含んでいるか、イメージの割合、W３Cの規定を遵守しているか、スタイルシートを使っているか、広告で覆われていないかなど |
Relevance | どれだけ検索クエリが広告と関連しているか | 入札語がtitleに現れるか？bodyに現れるか、bodyに現れるならその割合は？ |
全部で８１の特徴を５つのカテゴリから挙げた。
我々はユニグラムの特徴も加えた。広告のトレーニングセットのtitleとbody中で最も使用頻度が高い１００００の語に対して、語が存在したら１の値を、存在しなければ０の値をつけた。これらの特徴は我々が手動でとった特徴の機械版を意図している。これにより我々が発見できなかったような特徴もカバーできるかもしれない。
この結果さらに４％精度が向上した。しかしユニグラムの特徴を使わない場合わずか１％しか精度が向上しなかったのが驚きであった。
命令の詳細さを計測
例えば
Title: Buy shoes now,
Text: Shop at our discount shoe warehouse!
Url: shoes.com
Terms:{buy shoes,shoe,cheap shoes}
というように広告主が命令を与えておくと、広告主は靴を買いに来る人のみを限定的に狙っているということになる。ところが
Title:Buy [term] now,
Text: Shop at our discount warehouse!
Url:store.com
Terms:{shoe,TVs,grass,paint}
と命令を与えるとより広い層の顧客をターゲットしていることになる。ターゲットの絞込みが弱いともいえる。そしてターゲットの絞込みが弱いとCTRも下がってしまうのではないかと我々は考えているのでこれを実証してみる。
ターゲットの広さを測るために、我々は語のカテゴリーエントロピーを計測することにする。方法はまずTermsの語をWebサーチにかけ、その結果得られるスニペットをテキスト分類アルゴリズムにかけることでそれぞれの語を７４のカテゴリーに分類する。そのあと入札語のカテゴリの分布のエントロピーを測り、それを特徴として用いる。我々は入札語の個数も特徴として加えた。エントロピーの特徴と入札語の数の特徴は命令の特異性を扱ったものである。この結果はテーブル３のようになりさらに５．５％程度精度が向上した。
９. データの外部ソースの利用
さらに広告が持つデータ以外のデータを使って２つの特徴を加える。検索ヒット件数と検索回数である。我々は検索回数とCTRの関係を発見した。この関係は図５のようになる。図５より検索回数の多い語はクリック率が高いことが分かる。これらの特徴を考慮して実験したところテーブル４のようになった。ベースラインからだと３％精度が向上したにも関わらず、前章までの組み合わせで実験すると０．５％しか制度が上昇しなかった。これは前章までの特徴の何かと今回の特徴とがオーバーラップしているからである。
１０ 結果の討論
10.1 特徴の有用性
それぞれの特徴セットを独立してCTRの予測に用いると、どの特徴がより予測に有効なのか興味が出るところである。そこでそれぞれの特徴セットを独立に計測してKL-divergenceをとったところ広告の質が１２％（人手でつけた特長とユニグラムの特徴、ユニグラムだけだと１０．２％）でエントロピーの特徴が８．９％でサーチデータのセット（検索回数とヒット件数）が３．１％であった。
ロジスティック回帰モデルなので、我々はそれぞれの特徴の重みを知ることができる。その結果はテーブル５のようになった。
ユニグラムの特徴はテーブル６のようになった。これによるとofficialなどがトップに上がってきていることから、ユーザはより権威ある、一流のサイトを好んでクリックする傾向があるといえる。またquotes（見積もり）,trial（試用）,compareなどより限定的なユーザをつかむような単語が使われている場合のクリック率は低くなった。
それぞれの特徴の有用性をつかむのも面白いが、最も実用的なことはできる限り最終的なモデルに多くの特徴を含ませる事である。これによりどんな広告に対しても的確に予測できるようになるのである。
１０．２ 初期化後の進化？
我々のモデルはCTRをいくらか正確に予測することができるが、いったいどれくらいのViewがあればCTRが十分に推測できるのであろうか？ベースラインモデルと特徴を用いたモデルの、Viewの数とCTRの誤差の関係を表したグラフは図６のようになる。これによると１００回のView、表示回数に換算すると約２００～３００回の表示でベースラインモデルの誤差と特徴を用いたモデルの誤差が同じになることが分かる。特徴を用いたモデルは１００回Viewがあるまでの期間でうまく作用し、収益増をもたらしてくれる事が分かる。
１０．３ より多くのViewを持った広告
よりView数を多く持った広告をトレーニングセット、テストセットに選びCTRの予想に用いるとより正確なCTRを予測できる。よって１０００Viewを超えた広告のみをトレーニングセット、テストセットに選び同様の実験を行ったところテーブル７のような結果が得られ精度が向上した。しかし１０００Viewを超えるような広告は優良な広告が多くデータにかなりバイアスがかかってしまっている。
１１ 将来への考察・展望
この分野の研究があまりなされていないので、誰でも研究、比較できるように標準となるデータセットが必要である。
将来的にはユーザのクエリ情報を用いて、ユーザのクエリと入札語が完全に等しい場合、緩く当てはまる場合などを考慮する必要がある。（緩い例：広告主がパソコンという語が入ったクエリに対して広告を表示するという条件を与えておくと、“パソコン”というクエリ以外にも“中古パソコン”、“パソコン修理”といったクエリに対しても広告が表示される。）例えばクエリと入札語の類似度などを特徴として用いれば、今回のモデルをそのまま適用することができる。
RegelsonとFain[19]の手法を追加の特徴として取り入れて我々の手法と比較してみたい。
実際に実用化させるにあたっては、CTRの予測を広告の表示順位を決めるために使う以外に、広告主にCTRを向上させるアドバイスを与えるために使いたい。
その他、人による直感的な判断、広告サイトへの再訪問率、滞在時間、またデータを蓄積することで得られる広告主の質などを特徴として加え、さらなる精度の向上を図りたい。
