前馈神经网络的个体公平性保证方法

+v：mala2277获取更多论文≥≥≤神经网络的个体公平性保证Elias Benussi1岁，Andrea Patane1岁，Matthew Wicker1岁，Luca Laurenti2岁，MartaKwiatkowska1岁2TU代尔夫特1{elias.benussi，andrea.patane，matthew.wicker，marta.kwiatkowska} @ cs.ox.ac.uk，2l. tudelft.nl摘要本文研究前馈神经网络的个体公平性的证明问题。特别地，我们使用了NN-δ-IF公式，该公式在给定NN和从数据中学习的相似性度量的情况下，要求任何一对NN-相似个体之间的输出差异以最大决策容差δ0为界。使用一系列度量，包括Ma- halanobis距离，我们提出了一种方法来过度近似所产生的优化问题，使用分段线性函数来下界和上界NN的非线性全局我们将此计算编码为混合线性规划问题的解决方案，并证明它可用于计算广泛用于公平性基准测试的四个数据集上的IF保证我们展示了如何通过修改NN损失来鼓励模型在训练时的公平性，并从经验上证实了我们的方法产生的NN比最先进的1介绍对于神经网络在公平性是相对重要的情况下的应用，人们提出了保留意见。cern [Barocas and Selbst，2018].由于存在于真实世界数据中的固有偏见，如果不加检查，这些模型被发现基于敏感特征（例如种族或性别）歧视个体[Bolukbasi等人，2016年，Angwin等人，2016年]。最近，这个话题受到了关注，技术越来越多地受到偏见的挑战[Hardesty，2018，Kirk等人，2021年，赫恩，2020年]，导致引入了一系列的定义和技术来捕捉公平的多方面属性。公平方法大致分为：群体公平[Hardt et al.，2016]，其检查了数据人口统计学模型;以及个体公平性（IF）[Dwork等人，2012]，它考虑了每个人的行为。尽管它被更广泛地采用，但群体公平性只关心模型的统计特性，因此情况可能通讯作者在特定个体可能认为组公平模型的预测不公平的情况下出现。相比之下，IF是一个最坏情况下的措施，保证在每一个可能的个人在输入空间。然而，虽然存在用于NN 的 组 公 平 性 的 技 术 [Albaghouthi 等 人 ， 2017 年 ，Bastani等人，2018]，迄今为止，对IF的研究仅限于设计有利于公平的培训程序[Yurochkin等人，2020年，Yeom和Fredrikson，2020年，McNamara等人，2017]和对特定个体的验证[Ruoss等人，2020年]。据我们所知，目前还没有针对NN的IF全球认证的工作。我们开发了一个具有可证明界的任意时间算法来证明神经网络上的IF。我们建立在John et al. [2020]采用的α-δ-IF形式化的基础上。也就是说，给定δ 0，δ0和捕获个体之间相似性的距离度量dfair，我们要求，对于每对点，x′和x′′在输入空间中，dfair（x′，x′′）≠ 0，则NN虽然与之相关，但NN上的IF认证提出了与对抗鲁棒性不同的问题[Tjeng等人，2019]，因为x′和x′′在这里都是问题变量，跨越整个空间。因此，在对抗性文献中开发的局部近似技术不能在IF的背景下使用。然而，我们展示了如何将这种全局非线性需求以混合线性规划（MILP）的形式进行编码，方法是在整个输入空间上对NN中的每个激活函数推导一组全局上下分段线性（PWL）边界，并对（通常为非线性）相似性度量进行线性编码dfair（x′，x′′）.我们的优化作为MILP的公式化允许我们计算IF上的任何时间，最坏情况的界限，因此可以使用标准求解器从全局优化文献[Dantzig，2016]。此外，我们演示了如何将我们的方法嵌入到NN训练中，以便在训练时优化个人公平性。我们通过对加权损失执行梯度下降来实现这一点，该加权损失也考虑了每个训练点的d个公平邻域中的最大δ变化，类似于对抗学习中所做的[Goodfellowetal.，2014年，Gowal等人，2018年，Wicker等人，2021年]。我们将我们的方法应用于公平性文献中广泛使用的四个基准，即成人，德国，信用和犯罪数据集[Dua和Graff，2017]，以及从包括l∞，arXiv：2205.05763v1 [cs.LG] 2022年5月+v：mala2277获取更多论文∈- 是的Σ{∈{}}→⊆⊆J× ›→≥Mahalanobis和NN嵌入。我们凭经验证明，我们的方法是如何能够提供第一个，非平凡的IF证书的NN通常采用 的 任 务 ， 从 IF 文 献 ， 甚 至 更 大 的 NN 包 括 多 达thousands的神经元。此外，我们发现，我们基于MILP的公平训练方法在IF保证方面始终优于使用竞争性最先进技术训练的NN，尽管计算成本增加了几个数量级。决策，例如 对于贷款申请[Hardt等人，2016年]。形式上，给定一个紧凑的输入集XRn和一个输出集YR，我们考虑一个L层全连通NNfw：XY，由一个权重向量w参数化RNW培训=（x i，y i），i1、......、n d.对于输入x X，i = 1，. . . ，L且j =1，. . . ，n i，则NN被定义为：ni−1φ（i）=W（i）<$（i−1）+b（i），<$（i）= σ（i）φ（i）（1）本文的主要贡献如下：1• 设计了一种基于MILP的随时验证方法jjj j jk=1用于将IF认证为NN上的全局属性。• 我们展示了如何我们的技术可以用来修改-其中，x（0）= x j。这里，n i是第i个单元的个数层r，W（i）和b（i）是它的权重和偏差，σ（i）是jk j在训练时，考虑到IF的认证，对NN的损失函数进行• 在四个数据集和一系列指标上，我们展示了我们的技术如何获得非平凡的IF证书，并训练比最先进的更公平的NN。相关工作许多作品都考虑了IF采用对抗鲁棒性的技术。Yeom和Fredrikson[2020]依靠随机平滑来找到模型中最稳定的每个特征差异。然而，他们的方法只提供了模型统计的（弱）保证Yurochkin等人[2020]提出了一种基于投影梯度下降和最优传输的IF训练方法。虽然该方法被发现，以减少模型偏差的最先进的结果，没有得到正式的保证。Ruoss等人[2020]调整了MILP公式的对抗鲁棒性，以处理公平的度量嵌入。然而，该方法不是如Dwork等人[2012]所介绍的那样全局地解决IF问题，而是仅在有限的数据集上迭代地工作，因此在模型中留下了不公平的可能性相比之下，我们通过激活和相似性度量的PWL绑定获得的MILP编码允许我们对任何可能的indi-vidence对提供保证Urban等人[2020]采用静态分析来证明因果公平性。虽然这种方法产生了全局保证，但它不能直接用于IF，而且不是随时都可以，这使得详尽的分析不切实际。John等人[2020]提出了一种计算IF的方法，但仅限于线性和核模型。MILP和线性松弛已用于在局部对抗环境中认证NN [Ehlers，2017，Tjeng等人，2019年，Wicker等人，2020年]。然而，局部近似不能用于全局IF问题。Katz等人[2017]、Leino等人[2017] [2021]考虑到全局鲁棒性，他们的方法被限制到LP度量。此外，它们需要Lipschitz常数的知识或限于ReLU。2个人公平我们专注于回归和二进制分类与神经网络与实值输入和独热编码的分类特征。2这样的框架通常用于自动化1证明和其他细节可以在附录中找到一个扩展版本的文件，可在http://www.fun2model。org/bibitem.php？key=BPW+22。2多类可以通过组件分析来处理。激活函数，φ（i）是预激活，φ（i）是激活。 NN输出是这些计算的结果，f w（x）：= f（L ）。在回归中，f w（x）是预测，而对于分类，它表示类别概率。在这本文我们关注IF文献中广泛使用的全连接NN[Yurochkin等人，2020，Urban等人，2020年，Ruoss等人，2020年]。然而，我们应该强调，我们的框架基于MILP，可以通过使用来自对抗鲁棒性文献的嵌入技术容易地扩展到卷积层、最大池层和批范数层或res-net（参见例如[Boopathy et al.，2019年]。给定NNfw，IF的个体公平性[Dwork等人，2012]强制执行相似个体被相似地对待的属性相似性是根据任务相关的伪度量dfair定义的：XR0，由领域专家提供（例如，Mahalanobis距离将每个特征与敏感特征进行比较），而处理通过NN输出fw（x）上的绝对差来表示。 我们采用John等人的α-δ-IF公式。[2020]输入输出IF相似性的形式化。定义1（α-δ-IF [John等人，2020年]）。考虑k≥0，δ≥ 0。 我们说fw是<$-δ-个别公平的w.r.t. D公平当且仅当x′，x′′s. t. dfai r（x′，x′ ′）≤n =n|fw（x′）−fw（x′ ′）|≤δ。在这里，δ度量个体之间的相似性，δ是结果的差异（分类的类概率）。我们强调，个体公平性是一个全局概念，因为定义1中的条件必须对X中的所有点对成立。我们注意到Johnet al. [2020]（其比文献中通常使用的IF制 剂 更通用[Yurochkin 等 人 ， 2020年 ， Ruoss 等 人 ，2020]）是由Dwork等人引入的Lipschitz性质的轻微变化。[2012年]。由于其参数形式，它引入了更大的灵活性，因此在测试时需要进行IF参数分析。在第4节中，我们分析了神经网络的δ-IF如何受到δ和δ的变化的影响。IF的一个关键组成部分是相似性公平。直觉是，敏感的功能，或其敏感的组合，不应该影响神经网络的输出。虽然在文献[Ilvento，2019]中已经讨论了许多指标，但我们专注于以下代表性的一组指标，这些指标可以从数据中自动学习[John等人，2020年，Ruoss等人，2020年，Mukherjee等人，2020年，Yurochkin等人，2020年]。关于度量学习的细节在附录B中给出。+v：mala2277获取更多论文√−−JJj，MJ我j，l∈i=1我我d公平ϵJJJJ加权l p：在这种情况下，dfair（x′，x′′）被定义为alp度量的加权版本，即dfair（x′，x′′）=3个人公平的MILP方法因此，NN上的个体公平性认证要求我们乌普萨拉θi|x′−x′ ′|p. 直观地说，我们将权重θi设为-将敏感特征归零，这样，如果两个人只是在这些方面不同，他们就被认为是相似的。其余特征的权重θi可以根据实际情况进行调整Maxx'，x''∈X|δ|根据它们与敏感特征的相关程度M ahalanobis：In 这 情况 我们 对于给定的半正定（SPD）矩阵S，有dfair（x′，x′′）=（x′x′′）TS（x′x′′）. Mahalanobis距离通过考虑特征的内部相关性来推广l2度量以捕获潜在的依赖性。敏感的特征。特征嵌入：在嵌入上计算度量，使得dfair（x′，x′′）=df ai r（x′，x′′），其中dfair（x′）是马氏度量或加权lp度量，并且f ai r（x ′，x ′′）是a特征嵌入图这些允许更大的建模灵活性，但代价是降低了可解释性。2.1问题表述我们的目标是证明NN的-δ-IF为此，我们正式两个问题：计算证书和培训IF。问题1（公平认证）。 给定一个训练好的NN f w，受 δ=fw（x′）−f w（x′′）（2）dfair（x′，x′′）≤ n.（三）我们开发了一个混合线性规划（MILP）过近似（即，提供一个声音边界）来解决这个问题。我们注意到这里有两个非线性源，一个由NN（等式（2））引起，我们称之为模型约束，另一个由公平性度量（等式（3））引起，我们称之为公平性约束。在下文中，我们将展示如何通过分段线性函数来模有界。在第3.3节中，我们将这些结果结合起来，推导出一个关于α-δ-IF的MILP公式。3.1模型约束我们开发了一个计划的基础上分段线性（PWL）的上限和下限过逼近所有常用的非线性激活函数。的图示相似度和距离阈值≥PWL界限如图1所示。 设φ（i）L和φ（i）U∈ R为δmax = maxx'，x“∈Xdfair（x'，x"）≤n|.|.预激活φ（i）的上下界。3我们通过在上的φ（i）值上构建离散化网格来进行处理。M个网格点：φgrid=[φ（i），. . . ，φ（i）]，其中φ（i）：=φ（i）Lj，0j，Mj，0j问题1提供了优化方面的公式，试图计算任何情况下的最大输出变化δmaxφ（i）[φ（i），φ（i）：=φ（i）U，使得在每个分割区间[1]，我们有σ（i）是凸的或凹的。dfair距离不大于0的一对输入点。j，l j，l+1然后可以将δmax与任何阈值δ进行比较：然后，我们计算线性下限和上限函数，wσ（i）在每个[φ（i），φ（i）]asfollows. 如果σ（i）是conve x（resp.则模型f已被认证为δIF。j，lj，l+1虽然问题1涉及已经训练好的NN，concav e）in[φ（i），φ（i）[1]，然后是一个上（resp.下）线性j，l j，l+1我们开发的方法也可以用于在训练时鼓励IF。 类似于对抗性学习的方法[Goodfellow et al.，2014]，我们修改训练损失L（fw（x），y）以平衡模型拟合和IF。问题2（公平培训）。 考虑一个NN f w，一个训练集D，一个相似性度量d fair和一个距离阈值界限由连接区间的两个极值点的线段给出，并且下限（分别为）上）线性界限由通过区间中点的切线给出。然后，我们计算每个网格点中每个线性边界的值，并选择下限值的最小值和上限值的最大值，存储在两 个 矢 量 中 ， U=[PWL ，（ i ） ， U，. . . ， UPWL ，（i），U]n≥ 0。 设λ ∈ [0，1]为常数。将IF公平损失定义为JPWLj，0j，M和，（i），L =[PWL，（i），L，. . . （i），L]. 以下Lfair（ fw（ x），y，fw（x≠），λ）=jj，0j，M我 我我λL（fw（xi），yi）+（1−λ）|fw（xi）−fw（x<$i）|、引理是这个构造的结果。引理1. 设φ∈[φ（i）L，φ（i）U]. 用l表示整数x为-其中r ex∈i=argmaxx∈Xs. t. D公平 （x，x）≤0|fw（xi）−fw（x）|.与φ落在其中的φ网格的划分有关，并考虑该训练问题被定义为寻找wfair s.t.：η[0，1]使得φ=ηφ（i）Lj，l−1 +（1 − η）φ（i）L。然后又道：nd（i）PWL，（i），LPWL，（i），Lwfair=argminLfair（ fw（ xi），yi）.解决以下全局非凸优化问题：0，计算+v：mala2277获取更多论文JJσ（φ）≥ηj，l−1 +（1−η）j，l，wi=1σ（i）（φ）≤η <$PWL，（i），U+（1−η）<$PWL，（i），U，在问题2中，我们试图训练一个NN，不仅是准确的，但其预测也是公平的，根据定义。也就是说，PWL，（i），Lj，l−1（i），Uj，l定义连续PWL1. 参数λ在精度和IF之间进行平衡。在上界和下界是φ在[φ（i）L，φ（i）U]中的下界和上界。J J特别地，对于λ= 1，我们恢复标准训练，不考虑IF，而对于λ= 0，我们只考虑IF。3通过X上的边界传播计算[Gowal等人，2018年]。+v：mala2277获取更多论文j，l∞J（i）Lj，lJe（ φ）≤φMσ′（φCIMM−通过推导一组近似约束，M MMJ−σ φ+ φ（一）（）下一页PWL，LPWL，图1：对于越来越多的分区点M（用红色刻度标记），将上下PWL函数转换为sigmoid。引理3.1保证了我们可以使用PWL函数来约束非线性激活函数。关键是，PWL函数可以被编码到MILP约束中。提案1. 设y（i），其中l= 1，. . .，M是二元变量，η（i）∈ [0，1]是连续变量. 考虑φ（i）∈附录A给出了命题2的证明，以及收敛速度的实验分析。我们注意到PWL界可用于所有常用的激活函数σ。唯一的假设是σ在R的任何紧区间上有有限个拐点。对于收敛性（Prop.2），我们重新-[φ（i）L，φ（i）U]，则推出了σ（i）=σ（i）。φ（i）φ意味着：quire几乎处处连续可微，j j j jφy（i）= 1，φη（i）= 1，φ（i）=φφ（i）Lη（i），y（i）≤通过常用的激活来满足3.2公平约束l=1j，ll=1Mj，lJl=1j，lMj，lj，l在MILP中的公平性约束的编码用于-η（i）+η（i），U_n（i），L_n（i）≤ U_n（i）≤U_n（i）.仿真取决于度量D公平的具体形式。j，lj，l+1l=1j，lj，l jl=1j，lj，l加权lp度量：加权lp度量可以被通过采用矩形近似区域。 虽然这证据可以在附录A中找到。命题1确保每个NN神经元的全局行为可以通过使用2M辅助变量的5个线性约束利用命题1，我们可以以合理的方式将等式（2）的模型约束编码为MILP形式过逼近误差不依赖于MILP公式（其是精确的），而是依赖于PWL边界，并且因此是可通过选择网格点的数目M来控制的，并且在极限中变得精确对于l度量是直接的，对于其余情况，可以使用区间抽象[Dantzig，2016]。Mahalanobis 度量：我们首先计算S 的正交分解为UTSU=Λ，其中U是S的特征向量矩阵，Λ是以S个特征值为元素的对角矩阵 考虑旋转变量z′=UT x′，z′′=UTx′′，则我们得到方程（3）可以重写当（z′−z′′）TΛ（z′−z′′）≤λ2时，通过简单的代数，我们有对于每个i，（z′−z′′）2≤<$2。通过转换回请注意，在ReLU激活函数的特定情况我我我原始变量，我们得到方程（3）可以超过-假设过近似对任何M > 0都是精确的。近似为：−є诊断（Λ） ≤UT x′−UT x′′≤- 是 的诊断（Λ）2号提案假设σ（i）是连续可微的特征嵌入度量我们处理的情况下，(i) L（i）U当e在[φj]中时，，φj[1]，除了可能在有限集合中。则PWL引理3.1当M趋于无穷大时一致收敛于σ（i）。此外，定义φM=（φ（i）Uφ ）/M，则 对于M的有限值，较低的误差（分别为，上）在凸（相应地）中的边界凹）的σ（i）区域，在度量定义中使用的，即dfair（x′，x′′）=dfair（x′，x′′），是一个NN嵌入。这是直接的，因为对于模型约束，可以将MLP编码到MILP3.3总的制剂φ∈[φ（i），φ（i）]]由下式给出我们 现在 制定 的 MILP 编码 为 过度-j，l j，l+1 ..ΣΣ）−σ′φ（i）近似值δε≥δmax。对于等式（2），我们12j，l+1j，l+12变量x′和x′′通过使用第3.1节。 我们将相应的变量表示为φ′（i），和上部（分别地，下）凹（分别凸）区域：J分别为φ′（i）和φ′′（i），φ′′（i）。NN在x′上的最终输出- 是的Σe（ φ）≤φ（一）j，lM−σ（φj，l）+σ′（φ（i）） .JJJ+v：mala2277获取更多论文而在x′′上则分别为′（L）和′′（L），因此，δ=′（L）−′′（L）。最后，我们过度近似方程200万美元j，l（3）如第3.2节所述。 在马哈拉诺比斯的案件中，+v：mala2277获取更多论文MM−≥δ=|F （x）−f（十）|∗j，l∞j，lj，lj，lj，l+1KKJJKKJJj，lj，lKK≤图2：不同架构参数（宽度和深度）的IF（δ）的认证界限以及成人和犯罪数据集的最大相似度（g）。顶行：用于d公平的Mahalanobis度量。底行：用于d公平的加权l∞度量。距离，我们因此得到：定理1，其证明可以在附录A中找到Maxx'，x''∈X|（四）|(4)指出，MILP问题的解决方案为我们提供了一个健全的估计个人公平的NN。重要的是它subjectto=′（L）−′′（L）对于i = 1，. . . ，L，j = 1，. . . ，ni，<$∈ {′，′′}：可以证明，用于求解MILP问题的分支定界技术在有限时间内收敛到最优解[Del Pia和Weismartel，2012]，而此外y<$（i）=1，l=1l=1为我们提供了每个迭代步骤的最优值的上限和下限。因此，我们有：推论1. 设δL和δU的上下界为ni−1M由MILP求解器在步骤k > 0处计算。 然后我们有：φf（i）=φW（i）x f+b（i），φf（i）=φφ f（i）Lηf（i）δ L≤δ U。此外，给定精度τ，存在∗k=1l=1有限k使得δUδ Lτ。也就是说，我们的方法是健全的，在任何时候，在每个迭代-Un（i），Lηt（i）≤Un（i）在MILP求解的步骤中，我们可以检索一个较低的l=1j，l ϵ2j，lj′l=1′′j，l ϵ2j，l上界δ，因此可以用来提供证明。能够保证在有限时间内收敛到δε-Udiag（Λ）≤Ux −Ux≤Δdiag（Λ）。复杂性分析该模型的编码虽然类似，但上述MILP与用于对抗鲁棒性的MILP显著不同（参见例如Tjeng等人[2019]）。首先，我们不是寻找固定点周围的扰动，这里我们有x′和x′′作为变量。此外，MILP在整个输入空间X上，π-δ-IF问题是全局的。因此，不能使用非线性的局部近似，因为边界需要在整个输入空间上同时有效。最后，虽然在对抗鲁棒性中，可以忽略最后的S形层，但对于IF，由于两个优化变量，不能简单地从最后的预激活值映射到类概率，因此即使对于ReLU NN，也需要为最终S形采用非分段激活的边界。通过结合本节的结果，我们得到：定理1. 考虑一个相似性d公平和一个NNfw. 设x′和x′′是方程（4）中优化问题的最优点。定义w′w′′。 则fw是f-δ-单独公平的w.r.t. d对δ ≥ δθ的情况是公平的。∗应变可以在O（LMnmax）中完成，其中nmax是fw的最大宽度，L是层数，M是用于PWL边界的网格点的数量。公平性约束的计算复杂性取决于所采用的相似性度量。虽然对于l没有处理- ING需要做的，计算复杂度为O（n3）的Mahalanobis距离和再次O（LMn最大）的特征嵌入度量。MILP求解器的每次 迭 代 都 需 要 解 决 线 性 规 划 问 题 ， 因 此 是 O（（MnmaxL）3）。MILP的有限时间收敛性精度为τ的δ的求解器是问题变量，在τ和τ中。3.4神经网络的公平性训练在第3节中介绍的α- δ -IF MILP公式可以适用于问题2的求解。关键步骤是计算问题2中引入的修正损失的第二个分量中的xi，该分量用于将公平性直接引入神经网络的损失工作这个计算可以通过观察来完成，因为+v：mala2277获取更多论文∗DD←←∅←∗′← − ∇←←X∗我11：XMILPX MILP12：结束联系我们从D的每个训练点xi，xi=argmaxx∈Xs.t. d（x，x）≤n|fw（xi）−fw（x）|是一个角色-第3节中描述的公式的典型情况，其中，不是有两个变量输入点，而是只有一个输入点是问题变量，而另一个输入点是给定的，并从训练数据集中提取. 因此，可以通过解决MILP问题来计算xi，其中我们固定一组概率，lem变量到xi，并且可以随后用于获得修改的损失函数的值。请注意，这些约束不是累积的，因为它们是为每个小批量构建的，并且在解决优化以更新权重之后被丢弃算法1使用MILP进行公平训练输入：NN架构：fw，数据集：，学习率：α，迭代：nepoch，批量大小：nbatch，相似性度量：dfair，最大相似性：g，公平性损失加权：λ。输出：w fair：在准确性和公平性之间平衡的权重值。b1：w公平初始权重（fw）2：对于t = 1，. . . ，n epoch do第三章：对于b = 1，. . . 、）的内容|D|/n batch ¶ do第四章：{X，Y} ← {xi，yi}n批次编号#样本批次W图3：NN的平衡准确性/个体公平性权衡。4实验5：是清洁 f（X）i=0时#标准向前传球在本节中，我们实证验证了6：[φ′，φ′]InitMILP（fw，dfair，g） #第3节7：XMILP8：对于i = 0，. . . n批剂量9：φ′i，φi′←FixV arConst（xi）#Fixconstraints10：xi←MILP（xSi，φi，φi′）#Sol v e'local'MILP prob.←我们的MILP公式用于计算Δ-δ-IF保证，以及用于NN的公平性训练。我们在四个UCI数据集上进行了实验[Dua和Graff，2017]：成人数据集（预测收入），信用数据集（预测支付违约），德国数据集（预测信用犯罪数据集（预测暴力犯罪）。在每一种情况下，特征编码的信息，十三日：YMILPf w（XMILP）#MILP输入前向传递十四日：LL公平（Y干净，Y，YMILP，λ）# 公 平 损失15：w公平w公平αWL#优化器步骤（这里，SGD）16：结束17：结束18：returnwfair#针对公平性准确性优化的我们在Algo中总结了我们的公平性训练方法或种族被认为是敏感的在认证实验中，我们采用MILP解算器的精度τ为10−5，截止时间为180秒。我们将我们的训练方法与两种不同的学习方法进行了比较：公平性-无意识（FTU），其中敏感特征被简单地移除，并且SenSR [Yurochkin等人，2020年]。截止值、组公平性、附加NN的认证、方法的可扩展性和附加细节的探索Rithm 1. 对于每个批次，时代 训练时期，附录D和C中给出了实验设置。4我们执行NN的前向传递以获得输出Yclean（第5行）。然后，我们制定的MILP问题，在第3节（第6行），并初始化一个空集变量，以收集解决方案的各种子问题（第7行）。然后，对于小批量中的每个训练点xi，我们固定MILP对与xi相关联的变量的约束（第9行），求解得到的MILP 以 得 到 xi ， 并 将xi 放 置 在 收集 解 的 集 合 中 ， 即XMILP。最后，我们计算XMILP上的NN预测（第13行）;结果用于计算通过采取梯度下降步骤来更新修改的损失函数（行14）和权重。所得到的权重集合w公平地平衡了训练点周围的经验准确性和公平性。λ的选择影响标准培训相对于r.t.公平性约束：λ= 1相当于标准训练，而λ= 0仅优化公平性。在我们的实验中，我们在一半的训练时期内保持λ = 1，然后将其更改为λ= 0。五、公平性认证我们分析了我们的方法在提供关于相似性阈值的非平凡证书时的适用性（我们从0. 01比0 25）、相似性度量dfair、NN的宽度（从8到64）及其层数（从1到4）。这些反映了IF文献中使用的NN和度量的特征[Yurochkin等人，2020年，Ruoss等人，2020，Urban等人，2020年];对于更大架构上的实验，展示了我们方法的可扩展性，请参见附录D.3。对于每个数据集，我们采用FTU方法训练NN。成人和犯罪数据集的分析结果见图2（信贷和German数据集的结果见附录D.1）。每个热图描绘了δ的变化作为Δ和NN架构的函数图中的顶行是通过考虑Mahalanobis相似性度量计算的;底行是[4] 该 方 法 和 实 验 的 实 现 可 以 在 www.example.com 上https://github.com/eliasbenussi/nn-cert-individual-fairness。+v：mala2277获取更多论文∞∗∗∗≥∗图4：经认证的δε作为最大相似度g的函数。计算加权的l度量（如Johnet al.[2020]），特征嵌入度量的结果见附录D.2。正如人们所预期的那样，我们观察到，在所有数据集和架构中，增加Δ k与δ值的增加相关，因为较高的Δ k值允许更大的特征变化。有趣的是，δ趋于减小（即，NN变得更公平）。这与对抗鲁棒性所观察到的相反，其中增加的容量通常意味着更脆弱的模型[Madry等人，2017年]。事实上，由于这些NN是通过FTU训练的，因此NN无法访问主要的敏感特征一个可能的解释是，随着层数的增加，NN结果表明，过度参数化的神经网络可能更善于解决公平的任务- 尽管这将伴随着模型可解释性的损失，并且将需要探索以评估在何种条件下这保持不变。最后，我们观察到，我们的分析证实了FTU训练通常不足以为Δ-δ-IF的模型行为提供公平性。对于每种模型，不相似的个体为100。25已经可以产生δ >0。5，这意味着如果使用标准分类阈值0，他们将被分配到不同的类别。五、公平性训练我们研究了我们的公平性训练算法的行为，以 改 善 NN 的 δ 我 们 将 我 们 的 方 法 与 FTU 和 SenSR[Yurochkin等人，2020年]。为了便于比较，在本节的其余部分中，我们用dfair等于Mahalanobis相似性度量来衡量公平性，其中d= 0。2，SenSR就是为此而开发的。该分析的结果如图3所示，其中散点图中的每个点表示针对给定NN架构获得的值。我们训练最多有2个隐藏层和64个单元的架构，以便具有可比性Yurochkin等人训练的人。[2020年]。正如预期的那样，我们观察到FTU在经认证的公平性方面表现最差，因为敏感特征的简单省略无法混淆敏感特征和非敏感特征之间的潜在依赖性。如先前在文献中所报道的，SenSR通过考虑特征潜在依赖性来显著改进FTU。然而，在所有四个数据集上，与SenSR相比，我们基于MILP的训练方法在所有架构中始终提高IF的数量级。特别是，对于具有 多 于 一 个 隐 藏 层 的 架 构 ， 平 均 而 言 ， MILP 优 于FTU78598倍，SenSR27739倍。直观地说，虽然SenSR和我们的方法具有类似的公式，但前者基于梯度优化，因此在最坏情况下无法保证训练损失。相比之下，通过依赖MILP，我们的方法在每一步都优化了NN的最坏情况行为，这进一步鼓励了单独公平模型的训练当然，显著改进的保证的成本是更高的计算成本。事实上，使用MILP对图3中的模型进行训练的平均训练时间约为 3小时虽然增加的成本是显着的，我们强调，这是一个成本，只支付一次，可能是合理的，在敏感的应用程序的必要性，公平的部署时间。我们还注意到，虽然我们的实现是顺序的，但在训练过程中MILP问题的每批并行解决方案将显着减少计算时间，并为将来的工作留下技术的并行化和张量化有趣的是，我们发现，在这里考虑的任务中，SenSR和MILP训练的平衡准确性也略有提高，可能是由于类标签w.r.t.中的偏差敏感特征。最后，在图4中，我们进一步分析了经认证的δ-曲线w.r.t.与输入相似度Δ f的关系，改变用于Δ f-δ-IF的认证的Δ f 在实验中，SenSR和MILP都是在k = 0的情况下训练的。2，这意味着我们的方法，基于正式的IF证书，保证优于SenSR，直到n= 0。2（事实上是这样的）。超过0。2，不能做出这样的声明，并且在特定情况下SenSR在理论上仍然有可能优于MILP。然而，根据经验，基于MILP的训练在获得认证的公平性方面仍然在很大程度上优于SenSR。5结论基于PWL边界和MILP编码的非线性度和相似性度量，提出了一种基于MILP的任意时刻的神经网络中δ-IF的认证和训练方法在包括四个数据集，广泛采用的NN架构和三种类型的相似性度量的选择的实验评估中，我们凭经验发现，我们的方法能够提供NN中的α-δ-IF的第一个非平凡证书，并产生NN，一致地，比通过竞争性IF训练技术获得的数量级致谢本项目由ERC欧盟地平线2020研究和创新计划资助834115）。+v：mala2277获取更多论文引用Aws Albarghouthi，LorisFairSquare：程序公平性的概率验证在OOPSLAACM，2017年。朱莉娅·安格温，杰夫·拉森，苏里亚·马图，劳伦·基什内尔.机器偏见：有软件在全国范围内使用，以预测未来的罪犯。而且它ProPublica，2016.Solon Barocas 和 Andrew D. Selbst. 大 数 据 SSRN 电 子 期刊，2018年。Osbert Bastani，Xin Zhang，and Armando Solar-Lezama.通过浓度对公平属性的概率验证，2018年。Tolga Bolukbasi ， Kai Wei Chang ， James Zou ，Venkatesh Saligrama，and Adam Kalai.男人对于计算机程序员就像女人对于家庭主妇一样？消除字嵌入的偏置。InNeurIPS，2016.Akhilan Boopathy，Tsui-Wei Weng，Pin-Yu Chen，SijiaLiu，and Luca Daniel. Cnn-cert：一个用于证明卷积神经网络鲁棒性的有效框架。在AAAI，第33卷，2019年。乔治·丹齐格线性规划与扩展普林斯顿大学出版社，2016年。阿尔贝托·德尔·皮亚和罗伯特·韦斯曼特尔。关于混合整数规划的收敛性。Mathematical Programming，135（1）：397迪鲁·杜瓦和凯西·格拉夫UCI机器学习存储库，2017年。辛西娅·德沃克，莫里茨·哈特，托尼娅·皮塔西，奥默·莱因戈尔德，理查德·泽梅尔。通过意识实现公平 。 ITCS 2012 - Innovations in Theoretical ComputerScience Conference，2012。鲁迪格·埃勒斯分段线性前馈神经网络的形式化验证。在ATVA。Springer，2017.Ian J Goodfellow，Jonathy Shlens，and Christian Szegedy.解 释 和 利 用 对 抗 性 的 例 子 。 arXiv 预 印 本 arXiv ：1412.6572，2014年。SvenGowal ， KrishnamurthyDvijotham ， RobertStanforth ， Rudy Bunel ， Chongli Qin ， JonathanUesato ， Relja Arand-jel o vi c' ， Timot h yMann ，andPushmeetKohli. 关于区间界限传播对训练可验证的鲁棒模型的有效性，2018年。拉里·哈德斯蒂研究发现商业人工智能系统中的性别和肤色偏见，2018年2月。Moritz Hardt，Eric Price，Nathan Srebro.监督学习中的机会平等。InNeurIPS，2016.亚历克斯·赫恩Twitter为“种族主义”的图像裁剪道歉克里斯蒂娜·伊尔文托 个人公平的度量学习。arXiv电子印刷品，第arXiv：1906.00250页，2019年6月。Philips George John 、Deepak Vijaykeerthy和DiptikalyanSaha。机器学习模型中的个人公平性，2020年。Guy Katz，Clark Barrett，David L Dill，Kyle Julian，andMykel J Kochenderfer. Reluplex：一个用于验证深度神经网络的高效SMT求解器。在CAV。Springer，2017.汉娜·柯克，杨尼·君，海德尔·伊克巴尔，埃利亚斯·贝努西，菲利普·沃尔平，弗雷德里克·A. 亚历山大·施泰德里茨基和浅野由纪·马库斯博士。gpt-2有多真实？交叉职业偏见的实证分析。2021年Klas Leino，Zifan Wang，and Matt Fredrikson.全局鲁棒神经网络。arXiv预印本arXiv：2102.08452，2021。AleksanderMadry ， AleksandarMakelov ， LudwigSchmidt，Dimitris Tsipras和Adrian Vladu。迈向深度学 习 模 型 抵 抗 对 抗 性 攻 击 。 arXiv 预 印 本 arXiv ：1706.06083，2017。Daniel