Using Random Projections to Make Sense of High-Dimensional ...
summary
Random projections (aka locality sensitive hashing) become a fast nearest-neighbor index for dense vectors by building many random-partition trees and aggregating candidates; an implementation using 10 trees reaches about 97% accuracy at ~5 ms per query, then dimensionality reduction cuts query time to ~0.7 ms while improving accuracy, and a custom implementation halves the time further at the cost of more trees. Demonstrated on the MNIST/Kaggle image set and used by Spotify and Etsy.
AI-written summary · about
chapters (25)
- 0:00Intro
- 2:23IMAGE SEARCH BY EXAMPLE
- 2:56TWO KINDS OF SEARCH
- 3:37OUTLINE
- 4:29MATRIX REPRESENTATION OF DATASET
- 4:44HIGH-DIMENSIONAL DATA
- 5:14DENSE VS SPARSE MATRIX
- 6:26DIMENSIONALITY REDUCTION = PATTERN DISCOVERY
- 7:00APPLICATIONS
- 8:46RANDOM PROJECTIONS IN INDUSTRY
- 9:53HOW DOES IT WORK?
- 10:33ILLUSTRATION ON ARTIFICIAL DATASET
- 12:24PARTITION BY RANDOM SPLITS
- 13:49PLATO'S ALEGORY OF THE CAVE
- 14:31PARTITIONING BY PROJECTING ON RANDOM LINES
- 14:52ALGORITHM VISUALIZATION
- 15:43MULTIPLE TREES
- 16:27ADDING MORE TREES
- 16:56CONSTRAINING THE NEAREST NEIGHBOR REGION
- 18:56IMAGE SEARCH FOR PREDICTION
- 19:52STAGE 1: INDEXING
- 20:26STAGE 2: SEARCH TO PREDICT THE LABEL
- 21:17BENCHMARK IMAGE SEARCH
- 23:50SAME FOUNDATION FOR SEARCH AND MACHINE LEARNING
- 25:25CONCLUSION
related talks
24mSpeeding up search with locality sensitive hashing
11mFinding Friends in High Dimensions...
32mAdventures with Randomized Algebra for Extreme-Scale Signal Processing
01h 34mAlgorithmic High-Dimensional Geometry I
39mProbabilistic Hashing Methods for Succinct Data Representations and Applications
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
01h 05mNearest Neighbor Methods I
23mErik Bernhardsson, CTO, Better Mortgage, NYC 2017