Source-linked AI summary
Predictive Multiplicity in Classification
Charles T. Marx, Flavio du Pin Calmon, Berk Ustun
TL;DR
When nearly equally performing models assign conflicting predictions, model selection can have materially different consequences for individuals. The paper defines predictive multiplicity measures, computes them exactly for linear classifiers using integer programming, and finds substantial conflicts in recidivism datasets. These results support measuring and reporting multiplicity so stakeholders can inform model-development and deployment decisions.
Problem
Nearly equally performing models may assign conflicting predictions in human-facing applications, creating ethical challenges even with agreed problem formulations and representative data.
Method
The paper defines ambiguity and discrepancy, then uses integer programming to compute these measures exactly for linear classification problems.
Results
In the ProPublica COMPAS dataset, a model 1% less accurate than the most accurate model conflicted on over 17% of individuals, and model choice affected 44%.
Takeaways & Limitations
Predictive multiplicity should be measured and reported so stakeholders can address competing predictions case by case and participate in deployment decisions.
Takeaways & Limitations
The recidivism focus is not an endorsement of the practice and reflects a domain where multiplicity may support forgoing machine-learning deployment.
Abstract
from arXiv · showhide
Prediction problems often admit competing models that perform almost equally well. This effect challenges key assumptions in machine learning when competing models assign conflicting predictions. In this paper, we define predictive multiplicity as the ability of a prediction problem to admit competing models with conflicting predictions. We introduce formal measures to evaluate the severity of predictive multiplicity and develop integer programming tools to compute them exactly for linear classification problems. We apply our tools to measure predictive multiplicity in recidivism prediction problems. Our results show that real-world datasets may admit competing models that assign wildly conflicting predictions, and motivate the need to measure and report predictive multiplicity in model development.
1 Introduction
Predictive multiplicity occurs when nearly equally accurate models assign conflicting predictions, creating ethical and practical challenges in human-facing machine learning. The paper defines measures for this conflict, computes them exactly for linear classifiers, and demonstrates substantial multiplicity in recidivism prediction.
- Motivation and definition: Nearly equally accurate models can produce conflicting predictions that affect people in applications such as lending and recidivism prediction.
- Motivation and definition: Predictive multiplicity is the ability of a prediction problem to admit competing models that assign conflicting predictions.
- Measures and tools: Ambiguity counts individuals whose predictions vary across competing models, while discrepancy measures the maximum number of predictions that could change when switching models.
- Measures and tools: The paper develops integer programming tools to compute ambiguity and discrepancy exactly for linear classification problems.
- Empirical study: In the ProPublica COMPAS dataset, a model only 1% less accurate than the most accurate model conflicted on over 17% of individuals, while model choice affected 44%.
- Related work: The paper distinguishes predictive multiplicity from the Rashomon effect, which concerns conflicting explanations despite identical training predictions.
2 Framework
The framework defines predictive multiplicity through competing classifiers that perform nearly as well yet disagree on predictions. It measures this disagreement using ambiguity and discrepancy over an ε-level set around a baseline classifier.
- Choosing ε: The tolerance ε should be chosen so the ε-level set is likely to contain a model with optimal deployment performance.Suggested approaches include confidence intervals, bootstrapping, cross-validation, and generalization bounds.
- Competing Models: Predictive multiplicity occurs when competing models in an ε-level set assign conflicting predictions.The ε-level set contains classifiers whose training error is within ε of the baseline's error.
- Implications: Multiplicity makes model selection an arbitration among irreconcilable predictions and can affect model validation and post-hoc explanation.The paper describes these conflicts as consequential when predictions affect people, including in lending and recidivism settings.
- Measures: Ambiguity measures the proportion of training points whose predictions can change across competing classifiers.It captures how many individuals' predictions are determined by model choice.
- Measures: Discrepancy measures the maximum proportion of predictions that change between the baseline and one competing classifier.Unlike ambiguity, discrepancy requires all conflicting predictions to be realized by a single competing model.
- Accuracy and Multiplicity: Proposition 1 shows that a less accurate baseline leaves more room for predictive multiplicity, motivating measurement with the best possible baseline.The framework therefore uses a best-performing baseline when assessing ambiguity and discrepancy.
3 Methodology
The methodology computes ambiguity and discrepancy for linear classifiers by solving mixed integer programs over ε-level sets. Path algorithms reuse solutions across tolerance values to efficiently trace how both measures change with ε.
- Integer Programming: The tools compute ambiguity and discrepancy for linear classification problems using integer programming.The formulations solve discrete empirical risk minimization problems over competing classifiers.
- Baseline Classifier: The baseline classifier is a minimum-error linear classifier intended to represent the model that would typically be deployed.Using a minimum-error baseline ensures measured multiplicity does not arise from baseline suboptimality.
- Path Algorithms: Path algorithms compute ambiguity and discrepancy for all tested ε values by initializing each problem from a previous solution.Reusing solutions produces bounds that reduce the next MIP's search space and can be faster than solving each tolerance separately.
- MIP Formulations: Mixed integer programming formulations recover competing classifiers while enforcing membership in the ε-level set.DiscMIP minimizes agreement with the baseline, whereas FlipMIP finds an accurate classifier forced to disagree on a specified point.
- Discrepancy: DiscMIP returns a classifier maximizing discrepancy, while solver bounds provide corresponding bounds when optimality is uncertified.For discrepancy, the solver's upper bound yields a lower bound on the measure, and its lower bound yields an upper bound.
- Ambiguity: Ambiguity is computed by fitting one pathological classifier per training point and counting those within ε of the baseline error.Each pathological classifier is the most accurate linear classifier required to flip its associated point's prediction.
4 Experiments
The experiments measure predictive multiplicity across recidivism datasets using exact tools and an ad hoc comparison, revealing substantial and unevenly distributed conflicts among near-optimal classifiers.
- Setup: The study derives eight recidivism datasets, preprocesses their features, and evaluates predictive multiplicity after an 80/20 train-test split.Features are binarized, missing entries are removed, and minority classes are oversampled; the authors report negligible effects of oversampling on multiplicity measures.
- Incidence: Across eight datasets, 4%–53% of individuals receive conflicting predictions in the 1%-level set.For compas arrest, ambiguity is 44%, while a competing model can change 17% of predictions relative to the baseline.
- Burden: In compas violent, ambiguity is 72.9% for African-Americans versus 37.2% for Caucasians over the 1%-level set.The authors characterize groups with greater multiplicity burden as more vulnerable to model selection and ignorance of competing models.
- Implications: Reporting ambiguity and discrepancy exposes conflicts that can affect explanations and model deployment, motivating greater scrutiny and stakeholder involvement in selection.For compas arrest, the baseline generalizes and optimizes training error, yet a competing model conflicts on 17% of individuals.
- Results: Compas arrest has at least two competing classifiers that reverse one person’s prediction from recidivate to not recidivate while also differing in coefficients and variable importance.The baseline predicts h(xp) = +1, whereas the competing models predict h(xp) = −1.
- Measurement comparison: An ad hoc analysis finds 10% ambiguity and 7% discrepancy, below the exact-tool values of 44% and 17%.The ad hoc approach searches only penalized logistic-regression models generated by varying ℓ1 and ℓ2 penalties, not all linear classifiers in the level set.
5 Concluding Remarks
The paper argues against a universal remedy for predictive multiplicity and instead supports measuring and reporting it so stakeholders can make case-specific deployment decisions.
- Concluding Remarks: The authors do not advocate a general prescription for resolving predictive multiplicity, despite techniques for choosing among competing models.They propose resolving multiplicity case by case with stakeholder input.
- Concluding Remarks: In human-facing applications, reporting multiplicity may prompt stakeholders to reconsider deployment, assign favorable predictions to conflicted individuals, or forgo deployment.The paper presents these as possible responses rather than a universal policy.
A Omitted Proofs
The omitted proof bounds the discrepancy between a baseline classifier and any classifier in its ϵ-level set using the Triangle Inequality and the level-set risk constraint.
- Proof of Proposition 1: The Triangle Inequality bounds the distance between baseline and competing prediction vectors through their distances from the observed-label vector.The proof then substitutes expressions for the two risks and discrepancy.
- Proof of Proposition 1: Because a competing classifier lies in the ϵ-level set, its empirical risk is at most the baseline risk plus ϵ.This level-set condition is used to rewrite the bound on discrepancy.
- Proof of Proposition 1: Maximizing over the ϵ-level set yields δϵ(h0) ≤ 2 R̂(h0) + ϵ.The result follows because every classifier in the level set satisfies the preceding discrepancy bound.
B MIP Formulation for Training the Best Linear Classifier
The paper trains a best linear classifier by minimizing training error through an optimization problem and an equivalent mixed-integer programming formulation.
- The classifier is fit by minimizing training error through an optimization problem.
- The optimization problem is reformulated as a mixed-integer programming formulation.
- The formulation constrains l_i to binary values and w_j to the interval [-1, 1].
- Mistake indicators l_i encode whether classifier h misclassifies example x_i.
- Constraint (6c) encodes that classifiers must make exactly one mistake for identical features with conflicting labels.
C Additional Experimental Results
The additional experiments present multiplicity profiles for recidivism datasets, including profiles for compas and pretrial data and analyses using logistic-regression model pools.
- Figure 4 presents multiplicity profiles for the compas and pretrial datasets.
- Figure 5 presents multiplicity profiles for the recidivism datasets.
- Figure 6 presents compas and pretrial multiplicity profiles produced via pools of logistic regression models.
- Figure 7 presents recidivism multiplicity profiles produced via pools of logistic regression models.