Source-linked AI summary
Prototype selection for interpretable classification
Jacob Bien, Robert Tibshirani
TL;DR
Large data sets make exhaustive inspection difficult, motivating prototypes as an interpretable sparse-in-samples summary for classification. The paper selects class-specific prototypes through a set cover optimization based on within-class coverage, cross-class avoidance, and sparsity, then uses nearest-prototype classification. The resulting method provides interpretable summaries, performs competitively with nearest-neighbor methods in the reported experiments, and supports non-Euclidean dissimilarities.
Problem
Large data sets can make examining all examples overwhelming or infeasible, motivating interpretable summaries based on sparsity in samples rather than variables.
Method
The method selects class-specific prototypes by approximately solving a set cover optimization that balances same-class coverage, avoidance of other classes, and prototype sparsity, using nearest-prototype classification.
Results
The method provides interpretable prototype summaries and performs as well as or better than 1-NN in most reported data-set comparisons, while using significantly fewer prototypes.
Takeaways & Limitations
Prototypes retain actual data examples that help specialists understand a data set and why a nearest-prototype prediction was made, while accommodating problem-specific dissimilarities.
Takeaways & Limitations
The LP relaxation with randomized rounding can be relatively slow and memory-intensive for large data sets, motivating a computationally easier preferred method.
Abstract
from arXiv · showhide
Prototype methods seek a minimal subset of samples that can serve as a distillation or condensed view of a data set. As the size of modern data sets grows, being able to present a domain specialist with a short list of "representative" samples chosen from the data set is of increasing interpretative value. While much recent statistical research has been focused on producing sparse-in-the-variables methods, this paper aims at achieving sparsity in the samples. 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.
1. Introduction.
The paper pursues interpretability through sparsity in samples, selecting representative examples from each class rather than sparse subsets of variables. Its prototypes summarize data, support nearest-prototype classification, and are chosen to cover within-class variability while avoiding cross-class confusion.
- Motivation: Prototype selection seeks a small subset of samples that can summarize a large labeled data set for domain specialists.The goal is interpretative value when examining all examples is overwhelming or infeasible.
- Contribution: The paper targets interpretability through sparsity in samples, contrasting with methods that select predictive subsets of variables.For handwritten digits, the method selects images rather than pixels.
- Prototype principle: The prototype sets are designed to capture a class’s variability while avoiding examples that could be confused with another class.The digit “7” example illustrates preserving serif variation while avoiding “7” images resembling “1.”
- Prototype principle: For each class, prototypes should be close to many same-class training points and far from points in other classes.This criterion is intended to capture the ordinary meaning of “prototypical.”
- Classification: Given prototype sets, a new observation is classified by the class containing its nearest prototype.When every labeled training point is used as a prototype, this rule reduces to 1-NN.
- Classification: The method’s main classifier strength is explaining why a prediction was made, while its classifier performance is described as reasonable.The prototypes provide a lighter-weight representation than the full training set.
- Approach: The paper formulates prototype selection as an optimization problem, reduces it to separate set cover problems, and presents two approximation algorithms.The paper also discusses application considerations and empirical evaluations on digits and proteomics data.
2. Formulation as an optimization problem.
The formulation encodes prototypicality as selective geometric coverage: prototypes should cover same-class points, avoid covering other classes, and remain sparse. This leads to a relaxed prize-collecting set cover formulation, solved separately by class with prototype cost controlled by λ.
- 2. Formulation as an optimization problem.: The method begins with three principles: cover same-class points, avoid covering other classes, and use as few prototypes as possible.The optimization uses a slightly relaxed version of these desired properties.
- 2.1. The intuition.: For a fixed ε, each prototype defines an ε-ball, and the selected balls induce partial covers of the training points.Figure 1 varies ε from the smallest value to approximately the median interpoint distance.
- 2.1. The intuition.: The desired cover maximizes coverage of same-class points, minimizes coverage of other classes, and remains sparse for the chosen ε.These criteria translate the informal notion of a prototype set into geometric terms.
- 2.1. The intuition.: The geometric selection problem reduces to set cover, which seeks the smallest subset of candidate-centered balls covering all points.The distance function d need not be a metric.
- 2.2. The set cover integer program.: The set cover integer program uses binary indicators to choose prototype centers and requires each point to be covered by at least one selected ball.A feasible solution places at least one prototype within ε of every training point.
- 2.2. The set cover integer program.: Because avoiding wrong-class coverage may require leaving some same-class points uncovered, the classification problem uses prize-collecting set cover with coverage penalties and prototype costs.This permits a minimum-cost partial cover rather than enforcing complete coverage.
- 2.3. From intuition to integer program.: Binary variables α_j^(l) indicate whether training point x_j is selected as a prototype for class l, while ξ_i and η_i encode missed and wrong-class coverage.ξ_i indicates no nearby prototype of the true class; η_i counts nearby prototypes from other classes.
- 2.3. From intuition to integer program.: The parameter λ controls prototype cost and therefore the number of selected prototypes; λ = 1/n generally makes sparsity a tie-breaker.The objective combines uncovered points, wrongly covered points, and prototype cost.
3. Solving the problem: Two approaches.
The paper develops two approximate approaches for the set-cover formulation of prototype selection: LP relaxation with randomized rounding and a deterministic greedy algorithm. The greedy method is computationally easier and preferred in practice, while randomized rounding offers an O(log|X_l|)-factor approximation for each class.
- Optimization framework: Set cover is NP-hard, so the prototype-selection integer program is solved approximately rather than exactly.The formulation can be transformed into standard set cover, for which exact polynomial-time optimization is not expected.
- LP relaxation with randomized rounding: LP relaxation replaces integer constraints with continuous variables, then rounds them probabilistically and unions partial covers across O(log|X_l|) iterations.The randomized procedure is applied separately to each class.
- LP relaxation with randomized rounding: O(log|X_l|) approximation is obtained for each class, yielding an overall O(K log N)-factor approximation to the full problem.The algorithm repeats when feasibility or the objective bound is not achieved; the stated probability of repetition is less than 1/2.
- Comparison in practice: The greedy approach is deterministic, computationally easier, and preferred because LP rounding can be slow and memory-intensive on large data sets.Figure 2 compares the methods on digits using running time and resulting integer-program objective, though timing depends on implementation and hardware.
- A greedy approach: The greedy algorithm adds the prototype-class pair with the best trade-off between covering same-class points and avoiding wrong-class coverage.Its incremental objective is Δξ(x_j,l) − Δη(x_j,l) − λ, and additions continue while the improvement is positive.
4. Problem-specific considerations.
The method can be tailored through dissimilarity choices and by expanding the candidate prototype set beyond labeled training points. These extensions preserve example-based prototypes while supporting non-vector data and high-dimensional settings.
- Dissimilarities: The method uses features only through pairwise dissimilarities, so kernel-based or non-Euclidean distances can be used.This permits application when data are not naturally embedded in a vector space, provided pairwise dissimilarities are available.
- Candidate prototype sets: In semi-supervised learning, unlabeled points Z can serve as candidate prototypes instead of restricting prototypes to the labeled training set X.The selected prototypes remain actual examples rather than arbitrary points in R^p.
- Candidate prototype sets: Adding K-means centroids to the candidate set can help in high-dimensional problems where restricting prototypes to observed data points suffers from the curse of dimensionality.This extension sacrifices the requirement that every prototype be an observed example if centroids are included.
5. Related work.
Related work spans prototype condensation, set-cover-based classification, clustering, and geometric representation methods. The paper distinguishes its approach primarily by treating prototypes as an interpretative aid for understanding large labeled data sets, rather than only as a classification preprocessing device.
- Interpretative goal: The paper differs from related classification-oriented methods in seeking an interpretative aid for analysts making sense of large labeled data sets.The authors note that other proposals might also be adapted for this purpose.
- The set covering machine: The paper’s set-cover formulation closely corresponds to the set covering machine when balls centered at positive points define the candidate functions.The class-specific problems decouple into forms equivalent to the set covering machine’s binary optimization problem.
- Condensation and data editing: Earlier condensation and data-editing methods also select subsets of training data, including the condensed nearest-neighbor rule and multiedit.Hart’s minimal consistent subset targets zero training error under nearest-prototype classification.
- Condensation versus interpretation: Condensation methods tend to retain class-boundary points, whereas this method retains examples from more homogeneous regions.The contrast reflects different goals: classification-oriented reduction versus data interpretation.
- Clustering methods: K-means and K-medoids can produce class-specific prototypes, but K-means prototypes need not lie on training points while K-medoids prototypes do.Allowing prototypes anywhere in R^p can improve classification error, according to the comparison presented.
- Other prototype methods: In the digits example, the relative number of prototypes selected for each class reveals that some classes are substantially more complex than others.The paper connects this observation to the broader study of data-set complexity.
6. Examples on simulated and real data.
Experiments on simulated, handwritten-digit, protein, and UCI data show that prototype selection can preserve classification performance while providing an interpretable sample-based representation. The selected prototypes also reveal class variability and structure through visualizations and class-specific selection patterns.
- Mixture of Gaussians simulation: On a three-class Gaussian mixture, prototype selection and LVQ capture the Bayes boundary shape, whereas K-medoids produces an erratic boundary under class overlap.K-medoids chooses prototypes without accounting for other classes, which explains its poorer boundary in the overlapping setting.
- ZIP code digits data: 2.49% test error is achieved by the 3,372-prototype solution, compared with 3.09% for 1-NN.Across a wide range of ε values, the method attains error comparable to 1-NN with substantially fewer prototypes.
- ZIP code digits data: The method adapts prototype counts to class variability, retaining only seven of 1,005 digit-1 examples because digit 1 has unusually low tangent-distance variation.Using equal-radius balls causes more variable classes to receive more prototypes.
- ZIP code digits data: The prototypes are sharper and more varied than K-means centroids because they are individual training images rather than averages.The comparison uses approximately 100 prototypes selected by tuning ε.
- ZIP code digits data: The greedy displays show each prototype’s newly correctly covered images, miscovered points, tangent-distance layout, and coverage-based visual prominence.The first prototype, a handwritten “1,” correctly covered 986 training images of 1’s and miscovered four non-1 images.
- Protein classification with string kernels: For protein data, the minimum cross-validation error is 1.76% with about 870 prototypes, matching the tuned support vector machine’s minimum cross-validation error.The selected solution contains 26 of 45 Positive samples and 907 of 1,663 Negative samples.
7. Discussion.
The paper presents prototype selection as a straightforward way to summarize data by choosing actual samples, using a set cover formulation solved with standard approximation algorithms. Its discussion emphasizes automatic class-wise prototype allocation, compatibility with problem-specific dissimilarities, and interpretability for domain experts.
- The procedure selects prototypical samples to provide a simple summary of a data set.
- The authors formulate their notion of a desirable prototype set as a set cover problem and solve it with two standard approximation algorithms.
- The method automatically chooses a suitable number of prototypes for each class and can use a problem-specific dissimilarity.
- Because prototypes are actual elements of X, they can represent concrete patients, genes, or hand-drawn images for domain experts.
- Prototype selection is separable by class and equivalent to solving L prize-collecting set cover problems.