[HN Gopher] K-Nearest Neighbors
___________________________________________________________________
K-Nearest Neighbors
Author : gk1
Score : 86 points
Date : 2022-04-13 14:42 UTC (8 hours ago)
(HTM) web link (www.pinecone.io)
(TXT) w3m dump (www.pinecone.io)
| leros wrote:
| I've gotten this as an interview question a few time.
| oofbey wrote:
| Why would somebody use pinecone instead of a high quality open
| source library like FAISS?
| dontreact wrote:
| * CRUD: Faiss indexes are static, if you want vector search
| over data that users can edit freely, it's not easy to use
| FAISS for this * Non-vector filtering: Often you need to do a
| search based on some structured query + rank the results by
| vector similarity. FAISS can only do vector similarity.
| autokad wrote:
| technically speaking, tree algorithms such as decision trees and
| gradient boosting are special cases of knn. Items in a leaf are
| within the same 'distance' from each other.
| SubiculumCode wrote:
| In my research I've been using a method called multivariate
| distance matrix regression, which is a multivariate methods that
| regresses a Gower transformed distance matrix onto a set of
| predictors. In this technique, one must first choose a distance
| metric. I have been choosing the Manhattan distance (city-block
| distance) for my brain imaging data variables (volumes,
| connectivity correlations values, etc) because it is somewhat
| less vulnerable to outliers than Euclidean distance or the
| Pearson's distance, and somewhat better in terms massively
| multivariate data. I am wondering whether HN gurus have any
| suggestions in terms of finding the optimal distance metric?
| PaulHoule wrote:
| When I first got involved with text classification (early 00's)
| k-NN was one of the best performing algorithms. It's still pretty
| good.
| teddykoker wrote:
| I wonder how their advertised "vector database" works. kNN
| combined with embeddings from pre-trained deep learning models
| can be very useful for information retrieval, (e.g. searching for
| duplicate/similar images or text).
|
| 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.
|
| [1] https://en.wikipedia.org/wiki/K-d_tree
| mrintellectual wrote:
| > kNN combined with embeddings from pre-trained deep learning
| models can be very useful for information retrieval
|
| 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/c9380a7f9b
| a411adeff0b727cdba15....
|
| 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.
|
| [1] https://milvus.io/docs/index.md
| teddykoker wrote:
| For image retrieval, have you tried using a model trained
| with contrastive learning (e.g. SimCLR)? This could produce
| better embeddings for retrieval since the model is trained to
| explicitly minimize euclidean distance between similar pairs.
|
| Thanks for the reference! Nice outline of various ANN
| approaches.
| mrintellectual wrote:
| I haven't tried SimCLR, but I did try face embedding models
| trained with contrastive and triplet loss. For applications
| where precision is the key metric, I do agree that these
| loss functions are much better overall.
|
| 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.
| gk1 wrote:
| Pinecone stores and searches through dense vector embeddings
| using a proprietary ANN index. It also has live index updates
| and metadata filtering, which you'd expect from any database
| but is surprisingly hard to find or do with vector indexes.
|
| As you said, common use cases include deduplication and image
| search, and especially semantic search (text).
| turnersr wrote:
| Do you happen to know other implementations that allow for
| live updates and metadata filtering like Pinecone?
| agys wrote:
| I think that the first picture listed, which should illustrate
| that close elements are perceived as a group, doesn't really
| obtain its intended result: (to me at least) the pink elements
| are the ones that stand out and tend to form a group.
| Tint/saturation is stronger than shape and/or proximity in this
| case.
| Bostonian wrote:
| Once you find the N nearest neighbors, why consider only the 0th
| order (locally constant) model, which is what KNN assumes?
| Instead you can use a larger N and fit a local linear regression.
| I have tried this on synthetic data sets, and it works pretty
| well. This is common for 1D regression but not regression with
| multiple predictors.
| nestorD wrote:
| Once you do that you have something that starts looking like a
| Gaussian process but is a lot cheaper. I believe it could have
| a lot of value (for people who have too much data for Gaussian
| process but otherwise could do with their good properties and
| are in a space with an easily defined distance).
| consoledev wrote:
| next_xibalba wrote:
| Would HN benefit from some kind of "self promotion" or
| "marketing" tag?
| kergonath wrote:
| I think it's fine as long as the content is interesting. It
| gets flagged to death pretty quickly if it is not.
| minimaxir wrote:
| Content marketing has been on HN since the beginning.
|
| At the least, it's fine ethically as long as it's high effort
| and there's unique content/approaches, which this is.
| brittanymdavis1 wrote:
| Data Skeptic podcast is currently doing a series on K-means
| applications (similar to KNN). Would recommend it for anyone
| exploring the topic: https://dataskeptic.com/episodes/k-means
| antognini wrote:
| k-NN is kind of an interesting machine learning algorithm because
| it is extremely simple (just take the average of the closest k
| data points in your dataset), but is, in a certain sense, the
| "ideal" algorithm. In the limit that the size of your data goes
| to infinity, k-NN performs perfectly. With the appropriate choice
| of k it is impossible for any algorithm, no matter how clever, to
| outperform it. Other ML algorithms generally lack this property.
|
| 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?"
| lmkg wrote:
| I think some fields have certain canonical methods which are
| often impractical, but foundational. And the "real" methods
| used in practice can, with work, be seen as an approximation or
| limit in some case. Understanding that perspective is useful in
| being able to reason about the trade-offs of different
| approaches.
|
| 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.
| mrfusion wrote:
| I believe it also makes overtraining impossible which is pretty
| strange for a learning algorithm.
| autokad wrote:
| I don't think this is true. you over train in KNN by making
| the distance small, the best example is when you set k = 1.
| some would argue that's just a parameter for regularization,
| but I tend to disagree.
| gatlin wrote:
| I don't want or expect you to do a book report for me :) but
| would you mind linking a thread or two here that an
| enthusiastic moron could pull at for more detail?
| pedrosorio wrote:
| Essentially, most ML algorithms, "learn" from data by
| condensing the data into a set of parameters.
|
| 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.
| mrfusion wrote:
| I could be wrong. If you give it bad data then it could
| still overfit.
|
| 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.
| mjburgess wrote:
| The issue with "infinite" is also infinite _in time_ , in the
| sense that all you're saying is "if we knew the future, we'd be
| right".
|
| 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.
| srean wrote:
| > In the limit that the size of your data goes to infinity,
| k-NN performs perfectly
|
| 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.
___________________________________________________________________
(page generated 2022-04-13 23:01 UTC)