Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO*
Authors: Ayman Chaouki, Jesse Read, Albert Bifet
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We prove both optimality and complexity guarantees for BRANCHES and we show that it is more efficient than the state of the art theoretically and on a variety of experiments. (Abstract). We employ 11 datasets from the UCI repository. For each dataset we use different types of encodings... (Section 5, Experiments) |
| Researcher Affiliation | Academia | 1LIX, Ecole Polytechnique, IP Paris 2AI Institute, University of Waikato 3LTCI, T el ecom Paris, IP Paris. |
| Pseudocode | Yes | We provide implementation details and a pseudocode in Appendix D and Algorithm 1. |
| Open Source Code | Yes | BRANCHES https://github.com/Chaoukia/branches. |
| Open Datasets | Yes | We employ 11 datasets from the UCI repository. |
| Dataset Splits | Yes | Figure 13, Figure 14, Figure 15 and Figure 16 report the median and the quartiles of the accuracy and number of splits of the proposed solutions induced by a 10 fold crossvalidation |
| Hardware Specification | Yes | we run all the experiments on a personal Machine (Processor: 2,6 GHz 6-Core Intel Core i7; Memory: 16 GB). |
| Software Dependencies | No | No specific software dependencies with version numbers are explicitly listed for the experiments. The paper mentions a "Python implementation" for BRANCHES, but does not provide version numbers for Python or any specific libraries used. |
| Experiment Setup | Yes | We set a time limit of 5 minutes for all algorithms and we run all the experiments on a personal Machine (Processor: 2,6 GHz 6-Core Intel Core i7; Memory: 16 GB). Moreover, since it is necessary to fix a maximum depth for DFS methods, we set it to 20 for Mur Tree and STree D while the BFS methods GOSDT and BRANCHES run with infinite maximum depth. The λ values reported in Table 4 are those employed in the experiments of Section 5, they were chosen from a pool of values λ {0.1, 0.05, 0.025, 0.01, 0.005, 0.001} to yield meaningful solutions. For DL8.5, we ran it with with maximum depths raging between 1 and 10. We set the maximum nodes for Mur Tree to 80. |