Streaming Submodular Maximization: Massive Data Summarization on the Fly - todo314 @ ウィキ

Streaming Submodular Maximization: Massive Data Summarization on the Fly

• Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbas, Andreas Krause
• KDD 2014

概要

• ストリーム設定の単調劣モジュラ関数最大化
• ワンパスで1/2-ε近似
• 関数評価も無作為標本で近似
• 実験で爆速

アルゴリズム1: 最適値$$ \texttt{OPT} $$を知っている

• $$ \alpha \texttt{OPT} \leq v \leq \texttt{OPT} $$
• $$ \textbf{for } i = 1 \textbf{ to } n $$
  • $$ \textbf{if } \Delta_f(e_i \mid S) \geq \frac{v/2-f(S)}{k-|S|} \textbf{ and } |S|<k $$
    • $$ S \leftarrow S+e_i $$
• 主結果
  • Sはα/2近似解，k空間

証明

• 補題
  • アルゴリズム中の任意のSについて$$ f(S) \geq \frac{|S|}{k} \cdot \frac{v}{2} $$
  1. $$ S = \emptyset $$: 自明
  2. Sで成立を仮定
     • eを追加した要素: $$ \Delta_f(e \mid S) = f(S+e)-f(S) \geq \frac{v/2-f(S)}{k-|S|} $$
     • 仮定を代入して式変形
• Case1: $$ |S|=k $$
  • $$ f(S) \geq v/2 \geq \frac{\alpha}{2}\texttt{OPT} $$
• Case2: $$ |S|<k $$
  • $$ O = \{o_1, \ldots, o_k\} $$: 最適解
  • $$ o_i \in O \setminus S $$について
  • $$ S_i \subseteq S $$: o_iを拒絶した時のS
    • $$ \Delta_f(o_i \mid S_i) < \frac{v/2-f(S_i)}{k-|S_i|} \leq \frac{v}{2k} $$
  • $$ \texttt{OPT}-f(S) $$
  • $$ \leq f(S \cup O) - f(S) $$ …単調性
  • $$ \leq \sum_{1 \leq i \leq k} \Delta_f(o_i \mid S) $$ …望遠鏡＋劣モジュラ性
  • $$ = \sum_{o_i \in O \cap S} \Delta_f(o_i \mid S) + \sum_{o_i \in O \setminus S} \Delta_f(o_i \mid S) $$
  • $$ \leq \sum_{o_i \in O \setminus S} \Delta_f(o_i \mid S_i) $$
  • $$ \leq \sum_{o_i \in O \setminus S} \frac{v}{2k} \leq \frac{v}{2} \leq \frac{\texttt{OPT}}{2} $$
  • ∴$$ f(S) \geq \frac{\texttt{OPT}}{2} $$

• $$ \texttt{OPT} $$を知っている：厳しい
• $$ \max f(\{e\}) $$を知っている：現実的

アルゴリズム2: 余は$$ \max_{e \in V} f(\{e\}) $$を知っている

• $$ m = \max_{e \in V} f(\{e\}) $$
• 観察：$$ m \leq \texttt{OPT} \leq km $$
• vの値を[m, km]から「上手く」選んでアルゴリズム1を動かす
  • どれかのvはOPTに近い
• $$ \mathcal{O} = \{ (1+\epsilon)^i \mid i \in \mathbb{Z} \} \cap [m, km] $$
  • $$ |\mathcal{O}| = O(\frac{\log k}{\epsilon}) $$
  • $$ \exists v \in \mathcal{O} \ v \leq \texttt{OPT} \leq (1+\epsilon) v $$
  • この時，$$ (1-\epsilon)\texttt{OPT} \leq (1-\epsilon^2)v \leq v $$
  • だから，$$ (1-\epsilon)\texttt{OPT} \leq v \leq \texttt{OPT} $$
• 主結果
  • $$ (1/2 - \epsilon) $$近似
  • $$ O(\frac{k \log k}{\epsilon}) $$空間
• 1週目: $$ \max f(\{e\}) $$を計算
• 2種目: アルゴリズム2を実行
• ワンパス＋無知で(1/2-ε)近似可能か？

アルゴリズム3: 提案手法は$$ m = \max_{1 \leq j \leq i}f(\{e_j\}) $$を更新しながら解を構築する

• $$ \textbf{for } i=1 \textbf{ to } n $$
  • $$ m \leftarrow \max \{m, f(\{e_i\})\} $$
  • $$ \mathcal{O}_i \leftarrow \{(1+\epsilon)^j\} \cap [m, \color{red}{2km}] $$
  • $$ v \not \in \mathcal{O}_i $$な$$S_v$$を削除（空間計算量削減のため）
  • $$ \textbf{for } v \in \mathcal{O}_i $$
    • $$ \textbf{if } \Delta_f(e_i \mid S_v) \geq \frac{v/2-f(S_v)}{k-|S_v|} \textbf{ and } |S_v|<k $$

---

• $$ \textbf{return } \mathrm{argmax}_{v \in \mathcal{O}_n} f(S_v) $$
• 主結果
  • $$ (1/2 - \epsilon) $$近似
  • $$ O(\frac{k \log k}{\epsilon}) $$空間
  • ワンパス

何故$$ [m, 2km] $$なのか？

• $$ S_v $$が最強だったとする，つまりvを固定する
• どんな$$e_i$$が入って欲しかったかというと
• $$ \Delta_f(e_i \mid S_v) \geq \frac{v/2-f(S_v)}{k-|S_v|} $$
• 特に$$S_v=\emptyset$$の時には
• $$ f(\{e_i\}) \geq v/2k $$
• だから，$$ v \leq 2kf(\{e_i\}) \leq 2km_i $$まで広げたい

関数評価

• $$ f(S) = \frac{1}{|V|} \sum_{e \in V} f_e(S) $$
  • こんな感じだとする（k-meansっぽいのとかがそう）
• 全Vを舐めたくはないので，Vから標本して近似

実験

• Active set selection
  • $$ f(S) = \frac{1}{2}\log \det(I+\sigma^{-2} \sigma_{S,S}) $$
• Exempler based clustering
  • L(S): 各点から最近点∈Sまでの距離自乗和
  • $$ f(S) = L(\{e_0\}) - L(S \cup \{e_0\}) $$

まとめ

• ストリーム設定が最初は謎だったが，こうせざるをえないのかも
• カスケードの塊がストリームで来てどうこうするとかいう，specificなのを考えていた
• アルゴリズムはわかりやすいし，近似保証も良さ気に見える

KDD ストリームアルゴリズム 劣モジュラ最大化 劣モジュラ関数

2015/10/31