The power of learning from examples is that it provides an ability to apply what has been learned to new cases. Otherwise, the process would amount to no more than memorization. What exactly are the requirements for this process of learning to be effective for generalization?
[...] How can we generalize beyond the specifics of the experiences we have had? How are we able to recognize a tree that we have never seen before as a tree? How do we recognize a letter “A” presented in a new font? How do pigeons recognize either? Most likely, neither humans nor pigeons employ consciously articulated definitions for the concept of an “A” or a “tree.”
In the eighteenth century the philosopher David Hume famously talked about induction as based on the detection of “regularities” in our experience. We use examples that we have seen to identify these regularities. We then make inferences about new examples by determining whether they contain these identified regularities. But what exactly is a regularity? Which kinds of regularities do humans and pigeons use to learn concepts like a tree or a chair, or children use to learn the concept of fruit? We can ask these questions in scientific terms if generalization is formulated as a computational task.
Central to the notion of educability will be answers to this question of generalization provided by the Probably Approximately Correct or PAC framework.