Reproduce “Anytime Optimal Decision Tree Learning with Continuous Features” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Harold Kiossou, Pierre Schaus, Siegfried Nijssen

CA-ConTree (Complete Anytime Continuous Tree) introduces an algorithm that learns optimal decision trees directly from continuous features, providing high-quality solutions rapidly while guaranteeing optimality upon completion. It achieves a lower primal integral across various time budgets and improves test set accuracy compared to existing exact and greedy methods.

Key insights

  • Combining Limited Discrepancy Search with heuristic-guided exploration allows algorithms to provide high-quality solutions early in the search process without sacrificing eventual optimality guarantees.
  • A balanced strategy for increasing discrepancy budgets, such as the diagonal sweep, is crucial for effectively improving anytime performance in complex search spaces with many continuous features.
  • Integrating specialized optimal solvers for subproblems (e.g., depth-2 trees) and pruning techniques (e.g., SLB) is essential for practical scalability when dealing with continuous features within an anytime framework.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.