Enumeration of Distinct Support Vectors for Interactive Decision Making

Kentaro Kanamori, Satoshi Hara, Masakazu Ishihata, Hiroki ArimuraarXiv 2019 · OpenReview

Abstract

In conventional machine learning, algorithms typically output a single model that globally optimizes a specific objective, such as accuracy. However, in many real-world applications, secondary criteria like interpretability or fairness are paramount. This paper introduces ENUMSV, an algorithm designed to enumerate the $K$-best Support Vector Machine (SVM) models with distinct support vectors. By leveraging the lattice structure of support vectors and Lawler’s framework, ENUMSV efficiently identifies near-optimal models, facilitating interactive human-in-the-loop decision-making.

Introduction

The standard paradigm of machine learning treats training as a "winner-takes-all" optimization. While effective for maximizing performance on a static metric, this approach often hides alternative models that might be better suited for practical deployment. A model that is technically "optimal" in terms of training loss might be biased, overfit to noise, or lack interpretability. To address this, the authors propose a shift toward model enumeration, providing users with a "menu" of high-performing alternatives.

The ENUMSV Algorithm

The core contribution is ENUMSV, an exact enumeration algorithm for SVMs. It identifies models based on their support vectors—the critical data points that define the decision boundary. Since the SVM objective value in the dual problem is determined entirely by these points, they serve as a natural basis for defining "distinct" models.

The algorithm utilizes Lawler’s framework for top-$K$ optimization, combined with a branch-and-bound strategy. It maintains a priority queue of candidate models and systematically explores the search space by excluding specific support vectors. This ensures that the algorithm finds the next-best models in descending order of their objective function values without redundant calculations, making the process computationally feasible despite the combinatorial nature of the problem.

Experimental Evaluation

The researchers evaluated ENUMSV on several UCI benchmark datasets (German, Ionosphere, and Sonar) and the COMPAS recidivism dataset. A key metric for interactive applications is latency; the algorithm must find the "next" model quickly enough for a human user to remain engaged.

Computational time for enumerating up to 1000 models, demonstrating linear scalability across different datasets.

As shown in the timing results, ENUMSV's running time scales almost linearly with the number of models ($K$). This efficiency is crucial for interactive tools where a user might click a button to "see the next best option" and expects a near-instant response.

Insights on Model Diversity

The experiments revealed a "goldmine" of near-optimal models. In many cases, the objective values of the top-50 models were nearly identical to the global optimum (often within a deviation of $6.0 \times 10^{-4}$). Despite these mathematical similarities, the models often exhibited significantly different real-world behaviors.

Objective function value ratio (a) and test loss ratio (b) for the top-50 models. Note how models with lower training ranks can achieve better test performance.

Interestingly, the model with the highest training objective (rank #1) was not always the best performer on the test set. For instance, in the German dataset, models ranked lower by the training objective sometimes achieved lower test loss, suggesting that enumeration can help identify models with better generalization properties.

Furthermore, in experiments with a biased version of the COMPAS dataset, ENUMSV successfully identified models that were both fairer and more accurate than the "optimal" (but biased) model. This demonstrates that model enumeration is a powerful defense against data injection attacks and a useful tool for ensuring algorithmic fairness.

Conclusion and Future Work

ENUMSV provides a robust framework for moving beyond single-model optimization. By efficiently enumerating near-optimal SVM models with distinct support vectors, it empowers users to select models that balance accuracy with other critical requirements. While currently optimized for SVMs, future work could involve incorporating explicit diversity constraints into the search process and exploring ways to scale the algorithm to massive datasets with millions of rows.

Summary updated

Abstract

In conventional prediction tasks, a machine learning algorithm outputs a single best model that globally optimizes its objective function, which typically is accuracy. Therefore, users cannot access the other models explicitly. In contrast to this, multiple model enumeration attracts increasing interests in non-standard machine learning applications where other criteria, e.g., interpretability or fairness, than accuracy are main concern and a user may want to access more than one non-optimal, but suitable models. In this paper, we propose a K-best model enumeration algorithm for Support Vector Machines (SVM) that given a dataset S and an integer K>0, enumerates the K-best models on S with distinct support vectors in the descending order of the objective function values in the dual SVM problem. Based on analysis of the lattice structure of support vectors, our algorithm efficiently finds the next best model with small latency. This is useful in supporting users's interactive examination of their requirements on enumerated models. By experiments on real datasets, we evaluated the efficiency and usefulness of our algorithm.
BibTeX
@misc{kanamori2019enumeration,
  author = {Kentaro Kanamori and Satoshi Hara and Masakazu Ishihata and Hiroki Arimura},
  title = {{Enumeration of Distinct Support Vectors for Interactive Decision Making}},
  year = {2019},
  eprint = {1906.01876},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1906.01876},
}
Figure