Dynamic Influence Maximization Under Increasing Returns to Scale - todo314 @ ウィキ

Dynamic Influence Maximization Under Increasing Returns to Scale

• Haifeng Zhang, Ariel D. Procaccia, Yevgeniy Vorobeychik
• AAMAS 2015

概要

• 時間が動的な設定
• 予算投入を途中で行う
• 活性化頂点: 時間に従い適当に増える，指数とか多項式とか
• 予算: 時間に従い指数的に増える
• 適当な設定では，ある時点に一斉投入（使い切る）のが最適
• そうでない場合はヒューリスティクス

導入

• ICモデルは劣モジュラ
• 最近は適応的劣モジュラ最大化もある
• しかし，Bassモデルのような古典的なモデルはS-shaped Curve
  • ここはミスリーディングで，劣モジュラは活性化集合に対してで，S-shapedは時間に対して．
• 時刻t+1の活性数が時刻tに依存
• ↑の関数が凸で，予算が指数関数的に増加する（活性化するコストが指数的に減衰）なら
• ある時点で使いきるのが最適

動的な影響最大化のモデル

• ネットワーク外部性…利用者が増えるともっと増える
  • イノベーションの選択者数だけを考える（ただの値）
• 選択のダイナミクス
  • 決定的
  • 一次Markov的
  • $$ D^t=f(D^{t-1}) $$
• fの仮定:
  1. 厳密に凸
  2. 狭義単調増加
  3. $$ f(D)>D \quad (D>0) $$
     • 3つは冗長ではない，一応．
• 活性化コストは一様（予算BでB人）
• もし予算が固定なら，即座に使えば良くね？
• →指数関数的に増加する予算
  1. 余った予算は金利δに投資
  2. 技術の発達で生産コスト⇩（活性化コスト⇩）
  • どっちも予算×α（みたいに思える）
• つまり，
• 時刻tで選択者$$D^t$$人，予算$$B^t$$の割合$$\alpha_t$$を使ったら
  • $$ D^{t+1} = f(D^t + \alpha_t B^t) $$
  • $$ B^{t+1} = (1+\delta)(1-\alpha_t)B^t $$
• 入力
  • 決定的T段階拡散モデル
  • 予算増加過程
    • ×δ等
• 出力
  • 方策 $$ \pi=(\alpha_0, \alpha_1, …, \alpha_{T-1}) $$
• 目標
  • $$ \mathrm{maximize} \ f(D^T) $$

提案手法

• 行動: その場で全部使う／少し使う
• 後退帰納法
  • DP的なことをする
  • O(DBT)時間 -- 遅すぎてやばお

最適アルゴリズム

• 0≦t≦T-1のどこかで全部使うのが実は最適
• T回目的関数を計算すればOK

ヒューリスティクス

• 前の手法は指数関数的な仮定が無いと最適でない
• しょーがないので，連続するK時間[i,j)に1/Kの割合で当てはめるヒューリスティクス
• O(T^2)回計算

実験

• 経費の減衰（予算の増加）を色々試す
• ネットワーク外部性…fで何倍増えるかを変える
• 指数的減衰
  • f=×1: 予算を最後まで増やして貯めておくのが良い
  • f=×1.75: 途中でやると良い
  • f=×2: 最初に使った方がめっちゃ拡散する
• 多項式減衰
  • 指数とあんまり変わらない
• 線形減衰
  • 一箇所でOK
• 線形+発見的学習
  • 累積選択者数に依存するほうが良さそう
  • 何か経費増えてない？謎

まとめ

• グラフ上の拡散かと思ったら違った(´・ω・｀)
• 予算は売上っぽいものを選択者数から何かイイ感じにモデル化できそうだが…
• 決定的だったので，途中まで良かったけど売れたり売れなかったりするような，
• リスクリターンまでを考慮した問題にすると面白いんでは？

AAMAS 影響最大化

2015/07/07 0:05