Teaching an Active Learner with Contrastive Examples

We study the problem of active learning with the added twist that the learner is assisted by a helpful teacher. We consider the following natural interaction protocol: At each round, the learner proposes a query asking for the label of an instance x q, the teacher provides the requested label \{x q, y q\} along with explanatory information to guide the learning process. In this paper, we view this information in the form of an additional contrastive example ( \{x c, y c\}) where x c is picked from a set constrained by x q (e.g., dissimilar instances with the same label). Our focus is to design a teaching algorithm that can provide an informative sequence of contrastive examples to the learner to speed up the learning process. We show that this leads to a challenging sequence optimization problem where the algorithm's choices at a given round depend on the history of interactions.