机器学习模型的黑盒公平性测试( 三 ) _机器学习

程序测试中的符号执行存在路径爆炸问题，尤其是在深度优先搜索方式下。它可以一直探索程序树深度的路径，而不探索程序其他部分的路径。研究者们已经探索出各种技术来解决这个问题——应用需求驱动或定向技术，向着程序中的某个特定位置生成测试用例，以及组合技术，试图分别分析各种功能模块，然后再将它们组合起来，在整个程序中生成更长的路径。所有这些技术都利用了被测程序的结构。

最大限度地提高歧视检测效率检查个体歧视。首先，让我们考虑一下检查个体歧视的情况，如算法 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 算法在两个搜索阶段运行--全局和局部。全局阶段考虑测试用例数量的限制，并通过对输入空间的随机抽样来生成测试用例。在所有这些生成的测试用例中，有少数测试用例具有鉴别性。然后，局部阶段开始将全局搜索阶段确定的每个判别性输入作为输入，并对其进行扰动，以进一步生成更多的测试用例。这个阶段就像之前的全局搜索一样，考虑了对生成的测试用例数量的限制。他们应用了三种不同类型的扰动，导致算法的三种不同变化。