Approximate Optimal Active Learning of Decision Trees

2025/12/03 by Chenglu Jin, Huang, Zunchen, Jin, Chenglu
Computer Science · #Machine Learning and Algorithms #Explainable Artificial Intelligence (XAI) #Adversarial Robustness in Machine Learning

paper · pdf · doi:10.48550/arxiv.2512.03971

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.

Citations

• A Simple Approximation Algorithm for Optimal Decision Tree
• Learning Optimal Signal Temporal Logic Decision Trees for Classification: A Max-Flow MILP Formulation
• Efficient Black-Box Checking via Model Checking with Strengthened Specifications
• Inferring Temporal Logic Properties from Data using Boosted Decision Trees
• Approximate Probabilistic Inference via Word-Level Counting
• Learning Invariants using Decision Trees
• A Scalable Approximate Model Counter
• Active Learning on Trees and Graphs
• On probabilistic inference by weighted model counting

Related

• Properly learning decision trees in almost polynomial time
• Adaptive Exact Learning of Decision Trees from Membership Queries
• Active Learning on Trees and Graphs
• Properly Learning Decision Trees with Queries Is NP-Hard
• Greedy Algorithms for Decision Trees with Hypotheses