提出量化决策树集成敏感性的新方法，可高效验证模型鲁棒性。
Quantifying Sensitivity for Tree Ensembles: A symbolic and compositional approach
- 用代数决策图编码问题，分治求解提升计算效率
- 在多组基准测试中速度比现有方法快数倍，支持大规模模型
- 适合安全关键领域模型的可靠性验证，如医疗、自动驾驶
决策树集成（DTE）是广泛应用于各类AI分类任务的模型，尤其在多个安全关键领域中备受关注，因此对这些模型进行性质验证一直是过去十年的研究热点。其中敏感性验证问题尤为关键：给定一个DTE，判断输入特征的微小变化是否会导致分类错误。本文提出一种针对DTE的定量敏感性度量方法，通过离散化输入空间并枚举易受敏感性影响的区域来实现。我们设计了一种新型算法，能够在保证误差和置信度的前提下高效完成计算。该方法基于将问题编码为代数决策图（ADD），并将其分解为可高效求解的子问题，实现组合式与可扩展的计算。我们在不同规模的基准上评估了该方法性能，涵盖树的数量与深度变化，与同类模型计数器进行了对比。实验结果表明，工具XCount相比其他方法显著提速，并能良好适应集成规模的增长。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。