Min-Wise Hashing for Large-Scale Regression and Classification
Talkat Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013) · 2013-09-16..09-19·
summary
Compresses very large sparse design matrices into a dense sketch via random permutations and signed hashing, proving an unbiased approximation to Xβ and giving mean-squared-error bounds that scale like ||β||^2/L. Uses b-bit min-wise hashing and an explicit MRS map (random sign mapping) so continuous entries work; interactions emerge implicitly, cutting a brute‑force P^2 interaction burden to about Q^2 (Q≈100–1,000 gives L≈10^6 vs 10^12). Empirically projects 3–4M predictors to a 1000-dimensional sketch and matches Lasso/ridge accuracy; aggregation further lowers approximation error.
AI-written summary · about
chapters (14)
- 0:00Intro
- 4:10Regression
- 5:33MinWise Hashing
- 7:33Example
- 11:39MS Map
- 19:32Mean Square Error
- 21:51Interactions
- 22:44Random Tree
- 23:51Interaction Model
- 26:55Prediction Buddy
- 29:04Aggregate Results
- 29:48Summary
- 31:00Example Data
- 35:27Conclusions
related talks
28mSketching for M-Estimators: A Unified Approach to Robust Regression
01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods
32mAdventures with Randomized Algebra for Extreme-Scale Signal Processing
28mRandomized Constrained Matrix Decompositions
36mThe unreasonable effectiveness of feature hashing
26mUsing Random Projections to Make Sense of High-Dimensional ...