机器学习模型的黑盒公平性测试

论文摘要

任何给定的人工智能系统都不能被接受，除非它的可信度被证明。值得信赖的人工智能系统的一个重要特征是没有算法偏见。“个体歧视”存在于给定个体与另一个体仅在“受保护属性”（如年龄、性别、种族等）上不同，但是它们会从给定的机器学习（ML）模型中得到不同的决策结果。目前的工作是解决给定 ML 模型中存在的个体歧视问题。在黑盒环境下，个体歧视的检测是测试密集型的，这对于非平凡的系统是不可行的。我们提出了一种自动生成测试用例进行输入的方法，用于检测个体歧视的任务。我们的方法结合了两种成熟的技术——符号执行和局部可解释性，以实现有效的测试案例生成。我们实证表明，与所研究的最著名的基准系统相比，我们生成测试用例的方法是非常有效的。

论文介绍

模型的偏见。这十年随着人工智能（AI）的复苏，AI 模型已经开始在很多系统中承担关键性的决策--从招聘决策、审批贷款到设计无人驾驶汽车。因此，为了确保人工智能系统被广泛接受，人工智能模型的可靠性是最重要的。可靠的 AI 系统的一个重要方面是确保其决策的公平性。偏见可能以多种方式存在于决策系统中。它可以以群体歧视的形式存在，即两个不同的群体（例如，基于性别/种族等“受保护的属性”）获得不同的决策。需要注意的是，歧视感知系统需要经过训练，以避免对敏感的特征进行歧视，这些特征被称为“受保护的属性”。受保护的属性是特定于应用的。年龄、性别、种族等特征是一些经常出现的例子，许多应用实际都将其作为受保护属性。

个体歧视。在本文中，我们讨论了机器学习模型中检测个体歧视的问题。我们在本文中使用的个体公平性/偏见的定义是一种简化的、非概率的反事实公平性，这也符合 Dwork 的个体公平性框架。如本工作所述，如果对于任何两个仅在受保护属性上有差异的有效输入，总是被分配到相同的类别，那么系统就被称为是公平的（如果对于某对有效输入，产生了不同的分类，那么就被称为存在偏差）。这样的偏差情况在之前的模型中已经被注意到了，并对模型生成者造成了不利的后果。因此，检测这类情况是最重要的。需要注意的是，从训练数据中删除受保护的属性并不能消除这种偏见，因为由于受保护属性和非受保护属性之间可能存在的共同关系，个体歧视可能仍然存在，就像成人人口普查收入数据中的种族（受保护）和邮编（非受保护）一样。因此，我们面临的挑战是，如何评估和找到非保护和保护属性的所有值，让模型显示出这种个体歧视行为。

现有技术及其缺点。衡量个体歧视需要进行详尽的测试，这对于一个非平凡的系统来说是不可行的。现有的技术能生成一个测试套件来确定模型中是否存在个体歧视以及个体歧视的程度。THEMIS 从域中选择所有属性的随机值，以确定系统是否在个体之间进行歧视。AEQUITAS 分两个阶段生成测试用例。第一阶段通过对输入空间进行随机采样来生成测试用例。第二阶段开始时，将第一阶段产生的每个判别输入作为输入，并对其进行扰动，以产生更多的测试用例。这两种技术的目的都是为了产生更多的测试输入。尽管上述这两种技术适用于任何黑盒系统，但我们的实验表明，它们会遗漏许多这样的非保护属性值组合，而这些组合可能存在单独的判别。我们还希望覆盖模型更多样化的路径，以生成更多的测试输入。

我们的方法。我们的目的是对特征空间进行系统化搜索，以覆盖更多的空间，而不需要太多的冗余。存在基于符号评估的技术，通过系统地探索程序中的不同执行路径来自动生成测试输入。这种方法避免了生成多个输入，因为这些输入倾向于探索相同的程序路径。这类技术本质上是白盒技术，利用约束求解器的能力来自动创建测试输入。符号执行从一个随机输入开始，分析路径生成一组路径约束条件（即输入属性的条件），并迭代地切换（或否定）路径中的约束条件，生成一组新的路径约束条件。然后，它使用约束求解器对所得的路径约束进行求解，以生成一个新的输入，这个输入可能会把控制带到新的路径上。我们的想法是使用这种动态符号执行来生成测试输入，这有可能导致发现 ML 模型中的个体歧视。然而，现有的这种技术已经被用来生成可解释程序的程序输入。我们的主要挑战是如何将这种技术应用于不可解释的机器学习模型。

• 限制条件。可以使用现成的局部解释器来生成路径的线性近似。从一个这样的解释器中得到的线性约束可以用于符号评价，这将不需要任何专门的约束求解器。
• 数据驱动。我们的算法可以利用已知的数据，这些数据可以作为种子数据开始搜索。
• 全局和局部搜索。一旦找到一个单独的判别，我们就进行局部搜索，以发现许多输入组合，从而发现更多的判别。否则，我们使用符号执行进行全局搜索，以覆盖模型中的不同路径。
• 优化。局部解释器呈现与谓词相关的置信度。我们的算法根据约束条件的置信度得分来执行对其进行切换的选择。
• 可扩展性。我们的算法通过切换特征相关的约束来系统地遍历特征空间中的路径。这使得它具有可扩展性，不像其他技术那样考虑基于结构的覆盖标准。

贡献：我们的贡献如下。

• 我们提出了一种新的技术来寻找模型中的个体歧视。
• 我们开发了一种新的动态符号执行和局部解释的组合，以生成非可解释模型的测试用例。我们相信，局部解释器的使用将为黑盒 AI 模型的基于路径的分析开辟许多途径。
• 我们在几个具有已知偏差的开源分类模型上展示了我们技术的有效性。我们将我们的技术与现有的算法即 THEMIS、AEQUITAS 进行了实证比较，并展示了我们的方法比这些先前的工作所带来的性能改进。

算法

我们将我们的算法分为两种不同的搜索算法，分别称为全局搜索和局部搜索。

下面是我们想通过设计的测试用例生成技术达到两个优化标准。有效的测试用例生成：给定一个模型 M，一组领域约束条件 C 和受保护属性集 P，目的是生成测试用例，以最大限度地提高|Succ|/|Gen|的比率，其中 Gen 是算法生成的非受保护属性值组合的集合，Succ ⊆Gen 可导致歧视，即 Succ 中的每个实例对不同的受保护属性值组合至少产生一个不同的决定。下面是关于这个标准的几个指标：

• 测试用例。每个测试用例不被视为所有属性值的集合，而只被视为非保护属性的集合。这确保了多个判别性测试用例不会被计入相同的非保护属性值组合。
• 领域约束。我们假设应用领域约束 C 可以过滤掉不真实的测试用例。
• 生成和判别测试的顺序。优化标准并没有规定所有的测试用例是否一次生成，也没有规定检查判别和生成是否可以同时进行。这样测试用例的生成也可以依赖于判别检查。

在软件测试领域，存在一些预定义的覆盖标准。在最近关于机器学习的著作中也定义了许多这样的覆盖标准。接下来，我们定义路径覆盖标准，使其适用于不同类型的模型。

覆盖标准：请注意，为任何黑盒模型定义路径覆盖标准都不是简单的。可以根据不同类型的模型的操作特点来定义其路径。例如，可以根据神经元的激活来定义神经网络中的路径，也可以定义决策树分类器中的决策路径。

我们将覆盖标准定义如下。给定一个分类模型 M 和一组测试用例 T，我们将 T 的覆盖率定义为 M 的决策区域被 T 执行的数量。

在本文中，我们使用决策树分类器来逼近模型 M 的行为，我们生成高精度的决策树模型来逼近 M 的决策区域，我们测试用例生成技术的目的是最大化路径覆盖率和个体歧视检测。

在实践中，自动测试用例生成过程总是有一个极限，在这个极限范围内，需要完成这两个目标的最大化。在我们的案例中，我们考虑了两个这样可能的限制：1）生成测试用例的数量 2）生成时间。

路径覆盖率最大化是通过利用符号执行算法的能力来实现的，该算法迎合了对不同执行路径的系统探索。。最大化路径覆盖率是在全局搜索模块中完成的，正如我们在最终算法所提到的。

符号执行和局部模型近似路径的思想的直接应用有三大挑战。前两者的产生是由于局部模型中存在的固有近似，而符号执行则是第三种的原因。

• 近似。决策树路径根据可解释的特征近似于实际执行路径。由于这样的近似，可以生成实际程序路径的重复。
• 可信度。决策树路径有一个与所有组成的谓词相关联的置信度得分（而程序路径则不是这样）。因此，挑战在于设计一种方法来使用这个置信度分数来更好地探索路径。
• 程序测试中的符号执行存在路径爆炸问题，尤其是在深度优先搜索方式下。它可以一直探索程序树深度的路径，而不探索程序其他部分的路径。研究者们已经探索出各种技术来解决这个问题——应用需求驱动或定向技术，向着程序中的某个特定位置生成测试用例，以及组合技术，试图分别分析各种功能模块，然后再将它们组合起来，在整个程序中生成更长的路径。所有这些技术都利用了被测程序的结构。

最大限度地提高歧视检测效率

检查个体歧视。首先，让我们考虑一下检查个体歧视的情况，如算法 2 所示。该算法按照个体歧视的定义来执行检查。如果一个测试用例保持其非保护属性集的值不变，但通过尝试各种可能的组合来改变其保护属性集的值，从而产生不同的类标签，那么这个测试用例被认为是具有个体歧视性的。

本地搜索。如前文所讨论的符号执行，试图找到测试输入以最大化路径覆盖率。我们把这样的符号搜索策略称为全局搜索。通过种子数据或符号执行产生的一些测试输入将具有鉴别性。为了增加歧视性测试用例的可能性，我们利用了这样一个事实：我们可以执行测试用例并检查它们是否具有判别性，然后根据这一点，生成更多的测试用例。

一旦发现了一个具有歧视性的测试用例，比如说 t，我们就尝试进一步生成更多的测试输入，这可能会导致个体歧视。关键思想是否定 t 的决策树的非保护属性约束，以生成更多的测试输入。通过切换一个与非保护属性相关的约束，并生成一个解决结果约束的输入，算法试图探索判别路径 p 的邻域，这种形式的符号执行就是我们所说的局部搜索，因为它倾向于搜索判别测试案例的局部性。这种方式之所以有效，是因为机器学习模型固有的对抗性鲁棒性属性，它证明了输入的微小扰动会导致分类器决策的改变。

粘性解决方案。局部搜索和全局搜索的目的是遍历尽可能多的路径。局部搜索集中在探索判别路径附近的路径，即由判别输入产生的路径。因此，我们只能得到一个约束的解。但是，为了照顾到局部线性模型可能引起的相似情况，我们使用与前一个约束（与判别输入有关）的解接近的约束求解器的解。我们把这样的解称为粘性解。由于粘性，如果我们否定了一个谓词，那么对于剩下的谓词，它就会趋向于取与前一个解相同的值。

本地搜索和全局搜索的排序。在综合算法 2 中，提出了三个参考等级，即 Rank1、Rank2 和 Rank3，分别为种子输入、本地搜索和全局搜索各一个。这些等级的设置方式是：根据其发现引起歧视的输入的能力，给予本地搜索最高的优先级，其次是种子输入，进一步是全局搜索（见算法 2 的第 3、18、32 行）。

实验评估

基线特征。我们对表 1 所列的 8 个不同来源的开源公平性基线进行了实验。

配置。我们的代码是用 Python 写的，用 Python 2.7.12 执行。所有的实验都是在运行 Ubuntu 16.04 的机器上进行的，有 16GB 内存，2.4Ghz 的 CPU，运行 Intel Core i5。我们使用了 LIME 来进行局部解释。我们使用 K-means 对输入的种子数据进行聚类。由于我们的用例需要在较少的时间内生成更多的测试用例，K-means 是最简单和最快的聚类算法之一，被证明是一个合理的选择。事实上，用于运行我们的实验的数据集具有两个或四个真正的类标签，这推动了将聚类数设置为 4 的逻辑假设。 这一点使用散点图进一步验证，如图 2 所示，它清楚地描绘了种子数据中的四个不同的聚类。

与 THEMIS 的比较。我们从他们的 GitHub 仓库中获取了 THEMIS 的代码，在仔细分析他们的代码后，我们发现了开放源码中的一个意外行为。THEMIS 实际上生成了重复的测试用例，他们报告的实验统计也包含了这些重复的测试用例。这是随机测试用例生成带来的问题之一，因为它会产生重复的测试用例。我们对 THEMIS 的代码进行了修改，以去除重复的测试案例，用于我们的实验评估。

与 AEQUITAS 比较。AEQUITAS 算法在两个搜索阶段运行--全局和局部。全局阶段考虑测试用例数量的限制，并通过对输入空间的随机抽样来生成测试用例。在所有这些生成的测试用例中，有少数测试用例具有鉴别性。然后，局部阶段开始将全局搜索阶段确定的每个判别性输入作为输入，并对其进行扰动，以进一步生成更多的测试用例。这个阶段就像之前的全局搜索一样，考虑了对生成的测试用例数量的限制。他们应用了三种不同类型的扰动，导致算法的三种不同变化。

全球搜索比较。表 5 是 SG 与 AEQUITAS 在全局搜索策略方面的比较。我们的全局搜索方法使用聚类种子数据和符号执行，而他们的策略则使用输入空间的随机采样。从统计结果可以看出，一般来说，我们的算法生成的输入有更多的判别性。

我们进行了一个实验来比较我们的全局搜索和基于随机数据的搜索的路径覆盖率。基于随机数据的搜索已经被应用于 THEMIS 和 AEQUITAS。因此，本实验提出了与现有相关工作的比较。为了进行路径覆盖，我们学习了一个精度为 85%-95%的决策树模型，对每个基准使用 5 倍交叉验证来测量，并将每个生成的测试输入映射到决策树模型的路径上。表 7 的结果显示，在所有的基准中，SG 的平均路径覆盖率是随机数据的 2.66 倍。这个结果表明，在路径覆盖率指标上，我们优于其他算法。因此，我们的算法将能够在模型的各个不同地方找到偏见性的输入。这一点很重要，因为在一次实验中，如果我们使用测试用例进行再训练，我们可以对模型的多个部分进行去偏见。

论文总结

在本文中，我们提出了一种测试用例生成算法，用于识别机器学习模型中的个体歧视问题。我们的方法结合了符号评价的概念，它为任何程序系统地生成测试输入，并使用线性和可解释的模型来近似模型中的执行路径的局部解释。我们的技术还提供了一个额外的优势，因为它是黑盒性质的。我们的搜索策略主要横跨两种方法，即全局搜索和局部搜索。全局搜索迎合了路径覆盖率的要求，有助于发现初始的判别输入集。为了实现这一点，我们使用种子数据与符号执行，同时考虑本地模型中存在的近似，并智能地使用与本地模型中获取的路径约束相关的置信度。此外，局部搜索的目的是寻找越来越多的判别性输入。它从初始的可用判别路径集开始，并生成属于附近执行路径的其他输入，从而系统地进行局部解释，同时依靠对抗性鲁棒性属性。我们的实验评估清楚地表明，我们的方法比所有现有的工具表现得更好。

致谢

本文由南京大学软件学院 2019 级硕士郭子琛翻译转述。