Optimizing query rewrites for keyword-based advertising
目的
広告をクリックするたびにインセンティブが入るモデル(pay-per-click)を考える．
クエリ(query)→クエリの書き換え(Rewrite)→広告(ad)からなる3層のグラフを考えて，収益を最大化するようなクエリの書き換えを提案する．
劣モジュラ問題として解く事ができるとかなんとか．
定義
クエリの集合とそのrewrite(書き換え)の集合
，及び広告の集合
からなる三層のグラフ
を考え，エッジを
及び
とする．
であるとき，クエリqはwに書き換えが可能であるとし，
は広告aは書き換えwにおいて表示されるものとする．
目的は収益を最大化するを求める事であるが，
のsubsetを求める事によって
は求まる．
はクエリ集合
における隣接要素の集合，つまりはrewriteの集合である．
はrewriteの集合における隣接要素，つまりはrewriteによって表示される広告の集合．
はクエリqにおいて広告aを表示したときに得られる収益（論文では書かれていないがついでに
とするとクエリqに対し広告集合Aを表示する場合の収益の集合の総和?）．
とする．つまりは要素数dの広告集合で得られる最大の利益(これをd-benefitと呼ぶ)．ついでに
でd-benefitを取る広告集合，つまりはargmax
を表す．同様に
で
から得られるd-benefitとする．
最後に，で
でrewriteのpairの集合によって得られる収益とする．
制約
これだけじゃ制約が全く無いので次に2種類の制約を考える．
Cardinality version
Weighted version
ついでに重み付き(weighted?)の場合を考える．何かというと，budgetとtrafficなる制約を考える．これ何かと言うとクエリから広告に流れる分がtraffic，クエリの受け入れ可能数がbudgetみたいな状態．式で書くと広告aについてなるbudgetがあり，各クエリ
についてtrafficが
となり，この時
となる．
解く
Cardinality version
single query
まずはクエリが1つだけの場合を解く．を最大化するrewriteをgreedyに追加する．以下擬似コード．
def single_query_greedy(q, d, k) w_dash = [ ] while w_dash.size <= k w = argmax{|w| beta(q, d, gamma(w_dash + w)) } w_dash.push w w_origin.remove(w) end return w_dash end
general case
今度は一般化する．これも同様にgreedyに解ける．この時制約を忘れずに追加しておく．
Weighted version
ここが全くわからなかった．
budgetとtrafficが制約として加わっているのにgreedyに解けるという事もさておき，そもそも論文の擬似コードにbudgetとtrafficに関する制約が全く登場しない．普通にgreedyに解いている．
たぶん何か重要な点を読み飛ばしている気がする．integral ad allocatorでやるよと書いてあるのでまあガンガン追加はしていけるだろうけど，そもそもintegral ad allocatorでも判別必要なんじゃないのかと思うがその雰囲気すら無いのはわからない．
感想
グラフっぽい話かと思って途中まで読んでたらあんまグラフっぽい話じゃなかったので肩透かし．劣モジュラわからんのでそろそろどうにかしたいですねと思っていたら「Nagamochi and Ibaraki の最小カットで勉強しろや」と教えてもらえたのでそのうち．
