Taking inspiration from the literature fuzzy decision trees, and leveraging many-valued logics, we propose a novel, and more general variety of decision trees.
Decision trees (DTs) [
Generally, a sub-optimal decision tree learning algorithm involves two steps: splitting, that is, the process of dividing a node into two or more sub-nodes based on certain statistical measures such as Gini impurity, entropy, or variance reduction, aiming to make the child nodes as homogeneous as possible concerning the target variable, and pruning, that is, the process of removing sub-nodes of a decision tree to reduce its complexity and prevent overfitting; this can be obtained using criteria to stop the tree growth early (pre-pruning), or by removing branches from a fully grown tree (post-pruning).
It is well-known that a decision tree has a logical counterpart consisting of a set of (propositional) logical rules.
One common approach for improving the performances and enhancing the interpretability of DTs,
and in particular of their corresponding set of rules, is that of resorting to non-crisp logic. Classical,
crisp propositional logic is characterized by being based on the Boolean two-valued algebra; non-crisp
logic relaxes this assumption by allowing the existence of more than two truth values. The set of
truth values forms an algebra, and when the domain of such an algebra is the set of all real numbers
from 0 to 1 with the usual ordering (that is, it is standard), the corresponding logic is called fuzzy. In
the accepted terminology, ‘fuzzy’ and ‘non-crisp’ are synonyms in the context of logic; noteworthy
examples of varieties of fuzzy algebras include Gödel algebras (G) [
0 1 0 . . . . . .
. . . . . . . . . (0.72,0.803,0.67) . . . . . . . . . . . .
A fuzzy decision tree (FDTs) is essentially a decision tree that corresponds to a set of fuzzy propositional
logic rules. Existing FDT learning methods range from algorithms to synthesize a tree from a
userfuzzyfied dataset, such as FuzzyID3 [
Two traits that are common to essentially all existing proposals for FDT models and their learning algorithms are: () they are based on some standard fuzzy logic, and () they are generally not included in open-source, available frameworks for learning and reasoning; the latter, in particular, makes it dificult to evaluate their efectiveness in real situations.
Towards a unifying approach to generalize learning algorithms to the non-crisp case, we consider
here a more general variety of algebras, known as FL algebras [
In this paper, we theorize the many-expert decision tree model (MEDT), that corresponds to a set of many-valued propositional logic rules. We consider a specific class of FL -algebras, general enough to capture all typical fuzzy algebras commonly used in the FDT literature and beyond. MEDTs are parametric, so that the number of experts (which in some way can be thought of as the non-linearity degree of the algebra of truth values) can be varied and the operators for their opinions to be combined (that is, the algebra operators) can be customized within the degrees of freedom of FL-algebras.
A = ⟨A, ∩, ∪, · , +, 0, 1⟩, where ⟨A, ∩, ∪, 0, 1⟩ is a bounded complete lattice with upper bound 1 and lower bound 0, and ⟨A, ⪯⟩ corresponds to its lattice-ordered set. The two operations · and + are such that ⟨A, · , 1⟩ and ⟨A, +, 0⟩ form commutative monoids, with both operations being monotone with respect to ⪯ . Specifically, if ⪯ and ⪯ , then · ⪯ · and + ⪯ + . The implication operation ˓→ in a FL-algebra is defined as ˓ → = max{ | · ⪯ }. In this context, we refer to ∩ as meet, ∪ as join, ˓→ as Temperature (°C)
Humidity (%)
Wind (km/h)
21.1
22.2
implication, · as t-norm, and + as t-co-norm. A FL-algebra is termed linearly ordered (or chain) if its
lattice order is total, standard if its lattice reduct is the real unit interval [
Given a FL-algebra A = ⟨A, ∩, ∪, · , +, 0, 1⟩ and a set of propositional letters , the formulas of ::= | | ∧ | ∨ | → , value () ∈ A, and, given a A-formula , its value ( ) is computed recursively as follows: where ∈ A and ∈ . A A-model 1 is a map from each propositional letter in ∈ to some truth ( ) = ( (
∧ ) = ( ) · ( ) ( ∨ ) = ( ) + ( )
→ ) = ( ) ˓→ ( ). are given in Fig. 1.
for both algebra values and symbols to represent them.
The Boolean two-element algebra B is a simple example of FL-algebra; the propositional B-logic is the classical propositional logic, and its semantics reduces to the obvious one. Another setting of [1, . . . , ] ⪯
[1, . . . , ] if and only if, for every , ≤ interest for us, given a natural number , is the FL-algebra A = ⟨A ⊆ , 0 = [0, . . . , 0], and 1 = [1, . . . , 1]. The
R, ∩, ∪, · , +, 0, 1⟩, where operators · and + are left unspecified; they, as well as the value of and the cardinality of A will be treated as parameters. We call the propositional A-logic many-expert propositional logic. Fixed a model , an algebra A, and a formula , we write A( ) to denote the value of assuming A as an algebra; so, for example, for a model and formula we have that B( ) = 1 is an alternative notation for |= , where |= is the classic symbol for propositional satisfaction. Examples of lattice structures
values of attributes = {1, . . . , }.
Definition 1.
A dataset is a set of instances ℐ = {1, . . . , }, each one of which is described by the ℐ, supervised classification Without loss 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 with a label (or class) ∈ ℒ and a dataset is termed labeled. Given a labeled dataset consists of synthesizing an algorithm (a classifier ) that is able to classify example of a dataset can be found in Tab. 1. the instances of an unlabelled dataset whose instances are defined on the same set of attributes. An 1In the following, the symbol is also used to denote an instance; this is intentional, as in the symbolic context instances are seen as logical models.
Temperature>23.9
Humidity≤ 70
In the symbolic context, instances are seen as logical models. To help this interpretation, one takes into consideration that datasets are naturally associated with a logical vocabulary of propositional letters, from which formulas are built. A simple choice for such a vocabulary is =
{◁▷ | ∈ R, ◁▷ ∈ {<, ≤ , ≥ , >}}.
Definition 2. Let ℒ be a set of classes, a finite set of propositional letters, and A an FL-algebra. A A-decision tree on ℒ and is an object of the type
= ⟨, , , ⟩, 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 . To each branch = 12 . . . ( ∈ , for every 1 ≤ ≤ ) in a decision tree is associated a branch-formula = (1) ∧ . . . ∧ (). Given an instance , is classified as ∈ ℒ by if and only if there exists ∈ such that its leaf is labelled by and that A( ) ⪰ A( ′ ) for every ′ ∈ , ′ ̸= . As it can be seen, a decision tree is a syntactical object. In the following, we simply use the term decision tree (DT) to denote a B-decision tree, that is, a classical propositional decision tree. Also, a fuzzy decision tree (FDT) is an A-decision tree for some standard FL-algebra A. Finally, a many-expert decision tree (MEDT) is a A-decision tree. An example of decision tree can be found in Fig. 2.
In the case of DTs, the decisions that label two outgoing edges from the same node are always semantically opposite; in terms of the propositional vocabulary as we have defined it, this means that two edges outgoing from the same node are labeled, respectively, with◁▷ and ◁▷′, where ◁▷′ is < (resp., ≤ , ≥ , >) if ◁▷ is ≥ (resp., >, <, ≤ ).
Decision trees classify a certain instance by executing a model checking algorithm. In the case of classical DTs, checking a branch-formula can be performed by progressively checking, step-by-step, each of its individual propositions/decisions, which makes classification with DTs particularly eficient; this is no longer true upon generalising DTs to FDTs and then MEDTs, but eficiency of classification can be, at least partially, preserved.
MEDTs are obtained from DTs as the result of two generalisation steps. First, we introduce a mechanisms to soften individual decisions, obtaining, as a matter of fact, a FDT in the process; to this end, let us fix a standard FL -algebra A. Consider a dataset ℐ. In the classic setting, to the purpose of learning a classical DT , ℐ is randomly separated into two subsets ℐ, used in the learning phase, and ℐ, used to test . By adding a further division, that is, by separating, instead, ℐ into portion of the dataset, we take a first step into ℐ, ℐ, and ℐ, and using ℐ as a fine tuning ℐ ℐ1 . . . ℐ ℐ
1 5 10 15 20 25 avoiding typical overfitting phenomena. Keeping a portion of the data for fine tuning is a well-known strategy, sometimes applied for post-pruning purposes; as already proposed in the literature, we can use it for assigning a non-binary truth value to each proposition on the original tree. This can be obtained, after having learned a classical DT = ⟨, , , ⟩ from ℐ using any algorithm, as follows: () for every ∈ , we associate the set ℐ = { ∈ ℐ | B(◁▷) = 1} ⊆ ℐ , that is, the portion of ℐ ,◁▷, computed that falls into , to itself; () for every ∈ , we associate the normal distribution Φ, on the set to the decision ◁▷ that labels the edge between the parent of and itself; and () for every instance and decision ◁▷ we define A(◁▷) = Φℐ (′), where ′ is the value of in 2. Observe that now the value of A( ) can be computed for every branch ∈ .
Stepping from a FDT, as defined above, to a MEDT requires switching from (a standard) A to (a concretization of) A. In other words, to every instance and decision ◁▷ we need to associate a value A (◁▷), which is a vector of real values. To this end, we replace ℐ with a family 1, . . . , of fine tuning portions of datasets. Each one of them plays the role of an expert. Therefore, proceeding as above, for every instance and decision ◁▷ we compute A (◁▷) = [Φℐ1,◁▷,(′), . . . , Φℐ1,◁▷,(′)], where ′ is the value of in .
An example of DT->MEDT generalisation of the DT in Fig. 2 is shown, partially, in Fig. 3. Consider, in particular, the decision ≤ 23.9. In Fig. 3, right, we assume = 3, so that three diferent distributions for the portion of the fine tuning dataset whose instances show a value of less than or equal to 23.9 are computed.
As a final observation it is worth noticing that classification with MEDTs is not as eficient as it is with DTs: the exponentially many diferent many-valued formulas that occurr on the branches of a MEDT should be checked in full to classify each instance individually. The tree structure of a MEDT, however, allows for the implementation of sub-optimal classification strategies, such as, for example, progressively checking all branches up to a fixed height, and then focusing on the sub-tree rooted at the chosen node only.
A many-expert decision tree is a non-crisp decision tree based on many-valued logic. This model generalizes both crisp and fuzzy decision trees, and can be obtained as the result of a fine tuning step upon learning a standard decision tree. We intend to carefully design, implement, and test the MEDT model, and include it in an already existing, comprehensive, end-to-end open-source framework for symbolic learning and reasoning. 2Obviously, FDTs and MEDTs can be defined with any other membership function.