Extracting logical rules from ensembles of symbolic learning models, and especially from ensembles of decision trees, is a very well-known discipline, and several methods and algorithms have been proposed for its solution. However, the existing approaches are characterized by being purely statistical. In this paper, we discuss the problem of systematically extracting minimal logical rules from ensembles of trees from both a theoretical and an algorithmic point of view.
In sharp opposition to the proliferation of machine learning models used to approach all range of typical artificial intelligence problems, from classification, to regression, to reinforcement learning, the universal concept linked to the interpretation and the explanation of such models is that of rule. As a matter of fact, it can be said that all diferent statistical learning models are diferent methods for implicit or explicit rule extraction from data.
Unsurprisingly, the idea of expressing the behaviour of a data-driven artificial intelligent agent in
terms of rules is extremely pervasive. On the one side, learning models are usually separated into
symbolic ones, such as decision trees or linear regressions, sub-symbolic ones, such as neural networks,
and mixed ones, such as ensembles of trees. On the other side, methods for explaining learning models
are classified into global ones, that are focused on the model as a whole, and local ones, focused on
the behaviour of a model on a specific instance. Numerous literature surveys on explainable artificial
intelligence and interpretable machine learning have been conducted (e.g., see [
With symbolic learning methods we represent data and relationships using symbolic structures.
Decision trees [
The development of global explanation methods for decision forests is paramount, and several
solutions have been proposed in the past, including Partial Dependence Plots [
We initiate a systematic study of purely logical global rules extraction from decision forests. The
language of standard decision forest is propositional; propositions range from simple assertions of the
type ◁▷ , where is an attribute, is a constant, and ◁▷ is a comparison operator (e.g., fever is over
38 degrees), to complex (yet atomic) sentences, of the type (1, . . . , ) ◁▷ , where 1, . . . , are
attributes and is an (arbitrary) function applied to them (e.g., the averaged vibration of sensors and
is below 100 Hertz — examples of such propositions emerge, among others, in oblique decision trees
and forests [
In this paper we ask the question, given a decision forest and a class : which is a strong class rule for whose antecedent is minimal in size? In its decision version, given a number , it becomes: is there a strong class rule for whose antecedent is such that | | ≤ ? Obtaining small class rules difers from pure logical minimization in two key aspects. First, minimization of propositional formula is usually not intended modulo a theory , but, in general, classic minimization methods and techniques can be adapted to this case. Second, in our case minimization does not need to preserve logical equivalence, but only equivalence modulo the set of instances ℐ on which the original forest was learnt. We shall see that this problem can be very hard in terms of computational complexity, and it makes sense to consider other (ideally, simpler) versions of it. We define the concept of right weak class rule, (resp., left weak class rule) that is, a rule of the type ⇒ (resp., ⇐ ) such that if ∈ ℐ satisfies (resp., classifies as ) then classifies as , (resp., that if ∈ ℐ satisfies ), and we ask the question, given a decision forest and a class : which is a right (resp., left) weak class rule for whose antecedent is minimal (resp., non-trivially maximal) in size? Or, in its decision version, given also a number : is there a right (resp., left) weak class rule for whose antecedent (resp., non-trivial antecedent) is such that | | ≤ (resp., | | ≥ )?
Definition 1. A dataset is a set of instances ℐ = {1, . . . , }, each one of which is described by the values of attributes = {1, . . . , }.
Without lack of generality we assume that the value of each attribute in an instance is a real number. Several problems are usually associated with datasets; in the case of supervised learning, each instance is also associated to a label (or class) ∈ ℒ, and a dataset is termed labelled. Given a labelled dataset ℐ, supervised classification consists of synthesizing an algorithm (a classifier ) that is able to classify the instances of an unlabelled dataset whose instances are defined on the same set of attributes.
In the symbolic context, instances are seen as logical models. To help this interpretation one takes into consideration that datasets are naturally associated to a logical vocabulary of propositional Definition 2. ℒ) is a tuple letters, from which formulas are built. In the most general case, we have =
{( (1, . . . , ) ◁▷ ) | ∈ ℱ , ∈ R, ◁▷ ∈ {<, ≤ , =, ≥ , >}}, where ℱ is a set of suitable feature extraction functions. To a dataset ℐ, we associate its vocabulary and a (possibly empty) theory , that is, a set of propositional formulas of the type → , where , ∈ , that expresses semantic constraints between propositional letters (e.g., > 5 implies > 4). In the following, we write |= to denote that a propositional formula is satisfied by .
Let ℒ be a set of classes and a finite set of propositional letters. Then, a decision tree (on = ⟨, , , ⟩, where ⟨, ⟩ is a full binary directed tree, is a leaf-labelling function that assigns a class from ℒ to each leaf node in , and is an edge-labelling function that assigns a decision from {, ¬ | ∈ } to each edge in , in such a way that two siblings always have opposite decisions. A decision forest = { 1, . . . , } (on ℒ) is a set of decision trees (on ℒ).
A decision tree/forest is learnt from a dataset ℐ based on its vocabulary (the language of the tree/forest). An instance is classified by a tree by progressively checking the truth value of each proposition on a path (and we denote with ( ) the class assigned to an instance by ), and by a forest ( ( )) by systematically querying each tree individually and then aggregating their decisions; among other possibilities, a typical aggregation function is simple majority, which is assumed here. Definition 3. Given a decision tree on ℒ and a class ∈ ℒ, then: () given and a path in from the root to a leaf labeled with (an L-path), the conjunction of all decisions on is called L-path tree formula, and it is denoted by , and () the disjunction of all -path formulas in is called L-class tree formula ( ). Given a decision forest on ℒ with trees, and a class ∈ ℒ, then: () given a collection 1 , . . . , ∈ and one -path (1 ≤ ≤ ) per tree , the conjunction of all -path tree formulas 1 , . . . , 1 is called partial L-path forest formula ( 1 ,..., ); () if > /2, then 1 ,..., is called L-path forest formula; and () the disjunction of all possible -path forest formulas is called L-class forest formula ( ).
Definition 4. Given a decision forest , learnt from a dataset ℐ, on ℒ, and a class ∈ ℒ, a strong -class rule is an object of the type ⇔ , where (the antecedent) is a propositional formula in the language of , such that, for every ∈ ℐ, |= if and only if ( ) = , a right weak -class rule is an object of the type ⇒ such that |= implies ( ) = , and a left weak -class rule is an object of the type ⇒ such that ( ) = implies |= .
Given a decision forest on ℒ, a class ∈ ℒ, and the -class forest formula , ⇔ is a (trivial) strong -class rule. In practical terms, it will likely be very redundant, due to the fact that decision trees and forest are general learnt via sub-optimal learning algorithms (recall that the problem of extracting a minimal decision tree is NP-hard, and sub-optimal, polynomial algorithms are commonly used for learning), and the fact that the theory underlying the language is ignored during learning. Thus, given a decision forest on ℒ, learnt from a dataset ℐ, and a class ∈ ℒ, we are interested in finding a minimal strong -class rule, that is, a strong -class rule ⇔ such that, for every strong class rule ′ ⇔ so that ≡ ℐ ′ (i.e., so that and ′ are equivalent modulo at least with respect to the instances in ℐ), it is the case that | | ≤ | ′|.
One way to assess the complexity of the problem of finding minimal strong rules is to study its decision version, that is: given a decision forest , learnt from a given dataset ℐ, on ℒ, a class ∈ ℒ, and a number , is there a strong -class rule ⇔ such that | | ≤ ? Given that the size of the input of this problem is the number of symbols of (denoted by | |) plus the number of instances in ℐ (|ℐ|) and the size of the representation of (||), we have the following result.
Theorem 1. Given a decision forest , learnt from a dataset ℐ, on ℒ, a class ∈ ℒ, a theory , and a number , the problem of establishing if there exists a strong -class rule ⇔ such that | | ≤ is in NEXPTIME.
Proof[sketch]. An (DNF) antecedent of size less than or equal to can be guessed. Then, for each instance ∈ ℐ, is checked against both and : if () = (resp., not ) and |= (resp., ̸|= ), then is marked. If all instances in ℐ end up being marked, then ⇒ is a strong -class rule. The complexity of this process is polynomial in | | and |ℐ|, but exponential in ||, and the value of the minimal for which a strong -class rule exist may be exponential in | |. □ Since extracting a minimal strong class rule may turn out to be impractical, we turn our attention to weak rules. Given a decision forest , learnt on a dataset ℐ, on ℒ, a class ∈ ℒ, and a -path forest formula 1 ,..., , 1 ,..., ⇒ is a (trivial) right weak -class rule whose antecedent may exhibit the same kind of redundancy and can be minimized as in the previous case. Similarly, ⊤ ⇐ is a (trivial) left weak -class rule whose antecedent can be maximized; in this case, however, one is interested in non-trivial maximal antecedents.
Theorem 2. Given a decision forest on ℒ, a class ∈ ℒ, a theory , and a number , the problem of establishing if there exists a right weak -class rule ⇒ such that | | ≤ is in NP, and the problem of establishing if there exists a non-trivial left weak -class rule ⇒ such that | | ≥ is in NEXPTIME. Proof[sketch]. As for right weak -class rules, a (term) antecedent of size less than or equal to can be guessed. Then, for each instance ∈ ℐ, is checked against both and : if ̸|= , or |= and () = , then is marked. If all instances in ℐ end up being marked, then ⇒ is a weak -class rule. The complexity of this process is polynomial in | |, |ℐ|, but exponential in ||; however, the value of the minimal for which a right weak -class rule exist is polynomial in | |. As for left weak -class rules, a (DNF) antecedent of size grater than or equal to can be guessed. Then, we first check that is non-trivial, that is, there are no repeated literals in any term, no term is unsatisfiable, and no terms implies any other term. Then, for each instance ∈ ℐ, is checked against both and : if () ̸= , or () = and |= , then is marked. If all instances in ℐ end up being marked, then ⇒ is a weak -class rule. The complexity of this process is polynomial in | | and |ℐ|, but exponential in ||, and the value of the minimal for which a left weak -class rule exist may be exponential in | |. □
We started a systematic study of logical methods for rule extraction from decision forests, a well-known classification model. Extracting rules from decision forests is a well-known problem, but existing solutions are statistical and data-driven. In our work, we apply known logical algorithms to rule extraction, contributing to bridging the gap between logic and machine learning.
We acknowledge the support of the FIRD project Methodological Developments in Modal Symbolic Geometric Learning, funded by the University of Ferrara, and the INDAM-GNCS project Symbolic and Numerical Analysis of Cyberphysical Systems (code CUP_E53C23001670001), funded by INDAM; Giovanni Pagliarini and Guido Sciavicco are GNCS-INdAM members. Moreover, this research has also been funded by the Italian Ministry of University and Research through PNRR - M4C2 - Investimento 1.3 (Decreto Direttoriale MUR n. 341 del 15/03/2022), Partenariato Esteso PE00000013 - "FAIR - Future Artificial Intelligence Research" - Spoke 8 "Pervasive AI", funded by the European Union under the NextGeneration EU programme".