Towards Modern Rule-Based Learning

Abstract

Symbolic classification is a subfield of symbolic learning focused on extracting a collection of mutually exclusive logical rules for classification. This is typically achieved by learning intermediate models, such as decision trees or decision lists. In this paper, we present Modal Sequential Covering (MSC), a decision list learning algorithm that generalizes several existing proposals in the literature. We also provide an early open-source implementation of this algorithm in Julia, integrated within Sole, a comprehensive end-to-end framework for modern symbolic AI. An experimental comparison with available tools reveals that MSC allows us to learn simpler but equally performant models. The integration of MSC into Sole enables manipulating and visualizing the extracted knowledge in logical form. As Sole is designed for symbolic learning with modal and propositional logics, this work lays the foundation for further generalization to non-tabular data.

Keywords

• eol>Symbolic Learning
• Decision List Learning
• Rule Extraction

1. Introduction

SoleXperimenter.jl

ModalDecisionLists.jl

ModalIsolationForests.jl

ModalDecisionTrees.jl

ModalAssociationRules.jl

SoleFeatures.jl

SoleViz.jl

SoleData.jl

SoleModels.jl

SoleLogics.jl

SolePostHoc.jl

SoleReasoners.jl

which provides a decision list algorithm (IREP [ 6 ], RIPPER); Orange, in Python, with both decision trees and lists (C4.5, CN2 [ 7 ]); Chefboost, in Python, with decision trees (ID3 [ 8 ]), supervisedPRIM and oneR, in R, with implementations for decision lists (PRIM [ 9 ], ONER), and MLJ, in Julia, which ofers a decision list learning algorithm (CART). While decision trees and similar techniques have received attention even in recent years (see, e.g. [ 10 ], among many others), it does not seem to be the case with rule covering, with the possible exception of explanation methods (see, e.g. [ 11 ]) or Tsetlin machines (see, e.g. [ 12 ]). A common characteristics of all mentioned programming frameworks, symbolic algorithms, and implementations, is that they do not leverage nor highlight the logical representations of the extracted knowledge. As such, the learned rules cannot be manipulated within a logical framework, and the algorithms themselves are not easily generalizable to more expressive logical languages.

Sole.jl (or, simply, Sole) [ 13 ] is a open-source framework, written in the Julia programming language, that allows one to design and deploy end-to-end learning tasks, from data preprocessing and cleaning, iflter-based feature extraction and selection, symbolic learning models training, testing, inspection, and post-hoc modification, and result visualization (a schema of Sole is shown in Fig 1). Sole is completely logic-based, and integrates several reasoning tools that can be paired up and used on the learned rules. As much as decision tree learning is concerned Sole already includes an implementation (MCART [ 14, 15 ]) that allows one to learn a decision tree from tabular and non-tabular data (using a suitable modal logic), and to manipulate the resulting rules in a comprehensive logical framework; modal logic extends propositional logic, and, as it emerges from several experiments on real-world data, can be applied to extract useful, non-trivial knowledge (see, e.g., [16, 17, 18]).

In this paper, we describe the implementation of the algorithm Modal Sequental Covering (MSC), which, in a nutshell, is the Julia implementation of a sequential covering algorithm that is based on, and generalizes several well-known algorithms, including RIPPER, CN2, ONER, and IREP. Decision lists learned with MSC may have rules whose literals are not just atomic statements but may be complex formulas; the covering can be heuristically driven by fully parameterizable beam search and be based on one of several available information measures; and, candidate literals can be explored via determinis(

⇒ BestGuess(ℐuncov)) if a Π-stopping condition applies then break

FindBestConjunction(ℐuncov, ℬ, ) (⊤ ⇒ BestGuess(ℐuncov)) Algorithm 1: Modal sequential covering algorithm. The input encompasses a dataset ℐ, a parametrization ℬ (resp., Π, ) for the beam search (resp., stopping conditions, search space and strategy). FindBestConjunction deploys a (CN2-like) beam search heuristic to learn conjunctions of formulas from a grammar; BestGuess computes the majority class of a dataset.

function MSC(ℐ, Π, ℬ, ):

2. Modal Sequential Covering

The most widely used algorithms for decision list learning follow the so-called sequential covering approach, that is, a separate-and-conquer method that learns rules sequentially. First, a set of uncovered instances is initialized as the set of all instances in the dataset; then, at each iteration of a loop, a single rule is learned on the uncovered instances by optimizing a loss function, and the instances covered by the rule is removed from the set of uncovered instances. Typically, a rule iteration is an object whose antecedent is given by a conjunction of conditions over the attributes.

A conjunction is progressively built via heuristic approaches that explore new conjuncts to be added, starting with an empty formula. For example, CN2 [ 7 ] adopts a beam search approach over the space of conjunctions, while RIPPER [ 3 ] specializes a single conjunction by selectively choosing the best condition to add (which is equivalent to single-beam search approach). The methods mainly difer from each other in terms of the loss function to be optimized (e.g., minimum description length, information gain, Laplace accuracy), as well as the regularization strategies deployed (e.g., pruning and stopping criteria). RIPPER, for example, performs a training/validation split prior to the learning, and after iteratively growing each conjunction on the training set, it uses the validation set to post-prune it; moreover, it prioritizes the least numerous classes, so that classes are covered, in order, by their ⇒ built at a given numerosity.

With a view of lifting the sequential covering approach to more-than-propositional logics (e.g., modal logics), these premises inspire the design of a more general sequential covering algorithm, namely Modal Sequential Covering (MSC), that iteratively learns conjunctions of type 1 ∧ . . . ∧ , with belonging to a (parametrizable) grammar; this extension is designed to trivially include the above algorithms where, for comparison, the conjuncts are limited to be atoms. MSC retains the list-level separate-and-conquer and rule-level beam search heuristic approaches, but extends the search space of conjuncts to a grammar, and deploys a parametrizable search heuristic, both of which are hyperparameters of the algorithm.

The pseudo-code of MSC is shown in Alg. 1.

y s p o i B e r e h p s o n o I e c i r P e li b o M t s a e Y e n o l a b A

Sole-CN2

Sole-RANDCOV

Orange-CN2

Wittgenstein-RIPPER

Scikit-CART

MLJ-CART

Sole-CN2

Sole-RANDCOV

Orange-CN2

Wittgenstein-RIPPER

Scikit-CART

MLJ-CART

Sole-CN2

Sole-RANDCOV

Orange-CN2

Wittgenstein-RIPPER

Scikit-CART

MLJ-CART

Sole-CN2

Sole-RANDCOV

Orange-CN2

Wittgenstein-RIPPER

Scikit-CART

MLJ-CART

Sole-CN2

Sole-RANDCOV

Orange-CN2

Wittgenstein-RIPPER

Scikit-CART MLJ-CART

Cross-validation results showing coeficient, training time, number of atoms in the model, and average atoms

3. Experiments and Results

We evaluated our implementation on five tabular datasets: Biopsy [ 19], Ionosphere [20], MobilePrice [21], Yeast [22], and Abalone [23]. All datasets, except MobilePrice, are publicly available on the UCI Machine Learning Repository [24], while MobilePrice is available via Kaggle.

We compared the following methods: MSC (Sole) with the RANDCOV profile ( Sole-RANDCOV); MSC (Sole) with the CN2 profile ( Sole-CN2); CN2 from the Orange Python package (Orange-CN2); RIPPER from the Wittgenstein Python package (Wittgenstein-RIPPER); CART from scikit-learn (ScikitCART); CART from the DecisionTree.jl Julia package (MLJ-CART). While the first two methods are based on MSC, Sole-CN2 behaves similarly to Orange-CN2, and Sole-RANDCOV introduces novelty by generating random propositional conjuncts. For each method, hyperparameter tuning was performed using grid search, optimizing for Cohen’s coeficient.

The results are summarized in Tab. 1. First, MSC achieves competitive accuracy (in terms of the coeficient) with state-of-the-art methods. Focusing on comparing, in particular, Sole-CN2 against SoleRANDCOV, the latter produces classifiers with less atoms in 3 out of 5 cases; in one case, Ionosphere the number of atoms is similar (14 vs 15). In the cases in which the random search produces better results in terms of number of atoms, the diference is very relevant (172 vs 213, 157 vs 464, and 108 vs 984); in all of them, Sole-RIPPER outperforms Orange-CN2 as well. Moreover, observe that Wittgenstein-RIPPER fails in 3 out of 5 cases, as it cannot handle more-than-binary problems. Finally, decision trees such as those produced by MLJ-CART or Scikit-CART are presented for reference, as there is no direct comparison between the two approaches.

Overall, our results show that MSC is a robust addition to the existing symbolic learning approaches, providing a balance between performance and rule complexity. The implementation in Sole makes it highly flexible, allowing the exploration of advanced symbolic learning techniques in future work.

4. Conclusions

In this paper, we have introduced the Modal Sequential Covering (MSC) algorithm, a generalization of existing decision list learning approaches, and its implementation within the Sole framework. While MSC currently operates in propositional logic, it is designed to seamlessly extend to modal logic formulas, which is particularly relevant given the success of using modal logics in symbolic learning for extracting useful, non-trivial knowledge from real-world data, as demonstrated in [16, 17, 18].

The integration of MSC into Sole provides a highly flexible platform, not only for working with traditional decision lists but also for exploring complex symbolic learning tasks using modal logics.

Acknowledgments

This research was supported by the FIRD project Methodological Developments in Modal Symbolic Geometric Learning, funded by the University of Ferrara, and the INDAM-GNCS project Symbolic and Numerical Analysis of Cyberphysical Systems (CUP_E53C23001670001), funded by INDAM. G. Pagliarini, G. Sciavicco, and I.E. Stan are GNCS-INdAM members. This research was also funded by the Italian Ministry of University and Research through PNRR - M4C2 - Investimento 1.3 (Decreto Direttoriale MUR n. 341 del 15/03/2022), Partenariato Esteso PE00000013 - "FAIR - Future Artificial Intelligence Research" - Spoke 8 "Pervasive AI", funded by the European Union under the NextGeneration EU programme. of the 21st International Conference of the Italian Association for Artificial Intelligence (AIxIA), volume 13796 of LNCS, Springer, 2022, pp. 47–59. [15] F. Manzella, G. Pagliarini, G. Sciavicco, I. E. Stan, Eficient modal decision trees, in: Proc. of the 22th Conference of the Italian Association for Artificial Intelligence (AIxIA), volume 14318 of Lecture Notes in Computer Science, Springer, 2023, pp. 381–395. [16] F. Manzella, G. Pagliarini, G. Sciavicco, I. E. Stan, The voice of COVID-19: breath and cough recording classification with temporal decision trees and random forests, Artifcial Intelligence in Medicine 137 (2023) 102486. [17] G. Pagliarini, G. Sciavicco, Interpretable land cover classification with modal decision trees,

European Journal of Remote Sensing 56 (2023) 2262738. [18] G. Pagliarini, S. Scaboro, G. Serra, G. Sciavicco, I. E. Stan, Neural-Symbolic Temporal Decision Trees for Multivariate Time Series Classification, in: Proceedings of the 29th International Symposium on Temporal Representation and Reasoning (TIME), volume 247 of LIPIcs, Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2022, pp. 13:1–13:15. [19] O. L. Mangasarian, W. H. Wolberg, Cancer diagnosis via linear programming, Technical Report,

University of Wisconsin-Madison Department of Computer Sciences, 1990. [20] V. Sigillito, S. Wing, L. Hutton, , K. Baker, Ionosphere, UCI Machine Learning Repository, 1989. [21] A. Sharma, Mobile price classification dataset, https://www.kaggle.com/datasets, 2021. [22] K. Nakai, Yeast, UCI Machine Learning Repository, 1996. [23] W. Nash, T. Sellers, S. Talbot, A. Cawthorn, W. Ford, Abalone, UCI Machine Learning Repository, 1995. [24] A. Asuncion, D. Newman, UCI machine learning repository, 2007.

References

[1] C. Rudin , Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead , Nature Machine Intelligence 1 ( 2019 ) 206 - 215 .

[2] J. R. Quinlan , Generating production rules from decision trees , in: Proceedings of the 10th International Joint Conference on Artificial Intelligence ., Morgan Kaufmann, 1987 , pp. 304 - 307 .

[3] W. W. Cohen , Fast efective rule induction , in: Proc. of the 12th International Conference on Machine Learning , Morgan Kaufmann, 1995 , pp. 115 - 123 .

[4] R. C. Holte , Very simple classification rules perform well on most commonly used datasets , Machine Learning 11 ( 1993 ) 63 - 91 .

[5] L. Breiman , J. Friedman , R. Olshen , C. Stone , Classification and regression trees , Wadsworth Publishing Company , 1984 .

[6] J. Fürnkranz , G. Widmer, Incremental reduced error pruning , in: Proc. of the 11th International Conference on Machine Learning„ Morgan Kaufmann , 1994 , pp. 70 - 77 .

[7] P. Clark , T. Niblett , The CN2 Induction Algorithm, Machine Learning 3 ( 1989 ) 261 - 283 .

[8] J. Quinlan , Induction of Decision Trees, Machine Learning 1 ( 1986 ) 81 - 106 .

[9] J. H. Friedman , N. I. Fisher , Bump hunting in high-dimensional data , Statistics and computing 9 ( 1999 ) 123 - 143 .

[10] A. Schidler , S. Szeider , Sat-based decision tree learning for large data sets , Journal of Artificial Intelligence Research 80 ( 2024 ) 875 - 918 .

[11] S. M. Lundberg , G. Erion, H. Chen , A. DeGrave, J. Prutkin , B. Nair , R. Katz , J. Himmelfarb , N. Bansal , S. Lee , From local explanations to global understanding with explainable ai for trees , Nature machine intelligence 2 ( 2020 ) 56 - 67 .

[12] K. Abeyrathna , O.-C. Granmo , R. Shafik , L. Jiao , A. Wheeldon , A. Yakovlev , J. Lei , M. Goodwin , A multi-step finite-state automaton for arbitrarily deterministic tsetlin machine learning , Expert Systems - the Journal of Knowledge Engineering 40 ( 2023 ).

[13] F. Manzella , G. Pagliarini , A. Paparella , G. Sciavicco, I. E. Stan , Sole.jl - Symbolic Learning in Julia, https://github.com/aclai-lab/Sole.jl, 2024 .

[14] D. Della Monica , G. Pagliarini, G. Sciavicco, I. E. Stan , Decision trees with a modal flavor , in: Proc.