4 ms·

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), b

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.
- seanhunter 5y ago
  I don't think that's the case. Depending on your dataset and objective function, for some (too small) values of k, kNN will settle into local minima and not locate the globally optimal solution (I believe).
mjburgess 5y ago
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 5y ago
> 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.
lmkg 5y ago
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 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.
seanhunter 5y ago
I don't think that's the case. Depending on your dataset and objective function, for some (too small) values of k, kNN will settle into local minima and not locate the globally optimal solution (I believe).

mjburgess 5y ago

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

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

lmkg 5y ago

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.