Stochastic Submodular Maximization: The Case of Coverage Functions - todo314 @ ウィキ

Stochastic Submodular Maximization: The Case of Coverage Functions

• Mohammad Reza Karimi, Mario Lucic, Hamed Hassani, Andreas Krause
• NIPS 2017

概要

• 確率的劣モジュラ最大化のための新しい手法を提案
  • まずは、被覆関数から
• 連続拡張をさらに緩和した問題を直接解いてから元に戻す

問題

• 目的関数 $$ f(S) = \mathbb{E}_{\gamma \sim \Gamma}[f_\gamma(S)] $$
  • 影響最大化なら、影響グラフからサンプルしたグラフ上で到達可能な頂点数
• 線形連続拡張 $$ F(\bm{x}) = \mathbb{E}_S[f(S)] $$
  • これのしかも凹緩和を考える

Stochastic Submodular Optimization

• まず、重み付き被覆関数を考える
• $$ g(T) = \sum_{u \in T}w(u) $$
• $$ f(S) = g(\bigcup_{B_i \in S} B_i) $$
• こいつの連続緩和と、さらに凹緩和を考える
  • 確率的に集合を選ぶので、各要素が勘定される確率を考えればOK
• $$ F(\bm{x}) = \sum_{u \in U}w(u)\Bigl(1-\prod_{B_i : u \in B_i}(1-x_i)\Bigr) $$
• $$ \bar{F}(\bm{x}) = \sum_{u \in U}w(u)\min\Bigl\{ 1, \sum_{B_i : u \in B_i}x_i \Bigr\} $$
• 不思議なことに… $$ (1-1/e)\bar{F}(\bm{x}) \leq F(\bm{x}) \leq \bar{F}(\bm{x}) $$
• $$\bar{F}$$は凹なので、project stochastic gradient ascentをすれば良い
  • 制約がマトロイドなら、基多面体に射影することが必要
  • 1/ε^2×諸々のパラメタ回の反復回数で(1-1/e)OPT-ε近似
  • 連続な$$\bm{x}$$を集合に丸めるには、(randomized) pipage-roundingをします
• アルゴリズム全体としては、勾配計算、射影、丸めがKEY
• いわゆる普通の貪欲と比べてk倍違うことになる

応用

影響最大化

• 上の議論は、個々の関数について適用すると考えるとわかりやすいかも
• $$ f_G(S) = Sから到達可能な頂点数 $$
• $$ F_G(\bm{x}) = \frac{1}{|V|} \sum_{v \in V} \Bigl( 1 - \prod_{u : u \mathrm{can reach} v} (1-x_u) \Bigr) $$
• $$ \bar{F}_G(\bm{x}) = \frac{1}{|V|} \sum_{v \in V} \min\{1, \sum_{u} x_u\} $$
• 確率的グラフ全体で期待値をとったFは、期待値の順番を交換するといいことが起きる：
• $$ \bar{F}(\bm{x}) = \mathbb{E}_{G \sim \mathcal{G}} \mathbb_{v \sim \mathcal{V}} \min\{1, \sum_{u} x_u\} $$
  • これは、部分グラフを固定したときに、一様ランダムに選んだ頂点に到達する確率（の上限）で、SODA'14と実質同じものになる
• random subgradientはAppendix
  • 逆BFSをするが、minのおかげで途中で打ち切れる！！

実験

• 比較手法：LazyGreedy、StochasticGreedy, Random
• 時間-関数値のトレードオフで比較、やったね！
• 反復回数は結構必要そう

まとめ

• 直接最適化しちゃうってのはオモシロイと思った
  • 今まで推定器を作ってその上で最適化するのに苦心していたので
• 特化した手法よりは遅い？

NIPS 劣モジュラ 影響最大化 確率的劣モジュラ 確率的最適化

2018/07/02