Classification by Set Cover: The Prototype Vector Machine
By Jacob Bien, Robert Tibshirani. 2009
17 citations recorded by the source corpus.
We introduce a new nearest-prototype classifier, the prototype vector machine (PVM). It arises from a combinatorial optimization problem which we cast as a variant of the set cover problem. We propose two algorithms for approximating its solution. The PVM selects a relatively small number of representative points which can then be used for classification. It contains 1-NN as a special case. The method is compatible with any dissimilarity measure, making it amenable to situations in which the data are not embedded in an underlying feature space or in which using a non-Euclidean metric is desirable. Indeed, we demonstrate on the much studied ZIP code data how the PVM can reap the benefits of a problem-specific metric. In this example, the PVM outperforms the highly successful 1-NN with tangent distance, and does so retaining fewer than half of the data points. This example highlights the strengths of the PVM in yielding a low-error, highly interpretable model. Additionally, we apply the PVM to a protein classification problem in which a kernel-based distance is used.
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
- Christopher R'e
- Ji Liu
- Ce Zhang
- Stephen J. Wright
- Martin Jaggi
- Marco F. Huber
- Peter Richtárik
- Nadia Burkart
Citations in the corpus
- Interpretable Decision Sets: A Joint Framework for Description and Prediction (2016, background): “They will form the basis of our approach to learning.”
- Learning Cost-Effective and Interpretable Treatment Regimes (2017, unknown): “To this end, various classes of models such as decision lists [18], decision sets [15, 36], prototype (case) based models [4], and generalized additive models [21] were proposed.”
- A Survey on the Explainability of Supervised Machine Learning (2020, methodology): “An unseen data instance can be labeled based on the closest prototypes (Bien & Tibshirani, 2009).”
- An Approximate, Efficient LP Solver for LP Rounding (2013, background): “Problem Family Approximation Factor Machine Learning Applications Set Covering log(N) [20] Classification [3], Multi-object tracking [24].”