TY - JOUR
AU - Xu, Zhe
AU - Chen, Yuxin
AU - Topcu, Ufuk
PY - 2021/05/18
Y2 - 2024/06/18
TI - Adaptive Teaching of Temporal Logic Formulas to Preference-based Learners
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 35
IS - 6
SE - AAAI Technical Track Focus Area on Neuro-Symbolic AI
DO - 10.1609/aaai.v35i6.16640
UR - https://ojs.aaai.org/index.php/AAAI/article/view/16640
SP - 5061-5068
AB - Machine teaching is an algorithmic framework for teaching atarget hypothesis via a sequence of examples or demonstrations.We investigate machine teaching for temporal logicformulasâ€”a novel and expressive hypothesis class amenableto time-related task specifications. In the context of teachingtemporal logic formulas, an exhaustive search even for a myopicsolution takes exponential time (with respect to the timespan of the task). We propose an efficient approach for teachingparametric linear temporal logic formulas. Concretely,we derive a necessary condition for the minimal time lengthof a demonstration to eliminate a set of hypotheses. Utilizingthis condition, we propose an efficient myopic teaching algorithmby solving a sequence of integer programming problems.We further show that, under two notions of teachingcomplexity, the proposed algorithm has near-optimal performance.We evaluate our algorithm extensively under differentclasses of learners (i.e., learners with different preferencesover hypotheses) and interaction protocols (e.g., non-adaptiveand adaptive). Our results demonstrate the effectiveness ofthe proposed algorithm in teaching temporal logic formulas;in particular, we show that there are significant gains ofteaching efficacy when the teacher adapts to feedback of thelearner, or adapts to a (non-myopic) oracle.
ER -