hide
Free keywords:
-
Abstract:
A U-shape occurs when a learner first learns, then unlearns, and, finally,
relearns, some target concept. Within the framework of Inductive Inference,
previous results have shown, for example, that U-shapes are unnecessary for
explanatory learning, but are necessary for behaviorally correct learning.
This paper solves the following
two problems regarding non-U-shaped learning posed in the prior literature.
First, it is shown that there are classes learnable with three memory states
that are not learnable non-U-shapedly with any finite number of memory states.
This result is surprising, as for learning with one or two memory states,
U-shapes are known to be unnecessary.
Secondly, it is shown that there is a class learnable memorylessly with a
single feedback query such that this class is not learnable non-U-shapedly
memorylessly with any finite number of feedback queries. This result is
complemented by the result that any class of \emph{infinite} languages
learnable memorylessly with finitely many feedback queries is so learnable
without U-shapes -- in fact, all classes of infinite languages learnable with
\emph{complete} memory are learnable memorylessly with finitely many feedback
queries and without U-shapes. On the other hand, we show that there is a
class of infinite languages learnable memorylessly with a single feedback
query, which is \emph{not} learnable with\emph{out} U-shapes by any particular
bounded number of feedback queries.
