stat.MLMar 12, 2026

Decomposing Observational Multiplicity in Decision Trees: Leaf and Structural Regret

Authors: Mustafa Cavus

Organizations: Eskisehir Technical University, Department of Statistics, Turkiye 26555

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Many machine learning tasks admit multiple models that perform almost equally well, a phenomenon known as predictive multiplicity. A fundamental source of this multiplicity is observational multiplicity, which arises from the stochastic nature of label collection: observed training labels represent only a single realization of the underlying ground-truth probabilities. While theoretical frameworks for observational multiplicity have been established for logistic regression, their implications for non-smooth, partition-based models like decision trees remain underexplored. In this paper, we introduce two complementary notions of observational multiplicity for decision tree classifiers: leaf regret and structural regret. Leaf regret quantifies the intrinsic variability of predictions within a fixed leaf due to finite-sample noise, while structural regret captures variability induced by the instability of the learned tree structure itself. We provide a formal decomposition of observational multiplicity into these two components and establish statistical guarantees. Our experimental evaluation across diverse credit risk scoring datasets confirms the near-perfect alignment between our theoretical decomposition and the empirically observed variance. Notably, we find that structural regret is the primary driver of observational multiplicity, accounting for over 15 times the variability of leaf regret in some datasets. Furthermore, we demonstrate that utilizing these regret measures as an abstention mechanism in selective prediction can effectively identify arbitrary regions and improve model safety, elevating recall from 92% to 100% on the most stable sub-populations. These results establish a rigorous framework for quantifying observational multiplicity, aligning with recent advances in algorithmic safety and interpretability.

Figures & tables

Figure 1: Theorized versus actual regret in decision trees across three datasets. The x-axis represents the sum of expected leaf regret and structural regret, while the y-axis shows the simulated true variance.
Figure 2: The impact of minimum leaf size ( nLn_{L} ) on predictive stability and model performance. The dual-axis plot illustrates the trade-off between Leaf Regret and Logistic Loss. These empirical results confirm that increasing partition size effectively mitigates observational multiplicity, as predicted in Lemma 2, while the increase in Logistic Loss reflects an empirical underfitting trade-off.
DatasetLeaf RegretStructural RegretRatio
taiwan_credit0.0000960.00147315.34
hmeq0.0015110.0105216.96
bank_marketing0.0001200.00152012.67
Table 1: Mean Leaf and Structural Regret across benchmark datasets.
Figure 3: Selective Prediction: Recall vs. Coverage across six datasets. The x-axis is reversed, moving from full dataset utilization as 100% to selective prediction on the most stable individuals. Curves represent ranking strategies based on Leaf Regret, Structural Regret, and Total Regret.
More in this topic

Statistical Learning Theory

Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.

See all 578 papers

Explore similar work

CardsList
Jul 30, 2025

Observational Multiplicity

Many prediction tasks can admit multiple models that can perform almost equally well. This phenomenon can undermine interpretability and safety when competing models assign conflicting predictions to individuals. In this work, we study how arbitrariness can arise in probabilistic classification tasks as a result of an effect that we call observational multiplicity. We discuss how this effect arises in a broad class of practical applications where we learn a classifier to predict probabilities pi∈[0,1]p_i \in [0,1] but are given a dataset of observations yi∈{0,1}y_i \in \{0,1\}. We propose to evaluate the arbitrariness of individual probability predictions through the lens of regret. We introduce a measure of regret for probabilistic classification tasks, which measures how the predictions of a model could change as a result of different training labels. We present a general-purpose method to estimate the regret in a probabilistic classification task. We use our measure to show that regret is often higher for certain groups in the dataset and discuss potential applications of regret. We demonstrate how estimating regret can be used to promote safety in real-world applications by abstention and data collection.

Erin George, Deanna Needell, Berk Ustun

Department of Mathematics University of California, San Diego La Jolla, CA 92093, USA · Department of Mathematics University of California, Los Angeles Los Angeles, CA 90095, USA · Department of Computer Science & Halıcıoğlu Data Science Institute University of California, San Diego La Jolla, CA 92093, USA

Binary ClassificationClassification
AskPDF
Mar 12, 2026

Mitigating the Multiplicity Burden: The Role of Calibration in Reducing Predictive Multiplicity of Classifiers

As machine learning models are increasingly deployed in high-stakes environments, ensuring both probabilistic reliability and prediction stability has become critical. This paper examines the interplay between classification calibration and predictive multiplicity - the phenomenon in which multiple near-optimal models within the Rashomon set yield conflicting credit outcomes for the same applicant. Using nine diverse credit risk benchmark datasets, we investigate whether predictive multiplicity concentrates in regions of low predictive confidence and how post-hoc calibration can mitigate algorithmic arbitrariness. Our empirical analysis reveals that minority class observations bear a disproportionate multiplicity burden, as confirmed by significant disparities in predictive multiplicity and prediction confidence. Furthermore, our empirical comparisons indicate that applying post-hoc calibration methods - specifically Platt Scaling, Isotonic Regression, and Temperature Scaling - is associated with lower obscurity across the Rashomon set. Among the tested techniques, Platt Scaling and Isotonic Regression provide the most robust reduction in predictive multiplicity. These findings suggest that calibration can function as a consensus-enforcing layer and may support procedural fairness by mitigating predictive multiplicity.

Mustafa Cavus

Eskisehir Technical University, Department of Statistics, 26555 Eskisehir, Turkiye

Post-Hoc CalibrationAlgorithmic Fairness
AskPDF
Jun 1, 2026

Model Multiplicity and Predictive Arbitrariness in Recidivism Risk Assessment

Prediction tasks over individual futures, which are inherently noisy, often admit multiple similarly accurate models. When these models produce different predictions for the same individual, they raise concerns of arbitrariness in decision-making. How severe can this arbitrariness be, in theory and in practice? How can it be resolved to support high-stakes risk assessment? We address these questions through a study of a machine learning-based decision support system for recidivism risk assessment that has been in use for over 15 years. By translating complex legal rules into an algorithm for labeling post release outcomes (recidivist or non-recidivist), we first construct a dataset of thousands of inmate releases. Using this dataset, we learn interpretable models that improve predictive performance, reduce error-rate disparities between groups, and ensure that rehabilitative progress lowers risk scores. Next, we study predictive multiplicity, by first deriving a tight lower bound on the expected predictive agreement of any finite set of models over a dataset, and then by evaluating the extent to which structural diversity (e.g., different model coefficients) within this set translates to predictive multiplicity (i.e., different predictions for the same individual). Our experiments indicate that the existence of many similarly accurate models with comparable error-rate disparities does not necessarily translate into severe predictive multiplicity. Empirically, similarly performant models can exhibit substantially higher predictive agreement than worst-case theoretical guarantees suggest. We find that a simple policy that assigns each inmate the lowest risk among these models is effective for addressing predictive arbitrariness.

Ashwin Singh, Carlos Castillo

TU Wien, Vienna, Austria · ICREA and Universitat Pompeu Fabra, Barcelona, Spain

Algorithmic Fairness
AskPDF