跳到正文
arXiv cs.CY· Antonio Ferrara, Fabio Vitale, Atsushi Miyauchi, Francesco Bonchi·· 9 小时前AI 评分26

Fair Bubble Sort:面向连续敏感属性的可证明最优公平排序

Fair Bubble Sort: Provably Optimal Fair Ranking with Continuous Sensitive Attributes

AI 导读

针对公平排序方法普遍要求将年龄、收入等连续敏感属性离散化分组的问题,研究者提出 Continuous Pairwise Parity(CPP)公平性概念,基于排序位置与敏感属性的 Kendall 相关性,并给出后处理算法 Fair Bubble Sort(FBS)。

正文 · AI 翻译

查看 PDF HTML(实验性)

摘要:大多数公平排序方法假设受保护属性是分类属性,要求将年龄或收入等连续属性离散化为若干组。这会引入任意阈值、丢失细粒度信息,并忽略属性的自然顺序。本文研究在不依赖阈值化的情况下,针对连续受保护属性的公平排序问题。我们提出连续成对均等(Continuous Pairwise Parity,CPP),这是一种基于排序位置与受保护属性之间 Kendall 相关性的公平性概念,并寻求在满足规定 CPP 约束的同时,使其与初始基于分数的排序之间的 Kemeny 距离最小化的排序。为解决该问题,我们提出公平冒泡排序(Fair Bubble Sort,FBS),一种基于定向相邻交换的高效后处理算法。我们证明 FBS 在无权 Kemeny 距离下是精确最优的,并为分数加权情形提供了近似保证。FBS 是输出敏感的,其运行时间取决于满足公平性约束所需的交换次数。在合成数据集和真实数据集上的实验表明,FBS 具有可扩展性,并始终优于基于离散化的基线方法,实现了更优的公平性-准确性帕累托前沿。
评论: 35 页,9 幅图,4 张表。已被 NeurIPS 2026 接收。代码:此 https URL
主题: 机器学习(cs.LG);计算机与社会(cs.CY);数据结构与算法(cs.DS)
引用为: arXiv:2611.22352 [cs.LG]
  (或 arXiv:2611.22352v1 [cs.LG] 用于此版本)
  https://doi.org/10.48550/arXiv.2611.22352

由 DataCite 颁发的 arXiv DOI(待注册)

提交历史

来自:Antonio Ferrara [查看电子邮件]
[v1] 2026 年 11 月 17 日星期二 08:04:06 UTC(571 KB)

来源:arXiv cs.CY · arxiv.org