The Pokémon Theorem and other Fairness Impossibility Results¶

会议: NeurIPS 2026
arXiv: 2605.09221
领域: 安全
关键词: 算法公平性、再生核希尔伯特空间 (RKHS)、最大均值差异 (MMD)、不可能性定理、公平表征学习

一句话总结¶

本文将经典的算法公平性不可能性定理统一于再生核希尔伯特空间（RKHS）的条件均值嵌入几何视角，提出宝可梦定理（Pokémon Theorem）证明有限线性公平准则必然在正交补空间遗留 MMD 违规残差，并从理论上确立了公平特征学习在基础率不等时的类别坍缩不可能性。

研究背景与动机¶

算法决策中的公平性定义在过去半个世纪中经历了长期且激烈的争论。从早年在教育与雇佣测试中对偏见消除的形式化探讨，到现代机器学习中关于校准度（Calibration）、统计平等（Demographic Parity）与均等几率（Equalized Odds）的权衡，研究者们陆续提出了一系列著名的不可能性定理。以 Kleinberg-Mullainathan-Raghavan（KMR）定理和 Chouldechova 的二分法为代表的经典结论指出：在群体间基础率（Base Rate）存在客观差异时，组内校准度与类别条件均衡（正负类错误率一致）在非平凡预测器下无法同时满足。然而，这些经典证明几乎完全依赖标量统计量的代数运算，给实际应用留下了两个核心悬念：第一，这类不可行性究竟是选定标量指标的巧合，还是对任意有限个公平审计清单均恒成立？第二，大行其道的公平表征学习（Fair Representation Learning）试图通过编码器将群体敏感属性剥离，是否真能让下游任务免费继承公平性并绕开上述不可能性？

这种标量视角的局限性在于无法刻画无限维函数空间中的约束几何。现有的公平特征表征方法虽然试图通过对抗消除或分布对齐来隐藏群体标签，但在面对群间固有先验差异时，往往伴随着未被严格刻画的性能损失。本文的切入角度是：利用再生核希尔伯特空间（RKHS）中的均值嵌入（Mean Embeddings）和特征核（Characteristic Kernels），将所有线性均值公平性准则表示为特征空间中条件均值嵌入向量的线性约束，从而将全概率公式导致的自由度超定统一暴露为几何正交补结构的内在矛盾。核心 idea：将公平性准则形式化为 RKHS 条件均值嵌入上的线性泛函，证明群体分布差异构成了固定的 MMD 预算，任何有限维线性审计都无法穷尽分布差异（宝可梦定理），且在基础率不等时强求分布平等与类别分离必然导致表征空间的完全类别坍缩。

方法详解¶

整体框架¶

本文的方法并非提出新的公平训练算法，而是建立了一个统一解释标量与表征公平性不可行性的 RKHS 几何分析体系。整体流程从个体特征 $X$、二元结果 $Y$ 与群体属性 $G \in \{a,b\}$ 的条件均值嵌入出发，将评分函数 $S(X) = \langle w, \phi(X) \rangle$ 的公平性审计转化为内积约束，进而推导出四个递进的理论结果：强化版 KMR 定理、定性与定量宝可梦定理、公平特征学习不可能性定理，以及带松弛裕度的近似公平帕累托边界（Pokémon–KMR 桥梁）。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["个体特征分布 (X, Y, G)"] --> B["RKHS 条件均值嵌入与差异向量<br/>δ = μ_a - μ_b"]
    B --> C["强化版 KMR 判定<br/>仅需群体一阶无偏即可触发二分法"]
    B --> D["宝可梦定理与谱衰减<br/>有限审计遗留 MMD 见证残差"]
    B --> E["公平特征学习不可能性<br/>分布平等 + 类别分离 导致类别坍缩"]
    D --> F["近似公平松弛与信号边界<br/>Pokémon–KMR 连续收敛桥梁"]
    E --> F

关键设计¶

1. 强化版 KMR 定理：将全分布校准弱化为一阶均值无偏 经典的 KMR 定理要求严格的组内逐点校准度 $\mathbb{E}[Y \mid S=s, G=g] = s$，属于高阶分布条件。本文证明该不可能性结论在显著更弱的一阶矩条件——群体条件无偏性 $\mathbb{E}[S \mid G=g] = p_g$（其中 $p_g = \Pr[Y=1 \mid G=g]$）下即完全成立。当评分函数同时满足正类均衡与负类均衡时，记 $\mu^+ = \mathbb{E}[S \mid Y=1, G=g]$ 与 $\mu^- = \mathbb{E}[S \mid Y=0, G=g]$，根据全期望公式可展开为： $$p_g = p_g \mu^+ + (1 - p_g) \mu^- \quad \Longrightarrow \quad (p_a - p_b)(1 - (\mu^+ - \mu^-)) = 0$$ 在两组基础率不等（$p_a \neq p_b$）的前提下，必须有 $\mu^+ - \mu^- = 1$。结合评分有界性 $S \in [0,1]$，直接由马尔可夫不等式推出 $S=Y$ 几乎处处成立。这一结果表明，即使模型预测概率严重未校准，只要其组内宏观平均预测值与实际基础率一致，依然无法逃脱 KMR 锁死。

2. 宝可梦定理（Pokémon Theorem）：有限线性审计无法穷尽分布差异 针对工业界试图通过堆叠多项公平性检查清单（Demographic Parity, Equalized Odds 等）消除偏见的实践，宝可梦定理（取意自其宣传语“Gotta Catch 'Em All”，本文证明你抓不全所有偏见）指出：若特征核具备特征性（Characteristic），且群体分布客观相异 $P_a \neq P_b$，则群体差向量 $\delta = \mu_a - \mu_b \neq 0$。任何满足 $m$ 个线性均值公平准则 $\{v_1, \ldots, v_m\}$ 的系统，其约束本质上将 $\delta$ 限制在审计子空间 $V = \mathrm{span}\{v_1, \ldots, v_m\}$ 的正交补空间中。规范化的差向量 $v_{m+1} = \delta / \|\delta\|_\mathcal{H}$ 作为 MMD 见证函数，天然正交于已审定的 $m$ 个方向，并严格暴露残余违规： $$\langle v_{m+1}, \delta \rangle = \|\delta\|_\mathcal{H} = \mathrm{MMD}(P_a, P_b) > 0$$ 在定量版本中，设定混合协方差算子 $\Sigma$ 满足多项式特征值衰减 $\lambda_j \asymp j^{-\alpha}$（$\alpha > 1$），且 $\delta$ 满足积分源条件 $\delta = \Sigma^r u$（$\|u\|_\mathcal{H} \le R$）。审计预算为 $m$ 时的极小化极大残差严格匹配希尔伯特椭球的 Kolmogorov $m$-宽（Kolmogorov $m$-width）速率： $$\inf_{\dim V \le m} \sup_{\delta \in B_r(R)} \|P_{V^\perp} \delta\|_\mathcal{H}^2 = R^2 \lambda_{m+1}^{2r} = \Theta(R^2 (m+1)^{-2\alpha r})$$ 这证明前 $m$ 个主特征子空间构成了最优审计预算分配，但只要 $m$ 有限，最坏情况残余违规恒严格大于零。

3. 公平特征学习的不可能性：表征对齐与类别分离诱导类别坍缩 表征学习领域普遍期望构建可测编码器 $\Phi: \mathcal{X} \to \mathcal{Z}$，使得隐表征 $Z=\Phi(X)$ 既满足分布平等 $\Phi(P_a) = \Phi(P_b)$，又保留判别任务的类别分离性 $\mu_{\Phi, y, a} = \mu_{\Phi, y, b}$。本文证明在 $p_a \neq p_b$ 时，全期望公式在表征空间的 Bochner 积分上迫使均值嵌入崩塌： $$\mu_{\Phi, a} - \mu_{\Phi, b} = (p_a - p_b)(\mu_{\Phi, 1} - \mu_{\Phi, 0}) = 0 \quad \Longrightarrow \quad \mu_{\Phi, 1} = \mu_{\Phi, 0}$$ 在特征核映射的单射性保证下，这直接推导至分布级的完全独立性 $\Phi(X) \perp\!\!\!\perp Y$。这意味着任何可测下游预测器在表征上都无法保留任何关于真值类别 $Y$ 的均值判别信号，特征学习不仅无法规避 KMR，反而会导致下游预测效用全盘归零。

4. 近似公平帕累托边界与 Pokémon–KMR 连续收敛桥梁 为了指导现实中具有容忍度的算法设计，本文进一步推导出近似公平性松弛定理。在 $\varepsilon$-近似平等与 $\rho$-近似类别分离假设下，组内可用的最大类别均值判别信号被严格截断： $$\|\mu_{\Phi, 1, g} - \mu_{\Phi, 0, g}\|_{\mathcal{H}_\mathcal{Z}} \le \frac{\varepsilon + \rho}{|p_a - p_b|}, \quad \forall g \in \{a,b\}$$ 对于二元分类器 $\hat{Y}$，该几何界限退化为显式的误差下界 $\mathrm{error}(\hat{Y}) \ge \min(p, 1-p)(1 - \mathrm{DP\_gap}/|p_a - p_b|)$。最后，通过在核空间中引入 $m$ 维类别均衡审计约束，利用源条件衰减将尾部残差转化为连续有界概率： $$\Pr[|S - Y| > t] \le \frac{W \rho_m}{|\Delta p| t} = O(W R (m+1)^{-\alpha r} / (|\Delta p| t))$$ 当审计维度 $m \to \infty$ 时，该界限以多项式速率收敛至 0，从而在有限维审计逼近与经典 KMR 的 $S=Y$ a.s. 之间架起了严谨的几何桥梁。

实验关键数据¶

主实验¶

论文在三个经典公平性基准数据集上进行了总体水平的理论一致性检验：Adult Income（$n \approx 45\text{K}$，性别为保护属性）、COMPAS（$n \approx 5.3\text{K}$，种族为保护属性）以及 ACS PUMS California 2018（$n = 20\text{K}$，加州收入预测）。核函数统一采用高斯 RBF 核配中位数带宽，并通过 1000 次 Bootstrap 与 999 次置换检验保证显著性。

| 数据集 | 样本规模 ($n$) | 保护属性 ($G$) | 基础率差距 ($|\Delta \hat{p}|$) | 保护群体占比 ($\Pr[G=a]$) | 达到 99% MMD 捕获所需准则数 ($k_{99}$) | 前 3 阶谱方差占比 | |---|---|---|---|---|---|---| | Adult Income | $\approx 45,000$ | 性别 (男 vs 女) | $0.20$ ($0.306$ vs $0.109$) | $0.675$ | $35$ | $41\%$ | | COMPAS | $\approx 5,300$ | 种族 (非裔 vs 白人) | $0.13$ ($0.52$ vs $0.39$) | $0.60$ | $4$ | $98\%$ | | ACS PUMS | $20,000$ | 种族/性别复合 | $0.085$ ($0.44$ vs $0.36$) | $0.62$ | $8$ | $61\%$ |

消融与检验实验¶

下表汇总了对近分离分类器（Hardt 均衡几率后处理与指数梯度法 ExpGrad-EO，阈值门控 $\mathrm{EO\_gap} \le \tau$）理论下界的实证违规检验，以及公平特征表征模型在禁用区域边界上的表现。

检验项目与配置	门控阈值 ($\tau$)	检验点总数	原始下界违规点数	Bootstrap 95% CI 统计违规点数	理论符合率
分离条件帕累托界 (宽松门控)	$\mathrm{EO\_gap} \le 0.05$	46 (Adult 12, COMPAS 11, ACS 23)	7 (Adult 0, COMPAS 5, ACS 2)	1 (仅 ACS 边缘点，裕度 0.0035)	97.8% (CI 视角)
分离条件帕累托界 (严格门控)	$\mathrm{EO\_gap} \le 0.02$	17 (Adult 2, COMPAS 3, ACS 12)	3 (Adult 0, COMPAS 2, ACS 1)	0	100.0%
表征学习禁用角检验 (Fair-VAE)	$\rho = 0.15$	多组 $\lambda_{\mathrm{MMD}} \in [0, 10]$	0	0	100.0% (无越界)
表征学习禁用角检验 (Adv-Debias)	$\rho = 0.15$	多组 $\lambda_{\mathrm{adv}} \in [0, 10]$	0	0	100.0% (无越界)
表征学习禁用角检验 (LFR)	$\rho = 0.15$	多组 $A_z \in [0.1, 100]$	0	0	100.0% (无越界)

关键发现¶

审计衰减速度受数据内在支持集维度支配：在特征维度较低的 COMPAS（8个单热编码特征）中，协方差谱支撑集极小，前 3 个特征向量即捕获了 98% 的群体差向量范数，仅需 $k_{99}=4$ 个审计准则即可将残差压至 1% 以下；而在特征维度高且连续特征丰富的 Adult Income 中，捕获 99% 需要多达 35 个特征方向，严格符合 Kolmogorov $m$-宽在对数坐标下的多项式直线衰减特征。
经验分类器帕累托边界高度契合理论下界：在所有近分离分类器配置中，经验误差散点图完整贴合在下界曲线 $y = \min(p, 1-p)(1 - x/|\Delta p|)$ 之上。在严格的 $\tau = 0.02$ 判定下，所有数据集上的全部 17 个分类器无一突破该下界；唯一在宽松门控下越界的样本其超出幅度仅为 0.0035，完全处于测试集采样噪声范围内。
表征学习在“高判别、高公平”区域出现绝对空白：对于 Fair-VAE、对抗去偏（Adversarial Debiasing）和 LFR，在表征平等等级 $\varepsilon$ 趋于 0 时，组内类别信号呈现受斜率 $1/|\Delta p|$ 约束的线性压缩，坐标平面左上角（即小 $\varepsilon$ 且大信号的“理想区域”）在所有真实模型与随机种子上严格为空，有力证实了定理 5.1 和定理 6.1 所断言的表征坍缩机制。

亮点与洞察¶

将离散公平性指标统一于连续算子几何：该框架的一大亮点在于用再生核希尔伯特空间的条件均值嵌入将离散分布属性统一为单一内积算子，使得原本分散的各路不可行性证明（KMR、Chouldechova、Barocas 互不相容三角）收敛到了单一的全期望公式超定结构上。
将公平性审计重构为谱预算分配问题：传统公平性测试将合规视为“通过/不通过”的二元检验，而宝可梦定理将其重塑为“MMD 总预算分配问题”。群间分布差异构成了固定的物理预算，算子主特征方向给出了最优的审计优先级，为有限资源下的公平性审查提供了极小化极大谱截断依据。
确立了公平表征学习的本质局限：清晰界定了特征过滤器的理论天花板——在群体基础率失衡的前提下，试图依靠深度编码器无损抹除偏见并保留完全预测能力的构想在数学上是不可能的，强行过滤必然导致类别信号随之崩塌。

局限与展望¶

作者指出的理论边界：当前主要结论建立在二元受保护属性、二元输出标签与标量评分的基准假定上；尽管作者指出其可向 $K$ 群体（使用向量范数）、多分类及向量评分自然推广，但更复杂的交互结构仍需后续扩展。
观测性公平的范畴限制：本文的算子几何完全立足于观测分布（Observational Fairness），无法直接涵盖反事实公平（Counterfactual Fairness）或基于因果图的因果干预模型。
政策与工程层面的现实启示：当群体间存在显著的统计分布差异时，单纯依靠算法层面的损失约束或无偏特征抽取已无法从根本上解决问题，此时显式的差异化政策干预（如区分基准分数的专门化评级或政策性救济）才是合规且必要的手段。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 巧妙利用 RKHS 均值嵌入将公平性不可能性统一到几何正交补与 Kolmogorov 宽度，视角极具穿透力。
理论深度: ⭐⭐⭐⭐⭐ 证明严谨完备，涵盖从精确不可行性、谱衰减率到近似连续收敛桥梁的完整理论闭环。
实验充分度: ⭐⭐⭐⭐ 实验作为理论预言的实证一致性检验，紧密对应三大理论预测，统计检验与置信区间规范严密。
价值: ⭐⭐⭐⭐⭐ 澄清了公平特征学习与审计清单在实践中的理论天花板，为算法公平性设计指明了根本性界限。

检验项目与配置	门控阈值 (\(\tau\))	检验点总数	原始下界违规点数	Bootstrap 95% CI 统计违规点数	理论符合率
分离条件帕累托界 (宽松门控)	\(\mathrm{EO\_gap} \le 0.05\)	46 (Adult 12, COMPAS 11, ACS 23)	7 (Adult 0, COMPAS 5, ACS 2)	1 (仅 ACS 边缘点，裕度 0.0035)	97.8% (CI 视角)
分离条件帕累托界 (严格门控)	\(\mathrm{EO\_gap} \le 0.02\)	17 (Adult 2, COMPAS 3, ACS 12)	3 (Adult 0, COMPAS 2, ACS 1)	0	100.0%
表征学习禁用角检验 (Fair-VAE)	\(\rho = 0.15\)	多组 \(\lambda_{\mathrm{MMD}} \in [0, 10]\)	0	0	100.0% (无越界)
表征学习禁用角检验 (Adv-Debias)	\(\rho = 0.15\)	多组 \(\lambda_{\mathrm{adv}} \in [0, 10]\)	0	0	100.0% (无越界)
表征学习禁用角检验 (LFR)	\(\rho = 0.15\)	多组 \(A_z \in [0.1, 100]\)	0	0	100.0% (无越界)