hide
Free keywords:
-
Abstract:
In learning, a semantic or behavioral
U-shape occurs when a learner first learns, then unlearns, and, finally,
relearns, some target concept (on the way to success).
Within the framework of Inductive Inference,
previous results have shown, for example, that such
U-shapes are unnecessary for
explanatory learning, but are necessary for behaviorally correct and
non-trivial vacillatory learning. Herein we focus more on syntactic
U-shapes.
This paper introduces two general techniques
and applies them especially to syntactic U-shapes in learning:
one technique to show when they are necessary and one to show when they are
unnecessary. The technique for the former is very general and applicable
to a much wider range of learning criteria. It employs so-called
\emph{self-learning classes of languages} which are shown to
\emph{characterize} completely one criterion learning more than another.
We apply these techniques to show that, for set-driven and partially set-driven
learning, any kind of U-shapes are unnecessary. Furthermore,
we show that U-shapes are \emph{not} unnecessary in a strong way for iterative
learning, contrasting an earlier result by Case and Moelius that semantic
U-shapes \emph{are} unnecessary for iterative learning.