Scaling Locally Linear Embedding - todo314 @ ウィキ

Scaling Locally Linear Embedding

• Yasuhiro Fujiwara, Naoki Marumo, Mathieu Blondel, Koh Takeuchi, Hideaki Kim, Tomoharu Iwata, Naonori Ueda
• SIGMOD 2017

概要だけ

• LLE: 高次元データの可視化、２次元とかに
• 一般的な計算方法
  • 1. k-NNグラフ構築
  • 2. 辺重みを回帰で計算
    • ラグランジュの未定乗数法でまぁまぁ重い
  • 3. 固有ベクトルで埋込み
    • (I-W)^T(I-W)の固有ベクトルを固有値の昇順に求める、重そう
• 提案手法
  • 逐次的辺重み計算
    • 近傍が共通なことを利用
    • Woodbury formula
  • k-NNグラフ構築のための距離の下限
    • SVDで近似
  • LU分解ベースで固有分解
    • inverse power methodの適用逆行列が嫌だよ
• 実験
  • 厳密なまま早くなったよ

SIGMOD

2017/05/27