  Predictive models deployed in the real world may assign incorrect labels to
instances with high confidence. Such errors or unknown unknowns are rooted in
model incompleteness, and typically arise because of the mismatch between
training data and the cases encountered at test time. As the models are blind
to such errors, input from an oracle is needed to identify these failures. In
this paper, we formulate and address the problem of informed discovery of
unknown unknowns of any given predictive model where unknown unknowns occur due
to systematic biases in the training data. We propose a model-agnostic
methodology which uses feedback from an oracle to both identify unknown
unknowns and to intelligently guide the discovery. We employ a two-phase
approach which first organizes the data into multiple partitions based on the
feature similarity of instances and the confidence scores assigned by the
predictive model, and then utilizes an explore-exploit strategy for discovering
unknown unknowns across these partitions. We demonstrate the efficacy of our
framework by varying the underlying causes of unknown unknowns across various
applications. To the best of our knowledge, this paper presents the first
algorithmic approach to the problem of discovering unknown unknowns of
predictive models.
