技术摘要：用于公平属性表示的无偏分箱技术

1. 问题定义

本文探讨了属性分箱（或称桶化）的问题，这是一种常见的预处理步骤，即将原始连续特征离散化为若干区间，以便进行数据集共享或模型训练。虽然分箱被用于保护隐私和减少噪声，但作者指出，标准的分箱方法（如等大小分箱或等频分箱）可能会在无意中引入或放大针对特定人口统计群体的偏见。

核心问题被形式化为寻找一个满足群体平权（group parity）的 $k$-分箱（将一个属性划分为 $k$ 个桶）。

• 无偏分箱： 如果每个桶内各人口统计群体的比例等于该群体在整个数据集中的全局比例，则称该分箱是无偏的。
• 目标： 主要目标（问题 1）是寻找一种无偏分箱，使其与初始等大小分箱的偏差最小（具体而言，是使最大桶大小与最小桶大小之差最小）。
• $\epsilon$-偏置分箱： 考虑到完美的无偏分箱可能不存在，或者可能会产生较高的“公平性代价”（即与等大小程度的显著偏差），作者引入了一个松弛问题：寻找一种在任何桶中，群体差异都不超过 $\epsilon$ 的分箱。

2. 方法论

本文提出了一套针对不同约束条件和数据集规模量身定制的算法。

2.1 无偏分箱的精确解（等大小）

针对寻找最小化等大小基准尺寸偏差的无偏分箱这一特定情况，作者开发了一种**动态规划（DP）**方法。

• 边界候选集： 算法首先识别出一组“边界候选点”。如果某个索引 $i$ 处的特定群体的累积比例等于该群体的全局比例，则该索引为候选点。作者证明（定理 1），任何最优无偏分箱的边界必须完全取自于这个集合。
• DP 公式： 该算法使用递归函数 $OPT(j, \kappa)$ 将前 $j$ 个边界候选点划分为 $\kappa$ 个无偏桶，通过追踪最大和最小桶宽度来最小化其差异。
• 复杂度： 算法的运行时间为 $O(n \log n + m^2 k)$，空间复杂度为 $O(mk)$，其中$n$是数据集大小，$m$是边界候选点数量，$k$ 是桶的数量。

2.2 $\epsilon$-偏置分箱的解决方案

由于“边界候选点”的概念无法扩展到松弛的 $\epsilon$-偏置场景，且针对该场景的精确 DP 方法具有二次时间复杂度（$O(n^2 k)$），因此作者提出了一个具有实际可扩展性的两步走方法：

1. 分治法 (D&C)：

   • 该算法通过递归地将数据划分为两个“超桶”来快速找到有效的 $\epsilon$-偏置解。
   • 它从一个中点边界开始，迭代地扩大搜索半径，直到找到一个 $\epsilon$-偏置的划分。
   • 定理 4 证明，如果存在有效的 $\epsilon$-偏置分箱，分治法一定能找到它。
   • 复杂度： $O(n \log k)$（近线性），具有高度的可扩展性。

2. 局部搜索 (LS)：

   • 为了找到最优的 $\epsilon$-偏置分箱（即最小化尺寸偏差），局部搜索法使用分治法的解作为上界。
   • 它在初始等大小分箱的边界周围定义了一个搜索窗口，并受分治法解的目标值约束。
   • 它通过穷举检查该窗口内的组合，以找到具有更低目标值的解。
   • 复杂度： $O(n \log n + (w_{dnc})^{k-1})$，其中 $w_{dnc}$ 是分治法解的目标值。虽然在理论上对 $k$ 是指数级的，但作者指出，由于具有较大 $w_{dnc}$ 的对抗性情况很少见，因此在实践中是高效的。

3. 核心贡献

• 问题形式化： 本文正式定义了无偏分箱问题和松弛的 $\epsilon$-偏置分箱问题，强调了数据准备阶段关于公平性研究的空白。
• 理论保证：
  • 证明了最优无偏分箱的边界必须属于特定的候选集。
  • 证明了分治算法是完备的（即如果存在解，它一定能找到）。
• 算法套件：
  • 用于等大小无偏分箱的精确 DP 算法。
  • 用于在近线性时间内寻找有效 $\epsilon$-偏置分箱的可扩展分治算法。
  • 利用分治法高效寻找最优 $\epsilon$-偏置分箱的局部搜索算法。
• 广泛适用性： 与用于无偏分箱的 DP 解法不同，分治法和局部搜索法是通用的，不限于等大小分箱；它们可以作为任何黑盒桶化方法的后处理步骤。

4. 实验结果

作者在真实世界数据集（German Credit, COMPAS）和合成数据集上评估了他们的算法。

• 公平性影响： 实验表明，标准的非公平感知分箱会引入可衡量的偏见。应用 $\epsilon$-偏置分箱可以显著降低下游模型（逻辑回归和 SVM）中的群体不公平指标（差异影响、统计平权差异、机会均等差异）。
• 公平性代价： 将偏见减少一半可以在保持或略微提高模型准确性的同时，显著改善公平性指标。研究发现，在许多情况下，“公平性代价”（即与等大小桶尺寸的偏差）是微不足道的。
• 个体公平性： 研究观察到，虽然群体公平性得到了显著改善，但个体公平性（以一致性衡量）基本保持稳定，这表明无偏分箱不会损害个体层面的公平性。
• 可扩展性： 分治法和局部搜索算法在大规模数据集上表现出极高的效率，而二次时间复杂度的 DP 解法仅限于较小规模的设置。
• 集成性： 将 $\epsilon$-偏置分箱与下游 FairML 技术（如 Exponentiated Gradient）结合使用表明，数据准备可以作为模型级干预的补充，尽管当数据已经过公平性预处理时，边际收益较小。

5. 重要性与主张

本文将无偏分箱定位为负责任的数据分析流水线中必要但不充分的组成部分。

• 互补作用： 作者明确指出，无偏分箱并不能取代 FairML 技术（如训练公平模型），而是作为一种关键的预处理步骤，以防止偏见在模型训练开始前进行传播。
• 实际意义： 该工作认为，数据准备过程中引入的偏见是下游不公平现象的一个切实存在的来源。通过及早解决这一问题，从业者可以显著减轻下游公平性干预的负担。
• 审慎的主张： 作者谨慎地指出，虽然他们的方法减少了偏见并提高了公平性指标，但并不保证在所有下游任务中都能实现公平。其有效性取决于特定的数据分布和所选的 $\epsilon$ 阈值。论文强调，实现公平的结果需要将公平感知的数据准备与公平算法开发相结合。