On Bisubmodular Maximization - todo314 @ ウィキ

On Bisubmodular Maximization

• Ajit P. Singh, Andrew Guillory, Jeff Bilmes
• AISTATS 2012

概要

• 双劣モジュラ関数最大化問題を考える
• センサ配置・特徴選択への応用

単純双劣モジュラ

• $$ f:2^{2V} \to \mathbb{R} $$が単純双劣モジュラ$$ \iff $$
• $$ f(A,B) + f(A',B') \geq f(A \cup A', B \cup B') + f(A \cap A', B \cap B') $$
  • NOTE: 定義域がdisjointで無い
• g(S) := f(abs(S ∩ V1, S ∩ V2)) とかいう感じで書けるので、結構解ける

1. $$ |A| \leq k_1, |B| \leq k_2 $$
2. $$ |A|+|B| \leq k $$
3. $$ A \cap B = \emptyset $$
4. 上の組合せ

• 実際に解く時には象限毎に解けばOK
  • f(A,φ)を最大化するA*を求め、f(A*,B)を最大化するB*を求める、とか。

有向双劣モジュラ

• 大体は単純で良いので、理論的興味としてやる
• $$ f:3^{V} \to \mathbb{R} $$が単純双劣モジュラ$$ \iff $$
• $$ f(A,B) + f(A',B') \geq f(A \cap A', B \cap B') + f( (A \cup A') \setminus (B \cup B'), (B \cup B') \setminus (A \cup A') ) $$
• あまり自明ではない
• $$ f:3^{V} \to \mathbb{R} $$: 非負単調有向双劣モジュラ
• $$ f':2^{2V} \to \mathbb{R} $$: 非負単調単純双劣モジュラで、fと定義出来る所では値が同じ
• こういうf'があると、fの最大化が近似できる
• 象限ごとの最大化
  • 単純の場合みたいに解くが、ヒューリスティクスで近似保証無し

まとめ

• 思ってたより理論的な内容がたくさんあった
  • 適当にやれば最大化出来ると思っていた
• 色々な制約が結構あるなあ

AISTATS センサ配置 劣モジュラ 特徴選択

2016/11/27