K-Nearest Neighbors
pinecone.io
K-Nearest Neighbors
1–10 of 38 posts
Re: K-Nearest Neighbors
#2When I first got involved with text classification (early 00's) k-NN was one of the best performing algorithms. It's still pretty good.
Re: K-Nearest Neighbors
#3k-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?"
Re: K-Nearest Neighbors
#4k-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.
Re: K-Nearest Neighbors
#5I've gotten this as an interview question a few time.
Re: K-Nearest Neighbors
#6k-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 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?
Re: K-Nearest Neighbors
#7Earlier quoted context omitted.
I believe it also makes overtraining impossible which is pretty strange for a learning algorithm.
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?
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.
Re: K-Nearest Neighbors
#8Earlier quoted context omitted.
I believe it also makes overtraining impossible which is pretty strange for a learning algorithm.
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?
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.
Re: K-Nearest Neighbors
#9k-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…
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.
Re: K-Nearest Neighbors
#10technically 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.