Algorithmic machine teaching studies the interaction between a teacher and a
learner where the teacher selects labeled examples aiming at teaching a target
hypothesis. In a quest to lower teaching complexity and to achieve more natural
teacher-learner interactions, several teaching models and complexity measures
have been proposed for both the batch settings (e.g., worst-case, recursive,
preference-based, and non-clashing models) as well as the sequential settings
(e.g., local preference-based model). To better understand the connections
between these different batch and sequential models, we develop a novel
framework which captures the teaching process via preference functions
$\Sigma$. In our framework, each function $\sigma \in \Sigma$ induces a
teacher-learner pair with teaching complexity as $\TD(\sigma)$. We show that
the above-mentioned teaching models are equivalent to specific types/families
of preference functions in our framework. This equivalence, in turn, allows us
to study the differences between two important teaching models, namely $\sigma$
functions inducing the strongest batch (i.e., non-clashing) model and $\sigma$
functions inducing a weak sequential (i.e., local preference-based) model.
Finally, we identify preference functions inducing a novel family of sequential
models with teaching complexity linear in the VC dimension of the hypothesis
class: this is in contrast to the best known complexity result for the batch
models which is quadratic in the VC dimension.

该研究探索了算法机器教学中的不同教学模型和复杂度量度以及它们之间的联系，并提出了一种通过偏好函数刻画教学过程的新框架，通过比较不同的偏好函数诱导出的两种教学模型，即最强的批处理模型和较弱的顺序模型，并鉴别出诱导出 VC 维度为线性的新型顺序模型的偏好函数，其复杂度结果比最佳批处理模型的 VC 维度的复杂度结果是二次的得到了十分有力的补充。