Title: ProtoDash: Fast Interpretable Prototype Selection,
Abstract: In this paper we propose an efficient algorithm ProtoDash for selecting
prototypical examples from complex datasets. Our generalizes the learn to
criticize (L2C) work by Kim et al. (2016) to not only select prototypes for a
given sparsity level $m$ but also to associate non-negative (for
interpretability) weights with each of them indicative of the importance of
each prototype. This extension provides a single coherent framework under which
both prototypes and criticisms can be found. Furthermore, our framework works
for any symmetric positive definite kernel thus addressing one of the key open
questions laid out in Kim et al. (2016). Our additional requirement of learning
non-negative weights no longer maintains submodularity of the objective as in
the previous work, however, we show that the problem is weakly submodular and
derive approximation guarantees for our fast ProtoDash algorithm. We
demonstrate the efficacy of our method on diverse domains such as retail, digit
recognition (MNIST) and on publicly available 40 health questionnaires obtained
from the Center for Disease Control (CDC) website maintained by the US Dept. of
Health. We validate the results quantitatively as well as qualitatively based
on expert feedback and recently published scientific studies on public health,
thus showcasing the power of our method in providing actionability (for
retail), utility (for MNIST) and insight (on CDC datasets), which presumably
are the hallmark of an effective interpretable method.