TCS -TR-A-05-5

TCS Technical Report

Teaching Learners that can only Perform Restricted
Mind Changes

byFrank J. Balbach and Thomas Zeugmann

Division of Computer Science
Report Series A
July 18, 2005

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

thomas@ist.hokudai.ac.jp

Phone:
Fax:+81-011-706-7684+81-011-706-7684

Teaching Learners that can only Perform Restricted
Mind Changes
Frank J. BalbachThomas Zeugmann

Institut für Theoretische Informatik

Division of Computer Science

Universität zu Lübeck

Hokkaido University

Ratzeburger Allee 160

N-14, W-9

23538 Lübeck, Germany

Sapporo 060-0814, Japanbalbach@tcs.uni-luebeck.de

thomas@ist.hokudai.ac.jp

Abstract
Within algorithmic learning theory teaching has been studied in various
ways. In a common variant the teacher has to teach all learners that are restricted to output only consistent hypotheses. The complexity of teaching isthen measured by the maximum number of mistakes a consistent learner canmake until successful learning. This is equivalent to the so-called teaching dimension. However, many interesting concept classes have an exponential teaching dimension and it is only meaningful to consider 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 areeither required to teach finitely or in the limit. Moreover, the variant that theteacher 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 shown that
feedback can be very helpful. Moreover, within the new model one can also
study the teachability of infinite concept classes with potentially infinite concepts such as languages. Finally, it is shown that in our model teachability andlearnability 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 have some 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.

12Frank J. Balbach and Thomas Zeugmann

In the first approach, the goal is to find a teacher and a learner such that a given
learning task can be carried out by them. For the inductive inference framework,
Freivalds Kinber, and Wiehagen [7] and Jain, Lange, and Nessel [13] developed amodel in which a rather implicit teacher provides the learning strategy with good
examples. Jackson and Tomkins [12] as well as Goldman and Mathias [9, 14] definedmodels of teacher/learner pairs where teachers and learners are constructed explicitly.
In all these models, some kind of adversary disturbing the teaching process is necessary
to avoid collusion between the teacher and the learner. Angluin and Kriķis’ [3, 4]
model prevents collusion by giving incompatible hypothesis spaces to teacher andlearner. 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, Rivest, and Shapire [10] and Goldman and Kearns[8] substitute the adversarial teacher in the online learning model by a helpful one
selecting good examples. They investigate how many mistakes a consistent learner canmake in the worst case. In Shinohara and Miyano’s [16] model the teacher produces
a set of examples for the target concept such that it is the only consistent one in theconcept 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 not knowing
anything about the learners besides them being consistent. In reality a teacher canbenefit a lot from knowing the learners’ behavior or their current hypotheses. It istherefore natural to ask how teaching can be improved if the teacher may observe thelearners’ hypotheses after each example.
After translating this question into the TD-model, one sees that there is no gainin 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 basically two 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 a difference. 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 infinite classes
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Teaching Learners that can only Perform Restricted Mind Changes

3

unteachable in the TD-model. With appropriate neighborhood relations this class canbe 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 functions andΣ∗ for languages over a finite and non-empty alphabet Σ. By X = X × {0, 1} wedenote 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}
such that C = {Cr r ∈ R}, where Cr = {x γ(r, x) = 1}. The length of r is denoted
by |r| and size(c) := min{|r| Cr = c} for every c ∈ C. For any set S, we denoteby card(S) its cardinality and by S ∗ the set of all finite tuples over S. We use thesymbols ◦ for concatenation of tuples and 4 for the symmetric difference of 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 eachround the teacher provides an example to the learner who then computes a hypothesis
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 graph and we
define the neighborhood of r ∈ R as Nb(r) := {s ∈ R (r, s) ∈ ν} ∪ {r} and denoteby 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, wehave 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 asmaller error. This ensures that L will not change its mind after reaching a correct
hypothesis. On the other hand, we also require L to search for a better hypothesis if4Frank J. Balbach and Thomas Zeugmann

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 is afunction L : X ∗ → R such that 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 consistentexample if its hypothesis is inconsistent with an example received earlier. In thispaper, 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 ) andzi = 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∈N ofhypotheses converges to an h with Ch = Cr .
The teaching time of T on r is the maximum i such that there is a ν-learner L thatreaches 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 then given
by hi+1 = L(T (r, 0), . . . , T (r, i)). With this notation the definition of teaching in thelimit without feedback is literally the same as Definition 2.

N

In the situation with feedback the teacher can stop teaching as soon as the learnerhas reached the goal. If there is no feedback, the teacher may or may not know
when to stop. A teacher stopping after finitely many examples and still ensuring thelearning success is said to teach finitely without feedback. More formally we consider
T : R × → X ∪ {⊥} where ⊥ means “teaching has stopped.”

N

With feedback we do not need to distinguish teaching finitely from teaching in thelimit and we shall call this kind of teaching simply teaching with feedback.

Teaching Learners that can only Perform Restricted Mind Changes

5

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 .
If we set ν = R × R in Definition 3 then we have essentially the teacher-directed
learning model from Goldman, Rivest and Schapire [10] which has no restriction
on hypothesis changes. The following theorem justifies the use of arbitrary ν’s forstudying the impact of feedback on the teaching process.
Theorem 1. 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 feedback forν = R × R and let c ∈ C. We first prove that for all c ∈ C, TD(c) < ∞. Suppose
there is a c∗ ∈ C with TD(c∗ ) = ∞. Then there is a ν-learner L always assuming aconsistent hypothesis not representing c∗ . This is possible because there is no finite
set of examples specifying c∗ and because every hypothesis can be reached from every
other. Obviously L cannot be taught c∗ in the limit, not even with feedback; acontradiction.
Now, since all teaching dimensions are finite, we can define a teacher T that outputs
for each c ∈ C a teaching sequence and stops. Teacher T does not need any feedback.
Obviously, teacher T teaches C to all ν-learners finitely and without feedback, because
at the end of teaching there is only one consistent hypothesis left which is certainly
reachable.
In order to see that teacher T has optimal teaching time for c ∈ C with respect toall three teaching models, we consider a ν-learner L that always outputs a consistenthypothesis not representing concept c, unless c is the only consistent concept in whichcase L outputs a representation for c. It is easy to see that concept c cannot be taught
to learner L with less than TD(c) examples, no matter whether or not feedback isallowed.
Note that Theorem 1 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 shall investigate in a forthcoming paper.

6Frank J. Balbach and Thomas Zeugmann

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
Prepresents the language {w1 , . . . , wm }. To simplify proofs later, we set |r| := mi=1 |wi |,i.e., without counting the commas. We define the allowed transitions from r to sby ((r, s) ∈ ν) iff card(Cr 4 Cs ) ≤ 1. The initial hypothesis is the empty string εrepresenting the empty concept. Now we have:
Fact 2. Cfin is finitely teachable to ν-learners without feedback.
Proof. For a finite language with representation w1 , . . . , wm a teacher simply provides 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 themto 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 requirethat the size of the hypotheses may at most double each round: |s| ≤ 2|r|. In thespecial case r = ε we allow every singleton concept as neighbor: (ε, s) ∈ ν for all swith card(Cs ) = 1. For ν 0 -learners there is a big difference in teaching time between
teaching with and without feedback.
Fact 3. 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 tothe hypothesis and “invent” another string and add it to the hypothesis as well. Dueto 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 first teaches
all strings wi as positive examples. After wm the hypothesis of each learner containsc∗ plus at most m invented strings u1 , . . . , u` . From the feedback, the teacher getsto 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 4. Cfin is finitely teachable to ν 0 -learners without feedback. Every suchteacher needs Ω(2size(c) ) examples for some c ∈ C and there is no upper bound for thenumber of examples that depends only on card(c).

Teaching Learners that can only Perform Restricted Mind Changes

7

Proof. A suitable teacher is defined as follows. Let c ∈ Cfin . First of all, the teacher
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 as positive 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 these strings either have been ruledout 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} aconcept 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 mustoccur 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 of am and let zj2 = (b, 1) be thefirst 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∗ with |ŵ| ≤ m−1
which is not taught. We give a ν 0 -learner L that does not arrive at c∗ during teaching.
On zj1 , L switches to hypothesis hj1 +1 = am and does not change it until zj2 arrives.
Then L chooses the hypothesis hj2 +1 = am , b, ŵ which is incorrect, but consistent withthe examples so far. The length restriction is obeyed, since size(am ) = m = |b| + |ŵ|.
From then on, L will never change the hypothesis, 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 of examples
needed that depends on card(c∗ ) only.
If we remove the size restriction from ν 0 we yield ν 00 .
Fact 5. 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 acorrect 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 stringsin the hypothesis of a ν 00 -learner. T observes these strings and gives them as negative8Frank J. Balbach and Thomas Zeugmann

examples, thus forcing all learners to remove the excessive strings and to reach thecorrect 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 canbe removed in the limit.
Finally we define ν 000 . It differs from ν 00 in that a string may only be removed fromthe hypothesis if neither its predecessor nor its successor (wrt. the fixed ordering onΣ∗ ) is contained in the hypothesis.
Fact 6. Cfin is not teachable to ν 000 -learners in the limit without feedback, but it isfinitely 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 sequence of
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 be taught. Letzji = (wi , 1) be first occurrence of wi for i = 1, 2, 3. Without loss of generality, 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 asa 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 of which 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. Letc∗ ∈ Cfin be the target concept. The teacher first teaches all negative examples thatare 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 stringu into the hypothesis, the negative example (u, 0) is given. The string u cannot bepredecessor or successor of any other string in the hypothesis and is thus deleted fromthe 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 is finitely
teachable without feedback, with feedback or in the limit, respectively, we have justproved the following theorem.
Theorem 7. 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 ν can lead to different
teaching times for the same C.

Teaching Learners that can only Perform Restricted Mind Changes

9

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 teaching set, namely if
ν = R × R (see [16, 8, 5]).
Concept classes over finite instance spaces can always be taught in the TD-model.
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 andcard(X) + card(R) columns. Each row describes the represented concept in the firstcard(X) bits, and its neighborhood in the last card(R) bits (cf. Fig 1).

r0
r1
r2
r3
s0
s1
s2
s3
s4
s∗

x1 x̄1 x2 x̄2 x3 x̄3 x4 x̄41 1 1 1 1 1 1 1
0 1 1 0 0 1 1 1
0 1 0 1 1 1 0 1
1 0 1 1 0 1 1 0
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
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 r 1 r 2 r 3 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

Figure 1: Example for the reduction in Theorem 8 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 ν.
Theorem 8. 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. (Theorem 8). The proof is by reduction from 3-SAT. Let F = K1 ∧· · · ∧ Km be a formula in 3-CNF with clauses K1 , . . . , Km and variables v1 , . . . , vn .
Define XF , CF , RF and νF as follows. XF contains instances x1 , x̄1 , . . . , xn , x̄n andy1 , y10 , . . . , yn , yn0 and an instance w, hence card(XF ) = 4n + 1. RF contains therepresentations 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 repre0
sents 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 the target

10Frank J. Balbach and Thomas Zeugmann

hypothesis is r0 , s0 , s1 , . . . , sn , s∗ . If one of the ri ’s is reached, teaching has failed asthese 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 to showthat 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 mind change 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 tos1 . Similarly one can see that after teaching y2 , y20 , . . . , yn , yn0 all learners have reached
sn . Now each missing positive example triggers a mind change to s∗ . This shows thatc∗ is teachable.
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 both xi andx̄i have been taught. To prove this we show that if for some i both xi and x̄i havebeen taught, then it is impossible to force all learners to reach s∗ . Finally we definea satisfying assignment β depending, for each i, on whether xi or x̄i occurs in thesample.
As long as the teacher teaches examples different from w, r0 is consistent and nomind change happens. Therefore, for some k, zk = (w, 1). At this point a mind changemust happen. If there were no mind change, all neighbors of r0 , i.e., r1 , . . . , rm , s0 ,had more errors than r0 . This cannot be repaired, thus all learners 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 allneighbors 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 . The point now is that if x1 and x̄1 occur in thesample, s1 has two errors, but if only one of these examples occurs, s1 has only one
error. If the hypothesis is to be switched to s1 , the teacher 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

11

Teaching Learners that can only Perform Restricted Mind Changes

x1 , x̄1 , y1 , y10 , such errors can only be generated by teaching y1 as well as y10 . But eventhen, the mind change can only be performed if s1 has less than two errors. Thus,
since s1 is reached via the example sequence, it follows that not both x1 and x̄1 havebeen taught.
In a similar way it can be shown that si+1 can only be reached from si if not bothxi+1 and x̄i+1 appear in the sample. Note that teaching xi or x̄i after the learners havereached si is possible, but does not influence the following mind changes, because theconcepts si+1 , . . . , sn are identical wrt 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-definedby β(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 whatever x-examples havebeen taught before w. Thus, rj is an equally good neighbor as s0 and there will bea νF -learner choosing rj instead of s0 . But this is a contradiction to the assumptionthat all such learners reach s∗ .
For infinite instance spaces or infinite classes (and infinite ν) the following theorem
applies.
Theorem 9. 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. Within this proof, we use
as instance space and as representation language. Let C = {{0, . . . , i} i ≥ 1} ∪ { } a concept class. A concept {0, . . . , i} isrepresented by i, 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 must
be reachable in the graph ( , νj ). From the definition of νj it follows that ϕj (j) isdefined.

NN

N

For the opposite direction, let ϕj (j) be defined after r steps. Then
can betaught by the example sequence (2, 1), . . . , (r, 1), (r + 2, 1), where the last example
ensures that 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 to the
hypothesis 0.

12Frank J. Balbach and Thomas Zeugmann

5. Teaching Without Feedback
A teacher T without feedback knows all learners’ initial hypotheses h0 , but canquickly lose track of them during teaching. On the other hand, T can rule out neighbors r of h0 by giving examples consistent with h0 , but inconsistent with r. If insuch a way T can eliminate all but one neighbor r0 , he effectively forces all learners toswitch to r0 . By continuing in this manner, T always knows all learners’ 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;Figure 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 not need tobe finite, the condition in Step 2 does not need to be checked. Albeit simple, thestrategy works surprisingly often for natural concept classes and ν-restrictions. In thefollowing we give some examples.
First, we consider the class of all monomials over n variables. Let R = {0, 1, ∗}nand define (r, s) ∈ ν iff r and s differ only in one “bit.” As initial hypothesis h0 = ∗n
is used.
Fact 10. 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 [8, 16]). 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 ki where theki -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 νnlearners are forced to a consistent hypothesis in the neighborhood of ∗ . The only
such hypothesis is obtained from ∗n by setting the k1 -th “bit” to the correct value.

Teaching Learners that can only Perform Restricted Mind Changes

13This 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−` allconstants are set correctly and the target is reached.
At first glance, the new and the TD-model show little difference with regard tomonomials, since we can use teaching sets also for ν-learners. However, not every
teaching set could be used for teaching. Even the same teaching set might fail if theexamples 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 thoseexamples in reverse order can lead to the following hypothesis sequence: 0∗∗∗, 00∗∗,00∗∗, 00∗∗. The last hypothesis is not only incorrect, it is even impossible to reachr∗ from it (given the examples taught so far).
As another natural concept class, together with a representation, we consider theclass 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 and whose leaves
are labeled either as positive or as negative. An instance x ∈ {0, 1}n traverses the tree
beginning at the root and at each internal node choosing the left child if that node’s
variable is satisfied and the right child otherwise, until a leaf is reached. Thus eachtree 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 each roundone 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 11. The class of Boolean functions represented as decision trees can betaught without feedback to νDT -learners. The teaching time is linear in the size of thetree representation.
Proof. Let c∗ be a Boolean function over n variables v1 , . . . , vn represented by adecision tree D∗ . Without loss of generality we can assume that (1) for a node with
two leaves as children, both leaves are differently labeled, (2) on each path from theroot to a leaf each variable occurs at most once, and (3) for all internal nodes both
subtrees are semantically different. From this follows that for all internal nodes tcontaining a variable vk exist x− , x+ ∈ {0, 1}n such that x+ ∈ c∗ , x− ∈/ c∗ ; x− and x+
reach t and differ only in the k-th bit.
The basic idea of the teaching algorithm is to force all learners to build their
hypothesis identical to D∗ . Beginning with the root node, with each hypothesis change
a leaf in the hypothesis is substituted by the “correct” node of D∗ . Substitution ofa leaf by a node t can be caused by teaching x− and x+ as defined above. Moreprecisely:
1. r := tree consisting of a negative leaf only;
2. G := {the only node of r};
3. while r 6= D∗ :

14Frank J. Balbach and Thomas Zeugmann

3.1 Let g ∈ G be a leaf of r with label b;
3.2 Let t be the root of the subtree of D∗ by which g must be substituted inorder to construct D∗ from r;
3.3 Let vk be the variable in t;
3.4 Find x− , x+ as described above;
3.5 Let ĝ be the tree with root t and two child leaves that correctly classifies
x− and x+ ;3.6 r := r after replacing g by ĝ;
3.7 Teach the x ∈ {xi , x+ } with c∗ (x) = b;
3.8 Teach the x ∈ {xi , x+ } with c∗ (x) 6= b;
3.9 G := (G \ {g}) ∪ {` ` is a leaf of ĝ that is not in D∗ };The correctness is implied by the following invariants which hold at the beginningof each iteration of the while loop:
1. G 6= ∅;2. D∗ can be built from r by substituting all leaves in G by suitable subtrees of D∗ ;3. r is a hypothesis consistent with all examples taught so far and is also the
hypothesis of all ν-learners.
The algorithm terminates since r strictly grows in size with each iteration until
it equals D∗ . Note that r cannot “go astray” because of invariant 2. Therefore, thenumber of iterations is two times the number of internal nodes of D∗ .
We sketch the proof of the invariants which trivially hold before the first iteration.
Assume the invariants hold at the beginning of an iteration. Since G 6= ∅, there is aleaf g ∈ G of r with a label b. From invariant 2 follows that there is a subtree of D∗with root t by which g must be substituted in order to build D∗ . Then the path fromthe root of r to t also is in D∗ , hence there are instances x− , x+ reaching t such thatx− ∈/ c∗ , x+ ∈ c∗ , and only differing in the k-th bit. Both instances also reach g in r
and are classified as b. Therefore, the example taught in step 3.7 is consistent with r,
but the example from 3.8 is not.
Denote by r0 the tree resulting from replacing g in r by ĝ (step 3.6). We showthat r0 is the only ν-neighbor of r consistent with all examples including x− and x+ .
Replacing any other node than g does not change the way x− and x+ are classified.
Such a hypothesis would remain inconsistent with one of these examples. Replacing
g by a node with different variable than vk would also classify one of the instancesx− , x+ wrong since they differ only wrt. variable vk . Hence, all ν-learners assume r0
as their next hypothesis, which proves invariant 3.

Teaching Learners that can only Perform Restricted Mind Changes

15

Since t is a node from D∗ which has been put “in the right place” in r, it is still
possible to complete r with subtrees of D∗ which shows invariant 2.
G = ∅ can only happen, if there are no more leaves of r to be replaced, that is if
r = D∗ . In this case the loop terminates and there is no next iteration, hence nothing
to prove for invariant 1.
The teaching dimension with respect to all Boolean functions is 2n for all concepts.
As we have seen, for ν-learners based on decision trees, teaching can often be successful
with much fewer examples.
One can think of three situations where the above strategy either fails or is inefficient due to lack of feedback: (1) it is impossible to enforce a certain mind change
by ruling out all but one neighbor; (2) correcting a wrong hypothesis afterwards ischeaper than preventing all possible errors beforehand; (3) there are several equivalent, but syntactically different hypotheses in the neighborhood.
We have already seen examples of situations (1) in Fact 6, and of situation (2) in
Facts 3 and 4. For completing the picture, in the following we construct an example
for situation (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 the list startingat the node (y1 , b1 ) until it satisfies a variable, say yj , in which case it is classified as
bj . The default node (∗, 0) classifies all instances as negative that do not satisfy anyof the variables y1 , . . . , ym .
We use two kinds of learners obeying different neighborhood relations. Both startat a decision list consisting of only a positive default node (∗, 1) whose only neighboris the list h(∗, 0)i with a negative default node. All learners may insert nodes of theform (y, 0) in any position of the list. However, restrictions apply with regard to nodesof the form (y, 1). Learners of the first kind are allowed to substitute the first node of
the hypothesis by an arbitrary positive node or to insert such a node at the beginningof the list. Learners of the second kind may only substitute the last node or insert at
the end of the list. In both cases, the default node must not be substituted.
To distinguish the hypotheses of both kinds of learners we label the decision lists
with either B or E specifying whether modifications are allowed at the beginning orat the end of the list, respectively. We have therefore two relations, νB and νE , withexactly one common representation, the initital hypothesis h(∗, 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 either h(∗, 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 dead end
hypothesis and vice versa. Hence, it is important for the teacher to know what type

16

Frank J. Balbach and Thomas Zeugmannof learner he teaches. This can be recognized by the B/E-extension of the hypotheses,
which requires feedback.
Fact 12. 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.
Proof. We present an outline of the proof. We first describe a teacher T using
feedback. Let c∗ be a Boolean function over n variables represented by a monotone 1decision list D∗ = h(y1 , b1 ), . . . , (ym , bm ), (∗, 0)i. Without loss of generality we assume
that D∗ is in reduced form, that is (1) each variable occurs at most once (either as
positive or negative literal), (2) the default node is negative, (3) bm = 1 (otherwise(ym , bm ) can be removed without changing the represented concept).
T first teaches (0n , 0). This makes all νDL -learners switch to h(∗, 0)iB or h(∗, 0)iE .
The behavior of T depends on the type (B/E) of the learner.
Type B: For all j = m, . . . , 1 the teacher gives examples (xj , bj ) such that xj satisfies
yj and yk , where k > j is the minimum index with bk 6= bj , i.e., the next node to theright with a different bit (or the default node, if j = m).
It can be shown by induction over j that these examples enforce the constructionof the list beginning from the rightmost node. Intuitively an example xj proves thatyj is a relevant variable and triggers a mind change by being inconsistent.
Type E: For all j = 1, . . . , m with bj = 1 the teacher gives an example (xj , 1) wherexj satisfies only yj . On these examples all learners build a decision list containing all
positive nodes of D∗ in the right order.
To force the inclusion of the negative nodes, T presents a sequence of negative
examples. For each negative node (yj , 0) (from left to right) T teaches an example(xj , 0) such that xj satisfies yj and yk , where (yk , 1) is next positive node to the right.
This example causes the inclusion of the node (yj , 0) at the correct position in the
hypothesis.
For both types the teaching time is m + 1.
Assume for a contradiction that there is a teacher T not using feedback. Let
D = h(v1 , 1), (v2 , 0), (v3 , 1), (∗, 0)i be the target decision list. Note that there is noother monotone 1-decision list equivalent with D∗ .
∗Since both neighbors of the initial hypothesis represent the same concept, T cannot
enforce just one of them. Hence, there exist νDL -learners LB and LE going to h(∗, 0)iB
and h(∗, 0)iE , respectively, on the example sequence taught. Now, LE must continue
with hypothesis DE0 := h(v1 , 1), (∗, 0)iE since there is no other way to reach D∗ for a
type-E learner. However, DB0 is also a neighbor of LB ’s hypothesis, because insertingat the beginning is equivalent to inserting at the end of the list h(∗, 0)i. Thus, LB
can reach DE0 , but this is a dead end, as (v3 , 1) has to be inserted after (v1 , 1) which
is impossible for LB .

Teaching Learners that can only Perform Restricted Mind Changes

17

6. Comparison with Learning
Such comparisons have been done in the mistake bound model between teacherdirected learning and self-directed learning. In many natural concept classes, the bestlearner can always learn with fewer mistakes than the best teacher needs to teach allconsistent learners [11, 8, 10]. Rivest und Yin [15] use cryptographic assumptions toconstruct a concept class where a teacher needs less examples than the best learner, if
both are restricted to polynomial time algorithms. Ben-David and Eiron [6] 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 the teaching dimension
TD with the number MEMB of membership queries necessary. Goldman and Kearns[8] observed that for all C, MEMB (C) ≥ TD(C), i.e., being taught is generally simpler
than learning by oneself. This contrasts with the mistake bound model.
We will have a brief look at how the introduction of the ν-relation influences therelationship between teaching and learning. To do so, we give the ν-learners access toa membership oracle. Note that still all conditions of Definition 1 apply. For example,a ν-learner must try to change his mind when the oracle’s answer is inconsistent withthe current hypothesis.
The next two facts demonstrate that in our model teachability and learnability canbe rather different.
Fact 13. 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 to either
r1 or r2 . If L chooses r1 than it cannot learn c2 since there is no way back to 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 14. 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 }, and let c0 = ∅, c1 = {x1 }, c2 = {x1 , x2 }. Furthermore,
let R = {r0 , r1 , r10 , r2 } with ri representing ci and additionally r10 representing c1 . Let
ν = {(r0 , r1 ), (r0 , r10 ), (r1 , r2 )}.

18

Frank J. Balbach and Thomas ZeugmannA ν-learner works as follows. First query x1 . If the answer is “0”, then the target
must be c0 and L stops. If the answer is “1”, change to hypothesis r1 and query 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 first example
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 neverreach r2 . Thus, C cannot be taught.

7. Conclusion and Further Research
In our model several effects regarding feedback can be observed. Feedback canbe 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 inthe (R, ν)-graph) and semantics (number of errors).
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 forlearners with some sort of memory limitation.
Further directions of research include adding computability restrictions to theteachers and/or learners, teaching with only positive examples, and other types of
feedback, e.g., answering teacher’s questions.
Acknowledgments. The second author heartily acknowledges support 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.

Teaching Learners that can only Perform Restricted Mind Changes

19[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] S. Ben-David and N. Eiron. Self-directed learning and its relation to the VCdimension and to teacher-directed learning. Machine Learning, 33(1):87–104,
1998.
[7] 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.
[8] S. A. Goldman and M. J. Kearns. On the complexity of teaching. J. of Comput.
Syst. Sci., 50(1):20–31, 1995.
[9] S. A. Goldman and H. D. Mathias. Teaching a smarter learner. J. of Comput.
Syst. Sci., 52(2):255–267, 1996.
[10] S. A. Goldman, R. L. Rivest, and R. E. Schapire. Learning binary relations andtotal orders. SIAM J. Comput., 22(5):1006–1034, Oct. 1993.
[11] S. A. Goldman and R. H. Sloan. The power of self-directed learning. Machine
Learning, 14(3):271–294, 1994.
[12] 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.
[13] 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.
[14] H. D. Mathias. A model of interactive teaching. J. of Comput. Syst. Sci.,
54(3):487–501, 1997.
[15] 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.
[16] A. Shinohara and S. Miyano. Teachability in computational learning. New Generation Computing, 8(4):337–348, 1991.