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.

该研究工作将 Shapley value 的公平性要求推广为大概近似 Shapley 公平性，并提出了一个名为 fidelity score 的度量，可以确定公平保证的概率程度。同时，还提出了一种新的贪心主动估计算法（GAE），该算法将最大化最低保真度的值，并利用现实世界的数据集在几种机器学习场景中验证了 GAE 的优越性，既保证了公正性，同时也在估计精度方面具有竞争力。

机器学习中的Shapley公平性近似算法应用