Stochastic classifiers are mathematically elegant for solving complex fairness and optimization problems, but they can be a nightmare to deploy in the real world. This paper introduces theoretical bounds and practical algorithms—specifically hashing and variable binning—to convert these "random" models into deterministic ones that preserve their statistical benefits while remaining stable and predictable.
The Problem with Flipping Coins
In modern machine learning, we often face "constrained optimization" problems. For example, you might want a model that maximizes accuracy while ensuring the False Positive Rate is equal across different demographic groups to maintain fairness. The math used to solve these problems often produces stochastic classifiers: models that don't just give a strict "Yes" or "No," but instead flip a weighted coin to decide.
While theoretically sound, stochastic classifiers have major practical flaws:
- Ethical and Legal Issues: It is difficult to explain to a loan applicant that they were rejected because the computer "rolled a die."
- Vulnerability to Manipulation: If a spam filter is 99% accurate but stochastic, a spammer can simply send 100 copies of the same email, knowing one will eventually slip through.
- Debugging Nightmares: If the same input yields different results every time you run it, testing, reproducibility, and maintenance become nearly impossible.
The core challenge is turning these "coin-flippers" into deterministic functions without losing the fairness or performance guarantees they were designed to provide.
Methods for De-randomization
The authors compare three main approaches to making stochastic models deterministic:
- Thresholding (The Baseline): This is the most common method. If the model says there is a >50% chance of a positive label, it predicts "1." While simple, the authors prove this often fails to preserve the aggregate statistical properties (like fairness metrics) of the original model.
- Hashing: Instead of a random coin flip, this method uses a pairwise independent hash function on the input features. This "simulates" randomness: the model makes a deterministic decision for a specific person, but across a population, the decisions look stochastic enough to satisfy the original statistical constraints.
- Variable Binning (VarBin): A novel approach designed for stochastic ensembles (models that choose between several sub-models). It clusters similar data points together and uses a "score function" to assign them to specific sub-models. This is designed to be more "orderly"—meaning similar people are more likely to receive the same outcome.
Key Insights and Results
The researchers evaluated their methods on six datasets, primarily focused on fairness and recidivism (including COMPAS, UCI Adult, and Law School datasets).
The "Orderliness" Trade-off
The authors introduce the concept of "orderliness." A thresholding model is perfectly orderly (similar inputs get similar outputs), but it is inaccurate at matching the stochastic constraints. A hashing model is very accurate at matching the stochastic original but can be "disorderly" (tiny changes in input lead to different hashes and different outcomes).
The core "aha" moment is that we don't need the deterministic model to match the stochastic one on every single person. We only need it to match on aggregate metrics (like the average error rate for a specific group). Hashing excels here because it spreads "errors" out in a way that cancels out over a large population.
Superior Approximation
When matching overall performance profiles, Hashing and VarBin consistently outperform Thresholding.
As seen in the ROC curves above, the Hashing method closely mirrors the Stochastic baseline. In contrast, Thresholding and simply picking the "Best Iterate" from the optimization solver diverge significantly from the desired stochastic performance. In many cases, the difference in fairness metrics between the stochastic model and the Hashing/VarBin versions was near zero.
VarBin Wins on Smoothness
While Hashing is effective, Variable Binning provides a better trade-off for practical deployment.
As illustrated above, VarBin achieves lower objective and constraint bias with significantly fewer "bins" than Hashing. This efficiency leads to a more consistent and "orderly" user experience, as it requires less fragmentation of the input space to achieve the desired statistical guarantees.
Limitations and Future Work
- Clustering Dependency: The success of the "orderly" methods (VarBin and pre-clustered Hashing) depends heavily on choosing a good similarity measure or clustering function. If the clustering is poor, the principle that "similar individuals receive similar outcomes" fails.
- Metric Scope: The current theory focuses on "rate metrics" (like FPR, FNR). Future work could extend this to more complex metrics like F-score, G-mean, or ranking-based metrics.
- Local Orderliness: While VarBin improves upon pure hashing, there is still no "perfect" way to guarantee local consistency without sacrificing some global statistical guarantees. Finding the optimal point on that frontier remains an open question.
Summary updated