决策树集成 (DTE) 是广泛的 AI 分类任务, 的流行模型，用于多个安全关键领域,，因此验证这些模型的属性一直是过去十年的一个活跃的研究主题。其中一个验证问题是敏感性, 问题，它询问, 给定DTE, 特征子集的微小变化是否会导致输入的错误分类。在这项工作, 中，我们的重点是通过离散化模型的输入空间并枚举易受敏感性影响的区域，构建适合 DTE, 的敏感性, 定量概念。我们提出了一种新颖的算法技术，可以在经过认证的误差和置信区间内有效地执行此计算,。我们的方法基于将问题编码为代数决策图(ADD),，并进一步将其分解为可以有效解决的子问题，并使计算具有组合性和可扩展性。我们根据树的数量和深度, 的不同大小的基准来评估我们的技术的性能，并将其与相同问题编码的模型计数器的性能进行比较。实验结果表明，我们的工具 XCount 比其他方法实现了显着的加速，并且可以随着集成规模的增加而很好地扩展。
Decision tree ensembles (DTE) are a popular model for a wide range of AI classification tasks, used in multiple safety critical domains, and hence verifying properties on these models has been an active topic of study over the last decade. One such verification question is the problem of sensitivity, which asks, given a DTE, whether a small change in subset of features can lead to misclassification of the input. In this work, our focus is to build a quantitative notion of sensitivity, tailored to DTEs, by discretizing the input space of the model and enumerating the regions which are susceptible to sensitivity. We propose a novel algorithmic technique that can perform this computation efficiently, within a certified error and confidence bound. Our approach is based on encoding the problem as an algebraic decision diagram (ADD), and further splitting it into subproblems that can be solved efficiently and make the computation compositional and scalable. We evaluate the performance of our technique over benchmarks of varying size in terms of number of trees and depth, comparing it against the performance of model counters over the same problem encoding. Experimental results show that our tool XCount achieves significant speedup over other approaches and can scale well with the increasing sizes of the ensembles.
科目: 人工智能 (cs.AI); 机器学习 (cs.LG)
Subjects: Artificial Intelligence (cs.AI); Machine Learning (cs.LG)