Approximate Optimal Active Learning of Decision Trees
Zunchen Huang, Chenglu Jin · 2025
Read Approximate Optimal Active Learning of Decision Trees by Zunchen Huang, Chenglu Jin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-03971.txt.
Description
Imagine learning a hidden decision tree by asking it questions, one answer at a time, with a guarantee the questions are nearly optimal. Zunchen Huang and Chenglu Jin pursue that goal in a 2025 preprint on logic in computer science. Instead of entropy heuristics, they encode every candidate tree of bounded depth into SAT formulas.
Each possible question's value is estimated by counting, approximately, how many candidate trees it would rule out. An approximate model counter measures the shrinking hypothesis space after every answer, so the learner strengthens its formula step by step. If counting stalls, an equivalence check tests whether surviving trees compute the same function. In experiments, the method converged to the correct tree after a handful of queries. The rigorous foundation suits formal analysis and verification settings.
Catalog record
| CREATOR | Zunchen Huang, Chenglu Jin |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-03971