Symbolic Snapshot Ensembles

Mingyue Liu, Andrew Cropper · 2025

Read Symbolic Snapshot Ensembles by Mingyue Liu, 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-2510-24633.txt.

Introduction

Mingyue Liu and Andrew Cropper study logic based machine learning, where a rule set is learned from facts. Most such tools train once and keep just the last rule set. Their twist is to save the rule sets made along the way, not throw them out.

They then join those saved rule sets, weighting each by how short and neat it is. Tests on game play and image thought tasks raised right calls by four points on average. The extra cost was less than one point of added run time. So one training run can give a group gain that once took many runs.

Catalog record

CREATORMingyue Liu, Andrew Cropper
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-24633

Browse the full library · About the Tower of Babel

Full text

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

Symbolic Snapshot Ensembles Mingyue Liu, Andrew Cropper Abstract Inductive logic programming (ILP) is a form of logical machine learning. Most ILP algorithms learn a single hypothesis from a single training run. Ensemble methods train an ILP algorithm multiple times to learn multiple hypotheses. In this paper, we train an ILP algorithm only once and save intermediate hypotheses. We then combine the hypotheses using a minimum description length weighting scheme. Our experiments on multiple benchmarks, including game playing and visual reasoning, show that our approach improves predictive accuracy by 4% with less than 1% computational overhead. 1 Introduction Inductive logic programming (ILP) is a form of machine learning ( Muggleton 1991 ; Cropper and Dumancic 2022 ) . The goal is to search for a hypothesis that generalises given training examples and background knowledge (BK). The distinguishing feature of ILP is that it uses logical rules to represent hypotheses, examples, and BK. As with other forms of machine learning, ILP ensembles can reduce generalisation error ( Quinlan 1996 ; Kramer 2001 ; Hoche and Wrobel 2001 ; Jiang and Colton 2006 ; Salvini, Aguilar, and Dutra 2007 ) . For instance, de Castro Dutra et al. 2003 use bagging to learn multiple hypotheses from subsets of the training data and combine them via majority voting. Their empirical results show that their method improves accuracy by 3-4% compared to a single hypothesis prediction. Existing ensemble approaches have two notable limitations. First, when learning from a small dataset, bootstrap samples can significantly overlap, reducing ensemble diversity and limiting effectiveness ( Dietterich 2000 ) . Second, training an ILP algorithm multiple times to build an ensemble is computationally expensive. In this paper, rather than train an ILP algorithm multiple times, we train an algorithm only once and save the intermediate hypotheses it finds. When the ILP algorithm finds a hypothesis whose cost is lower than any encountered so far, we add it to a snapshot pool and we ask the ILP algorithm to keep searching until it exceeds a given timeout. We then combine the hypotheses using a minimum description length (MDL) ( Rissanen 1978 ) weighting scheme. We use the weighted combination to make predictions. We follow Huang et al. 2017 and call this approach a snapshot ensemble. Novelty and Contributions The novelty of this paper is using multiple hypotheses learned by a single ILP run to build a snapshot ensemble and combining the hypotheses with an MDL weighting scheme. The impact, which we demonstrate on multiple datasets, including game-playing and visual reasoning, is a reduction in generalisation error with almost no extra training cost compared to the classical bagging approach. Overall, we contribute the following: • We describe the first single-run ensemble framework for ILP, which is sufficiently general to work with any anytime ILP algorithm. • We introduce an MDL-based weighting scheme that balances training fit against ensemble complexity. • We experimentally show on multiple domains, including visual reasoning and game playing, that our snapshot ensemble approach improves predictive accuracy by 4% with less than 1% overhead. • We experimentally show that our ensemble approach matches or surpasses the predictive performance of standard bagging methods, while requiring significantly less computational cost. 2 Related Work ILP. Most ILP approaches learn a single hypothesis from one run on the training data ( Quinlan 1990 ; Muggleton 1995 ; Srinivasan 2001 ; Muggleton, Lin, and Tamaddoni-Nezhad 2015 ; Blockeel and De Raedt 1998 ; Law, Russo, and Broda 2014 ; Evans and Grefenstette 2018 ; Cropper and Morel 2021 ) . For instance, ProbFOIL ( De Raedt et al. 2015 ) extends FOIL ( Quinlan 1990 ) to find the single best probabilistic hypothesis. We differ from most ILP approaches by saving hypotheses found during training and combining them into an ensemble. ILP ensembles. Ensembling in ILP focuses on bagging and boosting ( Quinlan 1996 ; Kramer 2001 ; Hoche and Wrobel 2001 ; de Castro Dutra et al. 2003 ; Jiang and Colton 2006 ; Salvini, Aguilar, and Dutra 2007 ) . These approaches require multiple training runs or resampling procedures. For instance, de Castro Dutra et al. 2003 train an ILP learner on multiple bootstrap samples of the data (sampling with replacement) and combine the induced hypotheses by majority vote to improve generalisation. To reduce computational overhead of bagging, Salvini, Aguilar, and Dutra 2007 ensemble single rules rather than full hypotheses (with multiple rules), trading a slight decrease in accuracy for substantially faster training. Yan et al. 2024 introduce a method that merges relational decision trees ( Blockeel and De Raedt 1998 ) ensemble candidates into a single compressed decision list, reducing the hypothesis’s complexity while retaining the predictive accuracy of bagging or boosting. In contrast to these ensemble methods, our approach requires only a single ILP run. As far as we know, no previous work describes a single-run ensemble method in ILP. Single-run ensembles. Outside ILP, some ensemble methods capture multiple hypotheses from a single training run. Horizontal voting ensembles ( Xie, Xu, and Chuang 2013 ) and checkpoint ensembles ( Chen, Lundberg, and Lee 2017 ) both store intermediate checkpoints at various training epochs and combine their predictions, while snapshot ensembles use a cyclic learning-rate schedule that forces the model into different local optima ( Huang et al. 2017 ) . Another direction of research explores the construction of ensembles through subnetwork-based methods. For instance, MotherNet ( Wasay et al. 2020 ) expands a trained parent network by adding layers and neurons to form child networks. FreeTickets ( Liu et al. 2021 ) preserves diverse and low-cost sparse subnetworks during training. Prune and Tune Ensemble ( Whitaker and Whitley 2022 ) creates ensemble diversity by pruning each cloned network independently. Our method differs from these network-based approaches because it does not rely on manipulating a continuous weight space (e.g. via cyclic learning rates or pruning). Instead, we harness the natural diversity of structurally distinct rule sets generated during ILP’s search. 3 Problem Setting We now define our problem setting. We assume familiarity with logic programming ( Lloyd 2012 ; De Raedt 2008 ) . 3.1 Inductive Logic Programming We define an ILP input: Definition 1 ( ILP input ) . An ILP input is a tuple (E,B,\mathcal{H}) where E=(E^{+},E^{-}) is a pair of sets of ground atoms representing positive ( E^{+} ) and negative ( E^{-} ) examples, B is a definite program representing 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 2 ( Cost function ) . Given an ILP input (E,B,\mathcal{H}) , a cost function cost_{E,B}~:~\mathcal{H}~\mapsto~\mathbb{N} assigns a numerical cost to each hypothesis h\in\mathcal{H} . The MDL principle ( Rissanen 1978 ) trades off hypothesis complexity (hypothesis size) and data fit (training accuracy). The MDL principle can be expressed as finding a hypothesis that minimises L(h)+L(E|h) , where L(h) is the syntactic complexity of the hypothesis h and L(E|h) is the complexity of the data when encoded using h . Following Hocquette et al. 2024 , we evaluate L(E|h) as the cost of encoding the exceptions to the hypothesis, i.e. the

Read the complete text