  In this paper, we make an important step towards the black-box machine
teaching by considering the cross-space machine teaching, where the teacher and
the learner use different feature representations and the teacher can not fully
observe the learner's model. In such scenario, we study how the teacher is
still able to teach the learner to achieve faster convergence rate than the
traditional passive learning. We propose an active teacher model that can
actively query the learner (i.e., make the learner take exams) for estimating
the learner's status and provably guide the learner to achieve faster
convergence. The sample complexities for both teaching and query are provided.
In the experiments, we compare the proposed active teacher with the omniscient
teacher and verify the effectiveness of the active teacher model.
