Neurosymbolic Decision Trees

Matthias Möller, Arvid Norlander, Pedro Zuidberg Dos Martires, Luc De Raedt · 2025

Read Neurosymbolic Decision Trees by Matthias Möller, Arvid Norlander, Pedro Zuidberg Dos Martires, Luc De Raedt (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-2503-08762.txt.

Introduction

Matthias Moller and co-authors introduce neurosymbolic decision trees in a 2025 paper on mixing neural networks with logic. Most work in this field tunes the neural or fuzzy parts of a model, while the logical structure itself is fixed. The authors instead learn the structure.

Their trees extend classic decision trees, and their algorithm NeuID3 adapts the standard top-down way trees are built. It combines that induction with a neural probabilistic logic representation. The result is a model whose reasoning steps stay readable while its parts learn from data, a mix sought in explainable AI.

Catalog record

CREATORMatthias Möller, Arvid Norlander, Pedro Zuidberg Dos Martires, Luc De Raedt
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-08762

Browse the full library · About the Tower of Babel

Full text

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

Neurosymbolic Decision Trees Matthias Möller, Arvid Norlander, Pedro Zuidberg Dos Martires, Luc De Raedt Abstract NeSy ( NeSy ) AI studies the integration of NN and symbolic reasoning based on logic. Usually, NeSy techniques focus on learning the neural, probabilistic and/or fuzzy parameters of NeSy models. Learning the symbolic or logical structure of such models has, so far, received less attention. We introduce NLDT , as an extension of decision trees together with a novel NeSy structure learning algorithm, which we dub NeuID3. NeuID3 adapts the standard top-down induction of decision tree algorithms and combines it with a neural probabilistic logic representation, inherited from the DeepProbLog family of models. The key advantage of learning NLDT with NeuID3 is the support of both symbolic and subsymbolic data (such as images), and that they can exploit background knowledge during the induction of the tree structure, In our experimental evaluation we demonstrate the benefits of NeSy structure learning over more traditonal approaches such as purely data-driven learning with neural networks. 1 Introduction NeSy AI combines symbolic reasoning methods and NN in order to leverage their respective strengths: the ability to exploit background knowledge using logic and the function approximation capabilities of NN [ 27 , 18 , 40 ] . A common approach to constructing NeSy systems starts from probabilistic logic formulas, where, in contrast to deterministic logic formulas, the literals in a formula are true or false with a certain probability. By predicting the probabilities using NN we obtain a NeSy model. However, this approach requires the logical structure of the NeSy model to be given upfront, which is not possible in many practical settings. This paper addresses the challenging problem of simultaneously learning both the structure and the parameters for NeSy . More specifically, 1. we introduce NLDT by parametrizing probabilistic decision trees using NN ( Section 3 ), 2. we present NeuID3 1 1 1 The name Neural ID3 (NeuID3) is chosen after Ross J. Quinlan’s famous ID3 (Inductive Dichotomizer 3) algorithm [ 33 ] . an iterative top-down decision tree learner for inducing NLDT over tree-shaped logic formulas ( Section 4 ). In our experimental evaluation ( Section 6 ) we then demonstrate that NLDT can use symbolic as well as subsymbolic features in order to classify data points. Compared to standard decision trees, this has the advantage of being able to use raw sensor data, e.g. images, as features. Compared to NN , NLDT have the advantage of allowing the incorporation of background knowledge, leading, for instance, to more data-efficient learners. Compared to other NeSy approaches, NDTs have the advantage that the symbolic structure of the model is completely induced from scratch. We discuss the differences to related NeSy approaches in Section 5 . Note that throughout the paper, we focus largely on propositional logic for simplicity, though the introduced techniques can in principle be generalized towards first order logic following the works of [ 2 , 8 , 27 ] . 2 Background We first introduce the necessary concepts and notation for propositional logic programming. Then we describe Boolean decision trees and their probabilistic extension in terms of (probabilistic) logic programming [ 7 ] . An atom is a proposition q (sometimes also called a Boolean variable), and a literal is an atom or its negation \neg q . A rule is an expression of the form h\leftarrow b_{1}\wedge...\wedge b_{n} where h is an atom and the b_{i} are literals. The meaning of such a rule is that h holds whenever the conjunction of all b_{i} holds. Rules with an empty body n=0 are called facts and hold unconditionally. A set of rules and facts constitutes a logic program L and can be used to decide whether a literal q logically follows from the program. We write L\models q when it does ( L models q ), and L\not\models q when it does not. 2.1 Boolean Decision Trees BDT can be represented as a binary tree, cf. Figure 1 . Each internal node i (including the root) contains a proposition \tau_{i} , also called a test . The two children of an internal node then represent the two possible value assignment \tau_{i}=true and \tau_{i}=false , respectively. We will use \cal F to refer to the set of all propositions used as tests in the decision tree. For the decision tree in Figure 1 , we are given \mathcal{F}=\{burglary,earthquake,alarm\} . By associating each leaf with one of two classes, which we denote by pos and neg , respectively, we can use \Acp BDT as binary classification decision trees. For the BDT in Figure 1 we can pick for instance the following leaf-to-class mapping (written as rules): \displaystyle pos \displaystyle\leftarrow leaf_{1}.\quad pos\leftarrow leaf_{3}. \displaystyle neg \displaystyle\leftarrow leaf_{2}.\quad neg\leftarrow leaf_{4}.\quad neg\leftarrow leaf_{5}. To classify an example with a BDT one starts evaluating the atom in the root, and propagates the example towards the child corresponding to the truth-value of the atom. This process is repeated recursively until a leaf node is reached and the class assigned to that leaf node is predicted for the example. As an illustrative example, consider the two sets of literals \mathcal{L}_{e_{1}} and \mathcal{L}_{e_{2}} representing two examples e_{1} and e_{2} \displaystyle\mathcal{L}_{e_{1}} \displaystyle=\{\phantom{\neg}burglary,\neg earthquake,\phantom{\neg}alarm\} \displaystyle\mathcal{L}_{e_{2}} \displaystyle=\{\neg burglary,\neg earthquake,\neg alarm\} where a positive literal indicates that the test is assigned with true while a negated ( \neg ) literal indicates that the test evaluates to false. The corresponding subsets of the positive literals (atoms) are \mathcal{F}_{e_{1}}=\{burglary,alarm\} and \mathcal{F}_{e_{2}}=\{\} , respectively. In the context of the BDT in Figure 1 , e_{1} represents the situation where an alarm is triggered by a burglary . In contrast, e_{2} represents the case of no alarm being triggered and the absence of a burglary and no earthquake . We can also take a logic programming perspective on classification with BDT , as it is well-known that decision trees can be transformed into a set of logical rules [ 31 ] . We illustrate this on on the right in Figure 1 . Classification then proceeds as follows: an example e is labeled with class c\in\{pos,neg\} if and only if L\cup\mathcal{F}_{e}\models c , where \mathcal{F}_{e} is the subset of positive literals (atoms) in \mathcal{L}_{e} . The choice for using \mathcal{F}_{e} results from the principle of negation as a failure which states that all atoms that cannot be proven true are assumed to be false [ 16 ] . Reconsidering the set of literals \mathcal{L}_{e_{1}} and \mathcal{L}_{e_{1}} we consequently have L\cup\mathcal{F}_{e_{1}}\models pos and L\cup\mathcal{F}_{e_{2}}\models neg . true true false false true true false false burglary alarm leaf_{1} leaf_{2} earthquake alarm leaf_{3} leaf_{4} leaf_{5} Rules \displaystyle leaf_{1} \displaystyle\leftarrow burglary\land alarm. \displaystyle leaf_{2} \displaystyle\leftarrow burglary\land\neg alarm. \displaystyle leaf_{3} \displaystyle\leftarrow\neg burglary\land earthquake\land alarm. \displaystyle leaf_{4} \displaystyle\leftarrow\neg burglary\land earthquake\land\neg alarm. \displaystyle leaf_{5} \displaystyle\leftarrow\neg burglary\land\neg earthquake. Figure 1: Left: A BDT modelling whether a person calls the police conditioned on whether a burglary, an alarm, and an earthquake occur. Right: a set of rules representing the BDT as a logic program. 2.2 Probabilistic Boolean Decision Tree So far we have assumed that all tests in \cal F are deterministically true or false. We now lift this restriction by adopting probabilistic logic instead and use the concept of a probabilistic

Read the complete text