Non-monotone Adaptive Submodular Maximization
-
Alkis Gotovos, Amin Karbasi, Andreas Krause
-
IJCAI 2015
概要
-
これまでは単調だけ
-
非単調でも応用はあるので,1-1/e近似アルゴリズム作って実験
適応的な設定とは?
-
アイテムsの状態$$y_s$$が選択して初めて分かる
-
繰り返し:
-
アイテム選択
-
状態観測
-
状態$$\phi: V \rightarrow \mathcal{Y}$$
-
観察$$\psi = \{(s_1, y_1), \ldots, (s_\ell, y_\ell)\}$$
-
$$ p(\phi \mid \psi) $$は計算可能
応用例 [Golovin-Krause. '10]
-
センサ配置: センサが確率pで壊れている
-
影響最大化: 選択した頂点が伝えるかは選択しないと分からん
-
ベイズ的能動学習…大事らしい
-
ラベルが欲しいので,尋ねる
-
一次元&ノイズ無しなら,境界を二分探索すれば良い
-
目的関数 $$ f(A, \phi) $$
-
高さ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
最終更新:2016年06月01日 20:04