Approximate Optimal Active Learning of Decision Trees

• URL: http://arxiv.org/abs/2512.03971v1
• Date: Wed, 03 Dec 2025 17:03:39 GMT
• Title: Approximate Optimal Active Learning of Decision Trees
• Abstract summary: We consider the problem of actively learning an unknown binary decision tree using only membership queries.<n>We propose a symbolic method for active learning of decision trees, in which approximate model counting is used to estimate the reduction of the hypothesis space.<n> Experiments on decision trees show that the method reliably converges to the correct model using only a handful of queries.
• Score: 4.834817711255487
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of actively learning an unknown binary decision tree using only membership queries, a setting in which the learner must reason about a large hypothesis space while maintaining formal guarantees. Rather than enumerating candidate trees or relying on heuristic impurity or entropy measures, we encode the entire space of bounded-depth decision trees symbolically in SAT formulas. We propose a symbolic method for active learning of decision trees, in which approximate model counting is used to estimate the reduction of the hypothesis space caused by each potential query, enabling near-optimal query selection without full model enumeration. The resulting learner incrementally strengthens a CNF representation based on observed query outcomes, and approximate model counter ApproxMC is invoked to quantify the remaining version space in a sound and scalable manner. Additionally, when ApproxMC stagnates, a functional equivalence check is performed to verify that all remaining hypotheses are functionally identical. Experiments on decision trees show that the method reliably converges to the correct model using only a handful of queries, while retaining a rigorous SAT-based foundation suitable for formal analysis and verification.

Related papers

• TopBench: A Benchmark for Implicit Prediction and Reasoning over Tabular Question Answering [80.93487993878836]
  A common class of real-world queries is implicitly predictive, requiring the inference of unobserved answers from historical patterns rather than mere retrieval.<n>These queries introduce two challenges: recognizing latent intent and reliable predictive reasoning over massive tables.<n>We introduce TopBench, a benchmark consisting of 779 samples across four sub-tasks, ranging from single-point prediction to decision making, treatment effect analysis, and complex reasoning.
  arXiv  Detail & Related papers  (2026-04-30T16:22:51Z)
• Partition Trees: Conditional Density Estimation over General Outcome Spaces [46.1988967916659]
  We propose Partition Trees, a tree-based framework for conditional density estimation over general outcome spaces.<n>Our approach models conditional distributions as piecewise-constant densities on data adaptive partitions and learns trees by directly minimizing conditional negative log-likelihood.
  arXiv  Detail & Related papers  (2026-02-03T22:12:30Z)
• Bounding Causal Effects and Counterfactuals [0.0]
  This thesis addresses challenges by systematically comparing bounding algorithms across multiple causal scenarios.<n>We implement, extend, and unify state-of-the-art methods within a common evaluation framework.<n>Our empirical study spans thousands of randomized simulations involving both discrete and continuous data-generating processes.
  arXiv  Detail & Related papers  (2025-08-19T08:13:34Z)
• A Principled Approach to Randomized Selection under Uncertainty: Applications to Peer Review and Grant Funding [61.86327960322782]
  We propose a principled framework for randomized decision-making based on interval estimates of the quality of each item.<n>We introduce MERIT, an optimization-based method that maximizes the worst-case expected number of top candidates selected.<n>We prove that MERIT satisfies desirable axiomatic properties not guaranteed by existing approaches.
  arXiv  Detail & Related papers  (2025-06-23T19:59:30Z)
• Leveraging Predictive Equivalence in Decision Trees [25.79772180003752]
  Decision trees are widely used for interpretable machine learning.<n>We present a representation of decision trees that does not exhibit predictive equivalence.<n>We show that decision trees are surprisingly robust to test-time missingness of feature values.
  arXiv  Detail & Related papers  (2025-06-17T03:11:30Z)
• Learning Decision Trees as Amortized Structure Inference [59.65621207449269]
  We propose a hybrid amortized structure inference approach to learn predictive decision tree ensembles given data.<n>We show that our approach, DT-GFN, outperforms state-of-the-art decision tree and deep learning methods on standard classification benchmarks.
  arXiv  Detail & Related papers  (2025-03-10T07:05:07Z)
• Model-free Methods for Event History Analysis and Efficient Adjustment (PhD Thesis) [55.2480439325792]
  This thesis is a series of independent contributions to statistics unified by a model-free perspective.<n>The first chapter elaborates on how a model-free perspective can be used to formulate flexible methods that leverage prediction techniques from machine learning.<n>The second chapter studies the concept of local independence, which describes whether the evolution of one process is directly influenced by another.
  arXiv  Detail & Related papers  (2025-02-11T19:24:09Z)
• Optimized Feature Generation for Tabular Data via LLMs with Decision Tree Reasoning [53.241569810013836]
  We propose a novel framework that utilizes large language models (LLMs) to identify effective feature generation rules. We use decision trees to convey this reasoning information, as they can be easily represented in natural language. OCTree consistently enhances the performance of various prediction models across diverse benchmarks.
  arXiv  Detail & Related papers  (2024-06-12T08:31:34Z)
• Learning accurate and interpretable tree-based models [27.203303726977616]
  We develop approaches to design tree-based learning algorithms given repeated access to data from the same domain.<n>We propose novel parameterized classes of node splitting criteria in top-down algorithms, which interpolate between popularly used entropy and Gini impurity based criteria.<n>We extend our results to tuning popular tree-based ensembles, including random forests and gradient-boosted trees.
  arXiv  Detail & Related papers  (2024-05-24T20:10:10Z)
• Bisimulation Learning [55.859538562698496]
  We compute finite bisimulations of state transition systems with large, possibly infinite state space. Our technique yields faster verification results than alternative state-of-the-art tools in practice.
  arXiv  Detail & Related papers  (2024-05-24T17:11:27Z)
• Calibrating Neural Simulation-Based Inference with Differentiable Coverage Probability [50.44439018155837]
  We propose to include a calibration term directly into the training objective of the neural model. By introducing a relaxation of the classical formulation of calibration error we enable end-to-end backpropagation. It is directly applicable to existing computational pipelines allowing reliable black-box posterior inference.
  arXiv  Detail & Related papers  (2023-10-20T10:20:45Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  The sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs) This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models. In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.
  arXiv  Detail & Related papers  (2023-07-01T18:35:21Z)
• Regularized impurity reduction: Accurate decision trees with complexity guarantees [20.170305081348328]
  We propose a tree-induction algorithm that gives a logarithmic approximation guarantee on the tree complexity. The enhanced algorithms strike an excellent balance between predictive accuracy and tree complexity.
  arXiv  Detail & Related papers  (2022-08-23T13:15:19Z)
• The vacuum provides quantum advantage to otherwise simulatable architectures [49.1574468325115]
  We consider a computational model composed of ideal Gottesman-Kitaev-Preskill stabilizer states. We provide an algorithm to calculate the probability density function of the measurement outcomes.
  arXiv  Detail & Related papers  (2022-05-19T18:03:17Z)
• Adaptive n-ary Activation Functions for Probabilistic Boolean Logic [2.294014185517203]
  We show that we can learn arbitrary logic in a single layer using an activation function of matching or greater arity. We represent belief tables using a basis that directly associates the number of nonzero parameters to the effective arity of the belief function. This opens optimization approaches to reduce logical complexity by inducing parameter sparsity.
  arXiv  Detail & Related papers  (2022-03-16T22:47:53Z)
• Robust Optimal Classification Trees Against Adversarial Examples [5.254093731341154]
  We propose a collection of methods to train decision trees that are optimally robust against user-specified attack models. We show that the min-max optimization problem that arises in adversarial learning can be solved using a single minimization formulation. We also present a method that determines the upper bound on adversarial accuracy for any model using bipartite matching.
  arXiv  Detail & Related papers  (2021-09-08T18:10:49Z)

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.