Teaching Randomized Learners
Frank J. Balbach1 and Thomas Zeugmann2
1

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

Abstract. The present paper introduces a new model for teaching randomized learners. Our new model, though based on the classical teaching dimension model, allows to study the influence of various parameterssuch as the learner’s memory size, its ability to provide or to not provide
feedback, and the influence of the order in which examples are presented.
Furthermore, within the new model it is possible to investigate new aspects of teaching like teaching from positive data only or teaching withinconsistent teachers.
Furthermore, we provide characterization theorems for teachability frompositive data for both ordinary teachers and inconsistent teachers withand without feedback.

1

Introduction

A natural teaching model consists of a teacher giving examples to a set of students with the goal that all students eventually hypothesize a certain target
concept. Typically the admissible students are deterministic learning algorithms
and the teaching performance is measured with respect to the worst case student.
In the present paper we modify this model by assuming a partly randomized student and by measuring teaching performance in an average case fashion.
Our model is based on the teaching model introduced independently, and indifferent forms, by Shinohara and Miyano [19], Goldman et al. [11], Goldman
and Kearns [9] as well as Anthony et al. [5]. Here, a teacher has to give enoughexamples to uniquely identify the target concept among all concepts in a givenclass. Thus, the students are all deterministic consistent learning algorithms.
By varying the set of admissible learners, the influence of different propertiesof the learners 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 a concept to all consistent learning algorithms, the teacher must present all
2n examples. Teaching a concept to all consistent learners that can memorize lessthan 2n examples is impossible; there is always a learner with a consistent, but

230

F.J. Balbach and T. Zeugmann

wrong hypothesis. So teaching gets indeed harder, but in a rather abrupt way.
Moreover, it does not matter whether or not the teacher knows the learner’s
hypothesis, since there are deterministic learners choosing their next hypothesis
independently of their current one.
It seems that the worst case analysis style makes it impossible to investigate
the influence of memory limitations or learner’s feedback. A common remedy
for this is to perform an average case analysis instead. In the present paper, we
propose a rather radical approach, i.e., we replace the set of learners by a single
one that is intended to represent an “average learner.”
We achieve this goal by substituting the set of deterministic learners by asingle 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. For ensuring that thelearner maintains this correct hypothesis, we additionally require the learner tobe conservative, i.e., it can change its hypotheses only on examples that areinconsistent with its current hypothesis. The complexity of teaching is measured
by the expected teaching time (cf. Section 2).
Next, we explain why this model should work. Intuitively, since at every
round there is a chance to reach the target, the target will eventually be reachedeven if, for instance, the randomized learner can only memorize few examples.
Moreover, the ability of the teacher to observe the learner’s current hypothesis
should be advantageous, since it enables the teacher to teach an inconsistentexample in every round. Recall that only these examples can cause a hypothesischange. In Section 3, we show these intuitions to be valid.
Randomized learners show another phenomenon, too: The complexity of theteaching process now does not only depend on the examples, but also on theorder in which they are given.
The randomized teaching model can be regarded as a Markov Decision Process. Such processes have been studied for several decades and we will make useof some results from this theory (cf. Subsection 2.3).
Sections 4 and 5 study teaching with and without feedback, respectively.
Here, we focus on computing the optimal teaching times. In Sections 6 to 8 westudy variations of our model: teaching from positive data, inconsistent teachers
and another restriction on teachers. Theorems characterizing teachability withinthese model are shown.
Note that there are also other approaches to teaching. They differ from theone discussed here, since the learner is not given, but constructed to fit to theteacher. One such model is learning from good examples (cf. Freivalds et al. [8]and Jain et al. [13]). Jackson and Tomkins [12] as well as Goldman and Mathias [10] and Mathias [15] defined models of teacher/learner pairs. In their models,a kind of adversary disturbing the teaching process is necessary to avoid collusion
between the teacher and the learner. Angluin and Kriķis’ [3, 4] model prevents
collusion by giving incompatible hypothesis spaces to teacher and learner.

Teaching Randomized Learners

2

Preliminaries

2.1

Notations231

Set inclusion and proper set inclusion is denoted by “⊆” and “⊂,” respectively.
For numbers a, b with a < b we write [a, b] to denote the set {a, a + 1, . . . , b} or{a, a + 1, . . . } if b = ∞.
Let X be a finite instance space and X = X × {0, 1} the corresponding set ofexamples. A concept class is a set C ⊆ 2X of concepts c ⊆ X. An example (x, v)
is positive if v = 1 and negative if v = 0. We denote the set of all examples fora concept c by X (c) = {(x, v) v = 1 ⇐⇒ x ∈ c} ⊂ X . An example (x, v) iscalled consistent with c iff (x, v) ∈ X (c).
A teaching set for a concept c ∈ C with respect to C is a set S of examples suchthat c is the only concept in C consistent with S. The teaching dimension TD(c)is the size of the smallest teaching set. We set TD(C) := max{TD(c) c ∈ C}.
For any set S, we denote by S ∗ the set of all finite lists of elements from S, bym
S and S ≤m the set of all lists with length m and at most length m, respectively.
The operator ◦µ concatenates a list of length at most µ with a single element
resulting in a list of length at most µ: hx1 , . . . , x` i ◦µ hyi equals hx1 , . . . , x` , yi if` < µ and hx2 , . . . , x` , yi if ` = µ. We regard ◦∞ as the usual list concatenation.
For a list x of examples, we set C(x) = {c ∈ C x is consistent with c}.
We denote by Mn the concept class of monomials over {0, 1}n . We exclude
the empty concept from Mn and can thus identify each monomial with a stringfrom {0, 1, ∗}n and vice versa. Dn is the set of all 2n concepts over [1, n]. The
singleton classes are defined as Sn = {{x} x ∈ [1, n]}.
2.2

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 andcomputes a new hypothesis based on its last hypothesis and the known examples.
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, the hypothesis is chosen at random from all consistent ones.
The memory of our learners may be limited to µ ≥ 1 examples. If the memory
is full and 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 teaching is making the learner to hypothesize the target and tomaintain it. Consistency alone cannot guarantee this behavior if the memory is
too small. In this case, there is more than one consistent hypothesis at every
round and the learner would oscillate between them rather than maintaining asingle one. To avoid this, conservativeness is required, i.e., the learner can change
its hypothesis only when taught an example inconsistent with its current one.
To study the influence of the learners’ feedback to the teacher, we distinguishbetween private and public output of the learner. The private output is the resultof the calculation during a round (i.e., new memory content and hypothesis), the232

F.J. Balbach and T. Zeugmannpublic output is that part of the private one observable by the teacher. So, if
the learner gives feedback, the teacher can observe in every round the complete
hypothesis computed by the learner. If the learner does not give feedback, theteacher can observe nothing.
The following algorithm describes the behavior of the µ-memory learner−
with/without feedback (short: L+µ / Lµ ) during one round of the teaching process.
Input: memory x ∈ X ≤µ , hypothesis h ∈ C, example z ∈ X .
Private Output: memory x0 , hypothesis h0 .
Public Output: hypothesis h0 / nothing.
1 x0 := x ◦µ hzi;
2 if z ∈/ X (h) then pick h0 uniformly at random from C(x0 );
3else h0 := h;
For making 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 inconsistent with init. Thus, init is left after the firstexample and cannot be reached again. Moreover, the initial memory is empty.
The Teacher. A teacher is an algorithm taking initially a given target conceptc∗ as input. Then, in each round, it receives the public output of the learner (ifany) and outputs an example for c∗ .
Definition 1. Let C be a concept class and c∗ ∈ C. Let Lσµ be a learner (σ ∈{+, −}) and T be a teacher and (hi )i∈N be the series of random variables forthe hypothesis at round i. The event “teaching success in round t,” denoted by
Gt , is defined as
ht−1 6= c∗ ∧ ∀t0 ≥ t : ht0 = c∗ .
hSi
The success probability of T is Pr t≥1 Gt . A teaching process is successful iff the success probability equals
teaching process is called
hS1. A successfulifinite iff there is a t0 such that Pr 1≤t≤t0 Gt = 1, otherwise it is called infinite. For a successful
teaching process we define the expected teaching time as
E[T, Lσµ , c∗ , C] := Pt≥1 t · Pr[Gt ].
Definition 2. Let C be a concept class, c∗ ∈ C and Lσµ a learner. We call c∗teachable to Lσµ iff there is a successful teacher T . The optimal teaching time
for c∗ is
Eµσ (c∗ ) := inf E[T, Lσµ , c∗ , C]T

and the optimal teaching time for C is denoted by Eµσ (C) := maxc∈C Eµσ (c).
2.3Markov Decision Processes

For an extensive treatment of this topic see Puterman [17] and Bertsekas [6]. A
Markov Decision Process (MDP) is a probabilistic system whose state transitions
can be influenced during the process by actions which incur costs. Formally, anTeaching Randomized Learners

233

MDP consists of a finite set S of states, an initial state s0 ∈ S , a finite set A
of actions, a function cost : S × A → R, and a function p : S × A × S → [0, 1];cost(s, a) is the cost incurred by action a in state s; p(s, a, s0 ) is the probability
for the MDP to change from state s to s0 under action a.
In the total cost infinite horizon setting, the goal is to choose actions suchthat the expected total cost, when the MDP runs forever, is minimal. This makes
sense only if there is a costless absorbing state s∗ ∈ S . In the finite horizon setting
the MDP is only run for finitely many rounds.
The actions chosen at each point in time are described by a policy. This is afunction depending on the observed history of the MDP and the current state.
A basic result says that there is a minimum-cost policy that is stationary, i.e.,that depends only on the current state. A stationary policy π : S → A defines a
Markov chain over S and for all s ∈ S an expected time H(s) to reach s∗ from s.
Such a policy is optimal iff for all s ∈ S :!
X
π(s) ∈ argmin cost(s, a) +p(s, a, s0 ) · H(s0 ) .
a∈A

s0 ∈S

Finding optimal policies can be phrased as a linear programming problem
and can thus be done in polynomial time in the representation size of the MDP.

3

Varying Memory Size and Feedback

As a simple example, we calculate the optimal teaching times for Dn . To thelearner L+µ (1 ≤ µ ≤ n) the teacher can give an example inconsistent withthe current hypothesis in each round. For all such examples, there are 2n−µhypotheses consistent with the µ examples in the learner’s memory and learnerchooses one of them. Therefore the probability of choosing the target concept is2−(n−µ) . Thus, considering that in the first µ − 1 rounds the memory contains
less then µ examples, Eµ+ (Dn ) is, for constant µ, asymptotically equal to 2n−µ .
Clearly, teaching becomes faster with growing µ. Moreover the teaching speed
increases continuously with µ and not abruptly as in the classical deterministic
model. In particular, teaching is possible even with the smallest memory size(µ = 1), although it takes very long (2n−1 rounds).
Teaching is more difficult when feedback is unavailable. In this situation theteacher can merely guess examples hoping that they are inconsistent with thecurrent hypothesis. Roughly speaking, when teaching Dn , the teacher needs twoguesses on average to find such an example. Hence, the expected teaching timeEµ− is about two times Eµ+ . Thus feedback doubles the teaching speed for Dn .
Fact 3. For all C and µ ∈ [1, ∞] all c∗ ∈ C and σ ∈ {+, −}:σσ(1) Eµ+ (c∗ ) ≤ Eµ− (c∗ ),(2) E∞(c∗ ) ≤ Eµσ (c∗ ).
(c∗ ) ≤ Eµ+1
Proper inequality holds for the concepts in Dn .
Next, we relate the deterministic model (in terms of the teaching dimension)to the randomized model (in terms of the expected teaching time). Essentially,
the teaching dimension can be used to lower bound the teaching time.

234

F.J. Balbach and T. Zeugmann

Lemma 4. Let C be a class and let c∗ ∈ C be a target. For all µ ∈ [1, TD(c∗ )],Eµ− (c∗ ) ≥ Eµ+ (c∗ ) ≥µ(µ − 1)
+ TD(c∗ ) + 1 − µ,2TD(c∗ )and for all µ > TD(c∗ ), Eµ− (c∗ ) ≥ Eµ+ (c∗ ) ≥ TD(c∗ )/2.
Proof. Let k = TD(c∗ ) and µ ∈ [1, TD(c∗ )]. We show the statement for Eµ+ .
Claim: For i examples z0 , . . . , zi−1 ∈ X (c∗ ): |C(z0 , . . . , zi−1 )| ≥ k + 1 − i.
Proof : Suppose |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.
t ClaimuUsing the claim we upper bound the probabilities for reaching the target
in round i = 0, . . . , µ − 2. After round i the learner knows i + 1 examples andtherefore can choose between at least k − i consistent hypotheses (see Claim).
1. BeginningThus, the probability for reaching c∗ in round i is at most pi := k−iwith round µ − 1, the learner knows µ examples and has in each following roundi ≥ µ − 1 a probability of at most pi = pµ−1 = 1/(k + 1 − µ) of reaching c∗ .
No teaching process can be faster than one with the probabilities pi describedabove. 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 ) .

(1)

j=0

Qµ−2
the productWe start with the second sum in (1). Since j=0 (1 − pj ) = k−µ+1
k
Qi−1
k−µ+1
i−µ+1
· (1 − pµ−1 ). So, this sum is
j=0 (1 − pj ) in the this sum equalsk∞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 (1) we therefore get k−µ+1· (µ − 1 + k − µ + 1) = k − µ + 1 .
kCalculating the first sum in (1) 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 (1).
2k∗

For µ > TD(c ) the teaching process described above takes at most TD(c∗ )turounds. The lower bound is therefore the same as for µ = TD(c∗ ).

Teaching Randomized Learners

235

Input: Target c∗ ∈ Mn represented by γ1 . . . γn ∈ {0, 1, ∗}n ;Hypothesis h ∈ Mn represented by η1 . . . ηn ∈ {0, 1, ∗}n .
Output: Example z ∈ X (c∗ ).
8>γi
if ηi = γi 6= ∗,<1 if h ⊃ c∗ output (χ1 . . . χn , 0) with χi = 1 − γi if i = min{j ηj = ∗ 6= γj },>:0otherwise;∗
2 else output (x, 1) with arbitrary x ∈ c .
Fig. 1. Optimal teacher for monomials and the learner L+
1 .

4

Learners with Feedback

4.1

Learners with 1-Memory

A teaching process involving L+
1 can be modeled as an MDP with S = C ∪{init},
A = X (c∗ ), cost(h, z) = 1 for h 6= c∗ and cost(c∗ , z) = 0. Furthermore, for h 6= c∗ ,p(h, z, h0 ) = 1/|C(z)| if z ∈ X (h0 ) \ X (h) and p(h, z, h0 ) = 0 otherwise; finallyp(c∗ , z, c∗ ) = 1. The initial state is init and the state c∗ is costless and absorbing.
The memory does not need to be part of the state, since the next hypothesis
only depends on the newly given example which is modeled as an action.
An example z ∈ X (h) does not change the learner’s state h and is therefore
useless. An optimal teacher refrains from teaching such examples and thus wecan derive the following criterion by using the results from Subsection 2.3.
Lemma 5. Let C be a class over X and c∗ be a target. A teacher T : C ∪{init} →X (c∗ ) with expectations H : C ∪ {init} → R is optimal iff for all h ∈ C ∪ {init}:X
1
H(h0 ) .
T (h) ∈ argmin 1 +|C(z)| 0z∈X (c∗ )h ∈C(z)

z ∈X
/ (h)

This criterion can be used to prove optimality for teaching algorithms.
Fact 6. The teacher in Fig. 1 is an optimal teacher for Mn and the learner L+
1.
+2 )−2
Proof. We define H : C ∪{init} → R as H(h) = (3 −2 3n)(2−2n +2k−1
n

n

n

n

k

n+k−1

n+1

n

n

k

n+k−1

for h ⊃ c∗

n

)−2
+2
−3
and H(h) = (3 −2 )(2 3+2
for all other h, including init.
n −2n +2k−1
It is possible (though tedious) to show that H describes the teaching times
for T and that T and H satisfy the criterion of Lemma 5.
tu

The teacher from Fig. 1 can be computed in linear time. It outputs a positive
example whenever possible (i.e., when h 6⊃ c∗ ). Since there are 2n hypotheses
consistent with a positive example and 3n − 2n consistent with a negative one,this means following a greedy strategy minimizing the number of consistenthypotheses for the learner to choose from, thus maximizing the probability forreaching c∗ in the next step.
Such a greedy strategy seems sensible and is provably optimal in the caseof Mn . However, there are classes where no greedy teacher is optimal.

236

F.J. Balbach and T. Zeugmann

Definition 7. Let C be a class over X and c∗ ∈ C. A stationary teacher T : C ∪{init} → X for c∗ is called greedy iff for all h ∈ C: T (h) ∈ argminz∈X (c∗ ) |C(z)|.
z ∈C(h)/Fact 8. There is a class C and target c0 such that no greedy teacher is optimal.
Proof. Figure 2 displays such a concept class C and target c0 . T ∗ with teachingtimes H ∗ is an optimal teacher and T g with H g is the only greedy teacher. uth x1 x2 x3 x4 x5
init – – – – –c0 1 1 1 1 1
c1 0 0 0 0 1
c2 0 0 0 1 1
c3 0 0 1 0 1
c4 0 0 1 1 1
c5 0 1 0 1 1
c6 0 1 1 0 1
c7 0 1 1 1 1
c8 1 0 0 1 0
c9 1 1 1 0 0
c10 1 1 1 1 0

T ∗ (h)
x1
–
x1
x1
x1
x1
x1
x1
x1
x2
x5
x5

H ∗ (h)176/35=5.0285. . .
0176/35
176/35
176/35
176/35
176/35
176/35
176/35186/35
189/35
189/35

T g (h)
x1
–
x1
x1
x1
x1
x1
x1
x1
x2
x4
x5

H g (h)2536/504=5.0317. . .
02536/504
2536/504
2536/504
2536/504
2536/504
2536/504
2536/504
2680/504
2725/504
2723/504

Fig. 2. Class with an optimal teacher T ∗ and a greedy teacher T g that is not optimal.
Both teachers teach c0 to the learner L+
1 .

We now compare E1+ with other dimensions. The comparison of E1+ with thenumber MQ of membership queries (see Angluin [1]) is interesting because MQ
and E1+ are both lower bounded by the teaching dimension.
Fact 9. (1) For all C and c∗ ∈ C: E1+ (c∗ ) ≥ TD(c∗ ).
(2) There is no function of TD upper bounding E1+ (c).
(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. (1) This follows from Lemma 4. (2) Let Cn = {c ⊆ [1, n] |c| = 2}. Then
TD(Cn ) = 2, but E1+ (Cn ) = n − 1 because the optimal teacher gives positive
examples all the time and there are n − 1 hypotheses consistent to such an
example. (3) E1+ (c) = 1 for all c ∈ Sn , but MQ(Sn ) = n−1. (4) MQ(Dn ) = n andE1+ (D) = 2n−1 . (5) It is known (see e.g., 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 the fact. utRoughly speaking, teaching L+
1 can take arbitrarily longer than teaching in
the classical model, but is still incomparable with membership query learning.

Teaching Randomized Learners

4.2

237

Learners with ∞-Memory

A straightforward MDP for teaching c∗ to L+∞ has states S = (C ∪ {init}) ×X (c∗ )≤|X| . The number of states can be reduced because two states (h, m) and(h, m0 ) with C(m) = C(m0 ) are equivalent from a teacher’s perspective, but ingeneral the size of the resulting MDP will not be polynomial in the size of thematrix representation of C. Therefore, optimal teachers cannot be computed
efficiently by the known general MDP algorithms.
A similar criterion as Lemma 5 can be stated for the L+∞ learner, too, andused to prove optimality of algorithms. We mention, without the technical proof,that a slight modification of the algorithm in Fig. 1 is optimal for L+∞ and Mn .
+That computing E∞
is already a hard problem can be seen as follows. First,
there is always a teacher that needs at most TD(c∗ ) rounds by giving a minimal+ ∗teaching set, hence E∞(c ) ≤ TD(c∗ ). Second, it follows from Lemma 4 that
+ ∗
∗
+ ∗
E∞ (c ) ≥ TD(c )/2. This means that every algorithm computing E∞(c ) also
computes a factor 2 approximation of the teaching dimension.
As it has often been noted [19, 5, 9], the problem of computing the teaching
dimension is essentially equivalent to the SET-COVER (or HITTING-SET) problem
which is a difficult approximation problem. Raz and Safra [18] have shown that
there is no polynomial time constant-factor approximation (unless P = N P).
Moreover, Feige [7] proved that SET-COVER cannot be approximated better than
within a logarithmic factor (unless N P ⊆ DTime(nlog log n )).
+Corollary 10. Unless N P ⊆ DTime(nlog log n ), computing E∞
is N P-hard andcannot be approximated with a factor of (1 − ) log |C| for any  > 0.

Fact 11. Let C be a concept class and c∗ ∈ C a target. Then there is a successful
teacher for the learner L+∞ halting after at most |X| rounds that is also optimal.
Proof. Every given example is memorized forever. Hence, an optimal teacher
never presents the same example twice and after at most |X| rounds there is
only one consistent hypothesis for the learner to choose from, namely c∗ .
tu
As there is always a successful teacher giving at most TD(c∗ ) examples, one
could conjecture that there is also an optimal teacher teaching finitely within at
most TD(c∗ ) rounds. But this not the case.
Fact 12. There is a concept class C and a concept c∗ ∈ C such that all teachers∗
teaching c∗ to the learner L+∞ finitely within TD(c ) rounds are suboptimal.
Proof. (Sketch) The concept class C and the concept c∗ are defined by Figure 3.
The teaching dimension of c∗ is three and the only smallest teaching set S :={(x1 , 1), (x2 , 1), (x3 , 1)}. The only teachers finite after 3 rounds are those always
giving an inconsistent example from S. Their expected teaching time is 2.6.
A teacher starting with (x4 , 1) and then giving examples from S is not finite
after three rounds, but has an expected teaching time of only 2.5 rounds.
t
u

238

F.J. Balbach and T. Zeugmann
x1 x2 x3 x4 x5 x6
init: – – – – – –c∗ : 1 1 1 1 1 1
1 1 0 1 1 1
1 0 1 1 1 1
0 1 1 1 1 1
1 1 0 0 1 0
1 0 1 0 1 0
0 1 1 0 1 0
1 1 0 0 0 1
1 0 1 0 0 1
0 1 1 0 0 1
1 1 0 0 0 0
1 0 1 0 0 0
0 1 1 0 0 0∗
Fig. 3. Concept class and target whose optimal L+∞ -teacher is not finite after TD(c ) =3 rounds. The optimal teacher starts with x4 and is finite after 4 rounds (see Fact 12).

5

Learners without Feedback

The problem of finding the optimal cost in an MDP whose states cannot be observed is much harder than in an observable MDP. In general, it is not even decidable whether the optimal cost is below a given threshold (see Madani, Hanks,
and Condon [14]). We know of no obvious algorithm to decide this problem inthe special case of teaching 1-memory learners.
Teaching ∞-memory learners can be seen as a finite horizon unobservable
MDP since any reasonable teacher presents a different example in every roundand thus can stop after at most |X| rounds. The decision problem for finite
horizon unobservable MDPs is N P-complete (Mundhenk et. al. [16]) and theinapproximability result of Corollary 10 holds for the feedbackless case as well,− ∗(c ) ≤ TD(c∗ ).
since TD(c∗ )/2 ≤ E∞

6

Teaching Positive Examples Only

The learnability of classes from positive data is a typical question in learningtheory. Similar restrictions on the data can be posed in teaching models, too.
In contrast to teaching with positive and negative data, where all classes areteachable, we now get classes that are not teachable. More precisely we have thefollowing characterization for teachability with positive data.
Theorem 13. Let C be a concept class and c∗ ∈ C a target concept. Then for
all learners Lσµ with µ ∈ [1, ∞], σ ∈ {+, −}: The concept c∗ is teachable frompositive data iff 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 ∞memory can be taught by presenting S + , since they remember all examples andTeaching Randomized Learners

239

are always 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.
Thus, with positive probability the number of examples is infinite, leading to an
infinite expected number of examples.
tu
Theorem 13 also characterizes teaching with positive data in the classicalteaching dimension model. If there is no c ⊃ c∗ , the set of all positive examplesof c∗ is a teaching set, 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 inconsistentteachers discussed in the next section.

7

Inconsistent Teachers

Until now, teachers were required to always tell the truth, i.e., to provide examples z ∈ X (c∗ ). In reality it might sometimes be worthwhile to teach somethingwhich 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 inconsistent ones. One can see this as an analog to inconsistent learners inlearning theory, as these learners also contradict something they actually know.
Clearly, teaching learners with ∞-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, the model can be adapted to this, e.g., by stipulating that a memorized
example (x, v) can be “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.
We first look at inconsistent teachers in combination with teaching frompositive 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 4 shows that,when only positive data are allowed, inconsistent teachers can teach concepts toL+
1 that consistent teachers cannot. First, the teacher gives (x1 , 1). If the learnerguesses c∗ , we are done. Otherwise, the learner must return c1 and the teacher
gives (x3 , 1) which is inconsistent with c∗ . Now, the learner has to guess c2 . Next,(x1 , 1) is again given and the process is iterated until the learner returns c∗ .
However, consistent teachers with both positive and negative data are more
powerful as we show next.
Fact 14. There is a class that cannot be taught to L+
1 by an inconsistent teacher
from positive data.

240

F.J. Balbach and T. Zeugmann
C1 :x1 x2 x3
init: – – –c∗ : 1 0 0
c1 : 1 1 0
c2 : 0 0 1

T
x1
–
x3
x1

C2 :

x1 x2 x3
init: – – –c∗ : 0 1 0
c1 : 1 1 0
c2 : 0 1 1

Fig. 4. The class C1 can be taught to L+
1 by the inconsistent positive-data teacher T ,but cannot be taught by a consistent positive-data teacher (Theorem 13). The class C2
cannot be taught by an inconsistent positive-data teacher (Fact 14).

Proof. We show that C2 from Figure 4 is such a class. Let T be a teacher forL+
1 mapping C2 ∪ {init} to {x1 , x2 , x3 } × {1}. No matter what T (init) is, theprobability that the learner switches to c1 or c2 is positive. If the learner guessesc1 (the c2 case is analog), 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 . So, the probability that L+t
1 never reaches c is positive. uClasses 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 example inconsistent with c but consistent with d.
Theorem 15. Let C be a concept class and G(C) = (V, A) its associated graph.
∗
For the learner L+
1 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 aneighbor of 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 thedefinition of G(C) and the reachability assumption.
Denote by n = |C| and by p = 1/n the minimum probability for reaching c0
when the learner receives T (c) in state c. If the learner is in any state c, there
is a probability of at least pn > 0 for reaching c∗ within the next n rounds bytraversing the shortest path from c to c∗ . Therefore, no matter in which state
the learner is, the expected number of n-round blocks until reaching the target
is at most 1/pn . Thus, the expected time to reach the target from any state, inparticular from init, is at most n/pn < ∞.
For the only-if part, let T be a teacher for c∗ ∈ C. Suppose there is a state cwith no path to c∗ . Then c ⊃ c∗ (otherwise c∗ \ c 6= ∅ and (c, c∗ ) ∈ A). At sometime, 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 expectedteaching time altogether. A contradiction to c∗ being teachable by T .
tuTeaching Randomized Learners

241

The criterion in Theorem 15 requires to check the reachability of a certain
node from all 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 withfeedback from positive data that consistent teachers cannot teach to L+
1 (cf.
Figure 4), 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 13 and Theorem 16 below).
∗
Theorem 16. For the learner L−
1 a concept c ∈ C is teachable by an inconsistent teacher from positive data iff there is no c ∈ C with c ⊃ c∗ .

Proof. The if-direction follows from Theorem 13.
For the only-if part suppose that c∗ is teachable by a teacher T and there isa c with c ⊃ c∗ . Let (zi )i∈N be the series of examples taught.
Claim: T teaches inconsistent examples only finitely often.
Proof : Suppose T teaches an example (x, 1) ∈/ X (c∗ ) infinitely often. Without
loss of generality we assume that there is a concept containing x (otherwise(x, 1) would be useless and a teacher T 0 never giving this example would be
successful, too). Whenever (x, 1) is taught, the learner will not be in state c∗afterwards, i.e., there are infinitely many t such that Pr[ht 6= c∗ ] = 1. It follows
that Pr[Gt ] = Pr[ht−1 6= c∗ ∧ ∀t0 ≥ t : ht = c∗ ] = 0 for all t ≥ 1. This means thatthe success probability is zero, a contradiction. This proves the claim. ut Claim
From the claim it follows that there is a t0 such that zt ∈ X (c∗ ) for all t ≥ t0 .
We now show that Pr[ht0 = c∗ ] < 1, i.e., it is uncertain whether the learneris in the target state. Suppose that Pr[ht0 = c∗ ] = 1. Let t ≤ t0 be minimal
with Pr[ht = c∗ ] = 1. If zt ∈ X (c∗ ) then zt is consistent with c, too, and thusPr[ht = c∗ ] ≤ 1/2. If zt ∈/ X (c∗ ), then Pr[ht = c∗ ] = 0, a contradiction.
Hence, the probability that the learner is not in the target state at time t0
is positive. After t0 only consistent examples are given. So there is a probabilityof at least 1/|C| that the learner switches to c on the next example. As c ⊃ c∗the target cannot be reached by positive examples any more. Thus, the successprobability is less than one, a contradiction. This proves the only-if part.
tu

8

Mind Change Forcing Teachers

In this section we deal again with consistent teachers. When teaching L+
1 it isuseless to provide an example consistent with the current hypothesis, since it does
not change the state of L+
1 . In this situation the optimal teacher is necessarily“mind change forcing.” But if we look at L+µ (µ > 1), it is not obvious that an
optimal teacher has to force the learner to change its mind in every round until
successful learning. While we could prove that for L+∞ an optimal teacher canbe made “mind change forcing,” it remains open whether a similar statement istrue for L+µ with 1 < µ < ∞.
Theorem 17. Let C be a class and c∗ be a target. Then there is an optimalteacher for L+∞ never giving an example consistent with the current hypothesis.

242

F.J. Balbach and T. Zeugmann

Proof. Let T be a successful teacher that teaches a consistent example z1 in astate (h, m) that is reached with positive probability and is not a target state.
Then z1 ∈ X (h) ∩ X (c∗ ) and h 6= c∗ . We show that T is not optimal for thisstate and hence for the initial state. We do this by showing that there is anotherteacher T 0 giving an inconsistent example and being not worse than T .
After receiving z1 , the learner reaches (h, m ∪ {z1 }) due to the conservativeness property. Then T teaches z1 = T (h, m ∪ {z1 }) leading to (h, m ∪ {z1 , z2 })and so on. Since h 6= c∗ , T must eventually teach an example zk ∈/ C(h).
After teaching z1 , . . . , zk the learner has either reached the target or assumes
one of the hypotheses in C(m ∪ {z1 , . . . , zk }) \ {c∗ } with equal probability p :=1/|C(m ∪ {z1 , . . . , zk })| − 1. For the expected teaching time we haveX
H(h, m) = k +p · H(h0 , m ∪ {z1 , . . . , zk })h0 ∈C(m∪{z1 ,...,zk })The teacher T 0 teaches the same examples z1 , . . . , zk , but in different order,
namely zk , z1 , . . . , zk−1 , that is with the inconsistent example first. Formally:
T 0 (h, m) = zk and furthermore for all i = 0, . . . , k − 1 and for all h0 ∈ C(m ∪{zk , z1 , . . . , zi }): T 0 (h0 , m ∪ {zk , z1 , . . . , zi }) = zi+1 .
Beginning in (h, m) and being taught by T 0 for k rounds, the learner has either arrived at the target or assumes one of the hypotheses in C(m∪{z1 , . . . , zk })\{c∗ }. Furthermore all these hypotheses are equally likely. This follows inductively from the fact that whenever a hypothesis change is triggered, say after
zk , z1 . . . , zi , all hypotheses from C(m ∪ {zk , z1 , . . . , zi }), and in particular all
hypotheses from the subset C(m ∪ {z1 , . . . , zk }), are equally likely; no hypothesis is preferred. The probability p0 for each of these hypotheses is at most
1/(|C(m ∪ {z1 , . . . , zk })| − 1) = p. The expected teaching time under T 0 isX

H 0 (h, m) ≤ k +p0 · H 0 (h0 , m ∪ {z1 , . . . , zk })h0 ∈C(m∪{z1 ,...,zk })=k+X

p0 · H(h0 , m ∪ {z1 , . . . , zk }) ≤ H(h, m)

h0 ∈C(m∪{z1 ,...,zk })where the equality in the second line holds because T and T 0 are identical in thestates (h0 , m ∪ {z1 , . . . , zk }).
We have shown that T 0 is not worse than T and gives an inconsistent examplein (h, m). By repeating the above argument the states in which T gives consistentexamples can be moved to the “end” where they finally disappear.
tu

9

Conclusions and Future Work

We have presented a model for teaching randomized learners based on the classical teaching dimension model. In our model, teachability depends, in a qualitatively plausible way, on the learner’s memory size, on its ability to give feedback,and on the order of the examples taught. The model also allows to study learning theory like questions such as teaching from positive data only or teachingTeaching Randomized Learners

243

by inconsistent teachers. Randomization also gives more flexibility in defining
the learner’s behavior by using certain a priori probability distributions over the
hypotheses. So, one can define and study learners preferring simple hypotheses.

References[1] D. Angluin. Queries and concept learning. Machine Learning, 2(4):319–342, 1988.
[2] D. Angluin. Queries revisited. Theoret. Comput. Sci., 313(2):175–194, 2004.
[3] D. Angluin and M. Kriķis. Teachers, learners and black boxes. In Proc. of the10th Annual Conference on Computational Learning Theory, pages 285–297. ACM
Press, New York, NY, 1997.
[4] D. Angluin and M. Kriķis. Learning from different teachers. Machine Learning,
51(2):137–163, 2003.
[5] M. Anthony, G. Brightwell, D. Cohen, and J. Shawe-Taylor. On exact specification by examples. In Proc. of the 5th Annual ACM Workshop on Computational
Learning Theory, pages 311–318. ACM Press, New York, NY, 1992.
[6] D. P. Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific.
[7] U. Feige. A threshold of ln n for approximating set cover. J. of the ACM,
45(4):634–652, 1998.
[8] R. Freivalds, E. B. Kinber, and R. Wiehagen. On the power of inductive inference
from good examples. Theoret. Comput. Sci., 110(1):131–144, 1993.
[9] S. A. Goldman and M. J. Kearns. On the complexity of teaching. J. Comput.
Syst. Sci., 50(1):20–31, 1995.
[10] S. A. Goldman and H. D. Mathias. Teaching a smarter learner. J. Comput. Syst.
Sci., 52(2):255–267, 1996.
[11] S. A. Goldman, R. L. Rivest, and R. E. Schapire. Learning binary relations andtotal orders. SIAM J. on Computing, 22(5):1006–1034, Oct. 1993.
[12] J. Jackson and A. Tomkins. A computational model of teaching. In Proc. of the
5th Annual ACM Workshop on Computational Learning Theory pages 319–326.
ACM Press, New York, NY, 1992.
[13] S. Jain, S. Lange, and J. Nessel. Learning of r.e. languages from good examples.
In Algorithmic Learning Theory, 8th International Workshop, ALT ’97, Sendai,
Japan, October 1997, Proceedings, Lecture Notes in Artificial Intelligence Vol.
1316, pages 32–47, Springer, 1997.
[14] O. Madani, S. Hanks, and A. Condon. On the undecidability of probabilisticplanning and infinite-horizon partially observable Markov decision problems. In
Proc. of the 16th National Conference on Artificial Intelligence and 11th Conference on Innovative Applications of Artificial Intelligence, pages 541–548, AAAI
Press/The MIT Press, 1999.
[15] H. D. Mathias. A model of interactive teaching. J. Comput. Syst. Sci., 54(3):487–
501, 1997.
[16] M. Mundhenk, J. Goldsmith, C. Lusena, and E. Allender. Complexity of finitehorizon Markov decision process problems. J. of the ACM, 47(4):681–720, 2000.
[17] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 1994.
[18] R. Raz and S. Safra. A sub-constant error-probability low-degree test, and a subconstant error-probability PCP characterization of NP. In Proc. of the 29th ACM
Symposium on Theory of Computing, pages 475–484, 1997.
[19] A. Shinohara and S. Miyano. Teachability in computational learning. New Generation Computing, 8(4):337–348, 1991.