Quantifying Sensitivity for Tree Ensembles: A symbolic and compositional approach
2026-05-13 • Artificial Intelligence
Artificial IntelligenceMachine Learning
AI summaryⓘ
The authors focus on understanding how sensitive decision tree ensembles (DTEs) are to small changes in their input features, which could cause wrong outputs. They create a way to measure this sensitivity by breaking down the input space into smaller parts and checking where changes matter. They use a special data structure called an algebraic decision diagram (ADD) to efficiently compute these sensitive regions with guaranteed accuracy. Their tool, XCount, runs faster and handles larger models better than previous methods. They tested it on various examples and showed it works well as DTE size grows.
Decision Tree EnsemblesModel VerificationSensitivity AnalysisAlgebraic Decision DiagramInput Space DiscretizationCertified Error BoundsModel CountingScalabilityClassificationCompositional Computation
Authors
S. Akshay, Chaitanya Garg, Ashutosh Gupta, Kuldeep S. Meel, Ajinkya Naik
Abstract
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.