Rule Learning and Formal Concept Analysis (FCA) are two fields of science that study similar topic yet speak in a very diferent terms. This paper describes rule-based machine learning models with FCA-based terminology which results in decision quiver model. A decision quiver, discussed in the paper, is a supervised machine learning model that is based on intents, generators of intents, and predictions for each intent (or generator). We show that the finding of the optimal set of intents is a cornerstone task in constructing a decision quiver (and thus, any rule-based model). The paper finishes with the baseline algorithm to construct decision quivers. The algorithm produces machine learning models that are much smaller than the state-of-the-art ensembles of decision trees, yet that ofer the similar quality of predictions.
Rule Learning [
Rule learning is a mature and well-recognised research area mainly concerned with finding
the Boolean rules (i.e. ”rules”) from the given attributes that are able to predict the value of
“target” attribute. One specific configuration of a rule-based model – an ensemble of decision
trees – is considered among the state-of-the-art machine learning models on tabular data.
However, the last big increment in the prediction quality of the ensembles was introduced in the
year 2016 [
Formal Concept Analysis is a formalism aimed at analysing data based on discrete (often binary) descriptions. The FCA focus on binary descriptions promises its good applicability to become a formalism for rule-based models.
The natural connections between FCA and rule-based machine learning were covered in
many works: [
The paper is structured as follows. Section 2 recalls the basics of Formal Concept Analysis and Supervised Machine Learning, and defines Decision Quivers. Section 3 introduces the pipeline and the simple algorithm to construct decision quivers. Section 4 evaluates the algorithm on some of LUCS-KDD datasets. Section 5 concludes the paper.
This subsection introduces definitions we use throughout the paper. Firstly, we provide the basic terms of Formal Concept Analysis to describe the rule models. Secondly, we describe the space of premises that contains the machine learning models discussed in the paper. Thirdly, we describe the main topics of a binary classification in the language in the FCA notation.
In Formal Concept Analysis the data is represented as a formal context = (, , ) , which is a triple of a set of objects , a set of attributes and the relation ⊆ × among them.
A running example of a formal context is provided in Table 1 (together with “Target ” column and “test objects” rows that will be introduced in the following sections). To lighten the notation, we will represent a subset of attributes from the running example as a concatenation of these attributes: e.g. we denote the subset of attributes {, ℎ} as ℎ .
We call any subset of attributes ⊆ a description. And we denote the set of all descriptions (i.e. the powerset of ) as 2 :
2 = { ∣ ⊆ }
Now we can define two “prime” operations: ′ would describe all attributes shared by objects ⊆ , and ′ would describe all objects covered by attributes ⊆ . Prime operations:
Two prime operations, combined together, result in “double prime” operator (⋅)″ that has the properties of a closure operator. For example, if is a subset of attributes then ″ is the closure of on set .
′ = { ∈ ∣ ∀ ∈ ∶ (, ) ∈ }, ⊆ ′ = { ∈ ∣ ∀ ∈ ∶ (, ) ∈ }, ⊆ (1) (2) Attributes w x x x c x x x c ; ch dog,bream dog,corn, bream, egg h h x x x w cw chw
hw bream lives on land lives in water can move has limbs is mammal Running example of a formal context with additional target column and test objects (3) (4) Objects
Test objects
Attr. names bream dog corn egg reed frog dog,corn
l lc dog l x x x x lh lch tions of the empty set of objects are omitted.
″ = is also referred to as an intent. The set of all intent is denoted by and, together with set inclusion order, forms a lattice :
Line diagram on Figure 1 shows the descriptions of a context from the running from Table 1 grouped by the equivalence classes. Descriptions equivalent to (that describe no objects) are omitted as they would make the diagram harder to read.
In each equivalence class [], ⊆
, there is a single maximal description ″ = (also called closed description or intent) and possibly many minimal descriptions, that are called = { ⊆ ∣
″ = } [] = { ⊆ ∣ ″ = ″}.
Two diferent subsets of attributes , ⊆ , ≠ can describe the same set of objects ′ = ′ and, consequently, have the same closure ″ = ″ . Such descriptions are called equivalent. Equivalence class [] of description ⊆ is denoted as [] : “keys”. Let ⊆ equivalent to : be a closed description ″ = , then ()
is the set of minimal descriptions, () = { ∈ [] ∣ ∄ ∈ [] s.t. ⊂ }, ⊆ (5)
This subsection covers the basic ideas of Supervised Machine Learning and introduces our notation for these terms.
Let us define a formal context (, , ) , a space of target values , and a target label () ∈ for each object ∈ . The task of supervised machine learning is to find a function that maps any description ⊆ to a target value ( ) ∈ so that, for any object ∈ , the prediction ( ′) would be close to the target label () . The “closeness” of target labels and predictions on objects is evaluated by non-negative loss function ℒ ( , ∣ ) ∈ ℝ +, where ℒ ( , ∣ ) = 0 means that is optimal. Here we provide two loss functions that can be used to evaluate the prediction function : negative F1-score ℒ 1 for binary classification task (i.e. when = {0, 1} ), and Mean Squared Error (MSE) ℒ for regression task (i.e. when = ℝ ).
ℒ 1 ( , ∣ ) = 1 − 2 ℒ ( , ∣ ) = ∑ ( () − (
′))2 1 || ∈
∑∈ () ( ∑∈ (1 − () ( ′) ′))
It should be noted that, since the loss function ℒ is evaluated on objects , the “best” prediction function for these objects would be the function ∶ ′ ↦ () that predicts the label () of every objects ∈ based on its description ′. Such function would give zero loss on objects but it will not extrapolate well on new descriptions, not shared by objects . This issue is often mitigated by introducing the “test” formal context ( test, , test) with target labels test ∶ test → . Then, prediction function is constructed by minimizing the loss on “train” context (, , ) , but the final evaluation of the loss of function is done on the test context ( test, , test). In the running example from Table 1, objects test are denoted as Test objects.
In what follows we use the “average” operation over the target space (Equation 6). We assume,
therefore, that the space is “averageble”, i.e. for every list of tuple of target values , its average
avg( ) is also a target value from . This assumption does not make the following reasoning
too specific, as many Supervised Machine Learning problems can be reformulated to satisfy it.
For example, binary classification task suggests only two target values bin = {0, 1}. However,
it can be reformulated as a regression task with = [
avg( ) = 1 ∑ , ∈ | | ∈ 1 ∪ 2 ∪ … ∪ ∞ (6)
Given a description ⊆ , a rule-based machine learning model makes prediction ( ) based on a set of rules of the form: “if is described by ⊆ then predict ( ) ∈ ”. That is, every rule is characterised by a pair ( , ( )) where ⊆ is a subset of attributes called premise, and ( ) ∈ is a prediction of premise . A rule set is a pair ( , ) where ⊆ 2 is a set of premises and is a function that maps each premise to a target value ( ∶ ↦ ).
Now, let us consider two special cases when predicting with rule set ( , ) . Let ⊆ be a description and let 1, 2 ∈ be two comparable premises covered by : 1 ⊂ 2 ⊆ . Then we follow the intuition that a more precise premise 2 should give a more precise prediction ( 2), therefore we only use premise 2 to make a prediction about the target of . Now, let 1, 2 ∈ be incomparable premises, covered by : 1 ⊈ 2, 2 ⊈ 1, 1 ⊆ , 2 ⊆ . Then we use both premises 1, 2 to make a prediction for by averaging their predictions ( ) = avg((( 1), ( 2))).
With these ideas in mind we define prediction function ( ,) ∶ 2 → for rule set ( , ) as follows:
( ,) ( ) = avg((( ) ∣ ∈ where , max = { ∈ ∣ ⊆ , ∀ , max)), ⊆ 2 ∈ ∶ ( ⊂ 2) ⟹ ( 2 ⊈ )}
objects described by :
is often computed as the average of target labels of Example 1. Let us provide an example of a rule set ( , ) constructed on the example context 1. For the sake of readability, we represent the rule set as a set of implications { ⟹ ( ) ∣ ∈ } : {∅
⟹ 25%, ⟹ 50%, ⟹ 100%, ℎ ⟹ 100%, ⟹ 0%}.
Let us make a prediction for object reed with description = . There are three premises from that can be applied for : {∅, , } . Out of these three, there are two maximal descriptions: , max = {, } . The former predicts that reed is mammal with () = 50% probability, and the latter predicts that reed is mammal with ( ) = 0% probability. Therefore, the final prediction is ( ,) ( ) = 25% probability of reed being a mammal.
Analogously, let us predict whether object frog with description = ℎ is a mammal. All premises of can be applied for the given . However, only three of them are maximal: , max = {, ℎ, } . The corresponding premise predictions are () = 100%, (ℎ) = 100%, ( ) = 0% . Therefore, the final prediction is ( ,) ( ) = 67% probability of frog being a mammal.
This process of making predictions is schematically depicted in Figure 2.
( ) = avg(( () ∣ ∈
′)) X = lw PX;max fl; wg % (50%; 0%) avg.
25% = (P;%)(X)
X =lwchPX;maxflc; lh; wg % (100%; 100%; 0%) avg. 67%= (P;%)(X)
Let us rewrite the predictions from Example 1 in more details, considering what objects from we use to make predictions.
For object reed with description = the set contains two maximal premises describing : , max = {, } . Premise describes training objects ′ = {, } ⊂ with corresponding target labels () = 100%, ( ) = 0% whose average label is 50%. Premise describes training object ′ = { } ⊂ with target label ( ) = 0% . So the rule set ( , ) from Example 1 predicts that reed is mammal with 25% probability.
For object frog with description = ℎ the set contains three maximal premises describing : , max = {, ℎ, } . Premise describes training object ′ = {} ⊂ with target label () = 100% ; premise ℎ describes the same training object training object ′ = ′ = {} ⊂ with target label () = 100% ; and premise describes training object ′ = { } ⊂ with target label ( ) = 0% . So the rule set ( , ) from Example 1 predicts that frog is mammal with 67% probability.
This process of making predictions is schematically depicted in Figure 3.
X = lw PX;max fl; wg X = lwchPX;maxflc; lh; wg wl0h0 fdogg l0 fdog; corng w0 fbreamg lc0 fdogg (100%; 0%) avg. 50% avg.
(0%) (100%) avg. (100%) avg.
avg.
0% avg. 100% avg.
avg. 100% avg. 0%
Notice that two premises {, ℎ} ⊂ used for target prediction of object frog ( = ℎ ) have the same extent: ′ = ℎ ′ = {} . Therefore, the information that subset of objects {} has average target of 100% is used two times inside the rule set. In fact , if we count only one premise with extent {} dog when making the final prediction ( ,) we will get the value 50%, which is closer to the true value 0% than 67%.
There are many possible ways to overcome this issue. For example, one can construct rule set ( , ) such that the set would only contain premises that are either comparable or contradicting (i.e. ∀ 1, 2 ∈ ∶ 1 ⊆ 2 or 2 ⊆ 1 or ∃ ∈ 1, s.t. “not ” ∈ 2). This is the approach, used by decision trees. One can also construct rule set ( , ) such that the all premises in are closed (i.e. ⊆ ⊆ 2 ). Then, there will be no two premises that describe the same set of objects. This is the approach commonly used in FCA literature.
In this paper we propose another approach by enriching the rule set ( , ) with the set of closures ℬ of premises : ℬ = { ″ ∣ ∈ } .
The previous sections introduced equivalent descriptions and covered their importance for making predictions with rule sets. This section presents Decision Quiver: a rule set model enriched with the information about equivalent descriptions.
The model of Decision Quiver was introduced in [
Definition 1. Let (, , ) be a (training) context and be its set of closed descriptions, a decision quiver is a triplet = ( , ℬ, ) of premises ⊆ 2 , their intents ℬ ⊂ ∶ { ″ ∣ ∈ } = ℬ , and predictions ∶ ℬ → for every intent.
Given a description ⊆ , prediction ( ,ℬ,) ( ) is computed as the average of predictions of maximal intents ℬ , max ⊆ ℬ, whose generators ⊆ are covered by . ( ,ℬ,)
( ) = avg((() ∣ ∈ ℬ where ℬ , max = { ∈ ℬ ∣ ∃ ∈
, max)), , max s.t. =
″ ″, ∄ 2 ∈ , max s.t. ⊂ 2 } , max = { ∈ ∣ ⊆ , ∀ 2 ∈ s.t. ( ⊆ 2) ⟹ ( 2 ⊈ )} Example 2. Let us provide an example of a decision quiver ( , ℬ, ) having the same premises as a rule set ( , ) from Example 1. For the sake of readability, we represent the quiver ( , ℬ, ) as two sets of implications: { ⟹ ∣ ∈ , ∈ ℬ, ″ = } and { ⟹ () ∣ ∈ ℬ} : (11) (12) (13) → ℬ ∶{∅ ⟹ ∅, ⟹ , ⟹ ℎ, ℎ ⟹ ℎ, ⟹ ℎ }, ℬ → ∶{∅ ⟹ 25%, ⟹ 50%, ℎ ⟹ 100%, ℎ ⟹ 0%} = .
Contrary to the rule set ( , ) from Example 1, the quiver ( , ℬ, ) “knows” that premises and ℎ are equivalent as they correspond to the same closure ℎ . Therefore, when making prediction for a frog with description = ℎ , the quiver uses only two subsets of objects: {} = ℎ ′ with average target equal to 100%, and { } = ℎ ′ with average target equal to 0%. This prediction process is schematically represented on Figure 4.
X = lwch
lc00 lch PX;maxflc; lh; wg lh00 w00 chw % % 100% 0% avg avg 50% = (P;B;%)(X)
The previous section introduced target-based and arrow-based decision quivers. Now, let us discuss, how these quivers can be constructed.
Decision quiver = ( , ℬ, ) consists of three elements. Note that prediction function ∶ ℬ → depends on intents ℬ and not the premises . And considering the training formal context, every premise ∈ describes the same objects as itc closure ∈ ℬ, ″ = . So, when making predictions on the training context, the choice of a specific subset of premises is irrelevant. Therefore, the task of finding the optimal quiver ( , ℬ, ) on the training formal context reduces to finding the optimal rule set (ℬ, ) whose premises are limited to intents.
After finding (ℬ, ) one should select the optimal set of premises to construct a quiver ( , ℬ, ) that would be generalisable to the test data. However, since premises with the same intent describe the same objects, they are empirically indistinguishable. Thus, the choice of the premises relies on a priori intentions: for example, one may want to make premises as precise as possible (then = ℬ ), or as general as possible (then = ⋃∈ℬ () ).
More formally, let ℒ be a loss function, (, , ) be a training context, and opt = ( opt, ℬopt, opt) be the quiver, that achieves the minimal loss ℒ on the context (, , ) : ℒ ( , opt ∣ ) → 0 . Then, the task of finding such optimal quiver opt can be separated into three independent steps: 0. Fix the search space of intents search ⊆ of context (, , ) , 1. Find the optimal rule set (ℬopt, opt) of intents ℬopt ⊆ search and their predictions opt ∶ ℬopt → , 2. Construct the set of premises opt of intents ℬopt.
The initial step of the pipeline is fixing the search space search. For the sake of simplicity, in this paper we assign the search space search to be the space of all intents . The ways to minimise the search space is one of the future research directions.
The first and the main step of the algorithm is finding the optimal rule set (ℬopt, opt) where the choice of premises is limited to intents from the search space: ℬopt ⊆ search. Remind that the prediction function opt is often evaluated the same way for every intent. For example, similar to Equation 9, prediction opt() for an intent ∈ is the average target label of objects ′ described by intent . Thus, the search for optimal rule set (ℬopt, opt) is a search for optimal subset of intents ℬopt ⊆ search: ℬopt = arg
min ℬ⊆ search ℒ ( , (ℬ,) ∣ ) (14)
The last step of the pipeline is to construct the set of premises opt of quiver opt to generalise the latter to the possible test descriptions. Here we propose two options for the set of generators opt: the set of closed descriptions closed = ℬopt, and the set of keys keys = ⋃∈ℬ opt keys() .
This paper uses the very basic greedy discrete optimisation algorithm to find the optimal subset of intents (i.e. solving the task from Equation 14).
When finding the optimal subset of intents ℬopt ⊆ search we operate the fixed set training context (, , ) , the fixed targets ∶ → , and the fixed way to compute the prediction () for an intent ∈ search (see eq. 9). Therefore, for the sake of brevity, we define the training loss ℒtrain(ℬ) of a subset of intents ℬ as follows: ℒtrain(ℬ) = ℒ ( , (ℬ,) ∣ ). (15) The algorithm (to find
ℬopt given search): 0. Start with ℬ containing the top intent ℬ = {∅″}, 1. Find the intent opt ∈ search that gives the minimal loss, when added to the current set of intents ℬ: opt = arg min∈ search ℒtrain(ℬ ∪ {}) 2. Add intent opt to the set ℬ, 3. Repeat the steps 1, 2 while the set ℬ contains less than ℬmax ∈ ℕ elements and the loss decrease is higher than ∈ ℝ +: repeat until |ℬ| ≤ ℬmax, and ℒtrain(ℬ)−ℒtrain(ℬ∪{ opt})> .
The main limitation for the current algorithm is that considers the intents search space search
as the set of all intents . Therefore, we can only apply the algorithm on the datasets where
we can compute the intents . For the experiments we chose nine dataset from LUCS-KDD
repository [
The selected datasets give the task of multi-class classification. For example, Iris dataset asks to classify a flower into one of the three types (Setosa, Versicolour, and Virginica) based on its petal and sepal lengths and widths. We used F1 score with weighted averaging as a loss function so that it can be applied to all datasets with no adjustments.
For each dataset we fit a gradient boosting model provided by Sci-Kit learn [
Table 2 compares the test prediction quality of models on the selected datasets. One can see that the Gradient boosting models gave the best scores. However, in some cases, quiver models showed comparable decision quality: e.g. Iris, Congres, Breast, Flare datasets. Also, on this data, we see almost no diferences between quivers that make predict with intents and quivers that prediction with keys. The only dataset where the diference occurs is Zoo dataset. Currently, we cannot explain this fact as we assumed the diference would be much more apparent. So we should proceed with more profound studies comparing intents and keys as means for predictions.
Now, let us compare the sizes of the models, provided in Table 3. One can see that quiver models contain no more that 6 intents for all the datasets. While each gradient boosting consists of one hundred of decision trees. Note that each decision tree in each gradient boosting consist of many Boolean rules. In that regard, decision quiver model are more eficient, as they are able to achieve the similar prediction quality score with much lesser number of rules.
Dataset zoo iris ecoli congres breast ticTacToe flare led7 nursery
However, the better algorithm to construct decision quivers should be developed. As the current algorithm construct the quivers for too long. For example, on Nursery dataset, it took XGBoost 0.8 seconds to construct 100 decision trees, and it took decision quivers algorithm 19 minutes to select 5 intents.
In this paper we have presented decision quivers as a formalism for describing rule-based machine learning models. We showed that description quiver can describe any rule-based model. And, by incorporating closed descriptions, it can possibly suggest eficient algorithms to create more optimal machine learning models.
We have also presented a general pipeline to construct decision quivers. We showed that the most important part of the pipeline is finding the optimal set of intents. Thus, many FCA-based algorithm can be used to construct decision quivers. The current baseline algorithm for quivers construction is very slow, compared to the state-of-the-art models. However, it can produce much smaller models with the similar prediction quality.