Efficient Data Representation by Selecting Prototypes with Importance Weights

By Karthik S. Gurumoorthy, Amit Dhurandhar, Guillermo A. Cecchi, Charu C. Aggarwal. 2017

123 citations recorded by the source corpus.

Prototypical examples that best summarize and compactly represent an underlying complex data distribution, communicate meaningful insights to humans in domains where simple explanations are hard to extract. In this paper, we present algorithms with strong theoretical guarantees to mine these data sets and select prototypes, a.k.a. representatives that optimally describes them. Our work notably generalizes the recent work by Kim et al. (2016) where in addition to selecting prototypes, we also associate non-negative weights which are indicative of their importance. This extension provides a single coherent framework under which both prototypes and criticisms (i.e. outliers) 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). By establishing that our objective function enjoys a key property of that of weak submodularity, we present a fast ProtoDash algorithm and also derive approximation guarantees for the same. 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 technique in providing actionability (for retail), utility (for MNIST), and insight (on CDC datasets), which arguably are the hallmarks of an effective interpretable machine learning method.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Causal Interpretability for Machine Learning - Problems, Methods and Evaluation (2020, methodology): “[37] extend this method and designed a fast prototype selection algorithm called ProtoDash to not only select the prototypes and criticism instances, but also output non-negative weights indicating their importance.”
Selective Brain Damage: Measuring the Disparate Impact of Model Pruning (2019, background): “PIE could be used to surface atypical examples for further human inspection [48], choose not to classify certain examples when the model is uncertain [2, 10, 9, 11], or to aid interpretability as a case based reasoning tool to explain model behavior [41, 23, 4, 33].”
Explainable AI: A Review of Machine Learning Interpretability Methods (2020, background): “Protodash: the work that was detailed in [55] regarding prototypes was extended in [56] by associating non-negative weightings to prototypes corresponding to their contribution, consequently creating a unifying coherent framework for both prototypes and criticisms/outliers.”
Benchmarking and survey of explanation methods for black box models (2021, methodology): “Regarding the local post-hoc explanations, different methods are implemented, such as lime [102], shap [84], cem [40], cem-maf [85] and protodash [61]).”
Human-Centered Explainable AI (XAI): From Algorithms to User Experiences (2021, background): “Why (a given prediction) •Describe how features of the instance, or what key features, determine the model’s prediction of it∗ • Or describe rules that the instance fits to guarantee the prediction† • Or show similar examples with the same predicted outcome to justify the model’s prediction‡ LIME∗ [”
Sequential Explanations with Mental Model-Based Policies (2020, methodology): “We compared three experimental policies in selecting explanations generated by prototype (Kim et al., 2016; Gurumoorthy et al., 2017) and deep Taylor decomposition saliency map (Montavon et al., 2017) explainers, relative to random selection baselines.”
Interpreting Black-Box Models: A Review on Explainable Artificial Intelligence (2023, methodology): “From a research point of view, some of the widely accepted example-based interpretability techniques are the following: Prototypes and Criticisms Prototypes are a group of chosen examples that accurately depict all the data [140–142].”
One Explanation Does Not Fit All: A Toolkit and Taxonomy of AI Explainability Techniques (2019, methodology): “Feature importance The base algorithms for both ProtoDash [26] and CEM [18] do not return feature importances.”
A Survey on the Explainability of Supervised Machine Learning (2020, methodology): “ProtoDash (Gurumoorthy et al., 2017) is an approach for selecting prototypical examples from complex data sets that extends the work from Kim et al. (2016) by non-negative weights for the importance of each prototype.”