Lazier Than Lazy Greedy - todo314 @ ウィキ

Lazier Than Lazy Greedy

• Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrak, Andreas Krause
• CoRR

• AAAI-14に出したけど落ちたらしい
• このメンバーは劣モジュラ最大化マンっぽい
  • Andreas Krauseのサーベイがあったり，KDD14，SODA14に採択論文がある

概要

• 非負単調劣モジュラ関数最大化は関数をO(nk)回評価しないといけない
• Lazy Greedyとかもあるけど計算量は謎
• O(nlog1/ε)回の評価で1-1/e-ε近似の解を出力するRandomizedアルゴリズムを提案
• 実験的にもGood

Rand-Greedy

• 目的関数f:2^V→R+
• A←∅
• 以下をk回繰り返す
  • R←V\Aからs=(n/k)log(1/ε)個の要素をサンプリング
  • A << argmax_a∈R Δ(a|A)
• fの呼び出しは自明にnlog1/ε回
• Rから要素を選択するときに，Lazy Greedyが使える

実験

• 機械学習の何かに適用: nonparametric learningとexemplar-based clustering

比較対象

• Lazy-Greedy: 上界を使った枝刈り
• Sample-Greedy: 確率pでサンプリングしてLazy-Greedy
• Threshold-Greedy: [Badanidiyuru, Mirzasoleiman, Karbasi, Krause. KDD'14]
• Multi-Greedy: [Wei, Iyer, Bilmes. ICML'14]

結果

• ぱっと見
• 精度:
• Lazy-Greedyが最強（当たり前）
• 他の比較対象はそんなによくなさそう
• Rand-Greedyはεの最小値が実験ごとに異なるので何ともいえないが，よさげ
  • 割りとすぐ収束？
• 計算回数
• εを小さく0.001とかにしてもそれほど増えない
• RandはLazyに比べて3~10倍位速い？

解析

• 補題
  • 今の暫定解がAとする
  • Rand-Greedyの1ステップを適用後のゲインの期待値は
  • $$ \frac{1-\epsilon}{k}\sum_{a \in A^* \setminus A}\Delta(a\mid A) $$
• 証明のスケッチ
  • R∩(A*\A)≠∅となる確率を求めれば良い
  • (1-ほげ)^sの形になり，exp(-ほげ)で抑える
  • ちょっと変形すれば
  • Pr[R∩(A*\A)≠∅]≧(1-ε)|A*\A|/k
  • R∩(A*\A)な時は，A*\Aの要素を一様に含むので
  • E[Δ(a|A)]≧Pr[R∩(A*\A)≠∅]×(A*\Aに関するゲインの平均)
• 定理の証明
  • ゲインについて示したので後は元のGreedyに似た感じ

まとめ

• 滅茶苦茶シンプルでワ↓ロ↑タ↑
• Related workはチェックしておこう
• SODAのは比較なしかな？

CoRR submodular 良

2014/10/06