Quantifying Sensitivity for Tree Ensembles: A symbolic and compositional approach

• URL: http://arxiv.org/abs/2605.13830v1
• Date: Wed, 13 May 2026 17:52:19 GMT
• Title: Quantifying Sensitivity for Tree Ensembles: A symbolic and compositional approach
• Abstract summary: Decision tree ensembles (DTE) are a popular model for a wide range of AI classification tasks, used in multiple safety critical domains.<n>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.<n>We propose a novel algorithmic technique that can perform this efficiently, within a certified error and confidence bound.
• Score: 25.226048852824064
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• An Enhanced Projection Pursuit Tree Classifier with Visual Methods for Assessing Algorithmic Improvements [0.3610948254980783]
  We develop visual diagnostic approaches to verify that the enhancements perform as intended.<n>An interactive web application enables users to explore the behavior of both the original and enhanced classifiers under controlled scenarios.
  arXiv  Detail & Related papers  (2026-02-24T17:27:17Z)
• Variational Sparse Paired Autoencoders (vsPAIR) for Inverse Problems and Uncertainty Quantification [0.0]
  Inverse problems arise when one seeks to reconstruct hidden, underlying quantities from noisy measurements.<n>We propose the Variational Sparse Paired Autoencoder (vsPAIR) to provide fast inference alongside uncertainty estimates.
  arXiv  Detail & Related papers  (2026-02-03T00:46:29Z)
• Towards Size-invariant Salient Object Detection: A Generic Evaluation and Optimization Approach [118.75896764188424]
  We present a novel perspective to expose the inherent size sensitivity of existing widely used Salient Object Detection metrics.<n>To address this challenge, a generic Size-Invariant Evaluation (SIEva) framework is proposed.<n>We further develop a dedicated optimization framework (SIOpt), which adheres to the size-invariant principle and significantly enhances the detection of salient objects across a broad range of sizes.
  arXiv  Detail & Related papers  (2025-09-19T04:12:14Z)
• Enhancing point cloud analysis via neighbor aggregation correction based on cross-stage structure correlation [22.48120946682699]
  Point cloud analysis is a cornerstone of many downstream tasks, among which aggregating local structures is the basis for understanding point cloud data.<n>We propose the Point Distribution Set Abstraction module (PDSA) that utilizes the correlation in the high-dimensional space to correct the feature distribution during aggregation.<n>PDSA distinguishes the point correlation based on a lightweight cross-stage structural descriptor, and enhances structural homogeneity.
  arXiv  Detail & Related papers  (2025-06-18T06:08:17Z)
• SMAB: MAB based word Sensitivity Estimation Framework and its Applications in Adversarial Text Generation [10.111657705438654]
  We introduce a Sensitivity-based Multi-Armed Bandit framework (SMAB) for calculating word-level local (sentence-level) and global (aggregated) sensitivities.<n>We show that our algorithm indeed captures intuitively high and low-sensitive words.<n>We also show that sensitivity can serve as a proxy for accuracy in the absence of gold data.
  arXiv  Detail & Related papers  (2025-02-10T22:46:57Z)
• Assessing Systematic Weaknesses of DNNs using Counterfactuals [3.5849841840695835]
  It is non-trivial to attribute the reason for such observed low performances to the specific semantic features that describe the subset. Inspired by counterfactual explanations, we propose an effective and computationally cheap algorithm to validate the semantic attribution of existing subsets.
  arXiv  Detail & Related papers  (2023-08-03T08:41:39Z)
• Analyzing the Performance of Deep Encoder-Decoder Networks as Surrogates for a Diffusion Equation [0.0]
  We study the use of encoder-decoder convolutional neural network (CNN) as surrogates for steady-state diffusion solvers. Our results indicate that increasing the size of the training set has a substantial effect on reducing performance fluctuations and overall error.
  arXiv  Detail & Related papers  (2023-02-07T22:53:19Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  We improve the theoretical and empirical performance of neural-network(NN)-based active learning algorithms for the non-parametric streaming setting. We introduce two regret metrics by minimizing the population loss that are more suitable in active learning than the one used in state-of-the-art (SOTA) related work.
  arXiv  Detail & Related papers  (2022-10-02T05:03:38Z)
• Task-Oriented Sensing, Computation, and Communication Integration for Multi-Device Edge AI [108.08079323459822]
  This paper studies a new multi-intelligent edge artificial-latency (AI) system, which jointly exploits the AI model split inference and integrated sensing and communication (ISAC) We measure the inference accuracy by adopting an approximate but tractable metric, namely discriminant gain.
  arXiv  Detail & Related papers  (2022-07-03T06:57:07Z)
• High Dimensional Level Set Estimation with Bayesian Neural Network [58.684954492439424]
  This paper proposes novel methods to solve the high dimensional Level Set Estimation problems using Bayesian Neural Networks. For each problem, we derive the corresponding theoretic information based acquisition function to sample the data points. Numerical experiments on both synthetic and real-world datasets show that our proposed method can achieve better results compared to existing state-of-the-art approaches.
  arXiv  Detail & Related papers  (2020-12-17T23:21:53Z)
• AP-Loss for Accurate One-Stage Object Detection [49.13608882885456]
  One-stage object detectors are trained by optimizing classification-loss and localization-loss simultaneously. The former suffers much from extreme foreground-background imbalance due to the large number of anchors. This paper proposes a novel framework to replace the classification task in one-stage detectors with a ranking task.
  arXiv  Detail & Related papers  (2020-08-17T13:22:01Z)
• Discovering Representations for Black-box Optimization [73.59962178534361]
  We show that black-box optimization encodings can be automatically learned, rather than hand designed. We show that learned representations make it possible to solve high-dimensional problems with orders of magnitude fewer evaluations than the standard MAP-Elites.
  arXiv  Detail & Related papers  (2020-03-09T20:06:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.