Online Machine Teaching under Uncertainty about the Learner
Belen Martin Urcelay
Abstract:
Machine teaching is a subfield of artificial intelligence employed to find the sample selection policy that can teach a known target concept to a machine learning algorithm with the least number of examples possible. Online machine teaching algorithms usually assume that the entity selecting the examples has absolute knowledge about the learner status, making its implementation often unrealistic. We relax this omniscience assumption by proving that efficient machine teaching is possible even when the teacher is uncertain about the learner’s state. Our analysis holds for learners, with unknown initializations, that perform gradient descent of a quadratic loss to learn a linear classifier. We propose an online algorithm in which the teacher simultaneously learns about the learner’s state while teaching the learner. We theoretically and empirically show that the learner’s mean square error decreases exponentially with the number of examples, thus achieving performance similar to the omniscient case.