Generalizing conjunctive and disjunctive rule learning to learning m-of-n concepts

Abstract

Most rule learning algorithms learn rule concepts as conjunctions and disjunct them afterwards to rule sets, a few others swap the order of conjunction and disjunction so that rule concepts are learned as disjunctions. Depending on the domain, both approaches can have advantages or disadvantages in comparison to its counterpart. Instead of learning rule concepts only as conjunctions or only as disjunctions, one can also flexibly choose between these two representations. One way to do so is by using m-of-n concepts where m of conditions must be true in order for the expression to be true. This not only covers the two extreme cases where all conditions must be true (n-of-n, conjunctions) or any of them must be true (1-of-n, disjunctions) but also a smooth transition for other values of m, analogous to a customizable activation threshold in neural networks. In this paper, we discuss possibilities how to eficiently learn m-of-n rules using similar generalization and specialization operations as for conjunctions or disjunctions. Furthermore, we adjust the state-of-the-art rule learning algorithm LORD to learn m-of-n concepts instead of plain conjunctions and present an evaluation of the technique on artificial and real-world data sets.

Keywords

• eol>rule learning
• constructive induction
• m-of-n concepts

1. Introduction

transforming weights and node activations into rules that are easier to understand [ 2 ][ 3 ][ 4 ]. Moreover, these exWhile most rule learning algorithms stick to learning flat tracted rules often generalize better to examples not seen concepts as logical combinations of features, many re- during training than rules produced by "all-symbolic" rule cent approaches — most notably neural networks — use refinement algorithms [ 2 ]. Additionally, there has also threshold concepts instead. In threshold concepts, the been work on how these extracted rules can be unified contained features are associated with diferent weights, to obtain a smaller and potentially easier understandable and not necessarily all of them have to be present in order rule set [ 5 ]. to pass the threshold. This leads to more flexible repre- One of the few approaches that directly integrate msentations than in rules, where all features contribute of-n concepts in a rule learner is Neither-MofN [ 6 ]. In equally and a concept is fulfilled if all features are present comparison to its counterpart algorithm that does not (conjunctive rule) or any of the features is present (dis- use m-of-n concepts, it was able to generate less complex junctive rule). theories because it could directly modify threshold val

A smooth transition between the two approaches is ues rather than create new rules. By adding one more provided by m-of-n concepts: Of a given set of fea- operator to the generalization and specialization protures at least have to be present to fulfill the concept. cesses, Neither-MofN was able to accurately revise a theOne of the most well-known usages of m-of-n concepts ory known to be dificult for symbolic systems, without in symbolic approaches was in the domain of decision having to sacrifice the eficiency of a symbolic approach trees, namely by ID-2-of-3, which integrates m-of-n dis- [ 6 ]. criminators and could outperform standard decision tree In this paper, we further investigate into this increinduction in some domains while also providing smaller mental rule learning technique, using m-of-n concepts in trees [ 1 ]. the form of Boolean expressions within a state-of-the-art

In the area of rule learning, m-of-n concepts are mostly rule learner. Our goal is to analyze the performance of used when extracting concepts from neural networks and the learner using m-of-n-concepts in comparison to conventional rule learners, with the long-term perspective of using m-of-n concepts as modules in more sophisticated, $ [e-mail] (F. Beck); [e-mail] (J. Fürnkranz); deeper rule learners. [e-mail] (V. Q. P. Huynh) The remainder of the paper is organized as follows: Sec(J. F0ü0r0n0k-0r0a0n3z-)3183-2953 (F. Beck); 0000-0002-1207-0159 tion 2 describes how m-of-n concept can be represented © 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License and learned. Based on this, in Section 3, we propose a CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org)

2. M-of-n concepts

M-of-n concepts, also known as criteria tables, are the

simplest form of threshold descriptions, without any feature weights involved [7, Chapter 3]. They consist of a set of Boolean features and a threshold between 1 and . If for a given example of the features are true, this example is a positive instance of the concept.

M-of-n concepts can be written as linear combinations, e.g. + + ≥ 2, or in the form 2 of [, , ]. In this paper, we will use the latter notation.

Learning m-of-n concepts Similar to conventional rules, m-of-n concepts can be learned by starting with an arbitrary feature subset (e.g. [, , ]) and a threshold between 1 and (e.g. 2). Afterwards, this concept can be generalized and specialized by adding or removing features or by adjusting the threshold. Typical incremental algorithms (e.g. [ 1 ][7, Chapter 3]) use the following two generalization operations to learn m-of-n concepts: • add a feature,

e.g. 2 of [, , →]− 2 of [, , , ] • remove a feature and decrease ,

e.g. 2 of [, , →]− 1 of [, ] Accordingly, the specialization operators are: • remove a feature,

e.g. 2 of [, , →]− 2 of [, ] • add a feature and increase ,

e.g. 2 of [, , →]− 3 of [, , , ] novel rule learning algorithm using a dynamic program- Table 1 ming approach to compute m-of-n concepts eficiently, Dynamic programming approach to compute m-of-n concepts and test it in Section 4. Finally, the results are concluded as Boolean expressions. For the concepts 2-of-3, 2-of-4 and in Section 5, and future ideas are discussed in Section 6. 3-of-4, at the top the representation in DNF and at the bottom the shorter representation computed by dynamic programming is shown.

n be rewritten as (a ∧ b) ∨ [(a ∨ b) ∧ c], which requires one literal and one conjunction less. However, even more important than reducing the number of literals and conjunction or disjunction operations is the fact that these representations can reuse representations with smaller and . Hereby, the general idea is to distinguish between two cases, how a given m-of-n concept can be fulfilled: (a) Either among the first − 1 features already are true or (b) among the first − 1 features − 1 are true, and the last feature is true as well. Thus, this representation can be generated by the following recurrence system: (, ) = ⎧true ⎪ ⎪⎪⎨false ⎪(, − 1)∨ ⎪ ⎪⎩[( − 1, − 1) ∧ ] else if m=0 if m>n (1)

These generalization and specialization operations are

minimal; i.e. all other operations can be achieved by chaining these operations together. For example, the generalization of decreasing the threshold by 1 just combines both minimal generalization operations:

Note that there are two ways how the recurrence ter

minates: If no more feature needs to be fulfilled, i.e. if = 0, this m-of-n subconcept is always true. Analo• 2 of [, , →]− 2 of [, , , →]− 1 of [, , ] gously, if more features need to be fulfilled than exist in a concept, i.e. if > , this m-of-n subconcept is always M-of-n concepts as Boolean expressions. M-of-n false. concepts can also be formulated as Boolean expressions. If applied recursively, most "subexpressions" will apE.g., they can be expressed in disjunctive normal form pear multiple times in the recursion — the subprob(DNF) in a straightforward way, by listing all (︀ )︀ pos- lems to be solved are nested. E.g., ( − 1, − 2) sibilities to build a conjunction of of features, and appears as the first term in the recurrent formula for disjunct all these conjunctions. The length of this DNF ( − 1, − 1) and also as the second term in the is then (︀ )︀ * . recurrent formula for (, − 1). We can make use

An even shorter form with less literals can be achieved of dynamic programming to cope with these reoccurring if the representation is not limited to two layers. Using subproblems. the distributive law, e.g. (a ∧ b) ∨ (a ∧ c) ∨ (b ∧ c) can Table 1 gives an overview how the dynamic programming approach can be used to generate the shorter Boolean representation for the values , ∈ [1..4] and sample features 1 = , 2 = , 3 = , 4 = according to recurrence system 1. Note that for = 1 the expression is a flat disjunction and for = a flat conjunction. These are the two border cases before the most general concept "all true" ( = 0) or the most specific concept "all false" ( > ) are reached.

In the remaining three cases, first the (longer) DNF and below the recursively computed expression are listed. For example, the recursively computed expression for = 2, = 4 consists of the expression for = 2, = 3 (5 literals), and disjuncts this with the conjunction of the expression for = 1, = 3 (3 literals) and 4 = (1 literal). end if chosen_feature ̸= null then

remaining_features.remove(chosen_feature);

Algorithm 1: search_best_greedy_rule()

Input: example, metric, all_features, n_lists

Output: concept 1 best_rule.body ← []; 2 best_rule.heuristic ← -∞; 3 remaining_features ← example.features; 4 while true do 5 m ← best_rule.m; 6 new_rule, chosen_feature ← modify_rule(best_rule, remaining_features, example.class, metric, n_lists, m); if new_rule = null then

break; 7 8 9 10 11 12 end 13 best_rule ← new_rule; 3. Algorithm 14 end 15 remaining_features ← features ∖ best_rule.body; To evaluate the presented approach of recursively gener- 16 while true do ating m-of-n concepts, we will adjust Lord [ 8 ], a novel 17 m ← best_rule.m - 1; rule learner developed in our group. Regularly, Lord 18 new_rule, chosen_feature ← learns one conjunctive rule for each training example modify_rule(best_rule, remaining_features, and groups them (including some filtering) to a DNF rule example.class, metric, n_lists, m); set which is used for classification. In its extended ver- if new_rule = null then sion, Lord should be capable to learn an arbitrary m-of-n break; concept per training example instead. 19 20 21 end 22 if chosen_feature ̸= null then 23 remaining_features.remove(chosen_feature); Data structures in Lord. Lord builds upon data struc- 24 end tures that are well-known in association rule learning, 25 best_rule ← new_rule; namely PPC-Trees1 and n-Lists. The main idea is that 26 end only a single pass through the training data is required 27 return best_rule; during the learning phase. This pass is used to create the PPC-Tree where each path corresponds to a (unique) example. Afterwards, n-Lists can be used to determine one feature contained in the body as long as it further which parts of a tree are afected by a given Boolean improves the heuristic. expression — and therefor how many positive and neg- For the m-of-n version of Lord, we use the same ative examples are covered for a learned rule. N-lists greedy search approach. We start with an empty rule can be combined particularly eficiently by conjunctions body and = 0 and specialize it by either adding a but can be combined by disjunctions as well. Detailed feature and increasing or by removing a feature. Afinformation about these data structures are given in [ 9 ], terwards, by either removing a feature and decreasing and about their application in the Lord algorithm in [ 8 ]. or by adding a feature, the rule can be generalized. Thus, while the order of specialization and generalization reGreedy rule search. Lord greedily learns one con- mains the same as in regular Lord, the rule body can be junctive rule for each training example. It starts with an grown and pruned in both phases of the algorithm. empty rule body and specializes it by greedily adding Algorithm 1 shows the mentioned approach in pseuone feature at a time to it, always picking the feature docode. Lines 1-2 create an empty new "0-of-[]" concept with the maximum gain w.r.t. a given rule heuristic until with the worst heuristic, which is afterwards first specialno improvement is possible. The set of features is lim- ized (lines 3-14) and then generalized (lines 15-26). Note ited by the concerned example to ensure that it remains that there are only two small diferences between these covered with any tested specialization. In a second step, two blocks: Firstly, during the specialization, only the Lord tries to prune these rules by repeatedly removing features of the training example are considered while during the generalization all features (except those already contained) are considered. Secondly, the two phases call

1<pre, post>-code-Trees; the code is determined for each node after

a preorder and postorder traversal

Algorithm 2: modify_rule()

Input: best_rule, remaining_features, example.class, metric, n_lists, m

Output: new_rule, chosen_feature 1 chosen_feature ← null; 2 n_list_class ← n_lists.get("1 of " + [example.class]); 3 for feature ∈ remaining_features do 4 ext_body ← best_rule.body ∪ feature; 5 n_list ← get_n_list(n_lists, ext_body, m+1); 6 n_p ← n_list.support; 7 p ← conj(n_list, n_list_class).support; 8 n ← n_p - p; 9 heuristic ← metric.evaluate(p, n); 10 if best_rule.heuristic < heuristic or best_rule.heuristic = heuristic and best_rule.p < p then 11 best_rule ← Rule(ext_body, example.class, m+1, p, n, heuristic); chosen_feature ← feature; 12 13 end 14 end 15 if best_rule.body.length > 1 then 16 for feature ∈ best_rule.body do 17 prun_body ← best_rule.body ∖ feature; 18 n_list ← get_n_list(n_lists, prun_body, m); 19 n_p ← n_list.support; 20 p ← conj(n_list, n_list_class).support; 21 n ← n_p - p; 22 heuristic ← metric.evaluate(p, n); 23 if best_rule.heuristic < heuristic or best_rule.heuristic = heuristic and best_rule.p < p then 24 best_rule ← Rule(prun_body, example.class, m, p, n, heuristic); 25 end 26 end 27 end 28 return best_rule, chosen_feature;

Algorithm 3: get_n_list()

Input: n_lists, body, m

Output: new_rule, chosen_feature 1 n_list ← n_lists.get(m + " of " + body); 2 if n_list ̸= null then 3 return n_list; 4 end 5 n_list ← n_lists.get("1 of " + [body[body.length-1]]); 6 if m > 1 then 7 n_list ← conj(n_list, get_n_list(n_lists,

body[0..body.length-2], m-1)); 8 end 9 if body.length > m then 10 n_list_2 ← get_n_list(n_lists,

body[0..body.length-2], m); 11 end 12 if n_list.support > 0 and n_list_2.support > 0 then 13 n_list ← disj(n_list, n_list_2); 14 else if n_list.support = 0 then 15 n_list ← n_list_2; 16 n_lists.put(m + " of " + body, n_list); 17 return n_list; tion, which also has access to the total number of positive ( ) and negative examples ( ) to determine a heuristic for the rule. The rule with the best heuristic — if tied, the one with more positive examples covered — is returned, optionally with the feature added in case the rule was extended.

Finally, Algorithm 3 demonstrates how n-Lists are fetched from storage if available and otherwise computed recursively. Parameter n_lists is prefilled with n-Lists for every single feature (including class features), these will be retrieved immediately (line 5, also line 2 in algorithm 2). If no border cases or empty n-Lists occurz, the recurrent formula is applied so that recursive n-Lists are computed (lines 7 and 10) and combined by disjunction (line 13). All intermediate n-Lists are stored for future calls before the final n-List is returned. the method modify_rule with a diferent parameter set in lines 5 and 17 respectively.

Evaluation. While Lord generates a filtered rule tree

Dynamic programming of n-lists. Algorithm 2 in the classifier where the best covering rules for a test shows the starting point for the top-down dynamic pro- example can eficiently be extracted from, this is unfortugramming approach to evaluate m-of-n concepts efi- nately not possible for arbitrary m-of-n concepts that are ciently. Lines 3-14 show the procedure for growing the not limited to conjunctions. Instead, all rules learned durrule, lines 15-27 for pruning the rule. The decisive factor ing the training phase are sorted by their heuristic and for whether these operations are generalizations or spe- iterated from best to worst whether they cover a given cializations is parameter , which is passed to the n-List test example. Because both the features in the example computation method get_n_list in lines 5 and 18. and also the features in the m-of-n rules are sorted, these

After the n-List is computed or retrieved, both its sup- two feature lists can be iterated parallel while counting port (lines 6 and 19) and the support of its conjunction the matching features. The coverage check can stop early with the predictive class (lines 7 and 20) is used to de- if the value is already reached (return predictive class termine the number of positive () and negative covered of m-of-n rule) or if can not be reached anymore (conexamples (). These values are used in the metric func- tinue with next rule). [(c1=4),(c3=4),(c2=4),(c4=4)]->(class=1) (p=884.0, n=0.0, m=2/4, heuristic_value=0.9981981688891336) [(c1=1),(c2=1),(c3=1),(c4=1)]->(class=1) (p=884.0, n=0.0, m=2/4, heuristic_value=0.9981981688891336) [(c2=5),(c4=5),(c1=5),(c3=5)]->(class=1) (p=884.0, n=0.0, m=2/4, heuristic_value=0.9981981688891336) [(c1=6),(c4=6),(c2=6),(c3=6)]->(class=1) (p=884.0, n=0.0, m=2/4, heuristic_value=0.9981981688891336) [(c2=2),(c3=2),(c1=2),(c4=2)]->(class=1) (p=884.0, n=0.0, m=2/4, heuristic_value=0.9981981688891336) [(c3=3),(c4=3),(c1=3),(c2=3)]->(class=1) (p=884.0, n=0.0, m=2/4, heuristic_value=0.9981981688891336) [(c1=1),(c1=4),(c1=6),(c2=1),(c2=2),(c2=5),(c3=2),(c3=3),(c3=4),(c4=3),(c4=5),(c4=6)]->(class=0) (p=480.0, n=0.0, m=4/12, heuristic_value=0.9970977726611563) [(s1=2),(s2=2),(s3=2),(s4=2)]->(class=0) (p=360.0, n=0.0, m=4/4, heuristic_value=0.9961383586648443) [(s1=1),(s2=1),(s3=1),(s4=1)]->(class=0) (p=360.0, n=0.0, m=4/4, heuristic_value=0.9961383586648443) [(c1=1),(c1=4),(c1=6),(c2=1),(c2=5),(c3=3),(c3=4),(c4=3),(c4=5),(c4=6),(c4=2)]->(class=0) (p=288.0, n=0.0, m=4/11, heuristic_value=0.9951829010149089) ...

4. Experiments

pairs of 1s in the first two cards are retained for the test set, all other pairs of 1s are in the training set. As a

For the artificial data set, we use a special split between consequence, state-of-the-art DNF rule learners like Lord training and test set, for the real-world data sets, we use are only capable to detect these five pair combinations ten-fold-cross-validation instead. For all experiments, and will miss the last possible combination since they we use the m-estimate metric and tested eight diferent are not able to generalize well enough. values between 0 and 100. The m-estimate value ℎ of Figure 1 shows the best ten rules learned by m-ofa rule predicting class has been proposed by Cestnik n Lord. Independent of the chosen value of m for the [ 10 ] and is calculated as m-estimate, the first six rules are the optimal pair descriptions of the positive class. The algorithm detected the ℎ() = . + + , (2) four relevant "rank"-features for each rank {1..6} and . + . + correctly learned that if at least two these are true, the where example will be positive. Thus, it could also generalize to the missing pair that was only available in the test set. = a settable parameter in the range [0, +∞) The m-of-n concepts learned for the negative class are . = the number of true positives of rule interesting as well. Two of them are short and easy to . = the number of false positives of rule understand: If four of four cards have the same suits, = the number of examples with class = no pair can occur since we did not include duplicates. = the number of examples with class ̸= . The remaining two are harder to grasp and result from the special split of training and test set: Since four of the eleven/twelve features have to be true, all ranks are Artificial data set. For the first part of the experi- preselected of those among the features, and the only ments, we reused a variant of the pairs data set pre- pairs that can be built are those retained for the test set sented in an earlier paper [ 11 ]. Each example consists (e.g. 1 = 1 and 2 = 1). of four cards, which in turn consist of a rank (ace, 2, 3, ..., queen, king) and a suit (clubs, spades, hearts, dia- Real-world data sets. The second part of the expermonds). Each card is therefor defined by a unique rank- iments was executed on real-world data sets. We used suit-combination, e.g. "spades 7". In this paper, we use a the same 29 UCI data sets as [ 12 ] and compared m-of-n smaller numeric subset of two suits {1, 2} and six ranks Lord with the DNF rule learner regular Lord and the {1..6} to obtain 12 diferent cards, and generate all 11,880 CNF rule learner k-CNF [ 12 ]. Surprisingly, m-of-n Lord combinations as examples. All examples where at least could not compete at all with the other two rule learntwo of the ranks are equal, i.e., they contain a pair, are ers. Compared with regular Lord, it lost on 24 data sets, assigned to the positive class, all others to the negative tied on 3 and won on 2, with an average accuracy diferclass. ence of 3 percentage points, independent of the choice

The negative examples are distributed evenly between of parameter m for the m-estimate. training and test set. However, for the positive examples, Simple adjustments to the algorithm like ending with we always pick one diferent pair combination for each an additional specialization iteration or starting with a rank that is hold back for the test set. For example, all most-specific rule and first generalizing and then specializing it, did not increase the accuracy remarkably and generally even performed worse. Interestingly, ignoring the generalization step completely improved the performance on many data sets but also worsened its performance on the pairs data set drastically. This generalization step was also needed to achieve a promising performance on the similarly structured monks-2 benchmark data set: m-of-n Lord achieved 93% accuracy — 30% more than conventional rule learners.

5. Conclusion

In this paper we analyzed m-of-n concepts as a generalization of the logical conjunctive and disjunctive concepts learned by most state-of-the-art rule learners. We proposed a novel dynamic programming approach to learn m-of-n concepts as Boolean expressions, and use this technique to extend the rule learner Lord to learn mof-n concepts as well. This learner reliably found the generalized model for the pairs data set, which can not be learned by state-of-the-art rule learners. However, it could not achieve a similar performance like these rule learners on general real-world data sets, so that a more sophisticated design of the algorithm is needed in the future.

6. Future Work

An even more general representation than m-of-n con

cepts are scoring systems, which assign a weight to every of the features and have a flexible threshold that is usually greater than . This form is even closer to perceptrons and can therefor be extracted even easier from neural networks.

However, scoring systems can also be generated in two possible ways in Boolean expressions. For example, to learn a scoring system with features [, , ], weights [ 2, 1, 1 ] and a threshold of 3, m-of-n concepts can still be helpful. If generalization and specialization operations are allowed to also add features that are already contained in the concept again, we can use the generalization 2 of [, , ]→− 3 of [, , , ] to obtain the mentioned scoring system. This can already be achieved by slightly adjusting Algorithm 1 to ignore remaining_features completely.

Another option to emulate "weightings" in Boolean expression are nested structures. M-of-n concepts could be learned in multiple layers, so that for the given example the deep concept 2 of [, 1 of [, ]] could be found.

References

[1] P. M. Murphy , M. J. Pazzani , Id2 -of-3: Constructive induction of m-of-n concepts for discriminators in decision trees , in: Machine learning proceedings 1991, Elsevier , 1991 , pp. 183 - 187 .

[2] G. G. Towell , J. W. Shavlik , Extracting refined rules from knowledge-based neural networks , Machine learning 13 ( 1993 ) 71 - 101 .

[3] R. Setiono , Extracting m-of-n rules from trained neural networks , IEEE Transactions on Neural Networks 11 ( 2000 ) 512 - 519 .

[4] S. Odense , A. d'Avila Garcez, Extracting m of n rules from restricted boltzmann machines , in: Artificial Neural Networks and Machine Learning-ICANN 2017: 26th International Conference on Artificial Neural Networks, Alghero, Italy, September 11-14 , 2017 , Proceedings, Part II 26 , Springer, 2017 , pp. 120 - 127 .

[5] F. Maire , A partial order for the m-of-n ruleextraction algorithm , IEEE Transactions on Neural Networks 8 ( 1997 ) 1542 - 1544 .

[6] P. T. Bafes , R. Mooney , Symbolic revision of theories with m-of-n rules , 1993 .

[7] P. Langley , Elements of machine learning , Morgan Kaufmann, 1996 .

[8] V. Q. P. Huynh , J. Fürnkranz , F. Beck , Eficient learning of large sets of locally optimal classification rules , Machine Learning 112 ( 2023 ) 571 - 610 .

[9] Z.-H. Deng , S.-L. Lv , Prepost+: An eficient n-listsbased algorithm for mining frequent itemsets via children-parent equivalence pruning , Expert Systems with Applications 42 ( 2015 ) 5424 - 5432 .

[10] B. Cestnik , Estimating probabilities: A crucial task in Machine Learning , in: L. Aiello (Ed.), Proceedings of the 9th European Conference on Artificial Intelligence (ECAI-90) , Pitman, Stockholm, Sweden, 1990 , pp. 147 - 150 .

[11] F. Beck , J. Fürnkranz , P. H. V. Quoc , On the incremental construction of deep rule theories , in: L. Ciencialová , M. Holena , R. Jajcay , T. Jajcayová , F. Mráz , D. Pardubská , M. Plátek (Eds.), Proceedings of the 22nd Conference Information Technologies - Applications and Theory (ITAT 2022 ), Zuberec, Slovakia, September 23-27 , 2022 , volume 3226 of CEUR Workshop Proceedings, CEUR-WS.org , 2022 , pp. 21 - 27 . URL: https://ceur-ws. org/ Vol- 3226 /paper2.pdf .

[12] A. Dries , L. De Raedt, S. Nijssen , Mining predictive k-CNF expressions , IEEE Transactions on Knowledge and Data Engineering 22 ( 2009 ) 743 - 748 .