1 Introduction↩︎

Explainable AI (XAI) [1] has placed a growing emphasis on decision trees [2] due to their inherent interpretability. However, the phenomenon of predictive multiplicity [3], [4], where multiple models achieve similar performance but offer different explanations, poses a significant challenge for model reliability. To address this, we propose Algebraic Decision Tree Counting (ADTC), a framework that performs a global assessment of the entire hypothesis space rather than identifying a single heuristic solution.

Our ADTC is inspired by algebraic model counting (AMC) proposed by De Raedt and Kimmig [5] in knowledge representation [6]. AMC is an instance of the algebraic computation paradigm (see, e.g., Aji and McEliece [7], Eiter and Kiesel [8], and Goral [9]) that generalizes logical counting by evaluating formulas over a semiring. Specifically, our framework aggregates behaviors of near-optimal prediction models based on a dataset and a constraint formula, whereas AMC aggregates weights of satisfying assignments for a given formula. In this context, near-optimal models (or good models) [4], [10]–[12] refer to those within the Rashomon set [1], [13], [14] that satisfy a predefined performance threshold relative to the empirical best model.

Conceptually, the framework ADTC executes an “enumerate-filter-aggregate” style query over the huge hypothesis space of decision trees, similar to analytic queries in relational databases [15]. While the number of syntactically distinct decision trees is \(n^{\Theta(2^\Delta)}\), our approach achieves a time complexity of \(O^*(n^{\Delta})\), which is polynomial in data size \(n\) but exponential in query size \(\Delta\), by employing a dynamic programming scheme based on tensor operations. Consequently, our framework avoids the double-exponential complexity of exhaustive enumeration through algebraic aggregation.

The primary contributions of this paper are summarized as follows:

• Algebraic framework for decision trees: In 2, we propose ADTC, a unified framework based on algebraic model counting [5], [8], to evaluate and aggregate decision trees over arbitrary commutative semirings. It provides a comprehensive perspective that generalizes previous studies on induction [10], [16], [17], enumeration[18], counting as well as sampling [14], [19], and Pareto optimization [11] of optimal decision trees, which have often been treated independently.

• Theoretical complexity guarantees: In 3, we develop a dynamic programming (DP) algorithm EMT using tensor operations (Algorithm 3) that achieves a running time of \(O^*(n^{O(\Delta)})\) (3). This complexity is polynomial in data size \(n\), although exponential in query size \(\Delta\), avoiding the double-exponential bottleneck of exhaustive enumeration. The key to this efficiency lies in aggregating information of multiple metrics, such as size and error of decision trees, into a semiring of model behavior tensors, that allow for efficient computation via DP over a factorized representation of the decision tree space. In 4, we extend EMT to nonlinear metrics [11] as well as model selection and sampling [9], [19].

• Transparent model profiling: In 5, we demonstrate that our framework enables global navigation of the rashomon set, facilitating transparent and rigorous analysis of trade-offs between multiple objectives, such as the accuracy and F1-score in Fig. 1, and assessment of preprocessing, such as the original and balanced accuracy in Fig. 2 (in 5). This profiling addresses diverse requirements in real-world machine learning deployments. Finally, we conduct empirical evaluations of our emtrees software [20], an implementation of the EMT algorithm in Secs. 3 and 4, on the standard benchmark UCI adult dataset to demonstrate its scalability and effectiveness in global analysis tasks for sensitive domains.

Overall, this proposed framework enables a global navigation of the Rashomon set, allowing ADTC to analyze the trade-offs between multiple objectives, such as accuracy and fairness. By providing a rigorous profile of all near-optimal models, our framework facilitates transparent and rigorous model selection for diverse requirements in real-world machine learning deployments.

1.1 Related work↩︎

The global analysis of decision tree spaces intersects with several research areas, including optimal decision tree construction, model counting, and the study of the Rashomon set.

Optimal decision tree construction. Recent advancements have introduced exact algorithms such as GOSDT [12] and DL8.5 [17]. While these methods excel at finding a single optimal tree [10], [16], they are not designed to characterize the entire landscape of near-optimal models. In contrast, our approach enables a comprehensive aggregation of these models through a unified algebraic framework.

The Rashomon set and predictive multiplicity. Previous work by Dong and Rudin [21] explored the Rashomon set [1] via sampling, while Xin et al. [14] utilized compressed representations. However, the latter requires exponential memory and is primarily limited to counting [14]. In contrast, our approach employs model behavior tensors computable in polynomial space (see 3). Within a unified semiring-based framework of ADTC, we provide an exact profile of model diversity that reveals the underlying predictive multiplicity and trade-offs, enabling various analytical tasks beyond simple counting.

Algebraic model counting. Our work bridges the gap between Algebraic Model Counting (AMC) [5] and the combinatorial space of decision trees by adapting the AMC paradigm to the recursive structure of trees. This allows for efficient sum-of-product computations [8], [9] over tensors, avoiding the double-exponential bottlenecks associated with naive enumeration.

2 Preliminaries↩︎

The following notation and terminology are used throughout this paper. For standard terminology not defined below, please consult [22] for machine learning, [23] for algorithms, [24] for logic, and [25] for algebraic computation.

2.1 Basic definitions↩︎

Numbers, sets, and vectors. Let \(\mathbb{R}\), \(\mathbb{Z}\), and \(\mathbb{N} = \{0, 1, \dots\}\) be the sets of all real numbers, integers, and natural numbers, respectively. For an integer \(n, i, j\in \mathbb{N}\) with \(i\le j\), we define \([n]=\{1, \dots, n\}\), and \([i..j] = \{\kern 0.00emi, i+1, \dots, j\kern 0.00em\}\subseteq \mathbb{N}\). For any sets \(A\) and \(B\), \(|A|\) denotes the cardinality of \(A\), \(2^A\) the power set of \(A\), and \(A^*\) the set of all finite sequences of elements from \(A\). The notation \(B^A\) denotes the set of all mappings from \(A\) to \(B\). For \(d \in \mathbb{N}\), we write \(d\)-vector \(\boldsymbol{x} = (x_j)_{j=1}^{d}\) as \((x_j)_d\). For \(d \in \mathbb{N}\) and a \(d\)-vector \({\boldsymbol{m}}= (m_1, \dots, m_d) \in \mathbb{N}^d\), let \(\mathbb{N}[{\boldsymbol{m}}]\) denote \([m_1] \times \cdots \times [m_d] \subseteq \mathbb{N}^d\).

Semirings and polynomials. A monoid \((M, \cdot, e)\) is a set M equipped with an associative binary operation \(\cdot\) and an identity \(e \in M\). It is commutative if \(a + b = b + a\) holds. A semiring is an algebraic structure \(\mathcal{R} = (R, +, \cdot, \mathbf{0}, \mathbf{1})\), where \(a\cdot b\) is written \(ab\), and

for all \(a,b,c \in R\). In this work, we mainly consider commutative semirings. For \(d \in \mathbb{N}\) and a semiring \(R\), we denote by \(R[(x_j)_d]\) the semiring of \(d\)-variate polynomials with coefficients in \(R\). Each polynomial in \(R[(x_j)_d]\) with indeterminates \(x = (x_j)_d\) is represented as $ p(x) = {} c{} x^{} = { ^d} c{} _{j=1}^d x_j^{v_j},None$ where \(c_{\boldsymbol{v}} \in R\). These structures are fundamental for algebraic model counting [5].

2.2 Prediction models and their behaviors↩︎

Decision trees. Let \(\mathcal{X}\) be a universe of data. We assume \(n\) Boolean features \(F = \{f_1\), \(\dots\), \(f_n\}\) and \(c\) categorical labels \(L = \{\kern 0.00emy_0, \dots, y_{c-1}\kern 0.00em\}\), where each Boolean feature is a mapping \(f: \mathcal{X} \to \{\kern 0.00em0,1\kern 0.00em\}\). A decision tree (a tree, for short) over alphabets \(\Sigma = (F, L)\) is an expression represented as a node-labeled binary tree. A tree \(t\) and its string notation are defined inductively as follows: \(t\) is either

A tree \(t\) induces a prediction function \(f_t: \mathcal{X} \to \mathcal{Y}\) that, given a data \(x \in \mathcal{X}\), returns a prediction label \(y = f_t(x) \in L\) via a standard root-to-leaf traversal. A sample is a set of data \(S = \{\kern 0.00emx_i\kern 0.00em\}_{i=1}^{m}\) in \(2^{\mathcal{X}}\). An input data is a pair \((S, y)\) of a sample \(S\) and a labeling function \(y: S \to L\).

Hypothesis spaces: We consider the hypothesis space \(\mathcal{M}_{\Delta}\) of all decision trees with depth at most \(\Delta \ge 0\) over a given alphabet \(\Sigma = (F, L)\) because complexity is primarily governed by depth [16]. The number of syntactically distinct Boolean trees in \(\mathcal{M}_{\Delta}\) is \(n^{\Theta(2^{\Delta})}\), which exhibits double-exponential growth. While \(\mathcal{M}_{\Delta}\) serves as our baseline, we can further restrict it by imposing \(\texttt{minsup} \ge 1\) (minimum support) and \(\texttt{nbins}\) (discretization bins), denoted as \(\mathcal{M}_{\Delta, \texttt{minsup}, \texttt{nbins}}\) for effective pruning.

2.3 Model behavior metrics↩︎

We will analyze the hypothesis space \(\mathcal{M}_{\Delta}\) of models by means of measuring functions, called model metrics (or metrics). Let \(\Delta \in \mathbb{N}\). In our global analysis of decision tree space \(\mathcal{M}_{\Delta}\), a smallest unit of analysis is a pair \((t, S)\) of a tree \(t\) and a sample \(S\), called a structure. The domain of structures is \(\mathcal{S}= {{{\mathcal{M}_{\Delta}}}\times 2^{\mathcal{X}}}\). Then, a model metrics (or metrics) is any mapping \(\sigma: \mathcal{S}\to \mathtt{dom}(\sigma)\) that assigns a value \(k = \sigma(t, S) \in \mathcal{S}\) to each model \(t \in \mathcal{M}_{\Delta}\), where \(\mathtt{dom}(\sigma)\) is any set. A metric \(\sigma\) is said to be primitive if it has an integer-valued range \(\mathtt{dom}(\sigma) = [0..m_\sigma]\), where \(m_\sigma \in \mathbb{N}\) is called the maximum range. The following are examples of primitive metrics used in this paper.

In 4.1, we will introduce primitive metrics related to contingency tables as well as complex nonlinear metrics.

To devise efficient algorithms for ADTC, we need to introduce the notion of decomposition of a metric, in a similar way to AMC [5], [9]. For any feature \(f \in F\), we define the split of a data set \(S\) by \(f\) to be the partition \(S = S_{f=1} \uplus S_{f=0}\) such that \(S_{f=i} = \{ x \in S \mid f(x) = i \}\) for each \(i \in \{0, 1\}\).

2.4 Constraint formulas and \(\phi\)-good models↩︎

In the global analysis of decision trees, it is standard practice to investigate a subspace of the hypothesis space consisting of high-quality models, or good models [1], [4], called the Rashomon set, such that \(size(t) \le s\) and \(err(t, S) \le e\). We generalize this notion below. Let \(\Delta, d \in \mathbb{N}\) be any integers. We assume a \(d\)-vector \({\boldsymbol{m}}\in \mathbb{N}^d\) and a structure domain \(\mathcal{S}= {{{\mathcal{M}_{\Delta}}}\times 2^{\mathcal{X}}}\). We assume a \(d\)-vector of primitive metrics \(\boldsymbol{\sigma}^{{}}= (\sigma_i)_d\) and the associated shape vector \({\boldsymbol{m}}= (m_i)_d \in \mathbb{N}^d\), where \(\sigma_i: \mathcal{S}\to [0..m_i]\) for each \(i \in [d]\).

We introduce the syntax of constraint formulas as follows. The vocabulary with metrics \(\boldsymbol{\sigma}^{{}}\) includes constants for numbers in \(\mathbb{N}\) and \(\mathbb{R}\), nullary function variables \((\sigma_i)_d\), binary operators \(+, \times, (\frac{\cdot}{\cdot})\), and a binary relation symbol \(\le\). Terms are rational expressions¹ constructed from all constants, operators, and function variables \(\underline{\boldsymbol{\sigma}^{{}}}\). An atomic formula is either \((f(\underline{\boldsymbol{\sigma}^{{}}})\le c)\) or \((f(\underline{\boldsymbol{\sigma}^{{}}})\le g(\underline{\boldsymbol{\sigma}^{{}}}))\) with rational expressions \(f,g\) and constants \(c\). Then, the set of constraint formulas consists of all formulas with free variables \(\underline{\boldsymbol{\sigma}^{{}}}\) constructed from atomic formulas \(\phi[\underline{\boldsymbol{\sigma}^{{}}}]\) using Boolean operations \(\neg, \lor, \land\). For example, the followings are constraint formulas with metrics, \[\begin{align} \phi_1 &= (\mathtt{size}\le 4) \land (\mathtt{error} \le 0.05\cdot N) \text{ with } acc \equiv (N_{1,1} + N_{0,0})/N, \\ \phi_2 &= (\mathtt{acc} \ge 0.9) \land (\mathtt{f1}\ge 0.76) \text{ with } \mathtt{f1} \equiv (2\cdot N_{1,1})/(2\cdot N_{1,1} + N_{0,0} + N_{1,0}), \end{align}\] where \(\phi_1\) states that \(t\) is accurate and succinct on \(S\), while \(\phi_2\) states that \(t\) has high scores in both accuracy and F1. Metrics \(acc, f1, \{\kern 0.00emN_{i,j}\kern 0.00em\}\) will be introduced in 4.1.

The semantics is defined as follows. We consider a pair \((t, S) \in S = {{{\mathcal{M}_{\Delta}}}\times 2^{\mathcal{X}}}\) as a structure over the vocabulary. Then, a \(d\)-metric vector \(\boldsymbol{\sigma}^{{}}= (\sigma_i)_d\) assigns to the structure \((t, S)\) a \(d\)-interger vector \(\boldsymbol{k} = (k_i)_d = \boldsymbol{\sigma}^{{}}(t, S) \in \mathbb{N}^d\), called the index of \(t\), where \(k_i = \sigma_i(t, S)\) for all \(i\). Given a formula \(\phi = \phi[\underline{\boldsymbol{\sigma}^{{}}}]\), we write \((t, S)\models \phi\), if \(\phi\) evaluates true under valuation \(\underline{\boldsymbol{\sigma}^{{}}} \mapsto \boldsymbol{\sigma}^{{}}(t, S) \in \mathbb{N}^d\) with the standard interpretation to logical connectives. Then, we say that a decision tree \(t \in \mathcal{M}_{\Delta}\) is a \(\phi\)-good model on \(S\) if \((t, S)\models \phi\). Note that the truth of \(\phi\) on the structure \((t, S)\) is solely determined by the vector \(\boldsymbol{k} = \boldsymbol{\sigma}^{{}}(t, S)\) in \(\mathbb{N}^d\). We define the hypothesis space of \(\phi\)-good models by $ {}(, S) = { t {}(t, S) }.None$

2.5 Our problem: algebraic decision tree counting↩︎

From now on, we define our problem, \({\textsf{ADTC}}\), the algebraic decision tree counting over a semiring \((R, +_R, \cdot_R, \mathbf{0}, \mathbf{1})\). Let \(\mathcal{S}= {{{\mathcal{M}_{\Delta}}}\times 2^{\mathcal{X}}}\) be the domain of structures.

Then, a rank-\(d\) query is a tuple \(Q = (\Delta, \alpha, \boldsymbol{\sigma}^{{}}, \phi[\boldsymbol{\sigma}^{{}}])\) consisting of

An input data \(D = (S, y)\) is a pair of a sample \(S\) and a label function \(y: S \to L\). We state our problem.

By varying a semiring \((R, +_R, \cdot_R)\) and a query \(Q\) as its components, the ADTC problem can naturally formulate a wide range of global analytics tasks as follows. Let \(\mathtt{one}(t, S) = \mathbf{1}\) be the aggregation function that always returns the constant \(\mathbf{1}\in R\).

We remark that the complexity of ADTC depends crucially on an underlying semiring \(R\). To be precise, we introduce the parameter \(t_R\) and \(s_R\) to be the worst-case time and space complexities for operations on \(\mathcal{R}\). We observe that \({\textsf{ADTC}}\) can be solved by a straightforward method according to Eq.@eq:eqn:adtc:main as follows: it first initializes a variable \(r = \mathbf{0}\in R\), then, scans all trees \(t\) in \(\mathcal{M}_{\Delta}\), where at each iteration, it evaluates \(\boldsymbol{\sigma}^{{}}(t, S)\), and adds the weight \(\alpha(t, S) \in R\) to \(r\) if \((t, S) \models \phi[\boldsymbol{\sigma}^{{}}]\) holds. However, since \(|\mathcal{M}_{\Delta}| = n^{\Theta(2^\Delta)}\), this method requires doubly exponential time in \(\Delta\).

3 Efficient Algorithm↩︎

This section presents a dynamic programming approach solving ADTC in \(O^*(n^{O(\Delta)} \cdot t_R)\) time and \(O^*(s_R)\) space over \(\mathcal{M}_\Delta\). We first formalize decomposability of metrics (Sec. 3.1), and then develop the EMT algorithm for unconstrained ADTC (Sec. 3.2). Reducing the tensor construction MT to this unconstrained setting (Sec. 3.3) yields our final algorithm for the general constrained ADTC problem (Sec. 3.4).

3.1 Assumptions on analytic queries↩︎

Let \((R, +_R, \cdot_R, \mathbf{0}, \mathbf{1})\) be a semiring and \(({\mathcal{A}}, \boldsymbol{\circ}, \mathbf{1})\) be a \(d\)-vector \(\{\kern 0.00em(A_i, \circ_i, 1_i)\kern 0.00em\}_d\) of monoids. Throughout, we assume any rank-\(d\) query \(Q = (\Delta, \alpha, \boldsymbol{\sigma}^{{}}, \phi[\boldsymbol{\sigma}^{{}}])\) satisfies two conditions:

1. The aggregation \(\alpha: \mathcal{S}\to R\) is decomposable via \(\cdot_R\), that is, \(\alpha = \mathtt{Hom}[\underline{\alpha}, \cdot_R]\).

2. The metrics \(\boldsymbol{\sigma}^{{}}: \mathcal{S}\to \mathbb{N}[{\boldsymbol{m}}]\) with shape \({\boldsymbol{m}}\in \mathbb{N}^d\) is decomposable via \(\boldsymbol{\circ}\), that is, \(\boldsymbol{\sigma}^{{}}= \mathtt{Hom}[\underline{\boldsymbol{\sigma}^{{}}}, \boldsymbol{\circ}]\).

When the underlying algebraic structures are clear, we simply write \(\alpha\) and \(\boldsymbol{\sigma}^{{}}\) to denote the decomposable schemas \((\alpha, R)\) and \((\boldsymbol{\sigma}^{{}}, {\mathcal{A}})\), respectively.

3.2 ADTC without constraints↩︎

First, we present our basic algorithm EMT for unconstrained queries of the form \(Q = (\Delta, \alpha)\), where metrics \(\boldsymbol{\sigma}^{{}}\) and constraint formula \(\phi[\boldsymbol{\sigma}^{{}}]\) are empty. Although such restricted queries seem useless in practice, they will turn out to be useful as an important building block of a general \({\textsf{ADTC}}\) algorithm of 3.3 and 3.4.

In 3, we present the pseudocode of EMT that implements the recurrence of Def. 4, where we assume that \(\alpha\) is homomorphic on data, i.e., $ (, S) = _{x S} (, {0.00emx})$ as it is true with most \(\alpha\) in this paper. In the top-level, given \(\Sigma = (F, L)\) and an input \(D = (S, y)\), the invocation of \({\textsf{EMT}}(\Delta, S, F)\) computes a semiring element \(v \in R\). By the distributivity of \(\cdot_R\) over \(+_R\), we can show the next lemma.

Now, we show the first theorem. Recall that \(O^*\) notation hides polynomial factors.

From 1, we see that the problem \({\textsf{ADTC}}\) is computable in polynomial time w.r.t. the size of input \(D\) when a query \(Q\) is regarded as constant.

3.3 ADTC over a semiring of model behavior tensors↩︎

Next, we present an efficient algorithm for the Model Behavior Tensor problem. Intuitively, a rank-\(d\) model behavior tensor (or model tensor, MT) is a \(d\)-way cross table of aggregation values via \(\alpha\) on \(\mathcal{M}_{\Delta}\) w.r.t. multiple metrics \(\boldsymbol{\sigma}^{{}}\) (see Fig. 4 (a)). An MT query means any rank-\(d\) query \(Q = (\Delta, \alpha, \boldsymbol{\sigma}^{{}})\) with the empty constraint \(\phi[\boldsymbol{\sigma}^{{}}]\).

Behavior of decision trees as tensors. Let \(\Delta, d \in \mathbb{N}\) be any integers, and let \((R, +_R, \cdot_R, \mathbf{0}, \mathbf{1})\) be any semiring. Let \(Q = (\Delta, \alpha, \boldsymbol{\sigma}^{{}}, \phi[\boldsymbol{\sigma}^{{}}])\) be any rank-\(d\) (analytic) query. Recall that \(\mathcal{S}= {{{\mathcal{M}_{\Delta}}}\times 2^{\mathcal{X}}}\) is the domain of structures. By the assumptions in 3.1, we assume without loss of generality that the following conditions hold:

• (1) The aggregation function \(\alpha: \mathcal{S}\to R\) has a decomposition scheme \((\alpha, R)\) such that \(\alpha = \mathtt{Hom}[\underline{\alpha}, \cdot_R]\) via operator \(\cdot_R\) using a submonoid \((R, \cdot_R, \mathbf{1})\) of \(R\).

• (2) The combination function \(\boldsymbol{\sigma}^{{}}= (\sigma_i)_d: \mathcal{S}\to \mathbb{N}[{\boldsymbol{m}}]\), a \(d\)-vector of metrics with a shape vector \({\boldsymbol{m}}= (m_i)_d \in \mathbb{N}^d\), has a decomposition scheme \((\boldsymbol{\sigma}^{{}}, {\mathcal{A}})\) such that \(\boldsymbol{\sigma}^{{}}= \mathtt{Hom}[\underline{\boldsymbol{\sigma}^{{}}}, \boldsymbol{\circ}]\) via operator \(\boldsymbol{\circ}\) using a \(d\)-vector of monoids \(({\mathcal{A}}, \boldsymbol{\circ}, \mathbf{1})\), which denotes \(\{\kern 0.00em (A_i, \circ_i, 1_i) \kern 0.00em\}_d\).

Under the above assumption, we define the behavior of each structure \(\tau = (t, S) \in \mathcal{S}\) to be the index-weight pair \((\boldsymbol{k}, v)\) computed by \(\boldsymbol{k} = \boldsymbol{\sigma}(t, S) \in \mathbb{N}[{\boldsymbol{m}}]\) and \(v = \alpha(t, S) \in R\). Recall that a tensor \(T\) in \(R^{\mathbb{N}[{\boldsymbol{m}}]}\) is just a function \(T: \mathbb{N}[{\boldsymbol{m}}] \to R\) that assigns an element \(T(\boldsymbol{k})\) in \(R\) to each index (a point) \(\boldsymbol{k}\) in the \(d\)-dim discrete space \(\mathbb{N}[{\boldsymbol{m}}]\subseteq \mathbb{N}^d\). Now, we state the second problem of this paper as follows.

A key to efficient algorithms for the problem is a set of operations over model behavior tensors, introduced as follows.

In this way, we obtain from any semiring \((R, +_R, \cdot_R, 0_R, 1_R)\) the algebraic structure \((R^{\mathbb{N}[{\boldsymbol{m}}]}, \oplus, \otimes, \mathbf{0}, \mathbf{1})\) over the collection \(R^{\mathbb{N}[{\boldsymbol{m}}]}\) of rank-\(d\) tensors from \(\mathbb{N}[{\boldsymbol{m}}]\) to \(R\).

Decision trees as polynomials. Any model tensor \(T \in R^{\mathbb{N}[{\boldsymbol{m}}]}\) maps to a multivariate truncated polynomial \(P(x) = \sum_{\boldsymbol{k} \in \mathbb{N}[{\boldsymbol{m}}]} T(\boldsymbol{k}) x^{\boldsymbol{k}}\) over \(R\), where \(x = (x_i)_d\) are indeterminates. This establishes a bijection between \(R^{\mathbb{N}[{\boldsymbol{m}}]}\) and the quotient semiring \(R[(x_i)_d] / \langle x^{m_j}\rangle_{j=1}^{d}\) bounding each degree to \(m_i - 1\).² Division in \(R\) is not required.

From Lemma 3, the next lemma follows.

Reduction from MT to Unconstrained ADTC. We present a reduction from the Model Behavior Tensor problem to the unconstrained ADTC problem over the tensor semiring \(R^{\mathbb{N}[{\boldsymbol{m}}]}\).

Unconstrained ADTC computes the \(\oplus\)-sum of \(\alpha_*(t, S)\) over \(t \in \mathcal{M}_{\Delta}\). Definitions 3 and 5 immediately yield 5.

3.4 Putting it together↩︎

Given the model behavior tensor \(T\), the solution to ADTC is obtained by filtering out entries that violate \(\phi[\boldsymbol{k}]\) and summing the weights \(\alpha(t, S)\) of the remaining entries. Thus, the following theorem follows from 2.

Finally, the cell size \(s_R\) and operation time \(t_R\) over \(R\) depend on the maximum entry size \(M\) in \(T\). In the worst case, \(M\) reaches \(O(2^\Delta)\) if all \(|\mathcal{M}_{\Delta}| = n^{\Theta(2^\Delta)}\) trees fall into a single cell, yielding \(s_R = \Theta(\log |\mathcal{M}_{\Delta}|) = \Theta(2^\Delta \log n)\). In practice, however, appropriate hyperparameters like depth \(\Delta\) and minsup effectively bound \(M\) (5).

4 Extensions↩︎

In this section, we introduce extensions to algorithm EMT in 3 that enable the use of complex, nonlinear metrics as well as selection and sampling of concrete models.

4.1 Extensions to contingency tables and nonlinear model metrics↩︎

Global analysis often involves complex nonlinear metrics [11]. To address this, we use rational metrics, functions defined by a fraction \(P(x)/Q(x)\) of multivariate polynomials over primitive metrics (2.4), Many statistical scores [26] can be expressed as rational metrics. Below, we introduce rational metrics definable in terms of 2-way and 3-way contingency tables [22]. Let indices \(i, j, k \in \{\kern 0.00em0, 1\kern 0.00em\}\) represent the true label \(y\), predicted label \(\hat{y} = f_t(x)\), and sensitive attribute \(z\) in a dataset \(S\), respectively. For a tree \(t\), the 2-way table entry \(N_{ij}(t; S)\) is defined as \(\sum_{x\in S} \mathbf{1}[(y(x)= i) \land (f_t(x) = j)]\). Entries \(N_{ijk}(t; S)\) of a 3-way table are defined analogously. Cell probabilities are then easily derived (e.g., true positives \(tp = N_{11}/|S|\)).

Using the contingency tables, we can formulate a variety of score functions [26], such as the F1-score [22] and Equalized odds (EOdd) [27] as follows:

1. F1-score: \(F1(t; S) = 2 N_{11}/(2 N_{11} + N_{01} + N_{10})\), and

2. Equalized odds: \(EOdd(t; S) = | ({N_{011}}/{N_{0*1}}) - ({N_{010}}/{N_{0*0}}) | + | ({N_{111}}/{N_{1*1}})\) \(-\) \(({N_{110}}/{N_{1*0}}) |\), where \(N_{i*k} = N_{i1k} + N_{i0k}\) denotes the marginal count for true label \(i\) and sensitive attribute \(k\).

As a practical optimization for ADTC, we minimize the tensor dimensionality by isolating and maintaining model-independent metrics outside a tensor \(T\). For instance, \(N_{i*k}\) for any \(i,k \in \{\kern 0.00em0,1,*\kern 0.00em\}\) is a model-independent metric because its prediction label index \(j\) is fixed to \(*\). The counts of all, positive, and sensitive examples, specifically \(N_{***} = |S|\), \(N_{1**} = N_{y=1}\), and \(N_{**1} = N_{z=1}\), fall into this class. This leads to significant savings in both memory and construction time.

4.2 Selection and sampling of supporting models↩︎

By modifying the algorithm EMT, we can efficiently implement the selection and random sampling of decision trees that support the value of ADTC(R) in a model behavior tensor \(T\). For this purpose, we use the technique of a semiring extension for selection and sampling, recently proposed by Goral et al. [9] (see also [19] for a similar technique). To do this, we construct the product semiring \(\mathbb{N}\times\mathbb{T}\) of the count semiring \(\mathbb{N}\) and the pseudo semiring \(\mathbb{T}\) of decision tree syntaxes. For each index \(\boldsymbol{k} \in \mathbb{N}[{\boldsymbol{m}}]\), the \(\boldsymbol{k}\)-th cell of \(T\) holds a pair \(T(\boldsymbol{k}) = (N_{\boldsymbol{k}}, t_{\boldsymbol{k}})\) consisting of a count \(N_{\boldsymbol{k}} \in \mathbb{N}\) and a tree \(t_{\boldsymbol{k}} \in \mathcal{M}_{\Delta}\). The first semiring \(\mathbb{N} = (\mathbb{N}, +, \times)\) maintains the count \(N_{\boldsymbol{k}}\) of trees falling into the \(\boldsymbol{k}\)-th cell of \(T\), \(N_{\boldsymbol{k}} = T(\boldsymbol{k}) \in \mathbb{N}\), for all indices \(\boldsymbol{k} \in \mathbb{N}[{\boldsymbol{m}}]\). On the other hand, the second pseudo semiring \((\mathbb{T}, +, \{\kern 0.00em\langle f,\cdot,\cdot\rangle\kern 0.00em\}_{f \in F})\) holds a tree \(t\) uniformly sampled by the probability \(P_{\boldsymbol{k}} = N_{\boldsymbol{k}}/N_\mathrm{total} \in [0,1]\), where \(N_\mathrm{total} = \sum_{\boldsymbol{k}} N_{\boldsymbol{k}} = |\mathcal{M}_{\Delta}|\) is the total count. Since the rest of the construction is almost the same as Goral et al. [9], we omit the details. We implemented this function in our software emtrees. Fig. 4 shows our dashboard interface, rendering a randomly sampled tree from the associated cell.

5 Experimental Evaluation↩︎

We evaluate ADTC on real-world data to demonstrate its scalability and utility in providing a transparent and rigorous analysis of high-performing decision trees.

5.1 Setup↩︎

Dataset. We use the UCI adult dataset (32,129 data) as a standard benchmark for research on fairness and predictive multiplicity, aiming to predict whether annual income exceeds $50,000 using mixed categorical and continuous variables.

Measurement Protocol. Computational cost is evaluated using: (i) time (execution time in seconds); (ii) cell_scan (total number of cells scanned as a platform-independent cost); and (iii) num_cells (non-zero entries in the resulting tensors). For parameter configurations, we use the following settings unless otherwise stated: \(\texttt{maxdep}=5\) (maximum depth), \(\texttt{nbins}=7\) (number of bins in discretization of numerical features), \(\texttt{relminsup}=0.15\) (relative minimum support), and \(\texttt{siz}=6\) (tree size). Data scalability analysis varies \(n_{\text{data}}\) from 40 to 32,129 (all data). Structural complexity analysis scales maxdep and siz proportionally. Constraint relaxation analysis varies siz from 1 to 16 with \(n_{\text{data}}=640\) and \(\texttt{maxdep}=4\). Environment: The system emtrees is implemented in Python 3.12 and executed on an Apple M1 Pro PC (16GB memory, macOS 15.7.1). The source code is publicly available.³

5.2 Scalability and computational efficiency↩︎

Our empirical evaluation demonstrates that ADTC exhibits scalable and stable behavior across all parameters. Our program ran within several minutes on mid-sized datasets such as UCI mushroom, adult,⁴ and COMPAS ⁵ under the parameter settings above.

Scalability with input size. As shown in Fig. 5, the runtime and cell_scan follow near-linear trends on a log-log scale, confirming polynomial complexity relative to \(n_{\text{data}}\). Even with an 800-fold increase in data size, the runtime remains manageable at 255.79 seconds for the full dataset (\(1.1\times 10^9\) cells scanned). Concurrently, num_cells grows proportionally, indicating a more refined model profile for larger datasets.

Impact of structural constraints. We evaluate how structural expansion affects efficiency. Tree depth: Fig. 6 shows that the cell_scan grows as depth \(\Delta\) (maxdep) relaxes, reflecting the expansion of the search space. Despite the doubly exponential nature of the syntactical space, the operations remain stable, reaching \(\approx 2.0 \times 10^7\) scanned cells at \(\Delta = 5\). Tree size constraint: Fig. [fig:size95impact] shows that relaxing the tree size constraint \(s\) (siz) increases num_cells, yielding a more detailed model profile. Stabilization of cell_scan at higher siz values suggests that model tensors efficiently aggregate properties once structural complexity is captured, incurring minimal overhead.

5.3 Impact of model complexity on the Rashomon set↩︎

We analyze the structural properties of near-optimal models by examining the relationship between model size (siz) and depth (maxdep). We focus on high-performing models with \(\text{acc} \ge 0.749\) in the Rashomon set. Fig. 4 (a) (in 4.2) reveals that 352,768 top-performing trees cluster in the range of depth \(4\) and sizes \(4\sim 5\), showing strong structural consistency. This highlights the trade-off between interpretability and predictive performance under diverse deployment scenarios. See 4.2 for details on the dashboard shown in Fig. 4 (b).

5.4 Trade-off analysis between accuracy and fairness↩︎

To demonstrate how ADTC supports evidence-based model selection, Fig. 1 (in 1) and Fig. 7 show the distribution of the 34,706 models extracted from the Rashomon set on the adult dataset. These distributions are evaluated with respect to accuracy (acc), F1-score (F1), and fairness metrics, including demographic parity (DP), equalized odds (EOdd), and equal opportunity (EOpp) [27]. The obtained cross-tables provides a rigorous model profile that serves as objective evidence for model selection.

For instance, in Fig. 7 (a), our framework identifies a large cluster of \(15,340\) models in the bin with the highest accuracy (\(\texttt{acc} \in [0.765, 0.831]\)) and low fairness error \(\texttt{EOdd} \in [-0.029, 0.086]\)), while revealing a smaller cluster of \(688\) models with the same accuracy but significantly higher fairness error (\(\texttt{EOdd} \in [0.886, 1.000]\)). Conversely, many models with moderate accuracy exhibit high fairness disparity, such as the 10,906 models with \(\texttt{acc} \in [0.566, 0.633]\) and high EOdd. By providing a complete landscape of the Rashomon set, ADTC facilitates evidence-based model selection, allowing practitioners to prioritize high-accuracy models with minimal fairness disparity from numerous candidates rather than relying on a single heuristic output.

5.5 Assessment of preprocessing↩︎

In Fig. 2 (in 1), we show the model profiles on accuracy (acc) and balanced accuracy (bacc) [26] of near-optimal models generated by ADTC on the original adult dataset and its class-balanced dataset. They show a discrepancy between acc and bacc in the original dataset, which is successfully calibrated in the balanced dataset.

6 Conclusion↩︎

This paper presents ADTC, a formal framework for the global assessment of decision tree spaces. Through the use of model behavior tensors and an algebraic formulation, we provide a scalable methodology for evidence-based model selection, enabling a rigorous analysis of the landscape of interpretable models.

Theoretically, this research contributes by formulating the ADTC problem and developing efficient algorithms that establish complexity upper bounds over general semirings. For future work, extending the ADTC framework to other interpretable models is a promising direction, building upon existing enumeration techniques for LASSO models [28], support vector machines [29], and rule lists with profile construction [30]. Finally, we will investigate the computational complexity of ADTC relative to standard counting classes like Valiant’s \(\# \mathrm{P}\) [31] and the semiring-based class \(\mathrm{NP}_\infty(R)\) recently proposed in [32]. Our tensor-manipulation software, emtrees, introduced in Sec. 3 and Sec. 4, is publicly available at https://doi.org/10.5281/zenodo.20842908.

Acknowledgments.↩︎

The author thanks Koji Tsuda and Jun Sese for initially drawing attention to the optimal decision tree problem, and Yasuko Matsui for invaluable discussions on our preliminary research [19] during the organized session at IFORS 2017 in Québec. The author is also grateful to Ichigaku Takigawa, Shinya Takamaeda-Yamazaki, Atsuyoshi Nakamura, Masato Motomura, and the members of the CREST project. The author is also grateful to Kazuki Yoshizoe, Yasuaki Kobayashi, Norihito Yasuda, Takeaki Uno, and Shinichi Minato, during the AFSA project meeting for their comments and discussions. This work is supported by MEXT/JSPS KAKENHI Grant Number 26K02980, 20H00595, 20H05963, and JST CREST 18070962.

References↩︎

---

1. A rational expression is a fraction of multi-variate polynomials \(\frac{P(x)}{Q(x)}\), where \(x\) is a sequences of variables for functions. The set of rational functions is closed under addition, subtraction, multiplication, and division by non-zero functions [25].↩︎

2. Unlike cyclic polynomials \(R[(x_j)_d]/\langle x^{m_j}-1\rangle_{j=1}^{d}\) typical in signal processing, we use truncated polynomials \(R[(x_j)_d]/\langle x^{m_j}\rangle_{j=1}^{d}\).↩︎

3. emtrees: https://doi.org/10.5281/zenodo.20842908↩︎

4. https://archive.ics.uci.edu↩︎

5. https://www.kaggle.com/datasets/danofer/compass↩︎