Too Much Information Can be Too Much for Learning
Efficiently
Rolf Wiehagen∗Thomas Zeugmann

Humboldt–Universität

TH Darmstadt

Institut für Theoretische Informatik

Institut für Theoretische Informatik

PSF 1297

Alexanderstr. 10

O–1086 Berlin

W–6100 Darmstadt

wiehagen@hubinf.uucp

zeugmann@iti.informatik.th-darmstadt.de

Abstract
In designing learning algorithms it seems quite reasonable to construct them ina way such that all data the algorithm already has obtained are correctly and completely reflected in the description the algorithm outputs on these data. However,this approach may totally fail, i.e., it may lead to the unsolvability of the learning
problem, or it may exclude any efficient solution of it. In particular, we present anatural learning problem and prove that it can be solved in polynomial time if andonly if the algorithm is allowed to ignore data.

1. Introduction
The phenomenon of learning has attracted much attention of researchers in various
fields. When dealing with learning computer scientists are mainly interested in studying
the question whether or not learning problems may be solved algorithmically. Nowadays,
algorithmic learning theory is a rapidly emerging science (cf. Angluin and Smith (1983,
1987), Osherson, Stob and Weinstein (1986) and the references therein). Nevertheless, despite the enormous progress having been made since the pioneering papers of Solomonoff(1965) and of Gold (1965, 1967), there are still many problems that deserve special attention. The global question we shall deal with may be posed as follows: Are all data ofequal importance a learning algorithm is fed with?
First we study this question in the setting of inductive inference. Then we ask whether
the insight obtained may be important when one has to solve learning problems that are
somehow closer to potential applications. But let us explain all these things in some moredetail.
∗On leave at TH Darmstadt

1

One main problem of algorithmic learning theory consists in synthesizing ”global descriptions” for the objects to be learnt from examples. Thus, one goal is the following.
Let f be any computable function from N into N . Given more and more examples
f (0), f (1), ..., f (n), ... a learning strategy is required to produce a sequence of hypotheses
h0 , h1 , ..., hn , ... the limit of which is a correct global description of the function f , i.e.,a program that computes f . Since at any stage n of this learning process the strategy
knows exclusively the examples f (0), f (1), ..., f (n), it seems reasonable to construct the
hypothesis hn in a way such that for any x ≤ n the ”hypothesis function” g describedby hn is defined and computes the value f (x). Such a hypothesis is called consistent. In
other words, a hypothesis is consistent if and only if all information obtained so far about
the unknown object is completely and correctly encoded in this hypothesis. Otherwise,a hypothesis is said to be inconsistent. Consequently, if the hypothesis hn above is inconsistent, then there must be an x ≤ n such that g(x) 6= f (x). Note that there are two
possible reasons for g to differ from f on argument x; namely, g(x) may be not defined, orthe value g(x) is defined and does not equal f (x). Hence, if a hypothesis is inconsistentthen it is not only wrong at all but it is wrong on an argument for which the learning
strategy does already know the correct value. At first glance we are tempted to totally
exclude strategies producing inconsistent hypotheses ¿from our considerations. It mightseem that consistent strategies, i.e., strategies that produce always consistent hypotheses,
are the only reasonable learning devices.
Surprisingly enough this is a misleading impression. As it turns out, in a sense learning
seems to be the art of knowing what to overlook. Barzdin (1974) first announced that there
are classes of recursive functions that can be inferred in the limit but only by strategies
working inconsistently. This result directly yields the following questions:(1) Why does it make sense to output inconsistent hypotheses?
(2) What kind of data, if any, the strategy should overlook?
As we shall see below the first question finds its preliminary answer in the fact that,roughly speaking, there is no algorithm detecting whether or not a hypothesis is consistent. Consequently, in general a strategy has no chance to effectively verify the consistencyof its previous guess with the new data it has been fed with. On the other hand, a strategy
cannot overcome this drawback by simply searching any consistent hypothesis, since it
has to converge in the limit, too. Therefore, in order to be really successful, intuitively
speaking, a strategy cannot take care whether all the information it is provided with isactually correctly reflected by its current hypotheses. Answering the second question ismore complicated. However, an intuitively satisfying answer is provided by a characterization of identification in the limit in terms of computable numberings (cf. Wiehagen(1978b), Theorem 8). This theorem actually states that a class U of recursive functions
can be learnt in the limit iff there are a space of hypotheses containing for each function
at least one program, and a computable ”discrimination” function d such that for any two
programs i and j the value d(i, j) is an upper bound for an argument x on which program
i behaves different than program j does. The key observation used in constructing thestrategy that infers any function from U is the following. Let i be the strategy’s last guessand let f (0), ..., f (n) be the data now fed to it. If the strategy finds a program j suchthat for all inputs x ≤ d(i, j) its output equals f (x), then program i cannot be a correct2

one for function f . Then the strategy changes its mind from i to i + 1. In other words,
the strategy uses the data it receives for the purpose to find a proof for the incorrectnessof its actual hypothesis via some global property the space of all hypotheses possesses.
Summarizing the above discussion we see that the main reason for the superiority ofinconsistent strategies in the setting of inductive inference of recursive functions is causedby the undecidability of consistency. However, it remained open whether this phenomenon
is of fundamental epistemological importance but of almost no pratical relevance. Dealing
with the latter problem requires a different approach. It might be well conceivable thatconsistency is always decidable if one restricts itself to learning problems that are of interest with respect to potential applications. Consequently, the superiority of inconsistent
strategies in this setting, if any, can only be established in terms of complexity theory.
What we present in the sequel is a partial solution to this problem. As it turned out,
there are ”natural” learning problems having the following properties: First, consistency
is decidable, and second, they can be solved by a polynomial–time strategy if and only if
the strategy may work inconsistently.
Hence the inconsistency phenomenon does survive also in domains where consistency
is decidable. Moreover, the reason for the eventual superiority of inconsistent strategies
is in both settings in some sense the same. In both cases the learning algorithms cannot
handle the consistency problem. On the one hand this inability has been caused by theprovable absense of any algorithm solving it, while, on the other hand, the consistency
problem is computationally intractable, provided P 6= N P. As far as we know theresult above is the first one proving the existence of learning problems that cannot be
solved in polynomial time by any consistent strategy in a setting where consistency isdecidable. Moreover, in our opinion it strongly recommends to take seriously inconsistentlearning strategies into consideration. This requires both, the elaboration of ”intelligent”
inconsistent techniques as well as finding criteria with the help of which one can decide
whether or not inconsistent strategies are appropriate. The inconsistent technique wehave applied consists in overlooking or ignoring data unnecessary for the strategy in orderto fulfil its learning task. Of course, this might not be the only such technique.
The paper is structured as follows. Section 2 presents notation and definitions. Section
3 deals with the inconsistency phenomenon in the setting of inductive inference of recursivefunctions. The problem whether the inconsistency phenomenon is of any relevance inthe world of polynomial time computability is affirmatively exemplified in Section 4. In
Section 5 we discuss the results obtained and present open problems. All references are
given in Section 6.

2. Preliminaries
Unspecified notations follow Rogers (1967). N = {0, 1, 2, ...} denotes the set of all
natural numbers. The set of all finite sequences of natural numbers is denoted by N ∗ .
The classes of all partial recursive and recursive functions of one, two arguments over N
are denoted by P, P 2 , R, and R2 , respectively. R0,1 denotes the set of all 0 − 1 valued
recursive functions. Sometimes it will be suitable to identify a recursive function withthe sequence of its values, e.g., let α = (a0 , ..., ak ) ∈ N ∗ , j ∈ N, and p ∈ R0,1 ; then we3

write αjp to denote the function f for which f (x) = ax , if x ≤ k, f (k + 1) = j, andf (x) = p(x − k − 1), if x ≥ k + 2. Furthermore, let g ∈ P ; we write α < iff α is a prefix ofthe sequence of values associated with g, i.e., for any x ≤ k, g(x) is defined and g(x) = ax .
If U ⊆ R, then we denote by [U ] the set of all finite prefixes of functions from U .
Any function ψ ∈ P 2 is called a numbering. Moreover, let ψ ∈ P 2 , then we write ψiinstead of λxψ(i, x) and set Pψ = {ψi | i ∈ N } as well as Rψ = Pψ ∩ R. Consequently,
if f ∈ Pψ , then there is a number i such that f = ψi . A numbering ϕ ∈ P 2 is called aGödel numbering (cf. Rogers (1967)) iff Pϕ = P , and for any numbering ψ ∈ P 2 , there isa c ∈ R such that ψi = ϕc(i) for all i ∈ N . Göd denotes the set of all Gödel numberings.
Using a fixed encoding h...i of N ∗ onto N we write f n instead of h(f (o), ..., f (n))i, for
any n ∈ N, f ∈ R. Now we define some concepts of learning.
Definition 1. (Gold, 1965)
Let U ⊆ R and let ψ ∈ P 2 . The class U is said to be learnable in the limit with respect toψ iff there is a strategy S ∈ P such that for any function f ∈ U ,(1) for any n ∈ N , S(f n ) is defined,(2) there is a j ∈ N such that ψj = f and, for almost all n, S(f n ) = j.
If U is learnable in the limit with respect to ψ by strategy S we write U ∈ LIMψ (S). LetS
LIMψ = {U | U is learnable in the limit w.r.t. ψ}, and let LIM = ψ∈P 2 LIMψ .
Note that LIMϕ = LIM for any Gödel numbering ϕ. Next we formally define consistent learning.
Definition 2. (Barzdin, 1974)
Let U ⊆ R and let ψ ∈ P 2 . The class U is called consistently learnable in the limit withrespect to ψ iff there is a strategy S ∈ P such that
(1) U ∈ LIMψ (S)(2) ψS(f n ) (x) = f (x) for all n ∈ N and x ≤ n.
CON Sψ (S), CON Sψ and CON S are defined analogously as above.
Intuitively speaking, a consistent strategy does correctly reflect all the data it has
already seen. Note that CON Sϕ = CON S for any Gödel numbering ϕ. If a strategy
does not always work consistently, we call it inconsistent.

3. The Inconsistency Phenomenon
The inconsistency phenomenon has been discovered independently by Barzdin (1974)
and the Blums (1975). They observed that there are classes of recursive functions that are
inferrable in the limit but which cannot be learnt by any consistent strategy. Since both
papers do not contain a proof of this assertion, we present here a proof from Wiehagen(1976) actually showing a somewhat stronger result than the one formulated in the next
theorem. We shall discuss this issue below.
4Theorem 1. (Barzdin, 1974)
CON S ⊂ LIM
Proof. Let Uϕ = {f ∈ R | f = αjp, α ∈ N ∗ , j ≥ 2, p ∈ R0,1 , ϕj = f }, whereϕ ∈ Göd. Obviously, Uϕ ∈ LIM (S), where S(f n ) is equal to the last value f (x) ≥ 2 from(f (0), ..., f (n)) and 0, if no such value exists. For the purpose to prove that Uϕ ∈/ CON S
we need the following claim.
Claim: Let ϕ ∈ Göd. For any α ∈ N ∗ , there is a f ∈ Uϕ such that α < f .
Indeed, by an implicit use of the Recursion Theorem (cf. Rogers (1967)) it is easy to
see that for any α ∈ N ∗ and any p ∈ R0,1 there is a j ≥ 2 such that ϕj = αjp.
Now, suppose the converse, i.e., there is a strategy S ∈ P such that Uϕ ∈ CON Sϕ (S).
By the claim we get that S ∈ R and that for any α ∈ N ∗ , α < ϕS(α) . Thus, on any
α ∈ N ∗ , S always produces a consistent guess. Then, again by an implicit use of the
Recursion Theorem, let j ≥ 2 be any ϕ–number of the function f defined as follows:
f (0) = j, and for any n ∈ N ,(f (n + 1) =0 , if
1 , ifS(f n 0) 6= S(f n )S(f n 0) = S(f n ) andS(f n 1) 6= S(f n )In accordance with the claim and the assumption that S works consistently one straightforwardly verifies that S(f n 0) 6= S(f n ) or S(f n 1) 6= S(f n ) for any n ∈ N . Therefore
the function f is everywhere defined and we have f ∈ Uϕ . On the other hand, the strategy S changes its mind infinitely often when successively fed with f , a contradiction toUϕ ∈ CON Sϕ (S).
q.e.d.
Note that the class Uϕ from the proof of Theorem 1 is even iteratively learnable in thelimit. We call a class U of recursive functions iteratively learnable iff there is a strategy
that learns any f ∈ U as follows: In step n the strategy exclusively gets its previous guess
produced in step n − 1 as well as the new value f (n). By IT we denote the collection of allclasses U which can be learnt iteratively. In Wiehagen (1976) CON S ⊂ IT ⊂ LIM has
been proved. Recent papers give new evidence for the power of iterative learning (cf. e.g.
Porat and Feldman (1988), Lange and Wiehagen (1991), Lange and Zeugmann (1992)).
A closer look to the proof above shows that, in general, a strategy attempting toconsistently learn functions has to overcome two difficulties. First, it should avoid tochange too often its current guess that is eventually no longer consistent, to a definitely
consistent hypothesis, since this behavior may force the strategy to diverge. Second,
trusting that its current guess is consistent may eventually lead to an actually inconsistenthypothesis, since the strategy cannot effectively prove consistency. Indeed, it turns outthat a class U is consistently learnable iff there is a suitable space of hypotheses ψ suchthat the consistency problem restricted to U and ψ is effectively decidable. More precisely,let U ⊆ R and let ψ be any numbering. We say that U –consistency is decidable withrespect to ψ iff there is a predicate cons ∈ P 2 such that for any α < U and any i ∈ N ,cons(α, i) is defined and cons(α, i) = 1 if and only if α < ψi .
We say that consistency with respect to ψ is decidable iff there is a predicate cons ∈ R2
such that for any α ∈ N ∗ and for any i ∈ N , cons(α, i) = 1 if and only if α < ψi .
5

Theorem 2. U ∈ CON S iff there is a numbering ψ ∈ P 2 such that
(1) U ⊆ Pψ(2) U –consistency with respect to ψ is decidable.
Theorem 2 is a consequence of Theorem 9 from Wiehagen (1978b). Note that for an
arbitrary Gödel numbering, U -consistency is undecidable for any non–empty class U ⊆ R.
Furthermore, for many classes U ∈ CON S, the halting problem with respect to thenumbering ψ from Theorem 2 is undecidable. More exactly, let N U M = {U | U ⊆R and there is ψ ∈ R2 such that U ⊆ Pψ } denote the family of all classes of recursivefunctions that are contained in some recursively enumerable class of recursive functions.
Then we know that N U M ⊂ CON S (cf. Wiehagen (1976)). Furthermore, it turns outthat for any class U ∈/ N U M , there are only spaces of hypotheses ψ such that U ⊆ Pψ
implies the undecidabilty of the halting problem with respect to ψ (cf. Lemma 3 below).
Moreover, it is justified to call the latter property a ”bad” one, since conversely thedecidability of the halting problem easily implies the consistent learnability in the limitof all functions from Rψ with respect to ψ.
Lemma 3. Let U ⊆ R and let U ∈/ N U M . Then, for any numbering ψ ∈ P 2 satisfying
U ⊆ Pψ , the halting problem with respect to ψ is undecidable.
Proof. Let U ⊆ R and let U ∈/ N U M . Furthermore, let ψ ∈ P 2 be any numberingsuch that U ⊆ Pψ . Suppose, the halting problem with respect to ψ is decidable. Hence
there is a function h ∈ R2 such that for any i, x ∈ N , h(i, x) = 1 iff ψi (x) is defined. Thendefine a numbering ψ̃ by effectively filling out the ”gaps” in ψ as follows:(ψ̃i (x) =ψi (x) , if h(i, x) = 1
0 , otherwise

Obviously, for any i ∈ N , if ψi ∈ R then ψ̃i = ψi . Hence U ⊆ Pψ̃ . However, ψ̃ ∈ R2 andconsequently, U ⊆ Pψ̃ does imply U ∈ N U M , a contradiction.
q.e.d.
Therefore, Theorem 2 offers a possibility to compensate the undecidability of the halting problem with respect to ψ by the decidability of U –consistency. One can even showthat there are classes U ∈ CON S \N U M such that [U ] = N ∗ . By Theorem 2 and Lemma
3 this yields the existence of numberings ψ with undecidable halting problem and decidable consistency problem. Note that the latter assertion is a pure numbering theoreticalresult proved by learning theoretical observations (though it can also be proved directly).
Lemma 4. There is a class U ⊆ R such that
(1) U ∈ CON S(2) U ∈/ NUM
(3) [U ] = N ∗Sketch of proof. Let (ϕ, Φ) be any complexity measure (cf. Blum (1967)). We modify
Φ to Φ̂ in a way such that6

1. (ϕ, Φ̂) is again a complexity measure,
2. for any α ∈ N ∗ , there is an i ∈ N such that ϕi ∈ R and α < Φ̂i .
Now let U = {Φ̂i | ϕi ∈ R}. Then U ∈ CON SΦ̂ , since for any i, x, y ∈ N the predicate”Φ̂i (x) = y” is uniformly decidable. Furthermore, U ∈/ N U M , since otherwise R ∈ N U M .
∗Finally, [U ] = N by construction.
q.e.d.
Corollary 5. There is a numbering ψ with [Rψ ] = N ∗ such that
(1) The halting problem with respect to ψ is undecidable.
(2) The consistency problem with respect to ψ is decidable.
Proof. Let U ⊆ R be a class in accordance with Lemma 4. Furthermore, let ψ be anumbering chosen accordingly to Theorem 2. Then (1) is an immediate consequence ofLemma 3, and (2) follows from Theorem 2, assertion (2), taking into account that, byconstruction, [Rψ ] = N ∗ .
q.e.d.
Finally in this section we want to point out that a natural weakening of consistency
does not suffice to learn any class inferrable in the limit.
Definition 3. (Wiehagen, 1978a)
Let U ∈ R, ψ ∈ P 2 . U is called conformly learnable in the limit with respect to ψ iff there
is a strategy S ∈ P such that
(1) U ∈ LIMψ (S),(2) for any function f ∈ U , any n, x ∈ N such that x ≤ n, either ψS(f n ) (x) = f (x) orψS(f n ) (x) is not defined.
Intuitively speaking, a conform strategy is never allowed to output a hypothesis thatindeed computes a wrong value at an argument x which is less than the length of theinitial segment seen so far. By CON Fψ we denote the collection of classes U ⊆ R thatare conformly identifiable with respect to ψ. Finally, let CON F denote the union of all
families CON Fψ where ψ ∈ P 2 . The following theorem is due to Wiehagen (1978a).
Theorem 6.
CON S ⊂ CON F ⊂ LIM
The reader is encouraged to consult Jantke and Beick (1981), Zeugmann (1983) andFulk (1989) for further investigation concerning consistent and conform identification.

4. Inconsistency and Polynomial TimeThe results presented in the previous section may lead to the impression that the inconsistency phenomenon may be far beyond any practical relevance, since it has been7

established in a setting where both, the halting and the consistency problem are undecidable in general. Therefore now we ask whether the inconsistency phenomenon does survive
in more realistic settings, i.e., in settings where consistency is decidable. Moreover, in order to be consequently realistic we additionally restrict ourselves to deal exclusively withlearning strategies that are polynomial time computable. Then, of course, the superiority
of inconsistent strategies, if any, has to be established in terms of complexity theory. We
present a learning problem in a realistic setting which is generally consistently solvable
but which cannot be solved consistently in polynomial time, unless P =6 N P. The desired
goal is achieved by elaborating an algorithm inconsistently solving the same learning problem in polynomial time. As far as we know this is the first learning problem for which
the announced properties are rigorously proved. In our opinion, this result gives strong
evidence of taking seriously inconsistent learning strategies into consideration.
The setting we want to deal with is the learnability of pattern languages introduced by
Angluin (1980). Subsequently, Shinohara (1982) dealt with polynomial time learnabilityof subclasses of pattern languages. Nix (1983) outlined interesting applications of patterninference algorithms. Recently, Kearns and Pitt (1989) as well as Ko, Marron and Tzeng(1990) studied intensively the learnabilty of pattern languages in the PAC–learning model.
So let us define what are a pattern and a pattern language. Let Σ = {a, b, ..} be any
non–empty finite alphabet containing at least two elements. Furthermore, let X = {xi |i ∈ N } be an infinite set of variables such that Σ∩X = ∅. Patterns are non–empty strings
from Σ ∪ X, e.g., ab, ax1 ccc, bx1 x1 cx2 x2 are patterns. L(p), the language generated bypattern p is the set of strings which can be obtained by substituting non–null strings fromΣ∗ for the variables of the pattern p. Thus aabbb is generable from pattern ax1 x2 b, while
aabba is not. P at and P AT denote the set of all patterns and of all pattern languagues,
respectively. In order to deal with the learnability of pattern languages we have to specify
from what information the learning strategies should do their task. Following Gold (1967)
we distinguish between learning from text and from informant. Formally, let L ⊆ Σ∗ ; wecall a mapping I : N → Σ∗ × {+, −} informant of L iff(1) For any w ∈ Σ∗ , there are an n ∈ N and λ ∈ {+, −} such that I(n) = (w, λ).
(2) For any n ∈ N, w ∈ Σ∗ , and λ ∈ {+, −}, if I(n) = (w, λ) then w ∈ L iff λ = +.
Let Info(L) denote the set of all informants of L. Furthermore, for I ∈ Info(L) and n ∈ N
let I n = cod(I(0), ..., I(n)), where cod denotes an effective and bijective mapping fromthe set of all finite sequences of elements from Σ∗ × {+, −} onto N . Finally, we set In ={w ∈ Σ∗ | there are i ≤ n, λ ∈ {+, −}s.t. I(n) = (w, λ)}, and In+ = In ∩ L, In− = In \ In+ .
Any mapping T from N onto L is called a text for L. By Text(L) we denote the set of
all texts for L. The sets Tn , Tn+ as well as Tn− are defined analogously as above.
Intuitively, a text for L generates the language L– without any information concerning
the complement of L, whereas an informant of L decides L by informing the strategy
whether or not any word from Σ∗ belongs to L. Note that we allow a text and an
informant to be non–effective.
Definition 4. P AT is called learnable in the limit from informant (abbr. P AT ∈LIM − IN F ) iff there is an effective strategy S from N into P at such that for any
8L ∈ P AT and any I ∈ Info(L),(1) for any n ∈ N , S(I n ) is defined, and(2) there is a p ∈ P AT such that L(p) = L and for almost all n ∈ N , S(I n ) = p.
Definition 5. P AT is called consistently learnable in the limit from informant (abbr.
P AT ∈ CON S − IN F ) iff there is an effective strategy S from N into P at such that
(1) P AT ∈ LIM − IN F by S
(2) for any L ∈ P AT , I ∈ Info(L) and n ∈ N , In+ ⊆ L(S(I n )) and In− ∩ L(S(I n )) = ∅.
Note that a consistent learning strategy is required to correctly reflect both, the positive as well as the negative data it has already seen. Next we sharpen Definition 5 byadditionally requiring polynomial time computability of S.
Definition 6. P AT is called (consistently) learnable in the limit ¿from informant inpolynomial time (abbr. P AT ∈ Poly − LIM − IN F (P AT ∈ Poly − CON S − IN F )) iff
there are a strategy S and a polynomial pol such that
(1) P AT ∈ LIM − IN F (P AT ∈ CON S − IN F ) by S, and(2) for any L ∈ P AT, I ∈ Info(L) and any n ∈ N , time to compute S(I n ) ≤pol(length(I n )).
Learning from text is analogously defined in replacing everywhere ”informant” by”text”. However, one point should be stated more precisely, i.e., consistent learning on
text does only require consistency with the data contained in the text. In order to havean example illuminating the difference we could define a strategy that initially outputs x1 .
Since L(x1 ) contains any string over Σ but the empty one, this hypothesis is consistent on
text for any finite input. However, since the strategy has to converge, it cannot maintainthis hypothesis ad infinitum. Finally, we use LIM − T XT , CON S − T XT as well as
P oly − CON S − T XT to denote the corresponding learning types on text.
Now we can precisely state the result mentioned above.
Theorem 7.
(1) P AT ∈ CON S − IN F
(2) If P =6 N P, then P AT ∈/ P oly − CON S − IN F .
(3) P AT ∈ Poly − LIM − IN F
Sketch of proof. Assertion (1) is proved in applying Gold’s (1967) enumeration technique. Therefore, let (pi )i∈N be any fixed effective enumeration of P at. Let L ∈ P AT ,let I ∈ Info(L) be any informant, and let n ∈ N . Define S(I n ) to be the first pattern pin the enumeration of P at satisfying In+ ⊆ L(p) and In− ∩ L(p) = ∅. Since membershipfor pattern languages is uniformly decidable (cf. Angluin (1980)), S is computable. Due
9to the definition of S, consistency is obvious. Moreover, the strategy converges to thefirst pattern in the enumeration that generates the language L to be learnt. Note that S
cannot be computed in polynomial time, unless P = N P, since membership for patternlanguages is N P–complete (cf. Angluin (1980)).
Next we have to show that there is no strategy at all consistently learning P AT that iscomputable in polynomial time, if P =6 N P. This part of the proof is done by showing the
N P–hardness of an appropriate problem defined below. For any information concerning
reducibility as well as N P–complete problems the reader is referred to Garey and Johnson(1979). First we define the following decision problem SEP . Let W + , W − ⊆ Σ∗ . We saythat W + , W − are separable iff there is a pattern p such that W + ⊆ L(p) and W − ∩L(p) =∅. SEP denotes the problem of deciding whether any W + , W − ⊆ Σ∗ are separable.
Moreover, by CSEP we denote the problem of constructing a separating pattern p forany given W + , W − that are separable. The proof of assertion (2) is completed via thefollowing lemmata.
Lemma A. (Ko, Marron, Tzeng, 1990)
3 − SAT is polynomial time reducible to SEP .
Lemma B. CSEP is N P–hard.
Proof of Lemma B. Let C3 − SAT denote the problem to construct a satisfying assignment to any satisfiable instance from 3 − SAT .
Claim 1. C3 − SAT ∈ P implies 3 − SAT ∈ P
Assume there is an algorithm A having a running time that is bounded by somepolynomial pol in the length of its input, and that, moreover, on input C returns asatisfying assignment of C, if C is satisfiable. Now let C be any instance of 3 − SAT .
Start A on input C. Since any polynomial is time constructable, we we may combine
A with a clock, i.e., we can efficiently stop A on input C after at most length(C) stepsof computation. Then two cases are possible. Either A returns nothing. Consequently,
C cannot be satisfiable. Otherwise A outputs an assignment ass within the given timebound. Then one can check in polynomial time whether or not ass indeed satisfies C. In
case it does, we know that C is satisfiable. In case it does not C is again not satisfiable,
since otherwise A fails.
Note that we cannot prove the N P–hardness of CSEP in the same manner as inshowing claim 1, since membership for pattern languages is N P–complete, i.e., one cannot
check in polynomial time whether a pattern eventually returned on input (W + , W − ) does
indeed separate these sets. However, we overcome this difficulty in showing the following
claim.
Claim 2. CSEP ∈ P implies C3 − SAT ∈ P
In accordance with Lemma A let red be any polynomial time reduction of 3 − SAT
to SEP . Suppose, there is an algorithm B solving CSEP in polynomial time. Now let
C be any satisfiable instance of 3 − SAT . The wanted satisfying assignment may becomputed as follows. First, compute red(C) = (W + , W − ). Since C is satisfiable, we getthat (W + , W − ) are separable. Next compute p = B(W + , W − ). Finally, let ass be theassignment contructed to p in the proof of the ”only–if” direction of Lemma A. Since
red is computable in time bounded by a polynomial in the length of C, the length of10

(W + , W − ) is bounded by a polynomial in the length of C, too. Consequently, ass ispolynomial time computable. Hence, C3 − SAT ∈ P, if CSEP ∈ P.
Finally, Claim 1 and 2 directly yield Lemma B.
The proof of assertion (2) is completed by showing the next claim.
Claim 3. P AT ∈ Poly − CON S − IN F implies CSEP ∈ P.
Suppose P AT ∈ Poly − CON S − IN F by some strategy S. Let W + , W − be any
two separable sets, and let p be any pattern separating them. Let I ∈ Info(L(p)) be an
arbitrary informant such that, for some n, In+ = W + and In− = W − . In accordance withthe definition of separabilty, I obviously exists. Consequently, S(I n ) has to be defined,
and furthermore, q = S(I n ) has to be a pattern separating W + , W − , too. Finally, S ispolynomial time computable. Hence we get CSEP ∈ P.
It remains to prove assertion (3). In Lange and Wiehagen (1991) P AT ∈ Poly −LIM −T XT has been shown. The corresponding strategy witnessing P AT ∈ Poly −LIM −T XTworks by ”overlooking” data, i.e., it ignores all but the actually shortest strings of thelanguage to be learnt. It turns out that sufficiently many really shortest strings of apattern language do suffice to learn it. From these remaining strings a hypothesis is
generated in time that is even polynomial in the length of these strings. However, it ismost of the time inconsistent, while being correct in the limit. Let S denote the strategy
from Lange and Wiehagen (1991) proving P AT ∈ Poly − LIM − T XT . We define astrategy S̃ witnessing P AT ∈ Poly − LIM − IN F as follws: On any input I n we set
S̃(I n ) = S(In+ ). This proves the theorem.
Note that S̃ even works semi–consistently, since In− ∩ L(S̃(I n )) = ∅ is valid for alln ∈ N . Moreover, S̃ works iteratively as S does.
q.e.d.
At this point some remarks are mandatory. It should be mentioned that any consistent strategy S, independently of how complex it is, may be trivially converted into aninconsistent one that works in quadratic time. This is done as follows. On input I n , one
simulates S on input I 1 , I 2 ,...,I n no more than n steps, and outputs S(I k ), where k is thelargest number y ≤ n for which S(I y ) is computable within at most n steps.
However, it is obvious that this simulation technique does not yield any advantage. It
does neither increase the efficiency of the learning algorithm, if one sums up all steps ofcomputation until the learning task is successfully solved; nor does it enlarge the learning
power. What we are looking for are ”intelligent” inconsistent techniques. In our opinion, Lange and Wiehagen’s (1991) refined strategy behaves thus by the following reasons.
First, it avoids membership tests at all. Second, it computes its current hypothesis iteratively. Third, the test whether or not it should eventually change its mind is extremely
simple and may be executed in linear time. Moreover, the algorithm yielding an eventually
new hypothesis performs exclusively syntactical or formal manipulations over strings.
Finally, let Poly − CON S − LEXIN F (Poly − CON S − LEXT XT ) be the learning
type obtained from Poly − CON S − IN F ( Poly − CON S − T XT ) by restricting theinformation presentation from any informant I ∈ Info(L) (any text T ∈ Text(L)) to thelexicographically ordered one (cf. Definition 6). Furthermore, let S be a strategy suchthat P AT ∈ LIM − IN F (LIM − T XT ) by S. Then, for any L ∈ P AT and D ∈ Info(L)11∪ Text(L), letConv(S, D) = the least number m such that for all n ≥ m, S(Dn ) = S(Dm )denote the stage of convergence of S on D.
We have been surprised to obtain the following theorem. It actually states that theinconsistent learning strategy of Lange and Wiehagen (1991) may behave both, i.e., consistently and efficiently, if it receives the crucial information on the language to be learnt
in an appropriate order.
Theorem 8(1) There are a strategy S̃ and a polynomial pol such that(i) P AT ∈ Poly − CON S − LEXIN F by S̃,(ii) for any p ∈ P at, there is an Ip ∈ Info(L(p)) such that– S̃ works consistently on Ip ,Conv(S,Ip )– Σn=0time to compute S̃(Ipn ) ≤ pol(length(p)).

(2) There are a strategy S and a polynomial pol such that(i) P AT ∈ Poly − CON S − LEXT XT by S,(ii) for any p ∈ P at, there is a Tp ∈ Text(L(p)) such that
– S works consistently on Tp ,Conv(S,Tp )– Σn=0time to compute S(Tpn )) ≤ pol(length(p)).

Sketch of proof. Assertion (1), part (i) is proved using the strategy S̃ from the proof of
Theorem 7, assertion (3) above. Then part (i) follows by Lemma 2 of Lange and Wiehagen(1991). Part (ii) directly follows from Theorem 2, assertion (3) of Lange and Wiehagen(1991).
The first part of assertion (2) is an immediate consequence of the proof of Theorem 1
in Lange and Wiehagen (1991), while the second follows as above.
q.e.d.
We conjecture that Theorem 7 remains valid for CON S − T XT . Assertion (1) has
been proved by Angluin (1980). As already mentioned above, the strategy from Lange
and Wiehagen (1991) directly yields (3). Consequently, the only part not yet proved is(2). One reason why (2) seems to be easier provable for informant than for text is thefollowing. A strategy working consistently on informant has to work ”hard” at any stepof the learning process, while a consistent strategy on text may output x1 for a while.

5. Conclusions
We have investigated the problem of consistent versus inconsistent learning. In spite of
the remarkable power of consistent learning it turns out that this power is not universal.
12There are learning problems which can be exclusively solved by inconsistent strategies,
i.e., by strategies that do temporarily incorrectly reflect the behavior of the unknown
object on data for which the correct behavior of the object is already known at thecurrent stage of the learning process. This phenomenon has been investigated in a ”highly
theoretical” setting, namely in inductive inference of recursive functions. In this setting
the seemingly senseless work of inconsistent strategies could be completely explained by
the undecidability of consistency.
However, it turned out that the inconsistency phenomenon is also valid in more realistic
situations, namely in domains where consistency is always decidable and the learning
strategies have to work in polynomial time. The reason is quite anologous to that in
the setting of arbitrary recursive functions. Providing P =6 N P, the N P-hardness ofproblems can prevent learning strategies to produce consistent hypotheses in polynomial
time.
Moreover, we conjecture that an analogous effect can be shown for incremental learningof finite classes of finite objects such as Boolean functions.
In any case, we regard the results obtained as giving strong evidence to take fast
inconsistent strategies seriously into account.
Finally, the presented results do suggest directions of further research such as
1. finding fast inconsistent learning techniques
2. deriving conditions yielding that a given learning problem has no fast consistentsolution, but a fast inconsistent one.
Acknowledgement
Substantial part of this work has been performed while the first author was visiting
TH Darmstadt. He is grateful indebted to Rüdiger Reischuk and Wolfgang Bibel for
providing inspiring working conditions.
Furthermore, both authors would like to acknowledge fruitful discussions with Andreas
Jakoby and Christian Schindelhauer.

6. References[1] Angluin, D., (1980), Finding Patterns Common to a Set of Strings, Journal ofComputer and System Sciences 21, 46 - 62
[2] Angluin, D. and C.H. Smith, (1983), Inductive Inference: Theory and Methods,
Computing Surveys 15, 3, 237 - 269[3] Angluin, D. and C.H. Smith, (1987), Formal Inductive Inference, In Encyclopedia ofArtificial Intelligence, St.C. Shapiro (Ed.), Vol. 1, pp. 409 - 418, Wiley-Interscience
Publication, New York
[4] Barzdin, Ya.M., (1974), Inductive Inference of Automata, Functions and Programs,
Proc. Int. Congress of Math., Vancouver, pp. 455 - 460
13

[5] Blum, M., (1967), Machine Independent Theory of Complexity of Recursive Functions, Journal of the ACM 14, 322 -336
[6] Blum, L. and M. Blum, (1975), Toward a Mathematical Theory of Inductive Inference, Information and Control 28, 122 - 155[7] Fulk, M.,(1988), Saving the Phenomena: Requirements that Inductive Inference
Machines Not Contradict Known Data, Information and Computation 79, 193 - 209[8] Garey, M.R. and D.S. Johnson, (1979), Computers and Intractability, A Guide to
the Theory of N P–completness, Freeman and Company, San Francisco[9] Gold, M.E., (1965), Limiting Recursion, Journal of Symbolic Logic 30, 28 - 48
[10] Gold, M.E., (1967), Language Identification in the Limit, Information and Control
10, 447 - 474[11] Jantke, K.P. and H.R. Beick, (1981), Combining Postulates of Naturalness in Inductive Inference, Journal of Information Processing and Cybernetics (EIK) 17, 465- 484[12] Kearns, M. and L. Pitt, (1989), A Polynomial–time Algorithm for Learning k–variable Pattern Languages From Examples. In Proc. 2nd Annual Workshop on
Computational Learning Theory, R. Rivest, D. Haussler, and M.K. Warmuth (Eds.),
pp. 57 - 70, Morgan Kaufmann Publishers Inc.
[13] Ko, Ker–I, Marron, A. and W.G. Tzeng, (1990), Learning String Patterns and Tree
Patterns From Examples, Proc. 7th Conference on Machine Learning, pp. 384 391[14] Lange, S. and R. Wiehagen, (1991), Polynomial–Time Inference of Arbitrary Pattern
Languages, New Generation Computing 8, 361 - 370[15] Lange, S. and T. Zeugmann, (1991), Monotonic versus Non-monotonic Language
Learning, in Proc. 2nd International Workshop on Nonmonotonic and Inductive
Logic, December 1991, Reinhardsbrunn, to appear in Lecture Notes in Artificial
Intelligence[16] Lange, S. and T. Zeugmann, (1992), Types of Monotonic Language Learning and
Their Characterization, Proc. 5th Annual Workshop on Computational Learning
Theory, Morgan Kaufmann Publishers Inc.
[17] Nix, R.P., (1983), Editing by Examples, Yale University, Dept. Computer Science,
Technical Report 280[18] Osherson, D., Stob, M. and S. Weinstein, (1986), Systems that Learn. An Introduction to Learning Theory for Cognitive and Computer Scientists, MIT-Press,
Cambridge, Massachusetts14[19] Porat, S. and J.A. Feldman, (1988), Learning Automata from Ordered Examples,in Proc. First Workshop on Computational Learning Theory, D. Haussler and L.
Pitt (Eds.), pp. 386 - 396, Morgan Kaufmann Publishers Inc.
[20] Rogers, H.Jr., (1967), Theory of Recursive Functions and Effective Computability,
Mc Graw–Hill, New York[21] Shinohara, T., (1982), Polynomial Time Inference of Extended Regular Pattern
Languages, RIMS Symposia on Software Science and Engineering, Kyoto, Lecture
Notes in Computer Science 147, pp. 115 - 127, Springer–Verlag[22] Solomonoff, R., (1964), A Formal Theory of Inductive Inference, Information andControl 7, 1 - 22, 234 - 254[23] Wiehagen, R., (1976), Limes–Erkennung rekursiver Funktionen durch spezielle Strategien, Journal of Information Processing and Cybernetics (EIK) 12, 93 - 99[24] Wiehagen, R., (1978a), Zur Theorie der algorithmischen Erkennung, Dissertation
B, Humboldt–Universität zu Berlin[25] Wiehagen, R., (1978b), Characterization Problems in the Theory of Inductive Inference, Proc. 5th Colloquium on Automata, Languages and Programming, Udine,
July 17 - 21, G. Ausiello and C. Böhm (Eds.), Lecture Notes in Computer Science62, pp. 494 - 508, Springer-Verlag[26] Zeugmann, T., (1983), A–posteriori Characterizations in Inductive Inference of Recursive Functions, Journal of Information Processing and Cybernetics (EIK) 19, 559- 594

15