Finding a short and accurate decision rule in disjunctive normal form by exhaustive search

By Peter R. Rijnbeek, Jan A. Kors. 2010

38 citations recorded by the source corpus.

Greedy approaches suffer from a restricted search space which could lead to suboptimal classifiers in terms of performance and classifier size. This study discusses exhaustive search as an alternative to greedy search for learning short and accurate decision rules. The Exhaustive Procedure for LOgic-Rule Extraction (EXPLORE) algorithm is presented, to induce decision rules in disjunctive normal form (DNF) in a systematic and efficient manner. We propose a method based on subsumption to reduce the number of values considered for instantiation in the literals, by taking into account the relational operator without loss of performance. Furthermore, we describe a branch-and-bound approach that makes optimal use of user-defined performance constraints. To improve the generalizability we use a validation set to determine the optimal length of the DNF rule. The performance and size of the DNF rules induced by EXPLORE are compared to those of eight well-known rule learners. Our results show that an exhaustive approach to rule learning in DNF results in significantly smaller classifiers than those of the other rule learners, while securing comparable or even better performance. Clearly, exhaustive search is computer-intensive and may not always be feasible. Nevertheless, based on this study, we believe that exhaustive search should be considered an alternative for greedy search in many problems.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Information Systems

In Algorithms & Complexity

Citations in the corpus

Learning Certifiably Optimal Rule Lists (2017, background): “Tight bounds, on the other hand, have been developed for the (immense) literature on building disjunctive normal form (DNF) models, a good example of this is the work of Rijnbeek and Kors [33].”
Learning Fair Rule Lists (2019, background): “For instance, when they have small or of reasonable size [44], ∗ Principal contributor. the following models can be considered as interpretable: rules sets [18, 43, 46, 54], rule lists [3, 59, 61], decision trees [9, 51] and scoring systems [39, 57, 64].”
Multi-Value Rule Sets (2017, background): “There has been a series of research on developing rule-based models for classiﬁcation [1, 3, 5, 8, 12, 17, 19, 22].”
A Bayesian Framework for Learning Rule Sets for Interpretable Classification (2017, background): “Rijnbeek and Kors (2010) proposed an efficient way to exhaustively search for short and accurate decision rules.”
Hybrid Decision Making: When Interpretable Models Collaborate With Black-Box Models (2018, background): “, [17, 22, 28, 34], Rule Lists [3, 36]), scoring systems [14, 32, 37], case based models [1, 4, 13], and etc.”
Foundations of Rule Learning (2012, background): “Recently, Rijnbeek and Kors (2010) proposed EXPLORE, a general framework for the exhaustive search of DNF formulas in propositional logic. Earlier, the ITRULE algorithm (Smyth & Goodman, 1991) implemented an efficient exhaustive search for a fixed number of rules with a fixed maximum length. In indu”