Learning Logical Rules using Minimum Message Length

Ruben Sharma, Sebastijan Dumančić, Ross D. King, Andrew Cropper · 2025

Read Learning Logical Rules using Minimum Message Length by Ruben Sharma, Sebastijan Dumančić, Ross D. King, Andrew Cropper (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-06230.txt.

Introduction

Ruben Sharma, Sebastijan Dumančić, Ross King, and Andrew Cropper teach logical rules from noisy data in a 2025 paper. Their method joins probability with logic programming under a Bayesian frame. It scores each candidate rule set by message length: shorter descriptions that still fit the data win. Priors favor more general programs, while the fit term favors accurate ones. That balance guards against both overfitting and oversimplifying.

Across domains including game playing and drug design, their learner beat previous methods clearly, including ones based on description length alone. It also learned efficiently from few examples, and even from positive examples only.

Catalog record

CREATORRuben Sharma, Sebastijan Dumančić, Ross D. King, Andrew Cropper
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-06230

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning Logical Rules using Minimum Message Length Ruben Sharma, Sebastijan Dumančić, Ross D. King, Andrew Cropper Abstract Unifying probabilistic and logical learning is a key challenge in AI. We introduce a Bayesian inductive logic programming approach that learns minimum message length programs from noisy data. Our approach balances hypothesis complexity and data fit through priors, which explicitly favour more general programs, and a likelihood that favours accurate programs. Our experiments on several domains, including game playing and drug design, show that our method significantly outperforms previous methods, notably those that learn minimum description length programs. Our results also show that our approach is data-efficient and insensitive to example balance, including the ability to learn from exclusively positive examples. Introduction Inductive logic programming (ILP) is a form of machine learning. The goal is to induce a logic program (a set of logical rules) that generalises examples and background knowledge (BK) ( Muggleton 1991 ; Cropper and Dumancic 2022 ) . As with all forms of machine learning, ILP learns from noisy data. A popular approach is to search for a minimal description length (MDL) ( Rissanen 1978 ; Rissanen 1998 ; Rissanen 1987 ; Grünwald 2007 ) hypothesis ( Quinlan 1990 ; Muggleton 1995 ; Srinivasan 2001 ; Cabalar, Pearce, and Valverde 2007 ; Hocquette et al. 2024 ) . MDL is a mathematical formalisation of Occam’s razor: a preference for simpler (formalised as shorter) explanations of data. The goal of MDL is to encode data as a binary string as concisely as possible. Minimum message length (MML) ( Wallace 2005 ) is another formalisation of Occam’s razor. The goal of MML is to find the most concise explanation of data, where an explanation is a two-part message consisting of a hypothesis (the first part) followed by the data given that the hypothesis is true (the second part). MDL and MML are closely related, but differ in philosophy, mathematical grounding, and practical usage ( Baxter and Oliver 1994 ; Makalic and Schmidt 2022 ) . We briefly summarise the key differences, but expand on them in Section 2. MML is explicitly Bayesian and uses priors over hypotheses and integrates them into encoding length. MDL avoids priors and often treats hypotheses as tools for encoding data rather than probabilistic entities. In MML, the message is two-part, first asserting the hypothesis, followed by data given that the asserted hypothesis is true. In MDL, the message may be one-part and often does not encode the hypothesis itself. MML and MDL also handle continuous parameters differently ( Baxter and Oliver 1994 ; Grünwald 2007 ) . In this paper, we use the MML principle to learn logic programs from noisy examples. Specifically, we design an encoding scheme which allows for lossless communication of a probabilistic logic program ( De Raedt, Kimmig, and Toivonen 2007 ) and examples. The cost of a hypothesis is the length of the hypothetical message which would result if we were to communicate the examples using this hypothesis. Our main claim is that MML outperforms a previous MDL-based score ( Hocquette et al. 2024 ) , shown to achieve state-of-the-art performance when learning logic programs from noisy examples. We term this previous score C-MDL. We argue that MML is better suited for this task for two reasons: (i) it uses prior probabilities, allowing us to favour more general programs, and (ii) it handles continuous parameters in a way that provides automatic regularisation ( Wallace 2005 ; Farr and Wallace 2002 ; Wallace and Freeman 1987 ) . MML has two more advantages over C-MDL: (iii) its hypothesis cost corresponds to an exact message length, and (iv) it uses a structured likelihood function that penalises over-generalisation, with this penalty being regulated by the generality priors from (i). Whilst an exact MDL approach could incorporate (iii) and (iv), it would still lack the intrinsic MML benefits of (i) and (ii). Specifically, we claim: Claim 1: MML performs similarly to C-MDL on general tasks Claim 2: MML outperforms C-MDL when learning from different example proportions, including learning from exclusively one type of example Claim 3: MML requires less data than C-MDL Claim 4: An explicit prior preference for more general programs improves the data efficiency of MML Claim 5: MML performs similarly to C-MDL on noisy data Claim 6: A practical approximation to MML outperforms C-MDL when learning from unbalanced examples Contributions Overall, our contributions are: 1. We formulate the program learning problem in Bayesian and MML terms. We use the MML framework to derive a cost function for learning probabilistic logic programs, consistent with the Problog semantics ( De Raedt, Kimmig, and Toivonen 2007 ) . 2. We introduce a practical method to learn approximate MML programs from examples. 3. We empirically show that the MML score outperforms C-MDL on predictive accuracy and matches its performance on noisy data. The method excels when learning from few or unbalanced examples. Related Work ILP. Most ILP approaches learn from noisy data ( Quinlan 1990 ; Muggleton 1995 ; Blockeel and De Raedt 1998 ; Srinivasan 2001 ) . For instance, MaxSynth ( Hocquette et al. 2024 ) searches for programs that minimise the total of the training errors and literals in the program. In contrast to our approach, these approaches do not allow for the explicit declaration of prior beliefs regarding the quantity of noise in the examples, do not employ techniques to mitigate the effect of example balance in their learning, and do not return probabilistic logic programs. Positive only learning. While several ILP approaches have been proposed that learn from exclusively positive examples ( De Raedt and Bruynooghe 1993 ; Quinlan and Cameron-Jones 1995 ; Mooney and Califf 1995 ) , most require an assumption of example completeness. One exception ( Muggleton 1996 ) also models the program learning task under a Bayesian framework, but is restricted to noiseless data, uses coarse size-related priors, and employs a greedy search to find the hypothesis of maximum posterior probability. We differ by handling noise and using a prior that exactly corresponds to the program message length. MML and MDL . MML and MDL have been applied to learn a wide range of models, including neural networks ( Makalic, Allison, and Dowe 2003 ; Hinton and Van Camp 1993 ) , decision trees ( Wallace and Patrick 1993 ) , automata ( Wallace 2005 ) , and statistical distributions ( Farr and Wallace 2002 ) . The most relevant prior work is ( Conklin and Witten 1994 ) , which learned deterministic logic programs. However, their coding scheme is inefficient and cannot handle noisy data. We introduce a more principled coding scheme, an improved search procedure, and extend the framework to learn probabilistic logic programs. We choose MML over MDL for its Bayesian framework and method of handling parameter uncertainty: encoding real-valued parameters to a finite precision. MDL usually uses approximations or penalised maximum likelihood (ML) estimators to estimate continuous parameters. MML’s handling often yields less biased and consistent estimators that are often more accurate than ML ( Baxter and Oliver 1994 ; Wallace 2005 ) . Probabilistic logic programming . Previous work has focused on learning rule probabilities ( Gutmann, Thon, and De Raedt 2011

Read the complete text