k-nearest neighbors classification is one of the first non-linear supervised learning algorithms. Its predictions are derived from the data sample distances.

It is basically a glorified fuzzy lookup table, but then again, so can one view deep learning (fuzzy hierarchical localized lookup).

Pure memorization can even outperform logistic regression, especially with big data sets, so there is some recent debate as to what degree models memorize and to what degree they generalize.

Interesting, though I don't totally see how deep learning would be similar. On deep learning, it is my understanding the weights are learned from the data. These are effectively constants, and represent logical rules.

So in essence, the rules which relates input to output are learned from the data in deep learning.

In nearest neighbour, the rule wasn't learned, we figured out the rule ourself: "use the nearest data point's result".

But in deep learning, the rule might be something like when feature x and y are between z range of each other and etc. And this rule is not defined by us, but by the weights which are learned from the data.

Effectively, deep learning thus learns the rules that define the relationship between input and class. But nearest neighbor is just a static rule that happens to be pretty general in essence, so it gives okay result for a lot of problems.

Not an AI expert, so take all this as my simple current understanding.

You could automatically encode a KNN model as a set of logical if-then rules: "if x1 > 10 and x2 < 3 then 4 nearest labels are [1, 1, 1, 0]" so the information is there. For KNN you could also train weights for every variable (how much should they count in the distance calculation?). For deep learning you have way more parameters and architecture choices than for nearest neighbors (mostly the distance metric and the number of neighbors to consider). After that, both learn a mapping from input data to a target.

What would you think about something like local linear least squares (where it uses linear regression but locally weights the linear regression so that it is designed to fit points closer to the target)?

Is it learning patterns in the data, or is it just a glorified lookup table?