Preference-Based Batch and Sequential Teaching: Towards a Unified View of Models
Preference-Based Batch and Sequential Teaching: Towards a Unified View of Models
复制标题
DOI：
--
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Farnam Mansouri;Yuxin Chen;A. Vartanian;Xiaojin Zhu;A. Singla
中科院分区：
文献类型：
--
作者：
Farnam Mansouri;Yuxin Chen;A. Vartanian;Xiaojin Zhu;A. Singla
数学机器教学研究教师和学习者之间的互动，教师选择标记的例子，旨在教授目标假设。在寻求降低教学复杂性和实现更自然的教师-学习者交互的过程中，已经针对批量设置（例如，最坏情况、递归、基于偏好和非冲突模型）以及顺序设置（例如，基于局部偏好的模型）。为了更好地理解这些不同的批处理和顺序模型之间的连接，我们开发了一个新的框架，通过偏好函数$\Sigma$捕捉教学过程。在我们的框架中，每一个函数$\sigma \in \Sigma$都会产生一个教学复杂度为$\TD（\sigma）$的师生对。我们表明，上述教学模式是等价的特定类型/家庭的偏好函数在我们的框架。这种等价性，反过来，使我们能够研究两个重要的教学模型之间的差异，即诱导最强批次的$\sigma$函数（即，非冲突）模型和引起弱序列（即，基于局部偏好的）模型。最后，我们确定的偏好函数，诱导一个新的家庭的顺序模型与教学的复杂性线性的VC维的假设类：这是在对比最知名的复杂性结果的批次模型是二次的VC维。
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.