Prototype selection for interpretable classification

By Jacob Bien, Robert Tibshirani. 2011

287 citations recorded by the source corpus.

We discuss a method for selecting prototypes in the classification setting (in which the samples fall into known discrete categories). Our method of focus is derived from three basic properties that we believe a good prototype set should satisfy. This intuition is translated into a set cover optimization problem, which we solve approximately using standard approaches. While prototype selection is usually viewed as purely a means toward building an efficient classifier, in this paper we emphasize the inherent value of having a set of prototypical elements. That said, by using the nearest-neighbor rule on the set of prototypes, we can of course discuss our method as a classifier as well. We demonstrate the interpretative value of producing prototypes on the well-known USPS ZIP code digits data set and show that as a classifier it performs reasonably well. We apply the method to a proteomics data set in which the samples are strings and therefore not naturally embedded in a vector space. Our method is compatible with any dissimilarity measure, making it amenable to situations in which using a non-Euclidean metric is desirable or even necessary.

Subfields: Artificial Intelligence, Statistics and Probability

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

In Statistics and Probability

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, background): “Generalized additive models (GAMs) were introduced to present a flexible extension of generalized linear models (GLMs) (Nelder and Wedderburn, 1972), allowing for arbitrary functions for modeling the influence of each feature on a response (Hastie and Tibshirani 1990 see also Wood 2017).”
Peeking Inside the Black-Box: A Survey on Explainable Artificial Intelligence (XAI) (2018, background): “Prototypes are a selection of representative instances from the data [133]–[135], thus item membership is determined by its similarity to the prototypes which leads to overgeneralization.”
Deep k-Nearest Neighbors: Towards Confident, Interpretable and Robust Deep Learning (2018, background): “A by-product of the approach introduced in Section IV is that it returns exemplar inputs, also called prototypes [55], [56], to interpret predictions through training points that best explain the model’s output because they are processed similarly to the”
A Survey of Methods for Explaining Black Box Models (2018, background): “Design DR - TAB X X PS [8] Bien et al.”
The Bayesian Case Model: A Generative Approach for Case-Based Reasoning and Prototype Classification (2014, methodology): “, nearest neighbors [10] or a supervised optimization-based method [5]).”
This looks like that: deep learning for interpretable image recognition (2018, methodology): “Our work relates closely to other prototype classification techniques in machine learning [32, 2, 45], and very closely, to the Bayesian Case Model [18].”
Interpretable 3D Human Action Analysis with Temporal Convolutional Networks (2017, background): “Example-based explanations and classifiers have shown to offer a condensed view of a dataset, potentially offering a reason why a classifier came to a certain conclusion through other data points in the dataset [33].”
Methods and Models for Interpretable Linear Classification (2014, methodology): “The interpretability of black-box models is mainly improved by auxiliary methods that extract rules and prototype examples to illustrate the relationship between input variables and the predicted outcome [78, 111, 40, 76, 11].”
Metadata Archaeology: Unearthing Data Subsets by Leveraging Training Dynamics (2022, methodology): “The aim of these methods is to find prototypical examples that represent a larger corpus of data (Zhang, 1992; Bien and Tibshirani, 2012; Kim et al., 2015; Kim et al., 2016), which can be used to speed up training (Sener and Savarese, 2018; Shim et al., 2021; Huggins et al., 2017; Sorscher et al.,…”
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].”
This Looks Like That: Deep Learning for Interpretable Image Recognition (2018, unknown): “Our work also relates closely to other prototype classification techniques in machine learning [25, 3, 14, 5].”
ProtoDash: Fast Interpretable Prototype Selection (2017, background): “The strategies involve building rule/decision lists [20, 19], to finding prototypes [12] in an unsupervised manner like us or strictly in a supervised manner as [2], to taking inspiration from psychometrics [10] and learning understandable models.”
A Bayesian Approach to Learning Scoring Systems (2015, methodology): “Other methods (Meinshausen, 2010; Van Assche and Blockeel, 2007; Fung, Sandilya, and Rao, 2005; Martens et al., 2007; Bien and Tibshirani, 2011) extract rules and prototype examples to illustrate the relationship between input variables and the predicted outcome.”
Attention-Based Prototypical Learning Towards Interpretable, Confident and Robust Deep Neural Networks (2019, methodology): “Prototype selection in its naive form is computationally expensive and perceptually challenging (Bien & Tibshirani, 2012).”
Black Box Explanation by Learning Image Exemplars in the Latent Feature Space (2019, methodology): “In the following experiment we generated n exemplars and counter-exemplars with abele , and we selected n prototypes and criticisms using mmd [18] and k-medoids [2].”