Robust Influence Maximization Chen+
Robust Influence Maximization
-
Wei Chen, Tian Lin, Zihan Tan, Mingfei Zhao, Xuren Zhou
-
KDD 2016
概要
-
最悪時比を最大化したい
-
解依存バウンド
-
パラメタ空間をいい感じに狭めるサンプリング手法提案
-
実際、パラメタ空間が大きいと解が良くないので提案手法が効果的
問題定式化
-
パラメタ空間 $$ \Theta = \times_{e \in E}[l_e, r_e] $$
-
頑健比 $$ g(\Theta, S) = \min_{\theta \in \Theta}\frac{\sigma_\theta(S)}{\sigma_\theta(S_\theta^*)} $$
-
問題 $$ S_\Theta^* = \mathrm{argmax}_{S \subseteq V, |S|=k} g(\Theta, S) $$
-
信頼区間の解釈に仕方
-
推定した確率ベクトル$$ \hat{\theta} $$と摂動レベル$$ \delta_e $$がある
-
$$ p_e \in [\hat{p}_e-\delta_e, \hat{p}_e+\delta_e] $$と思う
-
課題
-
Θ(でかすぎ)をそのまま使うと頑健比が微妙
-
代わりにΘ'を使って良い感じにしたい
-
サンプリングして(したと思って)$$ \Theta' $$と解$$ S' $$を得る s.t.
-
$$ \theta \in \Theta $$ w.h.p.: 真値θが含まれやすい
-
$$ g(\Theta', S') $$大: 頑健比が良い
提案手法
-
θは知らない、とりあえずΘの下で最適化する(サンプリングは後回し)
$$ \textsf{LUGreedy} $$ (Lower-Upper Greedy Algorithm)
-
$$ \theta^- / \theta^+ $$で貪欲して解を2つ得る
-
$$ \sigma_{\theta^-}(\cdot) $$で見て良い方を返す
-
定理2:
-
$$ g(\Theta, S_\Theta^{\textsf{LU}}) \geq \alpha(\Theta)(1-\mathrm{e}^{-1}) $$
-
$$ \alpha(\Theta) := \frac{\sigma_{\theta^-}(S_\Theta^{\textsf{LU}})}{\sigma_{\theta^+}(S_{\theta^+}^g)} $$
-
ギャップ比: α(Θ)=(LUGreedyで最適化した影響力)/(最も高い(と思しき)影響力)
-
こいつの評価は簡単
-
割とそれっぽい尺度です
-
ただし、最悪時頑健比はマジでやばい(頑張る意味が無いレベル)
-
Θを改良するためサンプリング
頑健比
-
定理3
-
仮定無: 頑健比=O(n/k)
-
弱い仮定: 頑健比=O(log n/n)
-
色々仮定: 頑健比の期待値っぽい奴=O(log n/√n)
-
2つのERグラフからなるグラフだと、どう選んでも死ぬ
サンプリング手法
-
Uniform Sampling $$ \textsf{US-RIM} $$
-
"max|確率の差|<δ→|影響力の差|<mnδ"とかそういう感じの保証
-
各辺をt回サンプリングして推定した$$ (p_e\pm \delta_e)_e $$でLUGreedy
-
Non-uniform & Adaptive Sampling $$ \textsf{ICS-RIM} $$
-
大事そうな辺を重点的にサンプリングする
-
重点的: 今ある解からシミュレートして見た辺
実験
-
US-RIM, ICS-RIM, OES-RIM(シードの出辺だけサンプリング)を比較
-
頑健比の上限
-
どれかθを(ヒューリスティクスで)決めて、上限をとれる
-
いい感じでしたねー、不確実性が頑健比にクリティカルに影響しますね―等
まとめ
-
こういう解依存のバウンドと、そのパラメタの解析でいい感じに何か出来るんかな
KDD 影響最大化 頑健最適化
2016/12/11
最終更新:2016年12月12日 18:44