Learning Recursive Concepts with Anomalies
Gunter Grieser1 , Steffen Lange2 , and Thomas Zeugmann3
1Technische Universität Darmstadt, Fachbereich Informatik, Alexanderstr. 1064283 Darmstadt, Germany, e-mail: grieser@informatik.tu-darmstadt.de2

3

Universität Leipzig, Institut für Informatik, Augustusplatz 10–11
04109 Leipzig, Germany, e-mail: slange@informatik.uni-leipzig.de

Medizinische Universität Lübeck, Institut für Theoretische Informatik, Wallstr. 40
23560 Lübeck, Germany, e-mail: thomas@tcs.mu-luebeck.de

Abstract. This paper provides a systematic study of inductive inferenceof indexable concept classes in learning scenarios in which the learner issuccessful if its final hypothesis describes a finite variant of the target
concept – henceforth called learning with anomalies. As usual, we distinguish between learning from only positive data and learning from positive
and negative data.
We investigate the following learning models: finite identification, conservative inference, set-driven learning, and behaviorally correct learning.
In general, we focus our attention on the case that the number of allowed
anomalies is finite but not a priori bounded. However, we also present
a few sample results that affect the special case of learning with an apriori bounded number of anomalies. We provide characterizations of
the corresponding models of learning with anomalies in terms of finite
tell-tale sets. The varieties in the degree of recursiveness of the relevanttell-tale sets observed are already sufficient to quantify the differences in
the corresponding models of learning with anomalies.
In addition, we study variants of incremental learning and derive a complete picture concerning the relation of all models of learning with andwithout anomalies mentioned above.

1

Introduction

Induction constitutes an important feature of learning. The corresponding theoryis called inductive inference. Inductive inference may be characterized as thestudy of systems that map evidence on a target concept into hypotheses about it.
The investigation of scenarios in which the sequence of hypotheses stabilizes to an
accurate and finite description of the target concept is of some particular interest.
The precise definitions of the notions evidence, stabilization, and accuracy goback to Gold [10] who introduced the model of learning in the limit.
The present paper deals with inductive inference of indexable classes of recursive concepts (indexable classes, for short). A concept class is said to be anindexable class if it possesses an effective enumeration with uniformly decidable membership. Angluin [2] started the systematic study of learning indexable
concept classes. [2] and succeeding publications (cf., e.g., [20], for an overview)found a lot of interest, since most natural concept classes form indexable classes.
For example, the class of all context sensitive, context free, regular, and patternlanguages as well as the set of all boolean formulas expressible as monomial,
k-CNF, k-DNF, and k-decision list constitute indexable classes.
As usual, we distinguish learning from positive data and learning from positive and negative data, synonymously called learning from text and informant,
respectively. A text for a target concept c is an infinite sequence of elements of csuch that every element from c eventually appears. Alternatively, an informant
is an infinite sequence of elements exhausting the underlying learning domainthat are classified with respect to their membership to the target concept.
An algorithmic learner takes as input larger and larger initial segments ofa text (an informant) and outputs, from time to time, a hypothesis about thetarget concept. The set of all admissible hypotheses is called hypothesis space.
When learning of indexable classes is considered, it is natural to require thatthe hypothesis space is an effective enumeration of a (possibly larger) indexable
concept class. This assumption underlies almost all studies (cf., e.g., [2, 20]).
Gold’s [10] original model requires the sequence of hypotheses to converge toa hypothesis correctly describing the target concept. However, from a viewpointof potential applications, it suffices in most cases that the final hypothesis approximates the target concept sufficiently well. Blum and Blum [5] introduced
a quite natural refinement of Gold’s model that captures this aspect. In their
setting of learning recursive functions with anomalies, it is admissible that thelearner’s final hypothesis may differ from the target function at finitely many
data points. Case and Lynes [6] adapted this model to language learning.
Learning with anomalies has been studied intensively in the context of learning recursive functions and recursively enumerable languages (cf., e.g., [11]). Preliminary results concerning the learnability of indexable classes with anomalies
can be found in Tabe and Zeugmann [17]. Note that Baliga et al. [3] studied thelearnability of indexable classes with anomalies, too. However, unlike all otherwork on learning indexable classes, [3] allows the use of arbitrary hypothesis
spaces (including those not having a decidable membership problem). Therefore, the results from [3] do not directly translate into our setting.
The present paper provides a systematic study of learning indexable concept
classes with anomalies. We investigate the following variants of Gold-style concept learning: finite identification, conservative inference, set-driven inference,
behaviorally correct learning, and incremental learning. We relate the resulting
models of learning with anomalies to one another as well as to the corresponding
versions of learning without anomalies. In general, we focus our attention to thecase that the number of allowed anomalies is finite but not a priori bounded.
However, we also present a few sample results that affect the special case thatthe number of allowed anomalies is a priori bounded.
Next, we mention some prototypical results. In the setting of learning withanomalies, the learning power of set-driven learners, conservative learners, andunconstrained IIMs does coincide. In contrast, when anomaly-free learning is
considered, conservative learners and set-driven learners are strictly less power-

ful. Moreover, a further difference to learning without anomalies is establishedby showing that behaviorally correct learning with anomalies is strictly more
powerful than learning in the limit with anomalies. Furthermore, in case thenumber of allowed anomalies is finite but not a priori bounded, it is proved that
there is no need to use arbitrary hypothesis spaces in order to design superior
behaviorally correct learners, thus refining the corresponding results from [3].
However, if the number of anomalies is a priori bounded, it is advantageous
to use arbitrary hypothesis spaces. In order to establish these results, we provide characterizations of the corresponding models of learning with anomalies
in terms of finite tell-tale sets (cf. [2]). As it turns out, the observed varieties inthe degree of recursiveness of the relevant tell-tale sets are already sufficient toquantify the differences in the corresponding models of learning with anomalies.
Moreover, we derive a complete picture concerning the relation of the different
models of incremental learning with and without anomalies.

2

Preliminaries

2.1

Basic notions

Let IN = {0, 1, 2, . . .} be the set of all natural numbers. By h., .i: IN × IN → IN wedenote Cantor’s pairing function. Let A and B be sets. As usual, A4B denotes
the symmetrical difference of A and B, i.e., A4B = (A \ B) ∪ (B \ A). We write
A # B to indicate that A4B 6= ∅. For all a ∈ IN, A =a B iff card (A4B) ≤ a,while A =∗ B iff card (A4B) < ∞. We let σ  τ denote the concatenation of two
possibly infinite sequences σ and τ .
Any recursively enumerable set X is called a learning domain. By ℘(X ) we
denote the power set of X . Let C ⊆ ℘(X ) and let c ∈ C. We refer to C and cas to a concept class and a concept, respectively. Sometimes, we will identify
a concept c with its characteristic function, i.e., we let c(x) = +, if x ∈ c, andc(x) = −, otherwise. What is actually meant will become clear from the context.
We deal with the learnability of indexable concept classes with uniformly
decidable membership defined as follows (cf. [2]). A class of non-empty concepts C
is said to be an indexable concept class with uniformly decidable membership if
there are an effective enumeration (cj )j∈IN of all and only the concepts in C and arecursive function f such that, for all j ∈ IN and all x ∈ X , it holds f (j, x) = +,if x ∈ cj , and f (j, x) = −, otherwise. We refer to indexable concept classes withuniformly decidable membership as to indexable classes, for short, and let IC
denote the collection of all indexable classes.
2.2Gold-style concept learning

Let X be the underlying learning domain, let c ⊆ X be a concept, and let t =(xn )n∈IN be an infinite sequence of elements from c such that {xn | n ∈ IN} = c.
Then, t is said to be a text for c. By Text(c) we denote the set of all texts for c.
Let t be a text and let y be a number. Then, ty denotes the initial segment of t
of length y + 1. Furthermore, we set content(ty ) = {xn | n ≤ y}.

Let CSbe an indexable class. Then, we let Text(C) be the collection of all
texts in c∈C Text(c).
As in [10], we define an inductive inference machine (abbr. IIM ) to be analgorithmic mapping from initial segments of texts to IN ∪ {?}. Thus, an IIM
either outputs a hypothesis, i.e., a number encoding a certain computer program,or it outputs “?,” a special symbol representing the case the machine outputs“no conjecture.” Note that an IIM, when learning some target class C, is required
to produce an output when processing any admissible information sequence, i.e.,
any initial segment of any text in Text(C).
The numbers output by an IIM are interpreted with respect to a suitablychosen hypothesis space H = (hj )j∈IN . Since we exclusively deal with the learnability of indexable classes C, we always assume that H is also an indexing ofsome possibly larger indexable class. Hence, membership is uniformly decidable
in H, too. If C ⊆ {hj | j ∈ IN} (C = {hj | j ∈ IN}), then H is said to be aclass comprising (class preserving) hypothesis space for C (cf. [20]). When an
IIM outputs some number j, we interpret it to mean that it hypothesizes hj .
We define convergence of IIMs as usual. Let t be a text and let M be an IIM.
The sequence (M (ty ))y∈IN of M ’s hypotheses converges to a number j iff all but
finitely many terms of it are equal to j.
Now, we are ready to define learning in the limit.
Definition 1 ([6, 10]). Let C ∈ IC, let c be a concept, let H = (hj )j∈IN be ahypothesis space, and let a ∈ IN ∪ {∗}.
An IIM M Lim aTxt H –identifies c iff, for every t ∈ Text(c), there is a j ∈ IN
with hj =a c such that the sequence (M (ty ))y∈IN converges to j.
M Lim aTxt H –identifies C iff, for all c0 ∈ C, M Lim aTxt H –identifies c0 .
Lim aTxt denotes the collection of all indexable classes C 0 for which there
are a hypothesis space H0 = (h0j )j∈IN and an IIM M such that M Lim aTxt H0 –identifies C 0 .
Subsequently, we write LimTxt instead of Lim 0Txt. We adopt this convention
to all learning types defined below.
In general, it is not decidable whether or not an IIM has already converged ona text t for the target concept c. Adding this requirement to the above definition
results in finite learning (cf. [10]). The resulting learning type is denoted by
Fin aTxt, where again a ∈ IN ∪ {∗}.
Next, we define conservative IIMs. Intuitively speaking, conservative IIMs
maintain their actual hypothesis at least as long as they have not seen data
contradicting it.
Definition 2 ([2]). Let C ∈ IC, let c be a concept, let H = (hj )j∈IN be a hypothesis space, and let a ∈ IN ∪ {∗}.
An IIM M Consv aTxt H –identifies c iff M Lim aTxt H –identifies c and, forevery t ∈ Text(c) and for any two consecutive hypotheses k = M (ty ) and j =M (ty+1 ), if k ∈ IN and k 6= j, then content(ty+1 ) 6⊆ hk .
M Consv aTxt H –identifies C iff, for all c0 ∈ C, M Consv aTxt H –identifies c0 .
For every a ∈ IN ∪ {∗}, the resulting learning type Consv aTxt is defined
analogously to Definition 1.

Next, we define set-driven learning. Intuitively speaking, the output of a setdriven IIM depends exclusively on the content of its input, thereby ignoring theorder as well as the frequency in which the examples occur.
Definition 3 ([18]). Let C ∈ IC, let c be a concept, let H = (hj )j∈IN be ahypothesis space, and let a ∈ IN ∪ {∗}.
An IIM M Sdr aTxt H –identifies c iff M Lim aTxt H –identifies c and, for everyt, t0 ∈ Text(C) and for all n, m ∈ IN, if content(tn ) = content(t0m ) then M (tn ) =M (t0m ).
M Sdr aTxt H –identifies C iff, for all c0 ∈ C, M Sdr aTxt H –identifies c0 .
For every a ∈ IN ∪ {∗}, the resulting learning type Sdr aTxt is defined analogously to Definition 1.
At the end of this subsection, we provide a formal definition of behaviorally
correct learning.
Definition 4 ([4, 6]). Let C ∈ IC, let c be a concept, let H = (hj )j∈IN be ahypothesis space, and let a ∈ IN ∪ {∗}.
An IIM M Bc aTxt H –identifies c iff, for every t ∈ Text(c) and for all but
finitely many y ∈ IN, hM (ty ) =a c.
M Bc aTxt H –identifies C iff, for all c0 ∈ C, M Bc aTxt H –identifies c0 .
For every a ∈ IN ∪ {∗}, the resulting learning type Bc aTxt is defined analogously to Definition 1.
2.3

Incremental concept learning

Now, we formally define the different models of incremental learning. An ordinary IIM M has always access to the whole history of the learning process,i.e., it computes its actual guess on the basis of the whole initial segment of
the text t seen so far. In contrast, an iterative IIM is only allowed to use its
last guess and the next element in t. Conceptually, an iterative IIM M definesa sequence (Mn )n∈IN of machines each of which takes as its input the output of
its predecessor.
Definition 5 ([19]). Let C ∈ IC, let c be a concept, let H = (hj )j∈IN be ahypothesis space, and let a ∈ IN ∪ {∗}.
An IIM M It aTxt H –identifies c iff, for every t = (xn )n∈IN ∈ Text(c), thefollowing conditions are fulfilled:(1) for all n ∈ IN, Mn (t) is defined, where M0 (t) = M (x0 ) and Mn+1 (t) =M (Mn (t), xn+1 ).
(2) the sequence (Mn (t))n∈IN converges to a number j with hj =a c.
M It aTxt H –identifies C iff, for each c0 ∈ C, M It aTxt H –identifies c0 .
For every a ∈ IN ∪ {∗}, the resulting learning type It aTxt is defined analogously to Definition 1.
Let M be an iterative IIM as defined in Definition 5 and t be a text.
Then, M∗ (tn ) denotes the last hypothesis output by M when processing tn ,i.e., M∗ (tn ) = Mn (t). We adopt this convention to all versions of incremental
learners defined below.

Next, we consider a natural relaxation of iterative learning, named k-bounded
example-memory inference. Now, an IIM M is allowed to memorize at most kof the elements in t which it has already seen, where k ∈ IN is a priori fixed.
Again, M defines a sequence (Mn )n∈IN of machines each of which takes as input
the output of its predecessor. A k-bounded example-memory IIM outputs ahypothesis along with the set of memorized data elements.
Definition 6 ([15]). Let C ∈ IC, let c be a concept, let H = (hj )j∈IN be ahypothesis space, let a ∈ IN ∪ {∗}, and let k ∈ IN.
An IIM M Bem akTxt H –identifies c iff, for every t = (xn )n∈IN ∈ Text(c), thefollowing conditions are satisfied:(1) for all n ∈ IN, Mn (t) is defined, where M0 (t) = M (x0 ) = hj0 , S0 i suchthat S0 ⊆ {x0 } and card (S0 ) ≤ k and Mn+1 (t) = M (Mn (t), xn+1 ) =hjn+1 , Sn+1 i such that Sn+1 ⊆ Sn ∪ {xn+1 } and card (Sn+1 ) ≤ k.
(2) the jn in the sequence (hjn , Sn i)n∈IN of M ’s guesses converge to a number jwith hj =a c.
M Bem akTxt H –identifies C iff, for each c0 ∈ C, M Bem akTxt H –identifies c0 .
For every k ∈ IN and every a ∈ IN ∪ {∗}, the resulting learning type Bem akTxt
is defined analogously to Definition 1. By definition, Bem a0Txt = It aTxt.
Next, we define learning by feedback IIMs. Informally speaking, a feedback
IIM M is an iterative IIM that is additionally allowed to make a particular typeof queries. In each learning stage n + 1, M has access to the actual input xn+1
and its previous guess jn . Moreover, M computes a query from xn+1 and jn
which concerns the history of the learning process. That is, the feedback learnercomputes a data element x and receives a “Yes/No” answer A(x) such that
A(x) = 1, if x ∈ content(tn ), and A(x) = 0, otherwise. Hence, M can justask whether or not the particular data element x has already been presented inprevious learning stages.
Definition 7 ([19]). Let C ∈ IC, let c be a concept, let H = (hj )j∈IN be ahypothesis space, let a ∈ IN ∪ {∗}, and let Q: IN × X → X be a total computablefunction. An IIM M , with a computable query asking function Q, Fb aTxt H –identifies c iff, for every t = (xn )n∈IN ∈ Text(c), the following conditions are
satisfied:(1) for all n ∈ IN, Mn (t) is defined, where M0 (t) = M (x0 ) as well as Mn+1 (t) =M (Mn (t), A(Q(Mn (t), xn+1 )), xn+1 ).
(2) the sequence (Mn (t))n∈IN converges to a number j with hj =a c provided A
truthfully answers the questions computed by Q.
M Fb aTxt H –identifies C iff, for each c0 ∈ C, M Fb aTxt H –identifies c0 .
For every a ∈ IN ∪ {∗}, the resulting learning type Fb aTxt is defined analogously to Definition 1.

3

Learning from positive data only

In this section, we study the power and the limitations of the various modelsof learning with anomalies. We relate these models to one another as well as tothe different models of anomaly-free learning. We are mainly interested in thecase that the number of allowed anomalies is finite but not a priori bounded.
Nevertheless, in order to give an impression of how the overall picture changes
when the number of allowed anomalies is a priori bounded, we also present
selected results for this case.
3.1

Gold-style learning with anomalies

Proposition 1 summarizes the known relations between the considered modelsof anomaly-free learning from text.
Proposition 1 ([10, 14, 16]).
FinTxt ⊂ ConsvTxt = SdrTxt ⊂ LimTxt = BcTxt ⊂ IC.
In the setting of learning recursive functions the first observation made whencomparing learning in the limit with anomalies to behaviorally correct inference
was the error correcting power of Bc-learners, i.e., Ex ∗ ⊆ Bc (cf., e.g., [4, 7]).
Interestingly enough, this result did not translate into the setting of learning
recursively enumerable languages from positive data (cf. [6]). But still, a certain
error correcting power is preserved in this setting, since Lim aTxt ⊆ Bc bTxt
provided a ≤ 2b (cf. [6]).
When comparing learning with and without anomalies in our setting of learning indexable classes, it turns out that even finite learners may become more
powerful than Bc-learners.
Theorem 1. Fin 1Txt \ BcTxt 6= ∅.
However, the opposite is also true. For instance, PAT , the well-known classof all pattern languages (cf. [2]), witnesses the even stronger result:
Theorem 2. ConsvTxt \ Fin ∗Txt 6= ∅.
As we will see, the relation between the standard learning models changes
considerably, if it is no longer required that the learner must almost always output hypotheses that describe the target concept correctly. The following picture
displays the established coincidences and differences by relating the models oflearning with anomalies to one another and by ranking them in the hierarchy ofthe models of anomaly-free learning.
Fin ∗Txt ⊂ Consv ∗Txt = Sdr ∗Txt = Lim ∗Txt ⊂ Bc ∗Txt ⊂ IC
∪
∪
∪
∪
∪
FinTxt ⊂ ConsvTxt = SdrTxt ⊂ LimTxt = BcTxt
To achieve the overall picture, we establish characterizations of all models oflearning with a finite but not a priori bounded number of anomalies. On the
one hand, we present characterizations in terms of finite tell-tale sets. On theother hand, we prove that some of the learning models coincide.
Proposition 2 ([17]). For all C ∈ IC and all a ∈ IN ∪ {∗}: C ∈ Lim aTxt iff
there is an indexing (cj )j∈IN of C and a recursively enumerable family (Tj )j∈INof finite sets such that

(1) for all j ∈ IN, Tj ⊆ cj ,(2) for all j, k ∈ IN, if Tj ⊆ ck ⊆ cj , then ck =a cj .
The characterization of Fin ∗Txt is similar to the known characterization of
FinTxt (cf. [13]).
Theorem 3. For all C ∈ IC: C ∈ Fin ∗Txt iff there is an indexing (cj )j∈IN of C
and a recursively generable family (Tj )j∈IN of finite sets such that(1) for all j ∈ IN, Tj ⊆ cj ,(2) for all j, k ∈ IN, if Tj ⊆ ck , then ck =∗ cj .
In contrast to Proposition 1, when a finite number of errors in the final
hypothesis is allowed, conservative IIMs become exactly as powerful as unconstrained IIMs.
Theorem 4. Lim ∗Txt = Consv ∗Txt.
Proof. Let C ∈ Lim ∗Txt, let H = (hj )j∈IN be a hypothesis space, and let M
be an IIM that Lim ∗Txt H –identifies C. Moreover, assume that M never outputs“?.” The conservative IIM M 0 uses the following hypothesis space H0 . For allj ∈ IN and x ∈ X , we let h0j,x = hj \ {x}. Moreover, we let H0 be the canonicalenumeration of all those concepts h0j,x .
Let c ∈ C, let t = (xj )j∈IN be a text for c, and let y ∈ IN. On input ty , M 0determines j = M (ty ), and outputs the canonical index of h0j,x0 in H0 .
It is straightforward to verify that M is a conservative IIM that witnesses
C ∈ Lim ∗Txt.
2
As it turns out, when learning with anomalies is considered, set-driven learners become exactly as powerful as unconstrainted IIMs, again nicely contrasting
Proposition 1.
Theorem 5. Sdr ∗Txt = Lim ∗Txt.
However, there is a difference between conservative inference and set-driven
learning, on the one hand, and learning in the limit, on the other hand, which
we want to point out next. While learning in the limit is invariant to the choiceof the hypothesis space (cf. [17]), conservative inference and set-driven learning,respectively, is not. Moreover, in order to design a superior conservative and a
set-driven learner, respectively, it is sometimes inevitable to select a hypothesis
space that contains concepts which are not subject to learning.
Theorem 6.
(1) There is an indexable class C ∈ Consv ∗Txt such that, for all class preserving
hypothesis spaces H for C, there is no IIM M that Consv ∗Txt H –identifies C.
(2) There is an indexable class C ∈ Sdr ∗Txt such that, for all class preserving
hypothesis spaces H for C, there is no IIM M that Sdr ∗Txt H –identifies C.
For conservative learning and set-driven inference without anomalies, theanalogue of Theorem 6 holds, as well (cf. [14, 16]).
Next, we study behaviorally correct identification. As we will see, finite telltale sets form a conceptual basis that is also well-suited to characterize thecollection of all Bc ∗Txt–identifiable indexable classes. Surprisingly, the existenceof the corresponding tell-tale sets is still sufficient.
Theorem 7. For all C ∈ IC: C ∈ Bc ∗Txt iff there is an indexing (cj )j∈IN of C
and a family (Tj )j∈IN of finite sets such that(1) for all j ∈ IN, Tj ⊆ cj ,(2) for all j, k ∈ IN, if Tj ⊆ ck ⊆ cj , then ck =∗ cj .
Proof. Due to the space constraint we sketch the sufficiency part, only. First,
we define an appropriate hypothesis space H = (hhj,ki )j,k∈IN . Let (Fj )j∈IN be aneffective enumeration of all finite subsets of X and let (wj )j∈IN be the lexicographically ordered enumeration of all elements in X .
We subsequently use the following notions and notations. For all c ⊆ X andall z ∈ IN, we let cz = {wr | r ≤ z, wr ∈ c}. Moreover, for all j, k, z ∈ IN, we
let S(j,k,z) be the set of all indices r ≤ k that meet (i) Fj ⊆ cr and (ii), for all
r0 < r with cr0 ⊇ Fj , czr ⊂ czr0 .
Now, we are ready to define the required hypothesis space H. For all j, k ∈ IN
we define the characteristic function of hhj,ki as follows. If S(j,k,z) = ∅, we set
hhj,ki (wz ) = −. If S(j,k,z) 6= ∅, we let n = max S(j,k,z) and set hhj,ki (wz ) =cn (wz ).
Since membership is uniformly decidable in (cj )j∈IN , we know that H constitutes an admissible hypothesis space.
The required IIM M is defined as follows. Let c ∈ C, t ∈ Text(c), and y ∈ IN.
IIM M : “On input ty proceed as follows:
Determine j ∈ IN with Fj = content(ty ) and output hj, yi.”Due to lack of space, the verification of M ’c correctness is omitted.

2Note that Baliga et al. [3] have recently shown that the same characterizing
condition completely describes the collection of all indexable classes that are
Bc ∗Txt–identifiable with respect to arbitrary hypothesis spaces (including hypothesis space not having a decidable membership problem). Hence, our result
refines the result from [3] in that it shows that, in order to Bc ∗Txt–identify anindexable class, it is always possible to select a hypothesis space with uniformly
decidable membership. However, as we see next, it is inevitable to select theactual hypothesis space appropriately.
Theorem 8. There is an indexable class C ∈ Bc ∗Txt such that, for all classpreserving hypothesis spaces H for C, there is no IIM M that Bc ∗Txt H –learns C.
In contrast, BcTxt is invariant to the choice of the hypothesis space.
To be complete, note that it is folklore that there are indexable classes which
are not Bc ∗Txt-identifiable. Furthermore, applying the stated characterizationsof the learning types Fin ∗Txt, Lim ∗Txt, and Bc ∗Txt, the following hierarchy canbe shown.
Theorem 9. Fin ∗Txt ⊂ Lim ∗Txt ⊂ Bc ∗Txt ⊂ IC.
At the end of this subsection, we turn our attention to the case that the
number of allowed anomalies is a priori bounded. On the one hand, Case andLynes’ [6] result that Lim 2aTxt ⊆ Bc aTxt nicely translates into our setting.

Surprisingly, the opposite is also true, i.e., every IIM that Bc aTxt–identifies atarget indexable class can be simulated by a learner that Lim 2aTxt–identifies
the same class, as expressed by the following theorem.
Theorem 10. For all a ∈ IN: Bc aTxt = Lim 2aTxt.
Proof. Let a ∈ IN. As mentioned above, Lim 2aTxt ⊆ Bc aTxt can be shown by
adapting the corresponding ideas from [6] (see also [11], for the relevant details).
Next, we verify that Bc aTxt ⊆ Lim 2aTxt. Let C ∈ Bc aTxt, let H be a hypothesis space, and let M be an IIM that Bc aTxt H –identifies C. Since membership is
uniformly decidable in H, the set {(j, k) | hj 6=2a hk } is recursively enumerable.
Hence, without loss of generality, we may assume that there is a total recursivefunction f : IN → IN × IN such that {f (n) | n ∈ IN} = {(j, k) | hj 6=2a hk }.
The required IIM M 0 also uses the hypothesis space H. Let c ∈ C, t ∈ Text(c),and y ∈ IN.
IIM M 0 : “On input ty proceed as follows:
If y = 0, set z = 0, determine j0 = M (t0 ), and output j0 . If y ≥ 1, determine
j = M 0 (ty−1 ). For all s = z, . . . , y, determine js = M (ts ), and test whether
or not (j, js ) ∈ {f (n) | n ≤ y}. In case there is no such pair, then output j.
Otherwise, set z = y and output jy .”Since M Bc aTxt H –identifies c from t, there has to be a least y such that, forall y 0 ≥ y, hM (ty0 ) =a c, and therefore, for all y 0 , y 00 ≥ y, hM (ty0 ) =2a hM (ty00 ) .
Hence, M 0 converges on t to a hypothesis j that meets hj =2a c.
2Applying Theorem 2, we may conclude:
Corollary 11. For all C ∈ IC and all a ∈ IN: C ∈ Bc aTxt iff there is an indexing(cj )j∈IN of C and a recursively enumerable family (Tj )j∈IN of finite sets such that(1) for all j ∈ IN, Tj ⊆ cj , and(2) for all j, k ∈ IN, if Tj ⊆ ck and ck ⊆ cj , then ck =2a cj .
The latter corollary nicely contrasts the results in [3]. When arbitrary hypothesis spaces are admissible (including hypothesis space not having a decidable
membership problem), there is no need to add any recursive component, i.e., theexistence of the corresponding tell-tale sets is again sufficient.
Moreover, the relation between set-driven learners and conservative inferencechanges completely, if the number of allowed anomalies is a priori bounded.
S
Theorem 12. Consv 1Txt \ a∈IN Sdr aTxt 6= ∅.
Theorem 13. For all a ∈ IN: Sdr aTxt ⊂ Consv aTxt.
The relation between conservative learners and unconstrained IIMs is also
affected, if the number of allowed anomalies is a priori bounded.
Theorem 14. For all a ∈ IN: Lim aTxt ⊂ Consv a+1Txt ⊂ Lim a+1Txt.
Proof. Let a ∈ IN. By definition, we get Consv a+1Txt ⊆ Lim a+1Txt. Moreover, Consv a+1Txt \ Lim aTxt 6= ∅ follows via Theorem 15 below. Furthermore,
Lim a+1Txt \ Consv a+1Txt 6= ∅ can be shown by diagonalization.
It remains to show that Lim aTxt ⊆ Consv a+1Txt. To see this, recall thedefinition of the conservative IIM M 0 from the demonstration of Theorem 4. It

is easy to see that the final hypothesis of M 0 differs at most at one data pointfrom the final hypothesis of the unconstrained IIM M which M 0 simulates. 2
Finally, when learning with an a priori bounded number of allowed anomalies
is considered, the existence of infinite hierarchies of more and more powerful
Fin-learners, Consv -learners, Lim-learners, and Bc-learners, parameterized in
the number of allowed anomalies, can be shown. The following theorem provides
the missing piece to establish these infinite hierarchies.
Theorem 15. For all a ∈ IN: Fin 2a+1Txt \ Bc aTxt 6= ∅.
3.2

Incremental learning with anomalies

Proposition 3 summarizes the known results concerning incremental learning.
Proposition 3 ([15]).
(1) ItTxt ⊂ FbTxt.
(2) ItTxt ⊂ Bem 1Txt.
(3) For all k ∈ IN, Bem kTxt ⊂ Bem k+1Txt.
(4) Bem 1TxtS\ FbTxt 6= ∅.
(5) FbTxt \ k∈IN Bem kTxt 6= ∅.
The overall picture remains unchanged for incremental learning with a finite
number of allowed anomalies.
More specifically, iterative learners that have the freedom to store one additional example may outperform feedback learners that are allowed to make up
to finitely many errors in their final hypothesis.
Theorem 16. Bem 1Txt \ Fb ∗Txt 6= ∅.
Proof. The separating class C is defined as follows. C contains c0 = {a}+ and,for all j ≥ 1, cj = {a` | 1 ≤ ` ≤ 2j} ∪ {b}+ . Moreover, for all j, k, m ≥ 1, C
contains the concept c0j,k,m = {a` | 1 ≤ ` ≤ 2j} ∪ {a2hj,ki+1 } ∪ {b` | 1 ≤ ` ≤ m}.
Claim 1. C ∈ Bem 1Txt.
The required IIM M updates its example-memory as follows. As long as noelement from {b}+ occurs, M memorizes the maximal element from {a}+ seen
so far. Otherwise, it memorizes the maximal element from {b}+ that has beenpresented so far. In addition, M updates its hypotheses in accordance with thefollowing cases.
Case 1. M has never received an element from {b}+ .
Then, M guesses c0 .
Case 2. M receives an element x from {b}+ for the first time.
Let x = bm . If M has memorized an element of type a2j , M guesses cj . If
it has memorized an element of type a2hj,ki+1 , M guess c0j,k,m . If x is the firstelement presented at all, M simply guesses c1 .
Case 3. Otherwise.
Let x be the new element presented, let c0 be M ’s actual guess, and let bm
be the element memorized by M .
First, if x ∈ {b}+ and c0 is of type c0j,k,m , M guesses c0j,k,m0 , where m0 =max {m, |x|}. If x ∈ {b}+ and c0 is of type cj , M guesses c0 .

Second, if x ∈ {a}+ and x ∈ c0 , M guesses c0 . If x ∈ {a}+ , x ∈/ c0 , and x
2j+0
is of type a , M guesses cj . Otherwise, i.e., x ∈ {a} , x ∈/ c , and x is of typea2hj,ki+1 , M guesses c0j,k,m
The verification of M ’s correctness is straightforward.
Claim 2. C ∈/ Fb ∗Txt.
Suppose to the contrary that there is a feedback learner M 0 that witnesses
C ∈ Lim ∗Txt. Hence, there is a locking sequence σ for c0 , i.e., σ is a finite
sequence with content(σ) ⊆ c0 and, for all finite sequences ρ with content(ρ) ⊆c0 , M∗0 (σ  ρ) = M∗0 (σ).
Let j be the least index with content(σ) ⊆ cj . Consider M when fed thetext t = σ  a, . . . , a2j  b  b, b2  b, b2 , b3  · · ·  b, b2 , . . . , bn  · · · for cj . Since M 0learns cj , M 0 converges on t. Hence, there is a y such that (i) the last element
in ty equals b and (ii), for all r ∈ IN, M∗0 (ty ) = M∗0 (ty+r ).
Finally, fix τ such that ty = σ  a, . . . , a2j  τ . Let k, m be the least indicessuch that content(ty ) ⊆ c0j,k,m and a2hj,ki+1 is an element from c0 which M 0
has never asked for when processing ty . Consider M 0 when fed the text t0 =σ  a, . . . , a2j  a2hj,ki+1  τ  b, b, . . . for c0j,k,m . By the choice of σ und y, M 0converges on t and t0 to the same hypothesis. (To see this note that the b’s at
the end of t0 guarantee that M 0 almost always ask the same question as in case it
is fed ty , thereby, due to choice of a2hj,ki+1 , always receiving the same answer.)
Since cj 6=∗ c0j,k,m , M 0 cannot learn both concepts, a contradiction.
2
The opposite holds, as well. Feedback queries may compensate the ability ofa bounded-example memory learner to memorize any a priori fixed number ofexamples and to make finitely many errors in its final hypothesis.
S
Theorem 17. FbTxt \ k∈IN Bem ∗kTxt 6= ∅S
Proof. We define the separating class C as follows. We set C = k∈IN Ck ,where, for all k ∈ IN, the subclass Ck is defined as follows.
Let (Fj )j∈IN be a repetition-free enumeration of all finite sets of natural
numbers. By convention, let F0 = ∅. Moreover, we let P0 = {b}+ and Pj+1 =Pj \ {bnpj | n ≥ 1}, where, for all j ∈ IN, pj is the j + 1-st prime number.
Let k ∈ IN. Then, Ck contains the concept c0 = {a}+ as well as, for all
j, m ≥ 1 and all l0 , . . . , lk with j < l0 < · · · < lk , the concept c(j,m,l0 ,...,lk ) ={a` | 1 ≤ ` ≤ j} ∪ {al0 , . . . , alk } ∪ {bj+1 | j ∈ Fm } ∪ Phl0 ,...,lk i ∪ {dj }.
By definition, C contains exclusively infinite concepts, and thus C ∈ FbTxt(cf. [8], for the relevant
S details).
For proving C ∈/ k∈IN Bem ∗kTxt, it suffices to show that, for every k ∈ IN,
Ck ∈/ Bem ∗kTxt. The corresponding verification is part of the demonstration ofTheorem 18 below.
2
Our next result illustrates the error-correcting power of bounded examplememories. As it turns out, every additional example which an incremental learnercan memorize may help to correct up to finitely many errors.
Theorem 18. For all k ∈ IN, Bem k+1Txt \ Bem ∗kTxt 6= ∅.
Proof. Let k ∈ IN. We claim that Ck (cf. the demonstration of Theorem 17
above) separates the learning types Bem k+1Txt and Bem ∗kTxt.

Claim 1. Ck ∈ Bem k+1Txt.
The required bounded example-memory learner M behaves as follows. As arule, M memorizes the k + 1 longest elements from {a}+ which it has seen so
far. Moreover, M updates its hypotheses in accordance with the following cases.
Case 1. M has never received an element from {d}+ .
Then, M outputs an index for the concept c0 that allows M to determine all
elements from {b}+ that have been presented so far.
Case 2. M receives an element x from {d}+ for the first time.
Let x = dj and let S 0 be the set of all elements from {b}+ seen so far. M
outputs an index for the concept {a` | 1 ≤ ` ≤ j} ∪ {dj } ∪ S 0 that allows M todetermine the elements in S 0 .
Case 3. Otherwise.
We distinguish the following subcases.
Case 3.1. M has memorized k + 1 elements s with |s| > j.
Let x be the new element presented, let S = {al0 , . . . , alk } be the set ofelements memorized by M , and let S 0 be the set of elements from {b+ } that are
encoded in M ’s last hypothesis. If x ∈ {b}+ \ Phl0 ,...,lk i , we let S 0 = S 0 ∪ {x}.
Otherwise, S 0 remains unchanged. Moreover, M outputs an index for the concept{a` | 1 ≤ ` ≤ j} ∪ S ∪ S 0 ∪ Phl0 ,...,lk i ∪ {dj } that allows M to recompute theelements in S 0 .
Case 3.2. Not Case 3.1.
As above, M outputs an index of the concept {a` | 1 ≤ ` ≤ j} ∪ {dj } ∪ S 0
that allows M to determine the elements in S 0 , where S 0 is again the set of allelements from {b}+ seen so far.
The verification of M ’s correctness is straightforward.
Claim 2. Ck ∈/ Bem ∗kTxt.
Suppose to the contrary that there is a k-bounded example-memory learnerM 0 that witnesses C ∈ Lim ∗Txt. Hence, there is a locking sequence σ for c0 ,i.e., σ is a finite sequence with content(σ) ⊆ c0 and, for all finite sequences ρwith content(ρ) ⊆ c0 , π1 (M∗0 (σ  ρ)) = π1 (M∗0 (σ)).4 Now let j = max {|x| | x ∈content(σ)}. Similarly as in the demonstration of Theorem 6 in [15], one may
use counting arguments to show that there are indices l0 , l00 , . . . , lk , lk0 such that
Conditions (a) to (d) are fulfilled, where(a) j < l0 < l1 < · · · < lk .
(b) j < l00 < l10 < · · · < lk0 .
(c) {l0 , l1 , . . . , lk } =6 {l00 , l10 , . . . , lk0 }.
00(d) M∗0 (σ  al0 , . . . , alk ) = M∗0 (σ  al0 , . . . , alk ).
Assume that hl0 , . . . , lk i < hl00 , . . . , lk0 i. Let t1 and t01 be the lexicographicallyordered text for Phl0 ,...,lk i and Phl00 ,...,lk0 i , respectively. Moreover, we set σ 0 =σ  a, a2 , . . . , aj . Since M 0 infers c(j,0,l0 ,...,lk ) , there is a finite sequence τ with
content(τ ) ⊆ Phl0 ,...,lk i such that, for all finite sequences ρ with content(ρ) ⊆Phl0 ,...,lk i , π1 (M∗0 (σ 0  al0 , . . . , alk  dj  τ )) = π1 (M∗0 (σ 0  al0 , . . . , alk  dj  τ  ρ)).
4

Recall that M outputs pairs hj, Si. By convention, we let π1 (hj, Si) = j.

Now, fix m0 ∈ IN with Fm0 = {` | b` ∈ content(τ )} and consider M 0 whensuccessively fed the text t = σ 0  al0 , al1 , . . . , alk  dj  τ  t1 for c(j,0,l0 ,...,lk ) and000
the text t0 = σ 0  al0 , al1 , . . . , alk  dj  τ  t01 for c(j,m0 ,l00 ,...,lk0 ) , respectively. By the
choice of σ and τ and since, by definition, Phl00 ,...,lk0 i ⊂ Phl0 ,...,lk i , we may conclude
that M 0 converges to the same hypothesis when fed t and t0 , respectively. Sincec(j,0,l0 ,...,lk ) 6=∗ c(j,m0 ,l00 ,...,lk0 ) , M 0 cannot learn both concepts, a contradiction. 2
For incremental learning with anomalies, Proposition 3 rewrites as follows.
Corollary 19.
(1) It ∗Txt ⊂ Fb ∗Txt.
(2) It ∗Txt ⊂ Bem ∗1Txt.
(3) For all k ∈ IN, Bem ∗kTxt ⊂ Bem ∗k+1Txt.
(4) Bem ∗1Txt S\ Fb ∗Txt 6= ∅.
∗(5) Fb Txt \ k∈IN Bem ∗kTxt 6= ∅.

4

Learning from positive and negative data

In the section, we briefly summarize the results that can be obtained whenstudying learning with anomalies from positive and negative data.
Let X be the underlying learning domain, let c ⊆ X be a concept, andlet i = ((xn , bn ))n∈IN be any sequence of elements of X × {+, −} such that
content(i) = {xn | n ∈ IN} = X , content + (i) = {xn | n ∈ IN, bn = +} = c andcontent − (i) = {xn | n ∈ IN, bn = −} = X \ c = c. Then, we refer to i as an
informant. By Info(c) we denote the set of all informants for c.
For all a ∈ IN ∪ {∗}, the standard learning models Fin aInf , Consv aInf ,Lim aInf and Bc aInf are defined analogously as their text counterparts by replacing text by informant. Moreover, we extend the definitions of all variants ofiterative learning in the same manner and denote the resulting learning types
by It aInf , Fb aInf , and Bem akInf , where k ∈ IN.
Since IC = ConsvInf (cf. [10]), we may easily conclude:
Corollary 20.
For all a ∈ IN ∪ {∗}: ConsvInf = Consv aInf = Lim aInf = Bc aInf .
Moreover, one can easily show that the known inclusions FinTxt ⊂ FinInf
and FinInf ⊂ ConsvTxt (cf. [13]) rewrite as follows:
Theorem 21. Fin ∗Txt ⊂ Fin ∗Inf ⊂ Consv ∗Txt.
Concerning incremental learning, it has recently be shown that IC = FbInf =Bem 1Inf (cf. [12]). Clearly this allows for the following corollary.
Corollary 22. For all a ∈ IN ∪ {∗}: ConsvInf = Fb aInf = Bem a1Inf .
Moreover, it is folklore that IC = It ∗Inf . In contrast, if the number of allowed
anomalies is a priori bounded, an infinite hierarchy of more and more powerfuliterative learners can be observed.
Theorem 23. ItInf ⊂ It 1Inf ⊂ It 2Inf ⊂ · · · ⊂ It ∗Inf = ConsvInf .
Finally, it is not hard to verify that the results obtained so far prove theexistence of an infinite hierarchy of more and more powerful finite learners parameterized in the number of allowed anomalies.

References
1. D. Angluin. Finding patterns common to a set of strings. Journal of Computer and
System Sciences, 21:46–62, 1980.
2. D. Angluin. Inductive inference of formal languages from positive data. Information
and Control, 45:117–135, 1980.
3. G.R. Baliga, J. Case, and S. Jain. The synthesis of language learners. Information
and Computation, 152:16–43, 1999.
4. J. Bārzdiņš. Two theorems on the limiting synthesis of functions. In Theory of Algorithms and Programs Vol. 1, pages 82–88, Latvian State University, 1974, (Russian).
5. L. Blum and M. Blum. Toward a mathematical theory of inductive inference. Information and Control, 28:122–155, 1975.
6. J. Case and C. Lynes. Machine inductive inference and language identification.
In Proc. 9th International Colloquium on Automata, Languages and Programming,
Lecture Notes in Computer Science 140, pages 107–115. Springer-Verlag, Berlin,
1982.
7. J. Case and C.H. Smith. Comparison of identification criteria for machine inductive
inference. Theoretical Computer Science 25:193–220, 1983.
8. J. Case, S. Jain, S. Lange, and T. Zeugmann, Incremental concept learning forbounded data mining. Information and Computation 152:74–110, 1999.
9. M. Fulk. Prudence and other restrictions in formal language learning. Information
and Computation, 85:1–11, 1990.
10. E.M. Gold. Language identification in the limit. Information and Control, 10:447–
474, 1967.
11. S. Jain, D. Osherson, J. Royer, and A. Sharma. Systems that Learn - 2nd Edition,
An Introduction to Learning Theory. MIT Press, Cambridge, Mass., 1999.
12. S. Lange and G. Grieser. On the strength of incremental learning. In Proc. 10th International Conference on Algorithmic Learning Theory, Lecture Notes in Artificial
Intelligence 1720, pages 118–131. Springer-Verlag, Berlin, 1999.
13. S. Lange and T. Zeugmann. Types of monotonic language learning and theircharacterization. In Proc. 5th Annual ACM Workshop on Computational Learning
Theory, pages 377–390. ACM Press, New York, 1992.
14. S. Lange and T. Zeugmann. Language learning in dependence on the space of hypotheses. In Proc. 6th Annual ACM Conference on Computational Learning Theory,
pages 127–136. ACM Press, New York, 1993.
15. S. Lange and T. Zeugmann. Incremental learning from positive data. Journal ofComputer and System Sciences, 53:88–103, 1996.
16. S. Lange and T. Zeugmann. Set-driven and rearrangement-independent learningof recursive languages. Mathematical Systems Theory, 29:599–634, 1996.
17. T. Tabe and T. Zeugmann. Two variations of inductive inference of languages frompositive data. Technical Report RIFIS-TR-CS-105, Kyushu University, 1995.
18. K. Wexler and P. Culicover. Formal Principles of Language Acquisition. MIT
Press, Cambridge, Mass., 1980.
19. R. Wiehagen. Limes-Erkennung rekursiver Funktionen durch spezielle Strategien.
Journal of Information Processing and Cybernetics (EIK), 12:93–99, 1976.
20. T. Zeugmann and S. Lange. A guided tour across the boundaries of learning
recursive languages. In K.P. Jantke and S. Lange, editors, Algorithmic Learning
for Knowledge-Based Systems, Lecture Notes in Artificial Intelligence 961, pages
190–258. Springer-Verlag, Berlin, 1995.