How many training examples are sufficient to learn the
target concept?
The examples could come in several ways:
The learner proposes instances, as queries to teacher:
Learner proposes instance $x$, teacher provides $c(x)$.
Play 20 questions, divide space in half.
The teacher (who knows $c$) provides training examples
teacher provides sequence of examples of form $\langle x, c(x)
\rangle$. Best strategy depends on learner.
There is some random process that proposes the
instances. $x$ is generated randomly, teacher provides
$c(x)$.Hmmmm, this needs further analysis.