A Caltech Library Service

Barrier Certificates for Assured Machine Teaching

Ahmadi, Mohamadreza and Wu, Bo and Chen, Yuxin and Yue, Yisong and Topcu, Ufuk (2019) Barrier Certificates for Assured Machine Teaching. In: 2019 American Control Conference (ACC). IEEE , Piscataway, NJ, pp. 3658-3663. ISBN 978-1-5386-7926-5.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Machine teaching can be viewed as optimal control for learning. Given a learner's model, machine teaching aims to determine the optimal training data to steer the learner towards a target hypothesis. In this paper, we are interested in providing assurances for machine teaching algorithms using control theory. In particular, we study a well-established learner's model in the machine teaching literature that is captured by the local preference over a version space. We interpret the problem of teaching a preference-based learner as solving a partially observable Markov decision process (POMDP). We then show that the POMDP formulation can be cast as a special hybrid system, i.e., a discrete-time switched system. Subsequently, we use barrier certificates to verify set-theoric properties of this special hybrid system. We show how the computation of the barrier certificate can be decomposed and numerically implemented as the solution to a sum-of-squares (SOS) program. For illustration, we show how the proposed framework based on control theory can be used to verify the teaching performance of two well-known machine teaching methods.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Ahmadi, Mohamadreza0000-0003-1447-3012
Yue, Yisong0000-0001-9127-1989
Additional Information:© 2019 AACC. This work was supported by AFOSR FA9550-19-1-0005, DARPA D19AP00004, NSF 1646522 and NSF 1652113.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-19-1-0005
Defense Advanced Research Projects Agency (DARPA)D19AP00004
Record Number:CaltechAUTHORS:20190205-102249789
Persistent URL:
Official Citation:M. Ahmadi, B. Wu, Y. Chen, Y. Yue and U. Topcu, "Barrier Certificates for Assured Machine Teaching," 2019 American Control Conference (ACC), Philadelphia, PA, USA, 2019, pp. 3658-3663. URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:92662
Deposited By: Tony Diaz
Deposited On:05 Feb 2019 19:03
Last Modified:02 Jun 2023 00:42

Repository Staff Only: item control page