Adaptive Teaching of Temporal Logic Formulas to Preference-based Learners

Authors

  • Zhe Xu Arizona State University
  • Yuxin Chen University of Chicago
  • Ufuk Topcu University of Texas at Austin

Keywords:

Neuro-Symbolic AI (NSAI)

Abstract

Machine teaching is an algorithmic framework for teaching a target hypothesis via a sequence of examples or demonstrations. We investigate machine teaching for temporal logic formulas—a novel and expressive hypothesis class amenable to time-related task specifications. In the context of teaching temporal logic formulas, an exhaustive search even for a myopic solution takes exponential time (with respect to the time span of the task). We propose an efficient approach for teaching parametric linear temporal logic formulas. Concretely, we derive a necessary condition for the minimal time length of a demonstration to eliminate a set of hypotheses. Utilizing this condition, we propose an efficient myopic teaching algorithm by solving a sequence of integer programming problems. We further show that, under two notions of teaching complexity, the proposed algorithm has near-optimal performance. We evaluate our algorithm extensively under different classes of learners (i.e., learners with different preferences over hypotheses) and interaction protocols (e.g., non-adaptive and adaptive). Our results demonstrate the effectiveness of the proposed algorithm in teaching temporal logic formulas; in particular, we show that there are significant gains of teaching efficacy when the teacher adapts to feedback of the learner, or adapts to a (non-myopic) oracle.

Downloads

Published

2021-05-18

How to Cite

Xu, Z., Chen, Y., & Topcu, U. (2021). Adaptive Teaching of Temporal Logic Formulas to Preference-based Learners. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6), 5061-5068. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16640

Issue

Section

AAAI Technical Track Focus Area on Neuro-Symbolic AI