A core idea of inductive databases was the creation of systems that can be queried declaratively for patterns and models. A natural question during the development of inductive databases was how such systems would work for one of the most popular models in machine learning, the decision tree. In our ifrst work on this topic, in 2007, we introduced DL8, an algorithm that showed how to calculate optimal decision trees from itemset patterns. Driven by an interest in imposing additional requirements on predictive models, such requirements of interpretability and fairness, in recent years the calculation of optimal decision trees has gained a lot of interest again. In this context, we proposed an extension of DL8, DL8.5, which obtained better performance than competitor systems. This abstract describes how research on inductive databases led to these recent systems and provides an overview of these systems.
A core idea of inductive databases was to create systems similar to database systems that would
allow a user to query a database for patterns and models in a declarative manner: a user could
specify requirements on patterns or models in a declarative language, after which this system
would be responsible for finding the patterns or models satisfying the requirements. Initially, a
lot of this research focused on developing systems for patterns: indeed, in the first iterations of
the international workshop on Knowledge Discovery using Inductive Databases (KDID), the
majority of the papers focused on pattern mining [
However, as it was recognized that predictive models are very important in machine learning
and data mining, subsequent studies considered inductive databases that would support models
as well. One such model was the decision tree, as reported on in the KDID workshop of
2006 [
Given a database Find a classification tree
Such that
• accuracy( ) is maximal
• depth( ) <maxdepth
• ∀ ∈ leaves( ): support() ≥ minsup
Here maxdepth and minsup are parameters specified by the user, and users would have the
ability to add additional constraints, as required by the application context. These queries would
be expressed in a form of SQL [
The constraints proposed initially were relatively simple in nature, involving characteristics
such as accuracy, size and depth. However, soon it was realized that other constraints could
also be relevant, such as on the privacy preserving nature or the cost of the decision trees, and
these were added to the language of constraints that inductive databases could support [
For many years, this work went unnoticed. However, in recent years the interest in imposing additional requirements on predictive models has risen significantly: issues of explainability, fairness, and privacy have grown dramatically in importance. This has led to a renewed interest in the question of how to impose requirements on decision tree models. Here, the work on inductive databases has recently been shown to be particularly relevant. In this abstract, we present a short summary of how the work on inductive databases led to recent state-of-the-art algorithms for learning optimal decision trees.
While creating a language for formulating some form of decision tree queries is not very
dificult, an important challenge for inductive database systems was how to create algorithms
for answering these queries. Traditional algorithms for learning decision trees, such as CART,
are heuristic in nature and have no functionality to ensure that good trees are found under
constraints [
A first attempt to address this problem in the context of inductive databases was made by
Fromont et al. [
The scalability of this approach was still limited; it only worked on all but the smallest databases. A challenge remained how to answer inductive queries on more realistic databases.
One idea that surfaced here was based on the observation that significant efort in the inductive
databases community had been spent on how to build eficient algorithms for pattern mining
and itemset mining in particular [
In 2007, this led to our proposal for the DL8 algorithm (‘Decision trees from Lattices’) [
Compared to earlier algorithms, a key element of the DL8 algorithm is that it solves the problem of finding a decision tree using dynamic programming. For the following problem: [Depth-Constrained Accurate Trees] Given a Boolean database with examples labeled in two classes Find a classification tree Such that • error( ) is minimal • depth( ) ≤ maxdepth the following recursive equation is at the basis of this dynamic programming approach: _() = ︂{ min ∈ℱ leaf _error () ∑︀∈( ) _( ∪ {}) if || < ℎ; if || = ℎ.
Here the recursion starts at _(∅), is an itemset, ℱ is the set features in the database, ( ) returns two items for each feature (one item for the value 0, one item for the value 1), and _() is the number of examples in the minority class of the examples covered by the itemset . In words, the tree with minimal error is obtained by picking in the root the feature which leads to the lowest sum of errors for the left-hand and right-hand child.
The dynamic programming approach is based on storing the value _ for itemsets
such that they do not need to be recalculated later on when the same features are considered in
a diferent order. This trick has as efect that the algorithm does not need to enumerate all trees,
but only needs to enumerate itemsets. We showed in 2007 that this makes it possible to find
optimal decision trees for a much larger number of databases [
While in our example above we use a depth constraint, in our original publication we did not give this constraint much attention; we introduced an optimisation which allowed the algorithm to find optimal decision specifically in cases where this constraint was absent, and did our experiments for that setting. In these experiments we found that in some cases optimal decision trees have better predictive performance than heuristically learned trees, in other cases their performance is worse.
We subsequently showed that this approach of dynamic programming over itemsets can also
be used in other settings: when adding a regularisation term in the optimisation criterion, when
taking into account costs and when taking into account a score for discrimination [
For a number of years there was little interest in the problem of finding optimal decision trees.
A publication by Bertsimas and Dunn [
Bertsimas and Dunn were clearly unaware of prior work on learning decision trees in the
inductive database context; hence, their publication also did not include a comparison with our
earlier work on DL8. In 2019 we decided to compare our original DL8 implementation with one
of the optimized versions of the MIP approach, BinOCT [
max depth = 4 1e+03 ()s1e+01 e m it n u R 1e−01 ● 1e+02 )(s1e+01 ● ● ● ● ● ● ● ● e itnm1e+00 uR ● 1e−01 1e−02 0 ● ● ● ● ● ● ● 1e+02 )s1e+01 ( e m itn1e+00 u R 1e−01 ● 1e−02 Algo ● BinOCT
CP−based 5
10 15 # instances solved
First, we studied whether the idea of using bounds during a branch-and-bound search could be added to DL8. This turned out to be possible, and was implemented in an algorithm that we called DL8.5. Results for this algorithm are also shown in Figure 1: a significant further speed-up compared to DL8 was obtained, making the gap with MIP-based approach even larger.
A perceived strength of the MIP-based approach is that it allows to model other learning
problems simply by changing the MIP formulation, similar to how inductive databases would
allow to find many diferent types of models. To make DL8.5 also more generally usable, we
created a library in Python which allows the user also to implement their own scoring function
in Python [
We studied whether the idea of finding optimal trees can also be extended towards forests of
decision trees, and showed that this is the case for LP-Boost based methods [
Compared to MIP, a possible weakness of DL8.5 is its memory use: it stores large amounts of
itemsets in order to calculate decision trees from them. In practice this means that the algorithm
can run out of memory on machines with small amounts of memory. We addressed this challenge
in an extension of DL8.5 which from time to time also removes itemsets from memory; while
this could mean these itemsets need to be recalculated later, with proper heuristics we can
assure that this does not happen too often. In practice this makes it possible to run the algorithm
in memory constrained environments for the price of not too much additional run time; indeed,
even under memory constraints DL8.5 remains much faster than MIP-based approaches [
Despite its better performance, DL8.5 still takes significant amounts of time for calculating
an optimal tree on some datasets. We asked the following question: suppose the user stops the
algorithm after a certain amount of time, can we still assure that the algorithm will return a
good tree at that moment? This led us to study other orders for traversing the search space [
The good performance of DL8.5 has led other people to continue with this algorithmic
approach. In particular, Demirovic et al. proposed MurTree [
An extension of DL8.5’s algorithm was also used to find decision trees for certain types of
non-linear scoring functions [
In this paper, we provided a short overview of optimal decision tree learning such as studied initially in the context of the Knowledge Discovery in Inductive Databases workshop, and how this has led to a type of algorithm, DL8, which has recently been studied in detail again and led to numerous new publications.
Given the fact that also in the first half of 2022 already many new publications have appeared on algorithms for finding optimal decision trees, we believe that this work will continue to be relevant. Also other older results in the domains of inductive databases and pattern mining may here gain relevance once more.
For instance, many of the current approaches are focused on depth-constrained decision trees. However, in our past work we showed that optimisations based on condensed representations of itemsets allow to find optimal decision trees also without such a constraint. The use of condensed representations may hence also merit a new look in this context.
Motivated by concerns over discrimination, privacy and explainability, the integration of additional constraints continues to be relevant. We expect that DL8-style algorithms will continue to be important in this context.
DL8’s performance derives from dynamic programming, where it assumed that the left-hand
and right-hand side of a test in a tree can be optimised independently. For some scoring functions
this independence does not apply. Search algorithms such as developed by Fromont et al. [
At its core, DL8 still performs a form of itemset mining. Many ideas present in the itemset mining literature, such as FP-Trees [23], have not been evaluated in the context of DL8 yet.
A remaining challenge for DL8-style algorithms continues to be how to treat find trues or numerical data. The integration of better discretization algorithms could be relevant here. [23] J. Han, J. Pei, Y. Yin, Mining frequent patterns without candidate generation, ACM sigmod record 29 (2000) 1–12.