Recent Developments in Algorithmic Teaching
Frank J. Balbach1 and Thomas Zeugmann2
1

Neuhofen, Germany
frank-balbach@gmx.de2
Division of Computer Science
Hokkaido University, Sapporo 060-0814, Japanthomas@ist.hokudai.ac.jp

Abstract. The present paper surveys recent developments in algorithmic teaching. First, the traditional teaching dimension model is recalled.
Starting from the observation that the teaching dimension model sometimes leads to counterintuitive results, recently developed approaches arepresented. Here, main emphasis is put on the following aspects derived
from human teaching/learning behavior: the order in which examples
are presented should matter; teaching should become harder when thememory size of the learners decreases; teaching should become easier if
the learners provide feedback; and it should be possible to teach infinite
concepts and/or finite and infinite concept classes.
Recent developments in the algorithmic teaching achieving (some) of
these aspects are presented and compared.

1

Introduction

When preparing a lecture, a good teacher is carefully selecting informative examples. Additionally, a good teacher is taking into account that students do notmemorize everything previously taught. And usually we make a couple of assumptions about the learners. They should neither be ignorant, lazy, nor should
they be tricky. Thus, it is only natural to ask whether or not such human behavior is at least partially reflected in some algorithmic learning and/or teachingmodels studied so far in the literature.
Learning concepts from examples has attracted considerable attention inlearning theory and machine learning. Typically, a learner does not know muchabout the source of these examples. Usually the learner is required to learn fromall such sources, regardless of their quality. This is even true for the query learning model introduced by Angluin [1, 2], since the teacher or oracle, though answering truthfully, is assumed to behave adversarially whenever possible. Therefore, it was only natural to ask whether or not one can also model scenarios inwhich a helpful teacher is honestly interested in the learner’s success.
Perhaps the first approach was proposed by Freivalds, Kinber, and Wiehagen [15, 16]. They developed a learning model in the inductive inference paradigmof identifying recursive functions in which the learner is provided with good
examples chosen by an implicitly given teacher. Jain, Lange, and Nessel [23]2

F.J. Balbach and T. Zeugmann

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 oneof two basically different approaches.
In the first approach, the goal is to find a teacher and a learner such thata given learning task can be carried out by them. Jackson and Tomkins [22] aswell as Goldman and Mathias [18, 27] defined models of teacher/learner pairs
where teachers and learners are constructed explicitly. In all these models, somekind of adversary disturbing the teaching process is necessary to avoid collusion
between the teacher and the 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 ofcoding tricks is used and thus no collusion occurs.
Angluin and Kriķis’ [3, 4] model prevents collusion by giving incompatible
hypothesis spaces to teacher and learner. This makes simple encoding of thetarget 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 iscorrectly reflecting 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 [19] and Goldman and Kearns [17] substitute theadversarial teacher in the online learning model by a helpful one selecting good
examples. They investigate how many mistakes a consistent learner can makein the worst case. In Shinohara and Miyano’s [32] model the teacher produces aset of examples for the target concept such that it is the only consistent one in
the concept class. The size of this set is the same as the worst case number of
mistakes in the online model. This number is termed the teaching dimension of
the target. Because of this similarity we shall from now on refer to both models
as the teaching dimension model (abbr. TD model).
One difficulty of teaching in the TD model results from the fact that theteacher is not knowing anything about the learners besides them being consistent. In reality a teacher can benefit a lot from knowing the learners’ behavior
or their current hypotheses. It is therefore natural to ask how teaching can be
improved if the teacher may observe the learners’ hypotheses after each example.
We refer to this scenario as to teaching with feedback.
After translating this question into the TD model, one sees that there is no
gain in sample size at all. The current hypothesis of a consistent learner reveals
nothing about its following hypothesis. Even if the teacher knew the hypothesis
and provided a special example in response, he can only be sure that the learner’s
next hypothesis will be consistent. But this was already known to the teacher.
So, in the TD model, feedback is 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

Recent Developments in Algorithmic Teaching3

does not matter, and that teaching infinite concepts or infinite concept classes isseverely limited. Another drawback is the rather counterintuitive dependence on
the memory size of the learner. If the learner’s memory size is large enough tostore all examples provided by the teacher, then successful teaching is possible.
Otherwise, it immediately becomes impossible. Another problem is that there
are concept classes which are intuitively easy to teach that have a large teaching
dimension.
Therefore, our goal has been to devise teaching models that remedy the above
mentioned flaws. In particular, our aim has been to develop teaching models suchthat the following aspects do matter.
(1) The order in which the teacher presents the information should have an
influence on the performance of the teacher.
(2) Teaching should get harder when the memory size of the learners decreases,
but it should 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.
(5) The teaching model should work for both finite and infinite concepts and/or
finite and infinite concept classes.
We studied and developed several models of algorithmic teaching to overcome
these flaws to a different extent (cf. [7, 8, 9, 10, 11]). Within the present paper,
we shortly summarize our and the related results obtained.
The paper is organized as follows. Section 2 shortly recalls the TD modeland fundamental definitions needed subsequently. Then we discuss more recent
approaches. In Section 3 we summarize results concerning teaching learners thathave to obey restrictions on possible mind changes. Next, we turn our attention
to a randomized model of teaching (see Section 4). Finally, we shortly touchteaching dimensions for complexity based learners and for cooperative learning.

2

The Teaching Dimension Model

We start by introducing the necessary notions and definitions. Let N = {0, 1, . . .}denote the set of all natural numbers. For any set S we write |S| to denote its
cardinality. Let X be any (finite) set of instances also called instance space. A
concept c is a subset of X and a concept class C is a set of concepts over X.
It is convenient to identify every concept c with its characteristic function, i.e.,
for all x ∈ X we have c(x) = 1 if x ∈ c and c(x) = 0 otherwise. We consider
mainly three instance spaces: {0, 1}n for Boolean functions, Σ ∗ for languages
over a finite and non-empty alphabet Σ, and Xn = {x1 , . . . , xn } for having any
fixed instance space of cardinality n.
By X = X × {0, 1} we denote the set of examples over X. An example (x, b)
is either positive, if b = 1, or negative, if b = 0.
A concept c is consistent with a set S = {(x1 , b1 ), . . . , (xn , bn )} of examples
iff c(xi ) = bi for all i = 1, . . . , n.

4F.J. Balbach and T. Zeugmann

In the TD model, a learning algorithm takes as input a set S of examples for aconcept c ∈ C and computes a hypothesis h. As mentioned in the Introduction, we
have to restrict the set of admissible learners. A consistent and class preserving
learning algorithm is only allowed to choose the hypotheses from the set
H(S) = {h ∈ C | h is consistent with S} .
A teaching set 3 for a concept c with respect to C is a set S of examples suchthat c is the only concept in C consistent with S, i.e., H(S) = {c} (cf. [17, 19]).
The teaching dimension TD(c) is the size of the smallest teaching set for c, theteaching dimension of C is
TD(C) = max{TD(c) | c ∈ C} .

(1)

Consequently, the teaching dimension of a concept c determines the numberof examples needed by an optimal teacher for teaching c to all consistent and classpreserving learning algorithms. So in the TD model the information theoretic
complexity of teaching is reduced to a combinatorial parameter. Note that theteaching dimension has been calculated for many natural concept classes suchas (monotone) monomials, monotone k-term DNFs, k-term µ-DNFs, monotone
decision lists and rectangles in {0, 1, . . . , n − 1}d (cf. [17]); for linearly separable
Boolean functions (cf. [5, 6]); for threshold functions (cf. [32]); and for k-juntas
and sparse GF2 polynomials (cf. [26]).
Since the teaching dimension does depend exclusively on the concept class,it has also been compared to other combinatorial parameters studied in learningtheory. These parameters comprise the query complexity in Angluin’s [2] query
learning model, the VC-dimension and parameters studied in the online learningmodel (cf. Hegedűs [20, 21], Ben-David and Eiron [12], and Rivest and Yin [31]).
Despite its succinctness and elegance, the teaching dimension has also drawbacks. For seeing this, let us consider the following example. Fix any natural
number n ≥ 2 and define the concept class Sn = {c0 , c1 , . . . , cn } over Xn as
follows: c0 = ∅ as well as ci = {xi } for all i = 1, . . . , n. Then we have TD(ci ) = 1
for all i = 1, . . . , n, since the single positive example (xi , 1) is sufficient forteaching ci . Nevertheless, TD(c0 ) = n, since there are at least two consistent hypotheses until all n negative examples have been presented to the learners. Thus,
TD(Sn ) = n despite the fact that the class Sn seems rather simple. However,
the teaching dimension is the maximum possible.
Similar effects can be observed for the class of all monomials, all 2-term
DNFs, all 1-decision lists, and all Boolean functions (over {0, 1}n ), since allthese classes have the same teaching dimension, i.e., 2n .
2.1

The Average Teaching Dimension

As we have shortly outlined, the teaching dimension does not always capture ourintuition about the difficulty to teach concepts. One reason for the implausibility
3Note that a teaching set is also called key [32], discriminant [28] and witness set [25].

Recent Developments in Algorithmic Teaching

5of the results sometimes obtained is due to the fact that the teaching dimension of
the class is determined by the worst case teaching dimension over all concepts.
Thus, all easily learnable concepts are not taken into account. So a natural
remedy is to consider the average teaching dimension instead of the worst caseteaching dimension.
Definition 1. Let C beP
a concept class. The average teaching dimension of C is1
defined as TD(C) = |C|c∈C TD(c).
Looking again at the class Sn defined above, we directly see that
TD(Sn ) =

n+n·1
<2
n+1

for all n ≥ 2

and thus much smaller than the (worst case) teaching dimension TD(Sn ) = n.
Anthony, Brightwell and Shawe-Taylor [6] showed that the average teaching dimension for the class of linearly separable Boolean functions is O(n2 ) andKuhlmann [24] proved that all classes of VC-dimension 1 have an average teaching dimension of less than 2 and that balls of radius d in {0, 1}n have an averageteaching dimension of at most 2d.
A more general result was shown by Kushilevitz,
Linial, Rabinovich, andp
Saks [25]. They showed an upper bound of O( |C|) for the average teaching
dimension of any concept class C. Additionally, in [25]p a family of classes isdefined for which the average teaching dimension is Ω( |C|).
Naturally, determining the average teaching dimension for classes that are
more complex than Sn is often much harder than calculating their worst caseteaching dimension. However, recently progress has been made. Balbach [7] succeeded in showing that 2-term DNFs and 1-decision lists have an average teaching
dimension of O(n) nicely contrasting their teaching dimension which is 2n .
Based on Balbach’s [7] results, Lee, Servedio, and Wan [26] have shown thatthe class of DNFs with at most s ≤ 2Θ(n) terms has an average teaching dimension of O(ns). Furthermore, they proved that the class of k-juntas has anaverage teaching dimension of at most 2k + o(1) and that the average teaching
dimension of the class of GF2 polynomials with s ≤ (1 − ε) log2 n monomials is
at most ns + 2s.
Nevertheless, there are still points of concern when comparing the TD modeland the average teaching dimension model to a scenario where we have a machineteacher and human learners. Such scenarios are of interest for intelligent tutoring
systems (abbr. ITS), see e.g., www.aaai.org/AITopics/html/tutor.html.
Human learners are not necessarily consistent, they do not remember all
examples, they are sensitive to the order of examples, and they usually provide
feedback about their learning progress.
Clearly, the order of examples does not matter in the TD model and as
mentioned in the Introduction, in the TD model feedback is useless. Learners
not being consistent with all examples are excluded by the definition of the
TD model. There is, however, a dependence on the memory of the learners. Aslong as the learners can memorize at least TD(c) many examples, teaching the6

F.J. Balbach and T. Zeugmannconcept c is possible. If less than TD(c) many examples can be memorized thenteaching becomes impossible.
Last but not least, the applicability to infinite concepts and classes is limited.
Even a rather simple class, like the class of all finite languages over a fixedalphabet Σ yields an infinite teaching dimension. Therefore, we continue withdifferent approaches to model algorithmic teaching.

3

Teaching Learners with Restricted Mind Changes

In this section we summarize some of the results from Balbach and Zeugmann [9].
We modify the TD model by introducing a neighborhood relation over all possible hypotheses. The learners are then restricted to choose a new hypothesis
from the neighborhood of their current one. This may reflect human behavior,
since humans tend to modify their hypotheses instead of creating completely
new ones.
We then compare basically two variants: In the first, the teacher receives
the learner’s hypothesis after every example taught. In the second, the teacher
has no feedback available. As a matter of fact, in this new model feedback canreally make a difference. Some concept classes can be taught much faster withfeedback than without and some cannot be taught unless feedback is available
to the teacher.
Some additional notation is necessary. Let R be a set of strings. We say that
R represents the class C iff there is a function γ : R × X → {0, 1} such thatC = {Cr | r ∈ R}, where Cr = {x | γ(r, x) = 1}. The length of r is denoted by|r| and size(c) := min{|r| | Cr = c} for every c ∈ C. For any set S, we denote
by S ∗ the set of all finite tuples over S. We use the symbols ◦ for concatenationof tuples and 4 for the symmetric difference of two sets. Let c be a concept andlet x ∈ X ∗ be a list of examples, then err (x, c) is the set of all examples in xthat are inconsistent with c.
For studying feedback, the learners in our model have to evolve over time. We
adopt the online learning model and divide the teaching process into rounds. In
each round the teacher provides an example to the learner who then computes ahypothesis from R. At the end of the round the teacher observes this hypothesis.
Thus, we describe a teacher by a function T : R × R∗ → X receiving a
concept’s representation and a sequence of previously observed hypotheses as
input and outputting an example.
A learner can be described by a function L : X ∗ → R receiving a sequenceof examples as input and outputting a hypothesis. Let ν ⊆ R × R be a relation
over R. Then L is called restricted to ν iff ∀x ∈ X ∗ ∀z ∈ X [(L(x), L(x◦z)) ∈ ν],that is ν defines the admissible mind changes of L. Now, (R, ν) is a directed graphand we define the neighborhood of r ∈ R as Nb(r) := {s ∈ R | (r, s) ∈ ν} ∪ {r}and denote by dist(r, s) the length of a shortest path from r to s.
As we have seen, in the TD model, the learner is required to always output
a consistent hypothesis. Since in the restricted model all admissible hypotheses
might be inconsistent, we have to modify this demand. We require that L chooses

Recent Developments in Algorithmic Teaching

7

only among the admissible hypotheses with least error with respect to the known
examples. Moreover, we require a form of conservativeness: L may only change
its hypothesis if the new one has a smaller error. This ensures that L will notchange its mind after reaching a correct hypothesis. On the other hand, we
also require L to search for a better hypothesis if it receives an inconsistentexample. Otherwise, L could stay at the initial hypothesis forever and teachingwere impossible.
Definition 2. Let R be a representation language for a concept class C and letν ⊆ R × R be a relation over R and h0 ∈ R a starting hypothesis. A ν-learner isa function L : X ∗ → R with L(∅) = h0 and for all x ∈ X ∗ and for all z ∈ X :(1) (L(x), L(x ◦ z)) ∈ ν,(2) if L(x) 6= L(x ◦ z) then z is inconsistent with CL(x) ,(3) if z is inconsistent with CL(x) thenL(x ◦ z) ∈ arg mins∈Nb(L(x)) |err (x ◦ z, Cs )|.
We briefly remark that one can think of many plausible variants of the above
definition. For instance, the learner could be allowed to change its mind on aconsistent example if its hypothesis is inconsistent with an example received
earlier. In this section, however, all learners follow Definition 2.
The teaching process for a concept c = Cr is fully described by a teacher T anda learner L together with an initial hypothesis h0 . Such a process will result in aseries (hi )i∈N of hypotheses and a series (zi )i∈N of examples: hi+1 = L(z0 , . . . , zi )and zi = T (r, (h0 , . . . , hi )).
Definition 3. Let C be a concept class with representation R and let ν ⊆ R ×R.
We call C teachable to ν-learners in the limit with feedback iff there is a teacher
T such that for all representations r ∈ R and all ν-learners L the series (hi )i∈Nof hypotheses converges to an h with Ch = Cr .
The teaching time of T on r is the maximum i such that there is a ν-learner Lthat reaches a representation of Cr at round i for the first time.
Note that an infinite teaching time does not imply unteachability of a concept.
For studying the influence of feedback, we also have to define teaching without
feedback. In this situation the teacher is modeled as a function T : R × N → X ,where the second argument specifies the round. The series of hypotheses is thengiven by hi+1 = L(T (r, 0), . . . , T (r, i)). With this notation the definition of teaching in the limit without feedback is literally the same as Definition 3.
In the situation with feedback the teacher can stop teaching as soon as thelearner has reached the goal. If there is no feedback, the teacher may or may notknow when to stop. A teacher stopping after finitely many examples and still
ensuring the learning success is said to teach finitely without feedback. More formally we consider T : R × N → X ∪ {⊥} where ⊥ means “teaching has stopped.”
With feedback we do not need to distinguish teaching finitely from teachingin the limit and we shall call this kind of teaching simply teaching with feedback.

8

F.J. Balbach and T. Zeugmann

Definition 4. Let C be a concept class with representation R and let ν ⊆ R ×R.
We call C finitely teachable to ν-learners without feedback iff there is a teacher Tsuch that for all representations r ∈ R and all ν-learners L the hypothesis hj
with j = min{i | T (r, i) = ⊥} satisfies Chj = Cr .
Setting ν = R × R in Definition 4 gives the teacher-directed learning model
having no restriction on hypothesis changes (cf. [19]). Theorem 5 justifies theuse of arbitrary ν’s for studying the impact of feedback on the teaching process.
Theorem 5. Let C be a concept class with representations R and let ν = R × R.
Then the following statements are equivalent:(1) C is finitely teachable to ν-learners without feedback,(2) C is teachable in the limit to ν-learners without feedback,(3) C is teachable to ν-learners with feedback.
Furthermore in all three cases the same teacher can be used to obtain minimum
teaching time which for all c ∈ C equals TD(c) with respect to C.
Note that Theorem 5 relies on the fact that neither the teacher nor the learners nor the function γ are required to be recursive. Adding these requirements
leads to new questions which we skip here due to space constraints.
Next, we apply the new framework to the class Cfin of all finite languages
over an alphabet Σ. This class cannot be taught in the TD model. By using
different ν-restrictions we demonstrate various effects.
We fix any total ordering on all strings over Σ and use as representation
language R the set of all comma-separated ordered lists of strings over Σ, i.e., r =w1 , . . . , wm ∈ R represents the language {w1 , . . . , wm }. We define the allowedtransitions from r to s by (r, s) ∈ ν iff |Cr 4 Cs | ≤ 1. The initial hypothesis is
the empty string ε representing the empty concept. Now we have:
Fact 6. Cfin is finitely teachable to ν-learners without feedback.
Feedback can be utilized when the restriction is modified. We define (r, s) ∈ ν 0
iff Cs = Cr ∪ {w1 , w2 } for some w1 , w2 ∈ Σ ∗ or Cs = Cr \ {w1 }. In both cases, we
require that the size of the hypotheses may at most double each round: |s| ≤ 2|r|.
In the special case r = ε we allow every singleton concept as neighbor: (ε, s) ∈ ν
for all s with |Cs | = 1. For ν 0 -learners there is a big difference in teaching time
between teaching with and without feedback.
Fact 7. Cfin is teachable to ν 0 -learners with feedback such that for all c ∈ C thenumber of examples is O(|c|) ≤ O(size(c)).
If we remove the size restriction from ν 0 we obtain ν 00 .
Fact 8. Cfin is not finitely teachable to ν 00 -learners without feedback, but it isfinitely teachable with feedback as well as in the limit without feedback.

Recent Developments in Algorithmic Teaching

9

Finally we define ν 000 . It differs from ν 00 in that a string may only be removed
from the hypothesis if neither its predecessor nor its successor (with respect tothe fixed ordering on Σ ∗ ) is contained in the hypothesis.
Fact 9. Cfin is not teachable to ν 000 -learners in the limit without feedback, but it
is finitely teachable with feedback.
If we denote by TFIN , TFB , TLIM the set of all (C, R, ν, h0 ) such that C isfinitely teachable without feedback, with feedback or in the limit, respectively,
we have just proved the following theorem.
Theorem 10. TFIN ⊂ TLIM ⊂ TFB .
The teaching times in our model can hardly be compared to the teaching
dimension, since the latter depends only on C, whereas different choices of ν
can lead to different teaching times for the same C. The problem of finding an
optimal teacher (with or without feedback) for ν-learners is N P-hard, since it
is a generalization of finding an optimal teaching set, namely if ν = R × R (cf.
[32, 17, 5]). More precisely, we have the following theorem.
Theorem 11. For all notions of teaching, the following problem is N P-hard:
Instance: C, R, ν, and a concept c∗ as 0-1-vector of length |X|.
Question: Can c∗ be taught to ν-learners?
For infinite instance spaces or classes (and infinite ν) the next theorem applies.
Theorem 12. The following function is not computable:
Input: Algorithms computing total functions deciding C and ν.
Output: 1, if C can be taught to ν-learners; 0 otherwise.
We finish this section by looking at teaching without feedback. A teacher T
without feedback knows all learners’ initial hypotheses h0 , but can quickly lose
track of them during teaching. On the other hand, T can rule out neighbors rof h0 by giving examples consistent with h0 , but inconsistent with r. If in sucha way T can eliminate all but one neighbor r0 , he effectively forces all learners
to switch to r0 . By continuing in this manner, T always knows all learners’ hypotheses even without feedback. If the enforced hypotheses approach the target,
T will be successful. Figure 1 describes this strategy more formally.
The feasibility of this strategy depends on Step 2.1. If teaching does notneed to be finite, the condition in Step 2 does not need to be checked. Albeit
simple, the strategy works surprisingly often for natural concept classes andν-restrictions. In the following we give some examples.
First, we consider the class of all monomials over n variables. Let R ={0, 1, ∗}n and define (r, s) ∈ ν iff r and s differ only in one “bit.” As initial
hypothesis h0 = ∗n is used.
Fact 13. Monomials are finitely teachable without feedback. The teaching timefor each concept equals its teaching dimension.

10

F.J. Balbach and T. Zeugmann

1 r := h0 ;2 while Cr 6= c∗ do:
2.1 Find s ∈ Nb(r), S ⊆ X , and z ∈ X such that (1) Cr is consistent with S, but
not with z, (2) s is the only neighbor of r consistent with S ∪ {z}, and (3)dist(s, r∗ ) < dist(r, r∗ );2.2 Teach S in arbitrary order and then z;
2.3 r := s;Fig. 1. A simple general strategy for teaching without feedback by forcing all learners
to make the same mind changes. The initial hypothesis is h0 , r∗ represents the target.

Next, we look at decision trees. Each learner starts at the tree consisting of
only one negative leaf. In each round one leaf may be substituted by an internal
node that has two differently labeled leaves as children. This specifies a relation
νDT over all decision trees. Then, we have:
Fact 14. The class of Boolean functions represented as decision trees can betaught without feedback to νDT -learners. The teaching time is linear in the sizeof the tree representation.
Note that the teaching dimension with respect to all Boolean functions is 2n
for all concepts. As we have seen, for ν-learners based on decision trees, teaching
can often be successful with much fewer examples. Finally, we have been a bit
surprised to obtain:
Fact 15. The class of monotone 1-decision lists can be taught to νDL -learners
with feedback using m + 1 examples for a list of length m. It cannot be taught
without feedback.
In our model of teaching learners with restricted mind changes several effects
regarding feedback can be observed. Feedback can be useless, helpful, or evenindispensable for teaching. In addition, natural infinite concept classes can betaught in this model. However, the main drawback is that one has to define suitably a neighborhood relation for every concept class. Our next model avoids thisdifficulty. It will also allows us to study teaching learners with limited memory.

4

The Randomized Teaching Model

For the sake of motivation, let us consider the concept class of all Boolean functions over {0, 1}n . To teach a concept to all consistent learning algorithms, i.e.,in the TD model, 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 harder, but in a rather abrupt way.
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 forthis is to perform an average case analysis instead (cf. Subsection 2.1). In this

Recent Developments in Algorithmic Teaching

11

section we look at 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.
Next, we explain why this model should work. Since at every round there isa chance to reach the target, the target will eventually be reached even if, forinstance, the randomized learner can only memorize few examples. The ability ofthe 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. Below we showthese intuitions to be valid.
Note that for randomized learners the complexity of the teaching process
does not only depend on the examples, but also on the order in which they are
given to the learner.
The randomized teaching model can be regarded as a Markov Decision Process (abbr. MDP). Such processes have been studied for several decades andwe shall make use of some results from this theory (cf. [29, 13]). An MDP is a
probabilistic system whose state transitions can be influenced during the processby actions which incur costs. Let R denote the set of all real numbers. Formally,
an 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 :!
π(s) ∈ argmin cost(s, a) +
a∈A

X

0

0

p(s, a, s ) · H(s )

.

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.

12

F.J. Balbach and T. Zeugmann

For the following, we need a bit more notation. 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 = ∞. As
above, for any set S, we denote by S ∗ the set of all finite lists of elements from S.
Furthermore, by S m and S ≤m we denote 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 theusual 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. We use Dn to denote the set of all 2n concepts
over [1, n]. Thus, there are 2n many concepts in Dn .
Next, we define the randomized teaching model. The teaching process isdivided into rounds. In each round the teacher gives the learner an example
of a target concept. The learner memorizes this example and computes 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), thepublic 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 roundof 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;Recent Developments in Algorithmic Teaching

13

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 concept c∗
as input. Then, in each round, it receives the public output of the learner (if any)and outputs an example for c∗ .
Definition 16. Let C be a concept class and c∗ ∈ C. Let Lσµ be a learner, whereσ ∈ {+, −}, let T be a teacher and let (hi )i∈N be the series of random variables
for the hypothesis at round i. The event “teaching success in round t,” denotedby 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 successfuli0finite iff there is a t 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 17. 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).
For exemplifying our model, we compute the optimal teaching times for Dn .
To the learner L+µ (1 ≤ µ ≤ n) the teacher gives 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 it chooses
one of them. So the probability of choosing the target concept is 2−(n−µ) . Since
in the first µ − 1 rounds the memory contains less then µ examples, Eµ+ (Dn ) is,for constant µ, asymptotically equal to 2n−µ . Clearly, teaching becomes fasterwith growing µ. Moreover the teaching speed increases continuously with µ andnot abruptly as in the classical deterministic model. In particular, teaching ispossible 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 .

14

F.J. Balbach and T. Zeugmann

Fact 18. 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 TD model, i.e., the teaching dimension, to the randomized
model (in terms of the expected teaching time).
Lemma 19 ([11]). Let C be a concept 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.
Now, we take a closer look at learners with feedback. For the sake of presentation we start with 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; finally p(c∗ , z, c∗ ) = 1 (see[13, 29]). The initial state is init and the state c∗ is costless and absorbing. The
memory is not 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.
Lemma 20. Let C be a concept class over X and let 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)This criterion can be used to prove optimality for teaching algorithms.
We 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 21. (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) .

Recent Developments in Algorithmic Teaching

15

Roughly speaking, teaching L+
1 can take arbitrarily longer than teaching in
the classical model, but is still incomparable with membership query learning.
We finish this subsection by looking at learners with ∞-memory. A straight∗ ≤|X|
forward MDP for teaching c∗ to L+.
∞ has states S = (C ∪ {init}) × 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 thesize of 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 20 can be stated for the L+∞ learner, too, andused to prove optimality of algorithms. Note that 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 19 that E∞ (c ) ≥ TD(c )/2. This means+ ∗that every algorithm computing E∞(c ) also computes a factor 2 approximationof the teaching dimension.
As it has often been noted [32, 5, 17], 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 [30] have shown that
there is no polynomial time constant-factor approximation (unless P = N P).
Moreover, Feige [14] proved that SET-COVER cannot be approximated better than
within a logarithmic factor (unless N P ⊆ DTime(nlog log n )).
+Corollary 22. 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.

However, we have:
Fact 23. 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.
Note that our model of teaching a randomized learner also allows for studying
teaching from positive data only. The interested reader is referred to [11] fordetails. Here we only mention the following topological characterization.
Theorem 24. 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∗ .
Studying the teachability of randomized learners without feedback is muchharder, since the problem of finding the optimal cost in an MDP whose states are
not observable is much more difficult. We refer the interested reader to Balbach
and Zeugmann [10] for results in this regard.

5

Further Directions

A number of variations of the teaching dimension have been studied in which
the learner is assumed to act smarter than just choosing a consistent hypothesis.

16

F.J. Balbach and T. Zeugmann

One such model (see Balbach [7, 8]) assumes the learner picks hypotheses thatare not only consistent but of minimal complexity. This model is inspired by
the Occam’s razor principle. A teacher that exploits this learning behavior canmake do with fewer examples than in the original teaching dimension model. For
example, 2-term DNFs and 1-decision lists can be taught with O(n) examples,as opposed to 2n examples (n being the number of variables). Note that thismodel presupposes a measure of complexity for all concepts in the class, such as
the length of a decision list or the number of terms in a DNF. But there might
not be a unique, natural complexity measure for a given class.
Another variant devised by Balbach [8] assumes that the learners know theteaching dimensions of all concepts in the class and choose their hypotheses only
from the consistent ones with a teaching dimension at least as large as the sample given by the teacher. In other words, they assume the teacher does not give
more examples than necessary for the concept to be taught. This optimal teacher
teaching dimension (OTTD) model demands more of the learners, as they needto know all the teaching dimensions, but reduces the number of examples compared to the plain teaching dimension. For example, the OTTD of monomials is
linear √in the number of variables,
and the OTTD of 1-decision lists is bounded√by Ω( n · 2n/2 ) and O(n log n · 2n/2 ).
If the learners in the OTTD model base their reasoning on the OTTD rather
than the teaching dimension, one obtains yet another dimensionality measure.
Intuitively, the learners assume that the teacher knows how they think andadjusts the sample he gives. Now the teacher can exploit this new behavior of
the students, again reducing the number of examples needed. This gives rise to aseries of decreasing dimensionality notions which, for finite concept classes, will
eventually converge.
In a similar vein, Zilles, Lange, Holte, and Zinkevich [33] defined a teachingmodel which is based on cooperative learners. Here the learners are assumed toknow all minimal teaching sets for all concepts in the class, and they always
choose from the consistent hypotheses a minimal teaching set which contains all
examples given so far. In other words they assume that at all times the sample
given by the teacher can be extended to a minimal teaching set for the concept
to be taught. This demands even more of the learners than the OTTD, as they
now have to know all minimal teaching sets of all concepts. In a similar way as
above, this idea can be iterated, yielding a series of dimensionality notions thatconverge to one called the subset teaching dimension (STD). The STD is a lower
bound for the iterated OTTDs. Zilles et al. [33] show a number of surprisingproperties of the STD. For example, the STD of the class of monomials is two,
independent of the number of variables. A surprising property of the STD is its
nonmonotonicity, that is, the STD of some classes is less than that of one of
their subclasses.
Finally, Zilles et al. [33] devise a dimensionality notion called the recursive
teaching dimension (RTD), which combines the easy teachability of the monomials in the STD model with the property of monotonicity in the TD and OTTD
models. However, it is not based on refined assumptions about the learners’ be-Recent Developments in Algorithmic Teaching17

havior and only measures the teachability of an entire concept class, not that ofindividual concepts. The basic idea is to order the concepts in a class and determine the teaching dimension of each concept with respect only to the class of
all following concepts. The maximum teaching dimension for any concept minimized over all possible orderings determines the RTD of the class. The RTD isa lower bound for all iterated OTTDs, but its precise relationship to the STD is
unknown. The STD is conjectured to be a lower bound for the RTD.

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 Proceedings of
the Tenth Annual Conference on Computational Learning Theory, July 6th–9th,
1997, Nashville, Tennessee, pages 285–297, New York, NY, 1997. ACM Press.
[4] D. Angluin and M. Kriķis. Learning from different teachers. Machine Learning,
51(2):137–163, 2003.
[5] M. Anthony, G. Brightwell, D. Cohen, and J. Shawe-Taylor. On exact specification
by examples. In Proc. 5th Annual ACM Workshop on Computational Learning
Theory, pages 311–318, New York, NY, 1992. ACM Press.
[6] M. Anthony, G. Brightwell, and J. Shawe-Taylor. On specifying Boolean functions
by labelled examples. Discrete Applied Mathematics, 61(1):1–25, 1995.
[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] F. J. Balbach. Measuring teachability using variants of the teaching dimension.
Theoret. Comput. Sci., 397(1-3):94–113, 2008.
[9] F. J. Balbach and T. Zeugmann. Teaching learners with restricted mind changes.
In Algorithmic Learning Theory, 16th International Conference, ALT 2005, Singapore, October 2005, Proceedings, volume 3734 of Lecture Notes in Artificial
Intelligence, pages 474–489. Springer, 2005.
[10] F. J. Balbach and T. Zeugmann. Teaching memoryless randomized learners without feedback. In Algorithmic Learning Theory, 17th International Conference,
ALT 2006, Barcelona, Spain, October 2006, Proceedings, volume 4264 of Lecture
Notes in Artificial Intelligence, pages 93–108. Springer, 2006.
[11] F. J. Balbach and T. Zeugmann. Teaching randomized learners. In Learning
Theory: 19th Annual Conference on Learning Theory, COLT 2006, Pittsburgh,
PA, USA, June 2006, Proceedings, volume 4005 of Lecture Notes in Artificial
Intelligence, pages 229–243, Berlin, 2006. Springer.
[12] S. Ben-David and N. Eiron. Self-directed learning and its relation to the VCdimension and to teacher-directed learning. Machine Learning, 33(1):87–104,
1998.
[13] D. P. Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific,
2001.
[14] U. Feige. A threshold of ln n for approximating set cover. J. of the ACM,
45(4):634–652, 1998.

18

F.J. Balbach and T. Zeugmann[15] R. Freivalds, E. B. Kinber, and R. Wiehagen. Inductive inference from good
examples. In Analogical and Inductive Inference, International Workshop AII ’89,
Reinhardsbrunn Castle, GDR, October 1989, Proceedings, volume 397 of Lecture
Notes in Artificial Intelligence, pages 1–17. Springer-Verlag, 1989.
[16] 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.
[17] S. A. Goldman and M. J. Kearns. On the complexity of teaching. J. of Comput.
Syst. Sci., 50(1):20–31, 1995.
[18] S. A. Goldman and H. D. Mathias. Teaching a smarter learner. J. of Comput.
Syst. Sci., 52(2):255–267, 1996.
[19] S. A. Goldman, R. L. Rivest, and R. E. Schapire. Learning binary relations andtotal orders. SIAM J. Comput., 22(5):1006–1034, 1993.
[20] T. Hegedűs. Combinatorial results on the complexity of teaching and learning. In
Mathematical Foundations of Computer Science 1994, 19th International Symposium, MFCS ’94, Košice, Slovakia, August 22-26, 1994, Proceedings, volume 841
of Lecture Notes in Computer Science, pages 393–402. Springer-Verlag, 1994.
[21] T. Hegedűs. Generalized teaching dimensions and the query complexity of learning. In Proc. 8th Annual Conference on Computational Learning Theory, pages
108–117, New York, NY, 1995. ACM Press.
[22] J. Jackson and A. Tomkins. A computational model of teaching. In Proc. 5th
Annual ACM Workshop on Computational Learning Theory, pages 319–326, New
York, NY, 1992. ACM Press.
[23] S. Jain, S. Lange, and J. Nessel. On the learnability of recursively enumerable
languages from good examples. Theoret. Comput. Sci., 261(1):3–29, 2001.
[24] 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.
[25] E. Kushilevitz, N. Linial, Y. Rabinovich, and M. Saks. Witness sets for families ofbinary vectors. Journal of Combinatorial Theory Series A, 73(2):376–380, 1996.
[26] H. Lee, R. A. Servedio, and 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, volume 4005 of Lecture Notes in
Artificial Intelligence, pages 214–228, Berlin, 2006. Springer.
[27] H. D. Mathias. A model of interactive teaching. J. of Comput. Syst. Sci.,
54(3):487–501, 1997.
[28] B. K. Natarajan. Machine Learning: A Theoretical Approach. Morgan Kaufmann,
San Mateo, CA, 1991.
[29] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 1994.
[30] 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. ACM Press, 1997.
[31] R. L. Rivest and Y. L. Yin. Being taught can be faster than asking questions. In
Proc. 8th Annual Conference on Computational Learning Theory, pages 144–151,
New York, NY, 1995. ACM Press.
[32] A. Shinohara and S. Miyano. Teachability in computational learning. New Generation Computing, 8(4):337–348, 1991.
[33] S. Zilles, S. Lange, R. Holte, and M. Zinkevich. Teaching dimensions based oncooperative learning. In 21st Annual Conference on Learning Theory - COLT
2008, Helsinki, Finland, July 9-12, 2008, pages 135–146. Omnipress, 2008.