Probably Approximate Shapley Fairness with Applications in Machine Learning
This work addresses fairness preservation in approximate Shapley value computations, which is crucial for applications in machine learning, but it is incremental as it builds on existing estimation methods.
The paper tackles the problem that Shapley value estimates, used for fairness in machine learning applications like data valuation, often fail to preserve exact fairness guarantees due to approximation. It introduces a generalized fairness concept and a greedy algorithm that empirically outperforms existing methods in fairness guarantees while maintaining competitive accuracy on real-world datasets.
The Shapley value (SV) is adopted in various scenarios in machine learning (ML), including data valuation, agent valuation, and feature attribution, as it satisfies their fairness requirements. However, as exact SVs are infeasible to compute in practice, SV estimates are approximated instead. This approximation step raises an important question: do the SV estimates preserve the fairness guarantees of exact SVs? We observe that the fairness guarantees of exact SVs are too restrictive for SV estimates. Thus, we generalise Shapley fairness to probably approximate Shapley fairness and propose fidelity score, a metric to measure the variation of SV estimates, that determines how probable the fairness guarantees hold. Our last theoretical contribution is a novel greedy active estimation (GAE) algorithm that will maximise the lowest fidelity score and achieve a better fairness guarantee than the de facto Monte-Carlo estimation. We empirically verify GAE outperforms several existing methods in guaranteeing fairness while remaining competitive in estimation accuracy in various ML scenarios using real-world datasets.