Risk-Sensitive Submodular Optimization - todo314 @ ウィキ

Risk-Sensitive Submodular Optimization

• Bryan Wilder
• AAAI 2018

概要

• 確率的連続劣モジュラ関数のCVaR最大化
• 非凹なので大変だが1-1/e近似可能
• 集合上のポートフォリオを構築できます

アルゴリズム

• 問題: $$ \max_{\vec{x}, \tau} \tau - \frac{1}{\alpha}\mathbb{E}_y[ [\tau-F(\vec{x},y)]^+ ] $$
• 難しさ
  • F(*,y)がxについて凹なら、CVaRは凹最適化
  • 劣モジュラ（2階微分が非正）の場合、そんなことはない
    • だけど、非負方向に凹（up-concave性）
• Frank-Wolfは使えるの？
  • 今の勾配から線形最適化を解いて一番遠いところを目指す
    • $$ \vec{x}^k = \vec{x}^{k-1} + \gamma_k (\vec{v}^k - \vec{x}^{k-1}) $$
  • up-concaveな関数にこの方法は使えない→毎回xが単調増加するように変更→1-1/e近似
• アプローチ
  • 経験的CVaRを最大化したい
  • 現xの勾配から線形計画信託
  • xを更新（$$ \vec{x}^k \leftarrow \vec{x}^{k-1}+\frac{1}{K}\vec{v} $$）
  • τを更新（これは単一パラメタの最適化で可能）
  1. 勾配の計算：微分不可で難しい、積分で近似
  2. 最適なτ：頑張るとできる
• 理論的解析：ゲキムズ
• 集合上のポートフォリオへ…
  • 多重線形拡張を使ってFで解いて丸める
  • [O.-Yoshida. WWW'07]との違い
    1. 劣モジュラ一般に使える
    2. 近似がいい感じ（相対誤差なので…）
    3. 近似が負にならない

実験

• 汚染検知みたいな問題

まとめ

• これは中々すごい
• 連続劣モジュラ関数なら、そのまま最適化できる

AAAI リスク回避最適化 劣モジュラ

2018/09/18