Teaching an Active Learner with Contrastive Examples

Abstract:
We study the problem of active learning with the added twist that the learner is assisted by a helpful teacher. We consider the following natural interaction protocol: At each round, the learner proposes a query asking for the label of an instance x , the teacher provides the requested label {x, y} along with explanatory information to guide the learning process. In this paper, we view this information in the form of an additional contrastive example ({x, y}) where x is picked from a set constrained by x (e.g., dissimilar instances with the same label). Our focus is to design a teaching algorithm that can provide an informative sequence of contrastive examples to the learner to speed up the learning process. We show that this leads to a challenging sequence optimization problem where the algorithm’s choices at a given round depend on the history of interactions. We investigate an efficient teaching algorithm that adaptively picks these contrastive examples. We derive strong performance guarantees for our algorithm based on two problem-dependent parameters and further show that for specific types of active learners (e.g., a generalized binary search learner), the proposed teaching algorithm exhibits strong approximation guarantees. Finally, we illustrate our bounds and demonstrate the effectiveness of our teaching framework via two numerical case studies.

heading: 1 Introduction
text: Active learning characterizes a natural learning paradigm where a learner actively engages in the learning process, and has demonstrated great success in both the educational domain [Prince, 2004] and the machine learning literature [Settles, 2012]. In the context of machine learning, active learning has traditionally been studied as the active instance labeling problem, where the goal of an active learner is to learn a concept by selectively querying the labels of a sequence of data points [Kosaraju et al., 1999; Dasgupta, 2004; Nowak, 2008; Balcan et al., 2006; Gonen et al., 2013; Hanneke and Yang, 2014; Yan and Zhang, 2017]. Recently, active learning has been investigated under richer interaction protocols, including learning from feature feedback [Poulis and Dasgupta, 2017; Dasgupta and Sabato, 2020] or from demonstrations [Chernova and Thomaz, 2014; Silver et al., 2012]. Typically, these works assume that the rich feedback obtained from the teacher is adversarial [Dasgupta and Sabato, 2020] or stochastic [Poulis and Dasgupta, 2017]. While these results have shown promising improvements in sample complexity by leveraging more expressive feedback, the assumptions of an adversarial or stochastic teacher could fall short in characterizing many real-world interactive learning systems (e.g. automated tutoring or multi-agent learning systems) where the teacher cooperates with the learner to achieve the learning objective [Zilles et al., 2011; Zhu et al., 2018].
Motivated by real-world cooperative learning and teaching scenarios [Chen et al., 2018a; Teso and Kersting, 2019], we consider an optimistic yet natural interaction protocol between an active learner and a helpful teacher (see Figure 1 (c)): At each round, the learner proposes a query asking for the label of an instance xq; the teacher then provides the requested label {xq, yq} along with explanatory
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
information to guide the learning process. In this paper, we consider this information in the form of an additional contrastive example ({xc, yc}) where xc is picked from a set constrained by xq (e.g., dissimilar instances with the same label, or similar instances with opposite labels). In contrast to existing work in active learning with contrastive examples [Abe et al., 2006; Liang et al., 2020; Ma et al., 2021] or with comparison queries [Jamieson and Nowak, 2011; Kane et al., 2017] which focus on developing active learning algorithms, we assume that the learner’s querying and learning strategy is fixed and known to the teacher, and focus on designing a teaching algorithm that can provide an informative sequence of contrastive examples to the learner to speed up the learning process.
Note that in the absence of the learner’s query, this problem reduces to the classical machine teaching problem [Goldman and Kearns, 1995]. When teaching a (passive) version space learner [Goldman and Kearns, 1995], classical machine teaching can be viewed as a set cover problem, and the greedy algorithm is known to compute a cover that is within a logarithmic factor of the minimum cover [Chvatal, 1979]. However, as we show in section 3.3, an active learner actively trying to reduce the label cost could actually hurt the performance of a greedy teacher.
Given an active version space learner specified by an acquisition function, we show that the design of an optimal teaching algorithm induces a challenging sequence optimization problem, where the teacher’s available choices of constrastive examples at a given round depend on the history of interactions. We study the greedy teacher that adaptively picks contrastive examples in response to the learner’s queries. Specifically, we introduce several natural problem-dependent parameters to characterize (1) the constraints imposed by the active learner and (2) the structure of the coverage function resulting from the hypothesis space. Based on these characterizations, we explore the theoretical properties for the greedy teacher, and demonstrate the power and limitations of the interactive teaching framework. Our main technical contributions are summarized are:
I. We consider a novel interactive protocol for teaching an active learner, and derive a general performance guarantee for the greedy teacher, regardless of the choice of acquisition function by the active learner. Our result generalizes existing near-optimality guarantees for the greedy teacher under the classical teaching [Goldman and Kearns, 1995] to the more challenging sequence optimization problem (section 3).
II. We then show that, perhaps surprisingly, a greedy teacher may fail badly when interacting with an active learner compared to the optimal teacher, due to the constrained choices of contrastive examples imposed by the learner’s query (section 3). In fact, there exist pessimistic scenarios where an active learner alone is better off without the help of a greedy teacher (section 4).
III. When interacting with a generalized binary search (GBS) learner [Dasgupta, 2004; Nowak, 2008], we provide a strong performance guarantee for the greedy teacher, and show that it cannot perform arbitrarily badly (section 4). Our bound establishes a rigorous connection between the problem-dependent parameters introduced in section 3 to the classical k-neighborly condition and coherence parameter which are widely used in the active learning literature [Nowak, 2008, 2011; Mussmann and Liang, 2018].
IV. We empirically illustrate our bounds via two experiments. These examples illustrate the intuitive sequential teaching process and demonstrate the effectiveness of our teaching framework.

heading: 1.1 Related Work
text: Teaching a sequential learner Machine teaching has shown significant development in the past two decades in both theoretical and practical domains. In a quest to achieve rich teacher-learner interactions, various different models for machine teaching have been proposed under the sequential teaching setting (e.g., local preference-based model for version space learners [Chen et al., 2018b], models for gradient learners [Liu et al., 2017, 2018; Kamalaruban et al., 2019], models inspired by control theory [Zhu, 2018; Lessard et al., 2019], models for sequential tasks [Cakmak and Lopes, 2012; Haug et al., 2018; Tschiatschek et al., 2019], and models for human-centered applications that require adaptivity [Singla et al., 2013; Hunziker et al., 2019]). Compared to our setting, in these works, the teacher is responsible for designing all of the learning data. Recently, Peltola et al. [2019] investigated the task of teaching sequential learners such as multi-armed bandits or active learners where the learners also pose query, but they formulate the problem as a variant of reward shaping, and allow the teacher to provide teaching examples that are inconsistent with the true data distribution. While our work falls into the category of teaching sequential learners, it could be viewed as a form of explanation-based machine teaching, and hence inherits different teaching constraints and objectives from the above settings.
Explanation-based teaching and learning Explanation-based teaching captures a rich class of teaching protocols where labels are coupled with additional information (such as highlighting regions or features on an image). Having an additional mode in the feedback allows the learner to perceive more intuitive explanations of the target hypothesis, and hence dramatically improves the learner’s ability to learn a new concept. Explanations were shown to be effective in helping a human student to improve classification performance by steering the student’s attention [Grant and Spivey, 2003; Roads et al., 2016; Chen et al., 2018a; Aodha et al., 2018]; likewise, they also play an important role in helping machine learners to efficiently learn some concept classes that would otherwise form intractable learning problems [Poulis and Dasgupta, 2017; Dasgupta and Sabato, 2020]. Our work is motivated by the success of explanation-based learning, and consider contrastive examples as a simple yet effective form of explanations. In comparison with existing work on explanation-based teaching, our work has an additional twist featured by the interaction with an active learner.
Submodular set and sequence optimization Our theoretical framework in section 3 is inspired by recent results on sequence submodular function maximization [Zhang et al., 2015; Tschiatschek et al., 2017; Hunziker et al., 2019]. In particular, Zhang et al. [2015] introduced the notion of string submodular functions, which, analogous to the classical notion of submodular set functions [Krause and Golovin, 2014], enjoy similar performance guarantees for maximization of deterministic sequence functions. Our setting has three key differences in that (1) we focus on a constrained planning problem where the set of available actions is dynamic (i.e. depending on the learner’s query), (2) our objective function no longer exhibits diminishing returns properties and (3) we consider a min-cost coverage problem as opposed to the budgeted maximization problem.

heading: 2 Active Learning with a Teacher: Problem Formulation
text: In this section, we formally introduce the new problem of active learning with a helpful teacher along with the corresponding interaction protocol. Then, we formulate the problem of teaching an active learner as a constrained sequential optimization problem. Throughout the entire paper, we use X to denote the ground set of unlabeled instances. We consider a finite class of hypothesisH, where each hypothesis h ∈ H is a binary classifier with its output being either +1 or −1 (i.e., h(x) ∈ {+1,−1}).

heading: 2.1 Learner-Teacher Interaction Protocol
text: We study the problem of teaching an active version space learner with a teacher. In contrast to the standard active learning protocol, our framework not only allows the learner to ask questions but also enables the teacher to provide additional explanatory information to guide the learning process. Specifically, we model the explanatory information using a contrastive example picked from a set constrained by the learner’s query (e.g., dissimilar instances with the same label, or similar instances with opposite labels). The full interaction protocol is presented in Protocol 1. At each round t, the learner asks a query xqt = q(x c 1:t−1, x q 1:t−1, H q t−1) with query function q conditioning on the received
Protocol 1 An interaction protocol between the teacher and the active learner
1: An active learner with a query function q; Initial version space Hq0 = H; Constraint function ξ for the contrastive example; Target hypothesis h?. 2: for t = 1, 2, 3, . . . do 3: learner asks a query xqt = q(x c 1:t−1, x q 1:t−1, H q t−1) 4: teacher provides the label yqt for the query x q t 5: teacher provides a contrastive example (xct, y c t ) from a constrained set ξ(x q t). 6: learner computes the updated version space Hqt . 7: if Hqt = {h?} then teaching process terminates.
contrastive examples (xc1:t−1) and version space H q t−1. Then the teacher returns the ground-truth label yqt for x q t and also provides a contrastive example (x c t, y c t). Under this setting, the version space at iteration t with teaching sequence xc1:t = {xci}ti=1, can be computed by (we omitted y for clarity)
Hqt = H q(xc1:t) = H \ ( t⋃ i=1 S(xqi ) ∪ S(x c i) ) , (1)
whereH is the initial version space of the active learner and S(x) = {h ∈ H|h(x) 6= h?(x)} denotes the hypotheses covered by x (i.e., the hypotheses that predict different labels on x than h?).

heading: 2.2 Optimization Objective
text: Our goal is to reduce the learner’s version space such that only h? (the target hypothesis) is left with minimal cost (e.g., # of interaction rounds or # of samples). The definition of cost can be problem-dependent. For the general case, we consider the following form of the cost function
Jq(xc1:t) = ∑t
i=1 c (xci) + c
( xqi ) , (2)
where xc1:t is the teaching sequence given by the teacher, and c : X → R+ computes the cost of the example. We don’t write the dependencies on the learner’s query sequence explicitly, as the queries are induced by the teaching sequence and the query function q accordingly.
Given the active learner, we seek the optimal teaching sequence that achieves minimal cost by solving the following optimization problem.
min X∈X?
Jq(X) s.t. Hq(X) = {h?} and xt ∈ ξ(xqt) ∀t ∈ [|X|] , (3)
where we use X ? to denote the set of all possible sequences of teaching examples, and [n] denotes all the integers in [1, n]. At every iteration, we can compute the constraint set by the function ξ : X → 2X given the learner’s query. Then, the teacher must select the contrastive example from the constrained set. This is a natural consideration, since without the constraint, the teacher might have selected some contrastive examples that are not interpretable to the learner. In practice, the constrained set could be the instances that are dissimilar to the learner’s query but with the same label or the instances that are similar to the learner’s query but with different label.
To be noted, since the order of the teaching sequence matters in our problem, it expands the search space exponentially. This makes solving the above sequence optimization problem far more difficult than solving the corresponding set optimization problem (e.g., classical machine teaching problem), which is NP-hard. Hence, we turn to approximation algorithms with polynomial time complexity.

heading: 3 Greedy Teaching Algorithm and Analysis: A General Complexity Bound
text: In this section, we propose a simple yet effective greedy algorithm for solving the sequential optimization problem defined in the last section. Then, we further provide theoretical results to upper and lower bound the number of rounds of the interaction between the learner and the teacher or the sample complexity, for the general cases (i.e., we don’t have any assumptions on the active learner).1
1All the proofs are deferred to the Appendix due to page limit.
Algorithm 2 Greedy teaching algorithm for active leaner
1: An active learner with a query function q; Initial version space Hq0 = H; Constraint function ξ for the contrastive example; Target hypothesis h?. 2: for t = 1, 2, 3, . . . do 3: learner asks a query xqt = q(x c 1:t−1, x q 1:t−1, H q t−1). 4: teacher provides the label yqt = h ?(xqt). 5: teacher provides a contrastive example xct = arg maxx∈ξ(xqt) ∆(x|x c 1:t−1, q,H) (equation 5). 6: Update learner’s version space by equation 1. 7: if Hqt = {h?} then teaching process terminates.

heading: 3.1 Analysis on the Optimal Teacher
text: To demonstrate the effectiveness of our framework, we first conduct an analysis on the relationship between the teaching dimension (OPTT), the optimal sample complexity for active learning (OPTAL), and the sample complexity for active learning with an optimal and unconstrained teacher (OPTT+AL).
First of all, it is not too hard to show that OPTT+AL ≤ OPTAL. This result can be proved by the fact that the optimal teacher cannot perform worse than such a teacher, which mimics the query selection strategy of the active learner. More importantly, this result also implies that the optimal teacher is always helpful for the active learner. In addition, by the following Lemma 1, we have that OPTT ≤ OPTT+AL ≤ 2 · OPTT, which lower and upper bounds OPTT+AL. Lemma 1. For any (X ,H) and active learner with query function q, we have OPTT ≤ OPTT+AL ≤ 2 · OPTT, where OPTT is the classic teaching complexity.
Lastly, to further understand the relationship between OPTT+AL and OPTAL, we borrow the results from Hanneke [2007]. As proved in Hanneke [2007], we have OPTT ≤ OPTAL ≤ log |H| · OPTT. Therefore, OPTAL can potentially be as large as log |H| · OPTT, while OPTT+AL is upper bounded by 2 · OPTT. This distinction shows that the gap between OPTT+AL and OPTAL can be arbitrarily large, hence demonstrates the advantage of incorporating the teacher in active learning. A visual illustration is provided in Figure 2. Throughout the entire paper, we use OPTT+AL to denote the sample complexity of active learning with an initial hypothesis classH, and an optimal and unconstrained teacher.

heading: 3.2 Greedy Teaching Policy
text: We now present a simple yet effective greedy teaching algorithm for teaching an active learner (see Algorithm 2). For clarity of presentation, we focus on unit cost case, i.e., c(x) = 1 for all x, which is equivalent to minimizing the number of rounds of interactions between the teacher and active learner. The extension to a more general cost will be discussed in the Appendix.
Therefore, to obtain the teaching sequence, we will solve the following minimum-cost cover problem
min X∈X?
|X| s.t. Hq(X) = {h?} and xt ∈ ξ(xqt) ∀t ∈ [|X|]. (4)
For iteration t+ 1 with teaching history xc1:t, we define the marginal gain as the following
∆(xc|xc1:t, q,H) = f(xc1:t ⊕ xc|q,H)− f(xc1:t|q,H) = |Hq(xc1:t) \Hq(xc1:t ⊕ xc)|, (5)
where f(x1:t|q,H) = |H \Hq(x1:t)| is the number of hypotheses removed from the version by the teaching examples x1:t together with the corresponding learner’s queries (defined by equation 1), and
⊕ denotes the concatenation between two sequences. To be noted, when the function f is maximized, it is equivalent to that only the target hypothesis h? is left in the version space.
For the greedy teaching algorithm, as described in Algorithm 2, at each round, it selects the contrastive example from the constrained set that maximizes the marginal gain defined in equation 5. Such process will be repeated until the function f is maximized or the budget is used up.

heading: 3.3 Theoretical Guarantees for Greedy Teaching Policy
text: We now turn to analyzing the theoretical performance of the greedy algorithm. In general, for active learning, there is no guarantee for the sample complexity of arbitrary learners, and sometimes, the worst case complexity can be up to O(|H|) [Dasgupta, 2004], which is uninformative. To understand the role of the greedy teacher in active learning, we rely on the following two properties of the objective function f . These two properties are usually used in the characterizing the submodularity or string submodularity of a function [Zhang et al., 2015; Hunziker et al., 2019]. Definition 1 (Pointwise submodularity ratio). For any sequence function f , the pointwise submodularity ratio with respect to any sequences σ, σ′ and query function q and hypothesis class H is defined as
ρH(σ, σ ′, q) = min
x∈X ∆(x|σ, q,H) ∆(x|σ ⊕ σ′, q,H) . (6)
Definition 2 (Pointwise backward curvature). For any sequence function f , the pointwise backward curvature with respect to any sequences σ, σ′ and query function q and hypothesis class H is defined as
γH(σ, σ ′, q) = 1− f(σ ′ ⊕ σ|q,H)− f(σ|q,H) f(σ′|q,H)− f(∅|q,H) . (7)
The submodularity ratio measures the degree of diminishing returns of the underlying sequence function by computing the ratio between the marginal gains. When the sequence function f is string/sequence submodular [Zhang et al., 2015; Alaei et al., 2010], the minimum pointwise submodularity ratio over all possible sequences is 1. By contrast, the pointwise backward curvature measures the degree of diminishing returns of the difference between marginal gains. For postfix monotone sequence functions, the pointwise backward curvature is no greater than 1 [Zhang et al., 2015].
In addition, at each round, the teacher can only select examples from a constrained set, which limits its power. To accommodate such limitations, we can view the teacher as an α-approximate greedy teacher in the analysis. The parameter α characterizes the ratio between the marginal gain of an unconstrained greedy teacher and that of the constrained greedy teacher. For an active learner with query function q, constraint ξ, and version space Hq0 = H, we can compute the corresponding α by
α = max t maxx∈X ∆(x|xc1:t−1, q,H) maxx∈ξ(xqt) ∆(x|x c 1:t−1, q,H) . (8)
In general, the parameter α measures how strict the constraint is. When α becomes large, the effectiveness of the greedy teacher will correspondingly decrease.
The following theorem summarizes our first theoretical result, which provides a problem-dependent upper bound for the sample complexity of greedy teaching algorithms. Theorem 1. The sample complexity of the α-approximate greedy algorithm for any active learner with a initial hypothesis classH is at most(
α · O (log |H| · log (|H|/γg)) ρgγg log(γg/(γg − 1)) + α · O (log (|H|/γg)) ρgγg
) · OPTT+AL, (9)
where γg = maxH∈H′ γ g H and ρ g = minH∈H′ ρ g H with
γgH = max i≥1 γH(σ H , xH1:i, q), ρ g H = min i,j≥0 ρH(x H 1:i, σ H 1:j , q), (10)
which are computed with respect to the greedy teaching sequence xH and the optimal teaching sequence σH for the corresponding active learner with a initial hypothesis class H ∈ H′ = {Hq(X)|X ∈ X ? ∧ |Hq(X)| ≥ 2} and query function q.
Remark 1. For any active learner, 1 ≤ γg ≤ |H| − 1 and ρg ≤ 1. When γ → 1, the l.h.s. term in the parentheses of equation 4 will vanish. When γg → |H| − 1, the r.h.s. term will vanish.
Theorem 1 bounds the worst case sample complexity of greedy teaching algorithms. To be noted, both γg and ρg are computed with respect to the greedy teaching sequence and the optimal teaching sequence for the active learner with some initial hypothesis class H ⊆ H, rather than two arbitrary sequences. Therefore, based on Remark 1 and Zhang et al. [2015], if the objective function is postfix monotone, then we will have γg = 1, otherwise, we can only conclude that γg ≥ 1. In particular, when γg → 1, the r.h.s. term in equation 4 will dominate, whereas when γg → |H|−1, the l.h.s. term will become dominating. Informally, γg can be a measure of the difficulty of the underlying sequence optimization problem, and a larger γg will be likely to imply that the problem is more difficult. In what follows, we further argue that the linear dependency on α cannot be avoided, showing that Theorem 1 is non-vacuous. Theorem 2. There exists a constraint function ξ, version space H and active learner with query function q, such that the sample complexity of the greedy teacher is at least Ω( √ |H|) · OPTT+AL.
Theorem 2 shows that the linear dependency on α cannot be improved when without any assumptions on the constraint function ξ, hypotheses space and the active learner. To porve Theorem 2, we constructed a special case, detailed in the Appendix. In the example, the optimal teacher only uses a constant number of examples to teach the active learner, while the greedy teacher needs to provide all the examples, whose number is of the order Ω( √ |H|).

heading: 4 Teaching Greedy Active Learners
text: In this section, we consider the problem of teaching a greedy active learner, concretely, the Generalized Binary Search (GBS) [Nowak, 2008], which selects the query in a greedy manner (i.e., the one that maximizes the utility). At each iteration t + 1 with the version space Ht, the GBS learner selects the query according to the expected number of hypotheses that can be covered by the query (i.e., the utility of the query). Specifically, for binary classification problem, for each query x, the utility can be computed as
u(x|Ht) = 2
|Ht| · (∑ h∈Ht 1[h(x) = −1] ) · (∑ h∈Ht 1[h(x) = 1] ) . (11)
The above utility function measures how discriminative the selected query is. GBS selects the query that maximizes the utility, and hence it lower bounds the minimal number of hypotheses to be removed after the query. As pointed out in Dasgupta [2004], the worst case sample complexity for the GBS learner is O(|H|). However, for practical problems, there are usually some structures in the hypotheses space and the sample space we can exploit to get a tighter bound. Specifically, we consider problems with the k-neighborly structure [Nowak, 2008; Mussmann and Liang, 2018]. Definition 3 (k-neighborly). Consider the graph (V,E) with vertex set V = X , and edge set E = {(x, x′)|dH(x, x′) ≤ k, ∀ x, x′ ∈ X}, where dH(x, x′) = |{h|h ∈ H and h(x) 6= h(x′)}|. The query and hypotheses space (X ,H) is k-neighborly if the induced graph is connected.
Intuitively, the k-neighborly structure ensures that for any two points x, x′ ∈ X , there is a path formed by similar pairs connecting them. With such structures, Nowak [2011] further introduces the coherence parameter, which plays an important role in bounding the worst case complexity of GBS. Definition 4 (Coherence parameter). The coherence parameter for (X ,H) is defined as
c?(X ,H) := min P max h∈H ∣∣∣∣∣∑ x∈X h(x)dP (x) ∣∣∣∣∣ , (12) where we minimize over all possible distributions on X .
The coherence parameter c? measures how evenly the query selected by GBS bisects the hypotheses. With the above assumptions, Nowak [2008] shows that the sample complexity of GBS can be upper bounded by O(log(|H|)/ log(1/η)), where η = max{(1 + c?)/2, (k + 1)/(k + 2)}. This implies that, the smaller c? and k, the more efficient GBS is.
Next, we seek to understand the sample complexity when pairing GBS with a greedy teacher. Can we also upper bound its sample complexity, even though the interaction between the learner and the teacher introduces extra complexity? The result is summarized in the following theorem. Theorem 3. For the GBS learner with a initial hypothesis class H and ground set X , if (X ,H) is k-neighborly and with coherence parameter c?, then the sample complexity of the greedy teaching algorithm with any constraint function ξ is at most
α · O ( log2(|H|) ) · OPTT+AL, (13)
where = min {(1− c?)/(1 + c?), c?/(k − c?)}, and α ≤ max{k/c?, 2/(1− c?)}.
Theorem 3 gives a near-optimal bound for the greedy teaching algorithm for GBS learners, which guarantees that its performance cannot be arbitrarily bad. However, the bound cannot be directly compared to that of GBS alone, as we don’t know OPTT+AL. Unfortunately, our following remark shows that the sample complexity of GBS with a greedy teacher is not guaranteed to be smaller compared to GBS alone, and for some extreme cases, it can be even larger. Remark 2. The sample complexity of GBS with greedy teacher (even without the constraints) is not guaranteed to be smaller than that of GBS alone.
The bad news from Remark 2 shows that the greedy teacher may not be satisfactory for teaching a GBS learner under some circumstances, though the greedy teaching algorithm performs very well in classic machine teaching problems. For a better understanding of the failure of greedy teachers, we provide a realizable example (see Appendix), where the GBS with a greedy teacher will requires more samples than that of GBS alone. We hope that this example can motivate improved teaching algorithms for active learners, beyond the greedy heuristics.

heading: 5 Numerical Experiments
text: In this section, we empirically evaluate the greedy teaching algorithm with β-greedy active learners (a rich class of active learners including GBS) in a simulated environment. We seek to understand how the type of active learner (i.e., varying β) and the constraint on contrastive examples affect the performance of the greedy teacher. To dig deeper, we further demonstrate how these two factors affect the value of α and ρg , which plays an important role in our theoretical results.

heading: 5.1 Experimental Setup
text: β-greedy active learners: In the experiments, we consider the class of β-greedy active learners, for which the selected query xqt+1 satisfies
u(xqt+1|Ht) ≥ 1
β ·max x∈X u(x|Ht). (14)
We can interpolate β from 1 to +∞ to cover a broad range of active learners with different properties. Specifically, when β = 1, we recover the GBS active learner, whereas, when β = +∞, we recover the random active leaner. In general, as β increases, the strategy becomes less greedy. For the β-greedy active leaner, the query function q returns a query that satisfies inequality (14).
Datasets: We conducted experiments on two datasets: Vespula-Weevil and Butterfly-Moth, which were adopted by Singla et al. [2013, 2014] for verifying the algorithm for teaching the crowd to classify images. Specifically, Vespula-Weevil is a synthesized dataset with 200 images, which are generated by sampling 2-d features from two bi-variate Gaussian distributions. The dataset Butterfly-Moth consists of 160 real images with the two categories Butterfly and Moth. The 2-d embedding of each image is inferred from the annotation process using a generative Bayesian model proposed in Welinder et al. [2010]. More details about the datasets can be found in the Appendix.
Hypothesis space: Following Singla et al. [2014], for the Vespula-Weevil dataset, we generate the hypotheses by randomly sampling from eight multivariate Gaussian distributions, with mean µi = [π/4 · i, 0], and covariance Σi = [2, 0; 0, 5e−3], where i is varying from 0 to 7. For the Butterfly-Moth dataset, the hypotheses are inferred from the annotation process with the same generative Bayesian model for inferring the 2-d embedding.

heading: 5.2 Effects of Active Learners and Constraints
text: We first study how does the active learner (AL) affects the teaching performance under different constraints. Specifically, we vary β in [1, 5, 10, 100, 1, 000] to model different learners. In terms of the constraint on the teacher’s example, we consider the following three types of the constraints: 1) examples that are close to the learner’s query but with different label (denoted by C); 2) examples that are far away from the learner’s query but with the same label(denoted by F); 3) the union of 1)& 2) (denoted by C+F). For each constraint, we also adopt a parameter ψ ∈ [0, 1] to control the size of the search space (i.e., the closest or furthest ψ portion of the points with different or the same label as the query). We also include the unconstrained teacher, which can freely select examples.
To obtain more robust results, we iterate through all the hypotheses to serve as the target hypothesis once, and compute the averaged cost for identifying the target hypothesis, accompanied by the standard error. The results are presented in Figure 3. We observe that for both datasets, AL with greedy teacher (AL-GT, unconstrained) always achieves the best performance in terms the average cost. When β becomes larger, the average cost of AL-GT increase very slightly. For the others, when ψ is small, they usually perform worse than AL along. This is because when ψ is small, the candidate points in the constrained set are too restrictive and they are usually redundant to the query, making the contrastive example uninformative. By contrast, when ψ is large enough, AL-GT(C+F) can significantly outperform AL alone, showing that the teacher is helpful in this case. In summary, when β becomes large and the constraint is not too strict, the teacher will be more helpful (i.e., the gap between AL and AL with teacher becomes larger).
We further study how the constraints and β affect the parameters α. The results are provided in Figure 4. In general, we can observe that as the constraints become stricter (i.e., ψ becomes smaller),
α will correspondingly increase as well as the cost for teaching the active learner. This is consistent with our Theorem 1 and Theorem 3 in Section 3 and Section 4. In addition, when β becomes larger, α is also increasing, which is consistent with the trend in the cost plots (top row in Figure 4). Besides, we also compute the empirical values of ρg , finding that for different β and constraints, ρg stays very close to 1. According to our theoretical bounds, this may also explain why the trends in the cost plots are mostly consistent with those in the plots of α (bottom row in Figure 4).

heading: 5.3 Visualization of the Teaching Sequence
text: Lastly, we visualize a teaching sequence of AL-GT(C+F) in Figure 5. The results are obtained with β = 1 and ψ = 0.5 on the Vespula-Weevil dataset. The first and third examples are the learner’s queries and the second and fourth ones are the teacher’s provided contrastive examples. In general, weevils have relatively short heads with similar color to the body. In contrast, vespula have big and contrasting heads. From Figure 5, we can observe that at the first round, the teacher selects an image of vespula with similar body size to the learner’s query, but with a head that is in relatively larger and of different color. This highlights the key features (i.e., the color and size of the head) to distinguishing weevil and vespula. Subsequently, the teacher provides another image of weevil which is visually very different from the query in terms the size of body and head, but is in the same category.

heading: 6 Conclusion
text: We introduced a novel interactive protocol for teaching an active leaner. We first derived a general performance guarantee for the greedy teacher with arbitrary active learners, and then provided a stronger performance bound for teaching GBS learners with a greedy teacher under mild assumptions. In addition, we also demonstrated the limitations of greedy teachers by showing that 1) the performance of the greedy teacher can be arbitrarily worse than that of the optimal teacher due to the constrained choices of contrastive examples; and 2) the greedy teaching strategy for the GBS learner is not guaranteed to be better than GBS alone. Lastly, we provided empirical results to demonstrate the effectiveness and limitations of the greedy teachers. We believe that our results have taken a significant step in bringing active learning and machine teaching closer to real-world settings in which the teacher collaborates with the learner to achieve the learning goal.

heading: 7 Social Impact
text: In this work, we provided an greedy teaching algorithm for active learners with theoretical guarantees. Our algorithm is derived for teaching an active leaner in a collaborative setting to achieve some learning goal, which can be potentially helpful for improving many real-world interactive learning systems, e.g., automated tutoring or multi-agent learning system.
However, just as a coin has two sides, our algorithm can be easily extended to poisoning the active learner by change the objective of the teacher. This can potentially threaten the safety of deploying machine learning models in online products.
Acknowledgments and Disclosure of Funding
We thank Sandra Zilles for the helpful discussion and valuable feedback. This work is supported in part by NSF IIS-2040989 , and a C3.ai DTI Research Award 049755.

Review summaries:
The paper proposes a teaching algorithm that uses contrastive examples to teach an active learner. Some performance guarantees are given for some special cases. Some empirical evidences are presented to support the results.