5 ms·

Being in software development for the past 15 years I cant understand any of this. What are some good resource to get up to speed on this stuff?

esafak 3y ago
It crops up in machine learning. https://en.wikipedia.org/wiki/Nearest_neighbor_search https://en.wikipedia.org/wiki/Nearest_neighbor_search
WinLychee 3y ago
This series of articles from Pinecone seems accessible https://www.pinecone.io/learn/vector-indexes/ https://www.pinecone.io/learn/vector-indexes/ . Stepping back a moment, the problem "I want to find the top-k most similar items to a given item from a collection" comes up in a variety of domains, and a common approach is nearest-neighbor search. Depending on the number of dimensions and the number of items, you may need tricks to speed up the search. In recent years we've seen an increase in scale and invention of some new tricks to speed this up. In a bit more detail the idea is to convert your data into vectors embedded in some d-dimensional space and compute the distance between a query vector and all other vectors in the space. This is an O(dN) computation. ANN covers a number of techniques giving a speedup by letting you reduce number of required comparisons.
tysam_and 3y ago
High dimensional nearest neighbor search scales very poorly with dimensions and/or number of examples IIRC, so approximate methods are best for time/value tradeoffs. Oftentimes the applications don't require a perfect match anyways, just something 'close enough'. Because things live in high dimensions, and they're often related to each other, this results in these vast 'sparse' gaps where no data really generally lives. Hence allowing for good speed of approximate methods, and a good tradeoff of information-per-FLOP when compared to the full scale search itself.
shoo 3y ago
see also - the section titled "Distance function" from https://en.wikipedia.org/wiki/Curse_of_dimensionality https://en.wikipedia.org/wiki/Curse_of_dimensionality > One way to illustrate the "vastness" of high-dimensional Euclidean space is to compare the proportion of an inscribed hypersphere with radius r and dimension d, to that of a hypercube with edges of length 2 r . [...] As the dimension d of the space increases, the hypersphere becomes an insignificant volume relative to that of the hypercube E.g. in two dimensions the ratio area of the circle of radius r=1 to the area of a square of side length 2r is pi / 4 = approx 0.785. As the number of dimensions becomes large, this ratio drops toward zero. There's also some discussion of how using distance functions to measure distances from reference points become less useful as the number of dimensions of the space increases -- all distances becoming similar -- although > research has shown this to only hold in the artificial scenario when the one-dimensional distributions are independent and identically distributed.
visarga 3y ago
Trust me it is not that complicated, if you spend 1-2 hours on this you will walk away with a good grasp. But if you try the same for neural nets, it's impossible. Once you understand the dot product operation, which is high-school level math, can be written as a for loop with a multiply and add, it all falls from it. How do you speed up millions of dot products? Try a tree, clusters, hashing, inverted indices, GPUs... For a few million vectors it's a solved problem since 5 years ago. I was using annoy in 2017, the library is 10 years old, first commit on Feb 20, 2013. It's as old as the deep learning age. That's why I was curious why all this recent discussion about it, it's certainly a discovery phase for many people when they realise such a tool exists, made possible by the availability of efficient embedding models and needed by LLMs for retrieval.

esafak 3y ago

It crops up in machine learning. https://en.wikipedia.org/wiki/Nearest_neighbor_search https://en.wikipedia.org/wiki/Nearest_neighbor_search

WinLychee 3y ago

This series of articles from Pinecone seems accessible https://www.pinecone.io/learn/vector-indexes/ https://www.pinecone.io/learn/vector-indexes/ . Stepping back a moment, the problem "I want to find the top-k most similar items to a given item from a collection" comes up in a variety of domains, and a common approach is nearest-neighbor search. Depending on the number of dimensions and the number of items, you may need tricks to speed up the search. In recent years we've seen an increase in scale and invention of some new tricks to speed this up. In a bit more detail the idea is to convert your data into vectors embedded in some d-dimensional space and compute the distance between a query vector and all other vectors in the space. This is an O(dN) computation. ANN covers a number of techniques giving a speedup by letting you reduce number of required comparisons.

tysam_and 3y ago

High dimensional nearest neighbor search scales very poorly with dimensions and/or number of examples IIRC, so approximate methods are best for time/value tradeoffs. Oftentimes the applications don't require a perfect match anyways, just something 'close enough'. Because things live in high dimensions, and they're often related to each other, this results in these vast 'sparse' gaps where no data really generally lives. Hence allowing for good speed of approximate methods, and a good tradeoff of information-per-FLOP when compared to the full scale search itself.

shoo 3y ago

see also - the section titled "Distance function" from https://en.wikipedia.org/wiki/Curse_of_dimensionality https://en.wikipedia.org/wiki/Curse_of_dimensionality > One way to illustrate the "vastness" of high-dimensional Euclidean space is to compare the proportion of an inscribed hypersphere with radius r and dimension d, to that of a hypercube with edges of length 2 r . [...] As the dimension d of the space increases, the hypersphere becomes an insignificant volume relative to that of the hypercube E.g. in two dimensions the ratio area of the circle of radius r=1 to the area of a square of side length 2r is pi / 4 = approx 0.785. As the number of dimensions becomes large, this ratio drops toward zero. There's also some discussion of how using distance functions to measure distances from reference points become less useful as the number of dimensions of the space increases -- all distances becoming similar -- although > research has shown this to only hold in the artificial scenario when the one-dimensional distributions are independent and identically distributed.

visarga 3y ago

Trust me it is not that complicated, if you spend 1-2 hours on this you will walk away with a good grasp. But if you try the same for neural nets, it's impossible. Once you understand the dot product operation, which is high-school level math, can be written as a for loop with a multiply and add, it all falls from it. How do you speed up millions of dot products? Try a tree, clusters, hashing, inverted indices, GPUs... For a few million vectors it's a solved problem since 5 years ago. I was using annoy in 2017, the library is 10 years old, first commit on Feb 20, 2013. It's as old as the deep learning age. That's why I was curious why all this recent discussion about it, it's certainly a discovery phase for many people when they realise such a tool exists, made possible by the availability of efficient embedding models and needed by LLMs for retrieval.