Ignoring Data May be the Only Way to Learn
Eciently
Prof. Dr. Rolf Wiehagen

Dr. Thomas Zeugmann

University of Kaiserslautern

TH Darmstadt

Department of Computer Science

Institut fur Theoretische Informatik

P.O. Box 3049

Alexanderstr. 1067653 Kaiserslautern64283 Darmstadt

wiehagen@informatik.uni-kl.dezeugmann@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 re ected in the hypothesis 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 ecient 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
elds. 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 Solomono(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. We now want to explain this in some moredetail.
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 IN into IN. 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 de ned 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 di er from f on argument x; namely, g(x) may be not de ned, orthe value g(x) is de ned 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 rst glance we are tempted to totally2

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) rst announced that there
are classes of recursive functions that can be learnt 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 rst question nds 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 e ectively 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 re ected by its current hypotheses. Answering the second question ismore complicated. However, an intuitively satisfying answer is provided by a characterization of identi cation 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 i 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 di erent 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 nds a program j suchthat for all inputs x  d(i; j ) its output equals f (x), then program i cannot be a correct
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 nd a proof for the possible
incorrectness of its actual hypothesis via some global property the space of all hypotheses
possesses.
3Summarizing the above discussion we see that the main reason for the superiority
of inconsistent strategies in the setting of inductive inference of recursive functions iscaused by the undecidability of consistency. However, it remained open whether thisphenomenon is of fundamental epistemological importance but of almost no practicalrelevance. Dealing with the latter problem requires a di erent approach. It might bewell conceivable that consistency is always decidable if one restricts itself to learning
problems that are of interest with respect to potential applications. Consequently, thesuperiority of inconsistent strategies in this setting, if any, can only be established interms of complexity theory. What we present in the sequel is a partial solution to thisproblem. As it turned out, there are \natural" learning problems having the following
properties: Though consistency is decidable, they can be solved by a polynomial{timestrategy 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 absence of any algorithm solving it, while, on the other hand, the consistency
problem is computationally intractable, provided P 6= NP .
As far as we know the result above is the rst one proving the existence of learning
problems that cannot be solved in polynomial time by any consistent strategy in a setting
where consistency is decidable. Moreover, in our opinion it strongly recommends to takeseriously inconsistent learning strategies into consideration. This requires both, the elaboration of \intelligent" inconsistent techniques as well as nding criteria with the help of
which one can decide whether or not inconsistent strategies are appropriate. The inconsistent technique we have applied consists in overlooking or ignoring data unnecessary forthe strategy in order to ful l its learning task. Of course, this might not be the only suchtechnique.
The paper is structured as follows. Section 2 presents notation and de nitions. 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 armatively exempli ed in Section 4. In
4Section 5 we discuss the results obtained and present open problems. All references are
given in Section 6.
2. Preliminaries

Unspeci ed notations follow Rogers (1967). IN = f0; 1; 2; :::g denotes the set of all
natural numbers. The set of all nite sequences of natural numbers is denoted by IN3 .
The classes of all partial recursive and recursive functions of one, two arguments over IN
are denoted by P; P 2; R; and R2 , respectively. R0;1 denotes the set of all 0 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 ) 2 IN3 ; j 2 IN; and p 2 R0;1; then we
write jp to denote the function f for which f (x) = ax, if x  k, f (k + 1) = j , andf (x) = p(x 0 k 0 2), if x  k + 2. Furthermore, let g 2 P and 2 IN3 ; we write < g
i is a pre x of the sequence of values associated with g, i.e., for any x  k, g(x) isde ned and g(x) = ax. If U  R, then we denote by [U ] the set of all nite pre xes offunctions from U .
Any function 2 P 2 is called a numbering. Moreover, let 2 P 2 , then we write iinstead of x (i; x) and set P = f i j i 2 INg as well as R = P \ R. Consequently,
if f 2 P , then there is a number i such that f = i. A numbering ' 2 P 2 is called aGodel numbering (cf. Rogers (1967)) i P' = P , and for any numbering 2 P 2 , there isa c 2 R such that i = 'c(i) for all i 2 IN. God denotes the set of all Godel numberings.
Using a xed encoding h:::i of IN3 onto IN we write f n instead of h(f (o); :::; f (n))i, for
any n 2 IN; f 2 R. Now we de ne some concepts of learning.
De nition 1. (Gold, 1965)
Let U  R and let 2 P 2 . The class U is said to be learnable in the limit with respect toi there is a strategy S 2 P such that for any function f 2 U ,(1) for any n 2 IN, S (f n ) is de ned,
(2) there is a j 2 IN such thatnj = f and, for almost all n, S (f ) = j .

If U is learnable in the limit with respect to by strategy S we write U 2 LIM (S ). LetS
LIM = fU j U is learnable in the limit w:r:t: g, and let LIM = 2P 2 LIM .

5

Note that LIM' = LIM for any Godel numbering '. Next we formally de ne consistent learning.
De nition 2. (Barzdin, 1974)
Let U  R and let 2 P 2 . The class U is called consistently learnable in the limit withrespect to i there is a strategy S 2 P such that
(1) U 2 LIM (S )(2)

S (f n ) (x) = f (x) for any f

2 U , n 2 IN and x  n.

CONS (S ); CONS and CONS are de ned analogously as above.

Intuitively, a consistent strategy does correctly re ect all the data it has already seen.
Note that CONS' = CONS for any Godel 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
inferable 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.
Theorem 1. (Barzdin, 1974)
CONS  LIM
Proof. Let U' = ff 2 R j f = jp; 2 IN3 ; j  2; p 2 R0;1 ; 'j = f g, where' 2 God. Obviously, U' 2 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' 2= CONS

we need the following claim.

Claim: Let ' 2 God. For any

2 IN3 , there is an f 2 U' such that < f .

Indeed, by an implicit use of the Recursion Theorem (cf. Rogers (1967)) it is easy to
see that for any 2 IN3 and any p 2 R0;1 there is a j  2 such that 'j = jp.
6

Now, suppose the converse, i.e., there is a strategy S 2 P such that U' 2 CONS'(S ).
By the claim we get that S 2 R and that for any 2 IN3 , < 'S( ). Thus, on any
2 IN3 , 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 de ned as follows:
f (0) = j , and for any n 2 IN,

8< 0 ; if S (f n0) 6= S (f n)f (n + 1) =: 1 ; if S (f n0) = S (f n) and S(f n1) 6= S (f n)

In accordance with the claim and the assumption that S works consistently one
straightforwardly veri es that S (f n0) 6= S (f n ) or S (f n 1) 6= S (f n) for any n 2 IN. Therefore the function f is everywhere de ned and we have f 2 U'. On the other hand, thestrategy S changes its mind in nitely often when successively fed with f , a contradiction
to U' 2 CONS'(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 i there is a strategy
that learns any f 2 U as follows: In step n the strategy exclusively gets its previous guess
produced in step n 0 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) CONS  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 diculties. First, it should avoid tochange too often its current guess that is eventually no longer consistent, to a de nitely
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 e ectively prove consistency. Indeed, it turns outthat a class U is consistently learnable i there is a suitable space of hypotheses suchthat the consistency problem restricted to U and is e ectively decidable. More precisely,let U  R and let be any numbering. We say that U {consistency is decidable withrespect to i there is a predicate cons 2 P 2 such that for any 2 [U ] and any i 2 IN,
cons( ; i) is de ned and cons( ; i) = 1 if and only if < i .
7

We say that consistency with respect to is decidable i there is a predicate cons 2 R2such that for any 2 IN3 and for any i 2 IN, cons( ; i) = 1 if and only if < i.
Theorem 2. U 2 CONS i there is a numbering

2 P 2 such that

(1) U  P
(2) U {consistency with respect tois decidable.

Theorem 2 is a consequence of Theorem 9 from Wiehagen (1978b). Note that for an
arbitrary Godel numbering, U -consistency is undecidable for any non{empty class U  R.
Furthermore, for many classes U 2 CONS , the halting problem with respect to thenumbering from Theorem 2 is undecidable. More exactly, let NUM = fU j U 
R and there is 2 R2 such that U  P g denote the family of all classes of recursivefunctions that are contained in some recursively enumerable class of recursive functions.
Then we know that NUM  CONS (cf. Wiehagen (1976)). Furthermore, it turns outthat for any class U 2= NUM , there are only spaces of hypotheses such that U  P
implies the undecidability of the halting problem with respect to (cf. Lemma 3 below).
Moreover, it is justi ed 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 2= NUM . Then, for any numberingU  P , the halting problem with respect to is undecidable.

2 P 2 satisfying

Proof. Let U  R and let U 2= NUM . Furthermore, let 2 P 2 be any numberingsuch that U  P . Suppose, the halting problem with respect to is decidable. Hence
there is a function h 2 R2 such that for any i; x 2 IN, h(i; x) = 1 i i(x) is de ned. Thende ne a numbering ~ by e ectively lling out the \gaps" in as follows:8< i(x) ; if h(i; x) = 1~i(x) =
: 0 ; otherwise

Obviously, for any i 2 IN, if i 2 R then ~i = i. Hence U  P ~. However, ~ 2 R2 andconsequently, U  P ~ does imply U 2 NUM , a contradiction.
q.e.d.
8

Therefore, Theorem 2 o ers 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 2 CONS n NUM such that [U ] = IN3 . 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 2 CONS
(2) U 2= NUM(3) [U ] = IN3
Sketch of proof. Let ('; 8) be any complexity measure (cf. Blum (1967)). We modify

8 to 8^ in a way such that

1. ('; 8^ ) is again a complexity measure,
2. for any 2 IN3 , there is an i 2 IN such that 'i 2 R and < 8^ i.
Now let U = f8^ i j 'i 2 Rg. Then U 2 CONS8^ , since for any i; x; y 2 IN the predicate\8^ i (x) = y" is uniformly decidable. Furthermore, U 2= NUM , since otherwise R 2 NUM .
Finally, [U ] = IN3 by construction.
q.e.d.
Corollary 5. There is a numberingwith [R ] = IN3 such that

(1) The halting problem with respect tois undecidable.

(2) The consistency problem with respect tois 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 ] = IN3.
q.e.d.
9Finally in this section we want to point out that a natural weakening of consistency
does not suce to learn any class inferable in the limit.
De nition 3. (Wiehagen, 1978a)
Let U 2 R; 2 P 2 . U is called conformly learnable in the limit with respect tois a strategy S 2 P such thati there(1) U 2 LIM (S ),(2) for any function f 2 U and any n; x 2 IN such that x  n, either
or S (f n ) (x) is not de ned.

S (f n ) (x) = f (x)Intuitively, a conform strategy is never allowed to output a hypothesis that indeed
computes a wrong value at an argument x which is less than the length of the initial
segment seen so far. By CONF we denote the collection of classes U  R that are
conformly identi able with respect to . Finally, let CONF denote the union of all
families CONF where 2 P 2. The following theorem is due to Wiehagen (1978a).
Theorem 6.
CONS  CONF  LIM

The reader is encouraged to consult Jantke and Beick (1981), Zeugmann (1983) andFulk (1989) for further investigation concerning consistent and conform identi cation.
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 been
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
10

goal is achieved by elaborating an algorithm inconsistently solving the same learning problem in polynomial time. As far as we know this is the rst 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, Jantke (1991) and Lange and Zeugmann (1993) dealt
with the learnability of pattern languages under monotonicity constraints. Moreover,Kearns and Pitt (1989) as well as Ko, Marron and Tzeng (1990) intensively studied thelearnability of pattern languages in the PAC{learning model.
So let us de ne what are a pattern and a pattern language. Let 6 = fa; b; ::g be anynon{empty nite alphabet containing at least two elements. Furthermore, let X = fxi j
i 2 INg be an in nite set of variables such that 6 \ X = ;. Patterns are non{empty strings
from 6 [ X , e.g., ab; ax1 ccc; bx1 x1cx2 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
63 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 languages
over 6, respectively. In order to deal with the learnability of pattern languages we haveto 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  63; we call a mapping I : IN ! 63 2 f+; 0g informant of L i(1) For any w 2 63, there are an n 2 IN and  2 f+; 0g such that I (n) = (w; ).
(2) For any n 2 IN; w 2 63 ; and  2 f+; 0g, if I (n) = (w; ) then w 2 L i  = +.
Let Info(L) denote the set of all informants of L. Furthermore, for I 2 Info(L) and n 2 IN,
let I n = cod(I (0); :::; I (n)), where cod denotes an e ective and bijective mapping fromthe set of all nite sequences of elements from 63 2 f+; 0g onto IN. Finally, we set In =fw 2 63 j there are i  n;  2 f+; 0g s:t: I (i) = (w; )g, and In+ = In \ L; In0 = In n In+ .
Any mapping T from IN 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 Tn0 are de ned analogously as above.
11

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 63 belongs to L. Note that we allow a text and an
informant to be non{e ective.
De nition 4. P AT is called learnable in the limit from informant (abbr. PAT 2
LIM 0 INF ) i there is an e ective strategy S from IN into P at such that for any
L 2 P AT and any I 2 Info(L),(1) for any n 2 IN, S (I n ) is de ned, and(2) there is a p 2 P at such that L(p) = L and for almost all n 2 IN, S (I n) = p.

De nition 5. P AT is called consistently learnable in the limit from informant (abbr.
PAT 2 CONS 0 INF ) i there is an e ective strategy S from IN into P at such that
(1) P AT 2 LIM 0 INF by S
(2) for any L 2 PAT , I 2 Info(L) and n 2 IN, In+  L(S (I n)) and In0 \ L(S (I n)) = ;.

Note that a consistent learning strategy is required to correctly re ect both, the positive
as well as the negative data it has already seen. Next we sharpen De nition 4 and 5 byadditionally requiring polynomial time computability of S .
De nition 6. P AT is called (consistently) learnable in the limit from informant inpolynomial time (abbr. P AT 2 Poly 0 LIM 0 INF (P AT 2 Poly 0 CONS 0 INF )) i
there are a strategy S and a polynomial pol such that
(1) P AT 2 LIM 0 INF (P AT 2 CONS 0 INF ) by S , and(2) for any L 2 PAT; I 2 Info(L) and n 2 IN,
time to compute S (I n )  pol(length(I n )).

Learning from text is analogously de ned 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 di erence we could de ne a strategy that initially outputs x1 .
12

Since L(x1 ) contains any string over 6 but the empty one, this hypothesis is consistenton text for any nite input. However, since the strategy has to converge, it cannot
maintain this hypothesis ad in nitum. Finally, we use LIM 0 T XT , CONS 0 T XT ,Poly 0 LIM 0 T XT as well as P oly 0 CONS 0 T XT to denote the corresponding
learning types on text.
Now we can precisely state the result mentioned above.
Theorem 7.
(1) P AT 2 CONS 0 INF .
(2) P AT 2= P oly 0 CONS 0 INF , provided P 6= N P .
(3) P AT 2 Poly 0 LIM 0 INF .
Proof. Assertion (1) is proved in applying Gold's (1967) enumeration technique. Therefore, let (pi )i2IN be any xed e ective enumeration of Pat. Let L 2 P AT , let I 2 Info(L)be any informant, and let n 2 IN. De ne S(I n) to be the rst pattern p in the enumeration of P at satisfying In+  L(p) and In0 \ L(p) = ;. Since membership for patternlanguages is uniformly decidable (cf. Angluin (1980)), S is computable. Due to the de nition of S, consistency is obvious. Moreover, the strategy converges to the rst patternin the enumeration that generates the language L to be learnt. Note that S cannot becomputed in polynomial time, unless P = NP , since membership for pattern languages
is NP {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= NP . This part of the proof is done by showing the
NP {hardness of an appropriate problem de ned below. For any information concerning
reducibility as well as NP {complete problems the reader is referred to Garey and Johnson(1979). First we de ne the following decision problem SEP . Let W +; W 0  63 . We saythat W +; W 0 are separable i there is a pattern p such that W +  L(p) and W 0 \ L(p) =;. SEP denotes the problem of deciding whether any W + ; W 0  63 are separable.
Moreover, by CSEP we denote the problem of constructing a separating pattern p forany given W + ; W 0 that are separable. The proof of assertion (2) is completed via thefollowing lemmata.
13

Lemma A. (Ko, Marron, Tzeng, 1990)
3 0 SAT is polynomial time reducible to SEP .
Lemma B. CSEP is N P {hard.
Proof of Lemma B. Let C 3 0 SAT denote the problem to construct a satisfying assignment to any satis able instance from 3 0 SAT .
Claim 1. C 3 0 SAT 2 P implies 3 0 SAT 2 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 satis able. Now let C be any instance of 3 0 SAT .
Start A on input C . Since any polynomial is time constructable, we we may combine A
with a clock, i.e., we can eciently stop A on input C after at most pol(length(C )) stepsof computation. Then two cases are possible. Either A returns nothing. Consequently,
C cannot be satis able. Otherwise A outputs an assignment ass within the given timebound. Then one can check in polynomial time whether or not ass indeed satis es C . In
case it does, we know that C is satis able. In case it does not C is again not satis able,
since otherwise A fails.
Note that we cannot prove the NP {hardness of CSEP in the same manner as in showing 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 0 ) does
indeed separate these sets. However, we overcome this diculty in showing the following
claim.
Claim 2. CSEP 2 P implies C 3 0 SAT 2 P
In accordance with Lemma A let red be any polynomial time reduction of 3 0 SAT
to SEP . Suppose, there is an algorithm B solving CSEP in polynomial time. Now let
C be any satis able instance of 3 0 SAT . The wanted satisfying assignment may becomputed as follows. First, compute red(C ) = (W +; W 0 ). Since C is satis able, we getthat (W + ; W 0) are separable. Next compute p = B(W +; W 0). Finally, let ass be theassignment constructed 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 of(W +; W 0) is bounded by a polynomial in the length of C , too. Consequently, ass ispolynomial time computable. Hence, C 3 0 SAT 2 P , if CSEP 2 P .
14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 2 Poly 0 CONS 0 INF implies CSEP 2 P .
Suppose PAT 2 Poly 0 CONS 0 INF by some strategy S . Let W +; W 0 be any
two separable sets, and let p be any pattern separating them. Let I 2 Info(L(p)) be an
arbitrary informant such that, for some n, In+ = W + and In0 = W 0 . In accordance withthe de nition of separability, I obviously exists. Consequently, S (I n ) has to be de ned,and furthermore, q = S (I n) has to be a pattern separating W +; W 0, too. Finally, S ispolynomial time computable. Hence we get CSEP 2 P .
It remains to prove assertion (3). In Lange and Wiehagen (1991) P AT 2 Poly 0 LIM 0
TXT has been shown. The corresponding strategy witnessing P AT 2 Poly 0 LIM 0 T XT
works by \overlooking" data, i.e., it ignores all but the actually shortest strings of thelanguage to be learnt. It turns out that suciently many really shortest strings of apattern language do suce 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 2 Poly 0 LIM 0 T XT . We de ne a
strategy S~ witnessing P AT 2 Poly 0 LIM 0 INF as follows: On any input I n we set
S~(I n ) = S (In+ ). This proves the theorem.
Note that S~ even works semi{consistently, since In0 \ L(S~(I n )) = ; is valid for alln 2 IN. 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 eciency of the learning algorithm, if one sums up all steps ofcomputation until the learning task is successfully solved; nor does it enlarge the learning
15

power. What we are looking for are \intelligent" inconsistent techniques. In our opinion, Lange and Wiehagen's (1991) re ned 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 0 CONS 0 LEXINF (Poly 0 CONS 0 LEXT XT ) be the learning
type obtained from Poly 0 CONS 0 INF ( Poly 0 CONS 0 T XT ) by restricting theinformation presentation from any informant I 2 Info(L) (any text T 2 Text(L)) to
the lexicographically ordered one. Furthermore, let S be a strategy such that P AT 2
LIM 0 INF (LIM 0 TXT ) by S . Then, for any L 2 P AT and D 2 Info(L) [ Text(L),
let
Conv(

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 eciently, 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 2 Poly 0 CONS 0 LEXINF by S~,(ii) for any p 2 P at, there are uncountably many informants I 2 Info(L(p)) suchthat
{ S~ works consistently on I ,~(S;I ) time to compute S~(I n )  pol (length(p)).
{ 6Conv
n=0(2) There are a strategy S and a polynomial pol such that(i) P AT 2 Poly 0 CONS 0 LEXTXT by S ,16(ii) for any p 2 P at, there are uncountably many texts T 2 Text(L(p)) such that
{ S works consistently on T ,(S;T ) time to compute S (T n )  pol(length(p)).
{ 6nConv=0

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 rst 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 CONS 0 T XT . The corresponding
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 the following. A strategy working consistently on informant has to work \hard"at any step of the learning process, while a consistent strategy on text may output x1 fora 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.
There are learning problems which can be exclusively solved by inconsistent strategies,
i.e., by strategies that do temporarily incorrectly re ect 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
17

strategies have to work in polynomial time. The reason is quite analogous to that in thesetting of arbitrary recursive functions. Providing P 6= NP , the NP -hardness of problems
can prevent learning strategies from producing consistent hypotheses in polynomial time.
Note that the validity of our main result, Theorem 7, crucially depends on the fact thatmembership testing for pattern languages is N P -complete. Actually, one can easily showthat in domains where the membership problem is uniformly decidable in polynomial time,
any polynomial time learning algorithm can be e ectively transformed into a polynomial
time algorithm possessing at least the same learning power and being even consistent.
Nevertheless, just in these cases we conjecture that there are learning problems solvableconsistently in polynomial time, but solvable inconsistently (much) faster.
Moreover, we conjecture that our results may be extended to incremental learning ofnite classes of nite objects such as Boolean functions, too.
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. nding fast inconsistent learning techniques
2. deriving conditions yielding that a given learning problem has no fast consistentsolution, but a fast inconsistent one.
Acknowledgement

The rst author has been supported by the German Ministry for Research and Technology (BMFT) within the joint project (BMFT{Verbundprojekt) GOSLER under grant
01 IW 101 B/9.
Moreover, substantial part of this work has been performed while the rst author was
visiting TH Darmstadt. He is grateful indebted to Rudiger Reischuk and Wolfgang Bibelfor providing inspiring working conditions.
Furthermore, both authors heartily acknowledge many enlightening discussions with
Ste en Lange (HTWK Leipzig) and with Andreas Jakoby and Christian Schindelhauer(TH Darmstadt).
18

6. References[1] Angluin, D. (1980), Finding patterns common to a set of strings, Journal of Computer and System Sciences, 21:46 - 62.
[2] Angluin, D. and Smith, C.H. (1983), Inductive inference: theory and methods,
Computing Surveys, 15:237 - 269.
[3] Angluin, D. and Smith, C.H. (1987) Formal inductive inference, In St.C. Shapiro(ed.) Encyclopedia of Arti cial Intelligence, Vol. 1 (New York: Wiley-Interscience
Publication), 409 - 418.
[4] Barzdin, Ya.M. (1974), Inductive inference of automata, functions and programs,
In: Proc. Int. Congress of Math., Vancouver, pp. 455 - 460.
[5] Blum, M. (1967), Machine independent theory of complexity of recursive functions,
Journal of the Association for Computing Machinery, 14:322 -336.
[6] Blum, L. and Blum, M. (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 Johnson, D.S. (1979), Computers and Intractability, A Guide to
the Theory of NP {completeness, (San Francisco: Freeman and Company).
[9] Gold, M.E. (1965), Limiting recursion, Journal of Symbolic Logic, 30:28 - 48.
[10] Gold, M.E. (1967), Language identi cation in the limit, Information and Control,
10:447 - 474.
[11] Jantke, K.P. (1991) Monotonic and non{monotonic inductive inference of functions
and patterns, In J.Dix, K.P. Jantke and P.H. Schmitt (eds.) Proc. 1st International Workshop on Nonmonotonic and Inductive Logic, Lecture Notes in Arti cialIntelligence 543 (Berlin: Springer-Verlag), 161 - 177.
19

[12] Jantke, K.P. and Beick, H.R. (1981), Combining postulates of naturalness in inductive inference, Journal of Information Processing and Cybernetics (EIK), 17:465 484.
[13] Kearns, M. and Pitt, L. (1989), A polynomial{time algorithm for learning k{variable
pattern languages from examples, In D. Haussler and L. Pitt (eds.) Proc. 1stWorkshop on Computational Learning Theory (Los Alto, CA: Morgan Kaufmann
Publishers Inc.), 196 -205.
[14] Ko, Ker{I, Marron, A. and Tzeng, W.G. (1990), Learning string patterns and tree
patterns from examples, In Proc. 7th Conference on Machine Learning, 384 - 391.
[15] Lange, S. and Wiehagen, R. (1991), Polynomial{time inference of arbitrary patternlanguages, New Generation Computing, 8:361 - 370.
[16] Lange, S. and Zeugmann, T. (1993) Monotonic versus non{monotonic language
learning, In G.Brewka, K.P. Jantke and P.H. Schmitt (eds.) Proc. 2nd International Workshop on Nonmonotonic and Inductive Logic, Lecture Notes in Arti cialIntelligence 659 (Berlin: Springer-Verlag), 254 - 269.
[17] Lange, S. and Zeugmann, T. (1992), Types of monotonic language learning andtheir characterization, In Proc. 5th Annual Workshop on Computational Learning
Theory (New York: ACM Press), 377 - 390.
[18] Nix, R.P. (1983), Editing by examples, Yale University, Dept. Computer Science,
Technical Report 280.
[19] Osherson, D., Stob, M. and Weinstein, S. (1986), Systems that Learn. An Introduction to Learning Theory for Cognitive and Computer Scientists (Cambridge, MA:
MIT-Press).
[20] Porat, S. and Feldman, J.A. (1988), Learning automata from ordered examples, In
D. Haussler and L. Pitt (eds.) Proc. 1st Workshop on Computational Learning
Theory (Los Alto, CA: Morgan Kaufmann Publishers Inc.), 386 - 396.
[21] Rogers, H.Jr. (1967), Theory of Recursive Functions and E ective Computability(New York: McGraw{Hill).
20[22] Shinohara, T. (1982), Polynomial time inference of extended regular pattern languages, In Proc. RIMS Symposia on Software Science and Engineering, Kyoto,
Lecture Notes in Computer Science 147 (Berlin: Springer{Verlag), 115 - 127.
[23] Solomono , R. (1964), A formal theory of inductive inference, Information andControl, 7:1 - 22, 234 - 254.
[24] Wiehagen, R. (1976), Limes{Erkennung rekursiver Funktionen durch spezielle Strategien, Journal of Information Processing and Cybernetics (EIK), 12:93 - 99.
[25] Wiehagen, R., (1978a), Zur Theorie der algorithmischen Erkennung, Dissertation
B, Humboldt{Universitat zu Berlin.
[26] Wiehagen, R., (1978b), Characterization problems in the theory of inductive inference, In G. Ausiello and C. Bohm (eds.) Proc. 5th Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 62 (Berlin: SpringerVerlag), 494 - 508.
[27] Zeugmann, T., (1983), A{posteriori characterizations in inductive inference of recursive functions, Journal of Information Processing and Cybernetics (EIK) 19:559- 594.

21