2017/8/3 ERATO感謝祭SeasonIV Portfolio Optimization for Influence Spread 26th International Conference on World Wide Web大坂直人 東京大学複雑ネットワーク・地図グラフグループ研究協力者吉田您一NII & PFI複雑ネットワーク・地図グラフグループリーダπ = 0.2 ☎ + 0.3 ☎ + 0.5 ☎
規模と速度の飛躍個人の活動履歴のログータから学習して、予測・制御したい！グラフ上の最適化問題影響最大化[Kempe-Kleinberg-Tardos. KDD'03]拡散発生の早期検知[Leskovec-Krause-Guestrin-Faloutsos- VanBriesen-Glance. KDD'07]誤情報拡散の阻止[Budak-Agrawal-Abbadi. WWW'11]バイラルマーケティング[Domingos-Richardson. KDD'01] 18ヶ月で1200万人2 Influence Maximization影響最大化[Kempe-Kleinberg-Tardos. KDD'03] argmax  E[Aの引き起こす拡散のサイズ] A:|A|=k (確率的モデルに従う)劣モジュラ関数の枠組みで定式化→貪欲算法が(1 – e-¹)近似[Nemhauser-Wolsey-Fisher. Math. Program.'78] ▶効率的計算の追求▶異なるモデル▶新たな問題設定Q.そもそも期待値最大化でいいの？ 3
八とへのどちらがよいですか?よいリスク尺度の最適化が必要:(下方リスク尺度金融経済&保険数理の分野からValue at Risk (VaR) at α = α-percentile Conditional Value at Risk (CVaR) at α ＝最悪時α割合の期待値α :有意水準(典型的に0.01又は0.05)拡散のサイズ理論的・実用的に優れたCVaRを採用コヒーレント性、凸性、等5
影響最大化の考え方で甫一集合選択A = argmax CVaR α [Aの拡散サイズ]は解ける? A:|A|=k劣モジュラで無い多項式時間近似困難[Maehara. Oper. Res. Lett.'15]分散投資の考え方でπ = 0.2 ☎ + 0.3 ☎ + 0.5 ☎ポートフォリオ構築連続最適化分野での研究[Rockafellar-Uryasev. J. Risk'00] [Rockafellar-Uryasev. J. Bank. Financ.'02]挑戦：指数個の頂点集合に投資6本研究の貢献“拡散サイズのCVaRを最大化するポートフォリオ構築”の多項式時間近似アルゴリズムを提案影響最大化＝“拡散サイズの期待値を最大化する単一集合選択”計算機実験による評価
疎なポートフォリオを出力
[Zhang-Chen-Sun-Wang-Zhang. KDD'14] ▶ “(拡散のサイズのVaR) ≥閾値” [Deng-Du-Jia-Ye. WASA'15] ▶ “(#高確率でAに影響する頂点) ≥閾値” ▶近似保証無しロバスト影響最大化[Chen-Lin-Tan-Zhao-Zhou. KDD'16] [He-Kempe. KDD'16] ▶モデルパラメータが不確実▶ E[拡散のサイズ]を安定させる最大の違い：単一集合選択orポートフォリオ構築関連研究本研究
8
定式化拡散モデル独立カスケード[Goldenberg-Libai-Muller. Market. Lett.'01]グラフG = (V, E)辺確率p: E → [0,1]
211通りのランダムグラこの例では等確率で発生定式化拡散モデル独立カスケード[Goldenberg-Libai-Muller. Market. Lett.'01]グラフG = (V, E)辺確率p: E → [0,1] Rgの分布R A = Aから到達可能な頂点数これがAの拡散のサイズ定式化拡散モデル独立カスケード[Goldenberg-Libai-Muller. Market. Lett.'01]
Roの分布R A = Aから到達可能な頂点数E[Ra] = 2.4375全体の平均最悪時25%の平均CVaR0.25[Rq] = 1 11定式化k頂点ポートフォリオ('k')次元ベクトルπ  s.t. ||π||1 = 1例: k = 1, πα = πb = 0.5 〈π, R〉＝ παRα + πbRb
1.25 0.5×1 0.5×1 CVaR0.25[παRα+πьRb] ≥ παCVaR0.25[Rα] + πbCVaR0.25[Rb]優加法性12定式化問題定義入力: G = (V,E),  p,整数k, 有意水準α出力: k頂点ポートフォリオπ max  CVaR α [〈π, R〉] π T A R Aランダムグラフ上でAから到達可能な頂点数Δ π & Rは(ザル次元既存手法は適用困難13提案アルゴリズム概要CVaR最大化元の問題標準的変形[Rockafellar-Uryasev. J. Risk'00]サンプリング近似標本数のバウンドが必要巨大線形計画複雑な制約乗算型重み更新[Arora-Hazan-Kale. '12]最適化、機械学習、ゲーム理論等に出現感謝祭SeasonII [Hatano-Yoshida. AAA/'15] AdaBoost [Freund-Schapire. J. Comput. Syst. Sci.'97]制約の凸結合指数個の変数実は貪欲算法で近似的に解ける14提案アルゴリズム第一段階：標準的近似max  CVaR α [〈π, R〉] TT最適化問題としてCVaRを記述[Rockafellar-Uryasev. J. Risk'00] R¹, ..., R sをRの分布から標本1 AS max{τ — {π, R'}, 0}実行可能性問題“□≥ γ?”を繰り返し解き、 γで二分法15提案アルゴリズムで「 |≥ γ?”判定の難しさar ≥ γ?” =巨大線形計画[ 1  CVaR記述のための補助変数max関数除去の補助変数X = | V k頂点ポートフォリオLTT- ∃? x ∈ P γ      Ax ≥ b #変数~ (lVl) #制約= s llポートフォリオを構築し“複数の劣モジュラ関数が同時に閾値以上” У1 + (π, R 1 ) ≥ τこれは難しいУs + (π, Rs) ≥ τ 16提案アルゴリズム巨大線形計画□の実行可能性の近似判定乗算型重み更新[Arora-Hazan-Kale. '12] ①凸結合[¯]をp = p¹, …, p¹について解く②平均の解～ ■の解ﾖ? x ∈ P γ   〈p, Ax〉≥〈p, b〉 #変数~ (|V|) #制約= 1 llポートフォリオを構築し“単一の劣モジュラ関数が閾値以上” 〈p, y〉+〈π, p ⊙ R 〉≥ τ発見:貪欲算法の解A*にだけ投資(π A* = 1)すると、〈p, Ax〉≥〈p, b〉− e−1提案アルゴリズムまとめ：精度と時間CVaR α [〈π, R〉] ≥ max CVaR α [〈π*, R〉] — |V | e − ¹ — |V | ε付加誤差最適値0(ε−6k²|V||E| polylog)時間厳密CVaR最適化||ランダムグラフ標本　s = 0(kε−4 polylog)サンプル経験CVaR最適化T = 0(ε−² polylog)ステップ貪欲算法0(k|V||E|)時間18は正►ネットワークデータ(その他の結果は論文に記載) Physicians friend network (|V| = 117 & |E| = 542) [Koblenz Network Collection] 1/3 Puv = (uの出次数)−1 ►パラメタ: ε = 0.4 ▶ベースライン:単一k頂点集合を出力
▶実験環境: Intel Xeon E5-2670 2.60GHz CPU, 512GB RAM
πは非常に疎!! (πの非ゼロ要素数) = 42 πの次元=   (10)   ≈ 1014
ポートフォリオ最適化による影響最大化の低リスク戦略の獲得
すると今後の発展▶高速化：巨大線形計画をより速く解ける？ ▶ CVaRの効率的近似▶他のリスク尺度：Value at Risk、下方部分積率、 21
2014影響最大化の高速化技法大坂-秋葉-吉田-河原林AAAI'14 2015分散制約最適化の新解法波多野-吉田AAA/' 15 2016動的グラフの実時間解析大坂-秋葉-吉田-河原林VLDB'16共通利用技術乗算型重み更新巨大グラフの小型化|大坂-薗部-藤田-河原林SIGMOD'17 2017影響拡散の厳密計算や前原-鈴木-石畠WWW'17ポートフォリオ最適化によるリスク回避大坂-吉田WWW' 17 WWW'17 Social 2 session
▶ #steps T in multiplicative weights alg. ▶ O (ε−²) [Arora-Hazan-Kale. '12] ▶ #samplings = #graphs = 0(ε− 4 ) ▶ Bound the error for the all portfolios
▶ Ax ≥ b ⇔
Submodular in A X = V auxiliary variable required for expressing CVaR auxiliary variables for removing max functions k-vertex portfolio 25 Our algorithm Linear programming formulation ] auxiliary variable required for expressing CVaR auxiliary variables for removing max functions X = k-vertex portfolio Polyhedron for “ [] ≥ γ? ” s constraints on yﾖ? x ∈ P x ≥ b Convex combination One constraint on v For p ∈ [0,1] ⁵ ﾖ? x ∈ P v Our finding: ☺ [_] can be approximated in poly-time Key : Original influence maximization [Kempe-Kleinberg-Tardos. '03] + Multiplicative weights alg. [Arora-Hazan-Kale. '12] ☺️We can approximately check L Our algorithm Approximately checking multiplicative weights algorithmﾖ? x ∈ P v 〈p, Ax〉≥〈p, b〉 Generate p 1 , solve for p 1 , & obtain x 1 Generate p 2 , solve for p 2 , & obtain x 2 Generate p 3 , solve for p 3 , & obtain x 3 x = average(x 1 , x 2 , x 3 ... ) [Arora-Hazan-Kale. '12]ﾖ? x ∈ P γ   Ax ≥ b × E P γ & A × ≥ b − 1 ε [Arora-Hazan-Kale. '12] Our algorithm Approximately checking greedy algorithm日? x Ｅ Py 〈p, Ax〉 ll “ A single submodular function exceeds a threshold " The greedy algorithm achieves 〈p, Ax〉≥〈p, b〉− e−1ﾖ? x ∈ P γ Ax ≥ b ll “ Multiple submodular functions exceed a threshold simultaneously " Our algorithm So, what we can do finally?
ﾖ? x ∈ P γ   Ax ≥ b − e−¹ − ∈ me (# p's) · (Time of greedy alg.) = 0(ε−²k|V||E|s log s) Properly setting s & # bisection searches See our paper for details W.h.p.Your algorithm produces π s.t. CVaR α ((π,X)) ≥ m x CVaR α ((π*,X)) — e−1 — ε in time Õ(ε−6k²|V||E|) NOTE : Õ(ƒ) = O(ƒ logc ƒ)
CVaR has ▶ Monotonicity ▶ Translation invariance ▶ Concavity Running time Physicians dataset |V| = 117 & |E| = 542
Advogato dataset |V| = 5,042 & |E| = 78,454
31 Experiments Results for k = 1 & α = 0.01
(# non-zeros in π) =  10 = 117 dim. of π =   ( l V l ) 33
Summary Optimizing exact CVaR Sampling Optimizing empirical CVaR Feasibility “🌸≥ γ” Linear programming Easier to solve Convex combination Sol. Greedy strategy works!! Error is bounded )) Sol. Bisection search on γでSol. Nice application of multiplicative weights alg!!  : 35