Upgrade to Pro — share decks privately, control downloads, hide ads and more …

論文読んだ「Simple and Deterministic Matrix Sketching」

論文読んだ「Simple and Deterministic Matrix Sketching」

Shinichi Takayanagi

April 08, 2019

Transcript

24 slides
  1. Simple and Deterministic Matrix Sketching Edo Liberty (Yahoo! Labs )

    (KDD 2013, best research paper) 高柳慎一 @_stakaya 論文読んだ
  2. 本日のお持ち帰り • 近似精度の保証付で行列圧縮法を提案 • n x m の行列Aを l x

    mの行列Bへと圧縮 – l << n • 以下の量(分散的なもの)を良く近似させる • 理論保証あり 2
  3. 理論的な上限 • || ⋅ || はフロベニウスノルム • || ⋅ ||はスペクトルノルム(多分)

    • 削減する次元 lを決めると自動的に上限が決 まる(うれしい) 5
  4. Before we start • よく使う等式を示す – は行列Aの各行 –はiループでの行列B –はiループでの行列C •

    は−1 の全0な行に を挿入してVでぐ るっと回転させてるだけなので 7
  5. 上限の証明-1 8 xはATA − BTBの最大固有値の固有ベクトル ∑で 0, 以外は全部消える 0は零行列なのでやっぱりいらん 前Pの等式を代入

    Algorithmで 定義したΣを各々代入 − の真ん 中の(気持ち)√取って シュワルツの不等式 行列ノルムの定義 に従って頑張る アルゴリズムのここを見る
  6. データを読む • Kaggleからサンプルデータを落としてからの 16 library("h5") file <- h5file("C:¥¥temp¥¥usps.h5") x <-

    scale(file["train/data"][]) y <- file["train/target"][] > x[1:5, 1:6] [,1] [,2] [,3] [,4] [,5] [,6] [1,] -0.0692796 -0.124749 -0.1999769 -0.3113933 -0.4506665 -0.6198367 [2,] -0.0692796 -0.124749 -0.1999769 0.2073071 0.2038526 -0.3160401 [3,] -0.0692796 -0.124749 -0.1999769 -0.3113933 -0.4506665 -0.6198367 [4,] -0.0692796 -0.124749 -0.1999769 -0.3113933 -0.4506665 0.5364991 [5,] -0.0692796 -0.124749 -0.1999769 -0.3113933 -0.4506665 -0.5053164

More Decks by Shinichi Takayanagi

Other Decks in Science