DEIM Forum 2013 B9-3

クリックフィードバックによる広告検索精度向上徹†

田頭 幸浩†

小野 真吾†

山本 浩司†

塚本 浩司†

田島堀田玲†† ヤフー株式会社 〒 107–6211 東京都港区赤坂 9–7–1
E-mail: †{thotta,yutagami,shiono,koyamamo,kotsukam,atajima}@yahoo-corp.jp
あらましオンライン広告におけるコンテキスト広告では，閲覧ページの内容やユーザーの行動履歴といったコンテキスト情報から，それぞれの広告のクリック率 (click-through rate; CTR) を予測している．この CTR の予測値をもとに期待収益を計算し，それを最大化するようにランキングし表示させている．CTR は過去の広告クリックログを用いて機械学習モデルを作成し，モデルのスコアによって予測するのが一般的である．しかし，機械学習モデルは一般に精度が高い一方で，配信時に大規模なアイテム集合に対して CTR を予測すると計算コストが高い．多くの広告配信システムにおいては，ウェブページを素早く表示するために数十ミリ秒で上位の結果を検索する必要がある．精度とレイテンシの両方を追求するため，コサイン類似度などの単純なスコアで少数の広告を情報検索のシステムを用いて取得し，より精度の高い機械学習モデルでリランキングする手法が用いられる．本稿では，その 1 段階目の情報検索のシステムにおいて，標準的な情報検索システムで扱うことができる関数形のモデルを機械学習によって構築し，このモデルのスコアを従来のコサイン類似度の代わりに用いることにより，効率的な広告検索を行うアプローチをとり，評価を行った結果を報告する．
キーワード

1.

導

オンライン広告，CTR 予測，機械学習，情報検索

入れら二つのうち広告主が設定した入札額は既知であるが，同じ広告であっても閲覧中のページやユーザーにより CTR は異なオンライン広告はインターネットの経済を支える大きな柱のるため，配信時に予測が必要である．たとえば，株価や為替情一つである．そのため，この分野はビジネス的に，また学術的報のページを閲覧中であればそれに関連した証券会社の広告がにも大きな注目を浴びている [3], [14]．オンライン広告の例とクリックされやすく，自動車に興味を持つユーザーであれば自しては，検索サイトにおける検索連動型広告，ポータルサイト動車の広告がクリックされやすいであろうと考えられる．

におけるディスプレイ広告，ニュースやブログ記事のページにおけるコンテキスト広告が挙げられる．

現在の広告配信システムでは，CTR は過去の配信ログを用いて機械学習により作成された予測モデルのスコアによって求

本稿ではオンライン広告のうち，広告自体がテキストからめている．予測精度の観点からはリクエストごとにすべての広なる，クリック課金型のコンテキスト広告を扱う．クリック課

告の CTR を予測することが望ましい．しかし，実際の配信シ金型の広告では，ユーザーがその広告をクリックした場合にのステムでは 1 回のリクエストに対して数十ミリ秒で応答するこみ，広告主に課金が行われる．コンテキスト広告ではユーザーとが求められており，すべての広告に対して機械学習モデルをが閲覧中のページや行動履歴などから潜在的な興味を抽出し，適用するのは計算コストが高く，現実的ではない．そのため，その興味に連動した，クリックされやすいであろう広告を配信

情報検索のシステムを用いてコサイン類似度などの単純なスコする．これにより，広告主は広告に興味を持っているであろう

アで少数の広告を取得し，それらをより精度の高い機械学習モユーザーに対する効果的な広告配信を行うことができる．

デルでリランキングする手法が一般的である．概念図を図 1 に

広告主はある広告の掲載を依頼する時に，課金されてもよい示す．しかしながら，この手法では検索システムとランキングと考える額を入札額として提示し，その入札額をもとに実際のロジックとの間でスコアが異なるため，最適な広告配信ができ課金額が決定される．ているとは必ずしも言えない．

コンテキスト広告には，ユーザーや広告主の他に広告掲載

本稿ではこの問題へのアプローチとして，図 1 の太枠で囲っページを提供するパブリッシャーと呼ばれる事業者が存在する．

た広告検索システムにおいて，機械学習によって構築したモデパブリッシャーは広告掲載で収益を得るため，限られた広告掲ルを使う効率的な広告検索手法 [5] を適用し，評価を行った結載の機会の中で可能な限り収益を最大化することを目的とす果を報告する．この手法では，標準的な情報検索システムで扱る．そのためには，それぞれの広告を配信した際における収益うことができる関数形のモデルを構築することにより，従来のの期待値を知る必要があるが，これは広告主が設定した入札額検索システムの効率性を維持したまま精度の高い広告検索を実と広告のクリック率 (click-through rate; CTR) で決まる．こ現することができる．

ユーザー

広告検索システム

広告
広告
広告
広告
広告

広告
広告
CTR
広告
CTR
広告
CTR
広告
CTR
広告
CTR

CTR
予測モデル

広告

広告

ランキング
ロジック

CTR

広告
広告

ページ

図 1 コンテキスト広告の概念図．ユーザーとページから素性を抽出してクエリとし，検索システムを用いて候補となる広告を取得する．その後候補の広告に対して CTR を予測し，ランキングロジックにて最終的に配信する広告と順序を決定する．本稿では太枠で囲んだ広告検索システムの部分において，機械学習を用いた最適化を行う．

本稿の構成は下記の通りである．2 章では関連する先行研究ページや広告の単語の重みパラメータを利用して，そのコンテについて紹介する．続く 3 章で転置インデックスを用いた検索

キストにおいて CTR が高い広告を取得する手法を提案した．

システムについて説明する．4 章では検索システムで用いられ本稿では，この手法をもとに評価を行った結果を報告する．

る従来のコサイン類似度などのスコアを，機械学習モデルのス

ここまで広告検索に関する研究を挙げてきたが，もう一つのコア関数に置き換えるアプローチについて解説する．5 章では研究の方向性として CTR 予測がある．CTR 予測では，過去実際の広告配信ログを用いたオフラインシミュレーションの結の広告クリックログを用いた機械学習モデルが利用される．一果を示し，6 章で全体のまとめをする．

般的には線形モデルが用いられ，その中でも CTR が確率であ

2.

関連研究

この章では先行研究として，広告検索と CTR 予測に関する研究を挙げる．

ることから確率値を出力とするロジスティック回帰モデルが用いられることが多い [6], [7], [12]．

3.

検索システムWang らの研究 [13] では，ユーザービリティやクリック率を

この章ではキーワードをクエリとしてドキュメントを取得す向上させるために，ユーザーの興味に関連した広告を表示する

る一般的な検索システムについて説明を行う．コンテキスト広ことが有効であると確認されている．関連度の高い広告を検索

告における広告検索では，大まかに閲覧ページとユーザーの 2する技術としては，ウェブ検索で用いられる情報検索の手法が種類の情報を用いて広告を取得するため，広告をドキュメント効果的とされている．とし，閲覧ページとユーザーから抽出した情報をキーワードとRibeiro-Neto ら [11] はコンテキスト広告の広告引き当てにおして用いて検索を行う．

いて，ページと広告から抽出した単語をもとに引き当てを行う

まずベクトル空間モデルについて述べ，次に転置インデックいくつかの手法を評価した．この研究では，広告とページはそスを用いた検索システムについて説明する．最後に，クエリにれぞれ多次元ベクトルとして表現され，それら 2 つのベクトル依存しないドキュメントごとの静的クオリティスコアについてのコサイン類似度を利用して広告引き当てを行う手法について述べる．

検証している．この中で，広告のタイトルや本文，課金フレー

3. 1ズといったさまざまな広告セクションを利用し，精度の高い手ベクトル空間モデルにおいては，クエリとドキュメントの法を探求している．

ベクトル空間モデル

両方が同じ多次元空間上のベクトルとして表現される．m をページと広告が同じベクトル空間上にマッピングされる手法

単語の種類数とすると，クエリ q を表すクエリベクトルは

では，ページと広告の持つ単語群の違いから少なからずミス

q = (q1 , q2 , . . . , qm ) と表現され，同様にドキュメント d を表マッチが生じる．つまり，それぞれの次元が各単語を表現する

すドキュメントベクトルは d = (d1 , d2 , . . . , dm ) と表現される．

ベクトル空間モデルでは，同意語などを適切に扱うことができ

qi はクエリ q における単語 i の重みを表す．di も同様である．

ない．この問題に対応するために，ページから抽出される単語クエリ q に対するドキュメント d のスコアは，二つのベクト∑
i qi di で定義される．このクエリとドキュメ群を，そのページに似ているページの単語群を利用して拡張す

ルの内積 q T d =ることにより広告検索精度を向上させる手法が提案されていントの内積スコアは，3. 2 節で紹介する転置インデックスを用る [11]．また，ラベルづけされた教師データを用いて分類器をいた top-k retrieval システムにおいて，高速に計算することが作成し，その分類器を用いてページと広告にクラス情報を付与できる．

し，広告検索に利用する手法も提案されている [2]．

3. 2

転置インデックスを用いた検索システム

Chakrabarti ら [5] は，従来のコサイン類似度の代わりに，広検索システムにおける標準的なアプローチでは，まず最初告の配信ログからロジスティック回帰モデルによって学習したに検索アイテムであるドキュメントコーパスにおいて転置インデックスを構築する．これは，ポスティングリストと呼ばは広告ベクトルを表す．それぞれ，ページとユーザーから抽出れる，コーパス中での各単語の出現位置を表すリストの集合した素性ベクトルと，広告のみの素性ベクトルを表すものと(L1 , L2 , . . . , Lm ) を作成することと同義である．リスト Li は，する．

単語 i の重みが 0 でない広告を列挙することで作成される．ほ式 (2) の第一項はクエリと広告の関連度を表す項であり，各とんどの広告において，ある単語 i の重みは 0 なので，そのま素性に応じて wd = (wd,1 , wd,2 , . . .) で重みづけをした形となっ

ばらさを利用してポスティングリストは，ドキュメントの IDている．q ′ i = wd,i qi とした値をクエリとして用いるか，もしとそのドキュメント内の単語の重みからなる < doc id, di > の

くは a′ i = ws,i ai とした値をドキュメントベクトルとして転置二つ組を要素とする集合で記述可能である．今，クエリが与えインデックスを構築することで，従来の検索システムで検索をられたとすると，そのクエリに含まれる単語に対応するリスト行うことが可能である．

のみを考慮すればよく，これにより検索空間を削減し高速なシ第二項は閲覧ページやユーザーなどのコンテキストに依存しない，その広告自身のクリックされやすさを表す静的なクオリステムを構築することができる．

top-k retrieval では，転置インデックスを用いることで，与ティスコアである．これは広告ベクトル a = (a1 , a2 , . . .) と対えられたクエリに対してスコア上位 k 件のドキュメントを高速応する重みベクトル ws = (ws,1 , ws,2 , . . .) によって計算されに取得することができる．これはシステム内でのスコアの評価る．広告検索時には，ドキュメントの静的クオリティスコアと途中で，既に上位 k 件に入ることがないと分かっているドキュしてこの値を用いる．

メントに対する評価を省くことで効率化を行うもので，さまざ

3. 3

第三項はページやユーザーによって，広告の種類に関わらずCTR が変動することを表す項である．これはクエリベクトル

まな手法が提案されている [4], [8]．
ドキュメントごとの静的クオリティスコア

q = (q1 , q2 , . . .) と対応する重みベクトル wb = (wb,1 , wb,2 , . . .)各ドキュメントには，クエリに依存しない静的なクオリティによって計算される．広告検索時には，既にページとユーザースコアがあると考えられ，例としてウェブ検索における PageR-は固定されているため，この項は広告間の CTR 予測値の大小ank [10] が挙げられる．一般的な情報検索のシステムでは，こ関係には影響しない．しかしながら，学習データはページとのような静的なクオリティスコアを，クエリに応じて変化する

ユーザーによって CTR に偏りがあると考えられ，単純に式 (2)ドキュメントの動的なスコアに加算したものを最終的なスコアの第一項と第二項のみからなるモデルを学習すると，二つの項として扱うことができる [9]．

でその偏りを表現するため，精度が悪化することが予想される．

4.

この項は学習時には偏りを表現するために用いるが，広告間の機械学習モデルによる広告検索

CTR 予測値の大小関係には影響しないため，広告検索時のス

この章では，標準的な情報検索システムで扱うことができる関数形のモデルを機械学習によって構築し，このモデルのスココア計算には用いない．つまり，実際の広告検索時には下記のようなスコアが計算される．

アを従来のコサイン類似度の代わりに用いて，効率的な広告検索を行うアプローチについて説明する．なお，以下では CTR

scoread =∑iwd,i qi ai +∑ws,j aj(3)

jの予測値が高い広告を取得することを目的とする．期待収益が高い広告を取得することを目的とする場合もほぼ同様である．

4. 1

式 (2) の重みパラメータベクトル wd , ws , wb は機械学習によってデータから推定される．推定には大まかに二つの手法が機械学習による CTR 予測モデル

2 章で述べたように，CTR 予測モデルとしては線形モデル考えられる．一つ目は，広告配信ログを用いてクリックされたが用いられることが多い．ここでは以下のような線形モデルでか否かを目的変数として直接学習を行う手法である [5]．二つ目

CTR の予測値が表現されるとする．

は，あるページ，ユーザー，広告に対して既存の機械学習モデCT R =ルで CTR を予測し，その予測値を広告検索時のモデルの目的∑wi fi (p, u, a)(1)i変数として学習を行う手法である [1]．本稿では一つ目のアプローチを取り，この手法を用いた広告検索システムの概念図を，

ここで，fi (p, u, a) はページ p，ユーザー u，広告 a の 3 つ

図 2 に示す．

から抽出された i 番目の素性を，wi はその素性に対応する重み

図 2 の広告検索システムでは，事前に広告から素性ベクトルを表現している．重みベクトル w = (w1 , w2 , . . .) は，データを作成し，転置インデックスと静的クオリティスコアを作成しから機械学習で推定される．ておく．ユーザーとページの組み合わせが検索リクエストとし

4. 2

機械学習による広告検索モデルて与えられれば，それらから同様の素性ベクトルを作成し，機式 (1) で表現されるモデルの予測値が高い広告を検索時に取械学習によって推定された重みパラメータ wd を用いてクエリ得することがここでの目的である．広告検索時に用いるモデルの素性ベクトルを変換する．この変換されたクエリの素性ベクを，以下の関数形で表現する．

トルと広告の素性ベクトルの内積スコアと広告の静的クオリ

scoretrain =∑iwd,i qi ai +∑jws,j aj +∑wb,k qk

(2)

k

なお，q = (q1 , q2 , . . .) はクエリベクトルを，a = (a1 , a2 , . . .)ティスコアを合計すると，式 (3) が計算できる．

クエリ
広告DB,

FeatureFeature

ベクトル空間モデル

ベクトル空間モデル,,,…,,

静的クオリティスコア計算,,,…,,…,

重みによるクエリベクトルの変換,,,,,…,,

内積,,

静的クオリティスコア加算,
図2

機械学習モデルを用いた広告検索システムの概念図．図中の SQS は静的クオリティスコア (Static Quality Score) を意味する．

5.

実

験

この章では，4. 2 節で述べた機械学習モデルによる広告検索と，従来のコサイン類似度を用いた検索の比較を行う．

5. 1

広告検索手法ションを行った．実際の配信システムでは広告主の予算は動的に変化し，予算がなくなればその広告主の広告は配信されないが，本実験においては，予算の変化については考慮せず評価を行った．
また，クエリとしては，ウェブページの語句情報のみを用い以下の三つの手法を比較する．

る．それぞれの広告検索手法の比較をするため，いくつかの•コサイン類似度モデルウェブページを固定して評価を行う．今回は，11 のウェブサ•

機械学習モデル（静的クオリティスコアなし）

イトを実験対象とし，ある 1 日の広告配信回数が多かった上位•

機械学習モデル100 ページをそれぞれのウェブサイトごとに選択して用いた．

コサイン類似度モデルは，従来のコサイン類似度での広告検クエリが与えられ広告検索を行った後，取得した全ての広告に索方式である．この手法をベースラインとし，その他の手法の対して既存のモデルで CTR を予測し，上位 12 本の広告を最評価を行う．2 つ目のモデルは，式 (3) の第一項だけでスコアリ終的な配信対象とみなした．広告検索時には最大 1,000 本の広ングする手法で，クエリと広告の関連度だけで検索する手法で告をリクエストした．評価基準としては，CTR の高い広告をある．3 つ目の機械学習モデルは，式 (3) でスコアリングする検索システムから取得することを目的としているため，配信対広告検索手法である．機械学習モデルのうち、静的クオリティ象となった 12 本の CTR 予測値を平均して用いた．

スコアなしのモデルとありのモデルを比較することで，広告自身の魅力を表す静的クオリティスコアが，CTR にどれだけ影響を与えるかを見る．

5. 2

実験設定

式 (2) の重みパラメータを学習するためのデータとしては，広告配信ログを約 3 か月分サンプリングし，用いた．

5. 3

実験結果

実験の結果を図 3 に示す．アルファベットの A から K は各

実験では，実際の広告配信システムの中にある広告集合の中ウェブサイトを表しており，グラフの縦軸はコサイン類似度モから，広告主の予算状況などによるフィルタリングやサンプリデルを用いた場合と比較した，CTR 予測値の変化率である．

ングを施すことで約 30 万件を選択し，広告配信のシミュレー

図 3 の黒色のグラフは静的クオリティスコアありの機械学

40%
35%
30%

[5]

25%
20%
15%

[6]

10%
5%
0%
‑5%
A

B

CDE

FG

H

I

JK

[7]

図 3 ベースラインと比較した CTR 予測値の変化率．白色が静的クオリティスコアなしの機械学習モデル，黒色が静的クオリティスコアありの機械学習モデルの変化率を表している．

習モデルにおける合計 CTR の変化率であり，E 以外のすべて[8]のドメインで CTR が向上しているのがわかる．11 サイト中

6 サイトで 10%以上の向上をしており，多くのウェブサイトで大幅に向上しているのがわかる．全ウェブサイトでみると，約15%の向上であった．
一方，静的クオリティスコアなしの機械学習モデル（白色）[9]では，11 サイト中 9 サイトがコサイン類似度モデルを上回ったが，その向上率は小さく全ウェブサイトでみると 5%の向上で[10]あった．このことから，静的クオリティスコアで表現される広告自身の持つ魅力が，CTR に大きな影響を与えるといえる．

6.

[11]

まとめと今後の課題

本稿では，一般的なコンテキスト広告の配信システムにおける，機械学習モデルを用いた広告検索を行う手法について述べた．また実験では，この手法を用いることで従来のコサイン類[12]似度で広告検索を行った場合と比較して，実際に CTR の予測値が高い広告を取得できることを確認した．
今回はページと広告の語句情報のみを用いた実験を行ったが，ユーザー情報をクエリとした検索の実験も考えられる．これは[13]今後の課題である．

文

献[1] Deepak Agarwal and Maxim Gurevich. Fast top-k retrieval
for model based recommendation. In Proceedings of thefifth ACM international conference on Web search and data
mining, WSDM ’12, pages 483–492, New York, NY, USA,2012. ACM.
[2] Andrei Broder, Marcus Fontoura, Vanja Josifovski, andLance Riedel. A semantic approach to contextual advertising. In Proceedings of the 30th annual international ACM
SIGIR conference on Research and development in information retrieval, SIGIR ’07, pages 559–566, New York, NY,USA, 2007. ACM.
[3] Andrei Broder and Vanja Josifovski. Introduction to computational advertising. http://www.stanford.edu/class/msande239/. Accessed: 14/12/2012.
[4] Andrei Z. Broder, David Carmel, Michael Herscovici, AyaSoﬀer, and Jason Zien. Eﬃcient query evaluation using atwo-level retrieval process. In Proceedings of the twelfth in-[14]ternational conference on Information and knowledge management, CIKM ’03, pages 426–434, New York, NY, USA,2003. ACM.
Deepayan Chakrabarti, Deepak Agarwal, and Vanja Josifovski. Contextual advertising by combining relevance withclick feedback. In Proceedings of the 17th international conference on World Wide Web, WWW ’08, pages 417–426,
New York, NY, USA, 2008. ACM.
Haibin Cheng and Erick Cantú-Paz. Personalized click prediction in sponsored search. In Proceedings of the third
ACM international conference on Web search and datamining, WSDM ’10, pages 351–360, New York, NY, USA,2010. ACM.
Haibin Cheng, Roelof van Zwol, Javad Azimi, Eren Manavoglu, Ruofei Zhang, Yang Zhou, and Vidhya Navalpakkam. Multimedia features for click prediction of newads in display advertising. In Proceedings of the 18th ACM
SIGKDD international conference on Knowledge discovery
and data mining, KDD ’12, pages 777–785, New York, NY,USA, 2012. ACM.
Marcus Fontoura, Vanja Josifovski, Jinhui Liu, Srihari
Venkatesan, Xiangfei Zhu, and Jason Zien. Evaluation
strategies for top-k queries over memory-resident inverted
indexes. In Proceedings of the 37th International Conference on Very Large Data Bases, volume 4, pages 1213–1224,
2011.
Christopher D. Manning, Prabhakar Raghavan, and Hinrich
Schtze. Introduction to Information Retrieval. Cambridge
University Press, 2008.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry
Winograd. The pagerank citation ranking: Bringing orderto the web. Technical Report 1999-66, Stanford InfoLab,
November 1999. Previous number = SIDL-WP-1999-0120.
Berthier Ribeiro-Neto, Marco Cristo, Paulo B. Golgher, andEdleno Silva de Moura. Impedance coupling in contenttargeted advertising. In Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, SIGIR ’05, pages 496–503,
New York, NY, USA, 2005. ACM.
Rómer Rosales, Haibin Cheng, and Eren Manavoglu. Postclick conversion modeling and analysis for non-guaranteed
delivery display advertising. In Proceedings of the fifth ACM
international conference on Web search and data mining,
WSDM ’12, pages 293–302, New York, NY, USA, 2012.
ACM.
Chingning Wang, Ping Zhang, Risook Choi, and Michael
D’Eredita. Understanding consumers attitude toward advertising. In In: Eighth Americas Conference on Information Systems, pages 1143–1148, 2002.
Shuai Yuan, Ahmad Zainal Abidin, Marc Sloan, and JunWang. Internet advertising: An interplay among advertisers, online publishers, ad exchanges and web users. CoRR,
2012.