Learning Optimal Decision Trees using Constraint Programming (Extended Abstract)

Hélène Verhaeghe, Siegfried Nijssen, Gilles Pesant, Claude-Guy Quimper, Pierre SchausIJCAI 2020 · DOI

TL;DR

This paper introduces a novel constraint programming (CP) approach for learning optimal decision trees. By combining AND/OR search, a specialized global constraint (COVERSIZE), and caching, their method significantly improves efficiency and flexibility in finding decision trees that minimize classification error while adhering to constraints like maximum depth.

What Problem Does This Paper Address?

Decision trees are a cornerstone of machine learning due to their interpretability and strong performance. However, traditional greedy algorithms for learning them often fall short. They struggle to produce trees of optimal accuracy, can result in unnecessarily complex trees, and make it difficult to incorporate specific constraints. This paper addresses the challenge of learning optimal decision trees, meaning trees that achieve the absolute best possible classification accuracy for a given dataset, while also allowing for flexible constraint incorporation, such as limiting the tree's depth.

Methods

The authors propose a constraint programming (CP) model for learning optimal decision trees. Their approach is built upon several key components:

  • Constraint Programming (CP): This is the overarching framework, allowing for declarative modeling of the problem and leveraging powerful CP solvers.
  • AND/OR Search: This search strategy is designed to exploit the inherent decomposability of decision tree learning problems. It breaks down the problem into smaller, independent subproblems (subtrees) that can be solved optimally and then combined.
  • COVERSIZE Global Constraint: This is an adaptation of a constraint originally used in itemset mining. It efficiently links itemsets (representing feature combinations) to the number of transactions that contain them, which is crucial for calculating decision tree accuracy.
  • Caching: Similar to the DL8 algorithm, they employ caching to store and retrieve previously computed optimal subtrees. This avoids redundant computations when identical subproblems arise in different parts of the search space.
  • Branch-and-Bound: This optimization technique is integrated into the CP solver to prune the search space by eliminating branches that cannot lead to a better solution than the best one found so far.

Datasets

Not discussed in the paper. The paper focuses on the methodology and theoretical aspects, using general concepts of datasets (binary matrices, transactions, classes) for illustration.

Key Insights and Ideas

  • CP as a Powerful Framework for Optimal Decision Trees: The paper demonstrates that CP, when combined with specialized techniques, can effectively model and solve the problem of finding optimal decision trees, overcoming limitations of greedy approaches.
  • Exploiting Decomposability with AND/OR Search: The success of their method hinges on the insight that decision tree learning can be decomposed into independent subproblems. AND/OR search is a natural fit for this structure.
  • The Power of Global Constraints: Adapting the COVERSIZE constraint from itemset mining proves to be a key enabler for efficiently calculating the accuracy of decision trees within the CP framework.
  • Caching for Efficiency: Recognizing and exploiting subtree equality through caching is crucial for reducing the computational burden, especially in larger search spaces.
  • Flexibility for Future Constraints: A significant advantage of the CP approach is its inherent flexibility, making it easier to incorporate a wider range of constraints (e.g., fairness, interpretability metrics) compared to traditional methods.

Key Results

The paper reports that their CP approach outperforms existing methods like DL8 and BinOCT on most benchmarks, finding and proving optimality for approximately 75% of instances within the time limit. Their method generally finds the best solution and is faster at proving optimality. They also note that DL8 performs better on smaller instances, and the gap with BinOCT is attributed to the benefits of AND/OR search.

Limitations and Future Work

  • Binary Data Assumption: The current model is primarily described for binary data. While they mention that continuous data can be discretized and binarized, and multi-class extensions are possible, these are areas for future work.
  • Scalability for Very Large Datasets: While their approach is more scalable than some, the performance on extremely large datasets might still be a challenge.
  • Future Work: The authors explicitly state that their approach can be extended in many ways, including handling multiclass problems, continuous features (via binarization), and incorporating additional side constraints. They also refer to a more detailed original paper and an extended journal version for further information.

Summary updated

BibTeX
@inproceedings{verhaeghe2020learning,
  author = {Hélène Verhaeghe and Siegfried Nijssen and Gilles Pesant and Claude-Guy Quimper and Pierre Schaus},
  title = {{Learning Optimal Decision Trees using Constraint Programming (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/662},
}
Figure