Non-monotone Adaptive Submodular Maximization - todo314 @ ウィキ

Non-monotone Adaptive Submodular Maximization

• Alkis Gotovos, Amin Karbasi, Andreas Krause
• IJCAI 2015

概要

• これまでは単調だけ
• 非単調でも応用はあるので，1-1/e近似アルゴリズム作って実験

適応的な設定とは？

• アイテムsの状態$$y_s$$が選択して初めて分かる
• 繰り返し:
  1. アイテム選択
  2. 状態観測
• 状態$$\phi: V \rightarrow \mathcal{Y}$$
  • 事前分布$$ p(\phi) $$は既知
• 観察$$\psi = \{(s_1, y_1), \ldots, (s_\ell, y_\ell)\}$$
• $$ p(\phi \mid \psi) $$は計算可能

応用例 [Golovin-Krause. '10]

• センサ配置: センサが確率pで壊れている
• 影響最大化: 選択した頂点が伝えるかは選択しないと分からん
  • ステップ毎に観測からシードを選ぶ
• ベイズ的能動学習…大事らしい
  • ラベルが欲しいので，尋ねる
  • 一次元＆ノイズ無しなら，境界を二分探索すれば良い

• 目的関数 $$ f(A, \phi) $$
  • アイテムの状態φのもとでの集合Aの価値
• 高さk以下の決定木$$\pi$$を決めて$$ \mathbf{E}_{\phi}[f(V(\pi, \phi), \phi)] $$を最大化
• 適応的劣モジュラ
  • $$ \psi_A \subseteq \psi_B $$で，
  • 観察$$\psi_A$$の元での増分の期待値$$ \geq $$観察$$\psi_B$$の元での増分の期待値

提案手法

• 単調適応的: 貪欲が(1-1/e)-近似 [Golovin-Krause. '10]
• 単調非適応的: 乱択貪欲が(1-1/e)-近似 [Buchbinder-Feldman-Naor-Schwartz. SODA'14]
• 非単調非適応的: 乱択貪欲が(1/e)-近似 [Buchbinder-Feldman-Naor-Schwartz. SODA'14]
• 今回は「非」単調
• [Buchbinder-Feldman-Naor-Schwartz. SODA'14]の乱択貪欲
  • 2k-1個のダミーアイテムを加える
  • 増分上位k頂点からランダムに解に追加
  • 謎すぎ
• 提案手法
  • ほぼ同じ
  • 適応的単調＋適応的劣モジュラ→1-1/e
  • 適応的劣モジュラ＋各点劣モジュラ→1/e

応用

• (元の目的関数)-(コスト関数)
  • 影響最大化: シード数がペナルティ（なんぞ？）
  • 最大カット: 選んだ点かその近傍のどれかが解に追加

まとめ

• 応用がうーんという感じ
  • 非単調な簡単な例が中々少ないとはいえ
• 適応的の範疇で何をだなあ

IJCAI 劣モジュラ関数 適応的劣モジュラ

2016/06/01