TCS -TR-A-06-13

TCS Technical Report

On the Teachability of Randomized Learners

byFrank J. Balbach and Thomas Zeugmann

Division of Computer Science
Report Series A
April 26, 2006

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

thomas@ist.hokudai.ac.jp

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

On the Teachability of Randomized Learners
Frank J. BalbachThomas Zeugmann

Institut für Theoretische Informatik

Division of Computer Science

Universität zu Lübeck

Hokkaido University

Ratzeburger Allee 160

N-14, W-9

23538 Lübeck, Germany

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

thomas@ist.hokudai.ac.jp

Abstract
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 parameters such as the learner’s memory size,
its ability to provide or to not provide feedback, and the influence of the order inwhich examples are presented. Furthermore, within the new model it is possible
to investigate new aspects of teaching like teaching from positive data only orteaching with inconsistent teachers.
Furthermore, we provide characterization theorems for teachability frompositive data for both ordinary teachers and inconsistent teachers with andwithout 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 in different forms, by Shinohara and Miyano [22], Goldman et al. [13], Goldman and
Kearns [11] as well as Anthony et al. [6]. Here, a teacher has to give enough examples to uniquely identify the target concept among all concepts in a given class.
Thus, the students are all deterministic consistent learning algorithms.
By varying the set of admissible learners, the influence of different properties ofthe learners on the teaching process can be studied. For example, learners withlimited memory should be harder to teach, whereas learners that show their current
hypothesis to the teacher should ease the teaching process.
12Frank J. Balbach and Thomas Zeugmann

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. Soteaching 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 theinfluence of memory limitations or learner’s feedback. A common remedy for this isto perform an average case analysis instead (cf., e.g., [5, 7, 16]). 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 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. For ensuring that the learner maintains
this correct hypothesis, we additionally require the learner to be conservative, i.e.,
it can change its hypotheses only on examples that are inconsistent 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 roundthere is a chance to reach the target, the target will eventually be reached even if,
for instance, the randomized learner can only memorize few examples. Moreover, theability of 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 showthese intuitions to be valid.
Randomized learners show another phenomenon, too: The complexity of the teaching process now does not only depend on the examples, but also on the order 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 use of someresults 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 we study
variations of our model: teaching from positive data, inconsistent teachers and anotherrestriction on teachers. Theorems characterizing teachability within these model are
shown.
Note that there are also other approaches to teaching. They differ from the one
discussed here, since the learner is not given, but constructed to fit to the teacher.
One such model is learning from good examples (cf. Freivalds et al. [10] and JainOn the Teachability of Randomized Learners

3

et al. [15]). Jackson and Tomkins [14] as well as Goldman and Mathias [12] andMathias [18] defined models of teacher/learner pairs. In their models, a kind ofadversary disturbing the teaching process is necessary to avoid collusion between theteacher and the learner. Angluin and Kriķis’ [3, 4] model prevents collusion by giving
incompatible hypothesis spaces to teacher and learner.

2. Preliminaries
2.1. Notations
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 for a concept
c by X (c) = {(x, v) v = 1 ⇐⇒ x ∈ c} ⊂ X . An example (x, v) is called 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, by S m
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 ` < µ andhx2 , . . . , x` , yi if ` = µ. We regard ◦∞ as the usual list concatenation. For a list ~x ofexamples, 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 theempty concept from Mn and can thus identify each monomial with a string from{0, 1, ∗}n and vice versa. Dn is the set of all 2n concepts over [1, n]. The singletonclasses 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, thehypothesis is chosen at random from all consistent ones.

4Frank J. Balbach and Thomas Zeugmann

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, thememory works like a queue. Setting µ = ∞ models unlimited memory.
The goal of teaching is making the learner to hypothesize the target and to maintainit. 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 learnerwould oscillate between them rather than maintaining a single one. To avoid this,conservativeness is required, i.e., the learner can change its hypothesis only whentaught 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 result of
the calculation during a round (i.e., new memory content and hypothesis), the public
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 computedby the learner. If the learner does not give feedback, the teacher can observe nothing.
The following algorithm describes the behavior of the µ-memory learner with/with−out 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 initialstate of the learner, we stipulate a special initial hypothesis, called init. We assume
every example inconsistent with init. Thus, init is left after the first example andcannot be reached again. Moreover, the initial memory is empty.
The Teacher. A teacher is an algorithm taking initially a given target concept c∗ as
input. Then, in each round, it receives the public output of the learner (if any) andoutputs 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 for the
hypothesis at round i. The event “teaching success in round t,” denoted by Gt , isdefined as
ht−1 6= c∗ ∧ ∀t0 ≥ t : ht0 = c∗ .

On the Teachability of Randomized Learners

5SThe success probability of T is Pr t≥1 Gt . A teaching process is successful iff thesuccess probability equals 1. A successful teaching process is called finite iff there is a t0
Ssuch that Pr 1≤t≤t0 Gt = 1, otherwise it is called infinite. For a successful teachingP
process we define the expected teaching time as E[T, Lσµ , c∗ , C] := t≥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∗
isEµσ (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.3. Markov Decision Processes
For an extensive treatment of this topic see Puterman [20] and Bertsekas [8]. A
Markov Decision Process (MDP) is a probabilistic system whose state transitions canbe influenced during the process by actions which incur costs. Formally, an MDP
consists of a finite set S of states, an initial state s0 ∈ S , a finite set A of actions, afunction 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 such that 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 isonly 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 canthus 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 with the current
hypothesis in each round. For all such examples, there are 2n−µ hypotheses consistent with the µ examples in the learner’s memory and learner chooses one of them.

6Frank J. Balbach and Thomas Zeugmann

Therefore the probability of choosing the target concept is 2−(n−µ) . Thus, consideringthat 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 the teacher
can merely guess examples hoping that they are inconsistent with the current hypothesis. Roughly speaking, when teaching Dn , the teacher needs two guesses on average
to find such an example. Hence, the expected teaching time Eµ− is about two times
Eµ+ . Thus feedback doubles the teaching speed for Dn .
Fact 1. For all C and µ ∈ [1, ∞] all c∗ ∈ C and σ ∈ {+, −}:σσ(1) Eµ+ (c∗ ) ≤ Eµ− (c∗ ),(2) E∞(c∗ ) ≤ Eµ+1(c∗ ) ≤ Eµσ (c∗ ).
Proper inequality holds for the concepts in Dn .
Next, we relate the deterministic model (in terms of the teaching dimension) to therandomized model (in terms of the expected teaching time). Essentially, the teaching
dimension can be used to lower bound the teaching time.
Lemma 1. 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.
(Claim)Using the claim we upper bound the probabilities for reaching the target in roundi = 0, . . . , µ − 2. After round i the learner knows i + 1 examples and therefore canchoose between at least k − i consistent hypotheses (see Claim). Thus, the probability
1
for reaching c∗ in round i is at most pi := 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 describedabove. The expectation of such a process is
µ−2
X
i=0

i−1
∞
i−1
Y
X
Y
(i + 1) · pi · (1 − pj ) +(i + 1) · pi · (1 − pj ) .
j=0

i=µ−1

j=0

(1)

7

On the Teachability of Randomized Learners

Q
k−µ+1
We start with the second sum in (1). Since µ−2
the productj=0 (1 − pj ) =
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 + 1) · pµ−1 · (1 − pµ−1 )i.

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· (µ − 1 + k − µ + 1) = k − µ + 1 .
sum in (1) we therefore get k−µ+1kCalculating the first sum in (1) yields
µ−2
X
i=0

1
(i + 1) · k−i
·

i−1
Y

k−j−1
=
k−j

j=0

µ−2
X

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

i=0

µ(µ − 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∗ ) rounds.
The lower bound is therefore the same as for µ = TD(c∗ ).

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 we can derive thefollowing criterion by using the results from Subsection 2.3.
Lemma 2. 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 )
z ∈X
/ (h)

h ∈C(z)8Frank J. Balbach and Thomas Zeugmann

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∗ ).


γi
∗
1 if h ⊃ c output (χ1 . . . χn , 0) with χi = 1 − γi0if ηi = γi 6= ∗,if i = min{j ηj = ∗ =6 γj },
otherwise;

2 else output (x, 1) with arbitrary x ∈ c∗ .
Figure 1: Optimal teacher for monomials and the learner L+
1.

This criterion can be used to prove optimality for teaching algorithms.
To denote subsets of the monomials we use notations like 1k {0, 1}n−k for the set{1k y y ∈ {0, 1}n−k }.
Fact 2. The teacher in Fig. 1 is an optimal teacher for Mn and the learner L+
1.
Proof. Let without loss of generality c = 1k ∗n−k be the target concept (k ≥ 1).
The definition of T is based on a partition of all hypotheses into two groups. The
first group contains all h ⊃ c, the second group all h 6⊃ c and init. Within a group,
all hypotheses are assigned the example in the same way and have the same expectedteaching time. T (init) := (1n , 1); for h ⊃ c, T (h) := (01n−1 , 0); and for h 6⊃ c, let
T (h) be an arbitrary positive example inconsistent with h. For the expected times,
let(3n − 2n )(2n + 2k ) − 2n+k−1E⊃ :=3n − 2n + 2k−1
and
(3n − 2n )(2n + 2k ) − 2n+k−1 + 2n+1 − 3n.
E6⊃ :=
3n − 2n + 2k−1
Now set E(h) := E⊃ for all h ⊃ c and E(h) := E6⊃ for all h 6⊃ c including init.
We have to prove two points: (1) E describes the teaching times for teacher T ;(2) the criterion of Lemma 2 holds. To this end, we shall introduce the notion ⊃hypothesis and 6⊃-hypothesis for h ⊃ c and h 6⊃ c respectively.
Claim A: Let (x, 0) be consistent with c, i.e., x ∈/ c. Then (1) there are 3n − 2nhypotheses consistent with (x, 0); (2) x is of the form y{0, 1}n−k with y containing` ≥ 1 zeros, and (3) the number of ⊃-hypotheses consistent with (x, 0) is exactly
2k − 2k−` − 1.
Proof. Without loss of generality let x = 0` 1k−` ∗n−k . (1) There are 2n concepts
containing x, hence there are 3n − 2n concepts consistent with (x, 0).
(2) If y would contain no zeros, it would be of the form 1k {0, 1}n−k and therefore
in c.

9

On the Teachability of Randomized Learners(3) A concept d contains c iff d is of the form {1, ∗}k ∗n−k . In addition d is consistent
with (x, 0) (x ∈/ d) iff d is of the form z{1, ∗}k−` ∗n−k with z ∈ {1, ∗}` containing atleast one “1”. There are exactly (2` − 1) · 2k−` = 2k − 2k−` concepts satisfying thelatter condition. Since c does not count as ⊃-hypothesis, the sought number is one(Claim A)
less, as claimed.
Claim B: For every positive example there are 2n consistent hypotheses of which
2k − 1 are ⊃-hypotheses.
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 B)
This proves Claim B.
We now prove point (1). We have to show that for each h the linear equation
relating the teaching times as defined by E actually hold. First, let h ⊃ c. Then T
gives (01n−1 , 0). Considering Claim A, h’s expected teaching time is2k−1 − 1
3n − 2n − 2k−1
E(h) = 1 + n· E⊃ +· E6⊃ .
3 − 2n3n − 2n(2)After plugging in E⊃ and E6⊃ , a tedious calculation shows that indeed E(h) = E⊃ .
Second, let h 6⊃ c. Then T gives a positive example and according to Claim B, h’sequation is
2k − 12n − 2k·E+· E6⊃ .
(3)
E(h) = 1 +⊃2n2nAgain, a calculation shows that E(h) = E6⊃ actually holds. We have therefore provedthat E specifies the expected times for all hypotheses.
P
1
0
To prove point (2) we have to show that the value 1 + |C(z)|h0 ∈C(z) E(h ) is not
lower than E(h) for any z ∈ X (c). Let h ⊃ c. From Claim A (3) we know that theexample T (h) minimizes the number of consistent ⊃-hypotheses among all examplesz ∈ X (c) (which are all negative because of h ⊃ c). Changing T (h) can thus only
increase the probability for a transition to a ⊃-hypothesis (or leave it unchanged).
But since E⊃ > E6⊃ such a probability increase would be no improvement.
Let h 6⊃ c. Changing T (h) to a different positive example will not change theprobabilities (Claim B). Assume that T (h) is changed to a negative example (x, 0).
Then according to Claim A(1–3) we are lead to the equation
E(h) = 1 +2k − 2k−` − 1
3n − 2n − 2k + 2k−`·E+
· E6⊃ .
⊃
3n − 2n3n − 2n

The right hand side becomes minimal for ` = 1, since this results in the coefficient ofE⊃ being minimal and also E⊃ > E6⊃ . But this minimal right hand side is identicalto the ride hand side of equation (2) which has been shown to equal E⊃ . The originalvalue E(h) = E6⊃ is therefore still better.

10Frank J. Balbach and Thomas Zeugmann

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 consistent hypotheses for thelearner to choose from, thus maximizing the probability for reaching c∗ in the next
step.
Such a greedy strategy seems sensible and is provably optimal in the case of Mn .
However, there are classes where no greedy teacher is optimal.
Definition 3. 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 3. 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.
h
init
c0
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10

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

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

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

x4
–
1
0
1
0
1
1
0
1
1
0
1

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

H ∗ (h)T g (h) H g (h)176/35=5.0285. . . x1 2536/504=5.0317. . .
0–0176/35x1 2536/504
176/35x1 2536/504
176/35x1 2536/504
176/35x1 2536/504
176/35x1 2536/504
176/35x1 2536/504
176/35x1 2536/504
186/35x2 2680/504
189/35x4 2725/504
189/35x5 2723/504

Figure 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 andE1+ are both lower bounded by the teaching dimension.
Fact 4.
(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) .

On the Teachability of Randomized Learners

11

Proof. (1) This follows from Lemma 1. (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 and E1+ (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.
Roughly speaking, teaching L+
1 can take arbitrarily longer than teaching in theclassical model, but is still incomparable with membership query learning.
4.2. Learners with ∞-Memory
A straightforward MDP for teaching c∗ to L+∞ has states S = (C ∪ {init}) ×∗ ≤|X|X (c ). 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 in general the sizeof the resulting MDP will not be polynomial in the size of the matrix representation of
C. Therefore, optimal teachers cannot be computed efficiently by the known general
MDP algorithms.
A similar criterion as Lemma 2 can be stated for the L+∞ learner, too, and used
to prove optimality of algorithms. We mention, without the technical proof, that aslight modification of the algorithm in Fig. 1 is optimal for L+∞ and Mn .
+is already a hard problem can be seen as follows. First, thereThat computing E∞
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 1 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 [22, 6, 11], 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 [21] have shown that there is no
polynomial time constant-factor approximation (unless P = N P). Moreover, Feige [9]proved that SET-COVER cannot be approximated better than within a logarithmic
factor (unless N P ⊆ DTime(nlog log n )).
+is N P-hard andCorollary 5. Unless N P ⊆ DTime(nlog log n ), computing E∞
cannot be approximated with a factor of (1 − ) log |C| for any  > 0.

Fact 6. 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 neverpresents the same example twice and after at most |X| rounds there is only one
consistent hypothesis for the learner to choose from, namely c∗ .

12Frank J. Balbach and Thomas Zeugmann

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 7. 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. The concept class C and the concept c∗ are defined by Figure 3. The teaching
dimension of c∗ is three and the (unique) smallest teaching set is
S := {(x1 , 1), (x2 , 1), (x3 , 1)} .

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

x4
–
1
1
1
1
0
0
0
0
0
0
0
0
0

x5
–
1
1
1
1
1
1
1
0
0
0
0
0
0

x6
–
1
1
1
1
0
0
0
1
1
1
0
0
0

Figure 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 7).
We first prove that every teacher that is finite within three rounds needs expected
2.6 rounds.
Let T be such a teacher. In order to be finite after three rounds, T must teach S
and hence start with x1 , x2 , or x3 . For symmetry reasons we assume without loss ofgenerality that T starts with x1 . The probability for the learner to reach c∗ directlyis 1/9. With probability 1/2 the learner reaches a hypothesis containing x2 , but not
x3 ; and with equal probability a hypothesis containing x3 , but not x2 . As both cases
are symmetric, we assume the first one without loss of generality. The teacher T thengoes on teaching (x3 , 1) which is the only inconsistent example in S.
The probability of reaching c∗ is 1/5, since there are five hypotheses consistent with
(x1 , 1), (x3 , 1). With probability 4/5 the learner reaches a hypothesis not containing
x2 . Finally the teacher T gives (x2 , 1) which leads to c∗ with certainty. Altogether
the expected number of rounds is
8 1
8 4
1
· 1 + · · 2 + · · 3 = 2.6 .
9
9 5
9 5

On the Teachability of Randomized Learners

13

On the other hand, let T 0 be the teacher starting with (x4 , 1) and then teachingin each round an inconsistent example from S. In the first round, the probability
for an immediate transition to c∗ is 1/4. In the second, third, and fourth round theprobabilities are 1/3, 1/2, and 1, respectively, since each example rules out exactly
one hypothesis. Thus the expected number of rounds for T 0 is
3 1
3 2 1
3 2 1
1
· 1 + · · 2 + · · · 3 + · · · 4 = 2.5 .
4
4 3
4 3 2
4 3 2
Therefore T cannot be optimal.

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 [17]). We know of no obvious algorithm to decide this problem in the special caseof 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 round and thus canstop after at most |X| rounds. The decision problem for finite horizon unobservable
MDPs is N P-complete (Mundhenk et al. [19]) and the inapproximability result of− ∗Corollary 5 holds for the feedbackless case as well, since TD(c∗ )/2 ≤ E∞(c ) ≤∗
TD(c ).

6. Teaching Positive Examples Only
The learnability of classes from positive data is a typical question in learning theory.
Similar restrictions on the data can be posed in teaching models, too. In contrast toteaching with positive and negative data, where all classes are teachable, we now getclasses that are not teachable. More precisely we have the following characterization
for teachability with positive data.
Theorem 8. Let C be a concept class and c∗ ∈ C a target concept. Then for all
learners Lσµ with µ ∈ [1, ∞], σ ∈ {+, −}: The concept c∗ is teachable from positive
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 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

14Frank J. Balbach and Thomas Zeugmannthat 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 numberof examples.
Theorem 8 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 ateaching 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 inconsistent teachers
discussed in the next section.

7. 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}, eveninconsistent ones. One can see this as an analog to inconsistent learners in learningtheory, 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, themodel 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 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 4 shows that, when
only positive data are allowed, inconsistent teachers can teach concepts to L+
1 thatconsistent teachers cannot. First, the teacher gives (x1 , 1). If the learner guesses c∗ ,we are done. Otherwise, the learner must return c1 and the teacher gives (x3 , 1) whichis 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 9. There is a class that cannot be taught to L+
1 by an inconsistent teacher
from positive data.

15

On the Teachability of Randomized Learners

C1 :
init:
c∗ :
c1 :
c2 :

x1
–
1
1
0

x2
–
0
1
0

x3
–
0
0
1

T
x1
–
x3
x1

C2 :
init:
c∗ :
c1 :
c2 :

x1
–
0
1
0

x2
–
1
1
1

x3
–
0
0
1

Figure 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 8). The class
C2 cannot be taught by an inconsistent positive-data teacher (Fact 9).
Proof. We show that C2 from Figure 4 is such a class. Let T be a teacher for L+
1
mapping C2 ∪ {init} to {x1 , x2 , x3 } × {1}. No matter what T (init) is, the probability
that the learner switches to c1 or c2 is positive. If the learner guesses c1 (the c2case 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+
1 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
example inconsistent with c but consistent with d.
Theorem 10. 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 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) andthe 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 probabilityof at least pn > 0 for reaching c∗ within the next n rounds by traversing 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, in particular 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 c withno 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

16

Frank J. Balbach and Thomas Zeugmannc is infinite and hence the expected teaching time altogether. A contradiction to c∗being teachable by T .
The criterion in Theorem 10 requires to check the reachability of a certain nodefrom 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 with feedback
from positive data that consistent teachers cannot teach to L+
1 (cf. Figure 4), thesituation changes if no feedback is available. That is, 1-memory learners without
feedback can be taught the same classes by inconsistent teachers as by consistentteachers (cf. Theorem 8 and Theorem 11 below).
∗
Theorem 11. For the learner L−
1 a concept c ∈ C is teachable by an inconsistentteacher from positive data iff there is no c ∈ C with c ⊃ c∗ .

Proof. The if-direction follows from Theorem 8.
For the only-if part suppose that c∗ is teachable by a teacher T and there is a cwith 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 that the success probability is(Claim)zero, a contradiction. This proves the 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 learner is 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 thus Pr[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 probability of atleast 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 success probability isless than one, a contradiction. This proves the only-if part.

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On the Teachability of Randomized Learners

17change forcing.” But if we look at L+µ (µ > 1), it is not obvious that an optimalteacher 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 can be made “mindchange forcing,” it remains open whether a similar statement is true for L+µ with1 < µ < ∞.
Theorem 12. Let C be a class and c∗ be a target. Then there is an optimal teacher
for L+∞ never giving an example consistent with the current hypothesis.
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. Thenz1 ∈ X (h) ∩ X (c∗ ) and h 6= c∗ . We show that T is not optimal for this state and hence
for the initial state. We do this by showing that there is another teacher T 0 giving an
inconsistent example and being not worse than T .
After receiving z1 , the learner reaches (h, m ∪ {z1 }) due to the conservativenessproperty. Then T teaches z1 = T (h, m ∪ {z1 }) leading to (h, m ∪ {z1 , z2 }) and soon. 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 hypothesesin 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 fromthe 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 subsetC(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 the states(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.

18Frank J. Balbach and Thomas Zeugmann

9. 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, 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 by inconsistentteachers. Randomization also gives more flexibility in defining the learner’s behavior
by using certain a priori probability distributions over the hypotheses. So, one candefine 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
the 10th Annual Conference on Computational Learning Theory, pages 285–297.
ACM Press, New York, NY, 1997.
[4] D. Angluin and M. Kriķis. Learning from different teachers. Machine Learning,
51(2):137–163, 2003.
[5] M. Anthony, G. Brightwell, and J. Shawe-Taylor. On specifying boolean functions
by labelled examples. Discrete Applied Mathematics, 61(1):1–25, 1995.
[6] 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.
[7] 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, volume 3559 of Lecture Notes in
Artificial Intelligence, pages 668–683. Springer, 2005.
[8] D. P. Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific.
[9] U. Feige. A threshold of ln n for approximating set cover. J. of the ACM,
45(4):634–652, 1998.
[10] 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.
[11] S. A. Goldman and M. J. Kearns. On the complexity of teaching. J. Comput.
Syst. Sci., 50(1):20–31, 1995.

On the Teachability of Randomized Learners

19[12] S. A. Goldman and H. D. Mathias. Teaching a smarter learner. J. Comput. Syst.
Sci., 52(2):255–267, 1996.
[13] 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.
[14] 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.
[15] 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.
[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, volume 1572 of Lecture
Notes in Artificial Intelligence, pages 168–182. Springer, 1999.
[17] 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.
[18] H. D. Mathias. A model of interactive teaching. J. Comput. Syst. Sci., 54(3):487–
501, 1997.
[19] 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.
[20] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 1994.
[21] R. Raz and S. Safra. A sub-constant error-probability low-degree test, and a
sub-constant error-probability PCP characterization of NP. In Proc. of the 29th
ACM Symposium on Theory of Computing, pages 475–484, 1997.
[22] A. Shinohara and S. Miyano. Teachability in computational learning. New Generation Computing, 8(4):337–348, 1991.