Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
論文読んだ「Simple and Deterministic Matrix Sketching」
Search
Shinichi Takayanagi
April 08, 2019
Science
1.3k
1
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
論文読んだ「Simple and Deterministic Matrix Sketching」
Shinichi Takayanagi
April 08, 2019
Transcript
24 slides
Simple and Deterministic Matrix Sketching Edo Liberty (Yahoo! Labs )
(KDD 2013, best research paper) 高柳慎一 @_stakaya 論文読んだ
本日のお持ち帰り • 近似精度の保証付で行列圧縮法を提案 • n x m の行列Aを l x
mの行列Bへと圧縮 – l << n • 以下の量(分散的なもの)を良く近似させる • 理論保証あり 2
Matrix Sketching • Matrix Sketchingでは列ではなく行を削除 –皆大好きPCAは列を削除 • 直観的には頻出ベクトルを残す操作 –行空間(Not特徴量(列)空間)の基底探し的な –k-meansのクラスタ中心を残すイメージ
• Frequent Directionという手法を提案 3
Algorithm 4 O(nml)でいける (SVDがO(ml^2)で, n/(2/l)回やるので) 各行に対して逐次ループ
理論的な上限 • || ⋅ || はフロベニウスノルム • || ⋅ ||はスペクトルノルム(多分)
• 削減する次元 lを決めると自動的に上限が決 まる(うれしい) 5
その他のご利益 • オンライン更新OK –各行に対して独⽴に実行可能(for … in Algorithm) • 並列可 –行列Aを部分行列にばらして処理→その後Merge
6
Before we start • よく使う等式を示す – は行列Aの各行 –はiループでの行列B –はiループでの行列C •
は−1 の全0な行に を挿入してVでぐ るっと回転させてるだけなので 7
上限の証明-1 8 xはATA − BTBの最大固有値の固有ベクトル ∑で 0, 以外は全部消える 0は零行列なのでやっぱりいらん 前Pの等式を代入
Algorithmで 定義したΣを各々代入 − の真ん 中の(気持ち)√取って シュワルツの不等式 行列ノルムの定義 に従って頑張る アルゴリズムのここを見る
上限の証明-2 9 よりも大きいものが少なく ともl/2個アルゴリズム的に 残っているはずなので成⽴
上限の証明 • 上限の証明-1, 2を組み合わせればOK 10
やってみる • Python版は数年前にPFNのHido氏がやってる 11 https://www.slideshare.net/shoheihido/kdd-25788780
やってみる • 完全にHidoさんを真似る –同じと思われるデータがKaggleに転がってた 12 https://www.kaggle.com/bistaumanga/usps-dataset/version/1
やってみる • R版がない(と思う) –ないならば、作って見せよう、ホクソエム 13
つくった 14 https://github.com/shinichi-takayanagi/frequent-directions
インストール 15 devtools::install_github("shinichi-takayanagi/frequentdirections")
データを読む • 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
データを読む 17 image(matrix(x[338,], nrow=16, byrow = FALSE))
とりあえずSVDで 18 frequentdirections::plot_svd(x, y)
俺俺Matrix Sketching(l=8) 19 eps <- 10^(-8) frequentdirections::plot_svd(x, y, frequentdirections::sketching(x, 8,
eps))
俺俺Matrix Sketching (l=16) 20 frequentdirections::plot_svd(x, y, frequentdirections::sketching(x, 16, eps))
俺俺Matrix Sketching (l=32) 21 frequentdirections::plot_svd(x, y, frequentdirections::sketching(x, 32, eps))
俺俺Matrix Sketching (l=64) 22 frequentdirections::plot_svd(x, y, frequentdirections::sketching(x, 64, eps))
俺俺Matrix Sketching (l=128) 23 frequentdirections::plot_svd(x, y, frequentdirections::sketching(x, 128, eps))
まとめ • 近似精度の保証付で行列圧縮法をお勉強した • 理論保証があって嬉しい • Rのパッケージ作った –上手く行ってるような気もするがなんか違う気もする –単体テストとかCRANは次にやる 24
More Decks by Shinichi Takayanagi
See All by Shinichi Takayanagi
論文紹介「Evaluation gaps in machine learning practice」と、効果検証入門に関する昔話
stakaya
0
1.4k
バイブコーディングの正体——AIエージェントはソフトウェア開発を変えるか?
stakaya
5
2k
[NeurIPS 2023 論文読み会] Wasserstein Quantum Monte Carlo
stakaya
0
650
[KDD2021 論文読み会] ControlBurn: Feature Selection by Sparse Forests
stakaya
2
2.1k
[ICML2021 論文読み会] Mandoline: Model Evaluation under Distribution Shift
stakaya
0
2.1k
[情報検索/推薦 各社合同 論文読み祭 #1] KDD ‘20 "Embedding-based Retrieval in Facebook Search"
stakaya
2
700
【2020年新人研修資料】ナウでヤングなPython開発入門
stakaya
28
22k
Quick Introduction to Approximate Bayesian Computation (ABC) with R"
stakaya
3
420
The Road to Machine Learning Engineer from Data Scientist
stakaya
5
4.6k
Other Decks in Science
See All in Science
データベース15: ビッグデータ時代のデータベース
trycycle
PRO
1
630
Collective Predictive Coding Hypothesis: Emergence of Language and Cooperative Behaviors
tanichu
0
260
Build your own LLM, Live, with MicroGPT
ianozsvald
0
180
現代AI入門: 大規模言語モデルから思考するシステムへ — Test-Time Scaling, Loop, Harness, RSI
stillpedant
PRO
49
26k
Controller Design for Symbolic Input-Output Systems Using Feedforward Neural Networks
konakalab
0
160
Cross-Media Technologies, Information Science and Human-Information Interaction
signer
PRO
3
33k
生成AI・プレプリント時代における 研究成果公開の再設計 ― トップカンファレンス文化はどこへ向かうのか / Redesigning the Dissemination of Research Outputs in the Age of Generative AI and Preprints — Where Is the Top-Conference Culture Heading?
ykiyota
0
31k
20260820_アウトカムが二値のデータに対するCausal Impact@LINEヤフー Data Science Share #2 / Causal Impact for Binary Outcomes
brainpadpr
3
1.9k
機械学習 - SVM
trycycle
PRO
2
1.3k
Cognitive Debt - What AI will do to us
martinlippert
1
150
Засідання студентського наукового гуртка «Садово-паркове господарство»
mariiabarkan12
0
120
データベース10: 拡張実体関連モデル
trycycle
PRO
0
1.6k
Featured
See All Featured
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
28
3.8k
Amusing Abliteration
ianozsvald
1
400
The #1 spot is gone: here's how to win anyway
tamaranovitovic
4
1.2k
Chrome DevTools: State of the Union 2024 - Debugging React & Beyond
addyosmani
10
1.4k
Money Talks: Using Revenue to Get Sh*t Done
nikkihalliwell
0
570
DevOps and Value Stream Thinking: Enabling flow, efficiency and business value
helenjbeal
2
450
Why You Should Never Use an ORM
jnunemaker
PRO
61
10k
Ecommerce SEO: The Keys for Success Now & Beyond - #SERPConf2024
aleyda
1
2.3k
GraphQLの誤解/rethinking-graphql
sonatard
75
12k
<Decoding/> the Language of Devs - We Love SEO 2024
nikkihalliwell
1
380
ラッコキーワード サービス紹介資料
rakko
5
6M
The Anti-SEO Checklist Checklist. Pubcon Cyber Week
ryanjones
0
310