Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

K-Nearest Neighbors

pinecone.io

Post reply on HN
Print view View original

11–20 of 38 posts

Re: K-Nearest Neighbors

#11

Post by autokad »

mrfusion wrote: post #4
antognini wrote: post #3

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 algorithm…

I believe it also makes overtraining impossible which is pretty strange for a learning algorithm.

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.

Re: K-Nearest Neighbors

#12

Post by srean »

antognini wrote: post #3

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 algorithm…

> 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.

Re: K-Nearest Neighbors

#13

Post by SubiculumCode »

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?

Re: K-Nearest Neighbors

#14

Post by teddykoker »

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

Re: K-Nearest Neighbors

#15

Post by agys »

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.

Re: K-Nearest Neighbors

#17

Post by minimaxir »

next_xibalba wrote: post #16

Would HN benefit from some kind of "self promotion" or "marketing" tag?

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.

Re: K-Nearest Neighbors

#18

Post by lmkg »

antognini wrote: post #3

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 algorithm…

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.

Re: K-Nearest Neighbors

#19

Post by mrintellectual »

teddykoker wrote: post #14

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

> 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/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.

[1] https://milvus.io/docs/index.md

Re: K-Nearest Neighbors

#20

Post by Bostonian »

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.
Post reply on HN