Test your Machine Learning Algorithm with Metamorphic Testing

• 前言
• The oracle problem
• Metamorphic testing
• Metamorphic testing on machine learning classifiers
• Conclusion
• 好文推荐
• 原文链接
• 参考文献

前言

测试机器学习和人工智能算法很困难。 事实上，一般来说，测试科学软件是很困难的，并且已经有一些关于这个更普遍主题的文献。 正如 Carver et al (2017)【1】 的介绍中所说。

科学软件的开发与更传统的商业信息系统的开发有很大不同，许多软件工程最佳实践和工具都从中汲取了灵感。 这些差异出现在软件生命周期的各个阶段……

这些差异出现在软件生命周期的以下阶段：需求、设计、编码、验证和验证以及部署。 特别是，根据 Carver 等人的说法，人们在验证和验证科学软件时通常面临的困难是：

• 在探索新的科学或工程领域和算法时，结果通常是未知的。
• 流行的软件工程工具通常不适用于计算科学和工程中使用的架构

事实上，机器学习和人工智能算法往往是数据科学家和研究人员探索的结果。 当生成的算法随后由工程师实施时，由于两个角色之间工作文化的差异，软件质量保证中的一些非常重要的实践通常难以实施。

The oracle problem

其中之一是oracle的问题，正如 Weyuker (1982)[2] 中广泛讨论的那样。在软件测试中，oracle 是指一种可以告诉您程序是否正常工作的机制。对于最简单的情况，oracle 可以直接将程序的输出与正确答案进行比较。更复杂的oracle可能涉及运行另一个程序来确定目标程序的输出是否正确。

对于机器学习和 AI 算法，问题在于通常没有没有人工干预的oracle。以图像识别为例。解决图像识别问题的常用方法是通过监督机器学习。这通常首先策划一个正确标记的图像数据集以进行训练和验证，这本身就是通过人工干预为开发中的软件模型引入oracle的一种方式。这意味着对模型进行的测试范围将受到人类努力的限制，扩展测试用例，例如通过在线测试显着增加抽样规模和品种，将是一个问题。

已经提出了几种缓解oracle的问题的方法，包括使用pseudo-oracle （伪oracle）和变形测试（metamorphic testing），我们将在本文后面讨论。

pseudo-oracle，由 Davis 和 Weyuker (1981)[3] 提出，意味着我们可以有多个实现来解决相同的问题，相互验证。 比较所有实现的输出，如果其中之一不同，则可能表明该算法存在一些错误。 例如，在机器学习中，过滤对抗样本的方法之一是比较模型的输出有无特征压缩。 这是伪orcale在线测试监督机器学习模型的应用程序。

下面我们将讨论由 Chen 等人 (1998)[4] 提出的变形测试。 我们将首先介绍变形测试作为软件测试中的通用工具包的概念，然后解释一些关于将变形测试应用于机器学习软件的研究。

Metamorphic testing

变形测试是一种缓解预言机问题的软件测试方法。这个想法很简单：即使我们不知道单个输入的正确输出，我们仍然可能知道多个输入的输出之间的关系，特别是如果输入本身是相关的。我们可以在软件中查看这些关系，称为变形关系。如果它们不成立，则肯定表明该软件存在某些缺陷。

自从近 20 年前首次发表以来，变形测试已经显示出许多有希望的结果，并在 GCC 和 LLVM 等流行软件中检测到许多缺陷[5]。这些成功案例收集在 Chen 等人 (2017)[6] 的评论文章中。

Chen et al (1998) 给出的一个例子是测试给定路径是否是无向加权图中的最短路径。这是软件测试中的一个典型案例，当图很复杂时，求助于预言机的成本会很高。如果 (x, v1, …, vN, y) 是建议的 x 和 y 之间长度为 p 的最短路径，Chen 等人建议对该算法进行一些后续测试，其中包括：

• 找出 y 和 x 之间的最短路径（反向），并验证长度也是 p。
• 找出 x 和 vK 之间以及 vK 和 y 之间的最短路径。 对于介于 1 和 N 之间的任何 K，验证两条路径的长度总和也是 p。

正式地说，假设 f 是我们正在测试的软件，我们有一个输入 x 和输出 f(x)。 我们没有 f(x) 的预言机，因此验证这个单一的测试用例会很困难。 然而，基于变形关系的已知变换 T 可以应用于 x 以生成后续测试用例 T(x)。 我们可以计算出 f(T(x))，然后通过使用变形关系从已知的 f(x) 构造一个预言机 T’(f(x)) 来验证它。 在上面最短路径问题的例子中，已知的结果长度 p 成为了两类后续测试用例的预言机。

Metamorphic testing on machine learning classifiers

Xie et al (2011)[7] 提出将变形测试应用于机器学习分类器。 他们在 Weka 3.5.7 版上进行了测试，以 k-最近邻 (kNN) 和朴素贝叶斯分类器 (NBC) 的实现为例。 他们在 kNN 实现中发现了一些意想不到的假设，在 NBC 的情况下，发现了一些错误。

他们还将交叉验证（数据科学中的常见做法）与使用突变分析的变形测试的性能进行了比较。 换句话说，他们故意改变算法的实现来注入错误，然后使用交叉验证和变形测试来查看是否检测到错误。 事实证明，有一些常见的编程错误很难通过交叉验证检测到，但可以通过变形测试检测到。

Xie等人使用的变形关系是Murphy等人（2008）[8]提出的关系的一个子集，包括：

• MR-0: Consistence with affine transformation
• MR-1.1: Permutation of class labels
• MR-1.2: Permutation of the attribute
• MR-2.1: Addition of uninformative attributes
• MR-2.2: Addition of informative attributes
• MR-3.1: Consistence with re-prediction
• MR-3.2: Additional training sample
• MR-4.1: Addition of classes by duplicating samples
• MR-4.2: Addition of classes by re-labeling samples
• MR-5.1: Removal of classes
• MR-5.2: Removal of samples
  这些是程序输出之间的直观关系。

Conclusion

关于将变形测试应用于最近开发的机器学习和人工智能算法，尤其是基于神经网络的深度学习模型的报道并不多。 但是，我们相信这是验证机器学习软件的一种很有前途的方法。 配备了更多领域特定的变形关系，变形测试提供了大量的测试样本来检查实现。 除了针对策划的数据集进行交叉验证之外，这可能是测试软件的好方法。

好文推荐

Compiler Validation via Equivalence Modulo Inputs

原文链接

参考文献

1. J. Carver, N. P. C. Hong, and G. K. Thiruvathukal, Eds., Software engineering for science. Boca Raton: Taylor & Francis, CRC Press, 2017.
2. E. J. Weyuker, “On testing non-testable programs,” The Computer Journal, vol. 25, no. 4, pp. 465–470, 1982. ↩
3. M. D. Davis and E. J. Weyuker, “Pseudo-oracles for Non-testable Programs,” in Proceedings of the ACM ’81 Conference, New York, NY, USA, 1981, pp. 254–257. ↩
4. T. Y. Chen, S. C. Cheung, and S. M. Yiu, “Metamorphic testing: a new approach for generating next test cases,” Technical Report HKUST-CS98-01, Department of Computer Science, Hong Kong University of Science and Technology, Hong Kong, 1998. ↩
5. V. Le, M. Afshari, and Z. Su, “Compiler Validation via Equivalence Modulo Inputs,” in Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, New York, NY, USA, 2014, pp. 216–226. ↩
6. T. Y. Chen et al., “Metamorphic Testing: A Review of Challenges and Opportunities,” 2017. ↩ X. Xie, J. W. K. Ho, C. Murphy, G. Kaiser, B. Xu, and T. Y. Chen,
7. “Testing and validating machine learning classifiers by metamorphic testing,” Journal of Systems and Software, vol. 84, no. 4, pp. 544–558, Apr.2011. ↩
8. C. Murphy, G. E. Kaiser, L. Hu, and L. Wu, “Properties of Machine Learning Applications for Use in Metamorphic Testing,” in SEKE, 2008, vol. 8, pp. 867–872. ↩