Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries.
A pattern is a finite string of constant and variable symbols. The langauge generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting non-empty strings for variables. We study the learnability of one-variable pattern languages in the limit with respect to the update time needed for computing a new single hypothesis and the expected total learning time taken until convergence to a correct hypothesis. Our results are as follows. First, we design a consistent and set-driven learner that, using the concept of descriptive patterns, achieves update time O(n2logn), where n is the size of the input sample. The best previously known algorithm for computing descriptive one-variable patterns requires time O(n4logn) (cf. Angluin, J. Comput. Systems Sci. 21 (1) (1980) 46-62). Second, we give a parallel version of this algorithm that requires time O(logn) and O(n3/logn) processors on an EREW-PRAM. Third, using a modified version of the sequential algorithm as a subroutine, we devise a learning algorithm for one-variable patterns whose expected total learning time is O(l2logl) provided that sample strings are drawn from the target language according to a probability distribution with expected string length l. The probability distribution must be such that strings of equal length have equal probability, but can be arbitrary otherwise. Thus, we establish the first algorithm for learning one-variable pattern languages having an expected total learning time that provably differs from the update time by a constant factor only. Finally, we show how the algorithm for descriptive one-variable patterns can be used for learning one-variable patterns with a polynomial number of superset queries with respect to the one-variable patterns as query language.
Introduction
A pattern is a string of constant symbols and variable symbols. The language
generated by a pattern - is the set of all strings obtained by substituting strings
of constants for the variables in - (cf. [1]). Pattern languages and variations
thereof have been widely investigated (cf., e.g., [17, 18, 19]). This continuous
interest in pattern languages has many reasons, among them the learnability in
? A full version of this paper is available as technical report (cf. [4]).
the limit of all pattern languages from text (cf. [1, 2]). Moreover, the learnability
of pattern languages is very interesting with respect to potential applications
(cf., e.g., [19]). Given this, efficiency becomes a central issue. However, defining
an appropriate measure of efficiency for learning in the limit is a difficult problem
(cf. [16]). Various authors studied the efficiency of learning in terms of the
update time needed for computing a new single guess. But what really counts in
applications is the overall time needed by a learner until convergence, i.e., the
total learning time. One can show that the total learning time is unbounded in
the worst-case. Thus, we study the expected total learning time. For the purpose
of motivation we shortly summarize what has been known in this regard.
The pattern languages can be learned by outputting descriptive patterns as
hypotheses (cf. [1]). The resulting learning algorithm is consistent and set-driven.
A learner is set-driven iff its output depends only on the range of its input
(cf., e.g., [20, 22]). In general, consistency and set-drivenness considerably limit
the learning capabilities (cf., e.g., [14, 22]). But no polynomial time algorithm
computing descriptive patterns is known, and hence already the update time is
practically infeasible. Moreover, finding a descriptive pattern of maximum possible
length is NP-complete (cf. [1]). Thus, it is unlikely that there is a polynomial-time
algorithm computing descriptive patterns of maximum possible length.
It is therefore natural to ask whether efficient pattern learners can benefit from
the concept of descriptive patterns. Special cases, e.g., regular patterns, non-cross
patterns, and unions of at most k regular pattern languages (k a priori fixed)
have been studied. In all these cases, descriptive patterns are polynomial-time
computable (cf., e.g., [19]), and thus these learners achieve polynomial update
time but nothing is known about their expected total learning time. Another
restriction is obtained by a priori bounding the number k of different variables
occurring in a pattern (k-variable patterns) but it is open if there are polynomial-time
algorithms computing descriptive k-variable patterns for any fixed k ? 1
(cf. [9, 12]). On the other hand, k-variable patterns are PAC-learnable with
respect to unions of k-variable patterns as hypothesis space (cf. [11]).
Lange and Wiehagen [13] provided a learner LWA for all pattern languages
that may output inconsistent guesses. The LWA achieves polynomial update time.
It is set-driven (cf. [21]), and even iterative, thus beating Angluin's [1] algorithm
with respect to its space complexity. For the LWA, the expected total learning
time is exponential in the number of different variables occurring in the target
pattern (cf. [21]). Moreover, the point of convergence for the LWA definitely
depends on the appearance of sufficiently many shortest strings of the target lan-
guage, while for the other algorithms mentioned above at least the corresponding
correctness proofs depend on it. Thus, the following problem arises naturally.
Does there exist an efficient pattern language learner benefiting from the concept
of descriptive patterns thereby not depending on the presentation of sufficiently
many shortest strings from the target language, and still achieving an
expected total learning time polynomially bounded in the expected string length?
We provide a complete affirmative answer by studying the special case of
one-variable patterns. We believe this case to be a natural choice, since it is non-trivial
(there may be exponentially many consistent patterns for a given sample),
and since it has been the first case for which a polynomial time algorithm computing
descriptive patterns has been known (cf. [1]). Angluin's [1] algorithm for
finding descriptive patterns runs in time O(n 4 log n) for inputs of size n and it
always outputs descriptive patterns of maximum possible length. She was aware
of possible improvements of the running time only for certain special cases, but
hoped that further study would provide insight for a uniform improvement.
We present such an improvement, i.e., an algorithm computing descriptive one-variable
patterns in O(n 2 log n) steps. A key idea to achieve this goal is giving
up necessarily finding descriptive patterns of maximum possible length. Note
that all results concerning the difficulty of finding descriptive patterns depend
on the additional requirement to compute ones having maximum possible length
(cf., e.g., [1, 12]). Thus, our result may at least support the conjecture that more
efficient learners may arise when one is definitely not trying to find descriptive
patterns of maximum possible length but just descriptive ones, instead.
Moreover, our algorithm can be also efficiently parallelized, using O(logn)
time and O(n n) processors on an EREW-PRAM. Previously, no efficient
parallel algorithm for learning one-variable pattern languages was known.
Our main result is a version of the sequential algorithm still learning all one-variable
pattern languages that has expected total learning time O(' 2 log ') if the
sample strings are drawn from the target language according to a probability
distribution D having expected string length '. D can be arbitrary except that
strings of equal length have equal probability. In particular, all shortest strings
may have probability 0. Note that the expected total learning time differs only
by a constant factor from the time needed to update actual hypotheses. On the
other hand, we could only prove that O(log ') many examples are sufficient to
achieve convergence.
Finally, we deal with active learning. Now the learner gains information about
the target object by asking queries to an oracle. We show how the algorithm for
descriptive one-variable patterns can be used for learning one-variable patterns
by asking polynomially many superset queries. Another algorithm learning all
pattern languages with a polynomial number of superset queries is known, but
it uses a much more powerful query language, i.e., patterns with more than one
variable even when the target pattern is a one-variable pattern (cf. [3]).
1.1. The Pattern Languages and Inductive Inference
be the set of all natural numbers, and let IN
For all real numbers x we define bxc to be the greatest integer less than or equal
to x. Let be any finite alphabet containing at least two elements.
A   denotes the free monoid over A. By A + we denote the set of all finite non-null
strings over A, i.e., A denotes the empty string. Let
INg be an infinite set of variables with A " Patterns are
strings from . The length of a string s 2 A   and of a pattern - is
denoted by jsj and j-j, respectively. By Pat we denote the set of all patterns.
by -(i) we denote the i-th symbol in -, e.g.,
then -(i) is called a constant; otherwise -(i) 2 X,
i.e., -(i) is a variable. We use s(i), to denote the i-th symbol in
. By #var(-) we denote the number of different variables occurring in -,
and # x i
(-) denotes the number of occurrences of variable x i in -. If
then - is a k-variable pattern. By Pat k we denote the set of all k-variable patterns.
In the case we denote the variable occurring by x.
denotes the
string obtained by substituting u j for each occurrence of x j in -. The tuple
called substitution. For every pattern - 2 Pat k we define the
language generated by - by
. By PAT k we denote the set of all k-variable pattern languages.
denotes the set of all pattern languages over A.
Note that several problems are decidable or even efficiently solvable for PAT 1
but undecidable or NP-complete for PAT . For example, for general pattern
languages the word problem is NP-complete (cf. [1]) and the inclusion problem
is undecidable (cf. [10]), but both problems are decidable in linear time for one-variable
pattern languages. On the other hand, PAT 1 is still incomparable to
the regular and context free languages.
A finite set is called a sample. A pattern - is
consistent with a sample S if S ' L(-). A (one-variable) pattern - is called
descriptive for S if it is consistent with S and there is no other consistent (one-
pattern - such that L(- ) ae L(-).
Next, we define the relevant learning models. We start with inductive inference
of languages from text (cf., e.g., [15, 22]). Let L be a language; every
infinite sequence of strings with
to be a text for L. Text(L) denotes the set of all texts for L. Let t be a text,
and r 2 IN. We set t r the initial segment of t of length
r we denote the range of t r , i.e., t
rg. We define an
inductive inference machine (abbr. IIM) to be an algorithmic device taking as
its inputs initial segments of a text t, and outputting on every input a pattern
as hypothesis (cf. [7]).
Definition 1. PAT is called learnable in the limit from text iff there is an
IIM M such that for every L 2 PAT and every t 2 Text(L),
(1) for all r 2 IN, M (t r ) is defined,
(2) there is a - 2 Pat such that almost all r 2 IN, M (t r
The learnability of the one-variable pattern languages is defined analogously
by replacing PAT and Pat by PAT 1 and Pat 1 , respectively.
When dealing with set-driven learners, it is often technically advantageous to
describe them in dependence of the relevant set t
r , i.e., a sample, obtained as
input. Let
and refer to n as the size
of sample S.
3 We study non-erasing substitutions. Erasing substitutions have been also considered,
(variables may be replaced by "), leading to a different language class (cf. [5]).
PAT as well as PAT 1 constitute an indexable class L of uniformly recursive
languages, i.e., there are an effective enumeration (L j ) j2IN of L and a recursive
function f such that for all j 2 IN and all s 2 A   we have f(j;
Except in Section 3, where we use the PRAM-model, we assume the same
model of computation and representation of patterns as in [1]. Next we define the
update time and the total learning time. Let M be any IIM. For every L 2 PAT
the least number m such that for all r -
the stage of convergence of M on t. By TM (t r ) we
denote the time to compute M (t r ), and we call TM (t r ) the update time of M .
The total learning time taken by the IIM M on successive input t is defined as
Finally, we define learning via queries. The objects to be learned are the elements
of an indexable class L. We assume an indexable class H as well as a
fixed effective enumeration of it as hypothesis space for L. Clearly, H
must comprise L. A hypothesis h describes a target language L iff
source of information about the target L are queries to an oracle. We distinguish
membership, equivalence, subset, superset, and disjointness queries (cf. [3]). Input
to a membership query is a string s, and the output is yes if s 2 L and
no otherwise. For the other queries, the input is an index j and the output is
yes if
query), and (disjointness query), and no otherwise. If the reply is
no, a counterexample is returned, too, i.e., a string s 2 L4h j (the symmetric
difference of L and h j respectively. We
always assume that all queries are answered truthfully.
Definition 2 (Angluin [3]). Let L be any indexable class and let H be a hypothesis
space for it. A learning algorithm exactly identifies a target L 2 L with
respect to H with access to a certain type of queries if it always halts and outputs
an index j such that
Note that the learner is allowed only one hypothesis which must be correct.
The complexity of a query learner is measured by the number of queries to be
asked in the worst-case.
2. An Improved Sequential Algorithm
We present an algorithm computing a descriptive pattern - 2 Pat 1 for a sample
as input. Without loss of generality, we assume
that s 0 is the shortest string in S. Our algorithm runs in time O(n js 0 j log js 0
and is simpler and much faster than Angluin's [1] algorithm, which needs time
log js 0 j). Angluin's [1] algorithm computes explicitly a representation
of the set of all consistent one-variable patterns for S and outputs a descriptive
pattern of maximum possible length. We avoid to find a descriptive pattern of
maximum possible length and can thus work with a polynomial-size subset of all
consistent patterns. Next, we review and establish basic properties needed later.
and only if - can be obtained from - by substituting a pattern % 2 Pat for x.
For a pattern - to be consistent with S, there must be strings ff
A + such that s i can be obtained from - by substituting ff i for x, for all
Given a consistent pattern -, the set fff is denoted by ff(S; -).
Moreover, a sample S is called prefix-free if jSj ? 1 and no string in S is a prefix
of all other strings in S. Note that the distinction between prefix-free samples
and non-prefix free samples does well pay off.
Lemma 2. If S is prefix-free then there exists a descriptive pattern - 2 Pat 1
for S such that at least two strings in ff(S; -) start with a different symbol.
Proof. Let u denote the longest common prefix of all strings in S. The pattern
ux is consistent with S because u is shorter than every string in S, since S is
prefix-free. Consequently, there exists a descriptive pattern - 2 Pat 1 for S with
we know that there exists a pattern % 2 Pat 1
such that longest common prefix of all strings in S, we
can conclude
A. Hence, and at least two
strings in ff(S; ux- ) must start with a different symbol. 2
(1)]g. Cons(S) is a subset of all consistent patterns for S, and
S is not prefix-free.
Lemma 3. Let S be any prefix-free sample. Then Cons(S) 6= ;, and every
of maximum length is descriptive for S.
Proof. Let S be prefix-free. According to Lemma 2 there exists a descriptive
pattern for S belonging to Cons(S); thus Cons(S) 6= ;. Now, suppose there is a
of maximum length which is not descriptive for S. Thus,
and, moreover, there exists a pattern - 2 Pat 1 such that S ' L(- ) as
well as L(- ) ae L(-). Hence, by Lemma 1 we know that - can be obtained from
- by substituting a pattern % for x. Since at least two strings in ff(S; -) start
with a different symbol, we immediately get %(1) 2 X. Moreover, at least two
strings in ff(S; - ) must also start with a different symbol. Hence - 2 Cons(S) and
-. Note that j-j - 1, since otherwise
contradicting L(- ) ae L(-). Finally, by j-j - 1, we may conclude
contradiction to - having maximum length. Thus, no such pattern - can exist,
and hence, - is descriptive. 2
Next, we explain how to handle non-prefix-free samples. The algorithm checks
whether the input sample consists of a single string s. If this happens, it outputs
s and terminates. Otherwise, it tests whether s 0 is a prefix of all other strings
. If this is the case, it outputs ux 2 Pat 1 , where u is the prefix of s 0
of length js terminates. Clearly, S ' L(ux). Suppose there is a pattern
- such that S ' L(- ), and L(- ) ae L(ux). Then Lemma 1 applies, i.e., there is a
% such that
thus, S 6' L(- ). Consequently, ux is descriptive.
Otherwise, jSj - 2 and s 0 is not a prefix of all other strings in S. Thus, by
Lemma 3 it suffices to find and to output a longest pattern in Cons(S).
The improved algorithm for prefix-free samples is based on the fact that
jCons(S)j is bounded by a small polynomial. Let k; l 2 IN, k ? 0; we call
patterns - with # x l occurrences of constants (k; l)-patterns. A
(k; l)-pattern has length k
Thus, there can only be a (k; l)-pattern in Cons(S) if there is an
satisfying js refers to the length of the string substituted
for the occurrences of x in the relevant (k; l)-pattern to obtain s 0 . Therefore,
there are at most bjs 0 j=kc possible values of l for a fixed value of k. Hence, the
number of possible (k; l)-pairs for which (k; l)-patterns in Cons(S) can exist is
bounded by
The algorithm considers all possible (k; l)-pairs in turn. We describe the algorithm
for one specific (k; l)-pair. If there is a (k; l)-pattern - 2 Cons(S), the
of the strings ff i 2 ff(S; -) must satisfy is the
substring of s i of length m i starting at the first position where the input strings
differ. If (js
2 IN for some i, then there is no consistent (k; l)-pattern and
no further computation is performed for this (k; l)-pair. The following lemma
shows that the (k; l)-pattern in Cons(S) is unique, if it exists at all.
Lemma 4. Let be any prefix-free sample. For every given
(k; l)-pair, there is at most one (k; l)-pattern in Cons(S).
The proof of Lemma 4 directly yields Algorithm 1 below. It either returns the
unique (k; l)-pattern - 2 Cons(S) or NIL if there is no (k; l)-pattern in Cons(S).
We assume a subprocedure taking as input a sample S, and returning the longest
common prefix u.
Algorithm 1. On input (k; l), and u do the following:
l and b - k and c - l do
else
l and S ' L(-) then return - else return NIL fi
Note that minor modifications of Algorithm 1 perform the consistency test
even while - is constructed. Putting Lemma 4 and the fact that there
are O(js possible (k; l)-pairs together, we directly obtain:
Lemma 5. prefix-free sample
g.
Using Algorithm 1 as a subroutine, Algorithm 2 below for finding a descriptive
pattern for a prefix-free sample S follows the strategy exemplified above. Thus, it
simply computes all patterns in Cons(S) and outputs one with maximum length.
For inputs of size n the overall complexity of the algorithm is O(n js 0 j log js 0
O(n 2 log n), since at most O(js 0 j log js 0 tests must be performed, which
have time complexity O(n) each.
Algorithm 2. On input do the following:
\Pi do
if there is a (k; js0
Output a maximum-length pattern - 2 P .
Note that the number of (k; l)-pairs to be processed is often smaller than
O(js since the condition (js restricts the possible
values of k if not all strings are of equal length. It is also advantageous to
process the (k; l)-pairs in order of non-increasing k l. Then the algorithm can
terminate as soon as it finds the first consistent pattern. However, the worst-case
complexity is not improved, if the descriptive pattern is x.
Finally, we summarize the main result obtained by the following theorem.
Theorem 1. Using Algorithm 2 as a subroutine, PAT 1 can be learned in the
limit by a set-driven and consistent IIM having update time O(n 2 log n) on input
samples of size n.
3. An Efficient Parallel Algorithm
Whereas the RAM model has been generally accepted as the most suitable
model for developing and analyzing sequential algorithms, such a consensus has
not yet been reached in the area of parallel computing. The PRAM model introduced
in [6], is usually considered an acceptable compromise. A PRAM consists
of a number of processors, each of which has its own local memory and can execute
its local program, and all of which can communicate by exchanging data
through a shared memory. Variants of the PRAM model differ in the constraints
on simultaneous accesses to the same memory location by different processors.
The CREW-PRAM allows concurrent read accesses but no concurrent write ac-
cesses. For ease of presentation, we describe our algorithm for the CREW-PRAM
model. The algorithm can be modified to run on an EREW-PRAM, however, by
the use of standard techniques.
computing descriptive one-variable patterns has been
known previously. Algorithm 2 can be efficiently parallelized by using well-known
techniques including prefix-sums, tree-contraction, and list-ranking as subroutines
(cf. [8]). A parallel algorithm can handle non-prefix-free samples S in the
same way as Algorithm 2. Checking S to be singleton or s 0 to be a prefix of all
other strings requires time O(log n) using O(n= log n) processors. Thus, we may
assume that the input sample is prefix-free. Additionally, we
assume the prefix-test has returned the first position d where the input strings
differ and an index t,
A parallel algorithm can handle all O(js 0 j log js 0 possible (k; l)-pairs in par-
allel. For each (k; l)-pair, our algorithm computes a unique candidate - for the
(k; l)-pattern in Cons(S), if it exists, and checks whether S ' L(-). Again, it
suffices to output any obtained pattern having maximum length. Next, we show
how to efficiently parallelize these two steps.
For a given (k; l)-pair, the algorithm uses only the strings s 0 and s t for calculating
the unique candidate - for the (k; l)-pattern in Cons(S). This reduces
the processor requirements, and a modification of Lemma 4 shows the candidate
pattern to remain unique.
Position j t in s t is said to be b-corresponding to position j 0 in s 0 if
k. The meaning of b-corresponding positions is as follows.
Suppose there is a consistent (k; l)-pattern - for fs such that position j 0
in s 0 corresponds to -(i) 2 A for some i, 1 - i - j-j, and that b occurrences of
x are to the left of -(i). Then -(i) corresponds to position
in s t .
For computing the candidate pattern from s 0 and s t , the algorithm calculates
the entries of an array EQUAL[j; b] of Boolean values first, where j ranges from
1 to js 0 j and b from 0 to k. EQUAL[j; b] is true iff the symbol in position j in s 0
is the same as the symbol in its b-corresponding position in s t . Thus, the array
is defined as follows: EQUAL[j; )). The
array EQUAL has O(kjs 0 entries each of which can be calculated in constant
time. Thus, using O(kjs 0 log n) processors, EQUAL can be computed in time
O(log n). Moreover, a directed graph G that is a forest of binary in-trees, can be
built from EQUAL, and the candidate pattern can be calculated from G using
tree-contraction, prefix-sums and list-ranking. The details are omitted due to
space restrictions. Thus, we can prove:
Lemma 6. Let be a sample, and n its size. Given the
array EQUAL, the unique candidate - for the (k; l)-pattern in Cons(S), or NIL,
if no such pattern exists, can be computed on an EREW-PRAM in time O(logn)
using O(kjs 0 processors.
Now, the algorithm has either discovered that no (k; l)-pattern exists, or it has
obtained a candidate (k; l)-pattern -. In the latter case, it has to test whether
- is consistent with S.
Lemma 7. Given a candidate pattern -, the consistency of - with any sample
S of size n can be checked on in time O(logn) using O(n= log n) processors
on a CREW-PRAM.
Putting it all together, we obtain the following theorem.
Theorem 2. There exists a parallel algorithm computing descriptive one-variable
patterns in time O(logn) using O(js
n) processors on a CREW-PRAM for samples of
size n.
Note that the product of the time and the number of processors of our algorithm
is the same as the time spent by the improved sequential algorithm above
larger, the product exceeds the time of
the sequential algorithm by a factor less than O(js
4. Analyzing the Expected Total Learning Time
Now, we are dealing with the major result of the present paper, i.e., with
the expected total learning time of our sequential learner. Let - be the target
pattern. The total learning time of any algorithm trying to infer - is unbounded
in the worst case, since there are infinitely many strings in L(-) that can mislead
it. However, in the best case two examples, i.e., the two shortest strings -[0=x]
and -[1=x], always suffice for a learner outputting descriptive patterns as guesses.
Hence, we assume that the strings presented to the algorithm are drawn from
L(-) according to a certain probability distribution D and compute the expected
total learning time of our algorithm. The distribution D must satisfy two criteria:
any two strings in L(-) of equal length must have equal probability, and the
expected string length ' must be finite. We refer to such distributions as proper
probability distributions.
We design an Algorithm 1LA inferring a pattern - 2 Pat 1 with expected total
learning time O(' 2 log '). It is advantageous not to calculate a descriptive pattern
each time a new string is read. Instead, Algorithm 1LA reads a certain number
of strings before it starts to perform any computations at all. It waits until the
length of a sample string is smaller than the number of sample strings read so
far and until at least two different sample strings have been read. During these
first two phases, it outputs s 1 , the first sample string, as its guess if all sample
strings read so far are the same, and x otherwise. If - is a constant pattern,
the correct hypothesis is always output and the algorithm never
reaches the third phase. Otherwise, the algorithm uses a modified version of
Algorithm 2 to calculate a set P 0 of candidate patterns when it enters Phase 3.
More precisely, it does not calculate the whole set P 0 at once. Instead, it uses
the function first cand once to obtain a longest pattern in P 0 , and the function
next cand repeatedly to obtain the remaining patterns of P 0 in order of non-increasing
length. This substantially reduces the memory requirements.
The pattern - obtained from calling first cand is used as the current candidate.
Each new string s is then compared to - . If s 2 L(- is output. Otherwise,
next cand is called to obtain a new candidate - 0 . Now, - 0 is the current candidate
and output, independently of s 2 L(- 0 ). If the longest common prefix of
all sample strings including s is shorter than that of all sample strings excluding
s, however, first cand is called again and a new list of candidate patterns is
considered. Thus, Algorithm 1LA may output inconsistent hypotheses.
Algorithm 1LA is shown in Figure 1. Let
defined as follows. If string w,
then fvxg. Otherwise, denote by u the longest common prefix of s and
be the set of patterns computed by Algorithms 1 and 2 above if
we omit the consistency check. Hence, P 0 ' Cons(S), where Cons(S) is defined
as in Section 2. P 0 necessarily contains the pattern - if s; s 0 2 L(-) and if the
longest common prefix of s and s 0 is the same as the longest constant prefix of -.
Assuming t, first cand (s; s 0 ) returns
returns - i+1 . Since we omit the consistency checks,
a call to first cand and all subsequent calls to next cand until either the correct
pattern is found or the prefix changes can be performed in time O(jsj 2 log jsj).
We will show that Algorithm 1LA correctly infers one-variable pattern languages
from text in the limit, and that it correctly infers one-variable pattern
languages from text with probability 1 if the sample strings are drawn from L(-)
according to a proper probability distribution. 4
Theorem 3. Let - be an arbitrary one-variable pattern. Algorithm 1LA correctly
infers - from text in the limit.
4 Note that learning a language L in the limit and learning L from strings that are
drawn from L according to a proper probability distribution are not the same.
r / 0;
repeat r / r string sr ;
until
while string sr ;
f Phase 3 g
s / a shortest string in fs1 ;
prefix of fs1 ;
if string in fs1 ; that is longer than s
else s 0 / a string in fs1 ; that differs from s in position juj
first cand(s;s 0 );
forever do
read string s 00 ;
if u is not a prefix of s 00 then
common prefix of s and s 00 ;
first cand(s;s 0 )
else if s
output hypothesis - ;
od
Fig. 1. Algorithm 1LA
Theorem 4. Let - 2 Pat 1 . If sample strings are drawn from L(-) according
to a proper probability distribution, Algorithm 1LA learns - with probability 1.
Proof. If outputs - after reading the first string
and converges. Otherwise, let  is a string of d \Gamma 1 constant
symbols and - 2 Pat 1 [f"g. After Algorithm 1LA has read two strings that differ
in position d, pattern - will be one of the candidates in the set P 0 implicitly
maintained by the algorithm. As each string s r , r ? 1, satisfies s 1 (d) 6= s r (d)
with probability (jAj \Gamma 1)=jAj - 1=2, this event must happen with probability 1.
After that, as long as the current candidate - differs from -, the probability that
the next string read does not belong to L(- ) is at least 1=2 (cf. Lemma 8 below).
Hence, all candidate patterns will be discarded with probability 1 until - is the
current candidate and is output. After that, the algorithm converges. 2
Lemma 8. Let ux- be a one-variable pattern with constant prefix u, and
be arbitrary such that s 0 (juj
Let - 6= - be a pattern from P 0 (fs to generate
a string s drawn from L(-) according to a proper probability distribution with
probability at least (jAj \Gamma 1)=jAj.
Now, we analyze the total expected learning time of Algorithm 1LA. Obvi-
ously, the total expected learning time is O(') if the target pattern - 2 A + .
Hence, we assume in the following that - contains at least one occurrence of x.
Next, we recall the definition of the median, and establish a basic property of
it that is used later. By E(R) we denote the expectation of a random variable R.
Definition 3. Let R be any random variable with range(R) ' IN. The median
of R is the number - 2 range(R) such that Pr(R ! - 1and Pr(R ? -) ! 1Proposition 1. Let R be a random variable with range(R) ' IN + . Then its
median - satisfies - 2E(R).
Lemma 9. Let D be any proper probability distribution, let L be the random
variable taking as values the length of a string drawn from L(-) with respect to
D, and let - be the median of L and let ' be its expectation. Then, the expected
number of steps performed by Algorithm 1LA during Phase 1 is O(-').
Proof. Let L i be the random variable whose value is the length of the i-th string
read by the algorithm. Clearly, the distribution of L i is the same as that of L. Let
R be the random variable whose value is the number of strings Algorithm 1LA
reads in Phase 1. Let L \Sigma := LR be the number of symbols read by
Algorithm 1LA during Phase 1. Let W 1 be the random variable whose value is
the time spent by Algorithm 1LA in Phase 1. Obviously, W
Claim 1. For we have: E(L i
E(L)
(1)
As L i must be at least i provided R ? i, Equation (1) can be proved as follows:
Similarly, it can be shown that E(L r
Furthermore, it is clear that E(L r
Now, we rewrite E(L \Sigma
E(L
E(L \Sigma
r?-
E(L \Sigma
Using as well as Equations (1) and (3), we obtain:
E(L)
For (fi), we use Equations (1) and (2) to obtain:
E(L)
(using
r
under the same assumptions as in Lemma 9, we can estimate the expected
number of steps performed in Phase 2 as follows.
Lemma 10. During Phase 2, the expected number of steps performed by Algorithm
1LA is O(').
Finally, we deal with Phase 3. Again, let L be as in Lemma 9. Then, the
average amount of time spent in Phase 3 can be estimated as follows.
Lemma 11. During Phase 3, the expected number of steps performed in calls
to the functions first cand and next cand is O(- 2 log -).
Lemma 12. During Phase 3, the expected number of steps performed in reading
strings is O(-' log -).
Proof. Denote by W rthe number of steps performed while reading strings in
Phase 3. We make a distinction between strings read before the correct set of
candidate patterns is considered, and strings read afterwards until the end of
Phase 3. The former are accounted for by random variable V 1 , the latter by V 2 .
If the correct set of candidate patterns, i.e., the set containing -, is not yet
considered, the probability that a new string does not force the correct set of
candidate patterns to be considered is at most 1=2. Denote by K the random
variable whose value is the number of strings that are read in Phase 3 before the
correct set of candidate patterns is considered. We have:
Assume that the correct set of candidate patterns P 0 contains M patterns that
are considered before pattern -. For any such pattern - , the probability that a
string drawn from L(-) according to a proper probability distribution is in the
language of - is at most 1=2, because either - has an additional variable or - has
an additional constant symbol (Lemma 8). Denote by V i
2 the steps performed
for reading strings while the i-th pattern in P 0 is considered.
log R), we obtain:
=O(E(L)- log -)
and
O(E(L)r log r)
Hence, we have E(W r
Lemma 13. During Phase 3, the expected number of steps performed in checking
whether the current candidate pattern generates a newly read sample string
is O(-' log -).
Putting it all together, we arrive at the following expected total learning time
required by Algorithm 1LA.
Theorem 5. If the sample strings are drawn from L(-) according to a proper
probability distribution with expected string length ' the expected total learning
time of Algorithm 1LA is O(' 2 log ').
5. Learning with Superset Queries
PAT is not learnable with polynomially many queries if only equivalence,
membership, and subset queries are allowed provided
This result may be easily extended to PAT 1 . However, positive results are also
known. First, PAT is exactly learnable using polynomially many disjointness
queries with respect to the hypothesis space PAT [FIN , where FIN is the set of
all finite languages (cf. [13]). The proof technique easily extends to PAT 1 , too.
Second, Angluin [3] established an algorithm exactly learning PAT with respect
to PAT by asking O(j-j 2 + j-jjAj) many superset queries. However, it requires
choosing general patterns - for asking the queries, and does definitely not work
if the hypothesis space is PAT 1 . Hence, it is natural to ask:
Does there exist a superset query algorithm learning PAT 1 with respect to
PAT 1 that uses only polynomially many superset queries?
Using the results of previous sections, we are able to answer this question af-
firmatively. Nevertheless, whereas PAT can be learned with respect to PAT by
restricted superset queries, i.e., superset queries not returning counterexamples,
our query algorithm needs counterexamples. Interestingly, it does not need a
counterexample for every query answered negatively, instead two counterexamples
always suffice. The next theorem shows that one-variable patterns are not
learnable by a polynomial number of restricted superset queries.
Theorem 6. Any algorithm exactly identifying all L 2 PAT 1 generated by
a pattern - of length n with respect to PAT 1 by using only restricted superset
queries and restricted equivalence queries must make at least jAj n\Gamma2 - 2 n\Gamma2
queries in the worst case.
Furthermore, we can show that learning PAT 1 with a polynomial number of
superset queries is impossible if the algorithm may ask for a single counterexample
only.
Theorem 7. Any algorithm that exactly identifies all one-variable pattern
languages by restricted superset queries and one unrestricted superset query needs
at least 2 queries in the worst case, where k is the length of the
counterexample returned.
The new algorithm QL works as follows (see Figure 2). Assume the algorithm
should learn some pattern -. First QL asks whether L(-) '
holds. This is the case iff if the answer is yes QL knows the
right result. Otherwise, QL obtains a counterexample C(0) 2 L(-). By asking
the answer is no, QL computes
g. Now we know that - starts with C(0)
but what about the i-th position of -? If
asks L(-) ' L(C(0)) to determine if this is the case. If
A, since this would imply that
Now QL uses the counterexample for the query L(-) ' L(C(0) -i x) to construct
a set x)g. By construction, the two counterexamples differ
in their i-th position, but coincide in their first positions.
else
while L(-) ' L(C(0) -i x) do i
else S / fC(0); C(C(0) -i x)g; R / Cons(S);
repeat - / max(R); R / R n f-g until L(-) ' L(-)
Fig. 2. Algorithm QL. This algorithm learns a pattern - by superset queries. The
queries have the form "L(-) ' L(- )," where - 2 Pat 1 is chosen by the algorithm. If the
answer to a query L(-) ' L(-) is no, the algorithm can ask for a counterexample C(- ).
By w -i we denote the prefix of w of length i and by max(R) some maximum-length
element of R.
Algorithm 2 in Section 2 computes
coincides with S in the first Again we narrowed the search
for - to a set R of candidates. Let m be the length of the shortest counterexample
in S. Then log m) by Lemma 5. Now, the only task left is to find -
among all patterns in R. We find - by removing other patterns from R by using
the following lemma.
Lemma 14. Let S ' A
implies - .
QL tests L(-) ' L(- ) for a maximum length pattern - 2 R and removes -
from R if L(-) 6' L(- ). Iterating this process finally yields the longest pattern -
for which L(-) ' L(- ). Lemma 14 guarantees -. Thus, we have:
Theorem 8. Algorithm QL learns PAT 1 with respect to PAT 1 by asking only
superset queries. The query complexity of QL is O(j-j+m log m) many restricted
superset queries plus two superset queries (these are the first two queries answered
no) for every language L(-) 2 PAT 1 , where m is the length of the shortest
counterexample returned.
Thus, the query complexity O(j-j+m log m) of our learner compares well with
that of Angluin's [3] learner (which is O(j-jjAj) when restricted to learn PAT 1 )
using the much more powerful hypothesis space PAT as long as the length of
the shortest counterexample returned is not too large.

Acknowledgements

A substantial part of this work has been done while the second author was visiting
Kyushu University. This visit has been supported by the Japanese Society
for the Promotion of Science under Grant No. 106011.
The fifth author kindly acknowledges the support by the Grant-in-Aid for
Scientific Research (C) from the Japan Ministry of Education, Science, Sports,
and Culture under Grant No. 07680403.



--R

Finding patterns common to a set of strings.
Inductive inference of formal languages from positive data.
Machine Learning
Efficient Learning of One-Variable Pattern Languages from Positive Data
The relation of two patterns with comparable languages.
Parallelism in random access machines.
Language identification in the limit.
An introduction to parallel algorithms.
time inference of general pattern languages.
Inclusion is undecidable for pattern languages.
A polynomial-time algorithm for learning k-variable pattern languages from examples
A note on the two-variable pattern-finding problem


Systems that learn: An introduction to learning theory for cognitive and computer scientists.
Inductive inference
Patterns. EATCS Bulletin
Return to patterns.
Pattern inference.
Formal Principles of Language Acquisition.
Lange and Wiehagen's pattern language learning algorithm: An average-case analysis with respect to its total learning time
A guided tour across the boundaries of learning recursive languages.
--TR
A theory of the learnable
Systems that learn: an introduction to learning theory for cognitive and computer scientists
On the complexity of inductive inference
of pattern languages from examples and queries
A note on the two-variable pattern-finding problem
Deterministic simulation of idealized parallel computers on more realistic ones
Prudence and other conditions on formal language learning
A polynomial-time algorithm for learning <italic>k-</italic>variable pattern languages from examples
Polynomial-time inference of arbitrary pattern languages
Efficient PRAM simulation on a distributed memory machine
An introduction to parallel algorithms
Lange and Wiehagen?s pattern language learning algorithm
Queries and Concept Learning
Polynomial Time Inference of Extended Regular Pattern Languages
Inclusion is Undecidable for Pattern Languages
Polynomial Time Inference of General Pattern Languages
The Relation of Two Patterns with Comparable Languages
Pattern Inference
A Guided Tour Across the Boundaries of Learning Recursive Languages
Inductive Inference of Unbounded Unions of Pattern Languages from Positive Data
Monotonic and Nonmonotonic Inductive Inference of Functions and Patterns
Parallelism in random access machines

--CTR
John Case , Sanjay Jain , Rdiger Reischuk , Frank Stephan , Thomas Zeugmann, Learning a subclass of regular patterns in polynomial time, Theoretical Computer Science, v.364 n.1, p.115-131, 2 November 2006
Thomas Zeugmann, From learning in the limit to stochastic finite learning, Theoretical Computer Science, v.364 n.1, p.77-97, 2 November 2006
average-cae analysis;inductive learning;parallelization;one-variable pattern languages