Learning k-Variable Pattern Languages
Efficiently Stochastically Finite on Average
from Positive Data
Peter Rossmanith1 and Thomas Zeugmann2
1

Institut für Informatik, Technische Universität München, 80290 München, Germany
rossmani@in.tum.de
2
Department of Informatics, Kyushu University, Kasuga 816-8580, Japanthomas@i.kyushu-u.ac.jp

Abstract. The present paper presents a new approach of how to convert Gold-style [4] learning in the limit into stochastically finite learningwith high confidence. We illustrate this approach on the concept class ofall pattern languages. The transformation of learning in the limit into
stochastically finite learning with high confidence is achieved by first
analyzing the Lange–Wiehagen [7] algorithm with respect to its averagecase time behavior until convergence. This algorithm learns the class ofall pattern languages in the limit from positive data. The expectation of
the total learning time is analyzed and exponentially small tail bounds
are established for a large class of probability distributions. For patterns containing k different variables Lange and Wiehagen’s algorithmpossesses an expected total learning time of O (1/α)k (log1/β (k))E[Λ] ,where α and β are two easily computable parameters from the underlying probability distribution, and E[Λ] is the expected example string
length.
Finally, we show how to arrive at stochastically finite learning with highconfidence.

1

Introduction

Suppose you have to deal with a learning problem of the following kind. On the
one hand, it is known that the problem is not solvable within the PAC model
unless you achieve the needed breakthrough in complexity theory. On the other
hand, your learning problem has been proved to be learnable within Gold’s [4]learning in the limit model. Here, a learner is successively fed data about theconcept to be learned and is computing a sequence of hypotheses about thetarget object. However, the only knowledge you have about this sequence is its
convergence in the limit to a hypothesis correctly describing the target concept.
Therefore, you never know whether the learner has already converged. Such an
uncertainty may not be tolerable in many applications. In general, there may
be no way to overcome this uncertainty. But part of the problem is caused by
the fact that learning in the limit has to be successful from all possible data
sequences. It is intuitively clear that there are data sequences that contain hugeamounts of redundant data before successful learning can take place. But suchsequences may be rare in practice.
What we would like to present in this paper is a rather general method to
overcome the difficulties described above. This method is based on an averagecase analysis of known limit learners with respect to their time complexity including tail bounds. Assuming a certain amount of knowledge concerning theunderlying probability distributions, we can put it all together and arrive atstochastically finite learning with high confidence. This learning model may beconsidered as a variant of PAC-learning. The major differences are easily explained. First, stochastically finite learning with high confidence is not completely distribution independent. Thus, from that perspective, this variant is
weaker than the PAC-model. But the hypothesis computed is probably exactly
correct. Moreover, the learner is fed positive data only, while the correctness of
its final hypothesis is measured with respect to both positive and negative data.
Second, it should be emphasized that our approach is applicable in a rather
general context. Suppose you have a PAC-learner for the concept class you wantto learn. In that case, additional knowledge about the underlying probability
distributions directly yields better hypotheses, i.e., probably correct ones insteadof probably approximately correct ones. But its main advantage is achieved when
dealing with situations as described above, i.e., in those cases where it is highly
unlikely to obtain a PAC-learner. Now, instead of facing all the disadvantagesof limit learning additional knowledge about the underlying probability distributions nicely buys a learner that is even more reliable than a PAC-learner.
In the following, we exemplify this approach by dealing with the learnabilityof the well-known pattern languages (PAT for short), a prominent and important
language family that can be learned from positive data (cf. [1, 10, 12]). There arealso numerous interesting applications for pattern language learners (cf., e.g., [12]and the references therein).
Nevertheless, despite its importance there is still a bottleneck concerning
efficient learning algorithms. Kearns and Pitt [5], Ko, Marron and Tzeng [6]and Schapire [11] intensively studied the learnability of pattern languages in the
PAC–learning model. In particular, Schapire [11] proved that the class PAT is
not PAC-learnable regardless of the representation used by the learning algorithm, provided only that the learner is requested to output a polynomial-size
hypothesis that can be evaluated in polynomial time, unless P/poly = N P /poly .
However, the class Pat of all patterns is not a polynomial time representation
for PAT, since the membership problem for PAT with respect to Pat is N Pcomplete [1]. In contrast, we show Pat to be stochastically finite learnable withhigh confidence with respect to Pat (cf. Theorem 9). On the other hand, Kearns
and Pitt [5] designed a polynomial-time PAC-learner for the set of all k-variable
pattern languages (k arbitrarily fixed) if only product distributions are allowed.
But the constant in the running time achieved depends doubly exponentially onk, and thus, their algorithm becomes rapidly impractical when k increases.
In contrast, our stochastically finite learner achieves a running time whose
constant depends only exponentially on the number k of different variables oc-

curring in the target pattern and is otherwise linearly bounded in the expected
length of sample strings fed to the learner (cf. Corollary 1). The price paid israther small. We restrict the class of all probability distributions to a subclassthat has an arbitrary but fixed bound on two parameters arising naturally. In
essence, that means at least two letters from the underlying probability distribution have a known lower bound on their probability.
We use the Lange–Wiehagen [7] algorithm (LWA for short) as the basic ingredient for achieving our goal. The LWA learns the class of all pattern languages in
the limit from positive data. That means the learner is fed successively example
strings and its previously made hypothesis, and it computes from these input
data a new pattern as its hypothesis. The sequence of all hypotheses stabilizes
to a single pattern which generates the target pattern language. First, we generalize and improve the average-case analysis of the same algorithm performed byZeugmann [14] for its expected total learning time. The time taken by a learnerfor computing a single hypothesis from its input data is usually called update
time. The total learning time is the time taken by the learner until convergence, i.e., the sum of all update times until successful learning. Note that it is ahighly non-trivial task to define an appropriate complexity measure for learningin the limit (cf. [8]). The total learning time has been introduced by Daley andSmith [3]. As Pitt [8] pointed out, allowing the total learning time to depend on
the length of the examples seen so far is unsatisfactory, since the learner may
delay convergence until a sufficiently long example appears so that the algorithm
may meet the wanted polynomial time bound. We therefore measure the total
learning time only in dependence on the length of the target pattern.
Second, we show how the improved analysis can be used to establish stochastically finite learnability. The basic idea can be described as follows. Based on
exponentially shrinking tail bounds obtained from our average case analysis forthe expected total learning time, the new learner takes as input a randomly
generated text and a confidence parameter δ. It then computes internally hypotheses until the confidence bound is met and outputs exclusively its last guess(cf. Section 4, Definition 2).
Owing to lack of space some results and most proofs could not be included
into this extended abstract; they can be found in the full paper (cf. [9]).

2Preliminaries

Let N = {0, 1, 2, . . .} be the set of all natural numbers, and let N+ = N \ {0}.
Following Angluin [1] we define patterns and pattern languages as follows. Let
A = {0, 1, . . .} be any non-empty finite alphabet containing at least two elements.
By A∗ we denote the set of all strings over A and by A+ = A∗ \ ε all non-null
strings. By |A| we denote the cardinality of A. Furthermore, let X = { xi i ∈ N }be an infinite set of variables such that A∩X = ∅. Patterns are non-empty strings
over A ∪ X, e.g., 01, 0x0 111, 1x0 x0 0x1 x2 x0 are patterns. The length of a strings ∈ 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 variables in π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 in π. The examples given above are patterns in canonicalform. In the sequel we assume, without loss of generality, that all patterns arein canonical form. By Pat we denote the set of all patterns in canonical form.
Let π ∈ Pat, 1 ≤ i ≤ |π|; we use π(i) to denote the i-th symbol in π. If
π(i) ∈ A, then π(i) is a constant; otherwise π(i) ∈ X is a variable. Analogously,by s(i) we denote the i-th symbol in s for s ∈ A+ . By #var(π) we denotethe number of different variables occurring in π, and by #xi (π) we denote thenumber of occurrences of variable xi in π. If #var(π) = k, then we refer to π as
to a k-variable pattern. Let k ∈ N, by Pat k we denote the set of all k-variable
patterns. Furthermore, let π ∈ Pat k , and let u0 , . . . , uk−1 ∈ A+ ; then we denoteby π[x0 /u0 , . . . , xk−1 /uk−1 ] the string w ∈ A+ obtained by substituting uj foreach 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 referto (u0 , . . . , uk−1 ) as to a shortest substitution. Now, let π ∈ Pat k , and let S ={(u0 , . . . , uk−1 ) uj ∈ A+ , j = 0, . . . , k − 1} be any finite set of substitutions.
Then we set S(π) = {π[x0 /u0 , . . . , xk−1 /uk−1 ] (u0 , . . . , uk−1 ) ∈ S}, i.e., S(π) is
the set of all strings obtained from pattern π by applying all the substitutions
from S to it. For every π ∈ Pat k we define the language generated by pattern πby L(π) = {π[x0 /u0 , . . . , xk−1 /uk−1 ] u0 , . . . , uk−1 ∈ A+ }. By
S PAT k we denotethe set of all k-variable pattern languages. Finally, PAT = k∈N PAT k denotes
the set of all pattern languages over A. Note that for every L ∈ PAT there is
precisely one pattern π ∈ Pat such that L = L(π) (cf. [1]).
We are interested in inductive inference, which means to gradually learn aconcept from successively growing sequences of examples. If L is a language to be
identified, a sequence (s1 , s2 , s3 , . . .) is called a text for L iff L = {s1 , s2 , s3 , . . .}(cf. [4]). However, in practical applications, the requirement to exhaust the language to be learned will be hardly fulfilled. We therefore omit this restriction
here. Instead, we assume that the sequence t = s1 , s2 , s3 , . . . contains “enough”
information to recognize the target pattern. As for the LWA, “enough” can bemade precise by requesting that sufficiently many shortest strings appear in the
text. We shall come back to this point when defining admissible probability
distributions.
An inductive inference machine (IIM) is an algorithm that takes as input
larger and larger initial segments of a text and outputs, after each input, ahypothesis from a prespecified hypothesis space (cf. [4]). In the case of patternlanguages the hypothesis space is Pat.
Definition 1. PAT is called learnable in the limit from text iff there is an IIM
M such that for every L ∈ PAT and every text for L,(1) for all n ∈ N+ , M (tn ) is defined,(2) there is a pattern π ∈ Pat such that L(π) = L and for almost all n ∈ N+ ,M (tn ) = π.

It is well-known that pattern languages are learnable in the limit from text
(cf. [1]).
Whenever one deals with the average case analysis of algorithms one has toconsider probability distributions over the relevant input domain. For learningfrom text, we have the following scenario. Every string of a particular patternlanguage is generated by a substitution. Therefore, it is convenient to consider
probability distributions over the set of all possible substitutions. That is, if π ∈Pat k , then it suffices to consider any probability distribution D over A+ × · · · ×
A+ (k times). For (u0 , . . . , uk−1 ) ∈ A+ × · · · × A+ 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 as follows. 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 product distribution over A+ × · · · × A+ , i.e.,
Qk−1
D(u0 , . . . , uk−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 toQ
denote the distribution over A+
k−1
on substitution strings, i.e, D(u0 , . . . , uk−1 ) = j=0 d(uj ). As a special case ofa regular product distribution we sometimes consider the uniform distribution
over A+ , i.e., d(u) = 1/(2 · |A|)` for all strings u ∈ A+ with |u| = `.
Note, however, that most of our results can be generalized to larger classesof distributions. Finally, we can provide the announced specification of what
is meant by “enough” information. We call a regular distribution admissible
provided d(a) > 0 for at least two different elements a ∈ A.
Following Daley and Smith [3] we define the total learning time as follows. Let
M be any IIM that learns all the pattern languages. Then, for every L ∈ PAT
and every text t for L, let Conv (M, t) be the least number m ∈ N+ such that
M (tn ) = M (tm ) for all n ≥ m, denotes the stage of convergence of M on t.
Moreover, by TM (tn ) we denote the time to compute M (tn ). We measure thistime as a function of the length of the input and call it update time. Finally,
the total learning time taken by the IIM M on input t, one string at a time, isdefined as
Conv (M,t)
X
T T (M, t) =df
TM (tn ).
n=1

Assuming any fixed admissible probability distribution D as described above,
we aim to evaluate the expectation of T T (M, t) with respect to D which we call
total average learning time.
The model of computation as well as the representation of patterns we assume
is the same as in Angluin [1]. We assume a random access machine that performsa reasonable menu of operations each in unit time on registers of length O(log n)bits, where n is the input length.
Finally, we recall the LWA. The LWA works as follows. Let hn be the hypothesis computed after reading s1 , . . . , sn , i.e., hn = M (s1 , . . . , sn ). Then h1 = s1

and for all n > 1: hn−1 ,hn = sn ,hn−1 ∪ sn ,if |hn−1 | < |sn |if |hn−1 | > |sn |if |hn−1 | = |sn |The algorithm computes the new hypothesis only from the latest example andthe old hypothesis. If the latest example is longer than the old hypothesis, theexample is ignored, i.e., the hypothesis does not change. If the latest example
is shorter than the old hypothesis, the old hypothesis is ignored and the new
example becomes the new hypothesis. Hence, the LWA is quite simple and the
update time will be very fast for these two possibilities.
If, however, |hn−1 | = |sn | the new hypothesis is the union of hn−1 and sn .
The union % = π ∪ s of a canonical pattern π and a string s of the same lengthis defined asif π(i) = s(i)
 π(i),
if π(i) 6= s(i) & ∃k < i : [%(k) = xj , s(k) = s(i), π(k) = π(i)]%(i) = xj ,
xm ,otherwise, where m = #var(%(1) . . . %(i − 1)),
where %(0) = ε for notational convenience. The resulting pattern is canonical.
Obviously, the union operation can be computed in quadratic time. We finish
this section by providing a linear-time algorithm computing the union operation. The only crucial part is to determine whether there is some k < i with%(k) = xj , s(k) = s(i), and π(k) = π(i). The new algorithm uses an array
I = {1, . . . , |s|}A×(A∪{x0 , ..., x|π|−1 }) for finding the correct k, if any, in constanttime. The array I is partially initialized by writing the first position into it atwhich s(i), π(i) occurs. Then, for each position i, the algorithm checks whether
Is(i),π(i) = i. Suppose it is, thus s(i), π(i) did not occur left to i. Hence, it remains to check whether or not π(i) = s(i) and %(i) can be immediately output.
If Is(i),π(i) 6= i, then s(i), π(i) did occur left to i. Hence, in this case it suffices to
output %(j) where j = Is(i),π(i) .
Theorem 1. The union operation can be computed in linear time by Algorithm 1.
Algorithm 1
Input: A pattern π and a string s ∈ A+ such that |π| = |s|.
Output: π ∪ sfor i = 1, . . . , |s| do Is(i),π(i) ← i od; m ← 0;
for i = 1, . . . , |s| do j ← Is(i),π(i) ;if i = j thenif π(i) = s(i) then %(i) = π(i)else %(i) ← xm ; m ← m + 1 fi
else %(i) = %(j) fi
od
The correctness of this algorithm can be easily proved inductively by formalizing the argument given above. We omit the details.

3

Results of the Analysis

Following [14] we perform the desired analysis in dependence on the number
k of different variables occurring in the target pattern π. If k = 0, then the
LWA immediately converges. Therefore, in the following we assume k ∈ N+ ,and π ∈ Pat k . For analyzing the average-case behavior of the LWA, in thefollowing we let t = s1 , s2 , s3 , . . . range over all randomly generated texts withrespect to some arbitrarily fixed admissible probability distribution D. Thenthe stage of convergence is a random variable which we denote by C. Notethat the distribution of C depends on π and on D. We introduce several more
random variables. By Λi we denote the length of the example string si , i.e.,Λi = |si |. Since all Λi are independent and identically distributed, we can assume
that the random variable has the same distribution as Λ. We shall use Λ whentalking about the length of an example when the number of the example is
not important. Particularly, we will often use the expected length of a random
example E[Λ].
Let T = Λ1 + Λ1 + . . . + ΛC be the total length of examples processed untilconvergence. Whether the LWA converges on s1 , . . . , sr depends only on thoseexamples si with si ∈ L(π)min = { w w ∈ L(π), |w| = |π| }. It should be mentioned that without seeing a single shortest string, k-variable pattern languages
cannot be learned provided k > 1. This is easily seen if one looks at patterns
x0 · · · xk and x0 · · · xk xk+1 . The languages they generate are identical except for
strings of length k. Using a result from Zeugmann [14], this negative result extends to arbitrary k and k + 1 variable patterns, respectively. Moreover, as weshall see, waiting for one shortest strings takes almost the same time as waiting
for all the shortest strings needed to converge.
Let r ∈ N+ ; by Mr we denote the number of minimum length examples
among the first r strings, i.e., Mr = |{ i 1 ≤ i ≤ r and Λi = |π| }|. In particular,
MC is the number of minimum length examples read until convergence. We
assume that computing % ∪ s takes at most c · |%| steps, where c is a constantthat depends on the implementation of the union operation.
We express all estimates with the help of the following parameters: E[Λ], c, αand β. To get concrete bounds for a concrete implementation one has to obtainc 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 notmatter, we simply write u or u0 .
The two parameters α and β are now defined via d.
PFirst, α is simply theprobability that u has length 1, i.e., α = Pr(|u| = 1) = a∈A d(a). Second, β isthe conditional probability that two random words that get substituted into π
are identical under the condition that both their length are 1, i.e.,
.P
2
 P
β = Pr u = u0 |u| = |u0 | = 1 = a∈A d(a)2a∈A d(a) .
The parameters α and β are therefore quite easy to compute even for complicated distributions since they depend only on |A| point probabilities. We canalso compute E[Λ] for a pattern π from d quite easily. Let α̂ = 1/α.

Theorem 2. E[T T ] = O α̂k (log1/β (k))E[Λ] .
Next, we insert the parameter for the uniform distribution into Theorem 2.
For the uniform distribution we get α̂ = 2, β = 1/|A|, and E[Λ] ≤ 2|π|.
Theorem 3. E[T T ] = O(2k |π| log|A| (k)) for the uniform distribution.
Often time is the most precious resource, but the number of examples untilconvergence can also be interesting, if the gathering of examples is expensive.
Theorem 4. E[C] = O(α̂k · log1/β (k)).
We can even get a better understanding of the behavior if we examine theunion operations by themselves. Is it worthwhile to optimize the computationof w ∪ π? Let U be the number of union operations and V be the time spent inunion operations.
Theorem 5.
(1) E[U ] = O(α̂k + log1/β (k))(2) E[V ] = O(α̂kE[Λ] + log1/β (k)|π|) if the union operation is performed by
Algorithm 1,(3) E[V ] = O(α̂kE 2 [Λ] + log1/β (k)|π|2 ) if the union operation is performed by
the naı̈ve algorithm.
Consequently, in most cases we can use the simple, quadratic algorithm for union
operations, since they make only a small contribution to the overall running time.
The proof of this counterintuitive result is unfortunately very long and can befound in the full paper (cf. [9]).
3.1Tail Bounds

Finally we have to ask whether the expected value of the total learning time
is sufficient for judging the LWA. The expected value of a random variable isonly one aspect of its distribution. In general we might also be interested on how
often the learning time exceeds the average substantially. Again this is a question
motivated mainly by practical considerations. Equivalently we can ask, how goodthe distribution is concentrated around its expected value. Often this questionis answered by estimating the variance, which enables the use of Chebyshev’s
inequality. If the variance is not available, Markov’s inequality provides us with(worse) tail bounds: Pr(X ≥ t · E[X]) ≤ 1/t. The Markov inequality is quite
general but produces only weak bounds. The next theorem gives better tailbounds for a large class of learning algorithms including the LWA. A learneris set-driven, if its outputs depends only on the range of its input (cf. [13]).
Conservative learners maintain their actual hypotheses at least as long as they
have not seen data contradicting them (cf. [2]).
Theorem 6. Let X be the sample complexity of a conservative and set-driven
learning algorithm. Then V [X] ≤ 20E[X]2 and Pr(X ≥ t · E[X]) ≤ 2−t/2 for allt ∈ N.
Theorem 6 holds also for conservative, rearrangement independent learners,
which means that each hypothesis must not depend on the order of the examples.

3.2

The Sample Complexity

In this section we estimate the sample complexity. While being of interest itself,
whenever acquiring examples is expensive, E[C] is also an important ingredientin the estimation of the total learning time.
Lemma 1. Pr(MC > m) = Pr(C > r Mr = m) ≤ k2 β m + kβ m/2 for allm, r ∈ N+ with r ≥ m.
Proof. Without loss of generality, let Sr = {s1 , . . . , sm }, i.e., m = r. Additionally, we can make the assumption that all strings si ∈ Sr have length k,since we need to consider only shortest words for MC and we can assume thatπ = x0 x1 . . . xk−1 (cf. [14]). For 1 ≤ j ≤ k let cj = s0 (j)s1 (j) . . . sm−1 (j) be thejth column of a matrix whose rows are s1 , . . . , sm .
The algorithm computes the hypothesis π on input Sr iff no column is constant and there are no identical columns. The probability that cj is constantis at most β m/2 , since m/2 pairs have to be identical, but this short argument
works only for even m. A slightly more complicated proof shows that the same
bound holds also for odd m. The probability that at least one of the k columns
is constant is then at most kβ m/2 .
The probability that ci = cj is β m if i 6= j. The probability that some columnsare equal is therefore at most k2 β m . The probability that there is a constantcolumn or that there are identical columns is at most k2 β m + kβ m/2 .
Inserting the above tail bounds into the definition of the expected value yields
an upper bound on E[MC ].
Lemma 2. E[MC ] ≤ (2 ln(k)+3)/(ln(1/β))+2 ≤ 7 log1/β (k)+2 = O(log1/β (k)).
Proof. MC is the number of shortest words read until convergence. By Lemma 1
we have Pr(MC > m) ≤ k2 β m + kβ m/2 and thus E[MC ] is∞X
m=0

Pr(MC > m) ≤ ` +∞  
Xkm=`

2

β m + kβ m/2


=`+

√ `
  `
β
k
β
√
+k
2 1−β
1− β



for each natural number `. We choose ` = 2 log1/β (k) + 1, which yields when√ββinserted in above inequality √E[MC ] ≤ ` + 1−β+ √ . The lemma now follows
1−

β

β
β
from the inequality 1−β+ √ ≤ 3/ ln(1/β), which can be proved by standard
1− βmethods from calculus.

Our next major goal is to establish an upper bound on the overall numberof examples to be read on average by the LWA until convergence.
Theorem 7. E[C] = α̂k E[MC ] ≤ α̂k (7 log1/β (k) + 2) = O(α̂k log1/β (k)).
Proof. The LWA converges after reading exactly C example strings. Among theseexamples are MC many of minimum length. Prior to these minimum length
words come MC possibly empty blocks of words whose length is bigger than|π|. Let us call the numbers of those words in the ith block Gi . Then C =G1 + G2 + · · · + GMC + MC . It is easy to compute the distribution of Gi :Pr(Gi = m) = Pr(Λ > |π|)m Pr(Λ = |π|) = (1 − αk )m αk(1)

Of course, all Gi are identically distributed and independent. The expected valueof C is therefore
E[C] = E[MC ] + E[G1 + · · · + GMC ]∞X= E[MC ] +E[G1 + · · · + Gm | MC = m] · Pr(MC = m)
= E[MC ] +

m=0
∞
X

m · E[G1 ] · Pr(MC = m) = E[MC ] + E[MC ] · E[G1 ]

(2)

m=0

The expected value of G1 isE[G1 ] =∞X

m · Pr(Λ > |π|)m · Pr(Λ = |π|) =m=0

1 − αkPr(Λ > |π|)=Pr(Λ = |π|)αk(3)

Now combine (2) and (3) with E[MC ] ≤ 7 log1/β (k) + 2 from Lemma 2.
3.3

The Length of the Text until Convergence

When we use the linear time algorithm for union operations, then the total
learning time is O(T ), so the length of the text until convergence is an importantnumber. In the following we analyze its expected value.
Lemma 3. Let m ≥ 1. Then E[Λ1 | G1 = m] = (E[Λ] − αk )/(1 − αk ).
Theorem 8. E[T ] = E[MC ] · |π| + α̂k (E[Λ] − 1) ≤ (7 log1/β (k) + 2) |π| + α̂k (E[Λ] − 1) = O α̂k (log1/β (k))E[Λ] .
Proof. We can write the length of text read until convergence as T = T1 + T2 +· · · + TMC + |π|MC . Exactly MC strings of length |π| are read; all other strings
are longer and are contained in blocks in front of those minimum length strings.
The ith block contains Gi strings and we denote the total length of these Gi
strings by Ti (these are different Ti ’s than in [14]). In order to get E[T ] we startby computing E[T1 ].
E[T1 ] =
=
=

∞
X
m=0
∞
X
m=1
∞
X
m=1

E[Λ1 + · · · + Λm | G1 = m] · Pr(G1 = m)
m · E[Λ1 | G1 = m] · Pr(G1 = m)m·

E[Λ] − αk· (1 − αk )m αk
1 − αk= (E[Λ] − αk )αk

∞
X
m=1

(by Lemma 3 and (1))

m(1 − αk )m−1 = α̂k E[Λ] − 1

Now it is easy to estimate E[T ]. We use that T1 and MC are independent.
E[T ] − |π|E[MC ] = E[T1 + · · · + TMC ]∞X=
m · E[T1 ] · Pr(MC = m) = E[MC ] · E[T1 ]m=0and thus E[T ] = E[MC ] |π| + α̂k E[Λ] − 1 . Finally insert the estimation ofE[MC ] from Lemma 2.

4

Learning Stochastically Finite with High Confidence

Definition 2. Let D be an admissible probability distribution. PAT is calledstochastically finitely learnable with high confidence from random text iff there
is an IIM M such that for every L ∈ PAT and every number δ ∈ (0, 1), M
outputs the single hypothesis π, L(π) = L, with probability at least δ, and stops
thereafter, when fed a random text according to D and L.
Note that the learner in the definition above takes δ as additional input andthat the definition immediately generalizes to arbitrary concept classes.
Next, we show how the LWA can be transformed into a stochastically finite
learner that identifies all the pattern languages with high confidence provided
we have a bit of prior knowledge about the class of admissible distributions that
may actually be used to generate the information sequences.
Theorem 9. Let α∗ , β∗ ∈ (0, 1). Assume D to be a class of admissible probability distributions over A+ such that α ≥ α∗ , β ≥ β∗ and E(d) finite forall distributions d ∈ D. Then PAT is stochastically finitely learnable with highconfidence from random text for all distributions D generated by any d ∈ D.
Proof. Let d ∈ D and δ ∈ (0, 1) be arbitrarily fixed. Note that d induces anadmissible probability distribution D. Furthermore, let t = s1 , s2 , s3 , . . . be any
randomly generated text with respect to D for the target pattern language. The
learner M uses the LWA as a subroutine. Additionally, it has a counter for thenumber of examples already seen. We exploit the fact that the LWA produces asequence (τ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|τ |been processed, where C = 2 log(1/(1 − δ))(7α̂∗ + 2) log1/β∗ (|τ |) and τ is thecurrent output made by the LWA. By Theorem 6 and 7, it follows that after
processing
2 log(1/(1 − δ))(7α̂k + 2) log1/β (k)(A)
examples the LWA converges with probability at least δ. The number C is bigger
since |τ | ≥ k. If we are learning PAT k instead of PAT , we can replace |τ | in (A)by k to get a better bound.
If we fix k in advance to learn only PAT k then we arrive at a stochasticallyfinite linear-time learner for PAT k . This is a major improvement, since the constant depending on k grows only exponentially in k in contrast to the doubly
exponentially growing constant in Kearns and Pitt’s [5] algorithm.

Corollary 1. Let α∗ , β∗ ∈ (0, 1). Assume D to be a class of admissible probability distributions over A+ such that α ≥ α∗ , β ≥ β∗ and E(d) finite for all
distributions d ∈ D. Furthermore, let k ∈ N+ be arbitrarily fixed. Then there
exists a learner M such that
(1) M learns PAT k stochastically finitely with high confidence from random text
for all admissible probability distributions D generated by any d ∈ D, and
(2) The running time of M is bounded by O α̂k log(1/(1 − δ)) log1/β (k)E[Λ] .

References
1. D. Angluin. Finding patterns common to a set of strings. Journal of Computerand System Sciences, 21(1):46–62, 1980.
2. D. Angluin. Inductive inference of formal languages from positive data. Information and Control, 45:117–135, 1980.
3. R. Daley and C.H. Smith. On the complexity of inductive inference. Information
and Control, 69:12–40, 1986.
4. E. M. Gold. Language identification in the limit. Information and Control, 10:447–
474, 1967.
5. 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,
editors, Proc. 2nd Annual ACM Workshop on Computational Learning Theory
pp. 57–71, 1991, Morgan Kaufmann Publishers Inc., San Mateo.
6. Ker-I Ko, A. Marron and W.G. Tzeng. Learning string patterns and tree patterns
from examples. In B.W. Porter and R.J. Mooney, editors, Proc. 7th International
Conference on Machine Learning, pp. 384–391, 1990, Morgan-Kaufmann Publishers Inc., San Mateo.
7. S. Lange and R. Wiehagen. Polynomial-time inference of arbitrary pattern languages. New Generation Computing, 8:361–370, 1991.
8. L. Pitt. Inductive inference, DFAs and computational complexity. In K.P. Jantke, editor, Proc. Analogical and Inductive Inference, Lecture Notes in Artificial
Intelligence 397, pp. 18–44, Berlin, 1989, Springer-Verlag.
9. P. Rossmanith and T. Zeugmann. Learning k-variable pattern languages efficiently
stochastically finite on average from positive data, DOI Technical Report DOITR-145, Department of Informatics, Kyushu University, January 1998.
10. A. Salomaa. Patterns & Return to patterns. (The Formal Language Theory Column). EATCS Bulletin, 54:46–62 and 55:144–157, 1994.
11. R.E. Schapire. Pattern languages are not learnable. In M.A. Fulk and J. Case,
editors, Proc. 3rd Annual ACM Workshop on Computational Learning Theory,
pp. 122 – 129, 1990. Morgan Kaufmann Publishers Inc., San Mateo.
12. T. Shinohara and S. Arikawa. Pattern inference. In K. P. Jantke and S. Lange,
editors, Algorithmic Learning for Knowledge-Based Systems, Lecture Notes in Artificial Intelligence 961, pp. 259–291, Berlin, 1995. Springer-Verlag.
13. K. Wexler and P. Culicover. Formal Principles of Language Acquisition. MIT
Press, Cambridge, MA, 1980.
14. T. Zeugmann. Lange and Wiehagen’s pattern learning algorithm: An averagecase analysis with respect to its total learning time. Annals of Mathematics andArtificial Intelligence, 23:1-2, 117–145, 1998.