让分类器在博弈中公平对待各群体,同时保持高准确率。
Minimax Group Fairness in Strategic Classification
- 构建公平导向的博弈模型,使学习者对抗策略性特征操纵。
- 小群体数量下可高效求解近似最优确定性分类器。
- 透明化学习者能实现高效随机分类器,适合关注公平性的研究者。
在策略分类中,个体为获得正面分类结果而以成本操纵自身特征。本文关注兼具群体公平与准确率保障的学习目标,采用最小-最大群体公平性(minimax group fairness)定义,即最小化各群体间最高错误率。我们形式化了包含多个群体、各自具有不同成本函数的代理群体与学习者的博弈模型,在异构泛化框架(agnostic PAC)下,当代理成本函数可分离时,提出一种高效算法,可在群体数较少时找到近似最优的确定性分类器,且该算法在所有分类器集合上仍保持统计与计算效率。对于非可分离成本函数,证明存在基于预言机的高效算法,可求得近似最优的随机分类器,前提是学习者完全透明——在代理操纵前先从分布中抽样分类器。实验证明了所提算法在真实数据上的有效性。
原文摘要 · Abstract (English)
In strategic classification, agents manipulate their features, at a cost, to receive a positive classification outcome from the learner's classifier. The goal of the learner in such settings is to learn a classifier that is robust to strategic manipulations. While the majority of works in this domain consider accuracy as the primary objective of the learner, in this work, we consider learning objectives that have group fairness guarantees in addition to accuracy guarantees. We work with the minimax group fairness notion that asks for minimizing the maximal group error rate across population groups. We formalize a fairness-aware Stackelberg game between a population of agents consisting of several groups, with each group having its own cost function, and a learner in the agnostic PAC setting in which the learner is working with a hypothesis class H. When the cost functions of the agents are separable, we show the existence of an efficient algorithm that finds an approximately optimal deterministic classifier for the learner when the number of groups is small. This algorithm remains efficient, both statistically and computationally, even when H is the set of all classifiers. We then consider cost functions that are not necessarily separable and show the existence of oracle-efficient algorithms that find approximately optimal randomized classifiers for the learner when H has finite strategic VC dimension. These algorithms work under the assumption that the learner is fully transparent: the learner draws a classifier from its distribution (randomized classifier) before the agents respond by manipulating their feature vectors. We highlight the effectiveness of such transparency in developing oracle-efficient algorithms. We conclude with verifying the efficacy of our algorithms on real data by conducting an experimental analysis.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。