Why can't we find our friends easily as we move to a city with more and more neighborhoods?
Image: Jkatz (WMF), CC BY-SA 4.0, via Wikimedia Commons
the curse of dimensionality makes nearest neighbor search unreliable
Why can't we find our friends easily as we move to a city with more and more neighborhoods?
Imagine you're searching for your friend's house in a new city. The city has many neighborhoods, and each neighborhood is divided into even smaller blocks.
As the city grows with more neighborhoods and blocks, it becomes harder to pinpoint your friend's location because every area seems equally spread out and indistinguishable from the others.
Example
If there are 10 neighborhoods and each has 10 blocks, you have 100 places to search. But if each neighborhood has 100 blocks, you now have 1,000 places to search.
Remember this
The curse of dimensionality makes searching for your friend in a sprawling city inefficient as the number of neighborhoods and blocks increases exponentially.
Text adapted from Wikipedia, licensed under CC BY-SA 4.0.
Related concepts
the lottery ticket hypothesis says: sparse subnetworks can match full network performance
Can a small part of a puzzle fit perfectly into its place by chance?
GraphSAGE does: samples and aggregates a fixed-size neighborhood
GraphSAGE samples and aggregates a fixed-size neighborhood
the Johnson-Lindenstrauss lemma says
Can we shrink big data without losing important details?
t-SNE preserves local structure
Can we see the hidden patterns in a cloud of data points?
Locality-sensitive hashing
Locality-sensitive hashing (LSH) hashes similar items into the same buckets
UMAP is faster than t-SNE
UMAP is faster due to approximate nearest neighbors and cross-entropy optimization
Swipe through 100 ML concepts daily
Open Pocket Polymath