Optimizing Budget Allocation Among Channels and Influencers - todo314 @ ウィキ

Optimizing Budget Allocation Among Channels and Influencers

• Noga Alon, Iftah Gamzu, Moshe Tennenholtz
• WWW 2012

概要

• 最適予算配分問題の定式化
• 二部グラフ的な広告マーケティングを広告媒体視点と顧客視点のそれぞれでモデル化
• ポイント
  1. 予算の配分という概念，今までは頂点を選ぶだけだった
  2. 影響の伝播は扱わない，予算の配分が主眼だから
• hardnessを解析

影響モデル

• G=(S,T,E)
  • Sはソース，Tはターゲット，Eは辺集合
• c_s (s∈S): 整数容量
• B: 予算
• 各ソースsに0以上c_s以下の整数予算b_sを割り当てる
• ただし，Σb_s≦B

Source-side influence model

• 各ソースsは確率ベクトルp^s=<p_1,…p_c_s>を持つ
  • sは繋がっているターゲットを独立に高々b_s回活性化させようとする
  • p_kは（どっかのターゲット）k回目で活性化に成功する確率
• sがtを活性化する確率はΠ_{1≦i≦b_s}(1-p_i)
• tが活性化する確率は
• $$ 1 - \prod_{s \in \Gamma(t)} \prod_{i=1}^{b_s}(1-p_i^s) $$
• <1,*,…,*>とかすると最大被覆になる

Target-side influence model

• 各ターゲットtは確率ベクトルp^t=<p_1,…,p_B>を持つ
• B_t = Σ_{s∈Γ(t)}b_s
  • sに割り当てられた予算をターゲットに渡して積算した感じ
• tが活性化する確率は
• $$ 1 - \prod_{i=1}^{B_t}(1-p_i^t) $$
  • B_tの関数

• 確率ベクトルに対する制約は何もなし
• 推定は…頑張れ

結果

Source-side influence model

• 多項式時間の1-1/e近似アルゴリズム
• 1-1/eより良くするのは難しい

アルゴリズム

• L≧3について
• 高々Lソース選び，可能な予算の割当を全部試す
• 高々|S|^L*B^L通り
• これを全列挙してから，残りのソースに予算を貪欲に配分
  • ゲインは定義してるけど長いの省略
• Q. 遅すぎだろ!?
• A. ふふふ
  • 空の状態から貪欲 + |S|個に全予算
    • |S|+1通り
  • 0.316近似

Target-side influence model

• もっとヤバイ
• maximum edge bicliqueとdense k-subgraphの拡張に相当する
• 激やば
• Ω(1/B^ε)の近似がすでに困難
  • 3-SATに関する予想の仮定のもとで

• 解析なげえ

まとめ

• この内容でWWWのAdvertising on the Webに通るってのがすごい
  • 物凄く理論的，実験もない
• モデリングは素直だし，ソース・ターゲット両方についてなのが面白い
• 理論的解析部分はちゃんと読まないとなあ
• ICML 2014のは確率ベクトルが単調減少なのだな
• あんまこっちはsubmodularしてない？

WWW 最適予算配分問題

2014-03-29 16:36:32 (Sat)