インターネットにおける広告戦略モデル
有坂 昌樹
指導教員 合原 一幸 教授

2007 年 2 月 5 日
πi は一般には未知であるが, 本研究では既知として扱う.

1 はじめにpi も一般には未知である. 本研究ではこの pi をまずはインターネット広告の世界において, 検索エンジンで既知の場合として扱い, 近似アルゴリズムを提案する.

検索されたキーワードに合わせてテキストなどを表示さそして, この既知の場合の結果を用いて, pi が未知の場れる広告形態である検索連動型広告が急激な広がりを見合におけるアルゴリズムを提案する. 各パラメータは tせている.

に関して一定とする. また, 本研究において, 一期間の予算を 1 として ci と πi を標準化する.

検索連動型広告の研究にはサービス側の視点からの研究と広告主側からの研究がある. 広告主側の研究は広告先行研究 [1] において, pi が既知の場合は以下のよう主の収益最大化が大きな目的である. この研究分野の目に定式化されている.

的の一つはキーワード集合を選択することによる最適化

E[ZA ] =である.

∑i∈A

本研究は, 広告主の収益が上がるようにキーワード集

πi λi pi∞∑)][ (E 1 BrA ≥ ci , S ≥ r . (1)r=1

ここで BrA は A ⊆ {1, . . . , N } に入札したときに, r 番合を適切に選択する方法を提案する. 既存の研究 [1] で目の検索が行われたときの残りの予算を表し, S は一期は, 過去の観測結果を元に利益対コストの比が大きい順間の総検索回数である. この S は平均 µ の確率分布に従にキーワードを選択していくアルゴリズムが提案されてうものとする. 各 i で pi = 1 のとき式 (1) が Stochasticいる. 本研究ではこれと同様に, 選択するキーワードのKnapsack Problem に帰着でき, NP 完全であることが個数を改良することにより, 理論的に近似率を向上させ示されている.

ることに成功した. また, 数値実験を行った結果, 収益を12.7% 上昇させることに成功した．

3 研究結果[1] では, この問題に対して以下の仮定を導入している.

2 目的と定式化(a) キーワードの添え字は π1 /c1 ≥ π2 /c2 ≥ · · · ≥本研究では, 広告主が検索連動型広告に一定期間広告
キーワードは N 個あるものとし, {1, . . . , N } を入札可

πN /cN の順に並んでいるものとする.
∑N(b) µ i=1 ci pi λi > 1.

能なキーワード集合とする. 本研究の目的は, 各期間 t =(c) 全ての i に対して ci ≤ 1/k かつ λi µ ≤ k α を満たすを出稿することを考える. まず広告として入札できるようなある k ≥ 1 と 0 ≤ α < 1 が存在する.

1, 2, . . . , T で入札するキーワード集合 At ⊆ {1, . . . , N }を適切に選択することによって, 広告主の収益 ZAt の期待値の総和

この仮定の下, キーワード集合 P ⊆ {1, . . . , N } を提案さ

∑Tt=1 E [ZAt ] を最大化することである.

れている近似アルゴリズムによって選択することで, Z ∗(1 回の検索でどのキーワードが検索されるかという確)

2
1− k(1−α)/3Z∗ ≤を最適収益とすれば, ρ 1 − k(1+2α)/3率を λi で表す. また, 各キーワード 1 ≤ i ≤ N に対し

E [ZP ] ≤ Z ∗ となることが示されている. 但し ρ =て, 0 ≤ pi ≤ 1, ci > 0, πi ≥ 0 をそれぞれクリック率,

E [min{S, µ}] /µ であり, S がポアソン分布に従うなら√ば 1 − 3/ µ ≤ ρ ≤ 1 となる.

1 クリックあたりの広告料, 1 クリックあたりの期待収益とする. λi は検索連動型広告会社のサービスで各キー

これに対して, 本研究では, [1] の仮定 (c) をワードの月間検索回数を調べられるので推定できる. ま(c’) 全ての i に対して ci ≤ 1/k かつ λi µ ≤ k α を満たた, 広告料は広告主が設定するので既知として扱える.

すようなある k ≥ 1 と 0 ≤ α < 2/3 が存在する.

1

と変更し, (a),(b) は同様とした. これは [1] が調査した定理 2. (Gt : t ≥ 1) を提案したアルゴリズムによって生実データでも適応でき, また予算を十分に多く用意する成されたキーワード集合列とし, ρ = E[min{S, µ}]/µ とことで満たされる条件である.

する. そして, 1/k + 1/k 1−α + 1/k 1/3 + 1/k (1−α)/3 ≤ 1と仮定する. このとき, 我々の仮定の下で全ての T ≥ 1

我々は pi が既知の場合において以下の結果を示した.
これは先行研究における近似率の α = 0 の場合であり,に対して() PTi=1 γt M
32≥ ρ 1 − k1/3− k(1−α)/3− T −T,2 PIU−λi µ12I)
U32µIUi=1 λi µ/(1−eここで, M =+.
kkρ(1−1/k1/3 )PT

t=1 E[ZGt ]T Z∗

下界の上限を示したことになっている.
定理 1. k, α は我々の仮定を満たすとする. pi が既知であり, さらに 1/k + 1/k 1−α + 1/k 1/3 ≤ 1 とする.

PT

また, Z ∗ を最適収益とし, ρ = E [min{S, µ}] /µ, P ={1, 2, . . . , IU } と す る.
そ し て IU ≡ max{ℓ :∑ℓµ u=1 cu λu pu ≤ 1 − 1/k − 1/k 1/3 } とするとき,
(E[Z]

Gt
t=1[1] で 示 さ れ て い る 収 束 率 は≥
T Z∗PT)(4M
1i=1 γt− T , であり, 収
ρ 1 − k(1+2α)/3 − k(1−α)/3 −T

束率は改善されており, α = 0 のときに一致する. 図 1)3に数値実験の結果を示す.

ρ 1 − k1/3 Z ∗ ≤ E [ZP ] ≤ Z ∗ .

Profit of each period.

1500

また, クリック率が未知の場合において我々は以下のアルゴリズムを提案した.

• 初期化:– yi , xi をそれぞれキーワード i の累積表示回数と累積クリック回数とする. 全てのキーワード

Our Algorithm

1000

Previous Algorithm

5000i に対して, yi = xi = 0, クリック率の推定値

50100

150200Time period.

p̂0i = 1 とする.
– 時刻 t において, ランダムにキーワード集合を図1選ぶ確率を (γt = t−2 : t ≥ 1) とする.

数値実験による期待収益の比較. 条件は検索数を平均 40,000 のポアソン分布に従わせ,• アルゴリズム: t = 1, 2, . . . に対して,∑ℓt11cu λu p̂t−1≤ 1 − k1 − k1/3
– µ u=1− k(1−α)/3≤u∑ℓt +1t−1µ u=1 cu λu p̂u を満たすように ℓt を定める.

キーワードを 8,000 個, 予算を 400, 期間を 200としたものを 100 回繰り返した. 平均を実線で, 95% 信頼区間を破線で示している. 上側が我々の結果で, 下側が [1] の結果.

– θt を {1, 2, . . . , N } の中から一様乱数を用いてランダムに選ぶ.

– キーワード集合の決定変数 gt を{ℓt 確率 1 − γtgt =θt otherwise

4 今後の課題
本研究では ci , πi を一定として扱った. しかし, 実際,これらは変化するパラメータである. これらは掲載順位とする.

によって変動するし, また競争相手を考慮すると同じ掲– Gt = {1, 2, . . . , gt } とし, これらのキーワード載順位においても変動する. また πi を既知として扱っを入札する.

たが, 初めて広告を出稿する際には, 一般的には πi は未– 更新: Vit , Wit をそれぞれ期間 t におけるキー知である. 従ってこれらのことを考慮したモデルを構築

ワード i の表示回数とクリック回数とする. こすることが今後の課題となる.のとき, 全てのキーワード i に対して, yi ←yi + Vit , xi ← xi + Wit として{1,if yi = 0tp̂i = xi
yi , if yi > 0.

参考文献
[1] P. Rusmevichientong and D. P. Williamson, Proceedings of the 7th ACM Conference on Electronic
Commerce, 2006.

• 出力: キーワード集合列 (Gt : t ≥ 1).
このアルゴリズムの収束率を以下に示す.

2