Fast Algorithm for the Lasso based L1-Graph Construction - todo314 @ ウィキ

Fast Algorithm for the Lasso based L1-Graph Construction

• Yasuhiro Fujiwara, Yasutoshi Ida, Junya Arai, Mai Nishimura, Sotetsu Iwamura
• VLDB 2016

概要

• L1-Graph + Lassoなグラフ構築手法がある
• とても遅いので高速化
  • 基本アイデアは正重みな辺の事前計算＋反復の高速化

Lasso based L1-graph

• Least absolute shrinkage and selection operator
• $$ \min_{\mathbf{w}_p} \frac{1}{2M}\| \mathbf{x}_p - \mathbf{X} \mathbf{w}_p \|_2^2 + \lambda\|\mathbf{w}_p\|_1 $$
  • $$ \mathbf{w}_p $$がpに接続する辺の重みに対応していて、L1正則化のおかげで割りと疎になる
• 関連…L1-graph、k-NN graph等

Coordinate Descent

• 正則化項の偏微分が無理ゲーなので、頑張って解く
• 割りと単純な反復手順になる（lasso一般の手法）
• でもぼちぼち遅い、特に全頂点についてやるには

提案手法

• Weight updates
  • そもそも重みが零の要素がある
  • KKT条件スコアが分かれば大体判定が出来る
    • 見積もるのが大変なので、（いつものように）上下限で推定
  • 他にも少し高速化
• KKT条件スコアの上下限
  • X（入力; 高次元ベクトルデータ）をSVD分解しておく
  • 最初の時点で推定可能
  • 逐次的に改善も可能（要素当り定数時間）

実験

• 競合手法(?) [Fujiwara-Ida-Shiokawa-Iwamura. AAAI'16]
• 速くなりました結果も同じ
  • 数万点～数百万点、数百次元～数千次元
  • 数時間～数十時間
• 事例紹介
  • L1-graph [Cheng-Yang-Yan-Fu-Huang. IEEE Trans. Image Process. 2010]
  • Linear neighborhood graph [Wang-Zhang. IEEE Trans. Knowl. Data Eng. 2008]
  • とかと比較して、実際的に有用ですね～。

まとめ

• k-NNしか知らなかったので、グラフ構築手法として参考になった（あまり関係なし）
• 手法自体はいつもの感じ
• λ変えていったらどうなるんですかね？

VLDB lasso グラフ構築

2017/04/17