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.
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.
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