Understanding the Power and Limitations of Teaching with Imperfect Knowledge

1 Introduction

The field of machine teaching studies the interaction between a teacher and a student/learner where the teacher's objective is to select a short sequence of examples for the learner to learn a specific task [Goldman and Kearns, 1995; Zhu et al., 2018]. An important application is in education where the learner is a human student, and the teacher is a computerized intelligent tutoring system (ITS) that selects a curriculum of learning material for the student [Zhu, 2015; Rafferty et al., 2016; Sen et al., 2018; Hunziker et al., 2019]. Another concrete application is the data poisoning (trainingtime) adversarial attacks where the learner is a machine learning (ML) system, and the teacher is a hacking algorithm that poisons the training data to maliciously change the learner's output to a desired target [Mei and Zhu, 2015; Zhu, 2018]. Regardless of the application and the teacher's intentions, machine teaching provides a formal model of quantifying the teaching effort and an algorithmic framework for deriving an optimized curriculum of material to have maximum influence on the learner with minimal effort. Considering applications in educational settings, the problem of designing an optimized curriculum is of utmost importance because it leads to more effective learning, increased engagement, and reduced drop-out of students [Archambault et al., 2009].

∗Authors contributed equally to this work.

The key issue in applying machine teaching algorithms to real-world applications is that these algorithms (and the corresponding theoretical guarantees) often make unrealistic assumptions about the teacher's knowledge of the learner and the task. It is typically assumed that the teacher has perfect knowledge of the following: (i) the learner, e.g., a computational model of the learning dynamics, and parameters capturing initial knowledge and learning rate, (ii) task specification, e.g., a complete ground truth data and representation of the task as used by the learner. Assuming such a powerful teacher might be meaningful for deriving theoretical guarantees (e.g., computing information-theoretic lower bounds of teaching complexity [Goldman and Kearns, 1995; Zilles et al., 2011; Chen et al., 2018b; Mansouri et al., 2019]) or for understanding the vulnerability of an ML system (e.g., against a white-box poisoning attack [Zhang et al., 2018; Ma et al., 2019]). However, for applications in education where the student is a human learner, this assumption is clearly unrealistic: learning dynamics and task specifications are usually obtained from domain expertise or inferred from historical student data (see [Singla et al., 2014; Piech et al., 2015; Settles and Meeder, 2016; Sen et al., 2018; Hunziker et al., 2019]), and this information is often incomplete and noisy.

1.1 Our Approach and Contributions

Ironically, while the promise of machine teaching algorithms lies in providing a near-optimal teaching curriculum with guaranteed performance, the fundamental assumptions required by these algorithms are clearly violated in practice. The main research question we study in this paper is the following: When does a teacher succeed or fail in effectively teaching a learner using its imperfect knowledge?

To answer this question, we require a formal specification of the task, a learner model, and a concrete teaching algorithm. In our work, we study a classification task in the context of teaching human students the rules to identify animal speciesan important skill required for biodiversity monitoring related citizen-science projects [Sullivan et al., 2009; Van Horn et al., 2018]. This is one of the few real-world applications for which machine teaching algorithms with guarantees have been applied to teaching human learners in educational settings (see [Singla et al., 2013; Singla et al., 2014; Chen et al., 2018a; Mac Aodha et al., 2018]) and hence is well-suited for our work. We highlight some of the key contributions and results below:

• We formally study the problem of robust machine teaching. To quantify the effectiveness of teaching, we introduce two metrics that measure teacher's success in terms of the learner's eventual error, and the size of the teaching set as constructed by a teacher with imperfect knowledge (Section 2).
• We show that teaching is much more brittle w.r.t noise in learning rate and less so when considering noise in prior knowledge of the learner. This theoretical result aligns with a similar observation recently made in the context of a very different learning model (Section 3).
• When studying robustness w.r.t. noise in task specification, we provide natural regularity conditions on the data distributions and then use these conditions when specifying the guarantees. This allows us to take a less pessimistic view in comparison to contemporary works that study the worst-case setting (Section 4).

Remarks on proofs and reproducibility. Detailed proofs of theorems are provided in the longer version of the paper [Devidze et al., 2020]. For the reproducibility of experimental results and facilitating research in this area, the code and dataset are publicly available.

1.2 RelatedWork on Robust Machine Teaching

A growing body of contemporary works has tackled the problem of robust machine teaching in different forms, however, with a very different focus compared to ours. For instance, [Liu et al., 2018; Melo et al., 2018; Dasgupta et al., 2019; Kamalaruban et al., 2019] have studied the problem of teaching a "blackbox" learner where the teacher has very limited or no knowledge of the learner. The focus of these papers has been on designing an online teaching algorithm that infers the learner model in an online fashion. These works often conclude that an offline teaching algorithm that operates with limited knowledge can perform arbitrarily bad by considering a worst-case setting. However, designing and deploying online algorithms is a lot more challenging in practice-the results in contemporary works have mostly been theoretical and might not be directly applicable in practice given the high sample complexity of online inference. The focus of our work is primarily on offline teaching algorithms, where knowledge about the task is usually obtained from domain expertise or inferred from historical student data. We aim at developing a fundamental understanding of how the performance guarantees of a teaching algorithm degrade w.r.t. the noise in teacher's knowledge when considering natural data distributions.

In another line of contemporary work on teaching a reinforcement learning agent, [Haug et al., 2018; Tschiatschek et al., 2019] have considered the setting where teacher and learner have different worldview and preferences-the focus of these works is on designing a teaching algorithm to account for these mismatches, and do not directly tackle the question we study in this paper. There has also been some empirical work on understanding the robustness and effect of different model components as part of the popular Bayesian Knowledge Tracing (BKT) teaching model used in ITS [Klingler et al., 2015; Khajah et al., 2016]-we see this work as complementary to ours as we take a more formal approach towards understanding the robustness of theoretical guarantees provided by machine teaching algorithms.

2 ProblemFormulation

In this section, we first introduce the task representation, the learner's model, and the teacher's optimization problem. Then, we formulate the problem of teaching with imperfect knowledge, and discuss the notions of successful teaching.

2.1 Teaching Task and Representation

We consider the problem of teaching a binary classification task. Let X denote a ground set of instances (e.g., images), and the learner uses a feature representation of φ : X → Rd . Let H be a finite class of hypotheses considered by the learner where each hypothesis h ∈ H is a function h : X → {-1, +1}. As a concrete setting, H could be the set of hypotheses of the form h(x) = sign(〈θh, φ(x)〉) where θh ∈ Rd is the weight vector associated with hypothesis h.

Each instance x ∈ X is associated with a ground truth label given by the function y∗ : X → {-1, 1}, and we denote the ground truth label of an instance x as y∗ (x). The ground truth labels given by y∗ are not known to the leaner. We use Z to denote instances with their labels where a labeled example z ∈ Z is given by z = (x, y∗ (x)).

As typically studied in machine teaching literature, we consider a realizable setting where there exists a hypothesis h∗ ∈ H such that ∀x, h∗ (x) = y∗ (x). 1 The teacher's goal can then be stated as that of teaching the hypothesis h∗ to the learner by providing a minimal number of labeled examples to the learner. Before formulating the teacher's optimization problem of selecting labeled examples, we state the learning dynamics of the learner below.

2.2 Learner Model

We consider a probabilistic learner model that generalizes the well-studied version space models in classical machine teaching literature (see [Goldman and Kearns, 1995]). At a high-level, the learner works as follows: During the learning process, the learner maintains a score for each hypothesis given by Q(h) capturing learner's belief of how good the hypothesis h is. Given Q(h), the learner acts probabilistically by drawing a hypothesis with probability Q(h) ∑h′∈H Q(h′ ) . Next, we discuss how the scores are updated.

1 This assumption is w.l.o.g.: In a non-realizable setting, the teacher could consider h∗ ∈ H as a hypothesis with minimal error in terms of disagreement of labels w.r.t. the labels given by y∗ and the results presented in this paper can be extended to this general setting.

Before teaching starts, the learner's prior knowledge about the task is captured by initial scores given by Q0(h). For simplicity and as considered in [Singla et al., 2014; Chen et al., 2018a], we will assume that Q0(h) is a probability distribution over H. After receiving a set of labeled examples S = {(xs, ys)}s=1,2,... from the teacher, we denote the learner's score as Q(h|S) which are updated as follows:

where J is a likelihood function parameterized by η ∈ (0, 1]. In this paper, we consider the following likelihood function given by:

Here, the quantity η captures a notion of the learning rate. This model reduces to a randomized variant of the classical learner model [Goldman and Kearns, 1995]) for η = 1. The main results and findings in the paper also generalize to more complex likelihood functions such as the logistic functions considered by [Singla et al., 2014; Mac Aodha et al., 2018].

An important quantity of interest in this paper is the learner's expected error after receiving a set of examples S. Let err(h) = ∑z=(x,y)∈Z 1h(x)̸=y |Z| be the expected error of h. The learner's expected error is given by the following:

2.3 Teaching with Perfect Knowledge

We first consider the optimal teaching problem when the teacher has perfect knowledge of the teaching task represented as (Q0, η, Z, h∗ , φ,H). In particular, the teacher's knowledge comprises: (i) learning dynamics captured by learner's initial knowledge Q0 and learning rate η, (ii) task specification captured by the target hypothesis h∗ , the ground set of labeled examples Z, the feature map φ, and hypothesis class H.

Teacher's primary goal is to find a smallest set of labeled examples to teach so that learner's error is below a certain desirable threshold ϵ. To construct the optimal teaching set, instead of directly optimizing for a reduction in error, it is common in the literature to construct surrogate objective functions which capture learner's progress towards learning h∗ (also, see [Goldman and Kearns, 1995; Singla et al., 2014; Chen et al., 2018a; Mac Aodha et al., 2018].).

Let us define a set function F : 2Z →R≥0 as follows:

Here, the quantity (Q0(h) -Q(h|S)) captures the reduction in the score for hypothesis h after learner receives examples set S. In particular, the surrogate objective function F is a soft variant of set cover, and allows one to design greedy algorithms to find near-optimal teaching sets.

For a given ϵ, one can find a corresponding (sufficient) stopping value Cϵ such that F(S) ≥ Cϵ implies that ERR(S) ≤ ϵ. As used in the optimization frameworks of [Singla et al., 2014;

Mac Aodha et al., 2018], we use Cϵ = ∑h∈H Q0(h)·err(h)- ϵ · Q0(h∗ ). This leads to the following optimization problem:

where F(S) is given in Eq. 4. We use OPTϵ to denote the optimal teaching set as a solution to the problem (5).

2.4 Teaching with Imperfect Knowledge

We now consider a teacher with imperfect knowledge and study the following different settings:

• having noise on learner's initial knowledge Q0 ( Section 3.1)
• having noise on learner's learning rate η (Section 3.2).
• having access to ground truth labels for only a subset of instances instead of the whole ground set X (Section 4.1).
• having a noisy feature map, i.e., teacher's assumed feature map does not match with φ used by the learner (Section 4.2).

We denote the teacher's view of the imperfect knowledge as ( ˜Q0, ˜ η, ˜ Z, ˜ h∗ , ˜ φ, ˜H). Given this knowledge, the teacher has its own view of quantities such as ˜Q(h|S) (cf., Eq. 1), ˜ err(h) (cf., err(.) used in Eq. 3), and ˜ F (cf., Eq. 4) as counterparts to those of a teacher with perfect knowledge. The optimization problem from the viewpoint of the teacher with imperfect knowledge can be written as follows:

In the subsequent sections, we will introduce notions of ∆-imperfect knowledge depending on a set/tuple of parameters ∆. Let us denote by ˜ OPTϵ,∆ the teaching set found by ∆-imperfect teacher as a solution to the problem (6). The following definitions quantify the success of a teacher with imperfect knowledge w.r.t. to measure M.1 (related to learner's error) and measure M.2 (related to teaching set size).

Definition 1 (M.1-successful). We say a teacher is M.1successful if the learner's eventual error upon receiving the set ˜ OPTϵ,∆ is O(ϵ) (here we treat the parameters as constant).

Definition 2 (M.2-successful). We say a teacher is M.2successful if |˜ OPTϵ,∆| ≤ |OPTˆ ϵ|, where ˆ ϵ = Θ(ϵ) (here we treat the parameters as constant). In other words, the size of the teacher's teaching set is competitive w.r.t. that of a teacher with perfect knowledge which constructs an optimal teaching set for an Θ(ϵ) error threshold. 2

3 Imperfect Knowledge about the Dynamics

In this section, we explore the effectiveness of teaching when the teacher has imperfect knowledge of the learner's prior knowledge Q0 and learning rate η. In fact, these two parameters are key to many popular learner models (e.g., Bayesian Knowledge Tracing (BKT) models in educational applications [Piech et al., 2015; Klingler et al., 2015; Khajah et al., 2016], spaced-repetition models used in vocabulary applications [Settles and Meeder, 2016; Hunziker et al., 2019], or gradient learner models studied for data-poisoning attacks [Liu et al., 2018]).

2 This is the style of bound often considered in literature when taking an optimization perspective on teaching [Singla et al., 2014; Chen et al., 2018a]. One might be tempted to directly bound the size |˜ OPTϵ,∆| as a function of |OPTϵ|, however, this is usually not possible without making further assumptions about the data distribution.

3.1 Noise in the Learning Prior

Here, we consider the setting where the teacher has a noisy estimate ˜ Q0 of learner's initial distribution Q0, i.e., ( ˜Q0, ˜ η, ˜ Z, ˜ h∗ , ˜ φ, ˜H) := (˜ Q0, η,Z, h∗ , φ,H). The following definition quantifies the noise in ˜ Q0 w.r.t. the true Q0.

Definition 3 (∆Q0 -imperfect). Let ∆Q0 = (δ1, δ2) for δ1, δ2 ≥ 0. We say that teacher's estimated distribution ˜Q0 is ∆Q0 -imperfect if the following holds:

The following theorem quantifies the effectiveness of teaching w.r.t. measures M.1 andM.2 (see Definitions 1, 2).

Theorem 1. Fix ϵ ≥ 0, δ1 ≥ 0, and δ2 ≥ 0. Consider a teacher with knowledge ( ˜Q0, η, Z, h∗ , φ,H), where ˜Q0 is ∆Q0 -imperfect w.r.t. true Q0 for ∆Q0 = (δ1, δ2). Then, in the worst-case for any problem setting and any ∆Q0 -imperfect ˜Q0, the teacher is successful w.r.t. measures M.1 and M.2 with the following bounds:

1. The learner's error is O(ϵ) and is bounded as ERR( ˜ OPTϵ,∆Q0 ) ≤ ϵ·(1+δ2) (1-δ1) .
2. The size of the teaching set is bounded as |˜ OPTϵ,∆Q0 | ≤ |OPTˆ ϵ| where ˆ ϵ = ϵ·(1-δ1) (1+δ2) .

The proof is provided in the longer version of the paper [Devidze et al., 2020].

3.2 Noise in the Learning Rate

Next, we consider a setting where the teacher has an imperfect estimate of the learner's learning rate η while having perfect knowledge about the rest of the parameters, i.e., the teacher's knowledge is (Q0, ˜ η, Z, h∗ , φ, H). The following definition quantifies the noise in ˜ η w.r.t. true η.

Definition 4 (∆η-imperfect). Let ∆η = (δ) for δ ≥ 0. We say that a teacher's estimate ˜ η is ∆η-imperfect if |˜ η - η| ≤ δ, where both ˜ η ∈ (0, 1] and η ∈ (0, 1].

The following two worst-case scenarios are of interest: (i) a teacher who overestimates the learning rate with ˜ η = min{η + δ, 1} and (ii) a teacher who underestimates the learning rate with ˜ η = max{η - δ, 0}. The following theorem quantifies the challenges in teaching successfully in this setting.

Theorem 2. Fix ϵ ≥ 0 and δ > 0. Consider a teacher with knowledge (Q0, ˜ η, Z, h∗ , φ, H) where ˜ η is ∆η-imperfect w.r.t. true η for ∆η = (δ). Then, for any ∆η-imperfect ˜ η, there exists a problem setting such that the teacher is unsuccessful w.r.t. measures M.1 and M.2:

1. For any fixed ϵ and ∆η, there exist problem settings where ERR( ˜ OPTϵ,∆η ) ≥ 12 .
2. For any fixed ϵ and ∆η, and any ˆ ϵ arbitrarily close to 0, there exist problem settings where |˜ OPTϵ,∆η | ≥ |OPTˆ ϵ|.

The proof, provided in the longer version [Devidze et al., 2020], is given by creating two problem settings: (i) a setting for the teacher who overestimates η that leads to the first statement about the learner's error, and (ii) a setting for the teacher who underestimates η that leads to the second statement about the size of the teaching set. Comparing Theorem 1 and Theorem 2, these results suggest that noise in the teacher's assumption about the learning rate is a lot more hazardous compared to noise about the learner's initial distribution. While we derived these results by focusing on a very specific task and learner model, similar observations were made in the context of a different type of teaching setting when teaching a gradient learner [Yeo et al., 2019].

Theorem 2 only provides a pessimistic view that the teacher can fail badly. On closer inspection, the negative results arise from two separate issues: (i) teacher computing wrong utility of examples in (6), and (ii) teacher having a wrong estimate of stopping criteria in (6) which in turn depends on learner's progress. Empirically, we found that the second reason seems to be the dominant one for the teacher's failure. One practical way to fix this issue is to develop an interactive teaching strategy where the teacher's stopping criteria is determined by the learner's true progress measured in an online fashion instead of the progress as estimated by the teacher using its offline model (also, see discussions in Section 1.2).

4 Imperfect Knowledge about Representation

In this section, we explore the effect of teaching when the teacher has imperfect knowledge of the task specification, in particular, limited ground truth data and noisy representation of the task used by the learner.

4.1 Limited Ground Truth Labels

Here, we consider the setting where the teacher has ground truth labels for only a subset of examples ˜ Z ⊆ Z. The typical process followed when applying machine teaching algorithms is to first sample a small set of instances ˜ X ⊆ X and then get expert annotations to obtain ˜ Z ⊆ Z (e.g., see [Singla et al., 2014; Mac Aodha et al., 2018]. Then, the teacher selects a hypothesis ˜ h∗ as the one with minimal empirical error given by ˜ h∗ ∈ arg minh∈H ˜ err(h). For this setting, we represent the knowledge of the teacher as (Q0, η, ˜ Z, ˜ h∗ , φ, H).

As long as the set ˜ Z is constructed i.i.d., the teacher can construct teaching sets to ensure that the learner's error would be low (i.e., teaching is successful w.r.t. measure M.1). This argument follows from the standard concentration inequalities which ensures that with high probability, the teacher has a good estimate of ˜ err(·), i.e., ∀ h ∈ H, |˜ err(h)-err(h)| is small (see Theorem 3). However, regarding the teacher's performance on measure M.2, without any additional assumptions about data distribution, it is easy to construct a pessimistic scenario where the data distribution is skewed and the teaching set

-3

• (a) Setting with a few extreme data points

-3

• (b) Setting with skewed data distribution

-3

• (c) Real-world problem setting

Figure 1: (a) shows a problem setting with a few extreme points that are important for teaching-assuming η = 1 and ϵ = 0 for simplicity of arguments, the optimal teaching set consists of only two examples lying close to coordinates (3, 0). However, if these two examples are not present in ˜ Z, the teaching set can be arbitrarily large (i.e., of size 6 in the illustration). (b) shows another problem setting with skewed data distribution where a small perturbation of data could lead to big changes in the prediction of hypotheses. (c) shows a real-world problem setting to distinguish animal species. As can be seen, the data distribution here is more "well-behaved" and does not suffer from issues present in the other two problem settings. Note that only a few hypotheses are shown in the illustration, see Section 5 for more details.

˜ OPTϵ,∆ constructed by a teacher with imperfect knowledge is arbitrarily large w.r.t. the optimal teaching set OPTϵ (see Figure 1).

Building on insights from the problem settings discussed in Figure 1, we consider additional structural assumptions on the problem setting as discussed below. First, we introduce the notion of δ-perturbed set of examples.

Definition 5 (δ-perturbed). Consider a set of labeled examples S ⊆ Z. We call S′ a δ-perturbed version of S, if there exists a bijective map S ↦→ S′ , (x, y) ↦→ (x′ , y) such that ‖φ(x) - φ(x′ )‖2 ≤ δ.

We will also need the following smoothness notion for proving robustness guarantees (for bounding the size in Theorem 3 and for bounding both the error/size in Theorem 4).

Definition 6 (λ-smoothness). Let δ ≥ 0, λ ≥ 0. Consider any set S ⊆ Z, and let S′ be any δ-perturbed version of S. Then, we call the problem setting λ-smooth when the following holds: for any h ∈ H, the mismatch in labels assigned by h to examples S and S′ is upper-bounded by λ · δ.

Definition 7 below quantifies the imperfection in teacher's knowledge arising from the sampling process coupled with additional structural conditions.

Definition 7 (∆Z-imperfect). Let ∆Z = (δ1, δ2, δ3) for δ1, δ2, δ3 ≥ 0. We say that a teacher's knowledge is ∆Zimperfect if the following statements hold with probability at least (1- δ1):

• ∀ h, |˜ err(h) - err(h)| ≤ δ2,
• for any set of labeled examples S ⊆ Z with |S| ≤ | ˜ Z|, there exists a δ3-perturbed version of S in ˜ Z.

Note that in the above definition, the bound on error is satisfied from the i.i.d. sampling process and doesn't require any further structural assumption. The second condition implicitly adds regularity conditions on the underlying data distribution ensuring that it does not have characteristics as seen in Figure 1a and Figure 1b. The following theorem quantifies the effectiveness of a ∆Z-imperfect teacher.

Theorem 3. Fix ϵ ≥ 0 and ∆Z = (δ1, δ2, δ3) with δ1, δ2, δ3 ≥ 0. Consider a ∆Z-imperfect teacher with knowledge (Q0, η, ˜ Z, ˜ h∗ , φ,H). Assume the problem setting is λsmooth for some λ ≥ 0, η < 1, and | ˜ Z| is sufficiently large. Then, for any sample ˜ Z and selection of ˜ h∗ , with probability at least (1- δ1), the teacher is successful with the following bounds:

1. The learner's error is O(ϵ) and is bounded as ERR( ˜ OPTϵ,∆Z ) ≤ (ϵ·Qmax+δ2) Q(h∗ ) .
2. The size of the teaching set is bounded as |˜ OPTϵ,∆Z | ≤ |OPTˆ ϵ| where ˆ ϵ = (ϵ·Qmin-δ2)·(1-η)λ·δ3 Q(h∗ )

The proof of the theorem is provided in the longer version of the paper [Devidze et al., 2020]. Note that the bound is only valid for η < 1. When η approaches 1, and for the extreme case of η = 1, the learner reduces to a noise-free version space learner who eliminates all inconsistent hypothesis immediately. For this setting, bounding the teaching set size requires more combinatorial assumptions on the dataset (e.g., based on the separability of data from the hyperplanes)-however, for practical applications, η bounded away from 1 is a more natural setting as analyzed in this theorem.

4.2 Noise in Feature Embedding

Here, we consider imperfect knowledge in terms of noisy feature map ˜ φ. This is a challenging setting as noise in φ means error in the predictions of hypotheses h ∈ H which in turn leads to noise in error of hypotheses err(.) and in the likelihood function J. As noted earlier, the teacher will select a hypothesis ˜ h∗ as the one with minimal error given by ˜ h∗ ∈

arg minh∈H ˜ err(h). The following definition quantifies the imperfection in the teacher's knowledge (Q0, η, Z, ˜ h∗ , ˜ φ, H). Definition 8 (∆φ-imperfect). Let ∆φ = (δ1, δ2) for δ1, δ2 ≥ 0. We say that a teacher's knowledge is ∆φ-imperfect if the following holds:

• ∀ x ∈ X, ||φ(x) - ˜ φ(x)||2 ≤ δ1,
• ∀ h, |˜ err(h) - err(h)| ≤ δ2.

The following theorem quantifies the effectiveness of teaching of a ∆φ-imperfect teacher.

Theorem 4. Fix ϵ ≥ 0 and ∆φ = (δ1, δ2) with δ1, δ2 ≥ 0. Consider a ∆φ-imperfect teacher with knowledge (Q0, η, Z, ˜ h∗ , ˜ φ,H). Assume the problem setting is λ-smooth for some λ ≥ 0, that η < 1, and assume that the error ˜ err(˜ h∗ ) = 0. Then, in the worst-case for any observed ˜ φ and selection of ˜ h∗ , the teacher is successful with the following bounds:

1. The learner's error is O(ϵ) and is bounded as ERR( ˜ OPTϵ,∆φ ) ≤ (ϵ·Qmax+δ2) Q(h∗ )·(1-η)λ·δ1 .
2. The size of the teaching set is bounded as |˜ OPTϵ,∆φ | ≤ |OPTˆ ϵ| where ˆ ϵ = (ϵ·Qmin-δ2)·(1-η)λ·δ1 Q(h∗ ) .

The proof is provided in the longer version of the paper [Devidze et al., 2020]. In comparison to the error bound in Theorem 3, the error bound here with noise in φ is much worsethis is a lot more challenging setting given that hypotheses predictions on examples can be wrong in this setting. Here, for simplicity of the proof and presentation of results, we assumed that there exists some ˜ h∗ for which error in teacher's representation is 0, i.e., ˜ err(˜ h∗ ) = 0, see discussion in Footnote 1. The theorem suggests that when considering additional structural/smoothness assumptions on the problem, the teaching with imperfect knowledge about representations is robust w.r.t. both M.1 and M.2 success criteria. As we shall see in experiments, these robustness guarantees indeed hold in practice given that the real-world problem settings often respect these regularity assumptions.

5 Experimental Evaluation

In this section, we perform empirical studies to validate the guarantees provided by our theorems, and to showcase that the data regularity assumptions we made in the previous section are satisfied in real-world problem settings.

Teaching task. We consider a binary image classification task for identifying animal species. This specific task has been studied extensively in the machine teaching literature (see [Singla et al., 2014; Chen et al., 2018a; Mac Aodha et al., 2018; Yeo et al., 2019]). First, we state the problem setup from the viewpoint of a teacher with full knowledge represented as (Q0, η, Z, h∗ , φ, H). Our problem setup is based on the task and dataset that is used in the works of [Singla et al., 2014; Yeo et al., 2019]. The task is to distinguish "moths" (- labeled class) from "butterflies" (+ labeled class). We have a total of |Z| = 160 labeled images, and the embedding of instances is shown in Figure 1c. We have |H| = 67 hypotheses, and a subset of these hypotheses along with h∗ are shown in Figure 1c.

We consider Q0 to be uniform distribution over H, η = 0.5, and have desired ϵ = 0.001.

Metrics and baselines. All the results corresponding to four different notions of imperfect teacher are shown in Figure 2, averaged over 10 runs. For performance metrics, we plot the eventual error of the learner and the size of the teaching set. In addition to OPTϵ (simply denoted as OPT in plots) and ˜ OPTϵ,∆ (simply denoted as ˜ OPT in plots), we also have three more baselines denoted as Rnd: 12 , Rnd:1, and Rnd: 32 . These three baselines correspond to teachers who select examples randomly, with set sizes being 12 , 1, and 32 times that of |OPT|.

Empirical results. We consider ∆Q0 -imperfect teacher with ∆Q0 = (δ, δ) (i.e., δ1 = δ2 = δ) with δ ∈ [0, 0.8]; results are shown in Figures 2a,2e. For ∆η-imperfect teacher, we vary δ ∈ [0, 0.4] considering a teacher who overestimates or underestimates the learning rate; results are shown in Figures 2b,2f. For ∆Z-imperfect teacher, we vary the fraction of instances X from 1 to 0.5 that we sample to construct ˜ Z, and sampling is done i.i.d.; the performance of this teacher is shown in Figures 2c,2g. For ∆φ-imperfect teacher, we computed noisy representation ˜ φ by adding a random vector in R2 of norm δ as noise to φ(x) ∀x ∈ X; results are shown in Figures 2d,2h. Note that in Figures 2d,2h, the norm δ is shown as a relative % shift w.r.t. data radius, where the radius is maxx∈X ||φ(x)||2 (see Figure 1c).

The results in these plots validate the performance guarantees that we proved in previous sections. It is important to note that for ∆Z-imperfect and ∆φ-imperfect teacher, any additional structural assumptions as were needed by Definitions 7,8 and Theorems 3,4 are naturally satisfied in real-world problem settings, as is evident in the performance plots.

6 Conclusions

We studied the problem of machine teaching when the teacher's knowledge is imperfect. We focused on understanding the robustness of a teacher who constructs teaching sets based on its imperfect knowledge. When having imperfect knowledge about the learner model, our results suggest that having a good estimate of the learning rate is a lot more important than the learner's prior knowledge. In terms of imperfect knowledge about the task specification, we introduced some regularity assumptions under which the teacher is robust. Our empirical experiments on a real-world teaching problem further validate our theoretical results. Our findings have important implications in designing teaching algorithms for real-world applications in education.