The Power of Optimization from Samples - todo314 @ ウィキ

The Power of Optimization from Samples

• Eric Balkanski, Aviad Rubinstein, Yaron Singer
• NIPS 2016

概要

• 単調劣モジュラ関数を大量の標本データからその場で学習
• curvature制限時に多項式個のサンプルで近似比保証できる

動機づけと貢献

• 関数・信託のどちらにもアクセスできない
  • 情報検索ランキング、タギング、影響最大化
• 学習した関数が劣モジュラでも、最適化結果はめちゃくちゃ駄目
• 各集合がサイズkの$$ \{ (S_i, f(S_i)) \}_{i \in [m]} $$がもらえる
• 被覆関数でも辛いよ！（limitation of optimization from samples）
• $$ f(e \mid S) \geq (1-c)f(e) $$ならcurvature c
• $$ (1-c)/(1+c-c^2) $$近似達成

アルゴリズム

• 基本方針: $$ E_R[f_R(e_i)] $$を推定したい
  • ランダム集合に$$e_i$$を追加したときの効用
• $$ \hat{v}_i = $$ avg($e_i$を含む集合のf) - avg($e_i$を含まない集合のf)
• $$ \hat{v}_i $$の順にk要素$$S$$選び、curvatureで微妙に補正$$\hat{v}_S$$
• ランダム集合の期待関数値 $$ \hat{v}_R \approx E_R[f(R)] $$を推定
• $$ \hat{v}_S $$ or $$ \hat{v}_R $$の大きい方を返す
  • Rはこの時点で実際にサンプリング？？？
• $$ f(S) \geq (1-c) \sum_{i \leq k} E_R[f_R(e^*_i)] $$が大事
  • curvature、劣モジュラ性を使う

その他

• Hardness、実験あり

まとめ

• 設定・アルゴリズムが割と不思議でなんとも言えない…
  • すでにたくさん標本があるというのは…

NIPS OPS 劣モジュラ 影響最大化

2018/08/23