Search papers, labs, and topics across Lattice.
This paper introduces Algebraic Decision Tree Counting (ADTC), a formal framework that enables exhaustive analysis of optimal and near-optimal decision trees by reformulating various analytical tasks into a unified sum-of-products computation over a semiring. The authors present a dynamic programming algorithm that achieves a time complexity of \(O^*(n^{O(\Delta)})\), significantly improving the efficiency of analyzing the doubly exponential hypothesis space of decision trees. By utilizing model behavior tensors to aggregate metrics, ADTC provides a comprehensive model profile that aids in evidence-based model selection across critical dimensions such as accuracy, size, and fairness.
Exhaustive analysis of decision trees is now feasible with a new algebraic framework that transforms complex metrics into actionable insights for model selection.
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 $R$. While the hypothesis space of decision trees is doubly exponential with respect to the maximum depth $\Delta$, our dynamic programming algorithm achieves $O^*(n^{O(\Delta)})$ time complexity in the number of features $n$, where $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.
