Yes, kNN is the bound if you formulate learning as: there exists an f_true: Pixels->Animals; we have an infinite sampling of (Pixels, Animals); kNN performs at 100%. Therefore kNN is the bound.
Whereas I dont think this has much to do with learning. Learning for me is: the function probably doesnt exist, we dont know what its domain would even be, and we have no idea how to sample that space. You know: the history of human civilization, but also: the history of a day of any animal's life.
We encounter problems daily whose functions can only be modelled by partial input and output domains, and our job is to find ways of resolving the inherent ambiguities in those situations. Ie., to find what parts of the world are relevant, to find ways of measuring it, and hence to find more data until the ambiguity resolves itself.
kNN being a perfect algorithm is a catastrophe for this whole formulation of AI. All it means is that the whole field of machine learning has as its limit what you can do if you already know the answer. You can see from this that it isnt learning at all.
The situation is exactly backwards: ML assumes relevant well-carved unambiguous data. The whole problem of learning is precisely to produce it!
Doesn't the existence of unsupervised training and models that solve previously unsolved problems somewhat invalidate the NN=kNN analogy then? The protein folding problem didn't have an already known overall answer for instance. The model clearly 'learned' representational information that we are not aware of in order to be so much more effective at solving the problem than we are.
Or similarly with the Starcraft or Dota AI, while some strategies learned were similar to humans, others were entirely novel. I think that's getting pretty close to 'learning' as you've defined it.
If you can build a system like this, with no presumed domain distribution internally, then you're a step towards intelligence.
In the evolution of natural intelligence, physics provides the domain distribution and Darwin has explained what the reward function is. It does not follow that no learning can occur in an environment where either or both of the domain and reward function are defined by humans.
As far as I can tell, this was the explicit goal of AlphaGo Zero. Even if we were to accept your position that the data it was started with "contained the solution", then the fact it does rather better than humans at finding that solution is, by itself, significant. (In this view, one might characterize the evolution of natural intelligence as finding, within the biosphere domain, a rather successful solution to the survival problem.)
It would seem to me to be begging the question to say that the success of AlphaGo Zero is not learning because the environment was human-specified (At the same time, as Go is a highly-constrained environment, there is no reason to suppose that its successes indicate we are anywhere near AGI.)
If you can build a hand to grasp objects, and train its substructure to grasp this-way-and-that -- fine. So long as it can, in the end, also train itself... as we all do when we type.
Nature provides something to bootstrap learning, but it isnt "data" in the sense in which ML requires data. It isnt relevant, quantified, premeasured. The "data" nature provides is in our biochemistry .. how we react to our environment, etc.
If AI research can produce an intelligence which is able to formulate the very terms of problems it wishes to solve, great. I dont see "summarising the solution" as a strategy which is event in the ballpack.
While I agree that nature's data is less relevant, quantified, and premeasured than what current ML feeds on, I don't see that as establishing that there is a relevant qualitative distinction that renders this divide unbridgeable in principle. Every organism that senses its environment is processing data.
With regard to formulating the very terms of problems it wishes to solve, I have no difficulty in seeing that this has not been achieved yet, and personally, I don't expect it any time soon. At the same time, you seem to be very close to saying that no artificial system could do this because its goals are always, in some sense, those of its creators. To be clear, I would regard such a position as mostly avoiding the issues.
> we have infinite sampling
We don't. You're taking the learning out of the process you're discussing by using an infinite sample. Of course, then, the machine learning part becomes trivial, and it's just an optimization problem for minimal training error!
If we have all the data, like infinite data, then we have the classification for every one of the (finite) number of possible images already. At that point, why stop at kNN? Use a hashmap!
If this were true, then all people who observe the same training samples would learn equally well and predict equally well. But we don't. Some of us invent a better loss function than others or reject irrelevant data better. The representation formed by the data is surely derived, not fixed in its raw form. Forming a better representation of the data is the art of learning better. I'm convinced learning and remembering what you learn is more than kNN; in humans it involves data compression and recontextualization as you improve your loss function or tie your old representation to newly learned data — old raw data and representations that heretofore you had not believed were relevant to that objective (or lesson).
How do you know that we don’t? It’s an impossible experiment to conduct, right? Since same training samples == every stimuli experienced since birth, and even then you have the problem of possibly-different “initial conditions” i.e. development of the brain in the womb. Maybe if we did replicate that, we would learn & predict equally well.
All learning is bound by kNN, including, I would argue, human intelligence. When we compare and contrast things, be it words, objects, or images, the very best we can do is to compare those “units” to all other examples that we have ever observed.
There is no such thing as generalising beyond kNN. The real magic in generalising is not how many nearest neighbours you are able to compare against, the magic is in _which_ qualities you use to determine the kNN. Another way to state this is: intelligence is in the distance metric/embedding/compression, not the ability to process all examples.
When we say that humans are able to generalise, what we really mean is that we are able to compare and contrast specific subsets of qualities for a given object against all other things objects we have knowledge for. The way we choose and weight those specific qualities is what results in our “intelligence”.
So when we say that NN == kNN, I think this is actually a really impressive achievement for neural nets. Neural networks are able to produce kNN level results with orders of magnitude lower compute. Humans too, are able to do this, and if we’re being very thorough, we sometimes fall back to kNN-like processes