TCS -TR-A-05-08

TCS Technical Report

From Learning in the Limit to Stochastic Finite
Learning

byThomas Zeugmann

Division of Computer Science
Report Series A
August 27, 2005

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

thomas@ist.hokudai.ac.jp

Phone:
Fax:+81-011-706-7684+81-011-706-7684

From Learning in the Limit to Stochastic Finite
Learning
Thomas Zeugmann
Division of Computer Science
Hokkaido University
N-14, W-9, Sapporo 060-0814, Japanthomas@ist.hokudai.ac.jp

August 27, 2005
Abstract
Inductive inference can be considered as one of the fundamental paradigmsof algorithmic learning theory. We survey results recently obtained and show
their impact to potential applications.
Since the main focus is put on the efficiency of learning, we also deal withpostulates of naturalness and their impact to the efficiency of limit learners. In
particular, we look at the learnability of the class of all pattern languages andask whether or not one can design a learner within the paradigm of learning in
the limit that is nevertheless efficient.
For achieving this goal, we deal with iterative learning and its interplay
with the hypothesis spaces allowed. This interplay has also a severe impact topostulates of naturalness satisfiable by any learner.
Furthermore, since a limit learner is only supposed to converge, one neverknows at any particular learning stage whether or not the learner did alreadysucceed. The resulting uncertainty may be prohibitive in many applications. We
survey results to resolve this problem by outlining a new learning model, calledstochastic finite learning. Though pattern languages can neither be finitely
inferred from positive data nor PAC-learned, our approach can be extended toa stochastic finite learner that exactly infers all pattern languages from positive
data with high confidence.
Finally, we apply the techniques developed to the problem of learning conjunctive concepts.

1. Introduction
Inductive inference can be considered as one of the fundamental paradigms ofalgorithmic learning theory. In particular, inductive inference of recursive functions
and of recursively enumerable languages has been studied intensively within the last1

2

Thomas Zeugmannfour decades (cf., e.g., [3, 4, 30, 16]). The basic model considered within this frameworkis learning in the limit which can be informally described as follows. The learnerreceives more and more data about the target and maps these data to hypotheses. Of
special interest is the investigation of scenarios in which the sequence of hypotheses
stabilizes to an accurate and finite description (e.g. a grammar, a program) of thetarget. Clearly, then some form of learning must have taken place. Here by data wemean either any infinite sequence of pairs argument-value (in case of learning recursivefunctions) such that all arguments appear eventually or any infinite sequence of all
members of the target language (in case of language learning from positive data).
Alternatively, one can also study language learning from both positive and negative
data.
Most of the work done in the field has been aimed at the following goals: showing
what general collections of function or language classes are learnable, characterizing
those collections of classes that can be learned, studying the impact of several postulates on the behavior of learners to their learning power, and dealing with the influenceof various parameters to the efficiency of learning. However, defining an appropriate
measure for the complexity of learning in the limit has turned out to be quite difficult(cf. Pitt [31]). Moreover, whenever learning in the limit is done, in general one neverknows whether or not the learner has already converged. This is caused by the factthat it is in general undecidable whether or not convergence already occurred. But
even if it is decidable, it is practically infeasible to do so. Thus, there is always anuncertainty which may be prohibitive in many applications of learning.
Therefore, different learning models have been proposed. In particular, Valiant’s[46] model of probably approximately correct (abbr. PAC) learning has been very influential. As a matter of fact, this model puts strong emphasis on the efficiency oflearning and avoids the problem of convergence at all. In the PAC model, the learnerreceives a finite labeled sample of the target concept and outputs, with high probability, a hypothesis that is approximately correct. The sample is drawn with respect toan unknown probability distribution and the error of as well as the confidence in the
hypothesis are measured with respect to this distribution, too. Thus, if a class is PAC
learnable, one obtains nice performance guarantees. Unfortunately, many interesting
concept classes are not PAC learnable.
Consequently, one has to look for other models of learning or one is back to learningin the limit. So, let us assume that learning in the limit is our method of choice. What
we would like to present in this survey is a rather general way to transform learningin the limit into stochastic finite learning. It should also be noted that our ideas may
be beneficial even in case that the considered concept class is PAC learnable.
Furthermore, we aim to outline how a thorough study of limit learnability of concept classes may nicely contribute to support our new approach. We exemplify the
research undertaken by looking at the class of all pattern languages introduced by Angluin [1]. As Salomaa [37] has put it “Patterns are everywhere” and thus we believethat our research is worth the effort undertaken.

From Learning in the Limit to Stochastic Finite Learning

3

There are several problems that have to be addressed when dealing with the learnability of pattern languages. First, the nice thing about patterns is that they arevery intuitive. Therefore, it seems desirable to design learners outputting patterns
as their hypotheses. Unfortunately, membership is known to be N P -complete forthe pattern languages (cf. [1]). Thus, many of the usual approaches used in machinelearning will directly lead to infeasible learning algorithms. As a consequence, weshall ask what kind of appropriate hypothesis spaces can be used at all to learn thepattern languages, and what are the appropriate learning strategies.
In particular, we shall deal with the problem of redundancy in the hypothesis spacechosen, with consistency, conservativeness, and iterative learning. Here consistency
means that the intermediate hypotheses output by the learner do correctly reflect thedata seen so far. Conservativeness addresses the problem to avoid overgeneralization,i.e., preventing the learner from guessing a proper superset of the target language.
These requirements are naturally arising desiderata, but this does not mean that they
can be fulfilled. With iterative learning, the learning machine, in making a conjecture,
has access to only its previous conjecture and the latest data item coming in. Iterative
learning is also a natural requirement whenever learning in the limit is concerned, sinceno practical learner can process at every learning stage all examples provided so far,it may even not be able to store them.
Then, we address the question how efficient the overall learning process can be
performed, and how we can get rid of the uncertainty of not knowing whether or not
the learner has already converged.
Finally, we show our ideas to be beneficial for a class known to be PAC learnable bylooking at the class of all concepts describable by a monomial. A concept is describableby a monomial m if its elements are precisely the assignments satisfying m .

2. Preliminaries
Unspecified notation follows Rogers [35]. By N = {0, 1, 2, . . .} we denote the setof all natural numbers. We set N+ = N \ {0} . The cardinality of a set S is denoted
by |S| . Let ∅, ∈, ⊂, ⊆ , ⊃ , and ⊇ denote the empty set, element of, proper subset,
subset, proper superset, and superset, respectively.
Let ϕ0 , ϕ1 , ϕ2 , . . . denote any fixed acceptable programming system for all (andonly) the partial recursive functions over N (cf. Rogers [35]). Then ϕk is the partial
recursive function computed by program k .
In the following subsection we define the main learning models considered within
this paper.
2.1. Learning in the Limit
Gold’s [12] model of learning in the limit allows one to formalize a rather generalclass of learning problems, i.e., learning from examples. For defining this model we4Thomas Zeugmann

assume any recursively enumerable set X and refer to it as the learning domain. By℘(X ) we denote the power set of X . Let C ⊆ ℘(X ) , and let c ∈ C be non-empty;
then we refer to C and c as a concept class and a concept, respectively. Let c bea concept, and let t = (xj )j∈N be any infinite sequence of elements xj ∈ c suchthat range(t) := {xj j ∈ N} = c . Then t is said to be a positive presentation or,synonymously, a text for c . By text(c) we denote the set of all positive presentations
for c . Moreover, let t be a positive presentation, and let y ∈ N . Then, we set ty =x0 , . . . , xy , i.e., ty is the initial segment of t of length y + 1 , and t+y := {xj j ≤ y} .
+We refer to ty as the content of ty .
Furthermore, let σ = x0 , . . . , xn−1 be any finite sequence. Then we use |σ| todenote the length n of σ , and let σ + denote the content of σ . Additionally, let t
be a text and let τ be a finite sequence; then we use σ  t and σ  τ to denote thesequence obtained by concatenating σ onto the front of t and τ , respectively.
Alternatively, one can also consider complete presentations or, synonymously, informants. An informant for a concept c is an infinite sequence of all elements of
the underlying learning domain that are classified with respect to their containment in c . More formally, we define informants as follows. Let c be a concept;
then any sequence i = (xj , bj )j∈N of labeled examples, where bj ∈ {0, 1} suchthat {xj j ∈ N} = X and i+ = {xj (xj , bj ) = (xj , 1), j ∈ N} = c andi− = {xj (xj , bj ) = (xj , 0), j ∈ N} = X \ c is called an informant for c . For
the sake of presentation, the following definitions are only given for the text case, thegeneralization to the informant case should be obvious. We sometimes use the term
data sequence to refer to both text and informant, respectively.
An inductive inference machine (abbr. IIM) is an algorithm that takes as input
larger and larger initial segments of a text and outputs, after each input, a hypothesis
from a prespecified hypothesis space H = (hj )j∈N . The indices j are regarded as
suitable finite encodings of the concepts described by the hypotheses. A hypothesis
h is said to describe a concept c iff c = h .
A sequence (jn )n∈N of natural numbers is said to converge to number j if jn = j
for all but finitely many n ∈ N .
Definition 1. Let C be any concept class, and let H = (hj )j∈N be a hypothesis
space for it. C is called learnable in the limit from text with respect to H iff there isan IIM M such that for every c ∈ C and every text t for c ,(1) for all n ∈ N+ , M (tn ) is defined,(2) there is a j such that c = hj and the sequence (M (tn ))n∈N converges to j .
The set of all concepts classes that are learnable in the limit with respect to H isdenoted by LimTxt H . By LimTxt we denote the collection of all concepts classes C
for which there is a hypothesis space H such that C is learnable in the limit fromtext1 with respect to H .
1

If learning from informant is considered we use LimInf H and LimInf in an analogous way.

From Learning in the Limit to Stochastic Finite Learning

5

Note that instead of LimTxt sometimes TxtEx is used. In our notation, Lim stands
for “limit.” Suppose, an IIM learns some concept c . That means, after having seen
only finitely many data of c the IIM reached its (unknown) point of convergence andit computed a correct and finite description of the target concept. Hence, some formof learning must have taken place.
Note that Definition 1 does not contain any requirement concerning efficiency. Before we are going to deal with efficiency, we want to point to another crucial parameterof our learning model, i.e., the hypothesis space H . Since our goal is algorithmic learning, we can consider the special case that X = N and let C be any subset of thecollection of all recursively enumerable sets over N . Let Wk = domain(ϕk ) , where
ϕk is the partial recursive function computed by program k in the fixed acceptable
programming system. In this case, (Wk )k∈N is the most general hypothesis space.
Within this setting many learning problems can be described. Moreover, this setting has been used to study the general capabilities of different learning models which
can be obtained by suitable modifications of Definition 1. There are numerous papers
performing studies along this line of research (cf., e.g., [16, 30] and the references
therein). On the one hand, the results obtained considerably broaden our general
understanding of algorithmic learning. On the other hand, one has also to ask whatkind of consequences one may derive from these results for practical learning problems.
This is a non-trivial question, since the setting of learning recursively enumerable languages is very rich. Thus, it is conceivable that several of the phenomena observed
hold in this setting due to the fact that too many sets are recursively enumerable andthat there are no counterparts within the world of efficient computability.
As a first step to address this question we mainly consider the scenario that indexable concept classes with uniformly decidable membership have to be learned (cf.
Angluin [2]). A class of non-empty concepts C is said to be an indexable classwith uniformly decidable membership provided there are an effective enumeration
c0 , c1 , c2 , ... of all and only the concepts in C and a recursive function f such thatfor all j ∈ N and all elements x ∈ X we have
1, if x ∈ cj ,f (j, x) =0, otherwise.
In the following we refer to indexable classes with uniformly decidable membershipas to indexable classes for short. Furthermore, we call any enumeration (cj )j∈N of C
with uniformly decidable membership problem an indexed family.
Since the paper of Angluin [2], learning of indexable concept classes has attracted
much attention (cf., e.g., Zeugmann and Lange [52]). Let us shortly provide somewell known indexable classes. Let Σ be any finite alphabet of symbols, and let X
be the free monoid over Σ , i.e., X = Σ∗ . We set Σ+ = Σ∗ \ {λ} , where λ denotes
the empty string. As usual, we refer to subsets L ⊆ X as languages. Then the setof all regular languages, context-free languages, and context-sensitive languages areindexable classes.

6

Thomas Zeugmann

Next, let Xn = {0, 1}n be the set of all n -bit Boolean vectors. We considerS
X = n≥1 Xn as learning domain. Then, the set of all concepts expressible as amonomial, a k -CNF, a k -DNF, and a k -decision list form indexable classes.
When learning indexable classes C , it is generally assumed that the hypothesis
space H has to be an indexed family, too. We distinguish class preserving learningand class comprising learning defined by C = range(H) and C ⊆ range(H) , respectively. When dealing with class preserving learning, one has the freedom to choose as
hypothesis space a possibly different enumeration of the target class C . In contrast,
when class comprising learning is concerned, the hypothesis space may enumerate,
additionally, languages not belonging to C . Note that, in general, one has to allow
class comprising hypothesis spaces to obtain the maximum possible learning power(cf. Lange and Zeugmann [20, 22]). Finally, we call an hypothesis space redundant
if it is larger than necessary, i.e., there is at least one hypothesis in H not describing any concept from the target class or one concept possesses at least two different
descriptions in H . Thus, non-redundant hypothesis spaces are as small as possible.
Formally, a hypothesis space H = (hj )j∈N is non-redundant for some target concept
class C iff range(H) = C and hi 6= hj for all i, j ∈ N with i 6= j . Otherwise, H isa redundant hypothesis space for C .
Next, let us come back to the issue of efficiency. Looking at Definition 1 we seethat an IIM M has always access to the whole history of the learning process, i.e.,
in order to compute its actual guess M is fed all examples seen so far. In contrast
to that, next we define iterative IIMs. An iterative IIM is only allowed to use its
last guess and the next element in the positive presentation of the target concept forcomputing its actual guess. Conceptionally, an iterative IIM M defines a sequence(Mn )n∈N of machines each of which takes as its input the output of its predecessor.
Definition 2 (Wiehagen [47]). Let C be a concept class, let c be a concept, andlet H = (hj )j∈N be a hypothesis space. An IIM M ItLimTxt H -learns c iff for everyt = (xj )j∈N ∈ text(c) the following conditions are satisfied:(1) for all n ∈ N , Mn (t) is defined, where M0 (t) := M (x0 ) and for all n ≥ 0 :Mn+1 (t) := M (Mn (t), xn+1 ) ,(2) the sequence (Mn (t))n∈N converges to a number j such that c = hj .
Finally, M ItLimTxt H -learns C iff, for each c ∈ C , M ItLimTxt H -learns c . By
ItLimTxt we denote the collection of all concept classes for which there are an IIM
M and a hypothesis space H such that M ItLimTxt H -learns C .
In the latter definition Mn (t) denotes the (n+1) st hypothesis output by M whensuccessively fed the text t . So, it is justified to make the following convention. Let
σ = x0 , . . . , xn be any finite sequence of elements from X . Moreover, let C be any
concept class over X , and let M be any IIM that iteratively learns C . Then wedenote by My (σ) the (y + 1) st hypothesis output by M when successively fed σFrom Learning in the Limit to Stochastic Finite Learning

7

provided y ≤ n , and there exists a concept c ∈ C with σ + ⊆ c . Furthermore, we letM∗ (σ) denote M|σ|−1 (σ) .
Moreover, when learning a concept class from text, a major problem one has todeal with is avoiding or detecting overgeneralization. An overgeneralization occurs if
the learner is guessing a superconcept of the target concept. Clearly, such an overgeneralized guess cannot be detected by using the incoming positive data only. Hence,
one may be tempted to disallow overgeneralized guesses at all. Learners behaving thus
are called conservative. Intuitively speaking a conservative IIM maintains its actual
hypothesis at least as long as it has not seen data contradicting it. More formally, an
IIM M is said to be conservative iff for all concepts c in the target class C , all texts
t for c and all y, z ∈ N the condition “if M (ty ) 6= M (ty+z ) then t+
y+z 6⊆ hM (ty ) ” isfulfilled.
Another property of learners quite often found in the literature is consistency (cf.,e.g., Wiehagen and Zeugmann [48, 49] and the references therein). A learner is called
consistent if all its intermediate hypotheses correctly reflect the data seen so far.
Formally, an IIM M is said to be consistent iff t+
x ⊆ hM (tx ) for all x ∈ N and every
text t for every concept c in the target class C .
Whenever one talks about the efficiency of learning besides the storage needed by
the learner one has also to consider the time complexity of the learner. When talking
about the time complexity of learning, it does not suffice to consider the time needed
to compute the actual guess. What really counts in applications is the overall timeneeded until successful learning. Therefore, following Daley and Smith [10] we define
the total learning time as follows.
Let C be any concept class, and let M be any IIM that learns C in the limit.
Then, for every c ∈ C and every text t for c , let
Conv (M , t) :=the least number m ∈ N+
such that for all n ≥ m, M (tn ) = M (tm )denote the stage of convergence of M on t (cf. [12]). Moreover, by TM (tn ) we denotethe time to compute M (tn ) . We measure this time as a function of the length of the
input and call it the update time. Finally, the total learning time taken by the IIM
M on successive input t is defined as
Conv (M ,t)

T T (M , t) :=X

TM (tn ).

n=1

Clearly, if M does not learn the target concept from text t then the total learning
time is infinite.
Two more remarks are in order here. First, it has been argued elsewhere thatwithin the learning in the limit paradigm a learning algorithm is invoked only when
the current hypothesis has some problem with the latest observed data. However, such

8Thomas Zeugmanna viewpoint implicitly assumes that membership in the target concept is decidable
in time polynomial in the length of the actual input. This may be not the case.
Therefore, directly testing consistency would immediately lead to a non-polynomial
update time provided membership is not known to be in P .
Second, Pitt [31] addresses the question with respect to what parameter one shouldmeasure the total learning time. In the definition given above this parameter is thelength of all examples seen so far. Clearly, now one could try to play with thisparameter by waiting for a large enough input before declaring success. However,when dealing with the learnability of non-trivial concept classes, in the worst-casethe total learning time will be anyhow unbounded. This effect is caused by therequirement to learn from all input sequences. Clearly, there are input sequences thatstart with many repetitions of data not containing enough information for successful
learning. Thus, it does not make much sense to deal with the worst-case. Instead, weshall study the expected total learning time. In such a setting one cannot simply wait
for long enough inputs. We shall then restrict ourselves to probability distributions
that generate data sequences from which the target can be learned. Therefore, using
the definition of total learning time given above seems to be reasonable.
Next, we define important concept classes which we are going to consider throughout this survey.
2.2. The Pattern Languages
Following Angluin [1] we define patterns and pattern languages as follows. Let
A = {0, 1, . . .} be any finite alphabet containing at least two elements. Let X ={xi i ∈ N} be an infinite set of variables such that A ∩ X = ∅ . Patterns are nonempty strings over A ∪ X , e.g., 01, 0x0 111, 1x0 x0 0x1 x2 x0 are patterns. The lengthof a string s ∈ A∗ and of a pattern π is denoted by |s| and |π| , respectively. A
pattern π is in canonical form provided that if k is the number of different variablesin π then the variables occurring in π are precisely x0 , . . . , xk−1 . Moreover, for every
j with 0 ≤ j < k − 1 , the leftmost occurrence of xj in π is left to the leftmost
occurrence of xj+1 . The examples given above are patterns in canonical form. In thesequel we assume, without loss of generality, that all patterns are in canonical form.
By Pat we denote the set of all patterns in canonical form.
If k is the number of different variables in π then we refer to π as to a k -variable
pattern. By Pat k we denote the set of all k -variable patterns. Furthermore, let
π ∈ Pat k , and let u0 , . . . , uk−1 ∈ A+ ; then we denote by π[x0 /u0 , . . . , xk−1 /uk−1 ] thestring w ∈ A+ obtained by substituting uj for each occurrence of xj , j = 0, . . . , k −1 , in the pattern π . For example, let π = 0x0 1x1 x0 . Then π[x0 /10, x1 /01] =01010110 . The tuple (u0 , . . . , uk−1 ) is called a substitution. Furthermore, if |u0 | =· · · = |uk−1 | = 1 , then we refer to (u0 , . . . , uk−1 ) as to a shortest substitution. Let
π ∈ Pat k ; we define the language generated by pattern π byL(π) = {π[x0 /u0 , . . . , xk−1 /uk−1 ] u0 , . . . , uk−1 ∈ A+ } .

From Learning in the Limit to Stochastic Finite Learning

9

By PAT k we denote the set of all k -variable pattern languages. Finally, PAT =Sk∈N PAT k denotes the set of all pattern languages over A .
Furthermore, we let Q range over finite sets of patterns and define L(Q) =π∈Q L(π) , i.e., the union of all pattern languages generated by patterns from Q .
Moreover, we use Pat(k) and PAT (k) to denote the family of all unions of at
most k canonical patterns and the family of all unions of at most k pattern languages, respectively. That is, Pat(k) = {Q Q ⊆ Pat, |Q| ≤ k} and PAT (k) ={L(Q) Q ∈ Pat(k)} . Finally, let L ⊆ A+ be a language, and let k ∈ N+ ; we define
Club(L, k) = {Q |Q| ≤ k, L ⊆ L(Q), (∀Q0 )[Q0 ⊂ Q ⇒ L 6⊆ L(Q0 )]} . Club stands
for consistent least upper bounds.

S

The pattern languages and variations thereof have been intensively investigated(cf., e.g., Salomaa [37, 38], and Shinohara and Arikawa [43] for an overview). Nix [29]as well as Shinohara and Arikawa [43] outlined interesting applications of patterninference algorithms. For example, pattern language learning algorithms have beensuccessfully applied for solving problems in molecular biology (cf., e.g., Shimozono etal. [39], Shinohara and Arikawa [43]).
As it turned out, pattern languages and finite unions of pattern languages aresubclasses of Smullyan’s [45] elementary formal systems (abbr. EFS). Arikawa et al. [5]have shown that EFS can also be treated as a logic programming language over strings.
Recently, the techniques for learning finite unions of pattern languages have been
extended to show the learnability of various subclasses of EFS (cf. Shinohara [42]).
The investigations of the learnability of subclasses of EFSs are interesting because
they yield corresponding results about the learnability of subclasses of logic programs.
Hence, these results are also of relevance for Inductive Logic Programming (ILP)[28, 23, 8, 24]. Miyano et al. [26] intensively studied the polynomial-time learnabilityof EFSs.
Therefore, we may consider the learnability of pattern languages and of unions
thereof as a nice test bed for seeing what kind of results one may obtain by considering
the corresponding learning problems within the setting of learning in the limit.

3. Results Concerning Patterns
Within this section we ask whether or not the pattern languages and finite unions
thereof can be learned efficiently. The principal learnability of the pattern languages
from text with respect to the hypothesis space Pat has been established by Angluin [1]. However, her algorithm is based on computing descriptive patterns for thedata seen so far. Here a pattern π is said to be descriptive (for the set S of strings
contained in the input provided so far) if π can generate all strings contained in S
and no other pattern with this property generates a proper subset of the language
generated by π . Since no efficient algorithm is known for computing descriptive patterns, and finding a descriptive pattern of maximum length is N P -hard, its update
time is practically intractable.

10

Thomas Zeugmann

There are also serious difficulties when trying to learn the pattern languages within
the PAC model introduced by Valiant [46]. In the original model, the sample complexity depends exclusively on the VC dimension of the target concept class and theerror and confidence parameters ε and δ , respectively. Recently, Mitchell et al. [25]have shown that even the class of all one-variable pattern languages has infinite VC
dimension. Consequently, even this special subclass of PAT is not uniformly PAC
learnable. Moreover, Schapire [40] has shown that pattern languages are not PAC
learnable in the generalized model provided P /poly 6= N P /poly with respect toevery hypothesis space for PAT that is uniformly polynomially evaluable. Though
this result highlights the difficulty of PAC learning PAT it has no clear application
to the setting considered in this paper, since we aim to learn PAT with respect tothe hypothesis space Pat . Since the membership problem for this hypothesis spaceis N P -complete, it is not polynomially evaluable (cf. [1]).
In contrast, Kearns and Pitt [18] have established a PAC learning algorithm for theclass of all k -variable pattern languages. Positive examples are generated with respect
to arbitrary product distributions while negative examples are allowed to be generated
with respect to any distribution. In their algorithm the length of substitution strings
is required to be polynomially related to the length of the target pattern. Finally, they
use as hypothesis space all unions of polynomially many patterns that have k or fewer
variables2 . The overall learning time of their PAC learning algorithm is polynomial in
the length of the target pattern, the bound for the maximum length of substitution
strings, 1/ε , 1/δ , and |A| . The constant in the running time achieved depends
doubly exponential on k , and thus, their algorithm becomes rapidly impractical whenk increases.
Finally, Lange and Wiehagen [19] have proposed an inconsistent but iterative andconservative algorithm that learns PAT with respect to Pat . We shall study thisalgorithm below in some more detail.
But before doing it, we aim to figure out under which circumstances iterative
learning of PAT is possible at all. A first answer is given by the following theorems
from Case et al. [9]. Note that Pat is a non-redundant hypothesis space for PAT .
Theorem 1 (Case et al. [9]). Let C be any concept class, and let H = (hj )j∈N
be any non-redundant hypothesis space for C . Then, every IIM M that ItLimTxt H learns C is conservative.
Proof. Recall that we use M∗ (σ) to denote M|σ|−1 (σ) for any finite sequence σ =x0 , . . . , xn of elements from X (cf. Definition 2).
Suppose the converse, i.e., there are a concept c ∈ C , a text t = (xj )j∈N ∈ text(c) ,and a y ∈ N such that, for j = M∗ (ty ) and k = M∗ (ty+1 ) = M (j, xy+1 ) , both
j 6= k and t+y+1 ⊆ hj are satisfied. The latter implies xy+1 ∈ hj , and thus we may
2More precisely, the number of allowed unions is at most poly(|π|, s, 1/ε, 1/δ, |A|) , where π is
the target pattern, s the bound on the length on substitution strings, ε and δ are the usual error
and confidence parameter, respectively, and A is the alphabet of constants over which the patterns
are defined.

From Learning in the Limit to Stochastic Finite Learning

11

consider the following text t̃ ∈ text(hj ) . Let t̂ = (x̂j )j∈N be any text for hj andlet t̃ = x̂0 , xy+1 , x̂1 , xy+1 , x̂2 , . . . . Since M has to learn hj from t̃ there must be az ∈ N such that M∗ (t̃z+r ) = j for all r ≥ 0 . But M∗ (t̃2z+1 ) = M (j, xy+1 ) = k , acontradiction.
Next, we point to another peculiarity of PAT , i.e., it meets the superset condition
defined as follows. Let C be any indexable class. C meets the superset condition if,
for all c, c0 ∈ C , there is some ĉ ∈ C being a superset of both c and c0 .
Theorem 2. (Case et al. [9]). Let C be any indexable class meeting the superset
condition, and let H = (hj )j∈N be any non-redundant hypothesis space for C . Then,every consistent IIM M that ItLimTxt H -learns C may be used to decide the inclusion
problem for H .
Proof. Let X be the underlying learning domain, and let (wj )j∈N be an effective
enumeration of all elements in X . Then, for every i ∈ N , ti = (xij )j∈N is the following
computable text for hi . Let z be the least index such that wz ∈ hi . Recall that, bydefinition, hi 6= ∅ , since H is an indexed family, and thus wz must exist. Then, forall j ∈ N , we set xij = wj , if wj ∈ hi , and xij = wz , otherwise.
We claim that the following algorithm Inc decides, for all i, k ∈ N , whether or
not hi ⊆ hk .
Algorithm Inc: “On input i, k ∈ N do the following:
Determine the least y ∈ N with i = M∗ (tiy ) . Test whether or not ti,+y ⊆ hk .
In case it is, output ‘Yes,’ and stop. Otherwise, output ‘No,’ and stop.”
Clearly, since H is an indexed family and ti is a computable text, Inc is an algorithm.
Moreover, M learns hi on every text for it, and H is a non-redundant hypothesis
space. Hence, M has to converge on text ti to i , and therefore Inc has to terminate.
It remains to verify the correctness of Inc . Let i, k ∈ N .
Clearly, if Inc outputs ‘No,’ a string s ∈ hi \ hk has been found, and hi 6⊆ hk
follows.
Next, consider the case that Inc outputs ‘Yes.’ Suppose to the contrary thathi 6⊆ hk . Then, there is some s ∈ hi \ hk . Now, consider M when fed the textt = tiy  tk . Since ti,+
⊆ hk , t is a text for hk . Since M learns hk , there isysome r ∈ N such that k = M∗ (tiy  tkr ) . By assumption, there are some ĉ ∈ C withhi ∪hk ⊆ ĉ , and some text t̂ for ĉ having the initial segment tiy stkr . By Theorem 1,
M is conservative. Since s ∈ hi and i = M∗ (t̂y ) , we obtain M∗ (t̂y+1 ) = M (i, s) = i .
ikConsequently, M∗ (tiy  s  tkr ) = M∗ (tiy  tkr ) . Finally, since s ∈ t̂+
y+r+2 , k = M∗ (ty  tr ) ,and s ∈/ hk , M fails to consistently learn ĉ from text t̂ , a contradiction. This proves
the theorem.

12

Thomas Zeugmann

Taking into account that the inclusion problem for Pat is undecidable (cf. Jiang
et al. [17]) and that PAT meets the superset condition, since L(x0 ) = A+ , byTheorem 2, we immediately arrive at the following corollary.
Corollary 3 (Case et al. [9]). If an IIM M ItLimTxt Pat -learns PAT thenM is inconsistent.
As a matter of fact, the latter corollary generalizes to all non-redundant hypothesis
spaces for PAT . All the ingredients to prove this can be found in Zeugmann etal. [53]. Consequently, if one wishes to learn the pattern languages or unions ofpattern languages iteratively, then either redundant hypothesis spaces or inconsistentlearners cannot be avoided.
As for unions, the first result goes back to Shinohara [41] who proved the classof all unions of at most two pattern languages to be in LimTxt Pat(2) . Wright [50]extended this result to PAT (k) ∈ LimTxt Pat(k) for all k ≥ 1 . Moreover, Theorem
4.2 in Shinohara and Arimura’s [44] together with a lemma from Blum and Blum [6]S
shows that k∈N PAT (k) is not LimTxt H -learnable for every hypothesis space H .
The iterative learnability of PAT (k) has been established by Case et al. [9]. Ourlearner is also consistent. Thus, the hypothesis space used had to be designed to be
redundant. We only sketch the proof here.
Theorem 4.
(1) Club(L, k) is finite for all L ⊆ A+ and all k ∈ N+ ,(2) If L ∈ PAT (k) , then Club(L, k) is non-empty and contains a set Q , such that
L(Q) = L .
Proof. Part (2) is obvious. Part (1) is easy for finite L . For infinite L , it follows
from the lemma below.
Lemma 1. Let k ∈ N+ , let L ⊆ A+ be any language, and suppose t = (sj )j∈N ∈text(L). Then,+(1) Club(t+0 , k) can be obtained effectively from s0 , and Club(tn+1 , k) is effectively
obtainable from Club(t+n , k) and sn+1(* note the iterative nature *).
+(2) The sequence Club(t+0 , k), Club(t1 , k), . . . converges to Club(L, k).

Putting it all together, one directly gets the following theorem.
Theorem 5. For all k ≥ 1 , PAT (k) ∈ ItLimTxt .
Proof. Let can(·) , be some computable bijection from finite classes of finite setsof patterns onto N . Let pad be a 1–1 padding function such that, for all x, y ∈ N ,Wpad(x,y) = Wx . For a finite class S of sets of patterns, let g(S) denote a grammarTobtained, effectively from S , for Q∈S L(Q) .

From Learning in the Limit to Stochastic Finite Learning

13

Let L ∈ PAT (k) , and let t = (sj )j∈N ∈ text(L) . The desired IIM M is defined asfollows. We set+
M0 (t) = M (s0 ) = pad(g(Club(t+0 , k)), can(Club(t0 , k))) , and for all n > 0 ,Mn+1 (t) = M (Mn (t), sn+1 )+= pad(g(Club(t+n+1 , k)), can(Club(tn+1 , k))) .

Using Lemma 1 it is easy to verify that Mn+1 (t) = M (Mn (t), sn+1 ) can be obtained
effectively from Mn (t) and sn+1 . Therefore, M ItLimTxt -identifies PAT (k) .
So far, the general theory provided substantial insight into the iterative learnabilityof the pattern languages. But still, we do not know anything about the number ofexamples needed until successful learning and the total amount of time to processthem. Therefore, we address this problem in the following subsection.
3.1. Stochastic Finite Learning
As we have already mentioned, it does not make much sense to study the worstcase behavior of learning algorithms with respect to their total learning time. The
reason for this phenomenon should be clear, since an arbitrary text may provide
the information needed for learning very late. Therefore, in the following we always
assume a class D of admissible probability distributions over the relevant learning
domain. Ideally, this class should be parameterized. Then, the data fed to learnerare generated randomly with respect to one of the probability distributions fromthe class D of underlying probability distributions. Furthermore, we introduce a
random variable CONV for the stage of convergence. Note that CONV can be alsointerpreted as the total number of examples read by the IIM M until convergence.
We therefore also refer to CONV as to the sample complexity. The first major step
to be performed consists now in determining the expectation E[CONV ] . Clearly,
E[CONV ] should be finite for all concepts c ∈ C and all distributions D ∈ D .
Second, one has to deal with tail bounds for E[CONV ] . The easiest way to perform
this step is to use Markov’s inequality, i.e., we always know that
Pr(CONV ≥ t · E[CONV ]) ≤1
for all t ∈ N+ .
t

However, quite often one can obtain much better tail bounds. If the underlying
learner is known to be conservative and rearrangement-independent we always get
exponentially shrinking tail bounds. A learner is said to be rearrangement-independent
if its output depends exclusively on the range and length of its input (cf. [21] and thereferences therein). These tail bounds are established by the following theorem.
Theorem 6 (Rossmanith and Zeugmann [36]). Let CONV be the sample
complexity of a conservative and rearrangement-independent learning algorithm. Then
Pr(CONV ≥ 2t · E[CONV ]) ≤ 2−t for all t ∈ N .

14Thomas Zeugmann

Proof. First, recall the definition of median. If X is a random variable then µX
is a median of X iff
Pr(X ≥ µX) ≥ 1/2 and Pr(X ≤ µX) ≥ 1/2.
A nonempty set of medians exists for each random variable and consists either of asingle real number or of a closed real interval. We will denote the smallest median of
X by µX , since this choice gives the best upper bounds.
Now, we can establish the following claim.
Claim 1. Let X be the sample complexity of a conservative and rearrangementindependent learning algorithm. Then Pr(X ≥ t · µX) ≤ 2−t for all t ∈ N .
We divide the text s0 , s1 , . . . into blocks of length µX . The probability that thealgorithm converges after reading any of the blocks is then at least 1/2 . Since thealgorithm is rearrangement-independent the order of the blocks does not matter andsince the algorithm is conservative it does not change its hypothesis after computing
once the right hypothesis. This proves Claim 1.
Claim 2. µX ≤ 2E[X] for every positive random variable X .
Claim 2 is a direct consequence of the Markov inequality and the definition ofmedian.
Putting Claims 1 and 2 together directly yields the theorem.
Theorem 6 puts the importance of rearrangement-independent and conservative
learners into the right perspective. As long as the learnability of indexed families
is concerned, these results have a wide range of potential applications, since every conservative learner can be transformed into a learner that is both conservativeand rearrangement-independent provided the hypothesis space is appropriately chosen(cf. Lange and Zeugmann [21]).
Furthermore, since the distribution of CONV decreases geometrically for all conservative and rearrangement-independent learning algorithms, all higher moments of
CONV exist in this case, too. Thus, instead of applying Theorem 6 directly, one
can hope for further improvements by applying even sharper tail bounds using, forexample, Chebyshev’s inequality.
Additionally, the learner takes a confidence parameter δ as input. But in contrast
to learning in the limit, the learner itself decides how many examples it wants to read.
Then it computes a hypothesis, outputs it and stops. The hypothesis output is correct
for the target with probability at least 1 − δ .
The explanation given so far explains how it works, but not why it does. Intuitively, the stochastic finite learner simulates the limit learner until an upper boundfor twice the expected total number of examples needed until convergence has been
met. Assuming this to be true, by Markov’s inequality the limit learner has now

From Learning in the Limit to Stochastic Finite Learning

15

converged with probability 1/2 . All what is left, is to decrease the probability of
failure. This is done by using the tail bounds for CONV . Applying Theorem 6, one
easily sees that increasing the sample complexity by a factor of O(log 1δ ) results ina probability of 1 − δ for having reached the stage of convergence. If Theorem 6 is
not applicable, one can still use Markov’s inequality but then the sample complexity
needed will increase by a factor of 1/δ .
It remains to explain how the stochastic finite learner can calculate the upperbound for E[CONV ] . This is precisely the point where we need the parameterizationof the class D of underlying probability distributions. Since in general, it is notknown which distribution from D has been chosen, one has to assume a bit of priorknowledge or domain knowledge provided by suitable upper and/or lower bounds forthe parameters involved. A more serious difficulty is to incorporate the unknown
target concept into this estimate. This step depends on the concrete learning problem
on hand, and requires some extra effort. We shall exemplify it below.
Now we are ready to formally define stochastic finite learning.
Definition 3 ([33, 34, 36]). Let D be a set of probability distributions on thelearning domain, C a concept class, H a hypothesis space for C , and δ ∈ (0, 1) .
(C, D) is said to be stochastically finitely learnable with δ -confidence with respect to
H iff there is an IIM M that for every c ∈ C and every D ∈ D performs as follows.
Given any random data sequence θ for c generated according to D , M stops after
having seen a finite number of examples and outputs a single hypothesis h ∈ H .
With probability at least 1 − δ (with respect to distribution D ) h has to be correct,
that is c = h .
If stochastic finite learning can be achieved with δ -confidence for every δ > 0 thenwe say that (C, D) can be learned stochastically finite with high confidence.
Note that there are subtle differences between our model and PAC learning. By
its definition, stochastic finite learning is not completely distribution independent.
A bit of additional knowledge concerning the underlying probability distributions isrequired. Thus, from that perspective, stochastic finite learning is weaker than the
PAC-model. On the other hand, we do not measure the quality of the hypothesis withrespect to the underlying probability distribution. Instead, we require the hypothesis
computed to be exactly correct with high probability. Note that exact identification
with high confidence has been considered within the PAC paradigm, too (cf., e.g.,Goldman et al. [13]). Conversely, we also can easily relax the requirement to learn
probably exactly correct but whenever possible we shall not do it.
Furthermore, in the uniform PAC model as introduced in Valiant [46] the sample
complexity depends exclusively on the VC dimension of the target concept class andthe error and confidence parameters ε and δ , respectively. This model has been
generalized by allowing the sample size to depend on the concept complexity, too(cf., e.g., Blumer et al. [7] and Haussler et al. [15]). Provided no upper bound for theconcept complexity of the target concept is given, such PAC learners decide themselves

16

Thomas Zeugmann

how many examples they wish to read (cf. [15]). This feature is also adopted to our
setting of stochastic finite learning. However, all variants of PAC learning we areaware of require that all hypotheses from the relevant hypothesis space are uniformly
polynomially evaluable. Though this requirement may be necessary in some cases toachieve (efficient) stochastic finite learning, it is not necessary in general as we shallsee below.
Next, let us exemplify our model by looking at the concept class of all patternlanguages. The results presented below have been obtained by Zeugmann [51] andRossmanith and Zeugmann [36]. Our stochastic finite learner uses Lange and Wiehagen’s [19] pattern language learner as a main ingredient. We consider here learningfrom positive data only.
Recall that every string of a particular pattern language is generated by at least one
substitution. Therefore, it is convenient to consider probability distributions over theset of all possible substitutions. That is, if π ∈ Pat k , then it suffices to consider any+
probability distribution D over A· · × A+} . For (u0 , . . . , uk−1 ) ∈ A+ × · · · × A+
| × ·{zk−times

we denote by D(u0 , . . . , uk−1 ) the probability that variable x0 is substituted by u0 ,variable x1 is substituted by u1 , . . . , and variable xk−1 is substituted by uk−1 .
In particular, we mainly consider a special class of distributions, i.e., product distributions. Let k ∈ N+ , then the class of all product distributions for Pat k is defined asfollows. For each variable xj , 0 ≤ j ≤ k−1 , we assume an arbitrary probability distribution Dj over A+ on substitution strings. Then we call D = D0 × · · · × Dk−1 prodQ
uct distribution over A+ × · · · × A+ , i.e., D(u0 , . . . , uk−1 ) = k−1
j=0 Dj (uj ) . Moreover,
we call a product distribution regular if D0 = · · · = Dk−1 . Throughout this paper,
we restrict ourselves to deal with regular distributions. We therefore use d to denoteQthe distribution over A+ on substitution strings, i.e, D(u0 , . . . , uk−1 ) = k−1
j=0 d(uj ) .
We call a regular distribution admissible if d(a) > 0 for at least two different elements a ∈ A . As a special case of an admissible distribution we consider the uniform
distribution over A+ , i.e., d(u) = 1/(2 · |A|)` for all strings u ∈ A+ with |u| = ` .
Note that here only strings of equal length have the same probability and not eachelementary event.
We will express all estimates with the help of the following parameters: E[Λ] , αand β , where Λ is a random variable for the length of the examples drawn. α and β
are defined below. To get concrete bounds for a concrete implementation one has toobtain c from the algorithm and has to compute E[Λ] , α , and β from the admissible
probability distribution D . Let u0 , . . . , uk−1 be independent random variables with
distribution d for substitution strings. Whenever the index i of ui does not matter,
we simply write u or u0 .
The two parameters α and β are now defined via d . First, α is simply theprobability that u has length 1, i.e.,X
α = Pr(|u| = 1) =
d(a).
a∈A

From Learning in the Limit to Stochastic Finite Learning

17

Second, β is the conditional probability that two random strings that get substituted
into π are identical under the condition that both have length 1 , i.e.,
!2
. X
X
0
0
2
β = Pr (u = u | |u| = |u | = 1) =d(a)d(a) .
a∈A

a∈A

Note that we have omitted the assumption of a text to exhaust the target language.
Instead, we only demand the data sequence fed to the learner to contain “enough”
information to recognize the target pattern. The meaning of “enough” is mainly
expressed by the parameter α .
The model of computation as well as the representation of patterns we assume isthe same as in Angluin [1]. In particular, we assume a random access machine that
performs a reasonable menu of operations each in unit time on registers of lengthO(log n) bits, where n is the input length.
Lange and Wiehagen’s [19] algorithm (abbr. LWA) works as follows. Let hn be
the hypothesis computed after reading s0 , . . . , sn , i.e., hn = M (s0 , . . . , sn ) . Thenh0 = s0 and for all n ≥ 1 :
if |hn−1 | < |sn | hn−1 ,sn ,if |hn−1 | > |sn |hn =hn−1 ∪ sn , if |hn−1 | = |sn |The algorithm computes the new hypothesis only from the latest example and theold hypothesis. If the latest example is longer than the old hypothesis, the example
is ignored, i.e., the hypothesis does not change. If the latest example is shorter thanthe old hypothesis, the old hypothesis is ignored and the new example becomes the
new hypothesis. If, however, |hn−1 | = |sn | the new hypothesis is the union of hn−1
and sn . In order to explain the union, we need the following notation. Let π ∈ Pat ,1 ≤ i ≤ |π| ; we use π(i) to denote the i -th symbol in π . Now, the union % = π ∪ sof a canonical pattern π and a string s of the same length is defined asπ(i), if π(i) = s(i)xj , if π(i) 6= s(i) & ∃k < i : [%(k) = xj , s(k) = s(i),%(i) =
π(k) = π(i)]xm , otherwise, where m = #var(%(1) . . . %(i − 1))
where %(0) = λ for notational convenience. Note that the resulting pattern isagain canonical.
If the target pattern does not contain any variable then the LWA converges after
having read the first example. Hence, this case is trivial and we therefore assume
in the following always k ≥ 1 , i.e., the target pattern has to contain at least one
variable.

18

Thomas Zeugmann

Figure 1 displays the union operation for π = 01x0 x1 21x0 x2 01x0 x1 and s =120021010212 . Since the letters in the first column are different and there is noprevious column, %(1) = x0 . The letters in the second column are different, andthe second column is not equal to the first column, so %(2) = x1 . Next, π(3) = x0
and π(4) = x1 , and thus % must also contain different variables at positions 3 and
4 . Consequently, these variables get renamed, i.e., %(3) = x2 and %(4) = x3 . The
letters in the 5th and 6th column are identical, hence %(5) = 2 and %(6) = 1 (cf.
the first case in the definition of the union operation). In the 7th column, we havex0 and 0 and this column is equal to the third column. Therefore, the second casein the definition of the union operation applies and %(7) = x2 . Now, %(8) = x4
and %(9) = 0 are obvious. The 10th column is identical to the second one, thus%(10) = x1 . Next, we have x0 and 1 while both the third and 7th column containx0 and 0 . Therefore, a new variable has to be introduced and %(11) = x5 (cf. thethird case in the definition of the union operation). Analogously, the x1 in the 12thcolumn has to be distinguished from the x1 in 4th column resulting in %(12) = x6 .

π
s
%=π∪s

0
1
x0

1
2
x1

x0
0
x2

x1
0
x3

2 1 x02 1 0
2 1 x2

x2
1
x4

0 1
0 2
0 x1

x0
1
x5

x1
2
x6

Figure 1
Our next theorem analyzes the complexity of the union operation.
Theorem 7 (Rossmanith and Zeugmann [36]). The union operation can be computed in linear time.
Furthermore, the following bound for the stage of convergence for every target
pattern from Pat k can be shown.
Theorem 8(Rossmanith and Zeugmann [36]).
1
E[CONV ] = O· log1/β (k) for all k ≥ 2 .
αkHence, by expected total learning time can be estimated by
 Theorem 7, the1
E[Λ] log1/β (k) for all k ≥ 2 .
E[T T ] = O
αk
For a better understanding of the bound obtained we evaluate it for the uniform
distribution and compare it to the minimum number of examples needed for learninga pattern language via the LWA.
Theorem 9 (Rossmanith and Zeugmann [36]). To learn a pattern π ∈ Pat k ,k ≥ 2 , from texts randomly generated with respect to the uniform distribution, theLWA has the expected total learning time E[T T ] = O 2k |π| log|A| (k) .
Theorem 10 (Zeugmann [51]). To learn a pattern π ∈ Pat k the LWA needs
exactly blog|A| (|A| + k − 1)c + 1 examples in the best case.

From Learning in the Limit to Stochastic Finite Learning

19

The main difference between the two bounds just given is the factor 2k which
precisely reflects the time the LWA has to wait until it has seen the first shortest stringfrom the target pattern language. Moreover, in the best-case the LWA is processing
shortest examples only. Thus, we introduce MC to denote the number of minimum
length examples read until convergence. Then, one can show that
E[MC ] ≤2 ln(k) + 3+2 .
ln(1/β)Note that Theorem 8 is shown by using the bound for E[MC ] just given. More
precisely, we have E[CONV ] = 1/αk E[MC ] . Now, we are ready to transform the
LWA into a stochastic finite learner.
Theorem 11 (Rossmanith and Zeugmann [36]). Let α∗ , β∗ ∈ (0, 1) . Assume D
to be a class of admissible probability distributions over A+ such that α ≥ α∗ , β ≤ β∗
and E[Λ] is finite for all distributions D ∈ D . Then (PAT , D) is stochasticallyfinitely learnable with high confidence from text.
Proof. Let D ∈ D , and let δ ∈ (0, 1) be arbitrarily fixed. Furthermore, lett = s0 , s1 , s2 , . . . be any randomly generated text with respect to D for the target
pattern language. The wanted learner M uses the LWA as a subroutine. Additionally,it has a counter for memorizing the number of examples already seen. Now, we
exploit the fact that the LWA produces a sequence (τn )n∈N of hypotheses such that|τn | ≥ |τn+1 | for all n ∈ N .
The learner runs the LWA until for the first time C many examples have beenprocessed, where |τ | 
2 ln(|τ |) + 3
1
·
C=
+2
(A)
α∗
ln(1/β∗ )and τ is the actual output made by the LWA.
Finally, in order to achieve the desired confidence, the learner sets γ = dlog 1δ e
and runs the LWA for a total of 2 · γ · C examples. This is the reason we need thecounter for the number of examples processed. Now, it outputs the last hypothesis τ
produced by the LWA, and stops thereafter.
Clearly, the learner described above is finite. Let L be the target language andlet π ∈ Pat k be the unique pattern such that L = L(π) . It remains to argue that
L(π) = L(τ ) with probability at least 1 − δ .
First, the bound in (A) is an upper bound for the expected number of examples
needed for convergence by the LWA that has been established in Theorem 8 (via thereformulation using E[MC ] given above). On the one hand, this follows from ourassumptions about the allowed α and β as well as from the fact that |τ | ≥ |π| forevery hypothesis output. On the other hand, the learner does not know k , but theestimate #var (π) ≤ |π| is sufficient. Note that we have to use in (A) the bound20

Thomas Zeugmann

for E[MC ] given above, since the target pattern may contain zero or one different
variables.
Therefore, after having processed C many examples the LWA has already converged on average. The desired confidence is then an immediate consequence of Theorem 6.
The latter theorem allows a nice corollary which we state next. Making the same
assumption as done by Kearns and Pitt [18], i.e., assuming the additional prior knowledge that the target pattern belongs to Pat k , the complexity of the stochastic finite
learner given above can be considerably improved. The resulting learning time is linear
in the expected string length, and the constant depending on k grows only exponentially in k in contrast to the doubly exponentially growing constant in Kearns andPitt’s [18] algorithm. Moreover, in contrast to their learner, our algorithm learns frompositive data only, and outputs a hypothesis that is correct for the target languagewith high probability.
Again, for the sake of presentation we shall assume k ≥ 2 . Moreover, if the priorknowledge k = 1 is available, then there is also a much better stochastic finite learnerfor PAT 1 (cf. [34]).
Corollary 12. Let α∗ , β∗ ∈ (0, 1) . Assume D to be a class of admissible
probability distributions over A+ such that α ≥ α∗ , β ≤ β∗ and E[Λ] is finite forall distributions D ∈ D . Furthermore, let k ≥ 2 be arbitrarily fixed. Then there
exists a learner M such that
(1) M learns (PAT k , D) stochastically finitely with high confidence from text, and(2) The running time of M is O (1/α∗k )E[Λ] log1/β∗ (k) log2 (1/δ) .
(* Note that 1/α∗k and log1/β∗ (k) now are constants. *)This finishes our exposition concerning the pattern languages and unions thereof.
In the following section we show our ideas to be beneficial for a class known to be
PAC learnable by looking at the class of all concepts describable by a monomial.

4. Learning Conjunctive Concepts
In this section we exemplify the general approach outlined above by using the classof all concepts describable by a monomial. For all details omitted the reader is referred
to Reischuk and Zeugmann [33].
For defining the classes of concepts we shall deal with in this section, let Ln ={x1 , x̄1 , x2 , x̄2 . . . , xn , x̄n } be a set of literals. xi is a positive literal and x̄i a negative
one. A conjunction of literals defines a monomial. For a monomial m let #(m)denote its length, that is the number of literals in it.
A monomial m describes a subset L(m) of Xn , in other words a concept, inthe obvious way: the concept contains exactly those binary vectors for which theFrom Learning in the Limit to Stochastic Finite Learning

21

monomial evaluates to 1, that is L(m) := {b ∈ Xn m(b) = 1} . The collectionof objects we are going to learn is the set Cn of all concepts that are describableby monomials over Xn . There are two trivial concepts, the empty subset and Xn
itself. Xn , which will also be called “TRUE”, can be represented by the empty
monomial. The concept “FALSE” has several descriptions. To avoid ambiguity, wealways represent “FALSE” by the monomial x1 x̄1 . . . xn x̄n . Furthermore, we often
identify the set of all monomials over Ln and the concept class Cn . Note that|Cn | = 3n + 1 .
For the concept class Cn we choose as hypothesis space the set of all monomials
over Ln and denote this hypothesis space by Hn . We shall distinguish learningfrom positive data only and learning from both positive and negative data. Notethat when considering learning from positive data only, one cannot decide whether
or not the learner has already converged. When learning from positive and negative
data is considered, the stage of convergence is decidable, but one would have to readthe data sequence until all Boolean vectors did appear. Thus, for any interesting n ,decidability is practically infeasible.
The learner used is essentially Haussler’s [14] Wholist algorithm. We present ithere as an iterative learner. The iterative learner is defined in stages, where Stage `conceptually describes M` .
Algorithm IML: “Let c ∈ Cn , let i = (b0 , m(b0 )), (b1 , m(b1 )), . . . be any informant for c . Go to Stage 0.
Stage 0. IML receives as input (b0 , m(b0 )) .
Initialize hini = x1 x̄1 . . . xn x̄n .
If m(b0 ) = 0 then hini remains unchanged; else
for j := 1 to n do
if bj0 = 1 then delete x̄j in hini else delete xj in hini .
Denote the result by h0 , output h0 and go to Stage 1.
Stage ` , ` ≥ 1 . IML(b` , m(b` )) of i .

receives as input h`−1 and the (` + 1) th element

If m(b` ) = 0 then set h` = h`−1 ; else
for j := 1 to n do
if bj` = 1 then delete x̄j in h`−1 else delete xj in h`−1 .
Denote the result by h` , output h` and go to Stage ` + 1 .
By convention, if all literals have been removed, then h` = ∅ , and h` (b) = 1
for all b ∈ Xn .
end.”

22

Thomas Zeugmann

The following example illustrates Algorithm IML . Let n = 7 , and let m =x1 x̄2 x4 x7 be the target monomial. Suppose the input sequence to start as follows:
h1001111, 1, 0110110, 0, 1011101, 1, 1011001, 1, . . .i . In Stage 0 the loop is executedand all literals that do not evaluate to 1 are removed from hini . Thus, the hypothesis
computed is h0 = x1 x̄2 x̄3 x4 x5 x6 x7 . Next, h0 and 0110110, 0 are read and since
the label is 0, the hypothesis output is again x1 x̄2 x̄3 x4 x5 x6 x7 , i.e., h1 = h0 . In
Stage 2, IML receives h1 and 1011101, 1 and executes the loop resulting in h2 =x1 x̄2 x4 x5 x7 . Now, IML reads h2 and 1011001, 1 and executes the loop in Stage
3. The result is h3 = x1 x̄2 x4 x7 which equals the target monomial. Consequently,
Algorithm IML has reached the stage of convergence.
Now, we can directly state the following theorem.
Theorem 13. Algorithm IML ItLimInf Hn -learns Cn .
Moreover, Algorithm IML can be easily adapted to learn from positive data
only. We have just to omit the tests whether or not m(bn ) = 0 . We call the resulting
algorithm IMLP . Now, the following corollary is obvious.
Corollary 14. Algorithm IMLP ItLimTxt Hn -learns Cn .
If the target monomial is the concept “FALSE”, then Algorithms IML and
IMLP immediately converge. Thus, we call “FALSE” the minimal concept. If thetarget concept contains precisely n literals, then one positive example suffices. This
positive example is unique. Thus, for these two cases everything is clear and therefore,
we call these concepts trivial. Also, the set of probability distributions D on the setof positive examples for these trivial c are trivial, too.
To study the general case, let us call the literals appearing in a non-minimal monomial m relevant. All the other literals in Ln will be called irrelevant for m . Thereare 2n − #(m) irrelevant literals. Recall that #(m) denotes the number of literals
in monomial m .
We call bit i relevant for monomial m if xi or x̄i is relevant for m and use
k := k(m) = n − #(m) to denote the number of irrelevant bits.
4.1. Learning Monomials from Positive DataFirst, we consider learning from positive data. To avoid the trivial cases, we let
V
c = L(m) ∈ Cn be a concept with monomial m = #(m)j=1 `ij such that k = k(m) =kn − #(m) > 0 . There are 2 positive examples for c . For the sake of presentation,
we assume these examples to be binomially distributed. That is, in a random positive
example all entries corresponding to irrelevant bits are selected independently of eachother. With some probability p this will be a 1 , and with probability q a 0 , whereq = 1 − p . We shall consider only nontrivial distributions where 0 < p < 1 . Notethat otherwise the data sequence does not contain all positive examples. We aim tocompute the expected number of examples taken by IMLP until convergence. AgainFrom Learning in the Limit to Stochastic Finite Learning23

we use CONV to denote a random variable counting the number of examples readtill convergence.
The first example received forces IMLP to delete precisely n of the 2n literals
in hini . Thus, this example always plays a special role. Note that the resulting
hypothesis h0 depends on b0 , but the number k of literals that remain to be deleted
from h0 until convergence is independent of b0 . Using tail bound techniques, we canshow the following theorem.
Theorem 15 (Reischuk and Zeugmann [33]). Let c = L(m) be a non-minimal
concept in Cn , and let the positive examples for c be binomially distributed withp1
, p1 } and τ := max{ 1−p, 1−p} . Then the expectedparameter p . Define ψ := min{ 1−ppnumber of positive examples needed by algorithm IMLP until convergence can bebounded by
E[CONV ] ≤ dlogψ k(m)e + τ + 2 .
Proof. Let k = k(m) and let q = 1−p . The first positive example contains ν times
a 1 and k−ν times a 0 with probability νk pν q k−ν at the positions not corresponding
to a literal in the target monomial m . Now, assuming any such vector, we easily
see that h0 contains ν positive irrelevant literals and k − ν negative irrelevant
literals. Therefore, in order to achieve convergence, the Algorithm IMLP now needs
positive examples that contain at least one 0 for each positive irrelevant literal andat least one 1 for each negative irrelevant literal. Thus, the probability that atleast one irrelevant literal survives µ subsequent positive examples is bounded byνpµ + (k − ν)q µ . Therefore,k  Xk ν k−νPr(CONV − 1 > µ) ≤p q
· (νpµ + (k − ν)q µ ) .
νν=0
Next, we derive a closed formula for the sum given above.
k  
k  
X
X
k ν k−νk ν k−ν
Claim 1.
p q
· ν = kp and
p q· (k − ν) = kq
ν
ν
ν=0
ν=0
The first equality can be shown as follows.
k  
k  
X
X
k ν k−νk ν k−ν
p q
·ν =
p q
·ν
ν
ν
ν=0
ν=1

k−1 
X
k
=
pν+1 q k−1−ν · (ν + 1)
ν
+
1
ν=0
=

=
=

k−1
X




k − 1 ν+1 k−(ν+1)
k·
p q
ν
ν=0

k−1 
X
k − 1 ν (k−1)−ν
kp ·
p q
ν
ν=0
kp · (p + q)k−1 = kp .

24Thomas Zeugmann

The other equality can be proved analogously, which yields Claim 1.
Now, proceeding as above, we obtain
E[CONV − 1] =∞X

Pr(CONV − 1 > µ)

µ=0

≤

λ+

∞ X
k  
X
k
µ=λ ν=0

=

λ+

∞ X
k  
X
k
µ=λ ν=0

=

λ+

ν

∞
X

µ

p ·

ν

p q

=kp

=

λ + kp ·

∞
X
µ=λ



≤
≤

ν k−ν

µ

µ

· νp +

∞ X
k  
X
k

ν

µ=λ ν=0

k  
X
k

|ν=0

µ=λ

pν q k−ν · (νpµ + (k − ν)q µ )

ν

ν k−ν

p q

ν+

{z

}

∞
X
µ=λ

by Claim 1

p + kq ·

∞
X

q

µ

µ=λ

p −λ qλ+k·· ψ + · ψ −λqp
−λ
λ + kψ · (1 + τ ) .

µq ·pν q k−ν · (k − ν)q µ

k  
X
k

|ν=0


= λ+k·

ν=kq

pν q k−ν · (k − ν){zby Claim 1

p λ q λ·p + ·q
q
p

}





Finally, choosing λ = dlogψ ke gives the statement of the theorem as an easy calculation shows.
Now, taking into account that τ does not depend on the dimension n of thelearning domain {0, 1}n , we can easily determine the expected total learning time.
Corollary 16 (Reischuk and Zeugmann [33]). For every binomially distributed
text with parameter 0 < p < 1 the average total learning time of Algorithm IMLP forconcepts in Cn is at most O(n log n) .
Also, Algorithm IMLP possesses the two favorable properties needed to apply
Theorem 6, i.e., it is rearrangement-independent and conservative. Thus, we canconcludePr(CONV > 2 t · E[CONV ]) ≤ 2−t for all t ∈ N .
Next, we turn our attention to the design of a stochastic finite learner. We study thecase that the positive examples are binomially distributed with parameter p . But
we do not require precise knowledge about the underlying distribution. Instead, we
reasonably assume that prior knowledge is provided by parameters plow and pup suchthat plow ≤ p ≤ pup for the true parameter p . Binomial distributions fulfilling thisrequirement are called (plow , pup ) –admissible distributions. Let Dn [plow , pup ]denote the set of such distributions on Xn .
If bounds plow and pup are available, the Algorithm IMLP can be transformed
into a stochastic finite learner inferring all concepts from Cn with high confidence.

From Learning in the Limit to Stochastic Finite Learning

25

Theorem 17 (Reischuk and Zeugmann [33]). Let 0 < plow ≤ pup < 1 andψ := min{ 1−p1low , p1up } . Then (Cn , Dn [plow , pup ]) is stochastically finitely learnable with
high confidence from text. To achieve δ -confidence no more than O log2 1/δ · logψ nmany examples are necessary.
Proof. The stochastic finite learner is based on Algorithm IMLP and a counterfor the number of examples already processed. We set



plow
1 − plowpup
1 − pupτmax = max,,,.
1 − plowplow
1 − puppup
If Algorithm IMLP is run for ϑ := dlogψ ne + τmax + 2 many examples, Theorem 15
implies that ϑ is at least as large as the expected convergence stage E[CONV ] .
In order to achieve the desired confidence, the learner sets γ := dlog 1δ e and runs
Algorithm IMLP for a total of 2 γ · ϑ examples. This is the reason why we needa counter for the number of examples processed. The algorithm outputs the lasthypothesis h2 γ·ϑ produced by Algorithm IMLP and stops thereafter. The reliability
follows from the tail bounds established in Theorem 6.

4.2. Learning Monomials from Informant
Finally, we ask how the results obtained so far translate to the case of learning frominformant. Since Algorithm IML does not learn anything from negative examples,
one may expect that it behaves much poorer in this setting. First, we investigate theuniform distribution over Xn . Again, we have the trivial cases that the target concept
is “FALSE” or m is a monomial without irrelevant bits. In the first case, no example
is needed at all, while in the latter one, there is only one positive example having
probability 2−n . Thus the expected number of examples needed until successful
learning is 2n = 2#(m) .
Theorem 18 (Reischuk and Zeugmann [33]). Let c = L(m) ∈ Cn be a nontrivial
concept. If a data sequence for c is generated from the uniform distribution on thelearning domain by independent draws, the expected number of examples needed by
Algorithm IML until convergence is bounded by
E[CONV ] ≤ 2#(m) (dlog2 k(m)e + 3) .

Proof. Let CONV + be a random variable for the number of positive examples
needed until convergence. Every positive example is preceded by a possibly empty
block of negative examples. Thus, we can partition the initial segment of any randomly
drawn informant read until convergence into CONV + many blocks Bj containing acertain number of negative examples followed by precisely one positive example. LetΛj be a random variable for the length of block Bj . Then CONV = Λ1 + Λ2 +· · · + ΛCONV + , where the Λj are independently identically distributed. In order to26

Thomas Zeugmanncompute the distribution of Λj , it suffices to calculate the probabilities to draw anegative and a positive example, respectively. Since the overall number of positive
examples for c is 2k with k = k(m) , the probability to generate a positive example is2k−n . Hence, the probability to draw a negative example is 1 − 2k−n . Consequently,
Pr(Λj = µ + 1) =1 − 2k−nµ· 2k−n .

Therefore,
E[CONV ] = E[Λ1 + Λ2 + · · · + ΛCONV + ]∞X
E[Λ1 + Λ2 + · · · + Λζ | CONV + = ζ] · Pr(CONV + = ζ)
=
=

ζ=0
∞
X

ζ · E[Λ1 ] · Pr(CONV + = ζ)

ζ=0= E[CONV +] · E[Λ1 ]By Theorem 15, we have E[CONV +] ≤ dlog2 ke + 3 , and thus it remains to estimate
E[Λ1 ] . A simple calculation shows
Lemma 2. For every 0 < a < 1 , it holds:∞X(µ + 1) · aµ = (1 − a)−2 .

µ=0

Using this estimation we can conclude
E[Λ1 ] =∞X(µ + 1) · Pr(Λ1 = µ + 1)µ=0

= 2k−n∞X(µ + 1) · 1 − 2k−nµ= 2n−k ,µ=0

and thus the theorem follows.
Hence, as long as the length of m is constant, and therefore k(m) = n − O(1) , westill achieve an expected total learning time of order n log n . But if #(m) grows linearly the expected total learning becomes exponential. On the other hand, if there aremany relevant literals then even h0 may be considered as a not too bad approximation for c . Consequently, it is natural at this point to introduce an error parameterε ∈ (0, 1) as in the PAC model, and to ask whether one can achieve an expected
sample complexity for computing an ε -approximation that is bounded by a function
depending on log n and 1/ε .
To answer this question, let us formally define error m (hj ) = D(L(hj ) 4 L(m)) tobe the error made by hypothesis hj with respect to monomial m . Here L(hj )4L(m)stands for the symmetric difference of L(hj ) and L(m) and D for the underlyingFrom Learning in the Limit to Stochastic Finite Learning

27

probability distribution with respect to which the examples are drawn. Note that byconstruction of Algorithm IML we can conclude error m (hj ) = D(L(m) \ L(hj )) .
We call hj an ε –approximation for m if error m (hj ) ≤ ε . Furthermore, we
redefine the stage of convergence. Let m be any monomial, and let d = (dj )j∈N be
an informant for L(m) , then
CONV ε (d) := the least number j such thaterror m (IML(di )) ≤ ε for all i ≥ j .
Note that once the Algorithm IML has reached an ε -approximate hypothesis all
further hypotheses will also be at least that close to the target monomial.
The following theorem gives an affirmative answer to the question posed above.
Theorem 19 (Reischuk and Zeugmann [33]). Let c = L(m) ∈ Cn be a nontrivial
concept. Assuming that examples are drawn at random independently from the uniform distribution, the expected number of examples needed by Algorithm IML untilconverging to an ε –approximation for c can be bounded by
E[CONV ε ] ≤1· (dlog2 k(m)e + 3) .
ε

Proof. It holds error m (hini ) = 2k(m)−n , since hini misclassifies exactly the positive examples. Therefore, if error m (h0 ) ≤ ε , we are already done. Now suppose
error m (h0 ) > ε . Consequently, 1/ε > 2n−k(m) , and thus the bound stated in the theorem is larger than 2n−k(m) (dlog2 k(m)e + 3) , which, by Theorem 18 is the expected
number of examples needed until convergence to a correct hypothesis.
Thus, additional knowledge concerning the underlying probability distribution pays
off again. Applying Theorem 6 and modifying the stochastic finite learner presented
above mutatis mutandis, we get a learner identifying ε -approximations for all concepts
in Cn stochastically with high confidence using O( 1ε · log 1δ · log n) many examples.
Comparing this bound with the sample complexity given in the PAC model, we seethat it is reduced exponentially, i.e., instead of a factor n now we have the factor
log n .
Finally, we can generalize the last results to the case that the data sequences arebinomially distributed for some parameter p ∈ (0, 1) . This means that any particular
vector containing ν times a 1 and n − ν a 0 has probability pν (1 − p)n−ν since a
1 is drawn with probability p and a 0 with probability 1 − p . First, Theorem 18
generalizes as follows.
Theorem 20 (Reischuk and Zeugmann [33]). Let c = L(m) ∈ Cn be a nontrivial
concept. Let m contain precisely π positive literals and ν negative literals. If thelabeled examples for c are independently binomially distributed with parameter p and28

Thomas Zeugmannp1, p1 } and τ := max{ 1−p, 1−p} , then the expected number of examples
ψ := min{ 1−ppneeded by Algorithm IML until convergence can be bounded by

E[CONV ] ≤1
pπ (1 − p)ν

(dlogψ k(m)e + τ + 2) .

Proof. Assuming the same notation as in the proof of Theorem 18, it is easy to
see that we only have to recompute E[Λ1 ] , and thus Pr(Λ1 = µ + 1) , too. Since m
contains precisely π positive literals and ν negative literals, the probability to draw
a positive example is clearly pπ (1 − p)ν , and thus the probability to randomly drawa negative example is 1 − pπ (1 − p)ν . Consequently,
Pr(Λ1 = µ + 1) = (1 − pπ (1 − p)ν )µ · pπ (1 − p)ν ,1
and Lemma 2 gives E[Λ1 ] = pπ (1−p)ν .

Theorem 19 directly translates into the setting of binomially distributed inputs,
too.
Theorem 21 (Reischuk and Zeugmann [33]). Let c = L(m) ∈ Cn be a nontrivial
concept. Assume that the examples are drawn with respect to a binomial distributionp1
with parameter p , and let ψ := min{ 1−p, p1 } and τ := max{ 1−p, 1−p} . Then thepexpected number of examples needed by Algorithm IML until converging to an ε approximation for c can be bounded by
E[CONV ] ≤1· (dlogψ k(m)e + τ + 2) .
εFinally, one can also get stochastic finite approximations with high confidence frominformant with an exponentially smaller sample complexity.
Theorem 22 (Reischuk and Zeugmann [33]). Let 0 < plow ≤ pup < 1 andψ := min{ 1−p1low , p1up } . For (Cn , Dn [plow , pup ]) ε -approximations are stochasticallyfinitely learnable with δ -confidence from informant for any ε, δ ∈ (0, 1) .
For this purpose, O 1ε · log2 1/δ · logψ n many examples suffice.

5. Conclusions
The present paper surveyed results recently obtained concerning the iterative learnability of the class of all pattern languages and finite unions thereof. In particular,
it could be shown that there are strong dependencies between iterative learning, theclass of admissible hypothesis spaces and additional requirements to the learner suchas consistency, conservativeness and the decidability of the inclusion problem for the
hypothesis space chosen. Looking at these results, we have seen that the LWA is insome sense optimal.

From Learning in the Limit to Stochastic Finite Learning

29

Moreover, by analyzing the average-case behavior of Lange and Wiehagen’s patternlanguage learning algorithm with respect to its total learning time and by establishingexponentially shrinking tail bounds for a rather rich class of limit learners, we havebeen able to transform the LWA into a stochastic finite learner. The price paid is theincorporation of a bit prior knowledge concerning the class of underlying probability
distributions. When applied to the class of all k -variable pattern languages, where
k is a priori known, the resulting total learning time is linear in the expected string
length.
Thus, the present paper provides evidence that analyzing the average-case behavior of limit learners with respect to their total learning time may be considered asa promising path towards a new theory of efficient algorithmic learning. Recently
obtained results along the same path as outlined in Erlebach et al.[11] as well as in
Reischuk and Zeugmann [32, 34] provide further support for the fruitfulness of thisapproach.
In particular, in Reischuk and Zeugmann [32, 34] we have shown that one-variable
pattern languages are learnable for basically all meaningful distributions within an
optimal linear total learning time on the average. Furthermore, this learner canalso be modified to maintain the incremental behavior of Lange and Wiehagen’s [19]algorithm. Instead of memorizing the pair (PRE, SUF) , it can also store just the two or
three examples from which the prefix PRE and the suffix SUF of the target pattern has
been computed. While it is no longer iterative, it is still a bounded example memory
learner. A bounded example memory learner is essentially an iterative learner that isadditionally allowed to memorize an a priori bounded number of examples (cf. [9] for
a formal definition).
While the one-variable pattern language learner from [34] is highly practical, ourstochastic finite learner for the class of all pattern languages is still not good enough forpractical purposes. But our results surveyed point to possible directions for potential
improvements. However, much more effort seems necessary to design a stochastic
finite learner for PAT (k) .
Additionally, we have applied our techniques to design a stochastic finite learner forthe class of all concepts describable by a monomial which is based on Haussler’s [14]Wholist algorithm. Here we have assumed the examples to be binomially distributed.
The sample size of our stochastic finite learner is mainly bounded by log(1/δ) log n ,where δ is again the confidence parameter and n is the dimension of the underlying
Boolean learning domain. Thus, the bound obtained is exponentially better than thebound provided within the PAC model.
Our approach also differs from U-learnability introduced by Muggleton [27]. Firstof all, our learner is fed with positive examples only, while in Muggleton’s [27] model
examples labeled with respect to their containment in the target language are provided. Next, we do not make any assumption concerning the distribution of the target
patterns. Furthermore, we do not measure the expected total learning time with respect to a given class of distributions over the targets and a given class of distributions

30

Thomas Zeugmann

for the sampling process, but exclusively in dependence on the length of the target.
Finally, we require exact learning and not approximately correct learning.

References[1] D. Angluin, Finding patterns common to a set of strings, Journal of Computerand System Sciences 21 (1) (1980) 46–62.
[2] D. Angluin, Inductive inference of formal languages from positive data, Information and Control 45 (2) (1980) 117–135.
[3] D. Angluin and C.H. Smith, Inductive inference: Theory and methods. Computing Surveys 15 (3) (1983) 237–269.
[4] D. Angluin and C.H. Smith, Formal inductive inference, in: St.C. Shapiro (Ed.),
Encyclopedia of Artificial Intelligence, Vol. 1, Wiley-Interscience Publication,
New York, 1987, pp. 409–418.
[5] S. Arikawa, T. Shinohara and A. Yamamoto, Learning elementary formal systems, Theoretical Computer Science 95 (1) (1992) 97–113.
[6] L. Blum and M. Blum, Toward a mathematical theory of inductive inference,
Information and Control 28 (2) (1975) 125–155.
[7] A. Blumer, A. Ehrenfeucht, D. Haussler and M. Warmuth, Learnability and the
Vapnik-Chervonenkis dimension, Journal of the ACM 36 (1989) 929–965.
[8] I. Bratko and S. Muggleton, Applications of inductive logic programming, Communications of the ACM 38 (11) (1995) 65–70.
[9] J. Case, S. Jain, S. Lange and T. Zeugmann, Incremental concept learning forbounded data mining, Information and Computation 152 (1) (1999) 74–110.
[10] R.P. Daley and C.H. Smith, On the complexity of inductive inference, Information and Control 69 (1-3) (1986) 12–40.
[11] T. Erlebach, P. Rossmanith, H. Stadtherr, A. Steger and T. Zeugmann, Learning
one-variable pattern languages very efficiently on average, in parallel, and byasking queries, Theoretical Computer Science 261 (1/2) (2001) 119–156.
[12] E.M. Gold, Language identification in the limit, Information and Control 10 (5)(1967) 447–474.
[13] S.A. Goldman, M.J. Kearns and R.E. Schapire, Exact identification of circuits
using fixed points of amplification functions, SIAM Journal of Computing 22 (4)(1993) 705–726.

From Learning in the Limit to Stochastic Finite Learning

31[14] D. Haussler, Bias, version spaces and Valiant’s learning framework, in: Proceedings of the Fourth International Workshop on Machine Learning, Morgan
Kaufmann, San Mateo, CA, 1987, pp. 324–336.
[15] D. Haussler, M. Kearns, N. Littlestone and M.K. Warmuth, Equivalence ofmodels for polynomial learnability, Information and Computation 95 (2) (1991)
129–161.
[16] S. Jain, D. Osherson, J.S. Royer and A. Sharma, “Systems That Learn: An
Introduction to Learning Theory,” MIT-Press, Boston, Massachusetts, 1999.
[17] T. Jiang, A. Salomaa, K. Salomaa and S. Yu, Inclusion is undecidable for patternlanguages, in: A. Lingas, R. Karlsson, and S. Carlsson ( Eds.), Automata, Languages and Programming, 20nd International Colloquium, ICALP 93, Lund, Sweden, July 5-9, 1993, Proceedings, Lecture Notes in Computer Science, Vol. 700,
Springer-Verlag, Berlin, 1993, pp. 301–312.
[18] M. Kearns and L. Pitt, A polynomial-time algorithm for learning k –variable
pattern languages from examples, in: R. Rivest, D. Haussler, and M.K. Warmuth (Eds.), Proceedings of the Second Annual Workshop on Computational
Learning Theory, Santa Cruz, California, Morgan Kaufmann, San Mateo, CA,
1989, pp. 57–71.
[19] S. Lange and R. Wiehagen, Polynomial-time inference of arbitrary pattern languages, New Generation Computing 8 (4) (1991) 361–370.
[20] S. Lange and T. Zeugmann, Language learning in dependence on the space of
hypotheses, in: L. Pitt (Ed.), Proceedings of the Sixth Annual ACM Conference
on Computational Learning Theory, July 26th-28th, 1993, Santa Cruz, California,
ACM Press, New York, 1993, pp. 127–136.
[21] S. Lange and T. Zeugmann, Set-driven and rearrangement-independent learningof recursive languages, Mathematical Systems Theory 29 (6) (1996) 599–634.
[22] S. Lange and T. Zeugmann, Incremental learning from positive data, Journal ofComputer and System Sciences 53 (1) (1996) 88–103.
[23] N. Lavrač and S. Džeroski, “Inductive Logic Programming: Techniques andApplications,” Ellis Horwood, 1994.
[24] T. Mitchell. “Machine Learning,” McGraw-Hill, New York, 1997.
[25] A. Mitchell, A. Sharma, T. Scheffer and F. Stephan, The VC-dimension of
subclasses of pattern languages, in: O. Watanabe and T. Yokomori (Eds.),
Algorithmic Learning Theory, 10th International Conference, ALT ’99, Tokyo,
Japan, December 1999, Proceedings, Lecture Notes in Artificial Intelligence, Vol.
1720, Springer, Berlin, 1999, pp. 93 - 105.

32

Thomas Zeugmann[26] S. Miyano, A. Shinohara and T. Shinohara, Polynomial-time learning of elementary formal systems, New Generation Computing 18 (3) (2000) 217–242.
[27] S. Muggleton, Bayesian Inductive Logic Programming, in: M. Warmuth (Ed.),
Proceedings of the Seventh Annual ACM Conference on Computational Learning
Theory, July 12th-15th, 1994, New Brunswick, New Jersey, ACM Press, New
York, 1994, pp. 3–11.
[28] S. Muggleton and L. De Raedt, Inductive logic programming: Theory and methods, Journal of Logic Programming 19/20 (1994) 669–679.
[29] R.P. Nix, Editing by examples, Yale University, Dept. Computer Science, Technical Report 280, 1983.
[30] D.N. Osherson, M. Stob and S. Weinstein, “Systems that Learn, An Introduction to Learning Theory for Cognitive and Computer Scientists,” MIT-Press,
Cambridge, Massachusetts, 1986.
[31] L. Pitt, Inductive inference, DFAs and computational complexity, in: K.P. Jantke(Ed.), Analogical and Inductive Inference, International Workshop AII ’89, Reinhardsbrunn Castle, GDR, October 1989, Proceedings, Lecture Notes in Artificial
Intelligence, Vol. 397, Springer-Verlag, Berlin, 1989, pp. 18–44.
[32] R. Reischuk and T. Zeugmann, Learning one-variable pattern languages in linear
average time, in: Proceedings of the Eleventh Annual Conference on Computational Learning Theory, July 24th - 26th 1998, Madison, Wisconsin, ACM Press,
New York, 1998, pp. 198–208.
[33] R. Reischuk and T. Zeugmann, A complete and tight average-case analysis oflearning monomials, in: C. Meinel and S. Tison (Eds.), STACS 99, 16th Annual
Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March
1999, Proceedings, Lecture Notes in Computer Science, Vol. 1563, Springer 1999,
pp. 414–423.
[34] R. Reischuk and T. Zeugmann, An average-case optimal one-variable patternlanguage learner, Journal of Computer and System Sciences 60 (2) (2000) 302–
335.
[35] H. Rogers, Jr., “Theory of Recursive Functions and Effective Computability,”
McGraw–Hill, New York, 1967.
[36] P. Rossmanith and T. Zeugmann, Stochastic finite learning of the pattern languages, Machine Learning 44 (1-2) (2001) 67–91.
[37] A. Salomaa, Patterns (The Formal Language Theory Column), EATCS Bulletin
54 (1994) 46–62.

From Learning in the Limit to Stochastic Finite Learning

33[38] A. Salomaa, Return to patterns (The Formal Language Theory Column), EATCS
Bulletin 55 (1994) 144–157.
[39] S. Shimozono, A. Shinohara, T. Shinohara, S. Miyano, S. Kuhara and S. Arikawa,
Knowledge acquisition from amino acid sequences by machine learning system
BONSAI, Trans. Information Processing Society of Japan 35 (1994) 2009–2018.
[40] R.E. Schapire, Pattern languages are not learnable, in: M.A. Fulk and J. Case
(Eds.), Proceedings of the Third Annual Workshop on Computational Learning
Theory, Morgan Kaufmann, San Mateo, CA, 1990, pp. 122–129.
[41] T. Shinohara, Inferring unions of two pattern languages, Bulletin of Informatics
and Cybernetics 20 (1983) 83–88.
[42] T. Shinohara, Inductive inference of monotonic formal systems from positive
data, New Generation Computing 8 (4) (1991) 371–384.
[43] T. Shinohara and S. Arikawa, Pattern inference, in: K.P. Jantke and S. Lange(Eds.), Algorithmic Learning for Knowledge-Based Systems, Lecture Notes in
Artificial Intelligence, Vol. 961, Springer-Verlag, Berlin, 1995, pp. 259–291.
[44] T. Shinohara and H. Arimura, Inductive inference of unbounded unions of patternlanguages from positive data, in: S. Arikawa and A.K. Sharma (Eds.), Algorithmic Learning Theory, 7th International Workshop, ALT ’96, Sydney, Australia,
October 1996, Proceedings, Lecture Notes in Artificial Intelligence, Vol. 1160,
Springer-Verlag, Berlin, 1996, pp. 256–271.
[45] R. Smullyan, “Theory of Formal Systems,” Annals of Mathematical Studies,No. 47, Princeton, NJ, 1961.
[46] L.G. Valiant, A theory of the learnable, Communications of the ACM 27 (11)(1984) 1134–1142.
[47] R. Wiehagen, Limes-Erkennung rekursiver Funktionen durch spezielle Strategien,
Journal of Information Processing and Cybernetics (EIK) 12 (1/2) (1976) 93–99.
[48] R. Wiehagen and T. Zeugmann, Ignoring data may be the only way to learn
efficiently, Journal of Experimental and Theoretical Artificial Intelligence 6 (1)(1994) 131–144.
[49] R. Wiehagen and T. Zeugmann, Learning and Consistency, in: K.P. Jantke and
S. Lange (Eds.), Algorithmic Learning for Knowledge-Based Systems, Lecture
Notes in Artificial Intelligence, Vol. 961, Springer-Verlag, Berlin, 1995, pp. 1–24.
[50] K. Wright, Identification of unions of languages drawn from an identifiable class,in: R. Rivest, D. Haussler, and M.K. Warmuth (Eds.), Proceedings of the Second
Annual Workshop on Computational Learning Theory, Santa Cruz, California,
Morgan Kaufmann, San Mateo, CA, 1989, pp. 328–333.

34

Thomas Zeugmann[51] T. Zeugmann, Lange and Wiehagen’s pattern language learning algorithm: An
average-case analysis with respect to its total learning time, Annals of Mathematics and Artificial Intelligence 23 (1-2) (1998) 117–145.
[52] T. Zeugmann and S. Lange, A guided tour across the boundaries of learning
recursive languages, in: K.P. Jantke and S. Lange (Eds.), Algorithmic Learning
for Knowledge-Based Systems, Lecture Notes in Artificial Intelligence, Vol. 961,
Springer-Verlag, Berlin, 1995, pp. 190–258.
[53] T. Zeugmann, S. Lange and S. Kapur, Characterizations of monotonic and dual
monotonic language learning, Information and Computation 120 (2) (1995) 155–173.