電子情報通信学会ワードテンプレート (タイトル)

DEIM Forum 2012 E7-2
入札キーワードの重要度を考慮したスポンサードサーチの提案と評価
潘
献宇†
王
鑫‡
成
凱‡
†九州産業大学大学院情報科学研究科 〒813-8503 福岡県福岡市東区松香台 2-3-1
‡九州産業大学情報科学部 〒813-8503 福岡県福岡市東区松香台 2-3-1
E-mail: ‡[email protected]
あらまし
スポンサードサーチとは検索サービス利用者をターゲットとして，検索条件と一致する広告をスポンサードクリ
ックとして表示させ，クリックに基づき料金を徴収する検索連動広告の仕組みである．従来のスポンサードサーチでは，キーワ
ードの重要度を区別しない単純なキーワード設定方法しかなく適切なキーワード設定が困難である．本研究では，スポンサード
サーチのクリック率を高めるため，キーワードの重要度を考慮した柔軟なキーワード設定方式を提案し，それに適した広告検索
方式を開発する．また，実験によって提案方式が広告検索の精度の向上やクリック率の改善に有効であることを検証した．
キーワード
スポンサードサーチ，検索連動広告，辞書検索，Top-K 検索，ベンチマーク
Design and Analysis of a Sponsored Search with
Weighted Keyword Auctions
Xianyu PAN†
Xin WANG‡
and
Kai CHENG‡
†Graduate School of Information Science, Kyushu Sangyo University
‡Faculty of Information Science, Kyushu Sangyo University
2-3-1 Matsuda, Higashi-ku, Fukuoka, 813-8503 Japan
E-mail: ‡[email protected]
Abstract In this paper, a new sponsored search scheme is proposed for weighted keyword auctions.
Keyword Sponsored Search，keyword targeted advertisement，Dictionary Lookup，Top-K，Benchmark
1. は じ め に
データベースから取り出し，掲載順位を決めてスポン
インターネットの普及に伴い，ネットワークを経由
サーリンクの形で検索結果ページに表示させる．利用
した情報消費と情報発信が急速に広がり ，インターネ
者が掲載の広告コンテンツを消費した場合は広告料が
ット利用者をターゲットとするオンライン広告が新し
発生し，広告主に課金する．一般的に利用者がスポン
い 広 告 媒 体 と し て 確 立 さ れ つ つ あ る [8]．特 に ポ ン サ ー
サードリンクをクリックした場合にのみ課金する
ド サ ー チ (Sponsored Search)に 代 表 さ れ る 検 索 連 動 型 広
Cost-Per-Click（ CPC）方 式 が 採 用 さ れ て い る [3][4][5]．
告は注目を集めており大半の市場シェアが占められて
プロバイダーにとって，入札価格とクリック率とも
お り ， ラ ジ オ 広 告 市 場 と 並 ぶ 1,524 億 円 市 場 へ の 成 長
高いほど利益が高くなる一方，広告主が満足できなけ
が 見 込 ま れ る [9]．
れば長期的に顧客流失のリスクが 高くなる．広告主に
スポンサードサーチでは，検索サービスプロバイダ
とって，できるだけ多くの潜在顧客を獲得しながらコ
ー（ 以 降 ，プ ロ バ イ ダ ー ），広 告 依 頼 者（ 以 降 ，広 告 主 ），
ストが一定の範囲にとどまることが望ましい ．スポン
検索サービス利用者（以降，利用者）により次のよう
サードサーチサービスが順調に成長していくために、
にサービスが成り立っている．まず，広告主が広告対
プロバイダーと広告主の利害関係のバランスを保つ 必
象のコンテンツを用意し，関連するキーワードを入札
要がある．そのため，適切な情報を適切なタイミング
し，掲載依頼を行う．プロバイダー側では依頼を受け
で適切な利用者に発信し，クリック率を高めるだけで
て広告データベースに登録する．利用者が検索サービ
なく確実な広告効果が得られると期待され る．したが
スを利用するとき，検索キーワードに関連する広告を
って広告内容を適切に表すキーワード設定により，広
告内容と検索サービスの利用者との適切なマッチイン
際に広告が表示されるようになる．同一の広告は複数
グを実現することが必要不可欠である．
のキーワードで入札可能である．キーワードごとに入
広告主がキーワードを設定する際に検索数の多い
人気キーワードを設定すれば広告が表示される確率が
札可能な最低入札価格があり，入札価格は，最低入札
価格以上の価格に設定する必要がある ．
高くなると想定される．しかし人気キーワードは必ず
キーワードは単語，フレーズ，単語リスト等の形，
しも「広告内容にとって最も適切なキーワード」とは
例 え ば ，「 エ ク ス テ ン シ ョ ン 」，「 女 性 向 け ウ ィ ッ グ 」，
言い切れない．利用者の情報ニーズに合わない内容で
「ウィッグ
あれば，広告をクリックしてくれなかったり，クリッ
示の順番は，入札価格だけではなく，クリック率など
クしても実際に購入や申し込みまで行いかなかったり
広告の品質も考慮して判断される ．
検 索 q に 関 連 し て 広 告 {a 1 , a 2 , … , a n }が 1,2, … ,n の 順
すると，広告効果が薄く，無駄な広告料金を払うこと
になる．
医療用」のいずれも可能である．広告表
で 検 索 結 果 画 面 に 表 示 さ れ た と す る ．期 待 の 収 益 R は
次のように求められる．
n
R   ctr (q, ai )  cos t (q' , ai , i)
(1)
i 1
ここでは，
図 1
Yahoo! JAPAN に お け る キ ー ワ ー ド 入 札
ctr (q, ai ) は 広 告 a i の 推 定 ク リ ッ ク 率 ，
cos t (q' , ai , i) は 入 札 キ ー ワ ー ド q ' に よ り 広 告 a i が i 番
目に表示されるときにかかる広告費を表す．入札キー
しかし，既存の方式の問題点として，同じ広告また
広告グループに対して複数のキーワードやフレーズを
登 録 で き る も の の ， キ ー ワ ー ド や フ レ ー ズ の 間 に OR
関 係 と み な し ， 重 要 度 は 区 別 さ れ な い （ 図 1）． ま た ，
必須と思われるキーワードと，不要と思わるキーワー
ドの区別もできず，広告主にとって潜在顧客をターゲ
ットする適切なキーワード設定は困難である ．
本論文では，我々はスポンサードサーチにおけるキ
ーワード設定方式を改善するために， キーワードの重
要度を考慮したキーワード設計方式を提案する ．提案
のキーワード設定方式による新しいスポンサードサー
チの実現と評価を行う．
ワ ー ド q' と 検 索 キ ー ワ ー ド q は キ ー ワ ー ド マ ッ チ の ア
ルゴリズムによって必ずしも同じとは限らない．キー
ワ ー ド マ ッ チ に は 部 分 一 致 マ ッ チ (broad match)，完 全
一 致 マ ッ チ (exact match) ， フ レ ー ズ マ ッ チ
match)等 が あ る [6]．
2.2. 重 要 度 を考 慮 したキーワード登 録
キーワード登録をより柔軟に行えるために，我々は，
以下のような３種類キーワード を指定できるような方
式を考案する．
カテゴリ
必須
2. ス ポ ン サ ー ド サ ー チ お け る キ ー ワ ー ド 登 録
スポンサードサーチを利用する際に，広告主は検索
サービスプロバイダーに掲載対象ページに関連するキ
不要
ーワードを登録する必要がある．キーワード登録と同
重み付き
時にクリックごとに支払える料金などの条件も設定し
ておき，オークションにより検索条件と一致する複数
の広告から広告料金の高い広告を競争的に選出する ．
広告主がキーワードとともに掲載条件などを指定し広
-
-
札では，広告内容（タイトル・説明文）とリンク先の
URL を 設 定 す る こ と で ，関 連 キ ー ワ ー ド が 検 索 さ れ た
130
125
80
必 須 キ ー ワ ー ド（ Must Keywords）
：検 索 条 件 に 最
不 要 キ ー ワ ー ド (Stop Keywords)：検 索 条 件 に 含 ま
れ て は い け な い キ ー ワ ー ド ．一 つ で も 含 ま れ た 場
キーワード入札とは広告主が広告内容に応じてキ
Cost-Per-Click）を 設 定 す る こ と で あ る ．キ ー ワ ー ド 入
1.京 成 線
2.不 動 産 紹 介
3.引 っ 越 し
まない検索は広告を表示させない．
2.1. キーワード入 札
に 対 し て 1 ク リ ッ ク 当 た り 支 払 え る 広 告 料 金 （ CPC：
表 1 提案キーワード登録方式
キーワード
入札価格
マンション
100
アパート
105
賃貸
120
分譲
低 一 つ 含 ま れ る 必 要 の あ る キ ー ワ ー ド ．一 つ も 含
告掲載を依頼することはキーワード入札 という．
ーワードを指定するとともに，それぞれのキーワード
(phrase
合は，広告を表示させない．
-
重 み 付 き キ ー ワ ー ド（ Weighted Keywords）：こ の
カ テ ゴ リ の キ ー ワ ー ド が 検 索 条 件 に 現 れ る と ，一
定 の 重 み を 加 算 す る ．重 み が 大 き い ほ ど ，適 合 す
る キ ー ワ ー ド 数 が 多 い ほ ど ，広 告 を 表 示 さ せ る 可
能性が高くなる．
同じ広告に対して、上記の３種類のキーワードを設
定できる。例えば、ある賃貸紹介サイトのキーワード
3. 平 均 入 札 価 格 に よ る 広 告 評 価
登 録 例 と し て 、 必 須 キ ー ワ ー ド 「 マ ン シ ョ ン 、 賃 貸 」、
不 要 キ ー ワ ー ド「 分 譲 」、重 み 付 き キ ー ワ ー ド「 京 成 線 、
提案のキーワード設定方式に合わせて ，広告検索及
不 動 産 紹 介 、引 っ 越 し 」を 表 1 に 示 す よ う に 登 録 し て
び広告掲載の方式について述べる ．利用者が検索条件
い る 。つ ま り 、検 索 キ ー ワ ー ド に 、
「 マ ン シ ョ ン 」か「 賃
を入力して検索サービスを利用するときに ，検索結果
貸 」の い ず れ か が 含 ま れ な い と 表 示 し な い 。ま た 、
「分
とともに表示すべき広告及びその掲載順位を決める必
譲」で検索されるときにも広告を表示しない。必須キ
要がある．本研究では，平均入札価格を使い，掲載順
ーワードともに、重み付きキーワードも含まれる場合
位を決める．
は、広告が表示されるチャンスが多くなる。
ちなみに、不要キーワードのみの登録や、同じキー
3.1. 総 入 札 価 格 と平 均 入 札 価 格
ワードを違う種類として登録できない。例えば、同じ
広告データベースに格納されている広告の集合
キーワードは同時に必須キーワードと不要キーワード
A={a 1 , a 2 , … , a n }と す る ． そ れ ぞ れ の 広 告 に 必 須 キ ー
として登録してはいなけない。同様に、同じキーワー
ワード，不要キーワード，重み付きキーワードが登録
ドは必須キーワードでもあるし、重み付きキーワード
されている．複数のキーワードが含まれる検索条件
でもあることができない。
Q={q 1 , q 2 , … , q m }で 広 告 を 検 索 し ，掲 載 順 位 を 決 め る ．
キーワードごとに入札価格が設定される。例えば、
q1, q2, … , qm の う ち 広 告 ai の 必 須 キ ー ワ ー ド ， 不 要 キ
必 須 キ ー ワ ー ド 「 マ ン シ ョ ン 」 は 100 円 、 重 み 付 き キ
ー ワ ー ド ， 重 み 付 き キ ー ワ ー ド は そ れ ぞ れ Ni， S i， Wi
ー ワ ー ド 「 不 動 産 紹 介 」 は 125 円 で あ る 。 広 告 が 掲 載
と す る ． ま た ， 広 告 ai の 必 須 キ ー ワ ー ド を 集 合 Mi と
される際に、クリックごとに実際に払うべき金額は検
し ， w i, j, ， cost j は そ れ ぞ れ W i の j 番 目 の キ ー ワ ー ド と
索条件によって平均入札価格を使い計算する。平均入
入 札 価 格 と す る ． こ の と き ， 広 告 ai の 総 入 札 価 格
札価格についてのちほど説明する。
(Aggregate Price)は 次 の よ う に 求 め ら れ る ．
ri   wi , j  cos t j
2.3. 優 先 順 位 から重 みへの変 換
広告主の負担を軽減するために重み付けの方法を
簡略化し，キーワードごとに重みを明示的に付けず，
優先順位のみ指定すればよい．システムによって優先
ま た 、 平 均 入 札 価 格 (Average Price)は 次 の よ う に 求
められる．
順位から重みの具体値に換算する．一つの広告に n 個
r i   wi , j  cos t j /  wi , j
の キ ー ワ ー ド が 1,2, … ,n の 順 に な っ て い る と す る ． こ
j
のとき，順位 i の重みは次のように求められる．
wi  e1i / 
(2)
e は自然対数の底，λはパラメータとする．重みは
キーワードの数と関係のないようになっている ので，
(3)
j
(4)
j
例えば，広告 a に含まれる検索条件 q の重み付きキ
ー ワ ー ド は 順 位 1,3,4 の 三 つ あ り 入 札 価 格 は そ れ ぞ れ
100,110,80 と す る ． こ の と き ， 広 告 a の 総 入 札 価 格 と
平均入札価格は以下のように計算する．
パラメータλが決まれば，順位毎の重みが固定するの
r = 2.46 ∗ 100 + 2.01 ∗ 110 + 1.82 ∗ 80 = 612.7
で，あらかじめ計算しておけば，必要なとき参照すれ
2.46 + 2.01 + 1.82 = 6.29
ば よ い ．表 2 は λ =10 の と き 各 順 位 に お け る 重 み を 示
𝑟̅ = 612.7/6.29 = 97
している．
提案方式における広告検索と掲載は次のように行う。
i
wi
表 2
1
2.46
掲 載 順 位 か ら 重 み へ の 変 換 表 （ λ =10）
2
3
4
… 9
10
…
2.23 2.01 1.82 … 1.11 1.00 …
1.
検 索 条 件 と 一 致 す る 広 告 の う ち 、総 入 札 価 格 の 高
い K 個の広告を検索する。結果は集合 A とする。
2.
平 均 入 札 価 格 の 高 い 順 で 、広 告 の 掲 載 順 位 を 決 め
る。
また、次章で述べるように掲載順位を決めるために
必須キーワードを特殊な重み付きキーワードとして扱
う 。公 式 (2)で は 、必 須 キ ー ワ ー ド は i=0 の 重 み（ e =2.72）
3.
平均入札価格をベースにクリック単価を決めて
課金する。
ただし、必須キーワードしか登録していない広告は，
を持つとする。つまり、必須キーワードは重み付きキ
これまで通りに広告検索，掲載順位を行えるとよい．
ーワードより大きな重みをもつ特殊な重み付きキーワ
つまり，入札しているキーワードのうち，入札価格の
ードである。
高いものを一つ選んで評価し，掲載順位を決める．
ベ ス ト 順 位 の 次 の 行 か ら 調 べ て い く ．原 理 が BPA と 同
じ で あ る が ，調 べ た デ ー タ を 重 複 に 調 べ る こ と が な い ．
3.2. 広 告 の Top-K 検 索
大量の広告から総入札価格の高い K 個を求める問題
は Top-K 検 索 ア ル ゴ リ ズ ム を 用 い て 解 決 で き る ．Top-K
4. 実 験 評 価
検索とは m 個の順序付きリストから総合的重みが最も
大きな K 個を探し出す問題である．
重み付きキーワードにより，検索の精度が高まり，
広告検索の場合は，m の検索キーワードに対してそ
れぞれの
pi , j  wi , j  cos t j を 求 め 並 べ 替 え て ， 図
2
に示すような m 個の順序付きリストが得られる．
順
List 2
List 1
0
a4
230
1
3. 30a 2
182
2. 9 0a
7
245
5. 0 0a
1
100
2
2. 70a 3
165
2. 4 0a 4
182
3. 3 0a 7
92
3
2. 00a 5
4
1. 30
82
5
a0
p2
広告
250
1. 90a 8
149
1. 40a 2
100
1. 0 0a 5
82
a3
p2
130
1. 7 0
0. 50
図 2
順 序 付 き リ ス ト の Top-K 検 索
Top-K 検 索 を 効 率 的 に 行 う た め に ， FA， TA， BPA,
BPA-2 等 の 有 名 な ア ル ゴ リ ズ ム が 知 ら れ て い る [7] ．
BPA ア ル ゴ リ ズ ム は 以 下 の よ う に 、総 入 札 価 格 の 高 い
K 個の広告を検索する．
m 個 リ ス ト に 対 し 先 頭 か ら 同 時 調 べ て い く ．こ れ
1.
まで触れたことのない新たな広告 a があるリスト
に現れた場合は，広告 a の存在をほかのリストに
も 確 認 し ，存 在 す る 場 合 は ，そ こ の 順 位 と 重 み を
取得したうえ a の重みの合計を求める．
こ こ ま で 調 べ た 広 告 の う ち ，総 合 重 み の 最 も 大 き
2.
な k 個 を 集 合 Y と し て 保 持 す る ．さ ら に こ こ で 調
べた順位とそこの重みの合計も記録しておく ．
リスト i のこれまで調べたことのある順位が１位
3.
実験では，従来のキーワード登録方式と重み付きキ
リック率の変化を評価する．
広告
広告
では，この改善を実験より評価する結果を報告する ．
ーワード登録方式でよって，同じ検索を行う際に，ク
List 3
位
p1
クリック率の改善につながることが期待される ．本章
か ら 連 続 し て い る 最 大 の 順 位 を ベ ス ト 順 位 bp i と
し ， そ こ の 広 告 の 重 み を w i (bp i ) と す る ． さ ら に
  i1 wi (bpi ) ． Y の 要 素 の う ち 総 重 み が λ よ
m
り 低 い も の が な け れ ば ，ア ル ゴ リ ズ ム が 終 了 ．そ
うでなければ，１へ戻って繰り返す．
ベスト位置以下に広告が残っても，総重みがλ以下
な の で Top-K の 対 象 外 で あ る 。逆 に 集 合 Y に あ る 広 告
の 総 重 み が λ よ り 大 き い の で Top-K の 対 象 と 判 断 で き
る．
BPA-2 ア ル ゴ リ ズ ム で は ， 1 へ 戻 っ て ア ル ゴ リ ズ ム
を 繰 り 返 す と き ，表 の 一 行 一 行 で 調 べ る こ と で は な く ，
4.1. テストベッドの構 築
実験のベースとして ，N 個の広告，M 個のキーワー
ドを考える．広告ごとにそれぞれ必須キーワード，不
要キーワード，重み付きキーワードをランダムに生成
しておく．広告ごとの重み付きキーワードに，入札価
格も設定しておく．
ク リ ッ ク 率 は ， 掲 載 順 位 （ Rank）， キ ー ワ ー ド の 特
性（ Length），販 売 業 者 (Retailer)，商 品 ブ ラ ン ド (Brand)
な ど の 要 素 に よ っ て 左 右 さ れ る [4][5]．本 実 験 で は ，広
告の掲載順位ごとにクリック率は一定と想定 する．図
3 は ア キ ュ ー ラ カ ス ト （ AccuraCast） 社 に 提 供 さ れ た
2009 年 の Google ア ド ワ ー ズ の 広 告 掲 載 順 位 ご と の ク
リ ッ ク 率 の 調 査 結 果 を し め し て い る [10]． 本 実 験 は 図
3 のような分布でクリック率を自動生成する．
9.00%
8.00%
7.00%
6.00%
5.00%
4.00%
3.00%
2.00%
1.00%
0.00%
1
図 3
3
5
7
9 11 13 15 17 19
掲載順位とクリック率の関係
4.2. 実 験 結 果
キ ー ワ ー ド 数 M=1,000，広 告 数 N=10,000 の 場 合 で 評
価実験を行った．検索条件は次のようにランダム生成
し て い る ． 検 索 キ ー ワ ー ド 1 個 の 条 件 を 1,000 セ ッ ト
キ ー ワ ー ド 数 が 2～ 5 の 条 件 そ れ ぞ れ 10,000 セ ッ ト を
生成し，検索キーワード数が 1 個の場合と合わせて
41,000 セ ッ ト の 検 索 キ ー ワ ー ド で 実 験 を 行 っ た ．
実験結果は図 4 に示している．図 4 の横軸はクリ
く，提案方式の有効性を確認できたといえる．
ック率の改善範囲，縦軸はその範囲の広告数を示して
い る ． 例 え ば ， 横 軸 4％ の と こ ろ ， ク リ ッ ク 率 の 改 善
は 2~4%の 広 告 数 は 10,000 個 の う ち 3,093 個 で あ る ．
終わりに
0% だ け ， ク リ ッ ク 率 が 変 わ ら な い 広 告 数 で あ る ． こ
本論文では我々はスポンサードサーチにおける新
の実験結果からみて，広告数がある一定規模の場合で
しいキーワード設定方式及びそれに関する広告評価 方
は，提案手法は効率よく検索できることが分かった ．
式を提案した．重み付きキーワードの優先順位から重
みへ変換の方法や平均入札価格による広告評価，順序
3500
3000
2500
2000
1500
1000
500
0
3093
リ ス ト の Top-K 検 索 に よ る 効 率 的 な 実 装 技 術 を 検 討 し
た．実験によって提案方式のクリック率が改善できた
2281
1248
と確認した．
今後の課題として，掲載順位に加え，キーワードの
1192
991
785
特性，販売業者，商品ブランドなどの要素を考慮した
212 62
1
0 135
場合への対応やコンバージョン率を評価する仕組みの
検討等が挙げられる．また，大規模の広告データベー
ス に お い て ，平 均 入 札 価 格 の 計 算 や TOP-K 検 索 の 効 率
的な方法を検討する必要がある ．
図 4 クリック率改善の実験結果
5000
4364
4000
広 3000
告
数 2000
1000
1021
0
1
既存手法
2
提案手法
図 5 一度も表示されない広告数
25%
良くなった
68%
8%
同じ
悪くなった
図 6
クリック率改善の割合
図 5 は 提 案 手 法 に よ り 、一 度 も 表 示 さ れ な い 広 告 の
数 の 減 少 結 果 を 示 し て い る 。さ ら に 、図 6 は ク リ ッ ク
率が改善した割合とそうではない割合を示している．
結 果 と し て ，ク リ ッ ク 率 は 改 善 で き た 割 合 は 68％ と 多
参
考
文
献
[1] B. J. Jansen and M. Resnick, Examining Searcher
Perceptions of and Interactions with Sponsored
Results, Workshop on Sponsored Search Auctions at
ACM Conference on Electronic Commerce (EC'05)
2005
[2] [1] B. J. Jansen and M. Resnick, Factors Relating to
the Decision to Click on a Sponsored Link, Decision
Support Systems 44 (2007) 46–59
[3] Daniel C. Fain, Jan O. Pedersen, Sponsored Search:
A Brief History, Bulletin of the American Society for
Information Science and Technology, Vol. 32, Issue 2,
pp. 12–13, December/January 2006
[4] A. Ghose, S. Yang, An Empirical Analysis of
Sponsored Search Performance in Search Engine
Advertising, WSDM '08, pp.241-250, 2008
[5] D.
Hillard,S. Schroedl,
E.
Manavoglu,
H.
Raghavan,C. Leggetter, Improving Ad Relevance in
Sponsored Search, WSDM '10, pp.361-369, 2010
[6] A. C. König, K. Church, and M. Markov. A Data
Structure for Sponsored Search. In Proceedings of
the 25th IEEE International Conference on Data
Engineering (ICDE 2009), pp.90 -101, 2009
[7] R. Akbarinia, E. Pacitti and P. Valduriez. Best
Position Algorithms for Top-K Queries, In
Proceedings of VLDB 2007, pp. 495 -506, 2007
[8] 戸 田 淳 ， わ が 国 に お け る イ ン タ ー ネ ッ ト 広 告 の
歴 史 的 変 遷 と そ の 本 質 ， 情 報 文 化 学 会 誌 17(1),
49-54, 2010-09-07
[9] イ ン タ ー ネ ッ ト 検 索 エ ン ジ ン の 現 状 と 市 場 規 模
等 に 関 す る 調 査 研 究 ，総 務 省 情 報 通 信 政 策 研 究 所
調 査 研 究 報 告 書 ， 2009-08-20
[10] ア キ ュ ー ラ カ ス ト（ AccuraCast）, Google AdWords
Click Through Rates Per Position, 2009 -10-09
http://knowledge.accuracast.com/articles/adwords -cli
ckthrough.php