PyDL8.5: a Library for Learning Optimal Decision Trees

Gaël Aglin, Siegfried Nijssen, Pierre SchausIJCAI 2020 · DOI

TL;DR

This paper introduces PyDL8.5, a Python library for learning "optimal" decision trees (ODTs) that are constrained by depth. Unlike traditional heuristic methods, PyDL8.5 uses an efficient algorithm (DL8.5) to find trees that achieve the best possible score under depth constraints, making them more interpretable and accurate. The library offers a scikit-learn compatible interface, enabling its use for classification, regression, and clustering tasks.

What Problem Does This Paper Address?

Machine learning models are increasingly used across various domains, but their interpretability remains a significant concern, especially in fields like Explainable AI (XAI). Decision trees are popular due to their inherent interpretability, particularly when they are shallow. However, standard decision tree learning algorithms (like CART and C4.5) employ greedy, heuristic approaches. These methods can lead to suboptimal trees, especially when a depth constraint is imposed. A greedy algorithm might produce a tree that is unnecessarily deep to achieve a certain accuracy, or conversely, a depth-constrained tree might not reach the desired accuracy. Furthermore, adapting these greedy methods to tasks beyond classification often requires developing new, specialized heuristics, which is a cumbersome process. This paper addresses the need for a method to learn truly optimal decision trees under depth constraints, ensuring the best possible performance for a given tree depth and facilitating their application to a wider range of machine learning tasks.

Methods

The core of PyDL8.5 is the DL8.5 algorithm, which learns optimal decision trees (ODTs) under depth constraints. DL8.5 employs a combination of dynamic programming and branch-and-bound search. It recursively explores possible splits, aiming to find the split that yields the lowest score. To handle repeated computations on the same data subsets, DL8.5 incorporates a caching system. For pruning the search space, it uses a bounding system: when a subtree is found, its score serves as an upper bound for future subtrees. The algorithm leverages the additive nature of scoring functions to prune subtrees more effectively.

PyDL8.5 itself is a Python 3 library built upon this DL8.5 algorithm. It's implemented with a C++ core for performance, utilizing 64-bit vector operations. A key feature is its adherence to the scikit-learn fit/predict interface, making it seamlessly integrable into existing Python machine learning workflows. The library is designed to be extensible, allowing users to define custom scoring functions for various optimization criteria, provided they are additive. This flexibility is crucial for applying ODT learning to tasks beyond classification, such as predictive clustering.

Datasets

The paper mentions the use of "commonly used UCI datasets" for evaluating DL8.5's performance. Specific datasets are not detailed in the main text, but "anneal.txt" is used in Listing 1 for the shallow classifier example.

Key Insights and Ideas

  • Optimality Under Constraints: The paper highlights that traditional greedy decision tree algorithms are not optimal when depth is a strict constraint. DL8.5's approach of finding the best possible tree for a given depth is a significant improvement for interpretability and performance.
  • Extensibility for Diverse Tasks: The design of PyDL8.5, particularly its support for user-defined additive scoring functions, is a major innovation. This allows ODTs to be applied to tasks like predictive clustering without needing to develop entirely new heuristic algorithms, democratizing the use of optimal decision trees.
  • Performance Gains: The DL8.5 algorithm, as implemented in PyDL8.5, is shown to be computationally efficient, capable of finding ODTs on standard datasets within seconds, making interactive use feasible.
  • Scikit-learn Integration: Providing a scikit-learn compatible interface is a practical and impactful design choice, lowering the barrier to entry for users already familiar with the Python data science ecosystem.

Key Results

The paper demonstrates that PyDL8.5 can efficiently learn optimal decision trees. For classification tasks, the default scoring function minimizes misclassification error. The library is also shown to be capable of solving problems like finding the shallowest tree with perfect accuracy (100%) on training data, often more rapidly than SAT solver-based approaches. The examples showcase how easily users can define custom scoring functions for tasks like predictive clustering, where the objective is to minimize the sum of Euclidean distances to cluster centroids.

Limitations and Future Work

The authors acknowledge that while DL8.5 finds optimal trees under depth constraints, the problem of learning ODTs is inherently NP-hard, meaning that for very large or complex problems, computation time could still be a factor.

Future work suggested by the authors includes exploring the performance of ODTs in ensembles, their application to regression and probability estimation, multi-target prediction, and other related areas. The PyDL8.5 library is presented as a tool to facilitate research into these open questions.

Summary updated

BibTeX
@inproceedings{aglin2020pydl,
  author = {Gaël Aglin and Siegfried Nijssen and Pierre Schaus},
  title = {{PyDL8.5: a Library for Learning Optimal Decision Trees}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/750},
}
Figure