Studies on Explainable Artificial Intelligence show that a model should be small in order to be human understandable. The restriction on the size of a model drastically reduces the space of possible solutions. Many rule learning models still rely on greedy algorithms for generating ensembles of decision trees. This paper discusses FCA-inspired mathematical and engineering techniques to eficiently find most optimal short binary classifiers, i.e., classifiers that consist of no more than three binary attributes and are optimal w.r.t. F1 score.
human understandable.
Studies on Explainable Artificial Intelligence show that a model should be small in order to be
Modern learning models such as Gradient Boosting over Decision Trees [
Besides making models highly explainable, restricting the size of model also drastically limits
the space of all possible models. Thus, one can search for a globally optimal model instead of
approaching locally optimal ones. This paper considers the models operating only up to three
binary attributes. In order to find an optimal model meeting these conditions, one should iterate
though all combinations of up to three given binary attributes. However, such brute-force
algorithm sufers from combinatorial explosion with the increasing number of attributes. This
paper dwells on both mathematical and engineering techniques based on Formal Concept
Analysis (FCA) [
The challenge of constructing simple logical models has been addressed in many areas of
previous research. In the early 1960s, the work on formal logic led to the inception of logical
can FCA do for Artificial Intelligence?”, FCA4AI 2022, co-located with IJCAI-ECAI 2022, July 23 2022, Vienna, Austria,
programming and rule-learning algorithms [
Another possible reason to develop and to use short models is that they make good benchmark for big black box models. Indeed, if a short model outputs the same prediction quality as a big black box then there is no interest in using the latter.
Extensive research shows that a man can operate with premises having no more three plus
minus one ideas in his head simultaneously [
The structure of the paper is as follows. Section 2 presents the theoretical background used throughout the paper. Section 3 describes the mathematical techniques for optimizing the algorithm by minimizing the number of required operations. Complementing this, Section 4 discusses the engineering approaches to optimize the algorithm by maximizing the computation speed. Section 5 merges all the discussed techniques together in one algorithm. And Section 6 presents the experimental results of this algorithm. Finally, Section 7 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.
A formal context describes the dataset to build the model on. It is presented as a triple = (, , ) where is a set of objects (rows in a dataset), is a set of attributes (columns in a dataset), and ⊆ × represents relations between objects and attributes.
Prime (′) operators match a subset of objects ⊆ and a subset of attributes such that the objects from are “described” by the attributes from and vice versa: ′ = { ∈ ∣ ∀ ∈ ∶ } ′ = { ∈ ∣ ∀ ∈ ∶ } (1)
Given a subset of attributes ⊆ , the subset of objects = the subset of attributes = ′ is called intent of . ′ is called extent of . Dually,
In this subsection we define a premise as a combination of attributes of a formal context, joined by conjunction, disjuction, and negation operations. The notion of a premise is necessary for the following subsections.
Definition 1.
The premise space ℙ is a set of all combinations of attributes constructed with conjunction ∧, disjunction ∨, and negation operations: ℙ is a set s.t.
1) ⊂ ℙ, 2)∀, ∈ ℙ ∶ ∧ , ∨ , ∈ ℙ (2) (3) (4)
Each premise ∈ ℙ corresponds to a subset of objects ′ ⊆ called an extent of a premise. Extents of conjunction, disjunction, and negation operations are defined as follows: ( ∧ ) ′ = ′ ∩ ′, ( ∨ ) ′ = ′ ∪ ′, ′ = ⧵ ′
This paper is specifically interested in premises consisting of no more than three attributes. Generally, a set of premises constructed from attributes can be described in the following way:
1 = ∪ { ∣ ∈ } >1 ⌊/2⌋ =1 ∈ℕ = ⋃ { ∧ , ∨ , ∧ , ∨ ∣ ∈ , ∈ − }
Uniting sets of premises for each natural number we obtain the premise space ℙ: ℙ = ⋃∈ℕ . In what follows, we say that premise ∈ ℙ has size if it belongs to .
Binary classification is a task in machine learning when a model is asked to predict whether an object belongs to a “positive” or a “negative” class given the object’s description (given by a subset of attributes). The model is obtained based on the provided training context (dataset) = (, , ) with predefined positive + ⊂ and negative − = ⧵ + objects. The first step to constructing a good binary classifier is to find a model operating the set of attributes that eficiently separates positive objects from + and negative objects from − . After that, the model can be applied to a test context = ( , , ) to predict its unknown positive and negative objects. objects − ∶ + = ′.
This paper studies binary classifiers of the form “if premise ∈ ℙ is true then object is predicted positive, otherwise object is predicted negative”.
The prediction quality of a premise ∈ ℙ on a training dataset is measured by comparing the given sets of positive + and negative objects − with the sets of positive + and negative predicted by a premise . Note that the set + is exactly the extent of the premise tpp | ′| () = , rec() = , F1() = 2 prec() ∗ rec() prec() + rec() tpp + ∗ = arg max 1()
3 ∈ ⋃=
This paper focuses on finding the premise ∗ of size not bigger that 3 having the maximal F1 score: 1() ∼ () = | + ∩ ′| | + ∪ ′| () = | + ∩ ′| | + ∪ ′| =
The definition of F1 score as a harmonic mean of precision and recall makes the possible optimization strategies obscure. This subsection simplifies the task of maximizing the F1 score through maximizing the number of true positives and true negatives. of objects predicted positive + = ′: Proposition 1. F1 score 1() is comonotonic to Jaccard score () (denoted by ∼), where the latter represents the Jaccard similarity coeficient between the set of positive objects + and the set = + ∩ + = + ∩ ′ = + ∩ − = + ⧵ ′ = − ∩ + = − ∩ ′ = − ∩ − = − ⧵ ′
For the sake of brevity, let us use lowercase letters to denote the cardinalities of so-called true positives , false positives , false negatives , and true negatives . Likewise, we use +, − to denote the cardinalities of the set of positive objects + and the set of negative objects − respectively: tp = | |, fp = | |,
fn = | |, tn = | |, + = | +|, − = | −|
One of the most widely used quality scores for binary classifications are precision ( recall ( ), and their harmonic mean called F1 score ( 1 ). Their definitions are as follows: Proof. Let us describe the Jaccard score in terms of true positives and true negatives : Now we should also express F1 score in terms of true positives and true negatives : 1() = 2 () ∗ () () + () = + + | ′| =
− ) + ( + ) || + − Therefore we obtain the relation: =
1 1 + () 1() ∼ () (11) (12) (13) (14)
Since F1 score 1() is monotonic with respect to the Jaccard score () then the F1 score optimization problem can be viewed as the problem of optimizing the fraction /(|| − ), i.e. maximizing the number of true positives and true negatives: arg max 1() = ∈ℙ arg max () = ∈ℙ arg max ∈ℙ
This subsection discusses how conjunction and disjunction operations afect the Jaccard score. That is, given the Jaccard score of two premises , ∈ ℙ can we expect that premises ∧ , ∨ would have higher or lower Jaccard score values?
Firstly, let us express the true positives and true negatives of premises constructed by conjunction and disjunction with the true positives and true negatives of the original premises: ∧ = + ∩ ( ′ ∩ ′) = ∩ ∧ = − ⧵ ( ′ ∩ ′) = ∪ ∨ = + ∩ ( ′ ∪ ′) = ∪ ∨ = − ⧵ ( ′ ∪ ′) = ∩
Therefore, conjunction operation shrinks the set of true positives while expanding the set of true negatives. Opposite to it, disjunction operation expands the set of true positives while shrinking the set of true negatives.
Now we derive the equations for the infimum and the supremum for the cardinalities of true positives and true negatives. To do so we incorporate two notions from Equation 13. Firstly, we use set cardinality restrictions for intersection and union operations. Secondly, since the number of true positives is limited by the number of positive objects +, then for two premises , ∈ ℙ if the sum of , exceeds +, then the corresponding true positives should have at least + − + objects in common (analogous conclusions can be provided for the number of true negatives and the number of negative objects −).
max( + − +, 0) ≤ ∧ ≤ min( , ) max( , ) ≤ ∧ ≤ min( + , −) max( , ) ≤ ∨ ≤ min( + , +) max( + − −, 0) ≤ ∨ ≤ min( , ) Thus, the Jaccard score bounds are:
Figure 1 visualizes the bounds on TruePositive-TrueNegative plane for an abstract formal context with 40% of objects being positive. Maximizing the Jaccard score, shown by increasing grey colour gradient, requires us to reach the upper-right corner of the plane. However, conjunction and disjunction operations over premises , ∈ ℙ can only “move” the premises to the upper-left ( ∨ ) and lower-right ( ∧ ) corners.
The bounds derived for conjunction and disjunction operations are vague: they do not say whether the newly formed premise would have the higher or lower Jaccard score. The more precise estimation is only possible via intersecting the extents of premises , . In this case, however, one can immediately compute the resulting Jaccard score itself, rather than operating the estimations. q J(q) = 0.25
sup: J(p ∧ q) = 0.37 Proposition 2. Given a threshold ∈ ℝ and a premise ∈ ℙ , one can identify whether the Jaccard score of any premise ∧ , ∨ ∈ ℙ
will not exceed the threshold using the following inequations: ≤ + ≤ || − + ⟹ ( ∧ ) ≤ , ∀ ∈ ℙ ⟹ ( ∨ ) ≤ , ∀ ∈ ℙ Proof. Let us describe how the bounds in formulae 15 depend on true positives and true negatives of a premise ∈ ℙ : Now we compare the obtained fractions with a threshold : Thus we result in the initial implications: + ≤ + ⟹ ( ∧ ) ≤ , ∀ ∈ ℙ ≤ || − ⟹ ( ∨ ) ≤ , ∀ ∈ ℙ (16) (17) (18) (19) (20) (21)
Mathematical tricks help to minimize the number of comparing rules. However, the number of such rules is still high. This section concentrates on engineering tricks to make each comparison faster.
In this subsection we use two important facts about concept extents: (i) diferent premises may correspond to the same extent ∃, ∈ ℙ ∶ ≠ , a premise relies on the premise extent ′ (see eq. 5).
Diferent premises , ∈ ℙ, ≠
may correspond to the same extent ′ = ′ ⊆ for many reasons. First, the premises can be logically equivalent: e.g. ( ∧ ) laws. Second, if one premise is less general than another ′ ⊂ ′ then their conjunction would correspond to the extent ′ and their disjunction would correspond to the extent ′. Lastly, diferent premises may correspond to the same extents due to the specific characteristics of the formal context : e.g. it may occur that an extent of the conjunction of two premises ′ = ( ∨ ) ′ by De Morgan , ∈ ℙ would be equal to the extent of the third premise ∈ ℙ ⧵ {, } ∶ ( ∧ ) ′ = ′. Since the ′ = ′, (ii) any prediction quality measure of computation of prediction quality measures relies on extents of premises, then many various premises corresponding to the same extent would have the same prediction quality (on the train context ).
Thus, we propose to search for the most optimal extent instead of the most optimal premise. In order to formalize this idea, let us define the sets extents : (22) (23) (24) 1 = { ′ ∣ ∀ ∈ 1} = ⋃ { ′, () ′} ∈ ⌊/2⌋ ∈ℕ = ⋃ { ∧ , ∨ ∣ ∈ >1 =1
−1 , ∈ − } ⧵ ⋃ =1
The proposed definition of the sets of extents ensures that any extent ∈ is generated by a premise of size at least :
Thus the optimization problem becomes as the following: ∀, ∈ ℕ, ∈ , ∈ ∶ = ′
⟹ ≤ ∗ = arg max 1()
3 ∈ ⋃=1 where F1 score function is slightly modified to take an extent as its parameter and not the premise.
The last but not the least, an extent , being a subset of objects , can be represented and stored in a computer as a bit mask (a tuple of bits) of length || where each bit represents whether the corresponding object is in the extent of not. Conjunction and disjunction operations become operations on bit masks, that are the most eficient operations performed of modern binary coded computers. So the use of extents instead of premises not only reduces the number of comparisons, it also highly accelerates each of the comparisons.
This subsections describes the trick, that is well-known among data science practitioners, however we should cover it for the full disclosure.
Inequalities, presented in Proposition 2, allow us to skip the processing of many conjunctions
∧ and disjunctions ∨ based on the characteristics of the initial premises , ∈ ℙ and a
prediction quality threshold . However, these characteristics are still to be computed. And
to compute these numerical characteristics the most eficiently we use Numpy [
Here is a pseudo-code of the algorithm for finding the best premises of size no bigger than 3: • Step 1. Find all extents of size 1 that will not lose quality after conjunction, disjunction: 1. Compute all extents 1; 2. Find the quality threshold as the minimal quality of the best extents from 1; 3. Filter out extents from 1 that satisfy both inequalities presented in Prop. 2; • Step 2. Find all extents of size 2 that will not lose quality after conjunction, disjunction: 1. Compute all extents 2 based on filtered set 1 while keeping the information about a pair of extents , ∈ 1 and an operation (∧, ∨) used for constructing each extent ∈ 2; 2. Find the quality threshold as the minimal quality of the best extents from 1 ∪ 2 3. Filter out extents from 1, 2 that satisfy both inequalities presented in Prop. 2 • Step 3. Find only the best extents of size 3:
For each pair of extent 1, 2 from filtered 1, 2 1. If any of the extents 1, 2 satisfy both inequalities in Prop. 2 then proceed to the next pair; otherwise: 2. Compute and measure the prediction quality of the conjunction 1 ∩ 2; 3. Compute and measure the prediction quality of the disjunction 1 ∪ 2; 4. Update if needed; • Step 4. Reconstruct the premises corresponding to the best extents
using the kept information about extents and operations.
The time complexity of this algorithm is (| | 3) where is a set of attributes in a formal context . From the asymptotic point of view, this is the same time complexity as that of the brute force algorithm to test all premises of size not bigger than three. However, the use of extents, as well as reducing the number of combinations, allows us to minimize the practical processing time of the algorithm.
This section applies the proposed algorithm in practice. First, we study the statistics of the number of comparisons the algorithm has to make. Second, we roughly compare the prediction quality of short models with that of the black box model to show that there are cases where the former performs as eficient as the latter.
The algorithm is run on a real-world Myocard dataset [
Table 1 shows that the use of bounds from Prop. 2 does not filter out many extent combinations. For example, for the premise size of 3, the bounds filter only 21.5% of extents combinations (from 1.49e+09 to 1.17e+09). Although such percentage is better than nothing, it still requires to test 1.17 billions extent combinations. However, the use of bit arrays allows us to test 1.17 billions of extent combinations in only 1 hour on a laptop with 8 GB of RAM.
Legend for Table 1: • # premises: number of premises of a given size; It is the combinatorically computed maximal amount of iterations of the algorithm; • # ext. combinations: number of extent combinations resulting in a premise of a given size; • # ext. combs. to test: number of extent combinations that can result in a good prediction quality (filtered by Prop. 2); • # new extents: the number of newly generated extents resulted from testing extent combinations; • # extents to keep: the number of extents to keep in memory. For size 1 and 2 we keep all the extents, for size 3 we keep only the extents with high prediction quality; • computation time: the time it took to process all combinations for a given premise size.
The simplicity of short rule models allows us to fully describe some of the obtained models in the paper. The following list provides the best short models (w.r.t. F1 score defined in a standard way for a binary classification method) obtained on Myocard dataset: • Premise size 1: F1 score = 0.401426
Premise: There is data about the use of painkillers in intensive care unit in the third day of the hospital period • Premise size 2: F1 score = 0.448819
Premise: (a person had a chronic heart failure) OR (has diabetes mellitus in the anamnesis) • Premise size 3: F1 score = 0.473786
Premise: (has data on use of opioid drugs in the intensive care unit in the third day of the hospital period) AND ( (Had Chronic heart failure) OR (Age ≥ 66) ) • XGBoost model: F1 score = 0.464000
The model contains 100 decision trees of max depth 6 • CatBoost model: F1 score = 0.434783
The model contains 1000 decision trees of depth 6 We can also show all the obtained short rule models on TruePositive-TrueNegative space. Premise si e 1 Premise si e 2 Premise si e 3 XGBoost CatBoost 1190 1y3−06 TrueNegative iey+,394 v t iso 340 P e u rT 255 170 85 0 0 170 340 510 680 850 1020
In this paper we have presented some preliminary results on finding the most optimal rule with antecedent consisting of no more than three binary attributes. We described the F1 score optimization task in terms of true positive and true negative predictions. We computed upper and lower bounds on Jaccard coeficients for premises obtained with conjunction and disjunction operations. We also covered FCA-inspired technique of iterating over extents of premises in order to minimize the computation runtime.
In the following studies we plan to develop sharper lower and upper bounds on Jaccard score for premises constructed with conjunction and disjunction operations. We also plan to discuss other logical operations that will increase the prediction quality of rules keeping the number of used attributes the same.
The article was prepared within the framework of the Basic Research Program at HSE University, RF.