任何给定的人工智能系统都无法被接受除非它被证明可信任。可信任的AI系统的一个重要特性是没有算法偏差。当一个给定的个体仅仅在“受保护属性”(如年龄、性别、种族等)上与另一个个体不同时，给定的机器学习(ML)模型得到的决策结果与另一个个体不同时，就存在“个体歧视”。现有工作解决了给定模型中个体歧视出现的检测问题。个体歧视的测试在黑盒环境下是测试密集的,这对于一些不平凡的系统是不可行的。为了检测个体歧视的任务，我们提出了测试输出自动生成的方法。我们的方法结合了两个公认的技术-有效测试用例生成方面的符号计算和本地解释性。我们的经验表明，相比于其他知名的基准测试系统，我们对于测试用例生成的方法是非常有效的。
1. 介绍
模型偏差。这个时期标志着人工智能的复兴，AI模型开始对一些系统有重要的决策，比如雇佣决定，信贷批准，甚至是设计无人驾驶汽车。因此，AI模型的可依赖性对于确保AI系统得到更广泛的信任是至关重要的。可信赖AI系统的一个重要方面是确保决策公平。偏见可能以多种方式存在于一个决策系统中。它可以以群体歧视的形式存在，即两个不同的群体(如性别/种族)得出不同的决定，或者通过个人歧视，在两个样本之间进行歧视。值得注意的是，歧视感知系统需要训练，以避免歧视敏感的特征（即受保护的属性）。受保护属性是特定于应用程序的。年龄、性别、种族特点等特征是许多应用程序是为受保护属性的常见例子。
个体歧视。本文中，我们解决了机器学习模型中个体歧视检测问题。本文中使用的个体公平/偏差的定义是反事实公平一个简化且非概率的形式，并适用于个体公平的Dwork框架。正如本文所述，如果对于任何两个只有受保护属性不同的有效输入总是分配相同的类，那么系统就是公平的(如果对于某一对有效输入产生不同的分类，那么就说存在偏差)。这种偏见对模型生成器产生不利的结果。因此，这些案例的检测至关重要。注意，不能通过从培训数据中删除受保护属性来消除这种偏见，因为受保护属性和不受保护属性之间可能存在共同关系，就像成人人口普查收入数据集中的种族(受保护)和邮政编码(不受保护)情况一样，个人歧视可能仍然存在。这是间接歧视的一个例子，对于相关的不受保护的属性，仍然需要进行个人歧视测试。因此，挑战在于评估和发现所有未受保护和受保护属性的价值，模型证明了这样一种个体歧视行为。
现有技术及其缺陷。衡量个人歧视需要详尽的测试，但这对不平凡的系统是不可信的。现有的技术，比如THEMIS,AEQUITAS,生成一个测试套件来决定模型是否存在以及多大程度的个人歧视。THEMIS从域中为所有属性选择随机值，以确定系统是否在个体之间进行区分。AEQUITAS分两个阶段生成测试用例。第一阶段通过在输入空间上执行随机抽样来生成测试用例。第二阶段首先将第一阶段中生成的每个歧视性输入作为输入，并对其进行干扰以生成更多的测试用例。这两种技术都旨在产生更多的判别输入。尽管上述两种技术适用于任何黑盒系统，但我们的实验表明，它们忽略了许多可能村子啊个体歧视的非受保护属性值组合。我们希望覆盖模型的更多路径去生成更多的测试输入。
我们的方法。我们的目标是在覆盖空间没有太多冗余的情况下，对特征空间进行系统的搜索。基于符号计算的技术可以通过系统地探索程序中的不同解析路径来自动生成测试输入。这个方法避免了产生多个往往探索同一程序路径的输入。这样的技术本质上是白盒，利用约束解决程序的能力来自动创建测试输入。符号计算以随机输入开始，分析路径以生成一系列路径约束和在路径中迭代切换约束以生成一系列新的路径约束。它使用一个约束求解器来解决生成的路径约束，从而生成一个新的输入，这个输入可能会将控制带到新的路径。我们的想法是使用这样的动态符号计算来生成测试输入，这可能导致发现机器学习模型中的个体歧视。然而，这样的技术已经被用于为可解释性的程序化程序生成输入。我们的主要挑战是将这样的技术适用于无法符号性计算不可解释性的模型。值得注意的是，与THEMIS相似，我们的目标是构建一个可扩展性的黑盒解决途径，它可以有效应用于各种模型。黑盒分析将启用AI测试服务，其中第三方机器学习模型以访问API的形式提供作为输入，同时提供一些有效载荷/训练数据。
挑战。现有的一些工作试图使用符号计算为基础的技术，如深层神经网络等非解释性模型，虽然他们没有解决可能存在于模型的个人歧视发现问题。这些技术本质上是白盒技术，并试图近似网络中存在的函数(relu/sigmoid)。因此，他们迎合一个特定类型的网络，而不是一般化。其他测试用例生成技术使用依赖于结构的覆盖标准(如神经元覆盖、符号覆盖等)，因此这些技术受到可伸缩性的影响。
解决方案概述。在这篇论文中，我们的关键思想是使用本地可解释的模型作为符号计算的路径。像LIME这样的局部解释器可以以模型不可知的方式生成与输入相对应的决策树路径。然后切换决策树路径中的决策以生成一组新的约束。接下来，我们列出我们的方法的几个优点和显著特点。

  • 约束。可以使用现成的本地解释器生成路径的线性近似。从这样一个解释器获得的线性约束可以用于符号求值，而不需要任何专门的约束求解器。
  • 数据驱使。我们的算法可以利用存在的数据，作为种子数据开始搜素。
  • 全局和局部搜索。一旦一个个人歧视被发现，我们使用局部搜索以发现许多结合的输入，从而发现更多的歧视。否则，我们使用符号计算进行全局搜索以发现模型中不同的路径。
  • 优化。本地解释器表示与谓词关联的置信度。我们的算法根据约束的置信度来选择约束进行切换。
  • 可扩展性。我们的算法通过切换特征相关约束系统地遍历特征空间中的路径。这使得它具有可扩展性，不像其他技术那样考虑基于结构的覆盖标准。
贡献。我们的贡献如下所列。

  • 我们展示了一种模型中发现个人歧视的新技术。
  • 我们开发了一个新颖的结合动态符号执行和地方解释生成测试案例的非解释性模型。我们相信本地解释器的使用将为基于路径的黑盒人工智能模型分析开辟许多途径。
  • 我们证明了我们的技术对于几个有已知偏差的开源分类模型的有效性。我们将我们的技术与现有的算法，即THEMIS，AEQUITAS进行了实际的比较，并演示了我们的方法在这些先前的工作中所提供的性能改进。
2. 背景
动态符号计算
动态测试符号计算(DSE)在收集不同输入的执行路径约束时，通过检测和运行程序来执行自动测试生成。它系统地切换一组路径约束中的谓词生成一组新的路径约束，其解决方案生成新的输入以进一步探索新的路径。请注意，这种技术迎合了路径覆盖，因此不生成任何冗余输入。还需要指出的是，路径覆盖率标准比分支/决策覆盖率和语句覆盖率更强。
局部解释能力
本地可说明的不可知模型的解释(LIME)包括解释技术，它们以可解释的和忠实的方式解释任何分类器或回归器的预测。它能够做到这一点，通过本地围绕预测近似它作为一个可解释的模型。它以可解释性的预测模型的形式生成解释，如线性模型、决策树或下降规则列表，用户可以很容易地通过可视化或文字伪装。给定一个输入数据实例及其由分类器分级的输出，LIME通过扰动输入数据点在实例附近生成数据点并生成输出。利用这样的输入和输出，它通过最大化局部保真度和可解释性来学习一个可解释的模型。我们使用LIME来解释一个模型的预测实例，并生成一个决策树作为一个预测的可解释模型。
3. 算法
本节，我们分3个部分讨论全部的解决方法。第一部分讨论不同情况下测试用例生成技术的目标。将我们的算法分为全部和局部两种搜索算法。
3.1 问题的形成
有效测试用例生成：给定一个模型M，一组域约束C和一组受保护的属性集P，目的是生成测试用例以最大化|Succ|/|Gen|的比例，其中Gen是由算法和Succ产生的一组非受保护的属性值组合，这些属性值组合导致了歧视，即Succ中的每个实例对受保护的属性值的不同组合产生至少一个不同的决策。
覆盖率标准：注意，为任何黑盒模型定义路径覆盖率标准并不简单。这是可以基于它们操作特点不同类型的模型定义路径。例如，可以根据神经元的激活(类似于分支覆盖)，和决策树分类器中的决策路径。
本文使用决策树分类器来近似模型M的行为。我们生成高精度的决策树模型来逼近M。
我们的测试用例生成技术的目标是最大化路径覆盖率和个体识别检测。在实践中，自动测试用例生成过程总是有一定的限制，在这个过程中需要最大限度地实现两个目标。在我们的例子中，我们考虑两个可能的限制:1)生成测试用例的数量，2)生成测试用例所需的时间。
在随后的小节中，我们提出了我们的算法，旨在最大化路径覆盖率和有效地检测判别，以及如何将两者结合起来。


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

  • 路径创建。
  • 解决路径爆炸。
  • 解决近似的局部模型。
  • 基于置信度的排名。
  • 置信阈值。
3.3 最大化歧视检测的效率

  • 检查个体歧视。
  • 本地搜索。
  • 牢固的解决方案。
4. 实验评估
4.1设置

  • 基准特性。如表1所示，我们已经从不同来源对八个开放源码公平性基准进行了测试。
  • 配置。我们的代码是用Python编写并用Python2.7.12执行的。所有的实验都是在一台运行Ubuntu16.04，内存16GB，2.4GhzCPU运行Intel Core i5的机器上进行的。我们使用LIME进行局部解释。我们使用聚类大小为4的k均值对输入的种子数据进行聚类。
4.2 实验目标

  • 与现有工作相比较。
  • 算法特征有效性。
4.3 覆盖路径
我们做了一个实验来比较我们的全局搜索和基于随机数据的搜索的路径覆盖率。为了实现路径覆盖，我们学习了一个精度为85%-95%的决策树模型，对每个基准使用5倍的交叉验证，并将每个生成的测试输入映射到决策树模型的路径。结果显示，在所有基准测试中，SG的覆盖路径平均比随机数据高2.66倍。结果表明，在路径覆盖度量上，我们优于其他算法。因此，我们的算法将能够在模型的不同位置找到歧视性的输入。这一点非常重要，因为如果我们使用测试用例进行再培训，我们可以一次性去除模型的多个部分的偏差。
5. 结论
本文中，我们针对机器学习模型中的个体歧视问题，提出了一种测试用例生成算法。我们的该方法结合了符号计算的概念，系统地为任何程序生成测试输入，使用线性和可解释的模型逼近模型中的执行路径。我们的技术提供了一个额外的优势，因为它是自然界中的黑盒子。我们的搜索策略跨越了两种方法，即全局搜索和局部搜索。全局搜索为路径覆盖提供了便利，并有助于发现一组初始的歧视性输入。为了达到这个目的，我们使用种子数据和符号计算，同时考虑局部模型中存在的近似值，并聪明地使用从局部模型中获得的路径约束相关的置信度。此外，本地搜索的目的是寻找越来越多的歧视性投入。它从最初的一组可利用的歧视性路径开始，产生属于附近执行路径的其他输入，从而系统地进行地方解释，同时依靠对抗性的健壮性支持。我们的实验评估清楚地表明，我们的方法比所有现有的工具都要好。