ざっと読んだ：Partner Tiering in Display Advertising（WSDM2014）

ざっと見たときにグラフ系+広告の話と思って読んでみたけど、グラフという程ではなかった感じ。これは広告に詳しい人の解説がほしいなぁ

ディスプレイ広告に関する論文。
広告配信システムは、契約を満たすように広告主の代理としてページに広告を配信し、配置の質を最大化することを試みている。
一般に、このようなものをモデル化する際には、オンライン上の配置問題として考えられる。
しかし、広告主と発行者の間の契約の常用な部分のほとんどが、これまでの数式では考慮されていない。それは、発行者が決まって媒介者(配信システム)として表され、広告主は媒介者から在庫を購入するからである。
発行者は質、重要性ともに様々であり、かつ広告の在庫は限られているので、広告配信システムとしては高品質の発行者を選んで行きたい。
そこで、この問題をそれぞれのimpressionがその重要性から導かれたレベルを持った、オンライン上の配置問題として定式化する。

広告配信の話
一般的には、プレミアムパートナーの在庫を抑えたとしても、広告主
の需要と比べてパートナーからの在庫が余る。

f:id:A_Koide0519:20140323010329p:plain

プラットフォームの目的
1)広告主の需要を満たす
2)プレミアムパートナーに対する高水準を保証する
3)在庫は、広告主毎に価値が異なるので、配分されたimpressionの価値を最大化する

具体的な在庫と広告のマッチングの例
x)プレミアムパートナーの広告を当てる。一方で広告主に対してプラットフォーム生成した総クリック数が最適でなくなる
y)CTRの高い広告を当てる。総クリック数は最大化されるが、CTRの低いプレミアムパートナーを捨てることになる
z)どちらも平等に当てる。

●定義
広告主: $A_1,...A_N$
広告主 $A_i$ は $N(i)$ 回impressionしてほしい
それに対してm人のパートナー $P_1,...,P_m$ が媒介者(配信システム)となる
パートナーにはプライオリティに基づいて1-Lまでのレベルがつく $L(P_i)$
オンライン上の設定ではj回めのimpressionを $L_j$ とする。
そしてimpressionはパートナーのレベルを引き継ぎそれを $L(j)$ とする。
$A_i$ と $L_j$ 間のCTRを $w(i,j) \in {0,1}$ とする。

●アルゴリズム
※DUAL-SCALEアルゴリズム
$weight(i,l)$ ...広告主 $A_i$ に割り当てられたレベルlのimpressionの総重み
$\gamma(i,l)=\frac{\sum_{j\leq l}weight(i,j)+\beta * \sum_{j>l}weight(i,j)}{N(i)}$
$L_j(j=l)$ が与えられたときにスコアが最大に成るのは以下の式を満たす広告主i
$argmax_{i}(w(i,j)-\gamma(i,l))$
$\beta$ は高水準なimpressionによって導かれるコブ(?)のようなもの。
$\beta=0$ の時、レベルl+1以上のweightを完全に無視する。
$\beta=1$ の時、各レベルを計算する一方ですべてのimpressionが広告社に平等に割当られる
この２つの特殊ケースに対する理論保証のはなしがつらつら。
※EW-SCALINGアルゴリズム
スケールファクター： $sc_1 \leq sc_2 \leq ...sc_L$
$\gamma(i)$ ...広告主A_iに割り当てられる、impressionの平均重み
$L_j(j=l)$ が与えられたときにスコアが最大に成るのは以下の式を満たす広告主i
$argmax_{i}(sc_l*w(i,j)-\gamma(i))$

●実験
３つの匿名の発行者を準備。各々の発行者に関して完全なimpressionのセットを収集。
各々のimpsに対して興味を持った広告主、CTR、impsのタイプがついている。また、
広告主に対して配信契約もついている。
impsのレベルに関しては1-10の間で３つの付け方を準備
1)impsのタイプ
2)80%の確率でimpsのタイプ、残りはランダム
3)ランダム
今回は1を採用
データセットも３タイプあって、impsの重複具合が異なる。
a)広告主が狙うimpsが1-わずかなレベルに分布
b)中間くらい
c)広告主が狙うimpsのレベルが各レベルでほぼ同じくらい
※評価
Fill-Rate...広告主に割り当てられたimpsの比率
Under-Delivery...全広告主の未処理のデマンド数
Over-Delivery...前広告主のあふれてしまったimps数
Total Weight of Matching...グラフの重み->広告主の総クリック数に成るはず

パラメータやデータセットを色々かえて実験しているが、評価指標やデータセット
ごとにそれぞれの提案手法が良かったりベースラインの方が良かったりしている。

結論もないので結局どれが良かったのかがよくわからない...!