cs.LGAug 9, 2026

Backward Compatibility in Tree-Based Explanations and Enhanced CART Algorithm

Authors: Hirofumi Suzuki

Organizations: Fujitsu Limited Kawasaki, Kanagawa, Japan

Abstract

In the operation of machine learning models, model update is a fundamental process that requires careful consideration of its impact on downstream decision-making. Particularly when operating explainable models, changes in explanations resulting from model updates can lead to detrimental outcomes for users. Decision trees, due to their high transparency, are frequently employed in risk-sensitive decision-making and serve as a prominent example in which the aforementioned issue is evident. However, existing research addressing similar issues has focused on explanations based on feature contributions, and thus cannot handle explanations derived from tree structures. Therefore, this paper proposes the Backward Compatibility Loss in Tree-based eXplanations (BCLTX), a loss metric that suppresses changes in decision tree explanations before and after updates. Furthermore, we design CART with Backward Compatibility in Tree-based eXplanations (CART-BCTX), a lightweight algorithm that improves upon CART for the decision tree update problem under BCLTX. Experimental results using 10 real-world datasets, including both classification and regression tasks, show that CART-BCTX achieves favorable trade-offs between prediction performances and BCLTX values, with comparable computation times to CART, regardless of the task.

Explore similar work

CardsList
Jul 2, 2026cs.AI

Algebraic Model Counting for Global Analysis of Optimal Decision Trees

Ensuring model reliability in Explainable AI requires a global assessment of the hypothesis space. We propose a formal framework for the exhaustive analysis of optimal and near-optimal decision trees, called Algebraic Decision Tree Counting (ADTC). Inspired by Algebraic Model Counting (AMC) in knowledge representation, ADTC reformulates diverse analytical tasks, such as optimization, counting, and sampling, into a unified sum-of-products computation over a semiring RR. While the hypothesis space of decision trees is doubly exponential with respect to the maximum depth ΔΔ, our dynamic programming algorithm achieves O∗(nO(Δ))O^*(n^{O(Δ)}) time complexity in the number of features nn, where O∗O^* suppresses polynomial factors. To handle complex constraints consisting of multiple tree metrics, we introduce model behavior tensors that aggregate semiring values via convolution products over a tensor semiring. This algebraic approach efficiently constructs a model profile that captures the global landscape and trade-offs between criteria such as accuracy, size, and fairness. We demonstrate the utility of our software, emtrees, on real-world datasets, illustrating how ADTC facilitates evidence-based model selection in sensitive domains.
Hiroki Arimura
Decision TreesModel SelectionCounting
AskPDF
Jul 28, 2026cs.AI

dtControl2+\varepsilon: Trading Optimality for Explainability in MDPs via Decision Trees

Over the past decade, decision trees have been used to represent controllers (a.k.a. policies) in an explainable way, with dtControl2 as a current state-of-the-art tool. However, for systems that are large or have many corner cases, even such representations tend to be too complex and not human-comprehensible. Unfortunately, reducing the size of the decision tree is not straightforward, as missing just a single crucial case might result in an incorrect controller. We tackle this issue in the setting of Markov decision processes, extending dtControl2 by "ε\varepsilon" functionality: Given an allowed imprecision ε≥0\varepsilon \geq 0, we construct a smaller decision tree, distilling the essence of the controller, while still guaranteeing its ε\varepsilon-optimality. This enables us to provide tunably simpler explanations, omitting a controllable amount of detail. Our tool constructs decision trees that are orders of magnitude smaller than the state of the art.
Tereza Kinská, Jan Křetínský, Tobias Meggendorfer +2
Decision TreesMarkov Decision ProcessesEfficient ControlExplainability
AskPDF
May 17, 2026cs.LG

Counterfactual Explanations Under Concept Drift

Counterfactual explanations (CFEs) provide actionable recourse, but most methods assume a static framework with fixed data and a trained classifier. This assumption breaks in evolving data environments, such as data streams, where online models are repeatedly updated under concept drift. We identify CFE maintenance in this setting as a previously overlooked problem: explanations that are valid when generated may silently become invalid as the model evolves, including robust CFEs, which are not designed for continuous drift. We propose a lightweight, model-agnostic update scheme that repairs existing CFEs using local sampling to estimate validity and plausibility directions while preserving proximity to the original instance. Experiments on synthetic drifting streams show that initially created CFEs rapidly lose validity, whereas maintained CFEs preserve validity and local plausibility at a lower cost than repeated regeneration.
Marcin Kostrzewa, Jerzy Stefanowski, Maciej Zięba
Counterfactual ExplanationState DriftExplanationsRetrainingPost-HocPhysical Plausibility
AskPDF