While we have seen considerable progress in learning rule-based theories in the past years, all state-of-the-art rule learners still learn descriptions that directly relate the input features to the target concept. However, the limitation of learning concepts in this shallow disjunctive normal form (DNF) may not necessarily lead to the desired models. In this paper, we investigate a novel search strategy that uses conjunctions and disjunctions of individuals as its elementary operators, which are successively combined to deep rule structures with intermediate concepts. We make use of eficient data structures known from association rule mining, which can eficiently summarize counts of conjunctive expressions, and expand them to handle disjunctive expressions as well. The resulting rule concepts develop over multiple generations and consist of arbitrary, deep combinations of conjunctions and disjunctions. The behavior of this algorithm is evaluated on a benchmark task from the domain of poker. A comparison to other rule learning algorithms shows that, while it is not generally competitive, it has some interesting properties, such as finding more compact and better generalizing models, that cannot be found in conventional rule learning algorithms.
pair and no pair, Ripper gets stuck at 70% accuracy since it is not able to generalize to pairs that it has not seen Traditional rule learning algorithms usually learn models during training. that directly relate input features to the output class. In this paper, we make first steps towards tackling This approach works well for most benchmark datasets, this problem by trying to remove the restriction to DNF however, there are also datasets where it comes to its formulas that is commonly made by conventional rule limits. One such case is the poker-dataset, where the task learning algorithms, and directly learn arbitrary logical is to learn to identify the quantitative value (pair, full concept descriptions. More precisely, we investigate the house, straight, etc.) of a hand of five cards. Every card is behavior of a simple algorithm that successively comdefined by a unique combination of a suit (clubs, spades, bines input signals with logical operators, thus building hearts, diamonds) and a rank (ace, 2, 3, ..., queen, king). up complex logic structures.
For example, the class one pair includes hands where two The remainder of the paper is organized as follows: of the five cards have the same rank and the remaining Section 2 describes the problem of learning the pair conthree cards a diferent one. Already this task of detecting cept in diferent logical representations and refers to reone pair is particularly dificult for a rule learner, because, lated work. Based on this, we propose a combination of in order to make a correct classification, it essentially has a local search and genetic algorithm in Section 3 and test to enumerate all possible card combinations (card 1 and it in various settings in Section 4. Finally, the results are 2, card 1 and 3, ..., card 4 and 5), for every rank (ace, 2, 3, concluded in Section 5. ..., queen, king). Advanced concepts based on this pair concept, like two pairs or full house, are even harder to learn, so that on the full poker-dataset the state-of-the- 2. Pair Concept art rule learner Ripper only achieves a little more than 50% accuracy, which can already be reached by simply predicting the most frequent class nothing in hand that covers 50% of the data as well. Even in an adapted binary version of the poker-dataset, where the only classes are Disjunctive Normal Form. Ripper [1] and most other rule learners learn their models in disjunctive normal form (DNF) [2]. This normal form consists of a disjunction of conjunctions of literals whereby each conjunction is called a rule and the whole DNF expression a ruleset. To describe the concept of a pair in DNF for a set of cards and ranks, we have to find one rule for each possible combination of two cards for every rank as seen in the following equation: ⋁︁ ⋁︁ ⋁︁ = ∧ = . =1 =1 =+1
(
The total number of rules in this expression is · · − 2 1 = · (︀ 2)︀ with each of them consisting of two literals, resulting in a total number of · · ( − 1) literals for the whole ruleset. can reduce this number to 8, as, e.g., in the following two cases: [(1 = 0 ∨ 2 = 0) ∧ (3 = 0 ∨ 4 = 0)] ∨ (1 = 0 ∧ 2 = 0) ∨ (3 = 0 ∧ 4 = 0), [(1 = 0 ∨ 2 = 0) ∧ (3 = 0 ∨ 4 = 0)] ∨ [(1 = 0 ∨ 3 = 0) ∧ (2 = 0 ∨ 4 = 0)].
(
+ 2 + 2 = + 2 · 2 .
= 2 + 2
Flattening out the recursion yields
Each disjunction in this CNF has a length of − 1 literals, so that the whole CNF contains disjunctions, resulting in the same number of · ( − 1) literals as the DNF when only considering a single rank 0. However, in comparison to the DNF, this representation might require a closer look to be comprehensible: Whenever any card has the rank 0, all disjunctions in the CNF besides the 0th disjunction become true, and the latter is true if any other card has the rank 0 as well to form a pair.
Note, however, that the expressions of type 2 need to be combined disjunctively, so that the resulting formula actually contains three logical layers: which is considerably smaller than, for example, the ︀( )︀ = (2) terms that are needed for learning the DNF 2 representation of the concept.
Because of the more compact representation, deeper
models like shown in Equations (
Converting this formula to a pure CNF would be con- binations occur in the training data. If in the previous
siderably more complex than a DNF. In general, the example the pair combination of the first and the last card
choice whether CNF or DNF is a more compact represen- is missing in the training data, an algorithm looking for
tation depends on the problem. deep structures might still find and use the conjunction
(1 = 0 ∨ 2 = 0) ∧ (3 = 0 ∨ 4 = 0) instead
Other Representations. In fact, if we do not restrict of splitting it into two conjunctions of size three (1 =
the logic formula to consist of only one conjunctive and 0∨2 = 0)∧3 = 0 and 2 = 0∧(3 = 0∨4 = 0)
one disjunctive layer, even more compact representations or three conjunctions of size two 1 = 0 ∧ 3 = 0,
are possible. As an example, consider the pair concept 2 = 0 ∧ 3 = 0 and 2 = 0 ∧ 4 = 0. In the
for = 4 and a single rank 0. The corresponding CNF following, we present a genetic algorithm that is capable
and DNF contain 4 · (4 − 1) = 12 literals but other repre- to build a model with arbitrary combinations of
conjuncsentations allowing nested conjunctions and disjunctions tions and disjunctions to verify this hypothesis.
= log2 · ,
(
end population ← new_population.get_n_fittest(population_size, metric_type, metric_arg); population.print_summary();
n_generations, n_ofspring, max_sim, selectors Output: concept 1 population ← Population(selectors, metric_type, metric_arg); 2 population.print_summary(); 3 for ← 1 to n_generations do 4 new_population ← population; 5 for ← 1 to n_ofspring do 6 for 1 ∈ population do 7 repeat 8 2 ← tournament_selection(population, tournament_size); until 1 ̸= 2; ← crossover(1, 2, true); ← crossover(1, 2, false); sim ← .support / .support; if sim ≤ max_sim then if ̸= null then new_population.add( );
per was to investigate, whether general logical formulas could be built up using a local search algorithm, which incrementally builds up logical structures.
The key idea is to simply start with the logical input variables, and use the logical operators AND (∧) and OR (∨) to combine pairs of such values into a more complex expression. Note that such an approach should, in principle, be suficient for learning, for example, the DNF representation in the poker pairs domain. If, e.g., the population size is large enough to form all possible pairs in a first iteration, all subsequent iterations could form pairwise disjunctions of such pairs. Thus, once the (︀ 2)︀ 9 conjunctive pairs are formed, we would need log2 (︀ 2)︀ 10 iterations in order to combine them into a single large 11 disjunct, which makes in total 1 + log2 (︀ 2)︀ iterations. 12
The approach is quite similar to pattern trees, a data 13 structure designed for and used in fuzzy reasoning [5]. 14 However, while this approach deals with numerical data 15 and fuzzification operators, we remain in strictly binary 16 end weroarblldys,hwarhdeerretshoalnviinngiatsnloinpetaimrcizoautniotnerppraorbtl[e6m]. iAs lcsoon,sthide- 111978 iefndnew̸ =_pnouplulltahtieonn.add( ); structures are often built up in a top-down fashion [7], 20 end whereas we proceed from the bottom upwards. 21 end
The goal of the experiments reported is to see whether 22 a logical formula correctly describing the pair concept 23 can be found at all, which parameter settings would be necessary to find it, whether more compact structures can be found, or maybe even better generalizations can 24 be achieved. 25 end
This attempt is realized in the form of a variant of a ge- 26 concept ← population.get_n_fittest(1, metric_type, netic algorithm, which uses two types of crossovers, one metric_arg); for conjunctively combining and one for disjunctively 27 return concept combining two individuals in the current population, as shown in Algorithm 1.
The algorithm builds upon data structures created by Lord, a novel rule learner developed in our group [8].
Lord reuses ideas from association rule learning and only needs a single pass through the training data during the learning phase, which makes it very eficient for large datasets. All further operations, e.g., determining how many examples are correctly and incorrectly classified for any given rule expression, can be directly extracted from n-Lists. Note that, apart from the usage of the same data structures, the genetic algorithm presented in this paper and Lord are completely diferent and separate approaches: While the genetic algorithm aims at finding arbitrary logical formulas bottom upwards, Lord uses the data structures to find the best DNF rule for each training example. Detailed information about n-Lists are given in [9], and about their application in the Lord algorithm in [8].
The learning method of the variant of genetic algorithm is shown in Algorithm 1 and starts by creating a default population consisting of all possible features, also known as selectors in Lord. All single features can already be interpreted and evaluated as a rule for predicting the class pair for some arbitrary metric and parameter (e.g., m-Estimate with = 10). A first summary of the population is output to potentially analyze the best selectors.
The evolution begins in line 3 of Algorithm 1 and consists of an outer loop for each generation, which copies the population of the previous generation. It is followed by a loop for possibly generating multiple ofspring per individual and two inner loops for selecting individuals for the crossover. The first individual 1 is already preset whereas the second one 2 is selected by a tournament selection, returning the best individual of a fixed-sized subset of the population. Since conjunctions and disjuncnlist ← 3 ← + ")") Algorithm 2: crossover()-method
Output: 3 1 1, 2 ← order(1, 2); 2 if conjunctive then 3 nlist ← conj(1.nlist, 2.nlist); 4 3 ← Individual(nlist, 1.body + "&&" + 2.body) 5 else 6 7
disj(1.nlist, 2.nlist);
Individual(nlist, "(" + 1.body + "||" + 2.body 10 11 end 12 return 3 8 end 9 if 3.support = 1.support ∨ 3.support = 2.support ∨ 3.support = 0 then
return null tions with itself are not changing the coverage of the expression, we force 1 and 2 to be diferent individuals before starting with the crossovers. Note that both the conjunction and disjunction are computed successively in lines 10 and 11.
Algorithm 2 describes the crossover procedure. After ordering the two individuals alphabetically, either the conjunctive or disjunctive n-List and condition string are built. If one of the individuals covers a subset of instances of the other one, or both individuals are disjoint from each other, the resulting individual is meaningless and null is returned instead. Otherwise, the created crossover is returned to the learning method.
Optionally, in lines 12 and 13 of Algorithm 1, the Jaccard similarity between the two generated crossovers is computed to avoid ofspring that is too similar to its conjunction respectively disjunction "sibling" and parents. If this is not the case, the crossovers are added to the new population. Since the population increases this way, at the end of each generation the population is filtered and only the best individuals are kept (line 23). By printing the summary of the population in line 24, the maximum heuristic value and the ten best individuals are output.
Finally, the best individual of the last generation is returned as the concept, which can then be used to evaluate whether test examples are covered by the concept.
For the experiments, we generated multiple versions of the poker pairs-dataset with varying dificulty: • pairs2 consisting of 30 card combinations with 12 pairs ( = 2 cards, = 2 ranks, = 3 suits) • pairs3 consisting of 336 card combinations with 144 pairs ( = 3 cards, = 4 ranks, = 2 suits) • pairs4 consisting of 11,880 card combinations with 6,120 pairs ( = 4 cards, = 6 ranks, = 2 suits) • pairs4a consisting of 6,660 card combinations with 900 pairs ( = 4 cards, = 6 ranks, = 2 suits). In comparison to pairs4, all pairs besides those with rank 0 = 6 are removed, and additionally those with 1 = 6 and 4 = 6 are retained for evaluation.
nine of them are used for training to break symmetries.
In all experiments, 10 generations with a population size
of 100 and a tournament size of 5 are used, and the rules
are evaluated by the m-estimate metric with = 10.
The m-estimate value ℎ of a rule predicting class
has been proposed by Cestnik [10] and is calculated as
ℎ() =
. + + ,
. + . +
(
weighted relative accuracy (→− ∞ ), which is frequently used in descriptive rule learning, and precision (→− 0), the main target for predictive learning [11].
The results of the experiments are summarized in Tables 1 and 2, the detailed evaluation is split into one paragraph per poker pairs-dataset. Pairs within two cards. In this minimalistic dataset, Pairs within four cards. In the dataset with four cards there are only two diferent types of pairs since only we used six ranks, summing up to 36 pair combinations. two cards and ranks are available. Both the minimal DNF While a minimal DNF needs at least 72 literals, with 1 = 1∧2 = 1∨1 = 2∧2 = 2 and the corresponding deeper logical expressions sketched in Equations 4 and 5 CNF (1 = 1 ∨ 2 = 2) ∧ (1 = 2 ∨ 2 = 1) consist of only 48 literals are needed. However, this requires to find four literals and could be found in two steps. suitable disjunctions in the first generation.
Using a strict genetic algorithm approach, i.e., without The results for the dataset with four cards are similar building all possible crossovers in the first generation(s), to the previous one with three cards but with even more the learned concept describes all pairs for 5 out of 10 significant diferences between the three settings. The folds, and this concept is found between the third and performance of the pure genetic algorithm setting drops iffth generation. The 5 remaining folds also diverge to a to a pair coverage between 24% and 49% and it converges ifxed concept (in diferent logical expressions) the latest in an even later generation than in the smaller datasets. in the sixth generation, however, in 4 of them one or two This can again be fixed by a single exhaustive search for pairs are not covered respectively, and in the last one a crossovers and a subsequent genetic algorithm covering non-pair was covered mistakenly. between 79% and 93% of the pairs. However, similar to
If in the first generation all possible crossovers are gen- the dataset with three cards, if also in the subsequent generated, thus in particular the crossovers 1 = 1 ∧ 2 = 1 eration all crossovers are computed, the convergence of and 1 = 2 ∧ 2 = 2, the perfect theory can be found in the algorithm is sped up but the pair coverage decreases all 10 folds. 6 of theses folds need four generations to do to percentages between 52% and 77%. so, the remaining 4 find it already in the second gener- While the best performance is achieved by the alation. Interestingly, one of them also finds the minimal gorithm using a single generation with an exhaustive CNF additionally to the minimal DNF. crossover search, all resulting models have in common
Finally, if also in the second generation all crossovers that they learn DNFs instead of creating intermediate are generated, both the minimal DNF and CNF are found disjunctions before conjuncting them. To investigate in all folds. further into this, we refine the dataset in the following paragraph.
more complex; three cards and four ranks lead to 12 pair Subset of pairs within four cards. In the last excombinations, which need a length of at least 20 literals if periment, we want to focus on a diferent aspect: the using an arbitrary nested logical expression and a length capability of the learner to augment the concept to pairs of at least 24 literals if using a DNF. that are not covered in the training data like described
Even with problems of this size, the presented simple in the end of Section 2. We consider pairs with cards of genetic algorithm can not find an expression covering rank 6 and ensure that only five out of six are part of the all pairs in any fold. The percentage of covered pairs training data. As a consequence, state-of-the-art DNF ranges from 56% to 92% and is approximately equally rule learners like Ripper are only capable to detect these distributed, same holds for the number of generations five pair combinations and conjunct them: that lies between 4 and 7.
As discussed in Section 3, already a single generation
with all possible crossovers can fix this problem. Even if (1 = 6 ∧ 2 = 6) ∨ (1 = 6 ∧ 3 = 6)∨
the population size is too small to keep all crossovers, it (2 = 6 ∧ 3 = 6) ∨ (2 = 6 ∧ 4 = 6)∨ (
The average number of generations needed as well seen in Equations 4 and 5 that even smaller concepts can as the overall complexity of the found concepts can be be learned, and those possibly also cover the missing slightly decreased by computing all crossovers for a sec- pair combination. We verify whether similar models can ond generation. Surprisingly, this approach leads to in- indeed be learned with the suggested approach. Starting complete concepts in two folds though, that are missing with the pure genetic algorithm, the learner does not even 1 of the 12 pair combinations. This indicates that an ex- reliably find all pair combinations. In four out of ten folds, haustive search over multiple generations leads to too parts of the concepts additionally use suit attributes in many similar individuals that prevent other diverse in- the conjunctions, which led up to 37 of 810 pair instances dividuals from being included into the population and uncovered. used for further concepts. By generating all crossovers in the first generation, the five pair combinations are found and combined to a
DNF similar to Equation 9 within five generations, i.e., approach. one iteration more than in the optimal logarithmic case. While the presented combination of a local search and Therefore, all training instances consisting one of these genetic algorithm is not yet matured to be successfully ifve pair combinations are covered, but the test instances applied on arbitrary real-world datasets, through the apwith the remaining sixth pair combination remain disre- plication on diferent versions of the poker pairs-dataset garded. we could take away some interesting properties of the
This behavior changes if the second generation com- deep rule theories learned this way. An exhaustive search putes all crossovers as well. Figure 1 lists the best ten indi- for crossovers in the first generation was needed to reviduals found in the first and second generation. While in liably find concepts covering all or at least most pairs. the first generation this list only consists of conjunctions However, an additional exhaustive search in the subsethat are already able to only cover pairs, in the second quent generation led to too many similar individuals and generation the best three individuals are conjunctions resulted in a worse performance for the chosen parameof disjunctions, i.e., crossovers of individuals that have ters. Finally, the last experiment on a subset of the poker not been among the best ten in the first generation. In pairs-dataset with four cards showed that the presented particular, the second and third individual evaluate better learner indeed is capable to find the more compact and than all possible individuals in DNF and at the same time better generalizing model described at the beginning of still cover the missing sixth pair combination. this paper, which can not be learned by state-of-the-art
Based on these individuals, a concept covering all pairs rule learners, and highlights the importance of subseof the training set can be found already in the third gener- quent combinations of disjunctions and conjunctions to ation for five of the folds, and in the fourth generation for do so. the remaining five folds. The percentage of individuals covering the additional the missing sixth pair combination ranges from 13% to 31%. While this number is still 6. Future Work low, it is worthwhile to mention that in comparison to DNF rule learner it is capable to generate such individu- In future work, further refinements of the genetic alals, and in comparison to the other two versions it also gorithm are necessary and partly already implemented. actually finds them. Most emphasized should be the handling of diversity, which can, e.g., either be handled by a separate reserve population that focuses on covering a wider variety of 5. Conclusion examples instead of covering the most examples as possible or by penalizing the evaluation of individuals if their In this work, we dealt with the question when conven- Jaccard similarity is too high. Additionally, a penalty tional DNF rule learners come to their limits. We con- for the rule length might force the algorithm to prefer ducted this on the basis of a poker pairs-dataset and the most compact representation between those covershowed that deep rule theories can both describe the ing the same instances. Last but not least, the idea of pair concept in a more concise form and are capable to mutations might be refined for the rule learning setting. generalize the concept better. To investigate into this Features on all levels of the logical expression could be behavior in practical experiments, we created a simple removed, replaced or augmented, and conjunctions could variant of a genetic algorithm, which uses conjunctive be interchanged with disjunctions and vice versa. For all and disjunctive crossovers to built deep rule concepts out these suggestions, a further in-depth analysis is needed of single features. We also implemented the possibility though. to generate all possible crossovers at the beginning of the algorithm, which can then be seen as a local search