K-Nearest Neighbors
pinecone.io
pinecone.io
Of course, the catch is that when they say "infinite data", they really mean "infinite data", especially for high dimensional data. And finding the k nearest neighbors in an extremely large dataset is also a computationally difficult task.
So the real problem in machine learning is, "given that we have much less data than we would like for k-NN and a smaller computational budget, how can we do about as well as k-NN would have done with more data and more compute?"
https://datacadamia.com/data_mining/overfitting
But if all your data is good There’s no training step per se. And it just keeps improving with more data.
For example, in linear regression, you might have N observations (x, y) and condense them into 2 parameters for a line that "best fits" the data (y = mx + b).
Instead of linear regression, you can perform "polynomial regression" where you fit a polynomial of some order Q to the data. Since the data you have is often noisy, if Q is large, you will fit a polynomial full of "ups and downs" that goes through the points in the training data exactly, but is not a good representation of what you're trying to learn and will fail miserably on new inputs.
In deep learning, you may also specify a network with "too many parameters". A network is trained in steps, by slowly converging the parameters to the "optimal value" to fit the training data you give it. But if we allow it to converge, it might find parameters that "closely fit" the training data, but are not good for generalization, we would prefer a less optimized model. A classic trick (among others) in neural networks is to do "early stopping" to avoid this overfitting phenomenon.
In kNN the model is the historical dataset. (Aside: neural networks are basically kNN+Compression, model=compressed(dataset)).
kNN is therefore, in a sense, a perfect illustration of learning in the ML sense being widely at odds with any standard prior notions of "learning" we might have.
The goal of learning in animals is "mastery of the concepts" which enable one to imagine the ways the world might be, to reason, and likewise, act under novelty.
Learning in the ML sense is the "shortcut", basically, remember everything and have an index on-hand. This is an incredibly brittle strategy, as anything worth learning in-the-usual-sense has no near-identical-cases to consult.
if kNN = "k + data", then kNN tends towards perfect, as `data` tends towards "we already have the answer" and `k` tends towards `1`.
This is a general scheme for ML. If the `data` isnt already the solution, `ML` is useless.
To be more precise, the result is that it is asymptotically no worse than twice as bad as the best classification accuracy possible (the Bayes rate).
KNNs have trivial training cost but, as you pointed out, have a non-trivial cost of generating a prediction.
A related advantage that KNNs have is that it is easy to remove the effect of specific training examples from the model. With GDPR and other future legislations requiring the support of removing not only the user's data, but also the effect of the user's data from a trained model, KNNs are convenient.
In cryptography, the equivalent is the one-time pad. It has trade-offs which make it unavailable for many uses, but by some measures it is literally perfect and the only thing which can be perfect.
At the least, it's fine ethically as long as it's high effort and there's unique content/approaches, which this is.
In the past I have used a k-d tree [1] for this, which allows O(log n) searches in the vector space. It seems they are offering a k-d-tree-as-a-service.
Indeed! We've been able to build simple reverse image search apps and other solutions using the power of embeddings from pre-trained ML models: https://gist.github.com/fzliu/c9380a7f9ba411adeff0b727cdba15....
One quick note: k-d trees are great for indexing low-dimensional data, but for high-dimensional embeddings they tend to be a poor indexing choice since you'll end up visiting more nodes in the tree than you'd like. I found [1] to be a great overview of different indexing types for high-dimensional vectors and the advantages of each.
Thanks for the reference! Nice outline of various ANN approaches.
If discovery or recall is what you're after, a generic image classification model trained with binary cross-entropy might be better. For example, performing reverse image search on a photo of a German Shepherd should always return images of GSheps in the first N pages, but showing other dog breeds in later pages and possibly even cats after that would be a desirable feature for many search/retrieval solutions. An embedding model trained with contrastive loss might have this behavior to a certain extent, but a model based on BCE should be better.
As you said, common use cases include deduplication and image search, and especially semantic search (text).
1. The people who built the Pinecone vector index include some of the top experts in information retrieval/vector search in the world, the chances of someone like myself building something more efficient in Faiss is pretty slim, even after spending months learning the library and as much as I can about vector search
2. Faiss is only a vector index, it doesn't manage your data, so you need to personally build a framework around your Faiss index to handle that, speaking from experience this can be frustrating
3. Pinecone has one of (if not the) most advanced implementation of filtering available, they use 'single stage' filtering, which provides pre-filtering speeds with post-filtering accuracy
4. Scalability, want to search through an index of 2B vectors? Not an issue, getting that working with Faiss is not fun
5. Ease of use, all of the above takes an API key and ~5 lines of code to setup