Online Influence Maximization
-
Siyu Lei, Silviu Maniu, Luyi Mo, Reynold Cheng, Pierre Senellart
-
KDD 2015
概要
-
辺確率情報はたいてい不完全か利用不可
-
確率の学習と影響伝播を同時に施行
-
今の情報からシード選択
-
宣伝開始
-
反応から確率更新
動機付け
-
オフライン: 辺確率が事前にわかっている
-
行動ログ自体が入手容易でない
-
オンライン影響最大化問題
提案手法
不確かな影響グラフ
-
入力
-
$$G=(V,E,p)$$
-
$$N$$: 試行数
-
$$k$$: シード数
-
出力
-
$$ S_1, \ldots, S_N (|S_i| \leq k) $$
-
目標
-
$$ \mathrm{maximize}\; \mathbb{E} \left[ | \bigcup_{i} I(S_i) | \right] $$
-
$$ \bigcup $$なのがちょっとクール
-
辺確率
-
β分布$$ B(\alpha_e, \beta_e) $$に従う確率密度関数
-
期待値: $$ \mu = \frac{\alpha}{\alpha + \beta} $$
-
分散: $$ \sigma^2 = \frac{\alpha \beta}{(\alpha + \beta)^2 (\alpha + \beta + 1)} $$
枠組み
-
ラウンド$$n = 1, \ldots, N$$
-
選択フェイズ$$ \texttt{Choose} $$
-
行動フェイズ$$ \texttt{Update} $$
-
実世界で実施
-
活性化頂点$$A_n$$・辺活性化試行$$F_n$$を元に確率更新
シード選択の戦略$$ \texttt{Choose} $$
ヒューリスティクス
Exploit-Explore(活用・探索)戦略
-
活用=普通に選ぶ
-
探索=他の方法で選んでグラフ情報を改善
-
ε-greedy
-
活用: 確率1-ε
-
$$ p_e = \mathbb{E}[P_e] $$と思う
-
探索: 確率ε
-
$$ p_e = \mathbb{E}[P_e] + \sigma_e $$と思う
-
直感: 分散がデカイところは（本当は高いのに）低いと見積もられているかも？→不確実性削減
-
問題1: εの設定が難しい
-
問題2: +σ_eがいつも良い選択は限らない
-
Confidence-Bound(信頼上限)
-
$$ p_e = \mathbb{E}[P_e] + \theta \sigma_e $$
-
θの値？
帰還に伴う確率パラメータの更新$$ \texttt{Update} $$
-
局所的: 2頂点間のパラメータ
-
$$\alpha_e = \alpha + \#\mathrm{SUCC}(e) $$
-
$$\beta_e = \beta + \#\mathrm{FAIL}(e) $$
-
大域的: 全体に関わるパラメータ
-
θの更新
逐次的アルゴリズム
-
大体の高精度手法は標本ベース
-
$$ F_n $$が小さいから影響小さい
-
枠組み
-
標本が欲しいクエリ発行
-
適当に使われていない標本を選択
-
再利用可能かの局所的・大域的チェック
-
OKならその標本を返す
-
NGなら新しく生成
-
スケッチベースの場合
-
スケッチ中の辺確率が変わらなければ，そのスケッチの出現確率は変わらない
-
局所的チェック: ↑をチェック
-
大域的チェック: α/(α+β)がそのスケッチ生成時とあまり変わってなければOK
実験
-
辺確率: $$ p_{ij} = 1/d_j $$
-
$$ | \bigcup_{n \in [N]}A_n | $$の最大化が目的
-
結構色々試している
-
CBがやはり良い
-
逐次的なのを導入すると影響拡散の値が結構悪くなる
まとめ
-
動機付けも手法もわかりやすくて，ストーリーが完結しててよかった
-
こういう情報拡散から見たら新しい枠組みを導入すると受けるんだろうなあ
-
辺確率の設定は1/入次数が主流らしい
KDD 不確かなグラフ 影響最大化 情報拡散
2015/10/08 1:33
最終更新：2015年10月08日 01:35
