Teaching Learners with Restricted Mind
ChangesFrank J. Balbach1 and Thomas Zeugmann2
1

Institut für Theoretische Informatik, Universität zu Lübeck,
Ratzeburger Allee 160, 23538 Lübeck, Germany
balbach@tcs.uni-luebeck.de
2
Division of Computer Science,
Hokkaido University, Sapporo 060-0814, Japanthomas@ist.hokudai.ac.jp

Abstract. Within learning theory teaching has been studied in various
ways. In a common variant the teacher has to teach all learners thatare restricted to output only consistent hypotheses. The complexity ofteaching is then measured by the maximum number of mistakes a consistent learner can make until successful learning. This is equivalent to theso-called teaching dimension. However, many interesting concept classes
have an exponential teaching dimension and it is only meaningful toconsider the teachability of finite concept classes.
A refined approach of teaching is proposed by introducing a neighborhood relation over all possible hypotheses. The learners are then restricted to choose a new hypothesis from the neighborhood of their current one. Teachers are either required to teach finitely or in the limit.
Moreover, the variant that the teacher receives the current hypothesis of
the learner as feedback is considered.
The new models are compared to existing ones and to one another in
dependence of the neighborhood relations given. In particular, it is shownthat feedback can be very helpful. Moreover, within the new model one
can also study the teachability of infinite concept classes with potentiallyinfinite concepts such as languages. Finally, it is shown that in our model
teachability and learnability can be rather different.

1. Introduction
Teaching has been modeled and investigated in various ways within algorithmic learning theory. Already in Angluin’s query model [1, 2] the oracles havesome characteristics of teachers. However, they remain completely passive. In order to study teachers in a more active role, several models have been developed,
each of which follows one of two basically different approaches.
In the first approach, the goal is to find a teacher and a learner such thata given learning task can be carried out by them. For the inductive inference
framework, Freivalds et al. [8] and Jain et al. [14] developed a model in which arather implicit teacher provides the learning strategy with good examples. Jackson and Tomkins [13] as well as Goldman and Mathias [10, 15] defined models

Teaching Learners with Restricted Mind Changes

475

of teacher/learner pairs where teachers and learners are constructed explicitly.
In all these models, some kind of adversary disturbing the teaching process isnecessary to avoid collusion between the teacher and the learner. Angluin andKriķis’ [3, 4] model prevents collusion by giving incompatible hypothesis spaces
to teacher and learner. This makes simple encoding of the target impossible.
In the second approach, a teacher has to be found that teaches all learners.
This prevents collusion, since teaching happens the same way for all learners
and cannot be tailored to a specific one. Goldman et al. [11] and Goldman and
Kearns [9] substitute the adversarial teacher in the online learning model bya helpful one selecting good examples. They investigate how many mistakes aconsistent learner can make in the worst case. In Shinohara and Miyano’s [17]model the teacher produces a set of examples for the target concept such that itis the only consistent one in the concept class. The size of this set is the same as
the worst case number of mistakes in the online model. This number is termed
the teaching dimension of the target. Because of this similarity we will from now
on refer to both models as the teaching dimension (TD-)model.
One difficulty of teaching in the TD-model results from the teacher notknowing anything about the learners besides them being consistent. In reality
a teacher can benefit a lot from knowing the learners’ behavior or their current
hypotheses. It is therefore natural to ask how teaching can be improved if theteacher may observe the learners’ hypotheses after each example.
After translating this question into the TD-model, one sees that there is no
gain in sample size at all. The current hypothesis of a consistent learner reveals
nothing about its following hypothesis. Even if the teacher knew the hypothesis
and provided a special example in response, he can only be sure that the learner’s
next hypothesis will be consistent. But this was already known to the teacher.
In this paper we extend the TD-model by a neighborhood relation over all
hypotheses and by the requirement that all learners may only switch to a hypothesis in the neighborhood of their current one. We then compare basicallytwo variants: In the first, the teacher receives the learner’s hypothesis after every
example taught. In the second, the teacher has no feedback available. It turns
out that in the extended model the existence of feedback can really make adifference. Some concept classes can be taught much faster with feedback than
without and some cannot be taught unless feedback is available to the teacher.
As a side effect the model can be used to study the teachability of infiniteclasses with potentially infinite concepts, e.g., languages. In the class containing
all finite languages, for example, all concepts have an infinite teaching dimension and are thus unteachable in the TD-model. With appropriate neighborhood
relations this class can be taught, as we shall show in Section 3.

2. Preliminaries
A concept c is a subset of an instance space X and a concept class is a set ofconcepts over X. We consider two instance spaces: {0, 1}n for Boolean functionsand Σ ∗ for languages over a finite and non-empty alphabet Σ. By X = X ×{0, 1}

476

F.J. Balbach and T. Zeugmann

we denote the set of examples over X. An example (x, b) is either positive, if b = 1,or negative, if b = 0. A concept c is consistent with (x, b) iff x ∈ c ⇔ b = 1.
Let R be a set of strings. R represents C iff there is a function γ : R × X →{0, 1} with C = {Cr r ∈ R}, where Cr = {x γ(r, x) = 1}. The length of r isdenoted by |r| and size(c) := min{|r| Cr = c} for every c ∈ C. For any set S, wedenote by card(S) its cardinality and by S ∗ the set of all finite tuples over S. We
use the symbols ◦ for concatenation of tuples and 4 for the symmetric differenceof two sets. Let c be a concept and let x ∈ X ∗ be a list of examples, then err (x, c)is the set of all examples in x that are inconsistent with c.
A teaching set for a concept c with respect to C is a set S of examples suchthat c is the only concept in C consistent with S. The teaching dimension TD(c)is the size of the smallest teaching set for c, the teaching dimension of C is
TD(C) = max{TD(c) c ∈ C}.
For studying feedback, the learners in our model have to evolve over time. We
adopt the online learning model and divide the teaching process into rounds. In
each round the teacher provides an example to the learner who then computes ahypothesis from R. At the end of the round the teacher observes this hypothesis.
Thus, we describe a teacher by a function T : R × R∗ → X receiving a
concept’s representation and a sequence of previously observed hypotheses as
input and outputting an example.
A learner can be described by a function L : X ∗ → R receiving a sequence of
examples as input and outputting a hypothesis. Let ν ⊆ R × R be a relation overR. Then L is called restricted to ν iff ∀x ∈ X ∗ ∀z ∈ X [(L(x), L(x◦z)) ∈ ν], thatis ν defines the admissible mind changes of L. Now, (R, ν) is a directed graphand we define the neighborhood of r ∈ R as Nb(r) := {s ∈ R (r, s) ∈ ν} ∪ {r}and denote by dist(r, s) the length of a shortest path from r to s.
In the TD-model, the learner is required to always output a consistent hypothesis. Since in the restricted model all admissible hypotheses might be inconsistent, we have to modify this demand. We require that L chooses only among
the admissible hypotheses with least error with respect to the known examples.
Moreover, we require a form of conservativeness: L may only change its hypothesis if the new one has a smaller error. This ensures that L will not change its
mind after reaching a correct hypothesis. On the other hand, we also require L tosearch for a better hypothesis if it receives an inconsistent example. Otherwise,
L could stay at the initial hypothesis forever and teaching were impossible.
Definition 1. Let R be a representation language for a concept class C and letν ⊆ R × R be a relation over R and h0 ∈ R a starting hypothesis. A ν-learner isa function L : X ∗ → R with L(∅) = h0 and for all x ∈ X ∗ and for all z ∈ X :(1) (L(x), L(x ◦ z)) ∈ ν,(2) if L(x) 6= L(x ◦ z) then z is inconsistent with CL(x) ,(3) if z is inconsistent with CL(x) thenL(x ◦ z) ∈ arg mins∈Nb(L(x)) card(err (x ◦ z, Cs )).
We briefly remark that one can think of many plausible variants of the above
definition. For instance, the learner could be allowed to change its mind on aTeaching Learners with Restricted Mind Changes

477

consistent example if its hypothesis is inconsistent with an example received
earlier. In this paper, however, all learners follow Definition 1.
The teaching process for a concept c = Cr is fully described by a teacher T anda learner L together with an initial hypothesis h0 . Such a process will result in aseries (hi )i∈N of hypotheses and a series (zi )i∈N of examples: hi+1 = L(z0 , . . . , zi )and zi = T (r, (h0 , . . . , hi )).
Definition 2. Let C be a concept class with representation R and let ν ⊆ R ×R.
We call C teachable to ν-learners in the limit with feedback iff there is a teacher
T such that for all representations r ∈ R and all ν-learners L the series (hi )i∈Nof hypotheses converges to an h with Ch = Cr .
The teaching time of T on r is the maximum i such that there is a ν-learner Lthat reaches a representation of Cr at round i for the first time.
Note that an infinite teaching time does not imply unteachability of a concept.
For studying the influence of feedback, we also have to define teaching without
feedback. In this situation the teacher is modeled as a function T : R × → X ,where the second argument specifies the round. The series of hypotheses is thengiven by hi+1 = L(T (r, 0), . . . , T (r, i)). With this notation the definition of teaching in the limit without feedback is literally the same as Definition 2.
In the situation with feedback the teacher can stop teaching as soon as thelearner has reached the goal. If there is no feedback, the teacher may or may notknow when to stop. A teacher stopping after finitely many examples and still
ensuring the learning success is said to teach finitely without feedback. More formally we consider T : R × → X ∪ {⊥} where ⊥ means “teaching has stopped.”
With feedback we do not need to distinguish teaching finitely from teachingin the limit and we shall call this kind of teaching simply teaching with feedback.

N

N

Definition 3. Let C be a concept class with representation R and let ν ⊆ R ×R.
We call C finitely teachable to ν-learners without feedback iff there is a teacher Tsuch that for all representations r ∈ R and all ν-learners L the hypothesis hj
with j = min{i T (r, i) = ⊥} satisfies Chj = Cr .
Setting ν = R × R in Definition 3 gives the teacher-directed learning model[11] having no restriction on hypothesis changes. Theorem 4 justifies the use ofarbitrary ν’s for studying the impact of feedback on the teaching process.
Theorem 4. Let C be a concept class with representations R and let ν = R × R.
Then the following statements are equivalent:(1) C is finitely teachable to ν-learners without feedback,(2) C is teachable in the limit to ν-learners without feedback,(3) C is teachable to ν-learners with feedback.
Furthermore in all three cases the same teacher can be used to obtain minimum
teaching time which for all c ∈ C equals TD(c) with respect to C.
Proof. The implication 1. ⇒ 2. ⇒ 3. is clear from the definitions.
It remains to show 3. ⇒ 1. Let C be teachable to ν-learners with feedbackfor ν = R × R and let c ∈ C. We first prove that for all c ∈ C, TD(c) < ∞.

478

F.J. Balbach and T. Zeugmann

Suppose there is a c∗ ∈ C with TD(c∗ ) = ∞. Then there is a ν-learner L always
assuming a consistent hypothesis not representing c∗ . This is possible because
there is no finite set of examples specifying c∗ and because every hypothesis canbe reached from every other. Obviously L cannot be taught c∗ in the limit, noteven with feedback; a contradiction.
Now, since all teaching dimensions are finite, we can define a teacher T that
outputs for each c ∈ C a teaching sequence and stops. T does not need any
feedback. Clearly, T teaches C to all ν-learners finitely and without feedback,because at the end of teaching there is only one consistent hypothesis left whichis certainly reachable.
To see that T has optimal teaching time for c ∈ C with respect to all threeteaching models, we consider a ν-learner L that always outputs a consistenthypothesis not representing c, unless c is the only consistent concept in whichcase L outputs a representation for c. It is easy to see that c cannot be taught to Lwith less than TD(c) examples, no matter whether or not feedback is allowed.
Note that Theorem 4 relies on the fact that neither the teacher nor the learners nor the function γ are required to be recursive. Adding these requirements
leads to new questions which we skip here due to space constraints.

3. Comparison of the Teaching Models
In this section we will apply the new framework to the class Cfin of all finite
languages over an alphabet Σ. This class cannot be taught in the TD-model. By
using different ν-restrictions we demonstrate various effects.
We fix any total ordering on all strings over Σ and use as representation
language R the set of all comma-separated ordered lists of strings over Σ, i.e.,r = w1 , . . . , wm ∈ R
represents the language {w1 , . . . , wm }. To simplify proofs
Pmlater, we set |r| := i=1 |wi |, i.e., without counting the commas. We define theallowed transitions from r to s by (r, s) ∈ ν iff card(Cr 4 Cs ) ≤ 1. The initial
hypothesis is the empty string ε representing the empty concept. Now we have:
Fact 5. Cfin is finitely teachable to ν-learners without feedback.
Proof. For a finite language with representation w1 , . . . , wm a teacher simply
presents all positive examples (w1 , 1), . . . , (wm , 1). In every round, the learners
may either add or remove a string from their hypothesis. Starting at the empty
language, there is only one possibility to stay consistent with the examples,
namely by adding them to the hypothesis. Therefore, after m rounds all νlearners have arrived at the target hypothesis.
Feedback can be utilized when the restriction is modified. We define (r, s) ∈ ν 0
iff Cs = Cr ∪ {w1 , w2 } for some w1 , w2 ∈ Σ ∗ or Cs = Cr \ {w1 }. In both cases, we
require that the size of the hypotheses may at most double each round: |s| ≤ 2|r|.
In the special case r = ε we allow every singleton concept as neighbor: (ε, s) ∈ ν
for all s with card(Cs ) = 1. For ν 0 -learners there is a big difference in teachingtime between teaching with and without feedback.

Teaching Learners with Restricted Mind Changes

479

Fact 6. Cfin is teachable to ν 0 -learners with feedback such that for all c ∈ C thenumber of examples is O(card(c)) ≤ O(size(c)).
Proof. All ν 0 -learners may either add two strings to their hypothesis or remove
one. As a consequence, whenever a ν 0 -learner receives a positive example, he can
add it to the hypothesis and “invent” another string and add it to the hypothesis
as well. Due to the size restriction there are always only finitely many strings
that can be invented.
Let c∗ = {w1 , . . . , wm } be a target concept. A teacher with feedback firstteaches all strings wi as positive examples. After wm the hypothesis of eachlearner contains c∗ plus at most m invented strings u1 , . . . , u` . From the feedback,the teacher gets to know these strings and can teach them as negative examples.
Since at most one string can be removed per round, the learners have to remove
the negative example they are taught and thus arrive at the correct hypothesis
after ` rounds. Alltogether teaching takes at most 2m = 2card(c∗ ) rounds.
Fact 7. Cfin is finitely teachable to ν 0 -learners without feedback. Every suchteacher needs Ω(2size(c) ) examples for some c ∈ C and there is no upper boundfor the number of examples that depends only on card(c).
Proof. A suitable teacher is defined as follows. Let c ∈ Cfin . First of all, theteacher gives all strings of length at most 2size(c) that are not in c as negative
examples. Afterwards, all strings in c, starting with a longest one, are taught aspositive examples. The initial hypothesis is consistent with all negative examples,
hence no hypothesis change happens. During the positive examples, the learners
cannot include any strings outside of c into their hypotheses, since all thesestrings either have been ruled out by the negative examples or are too long to
be included. Also, since a longest string is taught first, the hypothesis growth
limitation cannot be violated by positive examples included later. Hence, all ν 0 learners must reach the target hypothesis after the positive examples are taught.
For the lower bound, let T be a teacher that teaches Cfin finitely without
feedback to all ν 0 -learners. Let a and b be symbols from the alphabet and c∗ ={am , b} a concept of size m + 1 for an arbitrary m > 2. Let z0 , . . . , zM be all
examples taught by T on concept c∗ . Let L be a ν 0 -learner.
Clearly both strings, am and b, must occur as positive examples, otherwise
the ν 0 -learner L0 that never “invents” a string could not be taught. Moreover,
am must occur before b, since otherwise L0 would at some point have b as
hypothesis. But because of the growth restriction, b cannot by changed to am , b
later, thus L0 cannot learn c∗ . Let zj1 = (am , 1) be the the first occurrence ofam and let zj2 = (b, 1) be the first occurrence of b.
It suffices to show that z1 , . . . , zM contains all strings of length at most m−1.
∗
This implies M ≥ 2m − 1 = Ω(2size(c ) ). Assume there were a string ŵ ∈/ c∗ with0|ŵ| ≤ m − 1 which is not taught. We give a ν -learner L that does not arrive atc∗ during teaching. On zj1 , L switches to hypothesis hj1 +1 = am and does notchange it until zj2 arrives. Then L chooses the hypothesis hj2 +1 = am , b, ŵ whichis incorrect, but consistent with the examples so far. The length restriction is

480

F.J. Balbach and T. Zeugmannobeyed, since size(am ) = m = |b| + |ŵ|. From then on, L will never change thehypothesis, since the only inconsistent example, (ŵ, 0), is never taught according
to the assumption.
As m can be choosen arbitrarily large, there is no bound on the number ofexamples needed that depends on card(c∗ ) only.
If we remove the size restriction from ν 0 we obtain ν 00 .
Fact 8. Cfin is not finitely teachable to ν 00 -learners without feedback, but it isfinitely teachable with feedback as well as in the limit without feedback.
Proof. Suppose there is a teacher that finitely teaches Cfin to ν 00 -learners without
feedback. Let c = {w1 , w2 } ∈ Cfin . Then a learner that, when the second positive
example arrives, “invents” a word not occurring in the examples does not arrive
at a correct hypothesis, a contradiction.
Next, we describe a teacher T which teaches Cfin finitely with feedback. On
c ∈ Cfin , T first gives all positive examples. This may lead to at most card(c)superfluous strings in the hypothesis of a ν 00 -learner. T observes these stringsand gives them as negative examples, thus forcing all learners to remove theexcessive strings and to reach the correct hypothesis.
A teacher for teaching Cfin in the limit without feedback, first teaches all
positive examples. Again, a ν 00 -learner’s hypothesis may contain finitely many
excessive strings. By teaching all strings outside the target concept, the superfluous strings can be removed in the limit.
Finally we define ν 000 . It differs from ν 00 in that a string may only be removed
from the hypothesis if neither its predecessor nor its successor (with respect tothe fixed ordering on Σ ∗ ) is contained in the hypothesis.
Fact 9. Cfin is not teachable to ν 000 -learners in the limit without feedback, but it
is finitely teachable with feedback.
Proof. Suppose there is a teacher T which teaches Cfin to ν 000 -learners in the limit
without feedback. Let c∗ = {w1 , w2 , w3 } ∈ Cfin and let (zi )i∈N be the sequenceof examples taught by T on c∗ . All three strings must occur in the example
sequence, otherwise the learner that does not “make up” strings could not betaught. Let zji = (wi , 1) be first occurrence of wi for i = 1, 2, 3. Without loss ofgenerality, we assume j1 < j2 < j3 .
We now construct a ν 000 -learner L which fails on the above example sequence.
After zj1 , L’s hypothesis is w1 . When taught zj2 , L adds w2 to the hypothesis,
as well as a string u1 ∈/ c∗ such that (1) neither u1 nor its successor u2 occurs
in z1 , . . . , zj3 , and (2) u2 ∈/ c∗ . When taught zj3 , L adds w3 and u2 to the
hypothesis. Adding u2 is possible, because it has not yet occurred as negative
example. At this point L’s hypothesis contains the strings u1 and u2 neither ofwhich can be deleted any more. Thus, L cannot end up with a correct hypothesis(because of the definition of ν 000 ), a contradiction.
Teaching Cfin to ν 000 -learners finitely with feedback can be done as follows. Let∗c ∈ Cfin be the target concept. The teacher first teaches all negative examples

Teaching Learners with Restricted Mind Changes

481

that are predecessors or successors of a string in c∗ . Then all positive examples
are taught and as soon as the teacher discovers that a learner has introduced
a wrong string u into the hypothesis, the negative example (u, 0) is given. The
string u cannot be predecessor or successor of any other string in the hypothesis
and is thus deleted from the hypothesis. After at most (2 + 1 + 1) · card(c) =O(size(c)) examples all ν 000 -learners have reached the target.
If we denote by TFIN , TFB , TLIM the set of all (C, R, ν, h0 ) such that C isfinitely teachable without feedback, with feedback or in the limit, respectively,
we have just proved the following theorem.
Theorem 10. TFIN ⊂ TLIM ⊂ TFB .
The teaching times in our model can hardly be compared to the teaching
dimension, since the latter depends only on C, whereas different choices of ν canlead to different teaching times for the same C.

4. Finding Teachers
The problem of finding an optimal teacher (with or without feedback) forν-learners is NP-hard, since it is a generalization of finding an optimal teachingset, namely if ν = R × R (see [17, 9, 5]).
Concept classes over finite instance spaces can always be taught in the TDmodel. Given ν-learners, however, the first question is whether teaching is possible at all. We shall show that this is difficult to decide in general.
The next theorem assumes that C and ν over an instance space X and representation language R are represented as a 0-1-valued matrix with card(R) rows
and card(X) + card(R) columns. Each row describes the represented concept in
the first card(X) bits, and its neighborhood in the last card(R) bits (cf. Fig 1).

x1 x̄1 x2 x̄2 x3 x̄3 x4 x̄4r0 1 1 1 1 1 1 1 1
r1 0 1 1 0 0 1 1 1
r2 0 1 0 1 1 1 0 1
r3 1 0 1 1 0 1 1 0
s0 1 1 1 1 1 1 1 1
s1 0 0 1 1 1 1 1 1
s2 0 0 0 0 1 1 1 1
s3 0 0 0 0 0 0 1 1
s4 0 0 0 0 0 0 0 0s∗ 1 1 1 1 1 1 1 1

w
0
1
1
1
1
1
1
1
1
1

y1 y10 y2 y20 y3 y30 y4 y40
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

r0 r1 r2 r3 s0 s1 s2 s3 s4 s∗
0 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0

Fig. 1. Example for the reduction in Theorem 11 for the formula F = (v1 ∨ v̄2 ∨ v3 ) ∧(v2 ∨ v4 ∨ v1 ) ∧ (v̄1 ∨ v3 ∨ v̄4 ). The left part of the matrix defines C, the right one ν.

482

F.J. Balbach and T. Zeugmann

Theorem 11. For all notions of teaching, the following problem is NP-hard:
Instance: C, R, ν, and a concept c∗ as 0-1-vector of length card(X).
Question: Can c∗ be taught to ν-learners?
Proof. The proof is by reduction from 3-SAT. Let F = K1 ∧· · ·∧Km be a formulain 3-CNF with clauses K1 , . . . , Km and variables v1 , . . . , vn . Define XF , CF , RFand νF as follows. XF contains instances x1 , x̄1 , . . . , xn , x̄n and y1 , y10 , . . . , yn , yn0
and an instance w, hence card(XF ) = 4n + 1. RF contains the representations
r0 , r1 , . . . , rm , s0 , s1 , . . . , sn , s∗ . The initial hypothesis r0 represents {x1 , x̄1 , . . . ,xn , x̄n }, the target concept c∗ := {x1 , x̄1 , . . . , xn , x̄n , w} will be represented by s∗ .
For each clause Ki we use ri to represent a concept that consists of all instances
except of xj for all vj in Ki and except of x̄j for all v̄j in Ki . Finally s0 represents
0
XF and si represents the concept {xi+1 , x̄i+1 . . . xn , x̄n , yi+1 , yi+1
, . . . , yn , yn0 , w}
for i = 1, . . . , n (see Fig. 1).
The relation νF contains (r0 , ri ) for all i = 1, . . . , n and (r0 , s0 ) and (si , si+1 )for i = 0, . . . , n − 1, as well as (sn , s∗ ). The only path from the initial to thetarget hypothesis is r0 , s0 , s1 , . . . , sn , s∗ . If one of the ri ’s is reached, teachinghas failed as these representations are dead ends.
CF and νF can easily be computed and encoded as a (4n + 1 + m + 1 + n + 2) ·(m+1+n+2) = O((n+m)2 ) size matrix. Therefore the reduction is polynomial.
Let F be satisfied by an assignment β : {v1 , . . . , vn } → {0, 1}. We have toshow that c∗ is teachable in the environment defined above. A successful example
sequence consists of (1) for all i = 1, . . . , n the positive examples xi , if β(vi ) = 1,or x̄i , if β(vi ) = 0; (2) the positive example w; (3) the sequence y1 , y10 , . . . , yn , yn0
of negative examples; (4) any positive example not yet presented. All examples
before w are consistent with r0 , hence no mind change can take place. A mindchange is then triggered by teaching (w, 1). By their definition all ri ’s are inconsistent with the examples taught at Step (1), whereas s0 certainly is consistent.
Therefore all νF -learners will hypothesize s0 after Step (2). Teaching y1 and y10
causes two inconsistencies with s0 , but s1 has only one error (either x1 or x̄1 ,depending on β). It follows that all learners are forced to s1 . Similarly one cansee that after teaching y2 , y20 , . . . , yn , yn0 all learners have reached sn . Now eachmissing positive example triggers a mind change to s∗ . This shows that c∗ isteachable.
Let F be a formula such that c∗ ∈ CF is teachable to all νF -learners. Let
z1 , . . . , z` ∈ X be a sequence of examples such that all νF -learners starting at r0
end up in s∗ . We have to show that F can be satisfied.
The idea of the proof is as follows. First we show that after a certain example
all learners must have reached s0 . At this point, for all i = 1, . . . , n not bothxi and x̄i have been taught. To prove this we show that, if for some i both xi
and x̄i have been taught, then it is impossible to force all learners to reach s∗ .
Finally we define a satisfying assignment β depending, for each i, on whether xi
or x̄i occurs in the sample.
As long as the teacher teaches examples different from w, r0 is consistentand no mind change happens. Therefore, for some k, zk = (w, 1). At this pointa mind change must happen. If there were no mind change, all neighbors of r0 ,

Teaching Learners with Restricted Mind Changes

483

i.e., r1 , . . . , rm , s0 , had more errors than r0 . This cannot be repaired, thus alllearners would remain in r0 forever.
Since the example sequence eventually leads to s∗ , the hypothesis after example zk must be s0 . Furthermore none of the y-examples can have been taught:
Otherwise all neighbors of r0 had at least one error (the y-example) and r0 had
exactly one error (the example w), hence no change from r0 had occured.
Since the only way to s∗ is via s1 , . . . , sn , the teacher must now provide examples that make all learners switch to s1 . Now, the point is that, if x1 and x̄1
occur in the sample, then s1 has two errors, but if only one of these examples
occurs, then s1 has only one error. If the hypothesis is to be switched to s1 , theteacher must provide examples such that s0 has at least two errors (otherwise
there were no better hypothesis in the neighborhood). Since s0 and s1 are identical with respect to all instances except x1 , x̄1 , y1 , y10 , such errors can only begenerated by teaching y1 as well as y10 . But even then, the mind change can only
be performed if s1 has less than two errors. Thus, since s1 is reached via theexample sequence, it follows that not both x1 and x̄1 have been taught.
In a similar way it can be shown that si+1 can only be reached from si if
not both xi+1 and x̄i+1 appear in the sample. Note that teaching xi or x̄i after
the learners have reached si is possible, but does not influence the following
mind changes, because the concepts si+1 , . . . , sn are identical with respect to
x1 , x̄1 . . . , xi , x̄i .
Altogether it follows that when all learners changed to s0 for all i either xi
or x̄i had not been in the sample taught so far. Therefore the assignment β is
well-defined by β(vi ) = 1 iff xi appears among the examples z1 , . . . , zk .
It remains to show that β satisfies F . This is clear from the definition of
the ri ’s. If β did not satisfy a clause Kj then rj is consistent with whateverx-examples have been taught before w. Thus, rj is an equally good neighbor
as s0 and there will be a νF -learner choosing rj instead of s0 . But this is acontradiction to the assumption that all such learners reach s∗ .
For infinite instance spaces or classes (and infinite ν) the next theorem applies.
Theorem 12. The following function is not computable:
Input: Algorithms computing total functions deciding C and ν.
Output: 1, if C can be taught to ν-learners; 0 otherwise.

N

Proof. We use
as instance space and as representation language. Let C ={{0, . . . , i} i ≥ 1} ∪ { } a concept class. A concept {0, . . . , i} is represented byi, and 0 represents the concept . Let (ϕi )i∈N be an effective enumeration of
all partial recursive functions. For all j ∈we define an effective enumeration(νj )j∈N by
1, if r + 1 = s or (s = 0 and ϕj (j) is defined after ≤ r steps),νj (r, s) =0, otherwise.

N

N

N

It suffices to show that C is teachable to νj -learners iff ϕj (j) is defined. Let
C be teachable to νj -learners. Then can be taught, hence the representation 0

N

484

F.J. Balbach and T. ZeugmannNmust be reachable in the graph ( , νj ). From the definition of νj follows thatϕj (j) is defined.
For the converse let ϕj (j) be defined after r steps. Then can be taught by
the example sequence (2, 1), . . . , (r, 1), (r + 2, 1), where the last example ensuresthat the only consistent neighbor of r is 0. Concepts {0, . . . , i} can be taughtby (i + 1, 0), (2, 1), . . . , (i, 1), where the first example prohibits a transition tohypothesis 0.

N

5. Teaching Without Feedback
A teacher T without feedback knows all learners’ initial hypotheses h0 , but
can quickly lose track of them during teaching. On the other hand, T can rule outneighbors r of h0 by giving examples consistent with h0 , but inconsistent with r.
If in such a way T can eliminate all but one neighbor r0 , he effectively forces
all learners to switch to r0 . By continuing in this manner, T always knows alllearners’ hypotheses even without feedback. If the enforced hypotheses approach
the target, T will be successful. Figure 2 describes this strategy more formally.
1 r := h0 ;2 while Cr 6= c∗ do:
2.1 Find s ∈ Nb(r), S ⊆ X , and z ∈ X such that (1) Cr is consistent with S, but
not with z, (2) s is the only neighbor of r consistent with S ∪ {z}, and (3)dist(s, r∗ ) < dist(r, r∗ );2.2 Teach S in arbitrary order and then z;
2.3 r := s;Fig. 2. A simple general strategy for teaching without feedback by forcing all learners
to make the same mind changes. The initial hypothesis is h0 , r∗ represents the target.

The feasibility of this strategy depends on Step 2.1. If teaching does notneed to be finite, the condition in Step 2 does not need to be checked. Albeit
simple, the strategy works surprisingly often for natural concept classes and νrestrictions. In the following we give some examples. Some proofs are omitted
due to lack of space; the reader is refered to [6].
First, we consider the class of all monomials over n variables. Let R ={0, 1, ∗}n and define (r, s) ∈ ν iff r and s differ only in one “bit.” As initial
hypothesis h0 = ∗n is used.
Fact 13. Monomials are finitely teachable without feedback. The teaching timefor each concept equals its teaching dimension.
Proof. Let c∗ be a concept represented by r∗ . We use the “standard” minimum
teaching set for monomials that can be constructed in time O(n2 ) (see [9, 17]).
Let k1 , . . . , k` be the positions of all constants in r∗ . The teaching set consists of+
two positive examples x+
0 , x1 which result from substituting all ∗’s with zeroes
and ones, respectively. Furthermore it contains one negative example x−
i for eachTeaching Learners with Restricted Mind Changes

485

ki where the ki -th bit is inverted and all ∗’s are replaced by zeroes. Let T teach+−−the sequence hx+
0 , x1 , x1 , . . . , x` i.
T follows the strategy of Fig. 2: After the first inconsistent example, x−
1 , allν-learners are forced to a consistent hypothesis in the neighborhood of ∗n . The
only such hypothesis is obtained from ∗n by setting the k1 -th “bit” to the correct
value. This reduces the distance from the target by one. Each of the remaining
examples forces all learners to set one ∗-bit of their hypothesis to a constant.
After x−` all constants are set correctly and the target is reached.
At first glance, the new and the TD-model show little difference with regard
to monomials, since we can use teaching sets also for ν-learners. However, notevery teaching set could be used for teaching. Even the same teaching set might
fail if the examples are given in the wrong order. For example, consider r∗ = 11∗∗+−−which has a teaching set with x+
0 = 1100, x1 = 1111, x1 = 0100, x2 = 1000.
Teaching those examples in reverse order can lead to the following hypothesis
sequence: 0∗∗∗, 00∗∗, 00∗∗, 00∗∗. The last hypothesis is not only incorrect, it iseven impossible to reach r∗ from it (given the examples taught so far).
As another natural concept class, together with a representation, we consider
the class of all Boolean functions of n variables represented by decision trees. A
decision tree is a binary tree whose internal nodes are labeled with a variable andwhose leaves are labeled either as positive or as negative. An instance x ∈ {0, 1}ntraverses the tree beginning at the root and at each internal node choosing theleft child if that node’s variable is satisfied and the right child otherwise, until
a leaf is reached. Thus each tree represents a concept c ⊆ {0, 1}n containing all
positively classified instances.
Each learner starts at the tree consisting of only one negative leaf. In eachround one leaf may be substituted by an internal node that has two differently
labeled leaves as children. This specifies a relation νDT over all decision trees.
Fact 14. The class of Boolean functions represented as decision trees can betaught without feedback to νDT -learners. The teaching time is linear in the sizeof the tree representation.
The teaching dimension with respect to all Boolean functions is 2n for allconcepts. As we have seen, for ν-learners based on decision trees, teaching canoften be successful with much fewer examples.
One can think of three situations where the above strategy either fails or isinefficient due to lack of feedback: (1) it is impossible to enforce a certain mindchange by ruling out all but one neighbor; (2) correcting a wrong hypothesis
afterwards is cheaper than preventing all possible errors beforehand; (3) there areseveral equivalent, but syntactically different hypotheses in the neighborhood.
We have already seen examples of situations (1) in Fact 9, and of situation (2)in Facts 6 and 7. In the following we construct an example for (3).
We consider monotone 1-decision lists h(y1 , b1 ), . . . , (ym , bm ), (∗, 0)i of variables y1 , . . . , ym and bits bi ∈ {0, 1}. An instance x ∈ {0, 1}n runs through thelist starting at the node (y1 , b1 ) until it satisfies a variable, say yj , in which case

486

F.J. Balbach and T. Zeugmann

it is classified as bj . The default node (∗, 0) classifies all instances as negativethat do not satisfy any of the variables y1 , . . . , ym .
We use two kinds of learners obeying different neighborhood relations. Both
start at a decision list with only a positive default node (∗, 1) whose only neighboris the list h(∗, 0)i with a negative default node. All learners may insert nodes ofthe form (y, 0) in any position of the list. However, restrictions apply with regard
to nodes of the form (y, 1). Learners of the first kind are allowed to substitutethe first node of the hypothesis by an arbitrary positive node or to insert such anode at the beginning of the list. Learners of the second kind may only substitutethe last node or insert at the end of the list. In both cases, the default node mustnot be substituted.
To distinguish the hypotheses of both kinds of learners we label the decisionlists with either B or E specifying whether modifications are allowed at the beginning or at the end of the list, respectively. We have therefore two relations,νB and νE , with exactly one common representation, the initital hypothesish(∗, 1)i. If we join both relations at this point, we get a relation νDL . Thus,a νDL -learner will, after receiving the first negative example, switch to eitherh(∗, 0)iB or h(∗, 0)iE and then act like a νB - or a νE -learner.
Intuitively, examples suitable for νB -learners can lead νE -learners into a deadend hypothesis and vice versa. Hence, it is important for the teacher to knowwhat type of learner he teaches. This can be recognized by the B/E-extension of
the hypotheses, which requires feedback.
Fact 15. The class of monotone 1-decision lists can be taught to νDL -learners
with feedback using m + 1 examples for a list of length m. It cannot be taught
without feedback.

6. Comparison with Learning
Such comparisons have been done in the mistake bound model between
teacher-directed learning and self-directed learning. In many natural concept
classes, the best learner can always learn with fewer mistakes than the bestteacher needs to teach all consistent learners [12, 9, 11]. Rivest und Yin [16] use
cryptographic assumptions to construct a concept class where a teacher needs
less examples than the best learner, if both are restricted to polynomial timealgorithms. Ben-David and Eiron [7] construct such classes without relying on
cryptographic assumptions.
Teaching and learning can also be compared according to the sample complexity instead of the mistake bound. This amounts to a comparison of theteaching dimension TD with the number MEMB of membership queries necessary. Goldman and Kearns [9] observed that for all C, MEMB (C) ≥ TD(C), i.e.,being taught is generally simpler than learning by oneself. This contrasts withthe mistake bound model.
We will have a brief look at how the introduction of the ν-relation influences
the relationship between teaching and learning. To do so, we give the ν-learners
access to a membership oracle. Note that still all conditions of Definition 1 apply.

Teaching Learners with Restricted Mind Changes

487

For example, a ν-learner must try to change his mind when the oracle’s answer
is inconsistent with the current hypothesis.
The next two facts demonstrate that in our model teachability and learnability can be rather different.
Fact 16. There are a class C with representation language R and a ν ⊆ R × R
such that C can be taught to all ν-learners, but no ν-learner can learn it.
Proof. Let X = {x1 , x2 , x3 }, c0 = ∅, c1 = {x1 }, c2 = {x1 , x3 }, c3 = {x2 },c4 = {x2 , x3 } and R = {r0 , r1 , r2 , r3 , r4 } with ri representing ci . Finally, ν
contains (r0 , ri ) for i = 1, 2, 3, 4.
The concept c1 can be taught using the instances x3 , x1 ; c2 by x2 , x3 ; c3 by
x3 , x2 ; and c4 by x1 , x3 . Thus C can be taught without feedback to ν-learners.
Assume there is a ν-learner L with access to a membership oracle.
Case 1. L first queries x1 . On answer “1”, L must change its hypothesis toeither r1 or r2 . If L chooses r1 than it cannot learn c2 since there is no way backto r0 . Similar, if r2 is chosen, L cannot learn c1 any more.
Case 2. L first queries x2 . Analogous to Case 1 with concepts c3 and c4 .
Case 3. L first queries x3 . Analogous to Case 1 with concepts c2 and c4 .
Fact 17. There are a class C with representation language R and a ν ⊆ R × R
such that C can be learned by a ν-learner, but cannot be taught to all ν-learners.
Proof. Let X = {x1 , x2 }, c0 = ∅, c1 = {x1 }, c2 = {x1 , x2 }, and let R ={r0 , r1 , r10 , r2 } with ri representing ci and additionally r10 representing c1 . Let
ν = {(r0 , r1 ), (r0 , r10 ), (r1 , r2 )}.
A ν-learner works as follows. First query x1 . If the answer is “0”, then thetarget must be c0 and L stops. If the answer is “1”, change to hypothesis r1 andquery x2 . If the answer is “0”, the target is c1 and L stops, otherwise L switches
to r2 and stops. Hence, this ν-learner learns C.
Let T be a teacher. We show that T cannot teach c2 . Let z be the firstexample taught. If z = (x1 , 1) there is a ν-learner going to r10 from where r2
cannot be reached. Consequently, T has to begin with z = (x2 , 1) which causes
no hypothesis change. As soon as T teaches (x2 , 1) there is a learner switching
to r10 . This learner will never reach r2 . Thus, C cannot be taught.

7. Conclusion and Further Research
In our model several effects regarding feedback can be observed. Feedback
can be useless, helpful, or even indispensable for teaching. In addition, natural
infinite concept classes can be taught in this model and the relationship between
teachability and learnability is more diverse than in the TD-model.
The variety of possible results stems mostly from the ability to define ν arbitrarily. We have also used rather artificial ν’s in some places. It would therefore
be interesting to put some natural restrictions on ν, e.g., some relation between
syntax (distance in the (R, ν)-graph) and semantics (number of errors).

488

F.J. Balbach and T. Zeugmann

The strategy of Section 5, which often makes teaching without feedback possible, relies on the (somewhat unrealistic) feature of our models that all learners
remember all examples (especially the consistent ones). It seems natural to study
feedback for learners with some sort of memory limitation.
Further directions of research include adding computability restrictions to
the teachers and/or learners, teaching with only positive examples, and othertypes of feedback, e.g., answering teacher’s questions.
Acknowledgments. The authors heartily thank the anonymous referees formany valuable comments. The second author has been supported by the 21stCentury COE Program C01.

References[1] D. Angluin. Queries and concept learning. Machine Learning, 2(4):319–342, 1988.
[2] D. Angluin. Queries revisited. In Algorithmic Learning Theory, 12th International
Conference, ALT 2001, Proc., vol. 2225 of Lecture Notes in Artificial Intelligence,
pages 12–31. Springer, 2001.
[3] D. Angluin and M. Kriķis. Teachers, learners and black boxes. In Proc. 10th
Annual Conference on Computational Learning Theory, pages 285–297, ACM
Press, New York, NY, 1997.
[4] D. Angluin and M. Kriķis. Learning from different teachers. Machine Learning,
51(2):137–163, 2003.
[5] M. Anthony, G. Brightwell, D. Cohen, and J. Shawe-Taylor. On exact specification
by examples. In Proc. 5th Annual ACM Workshop on Computational Learning
Theory, pages 311–318. ACM Press, New York, NY, 1992.
[6] F.J. Balbach and T. Zeugmann. Teaching Learners that can only Perform Restricted Mind Changes, TCS Technical Report, Series A, TCS-TR-A-05-5, Division of Computer Science, Hokkaido University, July 18, 2005.
[7] S. Ben-David and N. Eiron. Self-directed learning and its relation to the VC-dimension and to teacher-directed learning. Machine Learning, 33(1):87–104, 1998.
[8] R. Freivalds, E. B. Kinber, and R. Wiehagen. Learning from good examples. In
Algorithmic Learning for Knowledge-Based Systems, vol. 961 of Lecture Notes in
Artificial Intelligence, pages 49–62. Springer, 1995.
[9] S. A. Goldman and M. J. Kearns. On the complexity of teaching. J. of Comput.
Syst. Sci., 50(1):20–31, 1995.
[10] S. A. Goldman and H. D. Mathias. Teaching a smarter learner. J. of Comput.
Syst. Sci., 52(2):255–267, 1996.
[11] S. A. Goldman, R. L. Rivest, and R. E. Schapire. Learning binary relations andtotal orders. SIAM J. Comput., 22(5):1006–1034, Oct. 1993.
[12] S. A. Goldman and R. H. Sloan. The power of self-directed learning. Machine
Learning, 14(3):271–294, 1994.
[13] J. Jackson and A. Tomkins. A computational model of teaching. In Proc. 5th
Annual ACM Workshop on Computational Learning Theory, pages 319–326. ACM
Press, New York, NY, 1992.
[14] S. Jain, S. Lange, and J. Nessel. Learning of r.e. languages from good examples. In
Algorithmic Learning Theory, 8th International Workshop, ALT ’97, Proc., vol.
1316 of Lecture Notes in Artificial Intelligence, pages 32–47. Springer, 1997.

Teaching Learners with Restricted Mind Changes

489[15] H. D. Mathias. A model of interactive teaching. J. of Comput. Syst. Sci.,
54(3):487–501, 1997.
[16] R. L. Rivest and Y. L. Yin. Being taught can be faster than asking questions. In
Proc. 8th Annual Conference on Computational Learning Theory, pages 144–151.
ACM Press, New York, NY, 1995.
[17] A. Shinohara and S. Miyano. Teachability in computational learning. New Generation Computing, 8(4):337–348, 1991.