Quantitative Verification of Fairness in Tree Ensembles

• URL: http://arxiv.org/abs/2512.16386v1
• Date: Thu, 18 Dec 2025 10:31:15 GMT
• Title: Quantitative Verification of Fairness in Tree Ensembles
• Authors: Zhenjiang Zhao, Takahisa Toda, Takashi Kitamura,
• Abstract summary: This work focuses on quantitative verification of fairness in tree ensembles.<n>Unlike traditional verification approaches that merely return a single counterexample when the fairness is violated, quantitative verification estimates the ratio of all counterexamples.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work focuses on quantitative verification of fairness in tree ensembles. Unlike traditional verification approaches that merely return a single counterexample when the fairness is violated, quantitative verification estimates the ratio of all counterexamples and characterizes the regions where they occur, which is important information for diagnosing and mitigating bias. To date, quantitative verification has been explored almost exclusively for deep neural networks (DNNs). Representative methods, such as DeepGemini and FairQuant, all build on the core idea of Counterexample-Guided Abstraction Refinement, a generic framework that could be adapted to other model classes. We extended the framework into a model-agnostic form, but discovered two limitations: (i) it can provide only lower bounds, and (ii) its performance scales poorly. Exploiting the discrete structure of tree ensembles, our work proposes an efficient quantification technique that delivers any-time upper and lower bounds. Experiments on five widely used datasets demonstrate its effectiveness and efficiency. When applied to fairness testing, our quantification method significantly outperforms state-of-the-art testing techniques.

Related papers

• Greedy Is Enough: Sparse Action Discovery in Agentic LLMs [11.62669179647184]
  empirical evidence suggests that only a small subset of actions meaningfully influences performance in a given deployment.<n>Motivated by this observation, we study a contextual linear reward model in which action is governed by a structured sparsity assumption.<n>Our results identify sparse action discovery as a fundamental principle underlying large-action decision-making.
  arXiv  Detail & Related papers  (2026-01-13T07:15:32Z)
• Discrete Markov Bridge [93.64996843697278]
  We propose a novel framework specifically designed for discrete representation learning, called Discrete Markov Bridge.<n>Our approach is built upon two key components: Matrix Learning and Score Learning.
  arXiv  Detail & Related papers  (2025-05-26T09:32:12Z)
• Can We Validate Counterfactual Estimations in the Presence of General Network Interference? [13.49152464081862]
  We introduce a framework that facilitates the use of machine learning tools for both estimation and validation in causal inference.<n>New distribution-preserving network bootstrap generates statistically-valid subpopulations from a single experiment's data.<n>Counterfactual cross-validation procedure adapts the principles of model validation to the unique constraints of causal settings.
  arXiv  Detail & Related papers  (2025-02-03T06:51:04Z)
• SINDER: Repairing the Singular Defects of DINOv2 [61.98878352956125]
  Vision Transformer models trained on large-scale datasets often exhibit artifacts in the patch token they extract. We propose a novel fine-tuning smooth regularization that rectifies structural deficiencies using only a small dataset.
  arXiv  Detail & Related papers  (2024-07-23T20:34:23Z)
• Certified $\ell_2$ Attribution Robustness via Uniformly Smoothed Attributions [20.487079380753876]
  We propose a uniform smoothing technique that augments the vanilla attributions by noises uniformly sampled from a certain space. It is proved that, for all perturbations within the attack region, the cosine similarity between uniformly smoothed attribution of perturbed sample and the unperturbed sample is guaranteed to be lower bounded.
  arXiv  Detail & Related papers  (2024-05-10T09:56:02Z)
• Rethinking Semi-Supervised Medical Image Segmentation: A Variance-Reduction Perspective [51.70661197256033]
  We propose ARCO, a semi-supervised contrastive learning framework with stratified group theory for medical image segmentation. We first propose building ARCO through the concept of variance-reduced estimation and show that certain variance-reduction techniques are particularly beneficial in pixel/voxel-level segmentation tasks. We experimentally validate our approaches on eight benchmarks, i.e., five 2D/3D medical and three semantic segmentation datasets, with different label settings.
  arXiv  Detail & Related papers  (2023-02-03T13:50:25Z)
• Toward Certified Robustness Against Real-World Distribution Shifts [65.66374339500025]
  We train a generative model to learn perturbations from data and define specifications with respect to the output of the learned model. A unique challenge arising from this setting is that existing verifiers cannot tightly approximate sigmoid activations. We propose a general meta-algorithm for handling sigmoid activations which leverages classical notions of counter-example-guided abstraction refinement.
  arXiv  Detail & Related papers  (2022-06-08T04:09:13Z)
• Deconfounding Scores: Feature Representations for Causal Effect Estimation with Weak Overlap [140.98628848491146]
  We introduce deconfounding scores, which induce better overlap without biasing the target of estimation. We show that deconfounding scores satisfy a zero-covariance condition that is identifiable in observed data. In particular, we show that this technique could be an attractive alternative to standard regularizations.
  arXiv  Detail & Related papers  (2021-04-12T18:50:11Z)
• Incremental Verification of Fixed-Point Implementations of Neural Networks [0.19573380763700707]
  We develop and evaluate a novel symbolic verification framework using incremental bounded model checking (BMC), satisfiability modulo theories (SMT), and invariant inference. Our approach was able to verify and produce examples for 85.8% of 21 test cases considering different input images, and 100% of the properties related to covering methods.
  arXiv  Detail & Related papers  (2020-12-21T10:03:44Z)
• Lower bounds in multiple testing: A framework based on derandomized proxies [107.69746750639584]
  This paper introduces an analysis strategy based on derandomization, illustrated by applications to various concrete models. We provide numerical simulations of some of these lower bounds, and show a close relation to the actual performance of the Benjamini-Hochberg (BH) algorithm.
  arXiv  Detail & Related papers  (2020-05-07T19:59:51Z)
• Branch and Bound for Piecewise Linear Neural Network Verification [46.49816596173425]
  We propose a family of algorithms based on Branch-and-Bound (BaB)<n>We identify new methods that combine the strengths of multiple existing approaches.<n>We introduce an effective branching strategy on ReLU non-linearities.
  arXiv  Detail & Related papers  (2019-09-14T12:44:35Z)

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.