# One-shot Machine Teaching: Cost Very Few Examples to Converge Faster

Chen Zhang<EMAIL_ADDRESS>Xiaofeng Cao<EMAIL_ADDRESS>Yi
Chang<EMAIL_ADDRESS>Ivor W Tsang<EMAIL_ADDRESS>
###### Abstract

Artificial intelligence is to teach machines to take actions like humans. To
achieve intelligent teaching, the machine learning community becomes to think
about a promising topic named machine teaching where the teacher is to design
the optimal (usually minimal) teaching set given a target model and a specific
learner. However, previous works usually require numerous teaching examples
along with large iterations to guide learners to converge, which is costly. In
this paper, we consider a more intelligent teaching paradigm named one-shot
machine teaching which costs fewer examples to converge faster. Different from
typical teaching, this advanced paradigm establishes a tractable mapping from
the teaching set to the model parameter. Theoretically, we prove that this
mapping is surjective, which serves to an existence guarantee of the optimal
teaching set. Then, relying on the surjective mapping from the teaching set to
the parameter, we develop a design strategy of the optimal teaching set under
appropriate settings, of which two popular efficiency metrics, teaching
dimension and iterative teaching dimension are one. Extensive experiments
verify the efficiency of our strategy and further demonstrate the intelligence
of this new teaching paradigm.

###### keywords:

Machine teaching , New teaching paradigm , One-shot teaching , Converge ,
Mapping , Teaching dimension

††journal: Artificial Intelligence

##  1 Introduction

Artificial intelligence [1, 2, 3, 4] is to teach machines to be equipped with
the ability including understanding, synthesizing, and inferring like humans.
To achieve such intelligent teaching [5, 6, 7], the machine learning community
follows the human teaching paradigm to ponder an inverse problem to machine
learning, which is termed as machine teaching (MT) [8, 9]: searching the
optimal (usually minimal) teaching set111Teacher collects a set of teaching
examples to supervise the training of learner, and the teaching set is a
training set for learner. given a target model and a specific learner. In real
world, MT as an intelligent paradigm has benefits in a wide variety of
applications, e.g., crowd sourcing [10, 11], transfer learning [12], education
and personnel training of human [13, 8] and cyber-security [14, 15, 16].

Considering the interaction fashion between teachers and learners, MT is
studied from either traditional [17, 18] or iterative [19] paradigms.
Regarding learners to be non-gradient-based, traditional teachers invoke batch
sampling with prior knowledge on the underlying parameter distribution [18, 8,
20], then give a teaching set to learners without further communication (leave
training to learners own). It can be analogous to a real-world case that a
zoologist only provides several representative animal images for a student
once to teach how to distinguish the cheetah from the cat, and there is not
following interaction between them. The minimal count of provided images is
called teaching dimension [21]. Differently, capturing the iterative manner of
model training [19], iterative teachers sequentially feed teaching sets to
gradient-based learners, which is more applicable particularly in large-scale
scenarios [22] as it produces a concrete and practicable iterative algorithm
(teaching strategy). Recall the animal recognition instance, an iterative
zoologist would provide images in rounds based on current mastery degree of
learners. The number of rounds is called iterative teaching dimension [19].

However, contemporary strategies require large iterations as well as numerous
examples. This is far from one ultimate goal of MT from a perspective of
teaching cost, one-shot iteration: takes one, or a few examples for one-
iteration convergence [23, 24]. Besides, this objective is also the
requirement of high efficiency and low costs for diverse artificial
intelligence applications, e.g., autonomous driving [25, 26, 27] and smart
robots [28, 29], and serves as a stepping stone towards applying MT in more
fields, e.g., few/one-shot learning [30, 31] and imitation learning [32].

Figure 1: Machine teaching for a binary classification task. Traditional
teacher feeds teaching sets to the learner unilaterally without further
interaction; iterative teacher provides teaching sets iteratively and requires
large iterations; one-shot teacher only provides a singleton to help learner
converge within one iteration.

To achieve that goal, we propose a new paradigm named one-shot machine
teaching, which requires the optimal teaching set to be a singleton that can
guide learners to converge after one iteration. A brief comparison among three
paradigms is in Figure 1. This advanced paradigm establishes a mapping [33,
34] from the teaching set to the model parameter, which allows us to analyze
the essential relation between teaching sets and model parameters. Further, we
theoretically prove that this mapping is surjective [35], which indicates
there exists a singleton (i.e., the optimal teaching set) such that the target
model can be learnt after one iteration (mapping once). Then, relying on the
surjective mapping from teaching sets to model parameters, we present a
strategy called one-shot teaching strategy to solve for the optimal teaching
set, of which teaching dimension and iterative teaching dimension are one. By
exploring chain expansion of gradient across examples and parameters [36], our
strategy analytically derives a canonical singleton as the optimal teaching
set [37] under proper settings and tells the construction approach for
teachers with different teaching set candidates (a.k.a. the knowledge domain).
We eventually verify efficiency of our strategy with extensive experiments,
which demonstrates the intelligence of one-shot machine teaching.

To summarize, the contributions of this work are as follows.

  * •

We study a new paradigm named One-shot Machine Teaching (OSMT), which is to
search a singleton to achieve one ultimate goal of machine teaching: taking
fewer examples to aggressively converge within one iteration. OSMT establishes
a mapping proved to be surjective from teaching sets to model parameters,
which brings convenience to analyze the fundamental relation between teaching
sets and model parameters.

  * •

We provide a solution called One-shot Teaching Strategy (OSTS) to design the
optimal teaching set for different teachers under proper settings.
Specifically, with surjective mapping from teaching sets to model parameters,
OSTS exploits chain expansion of gradients and analytically derives a
canonical singleton as the optimal teaching set, of which teaching dimension
and iterative teaching dimension are one.

  * •

We empirically validate the efficiency of OSTS: costs few examples and achieve
one-iteration convergence. This demonstrates the fascinating evidence that
intelligent one-shot machine teaching can strikingly improve the efficiency of
teaching.

##  2 Related Works

This paper is closely related to Machine Teaching (MT) especially Iterative
Machine Teaching [19]. We review the development of MT including traditional
and iterative paradigms, and we situate this work in it. Besides, we also
discuss the connection and difference between this work and some relevant one-
shot machine learning works as they mention the same terminology, one-shot.

###  2.1 Machine teaching

As Rivest and Yin [6] pointed that being taught is faster than learning, MT
considers an inverse problem to machine learning by following the human
teaching paradigm. The promising application value of MT has been verified
over diverse domains including human education [38, 39], cyber security [40,
14, 41] and human-machine interaction [42, 43, 7, 44, 45], reinforcement
learning [46, 47].

Traditional paradigms [48, 17, 49, 18] towards lower teaching cost began an
early exploration where teachers are assumed to unilaterally convey teaching
sets once (without further communication) and know the underlying parameter
distribution and feature space. The most popular quantity of teaching cost is
the teaching dimension [21] which characterizes the size of the teaching set.
Meanwhile, Zilles et al. [50, 51] and Chen et al. [52] analyze the machine
teaching problem in a theoretical sight as well. Moreover, Balbach and
Zeugmann [53] summarize developments in the algorithmic teaching, and Zhu [8]
presents a general teaching framework closely connecting to curriculum
learning [54, 38, 55] and knowledge distillation [56]. The most related work
in the traditional paradigm of this paper is Liu et al. [20]. It discusses the
teaching dimension of linear learners, but is not aware of the iterative
interaction between teachers and learners, or produces a practical iterative
teaching strategy, or considers pool-based teachers, all of which are
considered in this work. Besides, Theorem 8 in this paper shows that we touch
a tighter bound of teaching dimension.

Differently, capturing the iterative fashion of model training [19], iterative
paradigms explore towards one-shot iteration further, in which teachers feed
teaching sets to gradient-based learners step by step. The teaching cost is
quantified by iterative teaching dimension [19]. This type of paradigm is more
practicable in complicated (e.g., large-scale) tasks [22] as it introduces an
iterative algorithm (teaching strategy) to simplify and solve problems
gradually [57]. Besides, Liu et al. [58] propose cross-space teaching towards
black-box [59] scenarios, and Cicalese et al. [60] focus on weaker black-box
learners and provide their insight into limited information teaching. At the
meantime, Hunziker et al. [61] and Dasgupta et al. [62] study the forgetful
case. Moreover, Zhou et al. [63] use iterative machine teaching to analyze
crowd teaching with imperfect labels, and Mosqueira-Rey et al. [64] apply the
combination of iterative machine teaching and active learning in machine
learning loop, which implies the close relation between iterative machine
teaching and active learning [65]. There has been a recent growth of interest
in iterative paradigms, which covers diverse fields including end-to-end
teaching [66], inverse reinforcement learning [67], text classification [68],
Internet-of-Things [22], human-robot interaction [69, 70, 71, 72], computer
vision [73, 74]. Compared with contemporary iterative works, our intelligent
one-shot paradigm dramatically cuts down the teaching cost (lower iterative
teaching dimension) and achieves one-shot iteration.

###  2.2 One-shot machine learning

One-shot learning attempts to train models from a limited number of examples
[75, 24, 76], motivated by a human learning ability (learn new concepts with
very few instances). Many works attempt to solve this challenge from diverse
directions including encoder training [77, 78] and example generation [79, 75,
80].

The encoder training methods [81, 82] attempt to train an encoder such that it
can thoroughly learn the inside characters and structures of each example.
Some works [77, 78] may call such encoder training as teaching. Specifically,
teaching in [77] is to train a Bidirectional Long Short Term Memory encoder,
and Bajracharya et al. [78] let human use virtual reality to take some actions
for training the encoder inside robots such that robots can reproduce these
behaviors. Essential, such encoder training is to search the optimal parameter
of encoders based on the training set with limited volume, which is a typical
optimal model parameter searching (i.e., machine learning) procedure [83]. In
contrast, MT is to find the optimal teaching set based on a target model,
which is an inverse procedure of machine learning [8]. As a teaching paradigm,
proposed OSMT is to search the optimal teaching set with smaller cardinality
such that learners can converge after one-iteration training.

The generative approaches [84, 85] attempt to enrich training sets based on
very fewer available examples to meet the training requirement of modern
models especially deep neural networks. Rezende et al. [79] develop a machine
learning systems to generate new examples such that there is not significant
difference between generated and existent examples. Vinyals et al. [75] share
the similar idea as augmentation, which attempts to map a small labeled
support set and an unlabeled example to its labels. Besides, Tjandra et al.
[80] combine Tacotron with DeepSpeaker to generate speeches from different
speakers. However, whether each generated example is helpful for the
convergence of a model is not discussed. Differently, OSTS with the prior
knowledge of $\theta^{*}$ (usually come from the pretrained model or expert
experience) generates examples such that they can help learners converge after
one iteration, which can be viewed as an inverse procedure of one-shot machine
learning [8]. Fundamentally, the difference comes from different settings
between machine learning and machine teaching [9]. Besides, the purpose of
generation (e.g., linear combination and scaling) in OSTS for pool-based
teachers is for the necessity of synthetic examples [23, 37] rather than
similarity between synthetic and existing examples.

##  3 Preliminaries

###  3.1 Notations

Let $\mathcal{X}\subseteq\mathbb{R}^{n}$ be a $n$ dimensional example (a.k.a.
feature and input) space and
$\mathcal{Y}\subseteq\mathbb{R}\,(\text{Regression})\,\text{or}\,\mathcal{Y}=\left\\{-1,1\right\\}(\text{Classification})$
be a label (a.k.a. output) space. The standard basis of $\mathbb{R}^{n}$ is
denoted as $\\{e_{i}|1\leq i\leq n\\}$ where $e_{i}$ means the vector with a 1
in the $i^{\text{th}}$ coordinate and 0’s elsewhere. A teaching example (could
be abbreviated as example) is a pair $(x,y)\in\mathcal{X}\times\mathcal{Y}$.
The optimal teaching example is $(x^{*},y^{*})$. A size $k$ teaching set is
defined as
$\mathcal{D}=\\{(x_{1},y_{1}),\dots(x_{k},y_{k})\\}=\\{(x_{i},y_{i})\\}_{i=1}^{k}$
with replacement and $\\{(x_{i},y_{i})\\}_{i=1}^{0}\coloneqq\emptyset$. The
optimal one is $\mathcal{D}^{*}$. We omit the set symbol $\\{\cdot\\}$ for
convenience if $\mathcal{D}$ is a singleton. The collection of teaching set
candidates is denoted by $\mathbb{D}\ni\mathcal{D}$, which is also called
knowledge domains of teachers [19]. Parameter is denoted by
$\theta\in\Theta\subseteq\mathbb{R}^{n}$, and optimal and initial parameters
are $\theta^{*}$ and $\theta^{0}$, respectively. A model is a mapping
$f(x,\theta):\mathcal{X}\times\Theta\to\mathcal{Y}$ assumed to be identified
by its parameter. In this paper, we are mainly concerned with models of linear
family $f(\theta,x)=\langle\theta,x\rangle$ (i.e., allow inner product
$\langle\cdot,\cdot\rangle$ defined in Euclidean vector space across
$\mathcal{X}$ and $\Theta$ since they essentially are the subspace of the
Euclidean vector space), and connect it with the generalized linear model [86]
by the typical convex loss function $\ell(f,y)$ (e.g., square, logistic and
hinge loss). The result of this paper can be generalized to the reproducing
kernel Hilbert space $\mathcal{H}$ equipped with
$\langle\cdot,\cdot\rangle_{\mathcal{H}}$ by kernel methods [87, 88].

###  3.2 Machine teaching

Machine teaching considers the selection of teaching set for learners such
that the model parameter $\theta^{*}$ can be learnt with fewer teaching
examples, and teachers are only allowed to teach via examples rather than
parameter clone directly [8]. It has been framed into a bilevel optimization
over $\mathbb{D}$ [9]:

$\displaystyle\begin{aligned}
&\mathcal{D}^{*}=\underset{\mathcal{D}\in\mathbb{D}}{\arg\min}\quad\mathcal{B}(\hat{\theta},\theta^{*})+\tau\mathcal{C}(\mathcal{D})\\\
&\text{s.t.}\quad\hat{\theta}=\textbf{ML}(\mathcal{D})\end{aligned},$ (1)

where $\mathcal{B}(\cdot,\theta^{*})$ is a class of distance (e.g., L-2 norm
$\mathcal{B}(\hat{\theta},\theta^{*})=\|\hat{\theta}-\theta^{*}\|_{2}$)
measuring the learner bias w.r.t. $\theta^{*}$, $\mathcal{C}(\cdot)$ is the
teaching cost (e.g.,
$\mathcal{C}(\mathcal{D})=\left\|\mathcal{D}\right\|_{0}\geq 1$ with
cardinality operator $\left\|\cdot\right\|_{0}$) regularized by a constant
$\tau$, and ML represents the model training (i.e., machine learning)
procedure of learners. With prior knowledge about $\theta^{*}$, the
traditional and iterative paradigms are provably more efficient than machine
learning. However, from a perspective of teaching cost, one-shot iteration
(taking a smaller teaching set $\mathcal{D}\in\mathbb{D}$ for converging to
$\theta^{*}$ within one iteration) is still under exploration even tradition
and iterative paradigms have made great progress towards it.

###  3.3 Traditional paradigms

Figure 2: 1D and 3D cases of constructing $\mathcal{D}^{*}$ under traditional
paradigms. $\theta^{*}$ is the midpoint of line segment $x_{-}x_{+}$ in 1D,
and vertically bisects $x_{-}x_{+}$ in 3D case.

Traditional paradigms where teachers only provide a teaching set without
additional interaction with learners explore one-shot iteration via batch
sampling with solid prior knowledge including concrete $\theta^{*}$, example
distributions and feature spaces. Considering a 1D threshold classifier
teaching, given $\theta^{*}\in\Theta=\mathbb{R}$ over uniform distribution,
and 1D feature space $\mathcal{X}=\mathbb{R}$, teachers pick two teaching
examples whose feature vectors satisfy [9]

$\frac{x_{-}+x_{+}}{2}=\theta^{*}$

with the negative $x_{-}$ and the positive $x_{+}$. Analogously, when teaching
a hard-margin support vector machine (SVM) of homogeneous version in high-
dimensional space, e.g., 3D cases, let $\theta^{*}=(a^{*},b^{*},c^{*})^{T}$,
teachers pick $x_{+}=(a_{+},b_{+},c_{+})^{T}$ and
$x_{-}=(a_{-},b_{-},c_{-})^{T}$ satisfying that vector $x_{+}-x_{-}$ is
orthogonal to hyperplane corresponding to $\theta^{*}$, and the distance
between $x_{+}$ and $\theta^{*}$ is the same as that between $x_{-}$ and
$\theta^{*}$ [9], which can be expressed as

$\displaystyle\begin{aligned}
\left\\{\begin{array}[]{lr}a^{*}(a_{+}-a_{-})+b^{*}(b_{+}-b_{-})+c^{*}(c_{+}-c_{-})=0\\\
\frac{a^{*}a_{+}+b^{*}b_{+}+c^{*}c_{+}}{\sqrt{{a^{*}}^{2}+{b^{*}}^{2}+{c^{*}}^{2}}}=-\frac{a^{*}a_{-}+b^{*}b_{-}+c^{*}c_{-}}{\sqrt{{a^{*}}^{2}+{b^{*}}^{2}+{c^{*}}^{2}}}\end{array}\right.\end{aligned}.$

Above instances are visualized in Figure 2.

###  3.4 Iterative paradigms

In contrast, iterative paradigms only requires concrete $\theta^{*}$ to
construct $\mathcal{D}^{*}$ via iteratively searching. With such weaker
requirement and iterative manner, these type of paradigms are more practicable
especially when it is computationally infeasible to train over the entire
dataset [22]. Generally, the iterative paradigm constructs $\mathcal{D}^{*}$
with focus on a specified algorithm in training procedures of learners [57].
In more detail, it considers $\hat{\theta}=\textbf{ML}(\mathcal{D})$ as

$\hat{\theta}=\arg\underset{\theta\in\Theta}{\min}\mathbb{E}_{(x,y)\sim\mathbb{P}(x,y)}\left[\ell(f(x,\theta),y)\right],$
(2)

whose parameter is specifically learnt by mini-batch gradient descent
algorithm [89, 19]:

$\theta^{t+1}\leftarrow\theta^{t}-\frac{\eta^{t}}{k}\sum_{i=1}^{k}\nabla_{\theta}\ell\left(f(\theta^{t},x^{t}_{i}),y^{t}_{i}\right),$
(3)

where $t=0,1,\dots,T$ is the iteration number, $\eta^{t}>0$ is learning rate
(a small constant), $k\geq 1$ is the batch size, $x^{t}_{i}$ denotes the
$i^{\text{th}}$ example features at the $t^{\text{th}}$ iteration
corresponding to label $y^{t}_{i}$ and $\ell(\cdot,\cdot)$ is the convex loss
function. For succinctness, Eq.(3) can be rewritten as

$\theta^{t+1}\leftarrow\theta^{t}-\eta^{t}\mathcal{G}(\theta^{t};\mathcal{D}^{t}|\ell;f),$
(4)

where $\mathcal{G}(\cdot|\ell;f)$ denotes the gradient function when the
family of both loss $\ell$ and model $f$ are given.

Specifically, we are concerned with one-shot teaching under applicable [57,
22] iterative settings where the learner is gradient-based and its training
algorithm is iterative. Besides, following the realistic fact that human
teachers would teach familiar learners better [90, 91], we focus on the case
learners are well-known for teachers, which means the teacher knows above
factors (e.g., $\eta$ and $\theta^{t}$) of gradient-based learners [19, 57].
The unfamiliar learner case where teachers do not know some factors can be
studied with surrogate methods [92, 58].

##  4 One-shot Teaching

In this section, we firstly establish a tractable mapping from teaching sets
to model parameters, which is proved to be surjective and corroborates the
existence of the optimal teaching set. Since the teaching set is closely
related to the knowledge domain of teachers, we, meanwhile, present further
discussion on different types of teachers. Then, we give the highly-efficient
one-shot teaching strategy (OSTS) for different teachers, which solves for the
optimal teaching set analytically and derives a canonical singleton. Finally,
we provide the case study about typical learner loss functions, which verifies
generalizability of OSTS.

###  4.1 One-shot paradigm

The one-shot paradigm aims to design a singleton as the optimal teaching set
to steer learners to converge after one iteration. It attempts to achieve one-
shot iteration by establishing a tractable mapping from teaching sets to model
parameters, and only requires concrete $\theta^{*}$ as well. First of all, we
present an expansion insight of the gradient across teaching sets and
parameters in model training algorithm Eq.(4) based on chain rule.

######  Proposition 1.

Given a specific teaching example $(x,y)$, the gradient of loss function
$\ell$ w.r.t. the model $f(\theta,x)=\langle\theta,x\rangle$ can be expended
as a constant times the example vector based on chain rule:

$\mathcal{G}(\theta;(x,y)|\ell;f)=\nabla_{f}\ell(f(\theta,x),y)\cdot
x\coloneqq\zeta\cdot x,$ (5)

where it omits the set symbol $\\{\cdot\\}$ out of $\\{(x,y)\\}$ for
convenience.

The teacher is an agent who knows the target model and attempts to search
examples for feeding learners. The Learner is an agent who update its
parameter based on received teaching set via the model training algorithm
Eq.(4). Fundamentally, Eq.(4) tells the relation between the teaching set (as
the input) and the model parameter (as the output), thus we make use of this
relation to establish a tractable mapping from teaching sets to model
parameters: let $\eta$ and input $\theta$ be fixed, each input $\mathcal{D}$
yields a corresponding output $\theta^{\prime}_{\mathcal{D}}$, and the
assignment is characterized by Eq.(4) whose domain is $\mathbb{D}$ and
codomain is $\Theta$. Similarly, let $\eta$ and input teaching set
$\mathcal{D}$ be fixed, each input $\theta$ yields a corresponding output
$\theta^{\prime}_{\theta}$, and Eq.(4) defines the assignment manner, of which
domain and codomain are $\Theta$ in this case. These derive Lemma 2.

######  Lemma 2.

Given a specific learner ($\ell$ and $\eta$ are fixed), the mini-batch
gradient descent algorithm (Eq.(4)) is a tractable mapping
$\mathcal{M}(\theta,\mathcal{D}):\Theta\times\mathbb{D}\mapsto\Theta$
satisfying

  1. (a)

$\mathcal{M}$ is surjective when $\mathcal{D}$ is fixed:
$\forall\theta^{\prime}\in\Theta,\exists\theta\in\Theta$ such that
$\mathcal{M}(\theta|\mathcal{D})=\theta^{\prime}$

  2. (b)

$\mathcal{M}$ is surjective when input $\theta$ is fixed:
$\forall\theta^{\prime}\in\Theta,\exists\mathcal{D}\in\mathbb{D}$ such that
$\mathcal{M}(\mathcal{D}|\theta)=\theta^{\prime}$.

###### Proof.

Without loss of generality, we are concerned with
$\left\|\mathcal{D}\right\|_{0}=1$ case for simplicity, i.e., $\mathcal{D}$
has one element $(x,y)$. The proof when $\left\|\mathcal{D}\right\|_{0}>1$ can
be derived analogously.

(a): For proving $\mathcal{M}$ is surjective in its first arguments, we need
to find $\theta_{\theta^{\prime}}$ such that
$\theta^{\prime}=\mathcal{M}(\theta_{\theta^{\prime}}|\mathcal{D})$. Since
$\Theta$ and $\mathcal{X}$ fundamentally are the subset of a vector space
$\mathbb{R}^{n}$, the operations of vector addition and scalar multiplication
is well defined. With fixed $(x,y)$, specific $\ell$, $f$ and $\eta$,
$\mathcal{M}$ can be specified as

$\displaystyle\mathcal{M}(\theta|(x,y))=\theta-\eta\zeta x$ (6)

based on Proposition 1. Therefore, we can derive that
$\forall\theta^{\prime}\in\Theta$, there always exists
$\theta_{\theta^{\prime}}=\theta^{\prime}+\eta\zeta x$ such that
$\mathcal{M}(\theta_{\theta^{\prime}}|(x,y))=\theta_{\theta^{\prime}}-\eta\zeta
x=\theta^{\prime}$, which concludes the proof of (a).

(b): Similarly, with fixed $\theta$, $\forall\theta^{\prime}\in\Theta$, there
always exists $x_{\theta^{\prime}}=(\theta-\theta^{\prime})/(\eta\zeta)$
(since $\eta$ and $\zeta$ are non-zero scalars) with its label
$y_{\theta^{\prime}}$ such that
$\mathcal{M}((x_{\theta^{\prime}},y_{\theta^{\prime}})|\theta)=\theta-\eta\zeta
x_{\theta^{\prime}}=\theta^{\prime}$. ∎

The Lemma 2 corroborates that this mapping is surjective in both arguments,
which is important as it provides a existence guarantee of the optimal
teaching set. Intuitively, the Lemma 2 tells that

  1. (a)

For any model $\theta^{\prime}\in\Theta$ and fixed teaching set $\mathcal{D}$,
there always exists a learner whose initial model is
$\theta_{\theta^{\prime}}$ such that this learner can learn $\theta^{\prime}$
after one-iteration update with $\mathcal{D}$ following Eq.(4).

  2. (b)

For any model $\theta^{\prime}\in\Theta$ and a learner with fixed model
$\theta$, there always exists a teaching set $\mathcal{D}_{\theta^{\prime}}$
such that this learner can converge to $\theta^{\prime}$ after one-iteration
evolution with $\mathcal{D}_{\theta^{\prime}}$ via Eq.(4).

The established mapping brings convenience to study the relation among input
$\theta$, $\mathcal{D}$ and output $\theta^{\prime}$. With the perspective of
surjective mapping based on (b) of Lemma 2 (existence guarantee), the problem
has been changed to design the optimal teaching set $\mathcal{D}^{*}$ such
that mapping once can achieve convergence from to pick the optimal teaching
set in each iteration to enlarge per-iteration improvement, which is briefly
illustrated in Figure 3.There is a natural concern how to construct
$\mathcal{D}^{*}$ when $\theta^{0}$ and $\theta^{*}$ are fixed such that the
learner can converge to $\theta^{*}$ after update once, i.e.,
$\mathcal{M}(\mathcal{D}^{*}|\theta^{0})=\theta^{*}$. In another word, one-
shot machine teaching is to find the singleton root of

$\displaystyle\mathcal{F}(\mathcal{D}|\theta^{0},\theta^{*})\coloneqq\mathcal{M}(\mathcal{D}|\theta^{0})-\theta^{*},$
(7)

and $\mathcal{D}^{*}=\mathcal{F}^{-1}(0|\theta^{0},\theta^{*})$ with
$\|\mathcal{D}^{*}\|_{0}=1$.

Figure 3: Comparison between iterative MT and one-shot MT. Iterative MT feeds
$\mathcal{D}^{0},\mathcal{D}^{1},\dots,\mathcal{D}^{T}$ gradually and the
learner converge to $\theta^{*}$ iteratively. One-shot MT searches the optimal
teaching set $\mathcal{D}^{*}$, via which the learner converge to $\theta^{*}$
after one iteration.

Since provided $\mathcal{D}$ depends on the specific $\mathbb{D}$ of teachers,
we further discuss possible teachers with different $\mathbb{D}$. Different
from Liu et al. [19, 58], we separate teachers into two types based on
infinite and finite $\mathbb{D}$, which are the complete teacher and pool-
based teachers, respectively.

######  Definition 3 (Complete teacher).

A teacher is called a complete teacher, if the knowledge domain $\mathbb{D}$
of this teacher is derived from the entire teaching example space, an infinite
pool
$\mathcal{P}=\\{(x_{i},y_{i})|x_{i}\in\mathcal{X},y_{i}\in\mathcal{Y}\\}$.

It is trivial to derive that the complete teacher is equipped with addition
and scalar multiplication. Let $\|\mathcal{P}\|_{0}$ in Definition 3 be
finite, we derive the definition of the pool-based teacher:

######  Definition 4 (Pool-based teacher).

A teacher is called a pool-based teacher, if the knowledge domain $\mathbb{D}$
of this teacher is derived from a pool
$\mathcal{P}_{N}=\\{(x_{i},y_{i})|x_{i}\in\mathcal{X}_{N},y_{i}\in\mathcal{Y}_{N},i\leq
N<\infty\\}\subsetneq\mathcal{X}\times\mathcal{Y}$.

Let
$\mathcal{X}_{\mathcal{P}}\times\mathcal{Y}_{\mathcal{P}}\subset\mathcal{X}\times\mathcal{Y}$
be the completion of $\mathcal{P}_{N}$ w.r.t. equipped operations. Further, we
define three types of pool-based teachers based on such operations.

######  Definition 5 (Combinable teacher).

A pool-based teacher is a combinable teacher, if $\mathcal{X}_{\mathcal{P}}$
is closed under addition and scalar multiplication, i.e.,
$\mathcal{X}_{\mathcal{P}}={\rm span}(\mathcal{X}_{N})$: it can provide linear
combination of existing examples as new examples.

######  Definition 6 (Scalable teacher).

A pool-based teacher is a scalable teacher, if $\mathcal{X}_{\mathcal{P}}$ is
not closed under addition but closed under scalar multiplication, i.e.,
$\mathcal{X}_{\mathcal{P}}=\alpha\cdot\mathcal{X}_{N},\alpha\in\mathbb{R}$: it
can provide scaled examples as new examples.

######  Definition 7 (Naive teacher).

A pool-based teacher is a naive teacher, if $\mathcal{X}_{\mathcal{P}}$ is not
closed under addition or scalar multiplication, i.e.,
$\mathcal{X}_{\mathcal{P}}=\mathcal{X}_{N}$: it can only provide existing
examples.

Table 1: The relation among different teachers with their properties. "ScaMul" is the abbreviation of "scalar multiplication". ✓ below "Complete $\mathbb{D}$" means this type of teacher has complete $\mathbb{D}$, and ✗ means not. ✓ below "Addition" and "ScaMul" means the example space of this teacher is closed under that operations, and ✗ means not. Primary | Secondary |  Complete $\mathbb{D}$ | Addition | ScaMul
---|---|---|---|---
Complete | - | ✓ | ✓ | ✓
Pool-based | Combinable | ✗ | ✓ | ✓
Scalable | ✗ | ✗ | ✓
Naive | ✗ | ✗ | ✗

Note that there are infinite potential teaching examples for combinable and
scalable teacher as they can generate examples by linear combination or
scaling, but the naive teacher has finite examples. The complete teacher can
be viewed as an infinite version of the pool-based teacher. We list the
property of above mentioned teachers and their relation in Table 1

###  4.2 One-shot teaching strategy

For different teachers, with established surjective mapping from teaching sets
and parameters we design corresponding one-shot teaching strategies (OSTS),
which attempts to analytically solve for a singleton root
$\mathcal{D}^{*}=\\{(x^{*},y^{*})\\}$ where $(x^{*},y^{*})$ is the optimal
teaching example. This means to find tighter bound of teaching dimension and
iterative teaching dimension.

######  Theorem 8 (One-shot teachability).

For a target $\theta^{*}$, there exists a singleton, on which a learner with
learning rate $\eta\neq 0$, initial $\theta^{0}$ and loss function $\ell(f,y)$
can converge to $\theta^{*}$ after one-iteration training (it can achieve one-
shot iteration), if learner $\ell$ is differentiable w.r.t. $f$.

###### Proof.

To prove the existence of the singleton that can help the learner converge
after one iteration, we need to solve for associated $(x^{*},y^{*})$ in terms
of $\theta^{*}$ in closed form.

With the mapping view in Lemma 2, it fixes $\theta^{0}$ and $\theta^{*}$ to
find a teaching example $(x,y)$ such that the learner touch $\theta^{*}$ after
mapping once:

$\displaystyle\mathcal{M}((x,y)|\theta^{0})=\theta^{*}.$ (8)

It follows from Eq.(7) that it is equivalent to find the singleton root:

$\displaystyle(x^{*},y^{*})=\mathcal{F}^{-1}(\mathcal{D}|\theta^{0},\theta^{*})\qquad\text{s.t.}\,\|\mathcal{D}\|_{0}=1,$
(9)

where we omit the set symbol $\\{\cdot\\}$ for convenience. Recall Proposition
1, when the first-order partial derivatives of $\ell(f,y)$ w.r.t. $f$ exists,
it follows from the chain rule that the gradient at one example can be
expanded as

$\displaystyle\mathcal{G}(\theta;(x,y)|\ell;f)=\nabla_{\theta}\ell(\left\langle\theta,x\right\rangle,y)=\nabla_{\left<\theta,x\right>}\ell(\left\langle\theta,x\right\rangle,y)x.$
(10)

Therefore, analytically solving for $(x^{*},y^{*})$ equals to find the root of
following equation

$\theta^{0}-\eta\nabla_{\left<\theta,x\right>}\ell\left(\left\langle\theta^{0},x\right\rangle,y\right)x-\theta^{*}=0.$
(11)

Since $\theta^{0}\neq\theta^{*}$, we deduce that each term of the product
$\eta\cdot\nabla_{\left<\theta,x\right>}\ell(\left\langle\theta^{0},x\right\rangle,y)\cdot
x$ is a non-zero scalar or vector. Thus, from Eq.(11) we can divide through by
$-\eta\nabla_{\left<\theta,x\right>}\ell(\left\langle\theta^{0},x\right\rangle,y)$
and rearrange, then obtain

$\displaystyle x^{*}=\xi_{\eta;\theta^{0}}(\theta^{*}-\theta^{0}),$ (12)

where constant
$\xi_{\eta;\theta^{0}}\coloneqq-1/\left(\eta\nabla_{\left<\theta,x\right>}\ell(\left\langle\theta^{0},x^{*}\right\rangle,y^{*})\right)$.
$y^{*}$ is a free variable and usually can be derived by $f^{*}(x^{*})$.
Thereby, we have analytically find the singleton root expressed by
$\theta^{*}$

$(x^{*},y^{*})=\left(\xi_{\eta;\theta^{0}}(\theta^{*}-\theta^{0}),f^{*}(\xi_{\eta;\theta^{0}}(\theta^{*}-\theta^{0}))\right),$
(13)

namely the universal optimal teaching example. This completes the proof. ∎

One-shot teachability is a weaker condition compared with Lipschitz smoothness
and strongly convexity since differentiable is weaker than these regularities.
For instance, absolute loss is one-shot teachable but not Lipschitz smooth and
strongly convex. Moreover, as a side effect, it derives that the teaching
dimension and iterative teaching dimension of those strategies who provide
concrete construction methods for existent singleton in Theorem 8 are one,
which is tighter than that of exponential teachability [19, 58, 57].

Since $\mathbb{D}$ of the complete teacher is derived from the entire teaching
example space, it is straightforward to derive OSTS for this type of teacher:

######  Proposition 9 (OSTS for the complete teacher).

For a learner with $\eta\neq 0$ and $\theta^{0}$, the complete teacher should
provide the universal optimal teaching example

$\displaystyle(x^{*},y^{*})=\left(\xi_{\eta;\theta^{0}}(\theta^{*}-\theta^{0}),f^{*}(\xi_{\eta;\theta^{0}}(\theta^{*}-\theta^{0}))\right),$
(14)

with learner-specific constant $\xi_{\eta;\theta^{0}}$ to the learner.

Proposition 9 tells that teachers need to teach learners in accordance with
their aptitude, and the optimal teaching example closely depends on learners
themselves. Specifically, $(x^{*},y^{*})$ is picked based on $\theta^{0}$ and
$\eta$ of learners. If a learner is well-equipped with primary knowledge on
$\theta^{*}$, i.e., its $\theta^{0}$ is very close to $\theta^{*}$, then
$x^{*}$ of sampled $(x^{*},y^{*})$ should be very close to $\vec{0}$, that is,
an indistinguishable one. But for a learner with poor primary knowledge, a
simple and distinguishable $x^{*}$ should be provided. This is consistent with
teaching strategy in curriculum learning [54, 38, 55], where easy examples for
learners at first, and difficult ones for learners as they approaches
$\theta^{*}$. Moreover, for learners with different $\eta$, the magnitude of
$x^{*}$ will be scaled relatively. For instance, an unresponsive learner with
a small $\eta$ should be given a distinguishable $x^{*}$ in relatively large
scale.

For pool-based teachers, the accessibility of the universal optimal teaching
example in Theorem 8 should be considered additionally. We following present
teacher-specific OSTS based on teacher-equipped operations.

######  Proposition 10 (OSTS for the combinable teacher).

For a learner with $\eta\neq 0$ and $\theta^{0}$, the optimal teaching example
$(x^{*},y^{*})$ for the combinable teacher with
$\mathcal{P}_{N}=\mathcal{X}_{N}\times\mathcal{Y}_{N}$ is

$\displaystyle\begin{aligned}
&x^{*}=\underset{x^{\dagger}\in\mathcal{X}_{\mathcal{P}}}{\arg\min}\quad\left\|x^{\dagger}-\xi_{\eta;\theta^{0}}(\theta^{*}-\theta^{0})\right\|_{2}^{2}\\\
&\text{s.t.}\quad
x^{\dagger}=\langle\beta,(x_{1},\dots,x_{N})^{T}\rangle,\qquad\beta\in\mathbb{R}^{N},x_{i}\in\mathcal{X}_{N}\end{aligned}$
(15)

where $\beta$ is called the generative coefficient vector, and
$y^{*}=f^{*}(x^{*})$.

$\beta$ can be trained by a two-layer multilayer perceptron (MLP) illustrated
in Figure 4 without nonlinear activation function, of which input and output
are $(x_{1},\dots,x_{N})^{T}$ and
$\langle\beta,(x_{1},\dots,x_{N})^{T}\rangle$, respectively.

Figure 4: The illustration of multilayer perceptron (MLP) structure. The input
is feature vectors of $N$ teaching examples $x_{1},\dots,x_{N}$ in pool
$\mathcal{X}_{N}$. The connection weights are precisely generative
coefficients. The output is the weighted sum of the input connections without
nonlinear activation.

Input: Optimal $\theta^{*}$, initial $\theta^{0}$, learning rate $\eta$, small
constant $\epsilon>0$ and maximal iteration number $T$. Small positive
constant $\delta$ and $\mathcal{P}_{N}$ for pool-based teachers. if  _teacher
is complete_ then

Return
$(x^{*},y^{*})=\left(\xi_{\eta;\theta^{0}}(\theta^{*}-\theta^{0}),f^{*}(\xi_{\eta;\theta^{0}}(\theta^{*}-\theta^{0}))\right)$
directly;

else if  _teacher is combinable_ then

Denote
$\mathcal{L}(\beta)\coloneqq\left\|\langle\beta,(x_{1},\dots,x_{N})^{T}\rangle-\xi_{\eta;\theta^{0}}(\theta^{*}-\theta^{0})\right\|_{2}^{2},\qquad
x_{i}\in\mathcal{X}_{N}$;

Random initial $\beta^{0}$, set $\beta^{t}\leftarrow\beta^{0}$ and $t=0$;

while  _$t\leq T$ and $\mathcal{L}(\beta^{t})\geq\epsilon$_ do

$\beta^{t}\leftarrow\beta^{t}-\delta\nabla_{\beta}\mathcal{L}(\beta^{t})$;

Set $t\leftarrow t+1$;

end while

Return
$(x^{*},y^{*})=\left(\langle\beta^{t},(x_{1},\dots,x_{N})^{T}\rangle,f^{*}(\langle\beta^{t},(x_{1},\dots,x_{N})^{T}\rangle)\right)$;

else if  _teacher is scalable_ then

Search $x^{\dagger}$ by
$x^{\dagger}=\underset{x_{i}\in\mathcal{X}_{N}}{\arg\min}\quad\min\left(\left\|\frac{x_{i}}{\left\|x_{i}\right\|_{2}}-\frac{\theta^{*}-\theta^{0}}{\left\|\theta^{*}-\theta^{0}\right\|_{2}}\right\|_{2}^{2},\left\|\frac{x_{i}}{\left\|x_{i}\right\|_{2}}+\frac{\theta^{*}-\theta^{0}}{\left\|\theta^{*}-\theta^{0}\right\|_{2}}\right\|_{2}^{2}\right)$;

Return $x^{*}=\kappa x^{\dagger}$ and $y^{*}=f^{*}(x^{*})$, in which
$\kappa=\operatorname{sgn}\left(\left\|\frac{x_{i}}{\left\|x_{i}\right\|_{2}}+\frac{\theta^{*}-\theta^{0}}{\left\|\theta^{*}-\theta^{0}\right\|_{2}}\right\|_{2}^{2}-\left\|\frac{x_{i}}{\left\|x_{i}\right\|_{2}}-\frac{\theta^{*}-\theta^{0}}{\left\|\theta^{*}-\theta^{0}\right\|_{2}}\right\|_{2}^{2}\right)\cdot\xi_{\eta;\theta^{0}}\left\|\theta^{*}-\theta^{0}\right\|_{2}/\left\|x^{\dagger}\right\|_{2}$;

else if  _teacher is naive_ then

Return
$x^{*}=\underset{x_{i}\in\mathcal{X}_{N}}{\arg\min}\quad\left\|x_{i}-\xi_{\eta;\theta^{0}}(\theta^{*}-\theta^{0})\right\|_{2}^{2}$
and $y^{*}=f^{*}(x^{*})$.

end if

Algorithm 1 One-shot teaching strategy (OSTS)

######  Proposition 11 (OSTS for the scalable teacher).

For a learner with $\eta\neq 0$ and $\theta^{0}$, the optimal teaching example
$(x^{*},y^{*})$ for the scalable teacher with
$\mathcal{P}_{N}=\mathcal{X}_{N}\times\mathcal{Y}_{N}$ is

$\displaystyle x^{*}=\kappa x^{\dagger}$ (16)

and $y^{*}=f^{*}(x^{*})$, in which
$\kappa=\operatorname{sgn}\left(\left\|\frac{x_{i}}{\left\|x_{i}\right\|_{2}}+\frac{\theta^{*}-\theta^{0}}{\left\|\theta^{*}-\theta^{0}\right\|_{2}}\right\|_{2}^{2}-\left\|\frac{x_{i}}{\left\|x_{i}\right\|_{2}}-\frac{\theta^{*}-\theta^{0}}{\left\|\theta^{*}-\theta^{0}\right\|_{2}}\right\|_{2}^{2}\right)\cdot\xi_{\eta;\theta^{0}}\left\|\theta^{*}-\theta^{0}\right\|_{2}/\left\|x^{\dagger}\right\|_{2}$
and

$\displaystyle
x^{\dagger}=\underset{x_{i}\in\mathcal{X}_{N}}{\arg\min}\quad\min\left(\left\|\frac{x_{i}}{\left\|x_{i}\right\|_{2}}-\frac{\theta^{*}-\theta^{0}}{\left\|\theta^{*}-\theta^{0}\right\|_{2}}\right\|_{2}^{2},\left\|\frac{x_{i}}{\left\|x_{i}\right\|_{2}}+\frac{\theta^{*}-\theta^{0}}{\left\|\theta^{*}-\theta^{0}\right\|_{2}}\right\|_{2}^{2}\right)$
(17)

For the scalable teacher, the fundamental difference among examples is their
normalized vector derived by operator $\frac{\cdot}{\left\|\cdot\right\|_{2}}$
since the magnitude can be scaled correspondingly. Besides, the operator
$\min\left(\left\|\cdot-\cdot\right\|_{2}^{2},\left\|\cdot+\cdot\right\|_{2}^{2}\right)$
is to avoid the influence of opposite direction between $x_{i}$ and
$\theta^{*}-\theta^{0}$. Therefore, the scalable teacher should pick the
example whose normalized vector is close to that of the universal optimal
teaching example when ignoring the direction. For the naive teacher, it is
straightforward to derive associated OSTS.

######  Proposition 12 (OSTS for the naive teacher).

For a learner with $\eta\neq 0$ and $\theta^{0}$, the optimal teaching example
$(x^{*},y^{*})$ for the naive teacher with
$\mathcal{P}_{N}=\mathcal{X}_{N}\times\mathcal{Y}_{N}$ is

$\displaystyle
x^{*}=\underset{x_{i}\in\mathcal{X}_{N}}{\arg\min}\quad\left\|x_{i}-\xi_{\eta;\theta^{0}}(\theta^{*}-\theta^{0})\right\|_{2}^{2},$
(18)

and $y^{*}=f^{*}(x^{*})$.

One can observe that pool-based teachers need more workload to construct the
optimal teaching example. Specifically, different from the complete teacher,
OSTS requires scalable (combinable) teachers to do further scaling (linear
combination) to match the universal optimal teaching example Eq.(13). Packing
OSTS for the complete and pool-based teachers up, the pseudo code is
summarized in Alg.1.

Limited knowledge knowledge leads to constrained capability of teachers.
Therefore, the condition of learners is discussed as follows, satisfying which
they can converge after one iteration with the help of a pool-based teacher.
In another word, pool-based teachers can construct the universal optimal
teaching example for the learner who satisfies such condition.

######  Theorem 13.

For a learner with $\eta\neq 0$ and $\theta^{0}$, the pool-based teachers are
able to construct the universal optimal teaching example, if $\theta^{0}$
satisfies following teacher-specific necessary and sufficient condition.

  1. (a)

$\theta^{0}-\theta^{*}\in\text{\rm span}(\mathcal{X}_{N})$ for the combinable
teacher;

  2. (b)

$\theta^{0}-\theta^{*}\in\alpha\cdot\mathcal{X}_{N},\alpha\in\mathbb{R}$ for
the scalable teacher;

  3. (c)

$\xi_{\eta;\theta^{0}}(\theta^{0}-\theta^{*})\in\mathcal{X}_{N}$ for the naive
teacher.

###### Proof.

The proof of the naive teacher (c) is trivial so we omit it.

"$\Rightarrow$":

  1. (a)

Since $\theta^{0}-\theta^{*}\in\text{\rm span}(\mathcal{X}_{N})$, we can
derive $\exists\,\lambda_{1},\lambda_{2},\dots,\lambda_{N}\in\mathbb{R}$ not
all zero, such that

$\displaystyle\theta^{0}-\theta^{*}=\sum_{i=1}^{N}\lambda_{i}x_{i},\qquad
x_{i}\in\mathcal{X}_{N}.$ (19)

Hence, we can obtain
$\xi_{\eta;\theta^{0}}(\theta^{*}-\theta^{0})=-\xi_{\eta;\theta^{0}}\sum_{i=1}^{N}\lambda_{i}x_{i}$.
Let $\beta_{i}=-\xi_{\eta;\theta^{0}}\lambda_{i}$, then the combinable teacher
can derive the universal optimal teaching example.

  2. (b)

Similarly,
$\because\theta^{0}-\theta^{*}\in\alpha\cdot\mathcal{X}_{N},\,\therefore\exists\alpha\neq
0\in\mathbb{R},x_{i}\in\mathcal{X}_{N}$ such that
$\theta^{0}-\theta^{*}=\alpha x_{i}$. Then the scalable teacher can obtain the
universal optimal teaching example by setting
$\beta=-\xi_{\eta;\theta^{0}}\alpha\cdot e_{i}$.

"$\Leftarrow$":

  1. (a)

Since the combinable teacher can derive the universal optimal teaching
example, we can derive $\exists\,\beta\in\mathbb{R}^{n}$, such that

$\displaystyle\xi_{\eta;\theta^{0}}(\theta^{*}-\theta^{0})=\langle\beta,(x_{1},\dots,x_{N})^{T}\rangle,\qquad
x_{1},\dots,x_{N}\in\mathcal{X}_{N}.$ (20)

Since the constant $\xi_{\eta;\theta^{0}}$ is non-zero, we have

$\displaystyle\theta^{0}-\theta^{*}=\sum_{i=1}^{N}-\frac{\beta_{i}}{\xi_{\eta;\theta^{0}}}x_{i},\qquad
x_{i}\in\mathcal{X}_{N},$ (21)

from which we can conclude $\theta^{0}-\theta^{*}\in\text{\rm
span}(\mathcal{X}_{N})$.

  2. (b)

Analogously, we can derive $\exists\,\beta\in\mathbb{R}$, such that

$\displaystyle\xi_{\eta;\theta^{0}}(\theta^{*}-\theta^{0})=\beta\cdot
x_{i},\qquad x_{i}\in\mathcal{X}_{N}.$ (22)

For a non-zero constant $\xi_{\eta;\theta^{0}}$, we have

$\displaystyle\theta^{0}-\theta^{*}=-\frac{\beta}{\xi_{\eta;\theta^{0}}}x_{i},$
(23)

i.e.,
$\theta^{0}-\theta^{*}\in\alpha\cdot\mathcal{X}_{N},\alpha\in\mathbb{R}$.

∎

Theorem 13 tells that the teaching ability of pool-based teachers depends on
equipped operation. Specifically, the combinable teacher is better qualified
than other pool-based teachers, who can construct the universal optimal
teaching example if the difference between $\theta^{0}$ of these learners and
$\theta^{*}$ is expressible in terms of $\mathcal{X}_{N}$. For the scalable
teacher, the capability is worse. They are only able to generate the universal
optimal teaching example for those learners whose $\theta^{0}$ satisfy
$\theta^{0}-\theta^{*}\in\alpha\mathcal{X}_{N}$. Moreover, for the naive
teacher, they only can do that when the universal optimal teaching example is
in their pools.

######  Remark 14.

The specific task for model $\theta^{*}$ can be not only regression but also
classification. Besides above analysis of OSTS is mainly on binary
classification, based on which K-class cases can be extend straightforward
since a K-class classification task usually can be separated into K binary
classification tasks.

###  4.3 Learner loss functions

We mainly discuss three typical loss functions (square loss, hinge loss and
logistic loss) under the complete teacher, which can be extended to the pool-
based teacher following Proposition 10, 11, 12. The learners with these loss
functions are called least square regression (LSR), support vector machine
(SVM) and logistic regression (LR) learners, respectively. Without loss of
generality, we consider the worse case where the learner has no primary
knowledge, i.e., $\theta^{0}=0$.

######  Proposition 15.

Square loss, $\ell(f,y)=\left(f-y\right)^{2}$ is one-shot teachable for the
complete teacher.

###### Proof.

It follows from Theorem 8 that the first-order differentiable learner loss is
one-shot teachable, and it is evident that square loss $\left(f-y\right)^{2}$
has first-order partial derivatives w.r.t. $f$, which justifies the existence
of the optimal teaching example. Hence, to prove square loss is one-shot
teachable, it needs to solve for $\xi_{\eta;\theta^{0}}$.

Following Proposition 1, we have

$\displaystyle\mathcal{G}\left(\theta^{0};(x,y)|\left(f-y\right)^{2};\left\langle\theta,x\right\rangle\right)=2\left(\left\langle\theta^{0},x\right\rangle-y\right)x.$

Thus, we obtain

$\displaystyle\xi_{\eta;\theta^{0}}=1/(2\eta y).$

Therefore, the optimal teaching example $(x^{*},y^{*})$ is

$(x^{*},y^{*})=\left((\theta^{*}-\theta^{0})/(2\eta y^{*}),y^{*}\right)$

where $y^{*}$ is a free variable, which can be arbitrarily chosen in
$\mathcal{Y}$ at first. ∎

We see that for the dynamic learner equipped with variable learning rate
$\eta^{t},t=0,1,\dots,T$, the teacher merely requires the initial $\eta^{0}$
to construct the optimal teaching example. For hinge loss, we mainly consider
homogeneous $\theta$ (without a bias term), and the inhomogeneous result can
be derived similarly.

######  Proposition 16.

Hinge loss, $\ell(f,y)=\max\left(1-y\cdot f,0\right)$ is one-shot teachable
for the complete teacher.

###### Proof.

The hinge loss, $\text{max}\left(1-y\cdot f,0\right)$, is also first-order
differentiable w.r.t. $f$. Besides, $(x^{*},y^{*})$ should be one of the
teaching examples $(x,y)$ who satisfy $1-y\cdot f(\theta^{0},x)>0$, otherwise
the gradient at $(x^{*},y^{*})$ is zero and $\theta^{0}$ will not be updated.
Therefore, we have

$\displaystyle\mathcal{G}\left(\theta^{0};(x,y)|1-y\cdot
f;\left\langle\theta,x\right\rangle\right)=-yx.$

Consequently, we have

$\displaystyle\xi_{\eta;\theta^{0}}=1/(\eta y),$

which yields the optimal teaching example

$(x^{*},y^{*})=\left((\theta^{*}-\theta^{0})/(\eta y^{*}),y^{*}\right)$

where $y^{*}$ is a free variable as well. This completes the proof. ∎

######  Proposition 17.

Logistic loss, $\ell(f,y)=\log\left(1+\exp\left(-y\cdot f\right)\right)$ is
one-shot teachable for the complete teacher.

###### Proof.

The logistic loss, $\text{log}\left(1+\text{exp}\left(-y\cdot
f\right)\right)$, is first-order differentiable w.r.t. $f$ as well. It follows
from Proposition 1 that

$\displaystyle\mathcal{G}\left(\theta^{0};(x,y)|\text{log}\left(1+\text{exp}\left(-y\cdot
f\right)\right);\left\langle\theta,x\right\rangle\right)$ $\displaystyle=$
$\displaystyle\frac{-y\text{exp}\left(-y\left\langle\theta^{0},x\right\rangle\right)}{1+\text{exp}\left(-y\left\langle\theta^{0},x\right\rangle\right)}x=\frac{-y}{1+\text{exp}\left(y\left\langle\theta^{0},x\right\rangle\right)}x.$

Thus, we have

$\displaystyle\xi_{\eta;\theta^{0}}=2/(\eta y).$

It derives the optimal teaching example

$(x^{*},y^{*})=\left(2(\theta^{*}-\theta^{0})/(\eta y^{*}),y^{*}\right)$

with free variable $y^{*}$, which is the desired result. ∎

As expected, these first-order differentiable loss functions are one-shot
teachable, which justifies that one-shot teachability is not a strict
condition and demonstrates the general applicability of OSTS.

##  5 Experiments

In this section, we compare OSTS with machine learning and iterative
strategies on synthetic and real-world data, which demonstrates the efficiency
of OSTS.

Specifically, we derive $\theta^{*}$ by predefining (synthetic data) or
pretraining (real-world dataset). L-2 norm is set to measure learner bias
$\mathcal{B}(\theta^{t},\theta^{*})=\|\theta^{t}-\theta^{*}\|_{2}$. Without
particular emphasis, experiments are implemented under the complete teachers
setting. We teach linear model binary classification tasks and nonlinear
neural networks (convolutional neural network) 10-class classification tasks.

###  5.1 Comparing OSTS with machine learning strategies

(a) MNIST 0 VS. 1 (b) MNIST 3 VS. 8 (c) CIFAR10

Figure 5: OSTS vs. machine learning strategies. LR learners following OSTS
converge faster and have higher testing accuracy than that guided by other
five machine learning strategies on both binary and 10-class classification
tasks.

(a) LSR leaner

(b) SVM leaner

(c) LR leaner

Figure 6: Teaching three typical learners on Gaussian data. Figures of
$\mathcal{B}(\theta^{t},\theta^{*})$ and $\theta^{t}$ evolution of three
learners show that OSTS arrives $\theta^{*}$ at one step while SGD and BSGD
approach $\theta^{*}$ gradually. $\ell_{sto}(\theta)$ of OSTS drops
significantly faster than that of SGD and BSGD.

We compare testing accuracy of LR learners guided by OSTS and machine learning
strategies on MNIST [93] and CIFAR10 [94]. In detail, unsupervised baselines
are K-means, hierarchical and spectral clustering, and supervised ones are
active learning strategies including max-entropy maximizing the predictive
entropy [95] and mean-std maximizing the mean standard deviation [96, 97]. As
expected, using one teaching example, OSTS surpass all these baselines.
Specifically, OSTS has the highest testing accuracy, and it also costs less
examples than other strategies to help learners converge to $\theta^{*}$.

Figure 5 shows that no matter binary or 10-class classification tasks, OSTS is
the most efficient strategies in terms of the cost examples and the testing
accuracy. This illustrates the necessity of teaching, that is, being taught
can be faster than asking questions [6]. Further, such outperformance is
increasingly significant as the complexity of classification tasks grows,
which implies the higher value of OSTS in complicated cases. On the other
hand, active learning strategies outperform unsupervised ones in complicated
cases since they have more clear objective of example selection, towards which
it can accelerate improvement of accuracy. Since we sample randomly for
clustering, the curves of unsupervised strategies are winding.

###  5.2 Comparing OSTS with iterative strategies

When comparing OSTS with iterative strategies (SGD and BSGD), we further
assess the performance including learner bias
$\mathcal{B}(\theta^{t},\theta^{*})$ and testing loss $\ell(\theta^{t})$. As
expected, costing less, OSTS outperforms iterative baselines in terms of the
speed of convergence and the testing accuracy on synthetic and real-world
(MNIST and CIFAR10) data.

(a) 0 VS. 1

(b) 3 VS. 8

Figure 7: Teaching LR learners on MNIST dataset. Two
$\mathcal{B}(\theta^{t},\theta^{*})$ figures illustrate that learners guided
by OSTS under complete and pool-based teachers converge to $\theta^{*}$ at one
step. Shown in testing loss and accuracy figures, OSTS under complete and
pool-based teachers have lower testing loss and higher testing accuracy after
one iteration, in contrast with gradual improvement of SGD and BSGD.

####  5.2.1 Synthetic data

Figure 8: Teaching sets under different strategies on MNIST dataset in left-
to-right and top-to-bottom ordering. There are no significant trends of the
selection ordering under SGD and BSGD. Two optimal teaching examples
$(x^{*},y^{*})$s are ambiguous.

To show the general applicability of OSTS, we take LSR, SVM and LR learners
mentioned in Section 4.3 as instances. LSR learners are taught regression
tasks when SVM and LR learners are taught binary classification tasks.
Besides, it is assumed that there are intercept terms in $\theta$ of these
three learners. Out of robustness, we utilize stochastic loss
$\ell_{sto}(\theta)$ on synthetic datasets defined as below. We set Batch in
stochastic loss and BSGD as 100.

######  Definition 18 (Stochastic Loss).

Given a pool of examples, stochastic loss of a specific parameter $\theta$ is
the average loss of a batch of stochastically chosen examples, which is
evaluated at model $f(\theta,x)$.

For instance, stochastic loss of $\theta^{*}$ is

$\ell_{sto}(\theta^{*})=\frac{1}{\text{batch}}\sum_{i=1}^{\text{batch}}\ell(f(\theta^{*},x_{i}),y_{i}).$

LSR learner. We set $\theta\in\Theta=\mathbb{R}^{2}$ so that we can visualize
the training procedure of LSR learners. Specifically,
$\theta^{*}=(-0.8,0.6)^{T}\text{ and }\theta^{0}=(0.1,0.3)^{T}$. Besides,
teaching set of SGD and BSGD, $\mathcal{D}=\\{(x_{i},y_{i})\\}_{i=1}^{1000}$
contains 1000 examples where $x_{i}\sim\mathcal{U}(-10,10)$ and
$y_{i}=\left<\theta^{*},x_{i}\right>+\epsilon,\epsilon\sim\mathcal{N}(0,2^{2})$.
We use $\mathcal{U}$ and $\mathcal{N}$ to denote uniform and normal
distribution, respectively. It follows from Theorem 8 that value of $\eta$
does not affect one-iteration convergence, we set $\eta$ for OSTS
($\eta_{\text{OSTS}}$) as 0.01 out of easy-visualized purpose, and $\eta$s for
SGD and BSGD ($\eta_{\text{SGD\&BSGD}}$) are set 0.0001.

SVM learner. We set $\theta\in\Theta=\mathbb{R}^{3}$ for SVM learners with
$\theta^{*}=(0.8,1,-0.6)^{T}\text{ and }\theta^{0}=(-0.1,0.1,-0.7)^{T}$.
Meanwhile, 500 positive and 500 negative teaching examples of SGD and BSGD are
constructed as $x_{+}\sim\mathcal{N}\left((1.8,2.85)^{T},\text{I}_{2}\right)$
and $x_{-}\sim\mathcal{N}\left((-1.8,-1.65)^{T},\text{I}_{2}\right)$ with 2-d
identity matrix $\text{I}_{2}$. Similarly to LSR learners,
$\eta_{\text{OSTS}}=0.1$ and static $\eta_{\text{SGD\&BSGD}}=0.0001$.

LR learner. $\Theta=\mathbb{R}^{3}$ as well.
$\theta^{*}=(0.8,0.6,0.5)^{T}\text{ and }\theta^{0}=(0.4,-0.2,0.46)^{T}$.
Besides, 500 $x_{+}\sim\mathcal{N}\left((5,10)^{T},\text{I}_{2}\right)$ and
500 $x_{-}\sim\mathcal{N}\left((-5,-10)^{T},\text{I}_{2}\right)$. Same as
previous two learners, $\eta_{\text{OSTS}}=0.1$ and static
$\eta_{\text{SGD\&BSGD}}=0.0001$.

The performance of these all three learners is evaluated with learner bias
$\mathcal{B}(\theta^{t},\theta^{*})$ and stochastic loss
$\ell_{sto}(\theta^{t})$ in combination with visualization of $\theta^{t}$
evolution. Learner bias and stochastic loss figures in Figure 6 clearly show
that OSTS outperform than SGD and BSGD, demonstrating the effectiveness of our
OSTS. In detail, $\mathcal{B}(\theta^{t},\theta^{*})$ and $\ell(\theta^{t})$
of SGD and BSGD decrease gradually as iteration number grows thus, they are
curves. More interestingly, since LSR, SVM and LR learners all are able to
converge to $\theta^{*}$ within one iterative training on $(x^{*},y^{*})$
derived by OSTS, OSTS looks like seemingly vertical lines. Actually, the
reason of this appearance is that the range of $x$ axis is just [0,1], which
we have zoomed in. 2D and 3D figures of $\theta^{t}$ evolution are more vivid,
which show that SGD and BSGD help learners approach $\theta^{*}$ progressively
while learners of OSTS arrives $\theta^{*}$ at one step. Magical performance
of OSTS shows the significant effectiveness of our theoretical proposition.
Just as the fact in real world that there are many knowledgeable and
sophisticated teachers qualified to help learners learn the knowledge with few
efforts, OSTS qualifies every teacher to make it.

Figure 9: Teaching LR learners on CIFAR10 dataset.
$\mathcal{B}(\theta^{t},\theta^{*})$ curves show that SGD and BSGD approach
$\theta^{*}$ slowly while OSTS reach $\theta^{*}$ at one step. Testing loss
and accuracy figures illustrate that OSTS costs less (one iteration) than SGD
and BSGD (more than 1000 iterations) to have competitive performance.

####  5.2.2 Real-world datasets

MNIST. We consider binary classification tasks and LR learners, and test the
performance of OSTS under both complete and pool-based teachers. We are mainly
concerned with combinable teachers among pool-based teachers since it is more
practical and flexible. First of all, random projection is hired to reduce
28*28 = 784D into 24D features (projection with a random matrix
$\mathbb{R}^{784\times 24}$). Based on 24D features, the LR learner with no
primary knowledge is trained to do binary classification tasks, which are
distinguishing 0 from 1 and 3 from 8. We randomly choose 48 teaching examples
from the whole dataset of MNIST as the pool of combinable teacher
$\mathcal{P}_{48}$, and the generative coefficient vector is 48D
$\beta\in\mathbb{R}^{48}$. Besides, it is assumed that there are no intercept
terms in $\theta$. $\eta_{\text{OSTS}}=\eta_{\text{SGD\&BSGD}}=0.0001$.

Table 2: Final results of different strategies on MNIST. "cOSTS" denotes OSTS
under the complete teacher and "pOSTS" represents OSTS under the pool-based
(combinable) teacher.

| 0 VS. 1 | 3 VS. 8
---|---|---
| SGD | BSGD | cOSTS | pOSTS | SGD | BSGD | cOSTS | pOSTS
Learner Bias | 0.3258 | 0.3279 | 0 | 0.0003 | 0.1952 | 0.1950 | 0 | 0.0008
Stochastic loss | 0.2340 | 0.2350 | 0.0794 | 0.0794 | 0.3560 | 0.3525 | 0.2837 | 0.2838
Testing accuracy (%) | 97.68 | 97.49 | 98.44 | 98.44 | 86.44 | 87.00 | 88.36 | 88.26

Figure 7 illustrates that SGD and BSGD help learners attain $\theta^{*}$
gradually while OSTS for both the complete and pool-based teacher did it at
one step, which shows OSTS is more efficient. Interestingly, if teachers
provide teaching sets at random, even they know $\theta^{*}$, learners usually
fail to learn $\theta^{*}$. Instead, learners tend to converge to another
suboptimal parameter ${\theta^{*}}^{\prime}$, which results in higher testing
loss and lower testing accuracy. These findings agree with the necessity of
supervision from teachers. Final results are listed in Table 2. Besides,
Figure 8 shows teaching sets of SGD and BSGD in combination with
$(x^{*},y^{*})$s derived by OSTS. One can see examples in SGD and BSGD are
randomly ordered. Aware of the linearity of random projection, we present
$(x^{*},y^{*})$ of complete teachers which are ambiguous. The auxiliary lines
of them offer two sights of $(x^{*},y^{*})$s in 0/1 or 3/8. Taking
$(x^{*},y^{*})$ in 0/1 as an instance, it is like 1 and also close to 0, which
is hard to classify. Actually, the label of $(x^{*},y^{*})$s are 1 and 8,
respectively. Ambiguous appearance meets expectation since only after learning
ambiguous examples, the learner is able to make a right judgment on
indistinguishable samples, then we can say this learner is qualified to handle
this classification problem. It is also consistent with active learning [98]
where learners query oracle with increasingly ambiguous examples.

Table 3: Structure of CNN.

Operation Layer | Filters Number | Filters Size | Stride | Padding | Output Size
---|---|---|---|---|---
Input image | - | - | - | - | $3\times 32\times 32$
Block 1 | Convolution | 32 | $3\times 3\times 3$ | 1 | 1 | $32\times 32\times 32$
ReLU | - | - | - | - | $32\times 32\times 32$
Convolution | 64 | $32\times 3\times 3$ | 1 | 1 | $64\times 32\times 32$
ReLU | - | - | - | - | $64\times 32\times 32$
| Max pooling | 1 | $2\times 2$ | 2 | 0 | $64\times 16\times 16$
Block 2 | Convolution | 128 | $64\times 3\times 3$ | 1 | 1 | $128\times 16\times 16$
ReLU | - | - | - | - | $128\times 16\times 16$
Convolution | 128 | $128\times 3\times 3$ | 1 | 1 | $128\times 16\times 16$
ReLU | - | - | - | - | $128\times 16\times 16$
| Max pooling | 1 | $2\times 2$ | 2 | 0 | $128\times 8\times 8$
Block 3 | Convolution | 256 | $128\times 3\times 3$ | 1 | 1 | $256\times 8\times 8$
ReLU | - | - | - | - | $256\times 8\times 8$
Convolution | 256 | $256\times 3\times 3$ | 1 | 1 | $256\times 8\times 8$
ReLU | - | - | - | - | $256\times 8\times 8$
| Max pooling | 1 | $2\times 2$ | 2 | 0 | $256\times 4\times 4$
Final block | Fully connected | - | - | - | - | $10$

Table 4: Final results of different strategies on CIFAR10.
| SGD | BSGD | OSTS
---|---|---|---
Learner Bias | 2.0940 | 2.0965 | 0
Testing loss | 0.1517 | 0.1494 | 0.1222
Testing accuracy (%) | 73.81 | 74.37 | 77.08

CIFAR10. We consider 10-class classification tasks and LR learners. We extend
the shallow models to the deep ones, the convolutional neural network (CNN)
whose structure is provided in Table 3. A CNN can be divided into feature
extraction and classification parts. Specifically, feature extraction is
comprised of blocks of convolutional, ReLU and pooling layers and
classification refers to the final fully connected (FC) layers. We make use of
feature extraction part to do feature engineering and derive input
$x\in\mathcal{X}=\mathbb{R}^{4096}$. Based on 4096D features from feature
extraction, the learner needs to learn the 10-class classifier identified by
$\theta\in\Theta=\mathbb{R}^{4096\times 10}$. Experiment results show that
even with a large number of features, OSTS always works. We extract features
at first 3 layer blocks of CNN, then train the fully connected layer on
extracted features with the loss function (the sum of ten logistic loss
functions for ten classes), finally teach this classifier to learners.
$\eta_{\text{OSTS}}=\eta_{\text{SGD\&BSGD}}=0.001$.

Analogously, Figure 9 illustrate that for 10-class classification tasks, OSTS
teaches $\theta^{*}$ at one step while SGD and BSGD accomplish it step by
step. Besides, it needs 10 distinct $(x^{*},y^{*})$ for OSTS to do that, and
it needs more than 1000 teaching examples for SGD or BSGD. These show the high
efficiency of OSTS. Besides, SGD has a poorer performance than BSGD since
training on a single example (SGD) is not enough to distinguish 10 classes.
The final results are shown in Table 4.

##  6 Conclusion

In this paper, we propose a more intelligent machine teaching paradigm named
one-shot machine teaching to achieve one-shot iteration, which is to search a
singleton that can steer learners to converge after one iteration.
Establishing a tractable mapping proved to be surjective from teaching sets to
model parameters, the one-shot paradigm corroborates the existence of the
optimal teaching set by which the optimal model can be learnt after one
iteration. Relying on the surjective mapping, we develop a canonical design
strategy of the optimal teaching set, namely one-shot teaching strategy whose
teaching dimension and iterative teaching dimension are one, for both complete
and pool-based (combinable, scalable and naive) teachers. We discuss the
generalizability of our strategy w.r.t. the learner loss functions (e.g.,
square, hinge and logistic loss). The high efficiency of our strategy has been
empirically verified, which also demonstrates the intelligence of this new
teaching paradigm.

## Acknowledgement

This work was supported by the National Natural Science Foundation of China
under Grant 62206108.

## References

  * Poole et al. [1998] D. Poole, A. Mackworth, R. Goebel,  Computational intelligence (1998).
  * Nilsson and Nilsson [1998] N. J. Nilsson, N. J. Nilsson, Artificial intelligence: a new synthesis, Morgan Kaufmann, 1998.
  * Luger [2005] G. F. Luger, Artificial intelligence: structures and strategies for complex problem solving, Pearson education, 2005.
  * Russell [2010] S. J. Russell, Artificial intelligence a modern approach, Pearson Education, Inc., 2010\.
  * Musial et al. [2012] M. Musial, F. Pradère, A. Tricot, Comment concevoir un enseignement?, De Boeck,, 2012.
  * Rivest and Yin [1995] R. L. Rivest, Y. L. Yin,  Being taught can be faster than asking questions,  in: Proceedings of the eighth annual conference on Computational learning theory, 1995, pp. 144–151.
  * Cakmak and Thomaz [2014] M. Cakmak, A. L. Thomaz,  Eliciting good teaching from humans for machine learners,  Artificial Intelligence 217 (2014) 198–215.
  * Zhu [2015] X. Zhu,  Machine teaching: An inverse problem to machine learning and an approach toward optimal education,  in: Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
  * Zhu et al. [2018] X. Zhu, A. Singla, S. Zilles, A. N. Rafferty,  An overview of machine teaching,  arXiv preprint arXiv:1801.05927 (2018).
  * Singla et al. [2013] A. Singla, I. Bogunovic, G. Bartók, A. Karbasi, A. Krause,  On actively teaching the crowd to classify,  in: NIPS Workshop on Data Driven Education, POST_TALK, 2013.
  * Singla et al. [2014] A. Singla, I. Bogunovic, G. Bartók, A. Karbasi, A. Krause,  Near-optimally teaching the crowd to classify,  in: International Conference on Machine Learning, PMLR, 2014, pp. 154–162.
  * Pan and Yang [2009] S. J. Pan, Q. Yang,  A survey on transfer learning,  IEEE Transactions on knowledge and data engineering 22 (2009) 1345–1359.
  * Patil et al. [2014] K. R. Patil, X. Zhu, Ł. Kopeć, B. C. Love,  Optimal teaching for limited-capacity human learners,  in: Advances in neural information processing systems, 2014, pp. 2465–2473.
  * Mei and Zhu [2015] S. Mei, X. Zhu,  Using machine teaching to identify optimal training-set attacks on machine learners,  in: Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
  * Alfeld et al. [2016] S. Alfeld, X. Zhu, P. Barford,  Data poisoning attacks against autoregressive models,  in: Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
  * Alfeld et al. [2017] S. Alfeld, X. Zhu, P. Barford,  Explicit defense actions against test-set attacks,  in: Thirty-First AAAI Conference on Artificial Intelligence, 2017.
  * Goldman and Mathias [1996] S. A. Goldman, H. D. Mathias,  Teaching a smarter learner,  Journal of Computer and System Sciences 52 (1996) 255–267.
  * Zhu [2013] X. Zhu,  Machine teaching for bayesian learners in the exponential family,  arXiv preprint arXiv:1306.4947 (2013).
  * Liu et al. [2017] W. Liu, B. Dai, A. Humayun, C. Tay, C. Yu, L. B. Smith, J. M. Rehg, L. Song,  Iterative machine teaching,  in: International Conference on Machine Learning, PMLR, 2017, pp. 2149–2158.
  * Liu et al. [2016] J. Liu, X. Zhu, H. Ohannessian,  The teaching dimension of linear learners,  in: International Conference on Machine Learning, PMLR, 2016, pp. 117–126.
  * Goldman and Kearns [1995] S. A. Goldman, M. J. Kearns,  On the complexity of teaching,  Journal of Computer and System Sciences 50 (1995) 20–31.
  * Xu et al. [2021] Z. Xu, B. Chen, C. Li, W. Liu, L. Song, Y. Lin, A. Shrivastava, Locality sensitive teaching, 2021.
  * Polyak [1964] B. T. Polyak,  Some methods of speeding up the convergence of iteration methods,  Ussr computational mathematics and mathematical physics 4 (1964) 1–17.
  * Fei-Fei et al. [2006] L. Fei-Fei, R. Fergus, P. Perona,  One-shot learning of object categories,  IEEE transactions on pattern analysis and machine intelligence 28 (2006) 594–611.
  * Suchan et al. [2021] J. Suchan, M. Bhatt, S. Varadarajan,  Commonsense visual sensemaking for autonomous driving–on generalised neurosymbolic online abduction integrating vision and semantics,  Artificial Intelligence 299 (2021) 103522.
  * Reece and Shafer [1995] D. A. Reece, S. A. Shafer,  Control of perceptual attention in robot driving,  Artificial Intelligence 78 (1995) 397–430.
  * Xie et al. [2022] S. Xie, J. Hu, P. Bhowmick, Z. Ding, F. Arvin,  Distributed motion planning for safe autonomous vehicle overtaking via artificial potential field,  IEEE Transactions on Intelligent Transportation Systems (2022).
  * Lemaignan et al. [2017] S. Lemaignan, M. Warnier, E. A. Sisbot, A. Clodic, R. Alami,  Artificial cognition for social human–robot interaction: An implementation,  Artificial Intelligence 247 (2017) 45–69.
  * Alomari et al. [2022] M. Alomari, F. Li, D. C. Hogg, A. G. Cohn,  Online perceptual learning and natural language acquisition for autonomous robots,  Artificial Intelligence 303 (2022) 103637.
  * Ravi and Larochelle [2016] S. Ravi, H. Larochelle,  Optimization as a model for few-shot learning (2016).
  * Snell et al. [2017] J. Snell, K. Swersky, R. S. Zemel,  Prototypical networks for few-shot learning,  arXiv preprint arXiv:1703.05175 (2017).
  * Duan et al. [2017] Y. Duan, M. Andrychowicz, B. C. Stadie, J. Ho, J. Schneider, I. Sutskever, P. Abbeel, W. Zaremba,  One-shot imitation learning,  arXiv preprint arXiv:1703.07326 (2017).
  * Halmos [1960] P. R. Halmos, Naive set theory, van Nostrand, 1960.
  * Kunen [2014] K. Kunen, Set theory an introduction to independence proofs, Elsevier, 2014.
  * Bourbaki [2006] N. Bourbaki, Théorie des ensembles, Springer, 2006.
  * Bentler and Lee [1978] P. Bentler, S.-Y. Lee,  Matrix derivatives with chain rule and rules for simple, hadamard, and kronecker products,  Journal of Mathematical Psychology 17 (1978) 255–262.
  * Crammer et al. [2006] K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, Y. Singer,  Online passive aggressive algorithms (2006).
  * Khan et al. [2011] F. Khan, B. Mutlu, J. Zhu,  How do humans teach: On curriculum learning and teaching dimension,  in: Advances in neural information processing systems, 2011, pp. 1449–1457.
  * Johns et al. [2015] E. Johns, O. Mac Aodha, G. J. Brostow,  Becoming the expert-interactive multi-class machine teaching,  in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2015, pp. 2616–2624.
  * Barreno et al. [2010] M. Barreno, B. Nelson, A. D. Joseph, J. D. Tygar,  The security of machine learning,  Machine Learning 81 (2010) 121–148.
  * Mei and Zhu [2015] S. Mei, X. Zhu,  The security of latent dirichlet allocation,  in: Artificial Intelligence and Statistics, PMLR, 2015, pp. 681–689.
  * Brochu et al. [2010] E. Brochu, T. Brochu, N. De Freitas,  A bayesian interactive optimization approach to procedural animation design,  in: Proceedings of the 2010 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 2010, pp. 103–112.
  * Cakmak and Thomaz [2011] M. Cakmak, A. L. Thomaz,  Mixed-initiative active learning (2011).
  * Meek et al. [2016] C. Meek, P. Simard, X. Zhu,  Analysis of a design pattern for teaching with features and labels,  arXiv preprint arXiv:1611.05950 (2016).
  * Schmit and Riquelme [2018] S. Schmit, C. Riquelme,  Human interaction with recommendation systems,  in: International Conference on Artificial Intelligence and Statistics, PMLR, 2018, pp. 862–870.
  * Chuang et al. [2020] Y.-S. Chuang, X. Zhang, Y. Ma, M. K. Ho, J. L. Austerweil, X. Zhu,  Using machine teaching to investigate human assumptions when teaching reinforcement learners,  arXiv preprint arXiv:2009.02476 (2020).
  * Zhang et al. [2020] X. Zhang, S. K. Bharti, Y. Ma, A. Singla, X. Zhu,  The sample complexity of teaching-by-reinforcement on q-learning,  arXiv preprint arXiv:2006.09324 (2020).
  * Shinohara and Miyano [1991] A. Shinohara, S. Miyano,  Teachability in computational learning,  New Generation Computing 8 (1991) 337–347.
  * Ben-David and Eiron [1998] S. Ben-David, N. Eiron,  Self-directed learning and its relation to the vc-dimension and to teacher-directed learning,  Machine Learning 33 (1998) 87–104.
  * Zilles et al. [2008] S. Zilles, S. Lange, R. Holte, M. Zinkevich,  Teaching dimensions based on cooperative learning.,  in: COLT, 2008, pp. 135–146.
  * Zilles et al. [2011] S. Zilles, S. Lange, R. Holte, M. Zinkevich, N. Cesa-Bianchi,  Models of cooperative teaching and learning.,  Journal of Machine Learning Research 12 (2011).
  * Chen et al. [2018] Y. Chen, O. Mac Aodha, S. Su, P. Perona, Y. Yue,  Near-optimal machine teaching via explanatory teaching sets,  in: International Conference on Artificial Intelligence and Statistics, PMLR, 2018, pp. 1970–1978.
  * Balbach and Zeugmann [2009] F. J. Balbach, T. Zeugmann,  Recent developments in algorithmic teaching,  in: International Conference on Language and Automata Theory and Applications, Springer, 2009, pp. 1–18.
  * Bengio et al. [2009] Y. Bengio, J. Louradour, R. Collobert, J. Weston,  Curriculum learning,  in: Proceedings of the 26th annual international conference on machine learning, 2009, pp. 41–48.
  * Lessard et al. [2019] L. Lessard, X. Zhang, X. Zhu,  An optimal control approach to sequential machine teaching,  in: The 22nd International Conference on Artificial Intelligence and Statistics, PMLR, 2019, pp. 2495–2503.
  * Hinton et al. [2015] G. Hinton, O. Vinyals, J. Dean,  Distilling the knowledge in a neural network,  arXiv preprint arXiv:1503.02531 (2015).
  * Liu et al. [2021] W. Liu, Z. Liu, H. Wang, L. Paull, B. Schölkopf, A. Weller,  Iterative teaching by label synthesis,  Advances in Neural Information Processing Systems 34 (2021) 21681–21695.
  * Liu et al. [2018] W. Liu, B. Dai, X. Li, Z. Liu, J. Rehg, L. Song,  Towards black-box iterative machine teaching,  in: International Conference on Machine Learning, PMLR, 2018, pp. 3141–3149.
  * Angluin and Kriķis [1997] D. Angluin, M. Kriķis,  Teachers, learners and black boxes,  in: Proceedings of the tenth annual conference on Computational learning theory, 1997, pp. 285–297.
  * Cicalese et al. [2020] F. Cicalese, E. Laber, M. Molinaro, et al.,  Teaching with limited information on the learner’s behaviour,  in: International Conference on Machine Learning, PMLR, 2020, pp. 2016–2026.
  * Hunziker et al. [2018] A. Hunziker, Y. Chen, O. Mac Aodha, M. G. Rodriguez, A. Krause, P. Perona, Y. Yue, A. Singla,  Teaching multiple concepts to a forgetful learner,  arXiv preprint arXiv:1805.08322 (2018).
  * Dasgupta et al. [2019] S. Dasgupta, D. Hsu, S. Poulis, X. Zhu,  Teaching a black-box learner,  in: International Conference on Machine Learning, PMLR, 2019, pp. 1547–1555.
  * Zhou et al. [2020] Y. Zhou, A. R. Nelakurthi, R. Maciejewski, W. Fan, J. He,  Crowd teaching with imperfect labels,  in: Proceedings of The Web Conference 2020, 2020, pp. 110–121.
  * Mosqueira-Rey et al. [2021] E. Mosqueira-Rey, D. Alonso-Ríos, A. Baamonde-Lozano,  Integrating iterative machine teaching and active learning into the machine learning loop,  Procedia Computer Science 192 (2021) 553–562.
  * Göpfert et al. [2020] J. P. Göpfert, U. Kuhl, L. Hindemith, H. Wersing, B. Hammer,  Intuitiveness in active teaching,  arXiv preprint arXiv:2012.13551 (2020).
  * Fan et al. [2018] Y. Fan, F. Tian, T. Qin, X.-Y. Li, T.-Y. Liu,  Learning to teach,  arXiv preprint arXiv:1805.03643 (2018).
  * Kamalaruban et al. [2019] P. Kamalaruban, R. Devidze, V. Cevher, A. Singla,  Interactive teaching algorithms for inverse reinforcement learning,  arXiv preprint arXiv:1905.11867 (2019).
  * Mallinar et al. [2020] N. Mallinar, A. Shah, T. K. Ho, R. Ugrani, A. Gupta,  Iterative data programming for expanding text classification corpora,  in: Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, 2020, pp. 13332–13337.
  * Losey [2018] D. P. Losey, Responding to Physical Human-Robot Interaction: Theory and Approximations, Ph.D. thesis, Rice University, 2018.
  * Yeo et al. [2019] T. Yeo, P. Kamalaruban, A. Singla, A. Merchant, T. Asselborn, L. Faucon, P. Dillenbourg, V. Cevher,  Iterative classroom teaching,  in: Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, 2019, pp. 5684–5692.
  * Han and Zhang [2019] Y. Han, X. Zhang,  Robust federated training via collaborative machine teaching using trusted instances,  arXiv preprint arXiv:1905.02941 (2019).
  * Sanchez et al. [2021] T. Sanchez, B. Caramiaux, J. Françoise, F. Bevilacqua, W. E. Mackay,  How do people train a machine? strategies and (mis) understandings,  Proceedings of the ACM on Human-Computer Interaction 5 (2021) 1–26.
  * Wang et al. [2021] P. Wang, K. Nagrecha, N. Vasconcelos,  Gradient-based algorithms for machine teaching,  in: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021, pp. 1387–1396.
  * Wang and Vasconcelos [2021] P. Wang, N. Vasconcelos,  A machine teaching framework for scalable recognition,  in: Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021, pp. 4945–4954.
  * Vinyals et al. [2016] O. Vinyals, C. Blundell, T. Lillicrap, D. Wierstra, et al.,  Matching networks for one shot learning,  Advances in neural information processing systems 29 (2016) 3630–3638.
  * Wang et al. [2020] Y. Wang, Q. Yao, J. T. Kwok, L. M. Ni,  Generalizing from a few examples: A survey on few-shot learning,  ACM computing surveys (csur) 53 (2020) 1–34.
  * Pan et al. [2020] C. Pan, J. Huang, J. Gong, C. Chen,  Teach machine to learn: hand-drawn multi-symbol sketch recognition in one-shot,  Applied Intelligence 50 (2020) 2239–2251.
  * Bajracharya et al. [2020] M. Bajracharya, J. Borders, D. Helmick, T. Kollar, M. Laskey, J. Leichty, J. Ma, U. Nagarajan, A. Ochiai, J. Petersen, et al.,  A mobile manipulation system for one-shot teaching of complex tasks in homes,  in: 2020 IEEE International Conference on Robotics and Automation (ICRA), IEEE, 2020, pp. 11039–11045.
  * Rezende et al. [2016] D. Rezende, I. Danihelka, K. Gregor, D. Wierstra, et al.,  One-shot generalization in deep generative models,  in: International conference on machine learning, PMLR, 2016, pp. 1521–1529.
  * Tjandra et al. [2018] A. Tjandra, S. Sakti, S. Nakamura,  Machine speech chain with one-shot speaker adaptation,  arXiv preprint arXiv:1803.10525 (2018).
  * Schwartz et al. [2018] E. Schwartz, L. Karlinsky, J. Shtok, S. Harary, M. Marder, A. Kumar, R. Feris, R. Giryes, A. Bronstein,  Delta-encoder: an effective sample synthesis method for few-shot object recognition,  Advances in neural information processing systems 31 (2018).
  * Chen et al. [2019] Z. Chen, Y. Fu, Y. Zhang, Y.-G. Jiang, X. Xue, L. Sigal,  Multi-level semantic feature augmentation for one-shot learning,  IEEE Transactions on Image Processing 28 (2019) 4594–4605.
  * Mitchell and Mitchell [1997] T. M. Mitchell, T. M. Mitchell, Machine learning, volume 1, McGraw-hill New York, 1997.
  * Salakhutdinov et al. [2012] R. Salakhutdinov, J. B. Tenenbaum, A. Torralba,  Learning with hierarchical-deep models,  IEEE transactions on pattern analysis and machine intelligence 35 (2012) 1958–1971.
  * Lake et al. [2015] B. M. Lake, R. Salakhutdinov, J. B. Tenenbaum,  Human-level concept learning through probabilistic program induction,  Science 350 (2015) 1332–1338.
  * McCullagh and Nelder [2019] P. McCullagh, J. A. Nelder, Generalized linear models, Routledge, 2019\.
  * Shawe-Taylor et al. [2004] J. Shawe-Taylor, N. Cristianini, et al., Kernel methods for pattern analysis, Cambridge university press, 2004.
  * Hofmann et al. [2008] T. Hofmann, B. Schölkopf, A. J. Smola,  Kernel methods in machine learning,  The annals of statistics 36 (2008) 1171–1220.
  * Li et al. [2014] M. Li, T. Zhang, Y. Chen, A. J. Smola,  Efficient mini-batch training for stochastic optimization,  in: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 2014, pp. 661–670.
  * Feldman [1976] K. A. Feldman,  The superior college teacher from the students’ view,  Research in higher education 5 (1976) 243–288.
  * Shishavan and Sadeghi [2009] H. B. Shishavan, K. Sadeghi,  Characteristics of an effective english language teacher as perceived by iranian teachers and learners of english.,  English language teaching 2 (2009) 130–143.
  * Queipo et al. [2005] N. V. Queipo, R. T. Haftka, W. Shyy, T. Goel, R. Vaidyanathan, P. K. Tucker,  Surrogate-based analysis and optimization,  Progress in aerospace sciences 41 (2005) 1–28.
  * LeCun [1998] Y. LeCun,  The mnist database of handwritten digits,  http://yann. lecun. com/exdb/mnist/ (1998).
  * Krizhevsky et al. [????] A. Krizhevsky, V. Nair, G. Hinton,  Cifar-10 (canadian institute for advanced research) (????). URL: http://www.cs.toronto.edu/~kriz/cifar.html.
  * Shannon [2001] C. E. Shannon,  A mathematical theory of communication,  ACM SIGMOBILE mobile computing and communications review 5 (2001) 3–55.
  * Kampffmeyer et al. [2016] M. Kampffmeyer, A.-B. Salberg, R. Jenssen,  Semantic segmentation of small objects and modeling of uncertainty in urban remote sensing images using deep convolutional neural networks,  in: Proceedings of the IEEE conference on computer vision and pattern recognition workshops, 2016, pp. 1–9.
  * Kendall et al. [2018] A. Kendall, V. Badrinarayanan, R. Cipolla, Segnet: Model uncertainty in deep convolutional encoder-decoder architectures for scene understanding, 2018\.
  * Settles [2009] B. Settles,  Active learning literature survey (2009).