6 ms·

K-Nearest Neighbors

118 points by gk1 5y ago

rgavuliak 5y ago
kNN is very well understood and well documented. It seems though someone makes a blog post about it every week that gets upvoted on HN. This only further solidifies the notion that most blogs relating to Data Science rarely cover advanced topics.
- Mandelmus 5y ago
  I feel like the percentage of "Let me make a blog post or YouTube tutorial about this thing I learned about yesterday" content on technical topics is trending towards 100% as time goes on.
  - rgavuliak 5y ago
    Exactly, I know the advice to boost your resume often tells you to write a blogpost or do a talk, but I would also say that you should do this if you have something interesting to say. Until that happens you're probably better off improving your technical skills.
PaulHoule 5y ago
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.
antognini 5y ago
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?"
- mrfusion 5y ago
  I believe it also makes overtraining impossible which is pretty strange for a learning algorithm.
  - gatlin 5y ago
    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?
    - mrfusion 5y ago
      I could be wrong. If you give it bad data then it could still overfit. https://datacadamia.com/data_mining/overfitting 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.
    - pedrosorio 5y ago
      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.
  - autokad 5y ago
    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.
leros 5y ago
I've gotten this as an interview question a few time.
autokad 5y ago
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 5y ago
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?
teddykoker 5y ago
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 https://en.wikipedia.org/wiki/K-d_tree
- mrintellectual 5y ago
  > 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/c9380a7f9ba411adeff0b727cdba153f 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 https://milvus.io/docs/index.md
  - teddykoker 5y ago
    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 5y ago
      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.
agys 5y ago
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.
next_xibalba 5y ago
Would HN benefit from some kind of "self promotion" or "marketing" tag?
- minimaxir 5y ago
  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.
- kergonath 5y ago
  I think it’s fine as long as the content is interesting. It gets flagged to death pretty quickly if it is not.
Bostonian 5y ago
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 5y ago
  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).
brittanymdavis1 5y ago
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 https://dataskeptic.com/episodes/k-means
consoledev 5y ago
The infamous kNN algorithm
oofbey 5y ago
Why would somebody use pinecone instead of a high quality open source library like FAISS？
- dontreact 5y ago
  * 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.
- redskyluan 5y ago
  FAISS is simply a library. You will need a system Like Milvus for huge data amount
- jamesbriggs 5y ago
  Faiss is great, but I see there being several strong reasons for using Pinecone: 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

118 points by gk1 5y ago

kNN is very well understood and well documented. It seems though someone makes a blog post about it every week that gets upvoted on HN. This only further solidifies the notion that most blogs relating to Data Science rarely cover advanced topics.

Mandelmus 5y ago
I feel like the percentage of "Let me make a blog post or YouTube tutorial about this thing I learned about yesterday" content on technical topics is trending towards 100% as time goes on.
- rgavuliak 5y ago
  Exactly, I know the advice to boost your resume often tells you to write a blogpost or do a talk, but I would also say that you should do this if you have something interesting to say. Until that happens you're probably better off improving your technical skills.

PaulHoule 5y ago

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.

antognini 5y ago

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?"

mrfusion 5y ago
I believe it also makes overtraining impossible which is pretty strange for a learning algorithm.
- gatlin 5y ago
  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?
  - mrfusion 5y ago
    I could be wrong. If you give it bad data then it could still overfit. https://datacadamia.com/data_mining/overfitting 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.
  - pedrosorio 5y ago
    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.
- autokad 5y ago
  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.

leros 5y ago

I've gotten this as an interview question a few time.

autokad 5y ago

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 5y ago

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?

teddykoker 5y ago

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 https://en.wikipedia.org/wiki/K-d_tree

mrintellectual 5y ago
> 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/c9380a7f9ba411adeff0b727cdba153f 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 https://milvus.io/docs/index.md
- teddykoker 5y ago
  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 5y ago
    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.

agys 5y ago

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.

next_xibalba 5y ago

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

minimaxir 5y ago
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.
kergonath 5y ago
I think it’s fine as long as the content is interesting. It gets flagged to death pretty quickly if it is not.

Bostonian 5y ago

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 5y ago
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).

brittanymdavis1 5y ago

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 https://dataskeptic.com/episodes/k-means

consoledev 5y ago

The infamous kNN algorithm

oofbey 5y ago

Why would somebody use pinecone instead of a high quality open source library like FAISS？

dontreact 5y ago
* 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.
redskyluan 5y ago
FAISS is simply a library. You will need a system Like Milvus for huge data amount
jamesbriggs 5y ago
Faiss is great, but I see there being several strong reasons for using Pinecone: 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