A Caltech Library Service

Barrier Certificates for Assured Machine Teaching

Ahmadi, Mohamadreza and Wu, Bo and Chen, Yuxin and Yue, Yisong and Topcu, Ufuk (2018) Barrier Certificates for Assured Machine Teaching. . (Submitted)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Machine teaching has received significant attention in the past few years as a paradigm shift from machine learning. While machine learning is often concerned with improving the performance of learners, machine teaching pertains to the efficiency of teachers. For example, machine teaching seeks to find the optimal (minimum) number of data samples needed for teaching a target hypothesis to a learner. Hence, it is natural to raise the question of how can we provide assurances for teaching given a machine teaching algorithm. In this paper, we address this question by borrowing notions from control theory. We begin by proposing a model based on partially observable Markov decision processes (POMDPs) for a class of machine teaching problems. 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 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:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Record Number:CaltechAUTHORS:20190205-102249789
Persistent 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:05 Feb 2019 19:03

Repository Staff Only: item control page