Efficient Rule Induction by Ignoring Pointless Rules Andrew Cropper, David M. Cerna Abstract The goal of inductive logic programming (ILP) is to find a set of logical rules that generalises training examples and background knowledge. We introduce an ILP approach that identifies pointless rules. A rule is pointless if it contains a redundant literal or cannot discriminate against negative examples. We show that ignoring pointless rules allows an ILP system to soundly prune the hypothesis space. Our experiments on multiple domains, including visual reasoning and game playing, show that our approach can reduce learning times by 99% whilst maintaining predictive accuracies. 1 ELLIS Institute Finland 2 University of Helsinki 3 Dynatrace Research 4 Czech Academy of Sciences Institute of Computer Science andrew.cropper@helsinki.fi, david.cerna@dynatrace.com, dcerna@cs.cas.cz Code — https://github.com/logicand-learning-lab/aaai26-implications 1 Introduction The goal of inductive logic programming (ILP) is to induce a hypothesis (a set of logical rules) that generalises training examples and background knowledge (BK) ( Muggleton 1991 ; Cropper and Dumančić 2022 ) . To illustrate ILP, suppose we have BK with the relations succ/2 , lt/2 , gt/1 , int/1 , even/1 , odd/1 and the following positive ( E^{+} ) and negative ( E^{-} ) examples: E + = { f(5), f(7) } E - = { f(2), f(3), f(4), f(6), f(8), f(9) } Given this input, we might want to learn a rule such as: r_{1} = f(A) \leftarrow odd(A), gt(A,3), lt(A,8) This rule says that f(A) is true if A is odd, greater than 3, and less than 8. An ILP learner tests rules on the examples and BK and uses the outcome to guide the search. For instance, suppose a learner tests the rule: f(A) \leftarrow even(A) This rule is too specific because it does not entail any positive example. Therefore, a learner can ignore its specialisations, such as: f(A) \leftarrow even(A), gt(A,2) Similarly, suppose a learner tests the rule: r_{2} = f(A) \leftarrow odd(A), int(A) This rule is too general because it entails two negative examples ( f(3) and f(9) ). Therefore, a learner can ignore its generalisations. A learner will not necessarily ignore its specialisations because one could still be helpful, such as: r_{3} = f(A) \leftarrow odd(A), int(A), gt(A,3), lt(A,8) This rule entails all the positive and none of the negative examples. However, r_{2} and r_{3} are pointless because odd(A) implies int(A) , so we can remove int(A) whilst preserving semantics. We call such rules reducible rules. Now consider the rule: f(A) \leftarrow lt(A,B) This rule entails all the positive and all the negative examples, so a learner can ignore its generalisations. However, although it entails all the negative examples, we cannot ignore its specialisations as one might still be a good rule, such as r_{1} . Now consider the specialisation: f(A) \leftarrow lt(A,10) This rule entails all the positive and negative examples, so a learner can ignore its generalisations. However, unlike the previous rule, a learner can ignore its specialisations. The reason is that the literal lt(A,10) implies all the negative examples, i.e. there is no negative example greater than 10. Moreover, this literal cannot be further specialised (besides grounding the variable A and thus disconnecting the head literal from the body). We call such rules indiscriminate rules. The novelty of this paper is to show that ignoring reducible and indiscriminate rules allows us to efficiently and soundly prune the hypothesis space and thus improve learning performance. Although existing approaches find reasons why a rule fails on examples, such as having erroneous literals ( Muggleton et al. 2015 ; Cropper and Hocquette 2024 ) or rules ( Shapiro 1983 ; Raghothaman et al. 2020 ) , they do not find reducible or indiscriminate rules. We demonstrate our idea in the new ILP system Reducer . This system builds on Popper ( Cropper and Morel 2021 ; Hocquette et al. 2024 ) , which can learn optimal and recursive hypotheses from noisy data. The key novelty of Reducer is identifying pointless rules and building constraints from them to prune the hypothesis space. Novelty and Contributions The novelty of this paper is identifying pointless rules and building constraints from them to prune the hypothesis space of an ILP system . The impact, which we demonstrate on multiple domains, is vastly reduced learning times. Overall, we contribute the following: • We define two types of pointless rules: reducible and indiscriminate . We show that specialisations of reducible rules are also reducible (Proposition 1 ). Likewise, we show that specialisations of indiscriminate rules are also indiscriminate (Proposition 3 ). Finally, we show that a hypothesis with a reducible or indiscriminate rule is not optimal (Propositions 2 and 4 ). • We introduce Reducer , an ILP system which identifies pointless rules in hypotheses, including recursive hypotheses, and builds constraints from them to prune the hypothesis space. We prove that Reducer always learns an optimal hypothesis if one exists (Theorem 1 ). • We experimentally show on multiple domains, including visual reasoning and game playing, that our approach can reduce learning times by 99% whilst maintaining high predictive accuracies. 2 Related Work ILP. Many ILP systems use bottom clauses ( Muggleton 1995 ; Srinivasan 2001 ) or variants ( Ray 2009 ) to restrict the hypothesis space. Building bottom clauses can be expensive ( Muggleton 1995 ) . In the worst case, a learner needs a bottom clause for every positive example. Bottom clause approaches struggle to learn hypotheses with recursion or predicate invention. Reducer does not use bottom clauses. Redundancy in ILP. Fonseca et al. (2004) define self-redundant clauses similar to reducible rules (Definition 8 ) but cannot guarantee that specialisations are redundant (unlike Proposition 1 ) and require users to provide redundancy information. Raedt and Ramon (2004) check redundancy before testing but require anti-monotonic constraints (holding for generalisations, not specialisations) and do not identify implications between literals. By contrast, Reducer finds implications to prune specialisations. Zeng et al. (2014) prune syntactic redundancy (e.g. duplicate variables), whereas we detect semantic redundancy. Srinivasan and Kothari (2005) compress bottom clauses statistically; we avoid bottom clauses. Rule selection. Many systems ( Corapi et al. 2011 ; Kaminski et al. 2019 ; Raghothaman et al. 2020 ; Bembenek et al. 2023 ; Law 2023 ) precompute every possible rule in the hypothesis space and then search for a subset that generalises the examples. Because they precompute all possible rules, they cannot learn rules with many literals and can build pointless rules. For instance, ilasp4 ( Law 2023 ) will precompute all rules with int(A) and even(A) in the body. By contrast, Reducer builds constraints from pointless rules to restrict rule generation. If Reducer sees a rule containing int(A) and even(A) , it identifies that even(A) implies int(A) and henceforth never builds a rule with both literals. Constraints. Many recent ILP systems frame the ILP problem as a constraint satisfaction problem ( Corapi et al. 2011 ; Ahlgren and Yuen 2013 ; Schüller and Benz 2018 ; Kaminski et al. 2019 ; Bembenek et al. 2023 ) . MUSPer ( Cropper and Hocquette 2024 ) finds minimal sub-hypotheses that can never be true and builds constraints from them to prune the hypothesis space. For instance, given the rule f(A) \leftarrow succ(A,B),odd(B),even(B) , MUSPer can identify that a number cannot be both odd and even and then prunes the hypothesis space accordingly. By contrast, Reducer finds pointless rules with redundancy. Rule induction. ILP approaches induce rules from data, similar to rule learning methods ( Fürnkranz and Kliegr 2015 ) such as AMIE+ ( Galárraga et al. 2015 ) and RDFRules ( Zeman et al. 2021 ) . Most rule-mining methods are limited to unary and binary relations, require facts as input, and operate under an open-world assumption. By contrast, Reducer operates under a closed-world assumption, supports arbitrary-arity relations, and can learn from definite programs as background knowledge. Redundancy in AI. Theorem proving has preprocessing techniques for eliminating redundancies ( Hoder et al. 2012 ; Khasidashvili and Korovin 2016 ; Vukmirovic et al. 2023 ) . In SAT, redundancy elimination techniques, such as blocked clause elimination ( Kullmann 1999 ) , play an integral role in modern solvers ( Heule et al. 2010 ; Barnett et al. 2020 ; Biere et al. 2021 ) . Similar to this paper, SAT redundancy elimination identifies clauses containing literals that always resolve to tautologies. 3 Problem Setting We assume familiarity with logic programming ( Lloyd 2012 ) but have included summaries in the supplementary material. For clarity, we define some key terms. A rule r is a definite clause of the form h\leftarrow p_{1},\ldots,p_{n} where h,p_{1},\ldots,p_{n} are literals, head(r)=h , and body(r)=\{p_{1},\ldots,p_{n}\} . A definite program is a set of definite clauses. We use the term hypothesis interchangeably with a definite program. We denote the set of variables in a literal l as vars(l) . The variables of a rule r , denoted vars(r) , is defined as vars(head(r))\cup\bigcup_{p\in body(r)}vars(p) . Given a rule r and a set of literals C , by r\cup C we denote the rule r^{\prime} such that head(r^{\prime})=head(r) and body(r^{\prime})=body(r)\cup C . A specialisation of a rule r is a rule r^{\prime} that is \theta -subsumptively more specific than r , where \theta=\{v_{1}/t_{1},…,v_{n}/t_{n}\} is a substitution that simultaneously replaces each variable v_{i} by term t_{i} (See ( Plotkin 1971 ) and the Appendix). We focus on a restricted form of \theta -subsumption which only considers whether the bodies of two rules with the same head literal are contained in one another, i.e., no variable renaming. We formally define this restriction through a subrule relation: Definition 1 ( Subrule ) . Let r_{1} and r_{2} be rules. Then r_{1} is a subrule of r_{2} , denoted r_{1}\subseteq r_{2} , if head(r_{1})=head(r_{2}) and body(r_{1})\subseteq body(r_{2}) . We generalise the subrule relation to a sub-hypothesis relation. Unlike the subrule relation, the sub-hypothesis relation is not a restriction of \theta -subsumption: Definition 2 ( Sub-hypothesis ) . Let h_{1} and h_{2} be hypotheses and for all r_{1}\in h_{1} there exists r_{2}\in h_{2} such that r_{1}\subseteq r_{2} . Then h_{1} is a sub-hypothesis of h_{2} , denoted h_{1}\subseteq h_{2} . The sub-hypothesis relation captures a particular type of hypothesis that we refer to as basic . These are hypotheses for which specific rules do not occur as part of a recursive predicate definition: Definition 3 ( Basic ) . Let h be a hypothesis, r_{1} a rule in h , and for all r_{2} in h , the head symbol of r_{1} does not occur in a body literal of r_{2} . Then r_{1} is basic in h . As we show in Section 3 , under certain conditions we can prune hypotheses containing sub-hypotheses that are basic with respect to a contained rule. Inductive Logic Programming We formulate our approach in the ILP learning from entailment setting ( De Raedt 2008 ) . We define an ILP input: Definition 4 ( ILP input ) . An ILP input is a tuple (E,B,\mathcal{H}) where E=(E^{+},E^{-}) is a pair of sets of ground atoms denoting positive ( E^{+} ) and negative ( E^{-} ) examples, B is background knowledge, and \mathcal{H} is a hypothesis space, i.e., a set of possible hypotheses. We restrict hypotheses and background knowledge to definite programs with the least Herbrand model semantics. We define a cost function: Definition 5 ( Cost function ) . Given an ILP input (E,B,\mathcal{H}) , a cost function cost_{E,B}~:~\mathcal{H}~\to~\mathbb{N} assigns a numerical cost to each hypothesis in \mathcal{H} . Given an ILP input and a cost function cost_{E,B} , we define an optimal hypothesis: Definition 6 ( Optimal hypothesis ) . Given an ILP input (E,B,\mathcal{H}) and a cost function cost E,B , a hypothesis h\in\mathcal{H} is optimal with respect to cost E,B when \forall h^{\prime}\in\mathcal{H} , cost E,B ( h ) \leq cost E,B ( h^{\prime} ). We use a cost function that first minimises misclassified training examples, then minimises the number of literals in a hypothesis. False positives are negative examples entailed by h\cup B . False negatives are positive examples not entailed by h\cup B . We denote these as fp_{E,B}(h) and fn_{E,B}(h) respectively. We define size:\cal{H}\rightarrow{\mathbb{N}} as the number of literals in h\in{\cal{H}} . We use the cost function cost_{E,B}(h)=(fp_{E,B}(h)+fn_{E,B}(h),size(h)) . Pointless Rules We want to find rules that cannot be in an optimal hypothesis. We focus on reducible and indiscriminate rules. A reducible rule contains a body literal that is implied by other body literals. For example, consider the rules: r 1 = h \leftarrow odd(A), int(A) r 2 = h \leftarrow odd(A) The rule r 1 is reducible because odd(A) implies int(A) . Therefore, r 1 is logically equivalent to r 2 . As a second example, consider the rule: h \leftarrow gt(A,B), gt(B,C), gt(A,C) This rule is reducible because the relation gt/2 is transitive, i.e. gt(A,B) and gt(B,C) imply gt(A,C) . Because it contains a redundant literal, a reducible rule cannot be in an optimal hypothesis. However, a specialisation of a reducible rule could be in an optimal hypothesis. For instance, consider the rule: r_{1} = h \leftarrow member(L,X), member(L,Y) In this rule, member(L,X) implies member(L,Y) and vice-versa, so one of the literals is redundant. However, we could still specialise this rule as: r_{2} = h \leftarrow member(L,X), member(L,Y), gt(X,Y) Rules r_{1} and r_{2} are not logically equivalent, and r_{2} could be in an optimal hypothesis. A key contribution of this paper is to identify reducible rules where we can prune all their specialisations. The idea is to identify a redundant captured literal. A captured literal is one where all of its variables appear elsewhere in the rule. For instance, consider the rule: h \leftarrow succ(A,B), succ(B,C), gt(C,A), gt(C,D) In this rule, the literal gt(C,A) is captured because all its variables appear elsewhere in the rule. By contrast, the literal gt(C,D) is not captured because the variable D does not appear elsewhere in the rule. We define a captured literal: Definition 7 ( Captured literal ) . Let r be a rule, l\in body(r) , and vars(l)\subseteq vars(body(r)\setminus\{l\})\cup vars(head(r)) . Then l is r - captured . If a literal is captured in a rule then it is captured in its specialisations: Lemma 1 . Let r_{1} and r_{2} be rules such that r_{2}\subseteq r_{1} , l\in body(r_{2}) , and l be r_{2} -captured. Then l is r_{1} -captured. Proof. Follows from Definition 1 as the subrule relation preserves variable occurrence. ∎ We define a reducible rule: Definition 8 ( Reducible ) . Let r be a rule, B be BK, l\in body(r) be r -captured, and B\models(body(r)\setminus\{l\})\rightarrow l . Then r is reducible . Some specialisations of a reducible rule are reducible: Proposition 1 ( Reducible specialisations ) . Let B be BK, r_{1} be a reducible rule, and r_{1}\subseteq r_{2} . Then r_{2} is reducible. Proof. Let l be a r_{1} -captured literal and B\models(body(r_{1})\setminus\{l\})\rightarrow l . By Lemma 1 , l is also r_{2} -captured. Let C=body(r_{2})\setminus body(r_{1}) . Then, (body(r_{1})\setminus\{l\})\rightarrow l is subsumptively more general than (body(r_{1}\cup C)\setminus\{l\})\rightarrow l , where r_{2}=r_{1}\cup C , i.e., if the former holds for r_{1} than the latter holds for r_{2} . Thus, r_{2} is reducible. ∎ Certain hypotheses that contain a sub-hypothesis with reducible rules are not optimal: Proposition 2 ( Reducible soundness ) . Let B be BK, h_{1} be a hypothesis, h_{2}\subseteq h_{1} , r_{1} be basic rule in h_{1} , r_{2}\in h_{2} , r_{2}\subseteq r_{1} , and r_{2} be reducible with respect to B . Then h_{1} is not optimal. Proof. By Proposition 1 , r_{1} is also reducible implying that there exists an l\in body(r_{1}) and rule r_{3}\subset r_{1} such that (i) B\models(body(r_{1})\setminus\{l\})\rightarrow l , (ii) r_{1}=r_{3}\cup\{l\} , and (iii) |r_{3}|<|r_{1}| . Furthermore, r_{3} is basic given that r_{1} is basic. Let h_{3}=(h_{1}\setminus\{r_{1}\})\cup\{r_{3}\} . Then cost_{E,B}(h_{3})