Teaching Randomized Learners with Feedback
Frank J. Balbacha,2 , Thomas Zeugmann∗,b,1
a Pattern Science AG, Freigericht, Germanyb Division of Computer Science, Hokkaido University, Sapporo 060-0814, Japan

Abstract
The present paper introduces a new model for teaching randomized learners. Our newmodel, though based on the classical teaching dimension model, allows to study the influence of the learner’s memory size and of the presence or absence of feedback. Moreover,in the new model the order in which examples are presented may influence the teachingprocess.
The resulting models are related to Markov decision processes, and characterizationsof optimal teachers for memoryless learners with feedback and for learners with infinite
memory and feedback are shown.
Furthermore, in the new model it is possible to investigate new aspects of teaching liketeaching from positive data only or teaching with inconsistent teachers. Characterization
theorems for teachability from positive data for both ordinary teachers and inconsistentteachers with and without feedback are provided.
Key words: Algorithmic teaching, randomized algorithms, computational complexity

1. Introduction
When preparing a lecture, a good teacher carefully selects informative examples.
Additionally, a good teacher takes into account that students do not memorize everything
previously taught. And usually we make a couple of assumptions about the learners. For
example, They should neither be ignorant nor should they be lazy. Thus, it is only
natural to ask whether or not such human behavior is at least partially reflected in somealgorithmic learning and/or teaching models studied so far in the literature.
Learning concepts from examples has attracted considerable attention in learningtheory and machine learning. Typically, a learner does not know much about the sourceof these examples. Usually the learner is required to learn from all such sources, regardless of their quality. This is even true for the query learning model introduced by∗ Corresponding author

Email addresses: frank-balbach@gmx.de (Frank J. Balbach), thomas@ist.hokudai.ac.jp (Thomas
Zeugmann)
1 Supported by MEXT Grant-in-Aid for Scientific Research on Priority Areas under Grant
No. 21013001.
2 This research was done at the Institute for Theoretical Computer Science, University Lübeck, Germany
Preprint submitted to Elsevier
November 26, 2010

Angluin [1, 2], since the teacher or oracle, though answering truthfully, is assumed tobehave adversarially whenever possible. Therefore, it was only natural to ask whether
or not one can also model scenarios in which a helpful teacher is honestly interested in
the learner’s success.
Perhaps the first approach was proposed by Freivalds, Kinber, and Wiehagen [3, 4].
They developed a learning model in the inductive inference paradigm of identifying recursive functions in which the learner is provided with good examples chosen by an implicitly
given teacher. Jain, Lange, and Nessel [5] adopted this model to learn recursively enumerable languages from good examples in the inductive inference paradigm.
The next step was to consider teaching as the natural counterpart of learning. Teaching has been modeled and investigated in various ways within algorithmic learning theory.
However, the more classical models studied so far all follow one of two basically different
approaches.
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. Jackson and Tomkins [6] as well as Goldman
and Mathias [7] and Mathias [8] defined models 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 andthe learner. That is, when modeling teaching, a major problem consists in avoiding
coding tricks. Though there is no generally accepted definition of coding tricks, it will
be clear from our exposition that no form of coding tricks is used and thus no collusion
occurs.
Angluin and Kriķis’ [9, 10] model prevents collusion by giving incompatible hypothesis spaces to the teacher and the learner. This makes simple encoding of the target
impossible.
In the second approach, a teacher has to be found that teaches all deterministic
consistent learners. Here a learner is said to be consistent if its hypothesis correctly andcompletely reflects all examples received. This prevents collusion, since teaching happens
the same way for all learners and cannot be tailored to a specific one. Goldman, Rivest,
and Shapire [11] as well as Goldman and Kearns [12] substitute the adversarial teacher
in the online learning model by a helpful one selecting good examples. They investigate
how many mistakes a consistent learner can make in the worst case. In Shinohara andMiyano’s [13] model the teacher produces a set of examples for the target concept suchthat it is the only consistent one in the concept class. The size of this set is the sameas the worst case number of mistakes in the online model. This number is termed theteaching dimension of the target. Because of this similarity, from now on, we shall refer
to both models as the teaching dimension model (abbr. TD model).
By varying the set of admissible learners, the influence of different properties of thelearners on the teaching process can be studied. For example, learners with limited
memory should be harder to teach, whereas learners that show their current hypothesis
to the teacher should ease the teaching process.
Let us consider the concept class of all Boolean functions over {0, 1}n . To teach aconcept to all consistent learning algorithms, the teacher must present all 2n examples.
Teaching a concept to all consistent learners that can memorize less than 2n examples is
impossible; there is always a learner with a consistent, but wrong hypothesis. So teachinggets indeed harder, but in a rather abrupt way.
A further difficulty of teaching in the TD model results from the fact that the teacher2does not know anything about the learners besides them being consistent. In reality ateacher 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 the teacher may observe
the learners’ hypotheses after each example. We refer to this scenario as teaching withfeedback.
After translating this question into the TD model, one sees that there is no gain in
the 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. So, in the TD model, feedbackis useless.
There are also several other deficiencies in the teaching models studied so far. These
deficiencies include that the order in which the teacher presents examples does not matter,and that teaching infinite concepts or infinite concept classes is severely limited.
Therefore, our goal has been to devise a teaching model that remedies the above
mentioned flaws. In particular, our aim has been to develop a teaching model such thatthe following aspects do matter.
(1) The order in which the teacher presents the information should have an influenceon the performance of the learner.
(2) Teaching should get harder when the memory size of the learners decreases, but itshould not become impossible for small memory.
(3) Teaching should get easier when the learners give feedback to the teacher.
(4) Concepts that are more complex should be harder to teach.
In the present paper we propose a new teaching model that achieves all these goals (1)through (4). Our approach is rather radical. It is based on the observation that the worst
case analysis style makes it impossible to investigate the influence of memory limitations
or learner’s feedback. Instead of following the more common remedy to perform an
average case analysis (cf., e.g., [14, 15, 16, 17]), we replace the set of learners by a single
one that is conceptually intended to represent an “average learner.”
We achieve this goal by substituting the set of deterministic learners by a single randomized one. Basically, such a learner picks a hypothesis at random from all hypotheses
consistent with the known examples. Teaching is successful as soon as the learner hypothesizes the target concept. To ensure that the learner maintains this correct hypothesis,
we additionally require the learner to be conservative, i.e., it can change its hypothesis
only on examples that are inconsistent with its current hypothesis. The complexity ofteaching is measured by the expected teaching time (cf. Section 2).
Next, we explain why this model should work. Intuitively, since at every roundthere is a chance to reach the target, the target will eventually be reached even if, forinstance, the randomized learner can only memorize few examples. Moreover, the abilityof the teacher to observe the learner’s current hypothesis should be advantageous, since
it enables the teacher to teach an inconsistent example in every round. Recall that only
these examples can cause a hypothesis change. In Section 3, we show these intuitions to
be valid.
Randomized learners show another phenomenon, too: The complexity of the teachingprocess now does not only depend on the examples, but also on the order in which they
are given (cf. Section 3).
3The paper is organized as follows. In Section 2 the formal definition of our randomized
teaching framework is provided. We continue with some examples already showing thatthe new models have the properties we aimed for (cf. Section 3).
Then we turn our attention to the main subject of the present paper, i.e., randomized
learners with feedback (cf. Section 4). After explaining how our models can be regarded
as Markov decision processes in Subsection 4.1, we discuss the simplest case, that is,memoryless learners with feedback and derive a characterization for optimal teachers.
This characterization is then shown to be useful by applying it to the concept class ofmonomials (cf. Subsection 4.2).
In Subsection 4.3 we then continue with learners with infinite memory and show
again a characterization of optimal teachers. However, computing the optimal teachingsets and times, respectively, turns out to be a difficult problem. Therefore, we also study
its approximability and show that the optimal teaching time for a concept class C is hard
to approximate within a factor of 12 (1 − ) ln(|C| − 1) for any  > 0 under a standard
complexity theoretic assumption. The hardness result concerning the approximability ofthe optimal teaching time is then extended to learners with infinite memory and without
feedback.
Furthermore, we study two variations of our model, namely teaching from positive
data and inconsistent teachers. Theorems characterizing the teachability within thesemodels are shown in Section 5. Finally, in Section 6 we discuss the results obtained.
2. Preliminaries
We start by introducing the necessary notions and definitions. Let N = {0, 1, . . .}denote the set of all natural numbers, and let N+ = N \ {0}. By R we denote the setof all real numbers. For any set S we write |S| and ℘(S) to denote its cardinality andpower set, respectively. Set inclusion and proper set inclusion is denoted by “⊆” and“⊂,” respectively. For a set S ⊆ N, we write min S and max S to denote the minimum
and maximum of S, respectively, where, by convention, min ∅ = ∞ and max ∅ = 0. For
any function f : S → R over an arbitrary set S and any set A ⊆ S we defineargmin f (x)= {x | x ∈ A, f (x) = min{f (x0 ) | x0 ∈ A}} .

x∈A

If {f (x0 ) | x0 ∈ A} has no minimum, then we set argminx∈A f (x) = ∅. The definition ofargmaxx∈A f (x) is analogous to the above.
For any set S, we denote by S ∗ the set of all finite sequences of elements from S. Letm ∈ N+ ; then we write S m and S ≤m to denote the set of all sequences with length mand at most length m, respectively. We use bold lowercase letters as identifiers forsequences. Elements forming a sequence are enclosed in angle brackets. The empty
sequence is denoted by h i and the length of a sequence s ∈ S ∗ is denoted by |s|. We
refer to sequences of length 1 as singleton sequences. For the i-th element of a sequence s(i = 1, . . . , |s|) we write s[i]. We use the symbol ◦ for the concatenation of sequences
and the symbol ◦µ , where µ ∈ N+ , for a length-restricted concatenation with a singleton
sequence, i.e.,(
hx1 , . . . , x` , yi ,if ` < µ ;hx1 , . . . , x` i ◦µ hyi =hx`−µ+2 , . . . , x` , yi , if ` ≥ µ .
4

To describe our teaching models we use mostly standard notations from algorithmic
learning theory. We always assume a finite learning domain X. We refer to the elementsof X as instances. Any subset c ⊆ X is said to be a concept. Whenever appropriate,
we identify a concept c with its characteristic function c : X → {0, 1}. A concept classis a set C ⊆ ℘(X) of concepts. As X is finite, every concept class is finite, too. A
pair (x, b) ∈ X × {0, 1} of an instance and a Boolean label is said to be an example. An
example (x, b) is positive if b = 1 and negative if b = 0. The set of all examples is denoted
by X = X × {0, 1}. A set S ⊆ X of examples is also called sample. We denote the set of
all examples for a concept c by X (c) = {(x, c(x)) | x ∈ X}. An example (x, b) is called
consistent with c iff (x, b) ∈ X (c). Let S be a sample and let C be a concept class; thenwe set C(S) = {c ∈ C | all z ∈ S are consistent with c}. Furthermore, for a sequence sof examples, we set C(s) = {c ∈ C | all s[i] are consistent with c, where i = 1, . . . , |s|}.
A teaching set [12, 11] for a concept c ∈ C with respect to C is any sample S suchthat C(S) = {c}. Note that teaching sets are also known as key [13], specifying set [18],discriminant [19], and witness set [20]. The teaching dimension of c with respect to C isdefined as the size of c’s smallest teaching set, i.e.,TD(c, C)=min{|S| | C(S) = {c}} .

We simply write TD(c) if the concept class is clear from the context. The teaching
dimension of the whole concept class C is defined as the maximum teaching dimension
over all concepts, that is,
TD(C)

=

max{TD(c, C) | c ∈ C} .

To have some concept classes that allow us to exemplify certain effects, for n ∈ N+ ,we define An to be the class of all concepts over {1, . . . , n}, i.e., An = ℘({1, . . . , n}). The
co-singleton concepts ci over {1, . . . , n} are defined as ci = {1, . . . , n} \ {i}, i = 1, . . . , n.
We set Sn = {ci | i = 1, . . . , n} ∪ {{1, . . . , n}}. Moreover, for n ∈ N+ we denote by Mn
the concept class of all monomials over {0, 1}n . We exclude the empty concept from Mn
and can thus identify each monomial with a string from {0, 1, ∗}n and vice versa.
2.1. The Teaching Model
The teaching process is divided into rounds. In each round the teacher gives thelearner an example of a target concept. The learner memorizes this example and computes a new hypothesis based on its last hypothesis and the memorized examples. The
target and the hypotheses are taken from a concept class known to both the teacher andthe learner.
The Learner. In a sense, consistency is a minimum requirement for a learner. We
thus require our learners to be consistent with all examples they know. However, thehypothesis is chosen at random from all consistent ones.
The memory of our learners may be limited to µ ≥ 1 examples. If the memory is fulland a new example arrives, the oldest example is erased. In other words, the memory
works like a queue. Setting µ = ∞ models unlimited memory.
The goal of the teacher is to teach the learner the target. Thus, the learner must
eventually hypothesize the target and maintain it. Consistency alone cannot guarantee
this behavior if the memory is too small. In this case, there is more than one consistent5

hypothesis at every round and the learner could oscillate between them rather thanmaintaining a single one. To avoid this, conservativeness is required, i.e., the learner canchange its hypothesis only when taught an example inconsistent with its current one.
So, we model the learner as an automaton with randomized state transitions. Whenever the learner has more than one hypothesis to choose between, it is supposed to pick
one alternative uniformly at random. The goal is that the learner hypothesizes the target as quickly as possible. But now we do not measure the worst case time until thishappens, rather we measure the expected teaching time of the learner.
To make our results dependent on C alone, rather than on an arbitrary initial state of
the learner, we stipulate a special initial hypothesis, called init. We assume every example
to be inconsistent with init. Thus, init is left after the first example and cannot be reachedagain. Moreover, the initial memory is empty. In other words, the randomized learners
are randomized automata. Every state consists of a sequence s ∈ X ∗ of memorized
examples and a hypothesis h ∈ C ∪ {init}. The state space is thus X ∗ × (C ∪ {init}).
More formally, we consider the following learners.
Definition 1. Let C be a concept class over X and let µ ∈ N ∪ {∞}. The following
randomized algorithm is called the randomized µ-memory learner using the hypothesis
space C and is denoted by Lµ,C (or by Lµ if C is clear or not important):
Current state: Memory s ∈ X ∗ , hypothesis h ∈ C ∪ {init}.
Input: Example z ∈ X .
Follow-up state: Memory s0 ∈ X ∗ , hypothesis h0 ∈ C.
1 s0 := s ◦µ hzi;
2 if z ∈/ X (h) then choose h0 uniformly at random from C(s0 );3else h0 := h .
Definition 1 implicitly defines the probabilities p((s, h), z, (s0 , h0 )) of a state change
from (s, h) to (s0 , h0 ) on input z ∈ X :
if z ∈ X (h) ∧ s0 = s ◦µ hzi ∧ h = h0 ;
 1,
0
0
0
1/|C(s )| , if z ∈/ X (h) ∧ s0 = s ◦µ hzi ∧ h0 ∈ C(s0 ) ; (1)p((s, h), z, (s , h )) =0,otherwise .
The Teacher. A teacher is an algorithm taking initially a given target concept c∗ as
input. In the presence of feedback, in each round it receives the follow-up state of thelearner and outputs an example for c∗ . Thus, in this case the teacher is a function
T : X ∗ × (C ∪ {init}) → X (c∗ ) .
In the absence of feedback, in each round it receives nothing and it just outputs an
example for c∗ . Hence, now the teacher is a function
T : N → X (c∗ ) .
A learner Lµ,C and a teacher determine a teaching process. The state of the process
in a round t ∈ N is described by the probability distribution over the learner’s state space6

that specifies for each state the probability of the learner being in this state in round t.
We denote this probability distribution by(t)δT : X ∗ × (C ∪ {init}) → [0, 1] .
The initial distribution is δ (init) with δ (init) (h i, init) = 1, since initially the learner
hypothesizes init and has an empty memory.
First, we consider the teaching process involving a teacher T without feedback and(t)
the learner Lµ,C . Then the probability distributions evolve as follows. Let δT be the
distribution in round t and let z = T (t) be the example given in round t. Then for every
state (s, h) the definition of Lµ,C implies a distribution over the follow-up states. The(t+1)
distribution δT
for round t + 1 is then the weighted sum over all the distributions for(0)
the single states of the learner. Thus, more formally we arrive at δT = δ (init) , and for
all t ≥ 0:X(t+1) 0(t)
δT(s , h0 ) =δT (s, h) · p((s, h), T (t), (s0 , h0 )) .
(2)
(s,h)
∈X ∗ ×(C∪{init})

Next, we look at the teaching process involving a teacher T with feedback and the(0)learner Lµ,C . Now, we have δT = δ (init) , and for all t ≥ 0:X(t)(t+1) 0(s , h0 ) =δT (s, h) · p((s, h), T (s, h), (s0 , h0 )) ,
δT
(3)
(s,h)
∈X ∗ ×(C∪{init})

which is similar to Equation (2) except that T (t) is replaced by T (s, h).
Since we are mostly interested in the probability for certain hypotheses, as opposedto the memory, we define as shortcut:
X (t)
(t)
δT (s, c) .
δT (c) =(4)s∈X ∗We distinguish two teaching success variants: finite and in the limit. Finite teaching
success means that after finitely many rounds the probability of having reached thetarget is 1. Teaching success in the limit means that the probability of reaching thetarget converges to 1.
∗
Definition 2. Let C be a concept class, c ∈ C be a target concept, and µ ∈ N ∪ {∞}.
(t)

Furthermore, let T be a teacher and let δTbe the series of probability distributionst∈Nover states of Lµ,C . The success probability of T is then(t)lim δ (c∗ ) .
t→∞ TA teacher is successful iff its success probability equals 1. A successful teacher is called(t)finitely successful iff there is a t such that δT (c∗ ) = 1, otherwise it is called successful inthe limit. For a successful teacher we define the expected teaching time asX  (t)(t−1) ∗
E[T, Lµ,C , c∗ ] =t · δT (c∗ ) − δT(c ) .
t≥1

7Note that the expected teaching time does not need to be finite, even if the teacher(t)(t)
is successful. Moreover, the limit limt→∞ δT (c∗ ) exists for every teacher, since δT (c∗ )is monotonically increasing due to the conservativeness of the learner. The teachabilityof a concept is then measured by the minimal expected teaching time over all teachers.
Definition 3. Let C be a concept class, c∗ ∈ C and µ ∈ N ∪ {∞}. The optimal teachingtime for teaching c∗ with feedback to Lµ,C is
Eµ+ (c∗ , C)=

inf E[T, Lµ,C , c∗ ]Twhere T ranges over all teachers T : X ∗ × (C ∪ {init}) → X (c∗ ). The optimal teachingtime for teaching c∗ without feedback to Lµ,C is
Eµ− (c∗ , C)=

inf E[T, Lµ,C , c∗ ] ,Twhere T ranges over all teachers T : N → X (c∗ ). For a class C we set Eµ− (C) =max{Eµ− (c, C) | c ∈ C} and Eµ+ (C) = max{Eµ+ (c, C) | c ∈ C}.
If the concept class is clear, we may write Eµ+ (c) instead of Eµ+ (c, C) and Eµ− (c) forEµ− (c, C). Note that, since we consider only finite concept classes, the infimum in thedefinition of Eµ+ (c) can be replaced by the minimum, because in this case there are only
finitely many teachers with feedback.
We finish this subsection with some simple facts about the notions of teachability andthe teaching times just defined.
Fact 1. Let C be a concept class and let µ ∈ N+ . A concept c∗ is teachable to Lµ,C
finitely (with or without feedback) if and only if TD(c∗ , C) ≤ µ.
Fact 2. For all C and µ ∈ N ∪ {∞} all c∗ ∈ C and α ∈ {+, −} we have:(1) Eµ+ (c∗ , C) ≤ Eµ− (c∗ , C),αα(2) E∞(c∗ , C) ≤ Eµ+1(c∗ , C) ≤ Eµα (c∗ , C).
Proper inequality holds for C = An with n ≥ µ + 3.
3. Varying Feedback, Memory Size and the Order of Examples
We start by calculating the teaching times for the concept {1, . . . , n} ∈ Sn for varying
memory size and feedback in order to show that feedback and memory size have a somewhat realistic influence on the duration of teaching. First, we consider a teacher withfeedback and the learner L1 using Sn . Our teacher now gives an example inconsistent
with the current hypothesis in every round until L1 reaches the target {1, . . . , n}. The
probability of reaching the target is 1/n in each round. Therefore the expected number ofrounds until the target is reached is n. This teacher is optimal, because it is basically the
only one. Giving an example consistent with the current hypothesis would not change
the learner’s state and would therefore be useless. Thus E1+ ({1, . . . , n}, Sn ) = n.
Generalizing this teacher to 1 < µ ≤ n is easy. A small problem for calculating the
expected teaching time is that the learner’s memory needs some rounds to fill. More8

precisely, in the first round the probability of reaching the target is 1/n, in the second
round 1/(n−1) and in round i ≤ µ it is 1/(n−i). Beginning with round µ the probability
remains constant 1/(n − µ). Thus on entering the µ-th round, the expected number ofremaining rounds is n − µ. Putting it all together and simplifying the expression, we get
the following formula for the expected number of rounds until Lµ (1 ≤ µ ≤ n) reaches{1, . . . , n}: µ(µ−1)
2n +n−µ+1. For memory sizes greater than n the teaching time improves
no further. So we obtain the teaching time for µ = ∞ by setting µ = n. Again, also forµ > 1 this is essentially the only teacher and its teaching time is therefore optimal:Eµ+ ({1, . . . , n}, Sn )=µ(µ − 1)+n−µ+1 .
2n(5)

Teaching is more difficult without feedback. In this situation the teacher can merely
guess examples hoping that they are inconsistent with the current hypothesis. If aconsistent example is presented no hypothesis change is possible, since the learner isconservative. Rather than using a provably optimal teacher, we use a “reasonable”
teacher whose optimality for the special case µ = 1 can be shown (cf. [21]).
In particular, giving one example a second time within an interval of µ rounds willcertainly not trigger a hypothesis change. Therefore, it seems to be a good strategy to
put a maximum length interval between two occurrences of the same example. This isachieved by the “reasonable” teacher T − that gives all n examples for {1, . . . , n} in the
canonical order in an infinite loop, that is, T − (i) = (1 + i mod n, 1) for all i ∈ N. The
analysis of T − is a bit more complicated and we sum it up in the
Pnfollowing theorem,
where we use Hn to denote the nth Harmonic number, i.e., Hn = i=1 1i .
Theorem 3. Let T − be a teacher for c∗ = {1, . . . , n} ∈ Sn with T − (i) = (1 + i mod n, 1)
for all i ∈ N. Then
E[T − , L1,Sn , c∗ ]=1+n(n − 1)
2

and for µ ∈ {2, . . . , n}:E[T − , Lµ,Sn , c∗ ]=(n − µ + 1)(n + µ)
− Hn + Hn−µ+1 .
2

Proof. First, the case µ = 1 is considered. To simplify notation we use F to denote thesought expectation. We derive some properties of F allowing us to find a formula for it.
Suppose the learner conjectures hypothesis ci (1 ≤ i ≤ n) and the teacher T − presents
example (i, 1) next. The resulting probability distribution is the same as after the regular
first example: all hypotheses except ci have a probability of 1/n and the teacher presents(i, 1) only after all other examples have been presented. Therefore, the expected numberof rounds to reach c∗ for this learner is also F .
Now suppose the learner conjectures hypothesis ci and the teacher T − presents example (i−1, 1) next. This will not change the learners hypothesis because ci is consistent
with (i − 1, 1). Only in the next round, in which T − gives example (i, 1), the hypothesischanges. Moreover this hypothesis change is the same as before; it only happens one
round later. Hence, the expectation for this learner is F + 1. In general, if it takes` ∈ {0, . . . , n − 2} rounds before the next inconsistent example arrives then the expectation is F + `. Of course, starting in the target concept c∗ has an expectation of 0.
9

Now let us go back to our “real” teaching process in which the learner starts in init.
After the first example, the learner assumes hypothesis c1 with probability 0 and allother hypotheses c∗ , c2 , . . . , cn with probability 1/n. This means that with probability
1/n the learner is in a state, namely c2 , in which the next example triggers a hypothesischange. More generally, the learner is with probability 1/n in a state in which after` = 0, . . . , n − 2 examples a hypothesis change is triggered (the states are c2 , c3 , . . . , cn ).
The expected number F of rounds is thus composed of n − 1 individual expectations,each of which is to be weighted by 1/n. This yields
F

=

1+

n−2
X
`=0

1
· (F + `)n(6)which is a linear equation with one variable whose solution is
F

=

1+

n(n − 1).
2

Next we consider the case µ > 1. Again, the situation is a bit more complicated,since it takes µ rounds until the memory is filled. We consider this initial phase laterand focus first on the situation in which the memory already contains µ examples.
The arguments are similar to the above for the case µ = 1. Suppose a learnerconjectures hypothesis ci and memorizes the last µ examples h(i − µ, 1), . . . , (i − 1, 1)i.
This means example (i, 1) comes next. We denote the expected number of rounds forthis learner to reach the target c∗ by F 0 . After the example (i, 1) is given, the learner iswith a probability of 1/(n − µ + 1) in each hypothesis consistent with the new memoryh(i − µ + 1, 1), . . . , (i, 1)i.
More generally, suppose the learner assumes ci+` for some ` > 0 and the memoryis the same as before. Then it takes 1 + ` rounds until a hypothesis change happens.
The situation reached afterwards is essentially the same as in the special case ` = 0 justdiscussed: the learner is with a probability of 1/(n − µ + 1) in each hypothesis consistent
with the new memory. Of course, the consistent hypotheses are different for different `.
The point, however, is that there is always a hypothesis that is inconsistent with the next
example, one that is consistent with the next but inconsistent with the example after
the next and so on. In effect the expectation for a learner starting in ci+` and receiving
example (i, 1) next is F 0 + `.
Our observations above allow us to state a formula for F 0 similar to the case µ = 1:
F0

=

1+

n−µ−1
X
`=0

1
(F 0 + `) .
n−µ+1

(7)

Note that for µ = 1 we get Equation (6). The solution of Equation (7) isF0 = 1 +(n − µ)(n − µ + 1)
.
2

(8)

Now, if n is large compared to µ the initial µ rounds can be neglected and Equation (8)gives a good approximation for the true expectation. We now derive the exact values.
The probability of reaching the target in the first round is 1/n. Otherwise after i ≤ µrounds the learner knows the examples (1, 1), . . . , (i, 1) and hypothesizes c∗ , ci+1 , . . . , cn
10

with equal probability, namely pi = 1/(n − i + 1). It follows that the probability of1. Calculating thereaching the target c∗ in round i > 1 is pi − pi−1 = (n−i+1)(n−i+2)
expectation would therefore begin like this:
µ
X
1
1
·1+
·i .
n
(n
−
i
+
1)(n
− i + 2)i=2(9)Computing the “in-the-target-probabilities” pi for i ≥ µ is more difficult, but we can use
the values for F 0 instead.
After µ examples have been given, the learner memorizes (1, 1), . . . , (µ, 1) and hypothesizes c∗ , cµ+1 , . . . , cn with probability 1/(n−µ+1) each. Then for all ` ∈ {0, . . . , n−µ−1}
there is a hypothesis, namely cµ+` , that is inconsistent only with the example given `rounds later. Thus, the expected number of rounds to reach the target from this probability distribution is
n−µ−1
X
`=0

1
· (F 0 + `) .
n−µ+1

But this probability distribution is reached after µ rounds. Thus the expectations haveto be considered higher by µ. Therefore we have to add to Equation (9) the expression:
n−µ−1
X
`=0

1
· (F 0 + ` + µ)
n−µ+1

=

(n − µ)(1 + (n − µ)2 + 2n)2(n − µ + 1)

which yields for the sought expectationµi(n − µ)(1 + (n − µ)2 + 2n)
1 X
+
+
.
n i=2 (n − i + 1)(n − i + 2)
2(n − µ + 1)

(10)

Next, we simplify the sum in (10) as follows.

µ
µ 
1 X
i
1 X
1
1
+
=
+
−
·i
n i=2 (n − i + 1)(n − i + 2)
n i=2 n − i + 1 n − i + 2
=
=

µ−1
µ−2
µ−2
X 1
1
2 X i+1 X i+2
µ
− +
−
=
−
n n i=2 n − i i=2 n − i
n − µ + 1 i=2 n − iµ− Hn + Hn−µ+1 .
n−µ+1All what is left is to add the right expression of (10) to the term just obtained. Then we
factor out n − µ + 1 and obtain
E[T − , Lµ,Sn , c∗ ]==µ(n − µ)(1 + (n − µ)2 + 2n)+− Hn + Hn−µ+1
n−µ+12(n − µ + 1)
(n − µ + 1)(n + µ)
− Hn + Hn−µ+12

as claimed.


11

expected teaching time∞

non-deterministic

144
121
100
81
64

wit
hou
t

49

feed

bac
k

36
25

with feedback

16
9
4
1

memory size µ
1

5

10

15

Figure 1: Influence of feedback and memory size on the expected teaching time. The concept{1, . . . , 16} ∈ S16 is taught to the randomized learners Lµ with and without feedback. The valuesfor µ = 1 and those for “with feedback” are the optimal teaching times. The values for 1 < µ ≤ 16 without feedback are based on a reasonable, supposedly optimal, teacher. In contrast, teaching is impossible
in the TD model unless the memory size is at least 16.

Comparing Equation (5) with Theorem 3, we see that for teaching with feedback the
expected teaching time is Θ(n) while for teaching without feedback it is Θ(n2 ).
As an illustration, all teaching times for n = 16 and µ = 1, . . . , 16 are shown in
Figure 1. Clearly, teaching becomes faster with growing µ. Moreover the teaching speed
increases continuously with µ and not abruptly as in the TD model. In particular,teaching is possible even with the smallest memory size (µ = 1).
In general, the influence of the memory size varies between concept classes. At one endof the spectrum there is the concept class of all singleton concepts over X = {1, . . . , n}.
Here all concepts have a teaching dimension of one, and increasing the memory size
beyond µ = 1 will not improve the expected teaching time.
On the other end of the spectrum, there is the class of all concepts over X ={1, . . . , n}, in which all concepts have a teaching dimension of 2n . For a given target
there is, up to symmetry, only one teacher with feedback giving an inconsistent example
in every round. This teacher is therefore optimal. After µ < n rounds there are always
2n−µ hypotheses consistent with the memory, resulting in a probability of 2µ−n of reaching the target in any given round. Thus, for small µ, the exptected teaching time isapproximately 2n−µ . This shows that increasing the memory size by one roughly halves
the teaching time.
In order to illustrate the influence of the order of examples in the randomized teachingmodel, we have calculated a numerical example. Figure 2 shows three teachers teaching
the monomial v3 ∧ v4 without feedback to L1 using the hypothesis space M4 . Allteachers use the same four examples from a minimum teaching set. Every teacher,however, arranges these examples into a different sequence and teaches this sequence in
an infinite loop.
12

v1

Target:v2

Teachers:
T1 : hx1 x2 x3 x1 x2 x4 i∞

x2
x1 x3

v4

T2 : hx1 x2 x3 x4 i∞

x4

**11

T3 : hx3 x4 x1 x2 i∞v3teaching success probability
0.5

28.0
32.7
34.2

0.4
0.3
0.2
0.1

round
0.0
0

5

10

15

20

Figure 2: Influence of the order of examples on the teaching succes probability and expected time. The
learner L1 using M4 is taught the monomial **11 by three teachers T1 , T2 , T3 . All teachers use thesame examples, but give them in different orders. This leads to different success probability curves andto different expected teaching times (the numbers on the right end of the curves).

We refrain from including all the numerical calculations of the teaching success probabilities in the curves of Figure 2. The expected teaching times have been proved by
Balbach [22, Fact 8.18].
Already these simple examples show that the randomized model is sensitive to feedback, memory size, and the order of examples. This sensitivity is also qualitatively
correct, that is, teaching becomes faster with growing memory or with feedback.
4. Teaching with Feedback as a Markov Decision Process
4.1. Markov Decision Processes
All our randomized teaching model variants can be regarded as special cases of socalled Markov decision processes (MDP). These processes have been extensively studied,
and we refer the reader to Puterman [23], and Bertsekas [24]. In this section we introduce
some basic terminology.
An MDP is a probabilistic system whose state transitions can be influenced during
the process by actions which incur costs. Formally, an MDP consists of a finite set
State of states, an initial state s0 ∈ State, a finite set Action of actions, a function
cost : State × Action → R, and a function prob : State × Action × State → [0, 1]. The
value cost(s, a) specifies the cost incurred if action a is performed in state s. The value
prob(s, a, s0 ) specifies the probability for the MDP to change from state s to s0 under13

action a. A policy π : State → Action assigns an action to every state and thus inducesa Markov chain.
A special case of Markov decision processes, which is still more general than our
teaching scenario, are stochastic shortest path problems (SSPP). In an SSPP there is a
set State ∗ ⊂ State of target states. Once a target state has been reached it cannot be left
and all actions in a target state incur no costs. In an SSPP the costs are then interpreted
as lengths and a minimum expected cost policy corresponds to a tour with minimum
expected length from the initial state to any of the target states.
The basic relation between SSPPs and our teaching model is as follows. The set State
contains all states of the learner, the set Action contains all examples for the target, costis set to 1, except for the target states, which incur no costs, and policies correspond toteachers. The function prob is identical to the function p defined in Equation (1). The
teaching time of a teacher corresponds to the expected length of the path from the initialstate to the target state under the policy corresponding to that teacher. The optimalteaching time corresponds to the minimal expected path length over all policies. A policy
π : State → Action defines a Markov chain over State and for all s ∈ State an expected
time Hπ (s) to reach the target c∗ from s. These expectations, called hitting times, satisfy
the following linear equations for all s ∈ State:X(11)
Hπ (s) = cost(s, π(s)) +prob(s, π(s), s0 ) · Hπ (s0 ) .
s0 ∈State

For a given policy π it is therefore possible, by solving a system of linear equation of size
|State|, to calculate the hitting times.
Under certain assumptions optimal policies and their expectations for SSPPs can becharacterized (cf., e.g., Bertsekas and Tsitsiklis [25], or Puterman [23, Chapter 7]). Theseassumptions are as follows. First, all costs, except in the target state, have to be positive.
This assumption is satisfied in our teaching model, since all costs are 1. Second, a socalled proper policy has to exist. A sufficient condition for properness is that in every
state an action is chosen such that there is a positive probability of reaching the target
state in the next round. A straightforward teacher that corresponds to a proper policy isa teacher that gives for every state an example inconsistent with the hypothesis. Such an
example triggers a hypothesis change that leads to the target with positive probability.
Now we are ready to state the optimality condition in terms of SSPPs. Interpretationsin terms of the teaching model are given in Subsections 4.2 and 4.3.
Lemma 4. All hitting times H(s) simultaneously assume their minimal values if andonly if for all states s ∈ State:!
X00H(s) =
mincost(s, a) +prob(s, a, s ) · H(s ) .
a∈Actions0 ∈State

A policy π has minimal hitting times for all states if and only if for all states s ∈ State:!
Xπ(s) ∈ argmin cost(s, a) +prob(s, a, s0 ) · H(s0 ) .
a∈Actions0 ∈State

14

The hitting time for a state s ∈ State ∗ is H(s) = 0.
A policy π : State → Action corresponds to a teacher that receives feedback andthat can thus choose an action depending on the current state of the learner. If theteacher receives no feedback the results about SSPPs, including Lemma 4, do not apply.
The notion corresponding to this teaching scenario is that of an unobservable stochastic
shortest path problem (USSPP). Only recently Patek [26, 27] has analyzed such problems
and derived an optimality characterization analogous to Lemma 4 for them.
In the following subsection we shall show how the theory developed so far can beapplied to teaching randomized learners with feedback. We start with the simplest case,i. e., with memoryless learners with feedback and then turn our attention to learners with
infinite memory and feedback.
4.2. Memoryless Learners
Teaching memoryless learners with feedback presents the simplest situation. The
teacher faces no uncertainty about the current state of the learner and there are only few
states. In this subsection we aim to apply Lemma 4 to the special case of teaching thememoryless learner with feedback and thus derive a characterization of optimal teachers(cf. Lemma 5). We then use this criterion to develop an optimal teacher for the monomials(cf. Fact 6). As we shall see, this optimal teacher is greedy. We therefore continue
by asking whether or not greedy teachers are always optimal and answer this question
negatively. Finally we compare the teachability measure E1+ with other popular measuresof teachability and learnability (Fact 8).
When L1 receives an example z, the new memory s0 will contain only this example,0s = hzi, and the follow-up hypothesis is chosen from C(hzi). Thus the behavior of L1
in a state (s, h) does not depend on s and in effect the memory is not part of thestate. Therefore the state can be described by the hypothesis alone. More precisely, thelearner L1 looks as follows (cf. Definition 1), where below we write C(z) for C(hzi):
Current state: Hypothesis h ∈ C ∪ {init}.
Input: Example z ∈ X .
Follow-up state: Hypothesis h0 ∈ C.
1 if z ∈/ X (h) then choose h0 uniformly at random from C(z);2else h0 := h .
A teacher for teaching c∗ to L1 with feedback is then a function T : C ∪{init} → X (c∗ ).
A teaching process with feedback involving L1 can be modeled as a stochastic shortest
path problem with State = C ∪ {init}, State ∗ = {c∗ }, Action = X (c∗ ), cost(h, z) = 1 for
h 6= c∗ and cost(c∗ , z) = 0 for all z ∈ X (c∗ ). Furthermore,(
1/|C(z)| , if z ∈ X (h0 ) \ X (h) ;prob(h, z, h0 ) =0,otherwise ;and prob(c∗ , z, c∗ ) = 1 for all z ∈ X (c∗ ). The initial state is init.
Next, we derive a characterization of optimal teachers and of the minimum teachingtime from the characterization of optimal policies (cf. Lemma 4). Note that if L1 is instate h, an example z ∈ X (h) does not change its state and is therefore useless. An
optimal teacher refrains from teaching such examples.
15

Lemma 5. Let C be a finite concept class and c∗ ∈ C be a target. Let H : C ∪ {init} → R
be such that for all h ∈ C ∪ {init} \ {c∗ },X1
H(h0 )
(12)
H(h) =min 1 +|C(z)| 0z∈X (c∗ )h ∈C(z)

z ∈X
/ (h)

and H(c∗ ) = 0. A teacher T : C ∪ {init} → X (c∗ ) is optimal for teaching c∗ to L1 withfeedback if and only if for all h ∈ C ∪ {init} \ {c∗ },X
1T (h) ∈ argmin 1 +
(13)
H(h0 ) .
|C(z)| 0z∈X (c∗ )h ∈C(z)

z ∈X
/ (h)

The minimum teaching time for teaching c∗ to L1 with feedback is H(init).
The characterization in Lemma 5 can be used to prove the optimality of teachers andthe optimal teaching time for concepts. We show this for the class of monomials Mn .
Recall that Mn does not contain the concept ∅. Also note that there are 2n monomialsconsistent with any positive example, and 3n −2n monomials consistent with any negative
example.
Fact 6. Let n ∈ N, n ≥ 2 and let Mn be the concept class of monomials. Then the
optimal teaching time for the concept 1k *n−k is
E1+ (1k *n−k , Mn )=(3n − 2n )(2n + 2k ) − 2n+k−1 + 2n+1 − 3n3n − 2n + 2k−1

for all k ∈ {1, . . . , n}. The optimal teaching time for the all-concept is
E1+ (∗n , Mn )

=

2n .

Input: Target c∗ ∈ {0, 1, *}n , hypothesis h ∈ {0, 1, *}n .
Output: Example (x, b) ∈ X (c∗ ).
1 if h ⊃ c∗ then output (x, 0) with∗

6 c∗ [j]} ;1 − c [i] , if i = min{j | h[j] = ∗ =x[i] =c∗ [i] ,if i 6= min{j | h[j] = ∗ =6 c∗ [j]} and c∗ [i] 6= ∗ ;0,otherwise.
2

else output (x, 1) with arbitrary x ∈ c∗ \ h.

Figure 3: Optimal teacher with feedback for the concept class Mn and the learner L1 . When the
hypothesis encompasses the target, the teacher gives a negative examples that maximizes the probability
that the learner reaches, in the next round, a hypothesis that does not encompass the target.

16

Proof. Let T be the teacher defined in Figure 3. We begin with the simpler case k = 0,
that is, c∗ = *n , and claim that H with H(h) = 2n for all h 6= c∗ is optimal. In this caseevery teacher that always gives an arbitrary positive example until the learner is in thetarget state is optimal. Every such example leads to one of 2n hypotheses with equal
probability of 2−n . Therefore, for all x ∈ X (c∗ ) and for all h 6= c∗ we have:1+X
1
H(h0 )|C(x)| 0=

1 + 2−n · (2n − 1)2n = 2n = H(h) .

h ∈C(x)The expectations H thus satisfy the first condition in Lemma 5. The teacher T satisfies
the second condition in Lemma 5.
Now let the target concept c∗ be represented by 1k *n−k with k ≥ 1. The behaviorof the teacher is based on a partition of all hypotheses into two groups. Within a group,
all hypotheses are assigned the example in the same way and have the same expectedteaching time. The first group contains all hypotheses h with h ⊃ c∗ . We refer tothese hypotheses as ⊃-hypotheses. The second group contains the remaining hypotheses(including init), called the 6⊃-hypotheses.
Now we define the expectations H : C ∪ {init} → R byH(h)= H⊃ :=(3n − 2n )(2n + 2k ) − 2n+k−1
3n − 2n + 2k−1

for all ⊃-hypotheses h andH(h) = H6⊃ :=(3n − 2n )(2n + 2k ) − 2n+k−1 + 2n+1 − 3n3n − 2n + 2k−1

for all 6⊃-hypotheses h. Note that for n ≥ 2, H6⊃ < H⊃ .
We have to prove that H and T satisfy Lemma 5. To achieve this goal, we show two
claims.
Claim 1. Let (x, 0) be consistent with c∗ , that is, x ∈/ c∗ . Then(a) there are 3n − 2n hypotheses consistent with (x, 0);(b) x is of the form y{0, 1}n−k with y containing ` ≥ 1 zeros;(c) the number of ⊃-hypotheses consistent with (x, 0) is exactly 2k − 2k−` − 1.
Proof. Without loss of generality let x ∈ 0` 1k−` {0, 1}n−k for some ` ≥ 0.
(a) There are 2n concepts containing x, hence there are 3n − 2n concepts that areconsistent with (x, 0).
(b) If ` = 0, then x would be of the form 1k {0, 1}n−k and thus in c∗ , a contradiction.
(c) A concept d ∈ Mn encompasses c∗ if and only if d is of the form {1, *}k *n−k .
Furthermore, d is consistent with (x, 0) (that is, x ∈/ d) if and only if d is of the formy{1, *}k−` *n−k with y ∈ {1, *}` containing at least one “1”. There are exactly (2` − 1) ·2k−` = 2k − 2k−` concepts satisfying the latter condition. Since c∗ does not count as⊃-hypothesis, the sought number is one less, as claimed.
 (Claim 1)
Claim 2. For every positive example there are 2n consistent hypotheses of which 2k −1
are ⊃-hypotheses.
17

Proof. For every instance x ∈ 1k {0, 1}n−k there are exactly 2n concepts containing x.
The concepts that result from substituting 1’s by * in c∗ are the only concepts containing
x and c∗ . There are 2k − 1 such concepts (c∗ itself is not a ⊃-hypothesis).  (Claim 2)
We continue by proving the necessary property for H.
Case 1. h ⊃ c∗ .
Then only negative examples z = (x, 0) are inconsistent with h. Without loss ofgenerality, let x ∈ 0` 1k−` {0, 1}n−k with 1 ≤ ` ≤ k. Note that, by Claim 1, Assertion (b),the case ` = 0 cannot occur. Then
1+

X
1
H(h0 )|C(x)| 0=1+h ∈C(x)3n − 2n − 2k + 2k−`
2k − 2k−` − 1· H⊃ +· H6⊃ .
nn3 −2
3n − 2n

The sum of the coefficients of H⊃ and H6⊃ is (3n −2n −1)/(3n −2n ) and thus independentof `. The right hand side of the equation becomes minimal for ` = 1, since the coefficientof H⊃ becomes minimal for ` = 1 and, moreover, H⊃ > H6⊃ . After plugging in H⊃
and H6⊃ , a tedious calculation shows that this minimal value equals H⊃ . Consequently,
in Case 1 the Condition (12) is satisfied.
Case 2. h 6⊃ c∗ .
If z is a positive example then by Claim 2,
1+

X
1
H(h0 )|C(z)| 0=h ∈C(z)1+2n − 2k
2k − 1·H+· H6⊃ = H6⊃⊃2n2nwhere the last equality is due to a tedious calculation. If z is a negative example then1+X
1
H(h0 )|C(z)| 0h ∈C(z)=1+3n − 2n − 2k + 2k−`
2k − 2k−` − 1·H+· H6⊃ .
⊃
3n − 2n3n − 2nAgain this expression is minimized for ` = 1 and its minimal value is H⊃ . The value
for a P
positive example is therefore smaller. Consequently, the minimal value of 1 +10
h0 ∈C(z) H(h ) is H6⊃ , and the Condition (12) is also satisfied for 6⊃-hypotheses.
|C(z)|InP
Case 1 and 2 above we have identified examples minimizing the value of 1 +0
h0 ∈C(z) H(h ). The teacher in Figure 3 always teaches such examples. Therefore,
the teacher in Figure 3 satisfies Condition (13) in Lemma 5 and is thus optimal.
1|C(z)|The teacher from Figure 3 can be computed in linear time. It outputs a positive example whenever possible (that is, when h 6⊃ c∗ ). Since there are 2n hypotheses consistent
with a positive example and 3n − 2n consistent with a negative one, this means that T
follows a greedy strategy minimizing the number of consistent hypotheses for the learnerto choose from, thus maximizing the probability for reaching c∗ in the next round.
Definition 4. Let C be a concept class over X and c∗ ∈ C. A teacher T : C ∪ {init} → X
for c∗ is called greedy iff for all h ∈ C: T (h) ∈ argmin |C(z)|.
z∈X (c∗ )z ∈C(h)/18

The notion of greedy teacher cannot be generalized to arbitrary stochastic shortest
path problems, since in general the target state cannot be reached from all states under
all actions. The question of how good a greedy teacher can be is thus a teaching-specificquestion which cannot be answered directly by the MDP theory. Such a greedy strategy
seems sensible in general and is provably optimal in the case of monomials. However,there are classes where no greedy teacher is optimal.

init
c∗

x1 x2 x3

y1 y2 y3 y4 y5 y6 y7 y8 y9 y10

T0

Tg

–
1
0
0
0
1
1
1
1
1
1
1

– – – – – – – – – –1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 0(x3 , 1)–(x1 , 1)(x1 , 1)(x1 , 1)(x3 , 1)(x3 , 1)(x3 , 1)(x3 , 1)(x3 , 1)(x3 , 1)(x3 , 1)(x3 , 1)–(x2 , 1)(x1 , 1)(x1 , 1)(x3 , 1)(x3 , 1)(x3 , 1)(x3 , 1)(x3 , 1)(x3 , 1)(x3 , 1)

–
1
0
1
1
0
0
0
1
1
1
1

–
1
1
1
1
0
0
0
0
0
0
0

Figure 4: The concept class C1 from the proof of Fact 7. For a family of generalizations of this class, thegreedy teacher T g has an expected teaching time of Ω(|C|) rounds greater than teacher T 0 has.

Fact 7. There is a family of concept classes Cn with |Cn | = 10n + 1 and target concepts
such that the difference between the teaching time of the greedy teacher and the optimalteaching time is Ω(n).
Proof. Let n ≥ 1 and Xn = {x1 , x2 , x3 }, and let the learning domain be Yn = Xn ∪{y1 , . . . , y10n }. The class Cn consists of the target concept c∗ = Yn , n concepts c withc ∩ Xn = {x3 }, 2n concepts c with c ∩ Xn = {x2 , x3 }, 3n concepts c with c ∩ Xn = {x1 },and 4n concepts c with c∩Xn = {x1 , x2 }. Each non-target concept contains all but one of
the instances y1 , . . . , y10n , and each such instance is missing from exactly one non-target
concept. This differentiates the concepts that are equal wrt. Xn (see C1 in Figure 4).
The unique greedy teacher is T g (c) = (x3 , 1) if c(x3 ) = 0 or c = init, T g (c) = (x2 , 1)
if c ∩ Xn = {x3 }, and T g (c) = (x1 , 1) for all remaining concepts except the target.
Denoting the teaching times when starting in a state c with T g (c) = (xj , 1) by Hj ,j = 1, 2, 3, we have
H1=

1 + 7n/(7n + 1) · H3

H2=

1 + 2n/(6n + 1) · H1 + 4n/(6n + 1) · H3

H3=

1 + 2n/(3n + 1) · H1 + n/(3n + 1) · H2 .

3

2+122n +19n+1
for the expected teaching time of T g .
This yields H3 = 266n63n
2 +16n+1
We define the teacher T 0 like T g except that T 0 (c) = (x1 , 1) for all concepts c withgT (c) = (x2 , 1). Analogously to the above, one determines that the expected teaching19

. Furthermore, an explicit calculation showstime of the teacher T 0 is H 0 = (6n+1)(7n+1)
10n+1
that H3 − H 0 = Θ(n). Since H 0 is an upper bound for the optimal teaching time, itfollows that H3 − E1+ (c∗ , Cn ) = Ω(n).
Next, we compare E1+ with other dimensions that occur in learning theory. In particular, the comparison of E1+ with the number MQ of membership queries (see Angluin [1])is interesting because MQ and E1+ are both lower bounded by the teaching dimension.
Fact 8. (1) For all concept classes C and all concepts c ∈ C, E1+ (c, C) ≥ TD(c, C).
(2) There is no function of TD upper bounding E1+ .
(3) There is no function of E1+ upper bounding MQ.
(4) There is a concept class C with E1+ (C) > MQ(C).
(5) For all concept classes C, E1+ (C) ≤ 2MQ(C) .
Proof. For every example x ∈ X (c) there are at least TD(c, C) consistent hypotheses.
Consequently, in every round the probability of reaching the target is at most 1/TD(c, C).
The expected number of rounds is therefore at least TD(c, C). This proves Assertion (1).
Let Cn = {c ⊆ {1, . . . , n} | |c| = 2}. Then TD(Cn ) = 2, but E1+ (Cn ) = n − 1, since
the optimal teacher gives positive examples all the time and there are n − 1 hypotheses
consistent with such an example. Thus Assertion (2) is shown.
Let Cn = {c ⊆ {1, . . . , n} | |c| = 1}. Then E1+ (c, Cn ) = 1 for all c ∈ Cn , but
MQ(Cn ) = n − 1 and Assertion (3) follows.
As an easy calculation shows MQ(An ) = n and E1+ (An ) = 2n−1 and Assertion (4) isproved.
It is known (see, for example, Angluin [2]) that log |C| ≤ MQ(C) for all classes C.
Also, E1+ (C) ≤ |C| because in every step the learner cannot choose from more than |C|hypotheses. Combining both inequalities yields Assertion (5).
Roughly speaking, teaching the learner L1 can take arbitrarily longer than teaching in
the teaching dimension model, but is still incomparable with membership query learning.
4.3. Learners with Infinite Memory
Learners with infinite memory can have infinitely many states (s, h) ∈ X ∗ × (C ∪{init}). But the behavior of the learner L∞ is not affected by memorizing the same
example multiple times. This makes it pointless to teach the same example twice. Thus
it suffices to consider the finitely many memories of length at most |X|. The number ofstates is therefore only finite. From the SSPP optimality criterion Lemma 4 we can then
immediately derive a characterization of optimal teachers for L∞ . This characterization
is more complicated than in the L1 case (Lemma 5) and difficult to write in a closed
form. Our first task is thus to simplify this criterion (Lemma 11) by proving that an
optimal teacher always gives examples that are inconsistent with the current hypothesis(see Proposition 10).
The criterion also yields an algorithm, called backward induction, for computing the
optimal teaching time. This algorithm’s runtime, however, is not polynomial in the
representation of the concept class. A straightforward idea to improve the backward
induction is to consider only the first TD(c∗ ) rounds of the teaching process, since there
is always a teacher successful after that many rounds. But, as we show in Fact 13, this20

modified algorithm does not always yield the optimal teaching time. Indeed, that an+
efficient algorithm for computing E∞
is unlikely to exist is then shown in Theorem 15.
+
This result is based on a general lemma (cf. Lemma 12) that relates E∞
to the teaching
dimension.
It is not difficult to formally describe the SSPP corresponding to teaching c∗ ∈ C to
L∞ with feedback: We stipulate that in every state (s, h) only examples z ∈/ s can begiven. As already mentioned, an optimal teacher would not teach other examples. Thus,
we only have to consider memories in which no example occurs twice. Therefore, the setof states isState= {(s, h) ∈ X (c∗ )≤|X| × (C ∪ {init}) | h ∈ C(s) ∧ (i 6= j ⇒ s[i] 6= s[j])} .

The initial state is (h i, init) and the set of target states isState ∗

= {(s, h) | (s, h) ∈ State, h = c∗ } .

For a state (s, h) and an example z ∈/ s the transition probabilities areprob((s, h), z, (s0 , h0 ))
if z ∈ X (h) ∧ s0 = s ◦ hzi ∧ h0 = h ;
1 ,
0
0
0
= p((s, h), z, (s , h )) = 1/|C(s )| , if z ∈/ X (h) ∧ s0 = s ◦ hzi ∧ h0 ∈ C(s0 ) ;0otherwise.
As usual, the costs are 1 for each example, except the examples given in the target state,
which are costless, i.e.,(
1 , if h 6= c∗ ;cost((s, h), x) =0 , if h = c∗ .

Plugging the above into Lemma 4 yields an optimality characterization that is hard towrite concisely. This is because we have to distinguish three cases for p. In comparison,
Lemma 5 looks rather simple because we could confine the actions to examples that areinconsistent with the current hypothesis. This was possible, since a consistent example
would not change the state of L1 . Giving a consistent example to L∞ , however, doeschange the learner’s state. Below we show that it nevertheless suffices to consider teachersthat always give inconsistent examples. This not only yields a simpler characterization,
it is also interesting in its own right.
Our first step towards this result is that the order of the examples in an infinite
memory is not important. Therefore, we can regard the memory as a set rather than asa sequence. As a by-product, this reduces the number of states we have to consider.
Proposition 9. Let H satisfy the condition in Lemma 4 for an SSPP corresponding
to teaching c∗ ∈ C to L∞ with feedback. Let (s, h), (s̃, h) ∈ State with s, s̃ ∈ X k and{s[1], . . . , s[k]} = {s̃[1], . . . , s̃[k]}. Then H(s, h) = H(s̃, h).
21

Proof. The proof is by induction on the length k of s and s̃. We start at the maximal
length k = |X|. Let (s, h), (z̃, h) ∈ State with |s| = |X|. Then both s and s̃ contain all
examples in X (c∗ ) and thus h = c∗ . Therefore H(s, h) = H(s̃, h) = 0.
Now assume the statement holds for all sequences of length k > 0. We show thestatement for all memories of length k − 1. Let s, s̃ ∈ X (c∗ )k−1 be memories withidentical range and h a hypothesis such that (s, h), (s̃, h) ∈ State. If h = c∗ then both
H-values are again 0. We thus assume h 6= c∗ . Since s and s̃ have the same range, wehave for all h0 and all z by the definition of p:p((s, h), z, (s ◦ hzi, h0 )) = p((s̃, h), z, (s̃ ◦ hzi, h0 )) .
From the latter equality and Lemma 4 we thus obtain:X
H(s, h) =min∗ 1 +p((s, h), z, (s0 , h0 )) · H(s0 , h0 )
z∈X (c )(s0 ,h0 )∈State=min 1 +z∈X (c∗ )Xp((s, h), z, (s ◦ hzi, h0 )) · H(s ◦ hzi, h0 )

(s◦hzi,h0 )∈State=min 1 +z∈X (c∗ )Xp((s̃, h), z, (s̃ ◦ hzi, h0 )) · H(s̃ ◦ hzi, h0 )

(s̃◦hzi,h0 )∈State= H(s̃, h).
Note that the third equality is valid, since H(s ◦ hzi, h0 ) = H(s̃ ◦ hzi, h0 ) by the induction
hypothesis.
Proposition 10. Let C be a concept class and c∗ be a target. Then there is an optimalteacher T 0 for teaching c∗ to L∞ with feedback that never gives an example consistent
with the current hypothesis, that is,
T 0 (s, h) ∈/ X (h)for all (s, h) ∈ State \ State ∗ .
Proof. Let H satisfy the first condition in Lemma 4. Furthermore, let T be a teacher
that gives a consistent example z1 = T (s, h) ∈ X (h) when the learner is in a state(s, h) ∈ State \State ∗ . We assume that s is of maximal length with this property. Thus in
the follow-up state (s ◦ hz1 i, h) the teacher T gives an example z2 = T (s ◦ hz1 i, h) ∈/ X (h).
We show that this teacher does not satisfy the second condition in Lemma 4 for state(s, h), i.e., we prove that


X
z1 ∈
/ argmin cost((s, h), z) +prob((s, h), z, (s ◦ hzi, h)) · H(s ◦ hzi, c) .
z∈X (c∗ )z ∈s/c∈C(s◦hzi)

Let us denote the expression in the large parentheses by Yz . The value of Yz isX
1
Yz = 1 +·H(s ◦ hzi, c)|C(s ◦ hzi)|c∈C(s◦hzi)

22

for examples z ∈/ X (h) andYz=

1 + H(s ◦ hzi, h)for examples z ∈ X (h). The value of Yz , with z set to z1 , isX
Yz1 = 1 + H(s ◦ hz1 i, h) = 2 + q ·H(s ◦ hz1 , z2 i, c)(14)c∈C(s◦hz1 ,z2 i)with q = 1/|C(s ◦ hz1 , z2 i)|.
Next, we prove that (14) is not the minimal value of Yz over all examples z by showingthat Yz2 < Yz1 . At first we haveX
(15)
Yz2 = 1 + q 0 ·H(s ◦ hz2 i, c)c∈C(s◦hz2 i)with q 0 = 1/|C(s ◦ hz2 i)|. The values H(s ◦ hz2 i, c) in the summation are
H(s ◦ hz2 i, c)

=


X

min 1 +z∈X (c∗ )z ∈s◦hz/
2i< 1+

prob((s ◦ hz2 i, c), z, (s ◦ hz2 , zi, c0 )) · H(s ◦ hz2 , zi, c0 )

c0 ∈C(s◦hz2 ,zi)X

prob((s ◦ hz2 i, c), z1 , (s ◦ hz2 , z1 i, c0 )) · H(s ◦ hz2 , z1 i, c0 ) ,c0 ∈C(s◦hz2 ,z1 i)

where the upper bound results from setting z to z1 . When substituting the upper bounds
just derived for the H-values in (15), we have to distinguish between hypotheses for which
z1 is consistent and those for which z1 triggers a hypothesis change. We get as upperbound for (15):





X
X

1 + q 00
Yz2 < 1 + q 0 
H(s ◦ hz2 , z1 i, c0 )
0c ∈C(s◦hz2 ,z1 i) c∈C(s◦hz2 i)c∈C(s◦hz/
2 ,z1 i)
c6=c∗





+
(1 + H(s ◦ hz2 , z1 i, c))
c∈C(s◦hz2 ,z1 i)

∗
X

c6=c

with q 00 = 1/|C(s ◦ hz2 , z1 i)| = q. Now all occurring H-values have s ◦ hz2 , z1 i as first23

argument. Removing the first summation yields





X

1 + q 0 |C(s ◦ hz2 i) \ C(s ◦ hz2 , z1 i) \ {c∗ }| · 1 + q 00

H(s ◦ hz2 , z1 i, c0 )

c0 ∈C(s◦hz2 ,z1 i)X+c∈C(s◦hz2 ,z1 i)c6=c∗(1 + H(s ◦ hz2 , z1 i, c)).

We set r = |C(s ◦ hz2 i) \ C(s ◦ hz2 , z1 i) \ {c∗ }| and r0 = |C(s ◦ hz2 , z1 i) \ {c∗ }|. After
multiplying out we obtainYz2 < 1+q 0 r0 +q 0 r0 q 00

X

H(s◦hz2 , z1 i, c0 )+q 0 r+q 0 r

c0 ∈C(s◦hz2 ,z1 i)X

H(s◦hz2 , z1 i, c0 )c0 ∈C(s◦hz2 ,z1 i)and after sorting the terms,
Yz2

X< 1 + q 0 r0 + q 0 r + (q 0 rq 00 + q 0 )H(s ◦ hz2 , z1 i, c0 ) .

(16)

c0 ∈C(s◦hz2 ,z1 i)

The first three terms can be upper bounded by 1 + q 0 r0 + q 0 r = 1 + q 0 (r + r0 ) = 2 − q 0 < 2.
The coefficient q 0 rq 00 + q 0 of the summation can be upper bounded as follows:
q 0 rq 00 + q 0|C(s ◦ hz2 i) \ C(s ◦ hz2 , z1 i) \ {c∗ }|+ q0|C(s ◦ hz2 i)||C(s ◦ hz2 , z1 i)| + 1
q 00 · 1 −+ q0|C(s ◦ hz2 i)||C(s ◦ hz2 , z1 i)|
q 00 · 1 −+ q0|C(s ◦ hz2 i)|
1
q 00 −+ q0|C(s ◦ hz2 i)|
q 00 .

= q 00 ·=<==Applying these upper bounds to (16), it follows
X
Yz2 < 2 + q 00 ·H(s ◦ hz2 , z1 i, c0 )c0 ∈C(s◦hz2 ,z1 i)

=

2+q·

X

H(s ◦ hz1 , z2 i, c0 )c0 ∈C(s◦hz2 ,z1 i)= Yz1 ,
where the first equality holds because q 00 = q and H(s ◦ hz2 , z1 i, c0 ) = H(s ◦ hz1 , z2 i, c0 )by Proposition 9. Therefore, Yz2 is strictly less than Yz1 . This means that the example
z1 is not in the set argminz∈X (c∗ ),z∈s/ Yz . This shows that the teacher T does not satisfy
the second condition in Lemma 4.
24

Now, we are in the position to state the optimality characterization.
Lemma 11. Let C be a finite concept class and c∗ ∈ C be a target. Furthermore, let
H : X ≤|X| × (C ∪ {init}) → R be such that for all (s, h) ∈ State \ State ∗ ,X1
H(s, h) =min 1 +H(s ◦ hzi, h0 )
|C(s ◦ hzi)| 0z∈X (c∗ )h ∈C(s◦hzi))

z ∈X
/ (h)

and for all (s, h) ∈ State ∗ , H(s, h) = 0. A teacher T : X ∗ × (C ∪ {init}) → X (c∗ ) is
optimal for teaching c∗ to L∞ with feedback if and only if for all (s, h) ∈ State \ State ∗ ,X1T (s, h) ∈ argmin 1 +H(s ◦ hzi, h0 ) .
|C(s ◦ hzi)| 0z∈X (c∗ )h ∈C(s◦hzi))

z ∈X
/ (h)

The minimum teaching time for teaching c∗ to L∞ with feedback is H(h i, init).
Lemma 11 is virtually the same as Lemma 5, only with a larger set of states. For
a given state (s, h) the sum in the minimization ranges over the hitting times of all
possible follow-up states. The main difference to the condition in Lemma 5 is that there
are no cyclic dependencies within the H-values. Intuitively, the reason for this is that alearner with infinite memory cannot reach the same state twice during a teaching process
because in each round the memory grows.
The lack of cyclic dependencies yields a straightforward inductive algorithm for computing all optimal hitting times. A state (s, h) with |s| = |X| has a hitting time ofH(s, h) = 0. The optimal hitting times for states with smaller memories can be computed using the first formula in Lemma 11, until finally the states with empty memory
are reached. This algorithm is called backward induction and runs in time polynomial in
the size the tabular representation of the MDP, but not polynomial in the representation
size of the teaching problem, that is, in the matrix representation of C.
A tempting idea for improvement is based on the observation that a teacher that gives
a minimum teaching set is always successful after TD(c∗ ) rounds. We shall call theseteachers MTS teachers. Not every such teacher is optimal, but one could conjecture that
there is at least one optimal teacher among them. This is, however, not always the case.
To show this, we use the following lemma, which gives an upper and lower bound for+ ∗E∞(c , C) in terms of the teaching dimension.
Lemma 12. Let C be a concept class and let c∗ ∈ C be a target. Then, for all µ ∈{1, . . . , TD(c∗ , C)} we have,Eµ− (c∗ , C) ≥ Eµ+ (c∗ , C) ≥µ(µ − 1)
+ TD(c∗ ) + 1 − µ ,2TD(c∗ , C)

and for all µ > TD(c∗ , C) and for µ = ∞,TD(c∗ , C) ≥ Eµ− (c∗ , C) ≥ Eµ+ (c∗ , C) ≥25

TD(c∗ , C).
2

Proof. Let k = TD(c∗ ) and µ ∈ {1, . . . , TD(c∗ )}. It suffices to show the statement
for Eµ+ . The proof is based on a simple observation.
Claim 1. For i examples z0 , . . . , zi−1 ∈ X (c∗ ) we have, |C({z0 , . . . , zi−1 })| ≥ k + 1 − i.
Proof. Assume |C({z0 , . . . , zi−1 })| ≤ k − i. Then c∗ can be specified with k − i − 1
examples with respect to C({z0 , . . . , zi−1 }) (each example rules out at least one concept).
Thus, c∗ can be specified with z0 , . . . , zi−1 plus k − i − 1 other examples, which amounts
to k − 1 examples. This contradicts TD(c∗ ) = k.
 Claim 1
Using Claim 1, we upper bound the probabilities for reaching the target in roundi = 0, . . . , µ − 2. After round i the learner knows i + 1 examples and therefore can choose
between at least k − i consistent hypotheses (see Claim 1). Thus, the probability forreaching c∗ in round i is at most pi = 1/(k − i). Beginning with round µ − 1, the learnerknows µ examples and has in each following round i ≥ µ − 1 a probability of at mostpi = pµ−1 = 1/(k + 1 − µ) of reaching c∗ .
No teaching process can be faster than one with the probabilities pi described above.
The expectation of such a process isµ−2X(i + 1) · pi ·

i=0

i−1
Y

∞
X

(1 − pj ) +j=0(i + 1) · pi ·

i=µ−1

i−1
Y

(1 − pj ) .

(17)

j=0

Qµ−2
the productWe first calculate the second sum in (17). Since j=0 (1 − pj ) = k−µ+1
k
Qi−1
k−µ+1
i−µ+1
(1
−
p
)
in
the
right
sum
equals
·
(1
−
p
)
and
the
whole
sum can be
j
µ−1
j=0
k
written as∞
X(i + 1) · pµ−1 · k−µ+1· (1 − pµ−1 )i−µ+1
k

i=µ−1

= k−µ+1·k∞X(µ + i) · pµ−1 · (1 − pµ−1 )i

i=0= k−µ+1
·
k

µ−1+

∞
X

!
i

(i + 1) · pµ−1 · (1 − pµ−1 ).

i=0

The sum appearing in the last line is the expectation of the first success in a Bernoulli
experiment with probability pµ−1 and thus equals 1/pµ−1 = k − µ + 1. For the second
sum in (17) we therefore get
k−µ+1· (µ − 1 + k − µ + 1)k

= k−µ+1 .

Calculating the first sum in (17) yields
µ−2
X
i=0

1
(i + 1) · k−i
·

i−1
Y
j=0

k−j−1
k−j

=

µ−2
X
i=0

1
(i + 1) · k−i
· k−i
=
k

µ(µ − 1).
2k

Putting it together, we obtain µ(µ−1)+ k + 1 − µ as the value of (17).
2k
26

init
c∗

x1
–
1
1
1
0
1
1
0
1
1
0
1
1
0

x2
–
1
1
0
1
1
0
1
1
0
1
1
0
1

x3
–
1
0
1
1
0
1
1
0
1
1
0
1
1

z
–
1
1
1
1
0
0
0
0
0
0
0
0
0

y1
–
1
0
1
1
1
1
1
1
1
1
1
1
1

y2
–
1
1
0
1
1
1
1
1
1
1
1
1
1

...
···
···
···

···

y11
–
1
1
1
1
1
1
1
1
1
1
1
0
1

y12
–
1
1
1
1
1
1
1
1
1
1
1
1
0

Figure 5: Concept class and target for which the optimal L∞ -teacher with feedback has not finishedafter TD(c∗ ) = 3 rounds. This class is C3,4 in the proof of Fact 13.

For µ > TD(c∗ ) the teaching process described above takes at most TD(c∗ ) rounds.
The lower bound is therefore the same as for µ = TD(c∗ ). Moreover, a teacher giving
the examples of a minimum teaching set is successful after TD(c∗ ) rounds, from which
follows TD(c∗ ) ≥ Eµ− (c∗ ) ≥ Eµ+ (c∗ ).

The expected teaching time of an MTS teacher is at most the teaching dimensionof the target. From Lemma 12 we know that an MTS teacher can have at most twice
the teaching time of an optimal teacher. Next, we show this bound to be asymptoticallytight.
Fact 13. For every k > 1 there is a family of concept classes and target concepts withteaching dimension k such that the ratio of any MTS teacher’s teaching time and the
optimal teaching time tends to 2 − O( k1 ).
Proof. For k, n > 1 we define the concept class Ck,n as follows. Let Xk = {x1 , . . . , xk }and Yk,n = {y1 , . . . , ykn } be sets of instances, and let Zk = Xk ∪Yk,n ∪{z} be the learning
domain. The target concept is c∗ = Zk , and there are, for every i = 1, . . . , k, exactly nconcepts c with Xk ∩ c = Xk \ {xi }, out of which exactly one satisfies c(z) = 1. The
instances in Yk,n serve to make all concepts distinct (see C3,4 in Figure 5).
There is only one minimum teaching set for c∗ , namely S = {(x1 , 1), . . . , (xk , 1)}. For
symmetry reasons, all MTS teachers have the same teaching time,
Hk,n

=


k i−1
X
Y
1
1
1
+
1−
·
·i .
(k − 1)n + 1 i=2 j=1(k − j)n + 1(k − i)n + 1

This value is bounded from above by |S| = k, and the last summand tends to k as ntends to infinity; thus limn→∞ Hk,n = k.
27

Now we consider the teacher that first teaches (z, 1) and then always the example
from S that is inconsistent with the observed hypothesis. Its expected teaching time is
0
Hk,n

=


k+1
X i−1
Y
1
1
1
k
+
1−
·
·i = 1+ .
k + 1 i=2 j=1
k−j+2
k−i+2
2

0
+ ∗
Since Hk,n
≥ E∞
(c , Ck,n ) ≥ k/2, we have

2

≥

+ ∗
0
lim Hk,n /E∞(c , Ck,n ) ≥ lim Hk,n /Hk,n
= 2−

n→∞

n→∞

4
.
k+2


+ ∗
We are going to show that there is most likely no algorithm approximating E∞(c , C)
up to a constant factor and running in time polynomial in the size of the matrix representation of C. Setting µ = ∞, we conclude from Lemma 12 that+ ∗TD(c∗ , C) ≥ E∞
(c , C) ≥TD(c∗ , C)
,
2

(18)

+ ∗
which means that every algorithm computing E∞(c , C) also computes a factor 2 approximation of the teaching dimension. Therefore, we continue with a closer look at thecomplexity of deciding and approximating the teaching dimension. Deciding whether
a given concept in a given class has a teaching dimension of less then a given value
is N P-complete [13, 12, 18]. This can be shown by a reduction from the SET-COVER
problem.
As an optimization problem, SET-COVER has been studied intensively, and it is relatively easy to translate these results to the problem of computing optimal teachingsets. For the formal definition of the MIN-TEACHING-SET problem we assume that
X = {1, . . . , k} for some k ∈ N+ and that C is represented as a binary |C| × k matrix. A concept is represented as a binary string of length k. In the following definitions
we use the terminology from Ausiello et al. [28].

Definition 5. The problem MIN-TEACHING-SET is the optimization problem with• instances of the form (C, c∗ ),• feasible solutions sol(C, c∗ ) = {s ∈ X ∗ | C(s) = {c∗ }},• a measure mes with mes((C, c∗ ), s) = |s| for all s ∈ sol(C, c∗ ).
Definition 6. The problem SET-COVER is the optimization problem with• instances of the form (U, V1 , . . . , Vk ) with a finite set U and sets V1 , . . . , Vk ⊆ U ,S|s|• feasible solutions sol(U, V1 , . . . , Vk ) = {s ∈ {1, . . . , k}∗ | i=1 Vs[i] = U },• a measure mes with mes((U, V1 , . . . , Vk ), s) = |s| for all s ∈ sol(U, V1 , . . . , Vk ).

28

The usual reductions from SET-COVER to MIN-TEACHING-SET considered in the literature (cf., e.g., [13, 12, 18]) map an instance (U, V1 , . . . , Vk ) of SET-COVER to the
MIN-TEACHING-SET instance ({c1 , . . . , c|U | , c∗ }, c∗ ) in which all concepts are subsets of{1, . . . , k}: cj = {i ∈ {1, . . . , k} | j ∈ Vi } and c∗ = ∅. Then the sets Vx1 , . . . , Vx` cover U
if and only if the examples (x1 , 0), . . . , (x` , 0) constitute a teaching set for c∗ .
On the other hand, every MIN-TEACHING-SET instance ({c1 , . . . , cn , c∗ }, c∗ ) over adomain X = {1, . . . , k} can be mapped to the SET-COVER instance (U, V1 , . . . , V|X| ),where U = {1, . . . , n − 1} and Vi = {j | ci (j) 6= c∗ (j)} for i = 1, . . . , |(|X). The examples(x1 , c∗ (x1 )), . . . , (x` , c∗ (x` )) then constitute a teaching set for c∗ if and only if the sets
Vx1 , . . . , Vx` cover U .
Thus, instances of both problems can be transferred into one another, with the representation size of the instances changing only slightly. In particular, for two corresponding
instances we have |C| − 1 = |U |. This means that the result by Feige [29], who shows
non-approximability for SET-COVER within a factor of (1 − ) ln |U |, can be formulated asfollows.
Theorem 14. The problem of computing a minimal teaching set is N P-hard. It cannot
be approximated in polynomial time within a factor of (1 − ) ln(|C| − 1) for all  > 0,
unless N P ⊆ DTime(nlog log n ).
In a similar way, other non-approximability results for SET-COVER (cf., e.g., Raz andSafra [30]) can be rephrased for MIN-TEACHING-SET.
The problem corresponding to MIN-TEACHING-SET in the TD model would be theproblem of finding an optimal teacher for L∞ with feedback. Such a teacher has a|X|!·|C|
representation size of O(|X|) and is thus not polynomial in the representation size
|C| · |X| of the teaching problem. Finding such an optimal teacher is therefore not an
N PO optimization problem (see Ausiello et al. [28]), and results about the hardness of
SET-COVER cannot be immediately transferred. But a closer look at the proofs of thesehardness results shows that also approximating this “set cover number” is hard in some+sense. We demonstrate such a reasoning in the next theorem, which shows that E∞is1
hard to approximate within a factor of 2 (1 − ) ln(|C| − 1) for any  > 0.
Theorem 15. If there is a polynomial time algorithm computing for all finite classes C
and concepts c ∈ C a rational number A(c, C) such that

1
2

+
E∞
(c, C)
p(1 − ) ln(|C| − 1)≤A(c, C)

≤

1
2

p

+
(1 − ) ln(|C| − 1) · E∞
(c, C)

for some  > 0, then N P ⊆ DTime(nO(log log n) ).
Proof. Suppose that there is such a polynomial time algorithm. Applying (18) we getTD(c, C)p

(1 − ) ln(|C| − 1)≤A(c, C)≤12p(1 − ) ln(|C| − 1) · TD(c, C).

Using the correspondence between SET-COVER and MIN-TEACHING-SET instances (seeabove), we conclude that there is also a polynomial time algorithm A0 computing for29every SET-COVER instance (U, V1 , . . . , Vk ) a value A0 (U, V1 , . . . , Vk ) with
SC (U, V1 , . . . , Vk )p
(1 − ) ln |U |≤A0 (U, V1 , . . . , Vk )

1
2

≤

p

(1 − ) ln |U | · SC (U, V1 , . . . , Vk )where SC (U, V1 , . . . , Vk ) is the minimal number of sets in V1 , . . . , Vk needed to cover U .
Now let Π be an N P decision problem and let Π+ and Π− be the set of positive andnegative instances, respectively. Feige [29, Theorem 4.4] shows that it is possible to map
every instance π ∈ Π in time nO(log log n) to a SET-COVER instance (U, V1 , . . . , Vk ) suchthat for an easily computable value Q:
π ∈ Π+ ⇐⇒ SC (U, V1 , . . . , Vk ) ≤ Q,(19)
π ∈ Π− ⇐⇒ SC (U, V1 , . . . , Vk ) > (1 − ) ln |U | · Q.
p
By checking the condition “A0 (U, V1 , . . . , Vk ) <(1 − ) ln |U | · Q” one can decide whether π is a positive or negative instance for Π: Assume the condition holds;
then SC (U, V1 , . . . , Vk ) < (1 − ) ln |U | · Q and by (19) we have π ∈pΠ+ . Now let
π ∈ Π+ ; then by (19) SC (U, V1 , . . . , Vk ) ≤ Q and A0 (U, V1 , . . . , Vk ) ≤ 21 (1 − ) ln |U | ·pp
SC (U, V1 , . . . , Vk ) ≤ 21 (1 − ) ln |U | · Q < (1 − ) ln |U | · Q.
It follows that it can be decided in time nO(log log n) whether any given π is a positive instance for the arbitrarily chosen N P problem Π. This means that N P ⊆DTime(nO(log log n) ).
Although Lemma 12 is responsible for a negative result about the approximability of+E∞, we can also draw a positive conclusion from it: if the TD-value is known, there is+often no need to compute the E∞-value. For example, the teachabilities of concepts orclasses for infinite memory learners with feedback can be compared by comparing theteaching dimensions of these concepts or classes.
+−
Another consequence of Lemma 12 is that the optimal teaching times E∞
and E∞of teaching with and without feedback differ by a factor of at most two. This meansthat feedback is not that much of a help when teaching randomized learners with infinite
memory.
−Finally, we briefly remark on the the hardness of approximating E∞. From Lemma 12∗− ∗∗we know that TD(c , C) ≥ E∞ (c , C) ≥ TD(c , C)/2. We can thus prove an analog to
Theorem 15.
Theorem 16. If there is a polynomial time algorithm computing for all c∗ , C a rational
number A(c∗ , C) such that−E∞
(c, C)
12p(1 − ) ln(|C| − 1)≤A(c∗ , C)

≤

1
2

p

− ∗
(1 − ) ln(|C| − 1) · E∞
(c , C)for some  > 0, then N P ⊆ DTime(nO(log log n) ).
5. Teaching Positive Examples Only or Inconsistent Ones
5.1. Teaching Positive Examples Only
The learnability of classes from positive data is a typical question in learning theory(cf., e.g., Gold [31] as well as Osherson et al. [32]). Similar restrictions on the data can30be posed in teaching models, too. In contrast to teaching with positive and negative
data, where all classes are teachable, we now get classes that are not teachable. Moreprecisely we have the following characterization for teachability with positive data.
Theorem 17. Let C be a concept class and c∗ ∈ C a target concept. Then for all learners
Lµ , where µ ∈ N+ ∪ {∞}, with or without feedback we have: The concept c∗ is teachable
from positive data if and only if there is no c ∈ C with c ⊃ c∗ .
Proof. For the if part, assume there is no proper superset of c∗ in the class. Thenthe set S + of all positive examples for c∗ is a teaching set for c∗ . Learners with infinite
memory can be taught by presenting S + , since they remember all examples and arealways consistent. Learners with smaller memory can be taught by infinitely repeating
S + in any order.
For the only-if part, assume there is a c ∈ C with c ⊃ c∗ . Let z = (x, 1) ∈ X (c∗ )be the first example taught. Then c ∈ C(z) and therefore there is a positive probability
that the randomized learner picks c as first hypothesis. In this case, it is impossible
to trigger any further mind changes by giving positive examples. Consequently, withpositive probability the number of examples is infinite; thus leading to an infinite expected
number of examples.

Theorem 17 also characterizes teaching with positive data in the classical teaching
dimension model. If there is no c ⊃ c∗ , the set of all positive examples of c∗ is a teachingset, but if there is a c ⊃ c∗ , then every set of positive examples for c∗ is also consistent
with c.
We have seen that teachability with positive data has a simple characterization.
Things become a little more complicated when combined with inconsistent teachers discussed in the next section.
5.2. Inconsistent Teachers
Until now, teachers were required to always tell the truth, i.e., to provide examplesz ∈ X (c∗ ). In reality it might sometimes be worthwhile to teach something which is,strictly speaking, not fully correct, but nevertheless helpful for the students. For example,
human teachers sometimes oversimplify to give a clearer, yet slightly incorrect, view on
the subject matter.
To model this we allow the teacher to present any example from X × {0, 1}, even if
it is inconsistent with the target. One can see this as an analog to inconsistent learners
in learning theory, as these learners also contradict something they actually know.
Clearly, teaching learners with infinite memory becomes difficult after giving an inconsistent example because the target is not consistent with the memory contents any
more. Even worse, there might be no consistent hypothesis available. However, themodel can be adapted to this, e.g., by stipulating that a memorized example (x, v) canbe “erased” by the example (x, 1 − v), but here we will not pursue this further. We
restrict ourselves to consider only the 1-memory learner.
But even in this scenario a few modifications of the definitions are necessary. First,
we need to explain what the learner is supposed to do when given an example that is notconsistent with any concept in C, a situation that cannot arise with consistent teachers,
since the target concept will always be consistent to any example given. We stipulate31that in such a case, the learner simply does not change the hypothesis. This implies thatsuch an example does not change the learner’s state and is thus useless from a teacher’s
perspective.
The second minor change concerns the definition of success probability (cf. Definition 2). The limit mentioned in this definition does not need to exist if the teacher isinconsistent, because whenever it presents an inconsistent example the probability for thelearner to assume the target hypothesis is zero. This is easily remedied by considering ateacher for which the limit does not exist as unsuccessful.
We consider inconsistent teachers only in combination with teaching from positive
data. In this case, for a target concept c∗ , the only inconsistent examples allowed are of
the form (x, 1), where x ∈/ c∗ . The class C1 in Figure 6 shows that, when only positive
data are allowed, inconsistent teachers can teach concepts to L1 with feedback thatconsistent teachers cannot. First, the teacher gives (x1 , 1). If the learner guesses c∗ , weare done. Otherwise, the learner must hypothesize c1 and the teacher gives (x3 , 1) whichis inconsistent with c∗ . Now, the learner has to guess c2 . Next, (x1 , 1) is again given andthe process is iterated until the learner hypothesizes c∗ . On the other hand, it follows
from Theorem 17 that c∗ cannot be taught by a consistent teacher from positive data,
because c1 ⊃ c∗ .
C1 :
init:
c∗ :
c1 :
c2 :

x1
–
1
1
0

x2
–
0
1
0

x3
–
0
0
1

C2 :

T
x1
–
x3
x1

init:
c∗ :
c1 :
c2 :

x1
–
0
1
0

x2
–
1
1
1

x3
–
0
0
1

Figure 6: The class C1 can be taught to L1 with feedback by the inconsistent positive-data teacher T ,but cannot be taught by a consistent positive-data teacher (Theorem 17). The class C2 cannot be taught
by an inconsistent positive-data teacher (Fact 18).

However, consistent teachers with both positive and negative data are more powerful,as we show next.
Fact 18. There is a class that cannot be taught to L1 with feedback by an inconsistentteacher from positive data.
Proof. We show that C2 from Figure 6 is such a class. Let T : C2 ∪{init} → {x1 , x2 , x3 }×{1} be a teacher for L1 with feedback. No matter what T (init) is, the probability that thelearner switches to c1 or c2 is positive. If the learner guesses c1 (the c2 case is analogous),
the teacher must teach (x3 , 1), since all other examples are consistent with the current
hypothesis c1 . But the only hypothesis consistent with (x3 , 1) is c2 . Analogously, T
must give (x1 , 1) when the learner is in c2 , leading again to c1 . Therefore the probability
that L1 never reaches c∗ is positive.
Classes teachable by inconsistent teachers from positive data can be characterized.
We associate a directed graph with the class C. Define the graph G(C) = (V, A) by V = C
and A = {(c, d) | d \ c 6= ∅}, i.e., there is an arc from c to d iff there is a positive exampleinconsistent with c but consistent with d.
32

Theorem 19. Let C be a concept class and G(C) = (V, A) its associated graph. For thelearner L1 with feedback a concept c∗ ∈ C is teachable by an inconsistent teacher frompositive data iff for all c ∈ V there is a path to c∗ in G(C).
Proof. For the if part we have to describe a teacher. For each c let c0 be a neighborof c on a shortest path to c∗ . Let T be such that for all c, T (c) is consistent with c0 ,but not with c. There is always such an example due to the definition of G(C) and thereachability assumption.
Denote by n = |C| and by p = 1/n the minimum probability for reaching c0 when thelearner receives T (c) in state c. If the learner is in any state c, there is a probability ofat least pn > 0 for reaching c∗ within the next n rounds by traversing the shortest pathfrom c to c∗ . Therefore, no matter in which state the learner is, the expected numberof n-round blocks until reaching the target is at most 1/pn . Thus, the expected time toreach the target from any state, in particular from init, is at most n/pn < ∞.
For the only-if part, let T be a teacher for c∗ ∈ C. Suppose that there is a state cwith no path to c∗ . Then c ⊃ c∗ (otherwise c∗ \ c 6= ∅ and (c, c∗ ) ∈ A). At some time, T
must teach an example consistent with c∗ , which is then also consistent with c. Hence,the probability for reaching c during the teaching process is positive. The graph G(C)contains all transitions that are possible between the hypotheses by positive examples.
Since c∗ is not reachable from c in G(C) there is no sequence of positive examples that
can trigger hypothesis changes from c to c∗ . Thus, the expected teaching time from c
is infinite and hence the expected teaching time altogether. A contradiction to c∗ being
teachable by T .
The criterion in Theorem 19 requires to check the reachability of a certain node fromall other nodes in a directed graph. This problem is related to the REACHABILITY problem
and also complete for the complexity class NL.
While inconsistent teachers can teach classes to 1-memory learners with feedback frompositive data that consistent teachers cannot teach to L1 with feedback (cf. Figure 6),
the situation changes if no feedback is available. That is, 1-memory learners without
feedback can be taught the same classes by inconsistent teachers as by consistent teachers(cf. Theorem 17 and Theorem 20 below).
Theorem 20. For the learner L1 without feedback a concept c∗ ∈ C is teachable by aninconsistent teacher from positive data iff there is no c ∈ C with c ⊃ c∗ .
Proof. The if-direction follows from Theorem 17.
For the only-if part suppose that c∗ is teachable by a teacher T and there is a c withc ⊃ c∗ .
Claim: T gives examples inconsistent with c∗ only finitely often.
Proof. Suppose T gives an example (x, 1) ∈/ X (c∗ ) infinitely often. Without loss ofgenerality we assume that there is a concept in C that contains x (otherwise (x, 1) would
be useless and a teacher never giving this example would be successful, too). Whenever(x, 1) is presented, the learner will not be in state c∗ afterwards, i.e., there are infinitely(t)(t)
many t such that δT (c∗ ) = 0. It follows that the limit limt→∞ δT (c∗ ) either does notexist or equals zero, which means that the teacher T is not successful; a contradictionthat proves the claim.
 (Claim)
33

Let t0 be the latest time point at which T presents an example inconsistent with c∗(the existence of t0 has been proved by the claim). Therefore the learner is not in statec∗ at round t0 + 1. Moreover T (t0 + 1) will be consistent with c∗ (by definition of t0 )and thus consistent with c ⊃ c∗ as well. For this reason, the learner will assume thehypothesis c in round t0 + 2 with positive probability. Since all following examples are
consistent with c∗ , and thus with c, there is a positive probability that the learner will
stay in c and never reach c∗ . In other words, the success probability is less than one, acontradiction. This proves the only-if part.

6. Conclusions and Future Work
We have presented a model for teaching randomized learners based on the classicalteaching dimension model. In our model, teachability depends, in a qualitatively plausible way, on the learner’s memory size. Intuitively, this holds, since the more examples
the learner memorizes the higher the probability of reaching the target. Also, teachability depends on the learner’s ability to give feedback, since this enables the teacher totrigger in every round a hypothesis change. Furthermore, as we have seen, teachability
is influenced by the order of the examples taught.
The model also allows to study learning theory like questions such as teaching frompositive data only or teaching by inconsistent teachers.
As already mentioned, if the teacher receives no feedback the results about SSPPs,
including Lemma 4, do not apply. The notion corresponding to this teaching scenario
is that of an unobservable stochastic shortest path problem (USSPP). In this setting, itmuch more complicated to derive an optimality criterion and thus, we shall present results
along this line of research in a subsequent paper and refer the reader to Balbach andZeugmann [21] for a first insight. Randomization also gives more flexibility in defining thelearner’s behavior by using certain a priori probability distributions over the hypotheses.
So, one can define and study learners preferring simple hypotheses. But the resulting
models seem to be much harder to analyze.
Furthermore, one could aim at modifying our model as follows. Instead of allowing thelearner to pick a hypothesis uniformly at random from all consistent hypotheses, it may
seem more “natural” to allow the learner to pick a hypothesis uniformly at random fromall consistent hypotheses that are within a certain neighborhood of the learner’s current
hypothesis. Such an approach would require to define an appropriate neighborhood
relation. As a matter of fact, we have already considered such a modification of the
traditional (non-randomized) TD model (cf. [33, 22]). Again, in such models feedback
can be very helpful. The order of examples is also crucial, and the learner’s memory
size influences the teaching time and also whether or not a concept is teachable at all.
All these effects can be achieved by defining appropriate neighborhood relations. On theother hand, it will require further research to arrive at a notion of “natural” neighborhood
relations.
Instead of considering the memory as queue as done here, one could and should also
study learners that have a selective memory, i.e., they still memorize only µ examples
but decide themselves which examples to keep in the memory. Models allowing such a
selective memory have been studied in algorithmic learning theory and shown to be quite
useful (cf., e.g., [34, 35]). Studies in this direction may also reveal more insight into the
problem of how informative particular examples are, or more generally, into the question34

of how to measure the information content of a sample. In this regard, it should be
mentioned that teaching sets should be considered as samples having a high information
content. We did not focus on this connection in the present paper, since it seems thatmuch more research is necessary to explore it.
Acknowledgment
We would like to thank the referees for many valuable comments and suggestions
which have resulted in several improvements of the presentation of the paper.
References[1] D. Angluin, Queries and concept learning, Machine Learning 2 (4) (1988) 319–342.
[2] D. Angluin, Queries revisited, Theoret. Comput. Sci. 313 (2) (2004) 175–194.
[3] R. Freivalds, E. B. Kinber, R. Wiehagen, Inductive inference from good examples, in: Analogicaland Inductive Inference, International Workshop AII ’89, Reinhardsbrunn Castle, GDR, October
1989, Proceedings, Vol. 397 of Lecture Notes in Artificial Intelligence, Springer-Verlag, 1989, pp.
1–17.
[4] R. Freivalds, E. B. Kinber, R. Wiehagen, On the power of inductive inference from good examples,
Theoret. Comput. Sci. 110 (1) (1993) 131–144.
[5] S. Jain, S. Lange, J. Nessel, On the learnability of recursively enumerable languages from good
examples, Theoret. Comput. Sci. 261 (1) (2001) 3–29.
[6] J. Jackson, A. Tomkins, A computational model of teaching, in: Proc. 5th Annual ACM Workshop
on Computational Learning Theory, ACM Press, New York, NY, 1992, pp. 319–326.
[7] S. A. Goldman, H. D. Mathias, Teaching a smarter learner, J. of Comput. Syst. Sci. 52 (2) (1996)
255–267.
[8] H. D. Mathias, A model of interactive teaching, J. of Comput. Syst. Sci. 54 (3) (1997) 487–501.
[9] D. Angluin, M. Kriķis, Teachers, learners and black boxes, in: Proceedings of the Tenth Annual
Conference on Computational Learning Theory, July 6th–9th, 1997, Nashville, Tennessee, ACM
Press, New York, NY, 1997, pp. 285–297.
[10] D. Angluin, M. Kriķis, Learning from different teachers, Machine Learning 51 (2) (2003) 137–163.
[11] S. A. Goldman, R. L. Rivest, R. E. Schapire, Learning binary relations and total orders, SIAM J.
Comput. 22 (5) (1993) 1006–1034.
[12] S. A. Goldman, M. J. Kearns, On the complexity of teaching, J. of Comput. Syst. Sci. 50 (1) (1995)
20–31.
[13] A. Shinohara, S. Miyano, Teachability in computational learning, New Generation Computing 8 (4)(1991) 337–348.
[14] M. Anthony, G. Brightwell, J. Shawe-Taylor, On specifying Boolean functions by labelled examples,
Discrete Applied Mathematics 61 (1) (1995) 1–25.
[15] F. J. Balbach, Teaching classes with high teaching dimension using few examples, in: Learning
Theory: 18th Annual Conference on Learning Theory, COLT 2005, Bertinoro, Italy, June 27-30,
2005, Proceedings, Vol. 3559 of Lecture Notes in Artificial Intelligence, Springer, 2005, pp. 668–683.
[16] C. Kuhlmann, On teaching and learning intersection-closed concept classes, in: Computational
Learning Theory, 4th European Conference, EuroCOLT ’99, Nordkirchen, Germany, March 29-31,
1999, Proceedings, Vol. 1572 of Lecture Notes in Artificial Intelligence, Springer, 1999, pp. 168–182.
[17] H. Lee, R. A. Servedio, A. Wan, DNF are teachable in the average case, in: Learning Theory: 19th
Annual Conference on Learning Theory, COLT 2006, Pittsburgh, PA, USA, June 2006, Proceedings,
Vol. 4005 of Lecture Notes in Artificial Intelligence, Springer, Berlin, 2006, pp. 214–228.
[18] M. Anthony, G. Brightwell, D. Cohen, J. Shawe-Taylor, On exact specification by examples, in:Proc. 5th Annual ACM Workshop on Computational Learning Theory, ACM Press, New York,NY, 1992, pp. 311–318.
[19] B. K. Natarajan, Machine Learning: A Theoretical Approach, Morgan Kaufmann, San Mateo, CA,
1991.
[20] E. Kushilevitz, N. Linial, Y. Rabinovich, M. Saks, Witness sets for families of binary vectors,
Journal of Combinatorial Theory Series A 73 (2) (1996) 376–380.

35

[21] F. J. Balbach, T. Zeugmann, Teaching memoryless randomized learners without feedback, in: Algorithmic Learning Theory, 17th International Conference, ALT 2006, Barcelona, Spain, October
2006, Proceedings, Vol. 4264 of Lecture Notes in Artificial Intelligence, Springer, 2006, pp. 93–108.
[22] F. Balbach, Models for Algorithmic Teaching, Dissertation, Universität zu Lübeck, Lübeck, 2007.
[23] M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John
Wiley & Sons, 1994.
[24] D. P. Bertsekas, Dynamic Programming and Optimal Control, Athena Scientific, 2001.
[25] D. P. Bertsekas, J. N. Tsitsiklis, An analysis of stochastic shortest path problems, Mathematics ofOperations Research 16 (3) (1991) 580–595.
[26] S. D. Patek, On partially observed stochastic shortest path problems, in: Proceedings of the 40 thIEEE Conference on Decision and Control (CDC 2001). IEEE Part, 1999, pp. 5050–5055.
[27] S. D. Patek, Partially observed stochastic shortest path problems with approximate solution by neurodynamic programming, IEEE Transactions on Systems, Man, and Cybernetics–Part A: Systems
and Humans 37 (5) (2007) 710–720.
[28] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity
and Approximation: Combinatorial Optimization Problems and Their Approximability Properties,
Springer, New York, 1999.
[29] U. Feige, A threshold of ln n for approximating set cover, J. of the ACM 45 (4) (1998) 634–652.
[30] R. Raz, S. Safra, A sub-constant error-probability low-degree test, and a sub-constant errorprobability PCP characterization of NP, in: Proc. of the 29th ACM Symposium on Theory ofComputing, ACM Press, 1997, pp. 475–484.
[31] E. M. Gold, Language identification in the limit, Inform. Control 10 (5) (1967) 447–474.
[32] D. N. Osherson, M. Stob, S. Weinstein, Systems that Learn: An Introduction to Learning Theory
for Cognitive and Computer Scientists, MIT Press, Cambridge, Massachusetts, 1986.
[33] F. J. Balbach, T. Zeugmann, Teaching learners with restricted mind changes, in: Algorithmic
Learning Theory, 16th International Conference, ALT 2005, Singapore, October 2005, Proceedings,
Vol. 3734 of Lecture Notes in Artificial Intelligence, Springer, 2005, pp. 474–489.
[34] J. Case, S. Jain, S. Lange, T. Zeugmann, Incremental concept learning for bounded data mining,
Inform. Comput. 152 (1) (1999) 74–110.
[35] S. Lange, T. Zeugmann, Incremental learning from positive data, J. of Comput. Syst. Sci. 53 (1)(1996) 88–103.

36