Rule-based decision models are attractive due to their interpretability. However, existing rule induction methods often result in long and consequently less interpretable rule models. This problem can often be attributed to the lack of appropriately expressive vocabulary, i.e., relevant predicates used as literals in the decision model. Most existing rule induction algorithms presume pre-defined literals, naturally decoupling the definition of the literals from the rule learning phase. In contrast, we propose the Relational Rule Network (R2N), a neural architecture that learns literals that represent a linear relationship among numerical input features along with the rules that use them. This approach opens the door to increasing the expressiveness of induced decision models by coupling literal learning directly with rule learning in an end-to-end diferentiable fashion. On benchmark tasks, we show that these learned literals are simple enough to retain interpretability, yet improve prediction accuracy and provide sets of rules that are more concise compared to state-of-the-art rule induction algorithms.
Over the last decade, black box decision models (e.g. neural networks) are increasingly used
in high stakes decision making, yet there has been equally growing concern over their use
[
We propose the Relational Rule Network (R2N): a three-layer neural network which learns literals in the first layer, each representing a partition of the input feature space delimited by a hyperplane, which we call a halfspace. The second and third layers map the binary vector of literals to a binary predictions, encoding a crisp logical formula in the form of a DNF. We consider halfspaces as literals as they are simple enough to retain interpretability, yet significantly improve expressivity and model accuracy. Encoding this structure in an end-to-end diferentiable neural network has the benefit that the learning of the literals is directly informed by their usage in the rule. To showcase the value of using appropriate predicates as literals in a rule model, we present a simple toy example: Given a dataset with two numerical input features ( 0, 1) and a corresponding label determined by the ground truth if ( 0/ 1 > 1.0 ∧ 0 > 0.5) then class = True; else class = False; (1) the task is to find a rule model that accurately predicts the label given the input. This model involves two distinct decision boundaries: 0 = 0.5 and 0/ 1 = 1.0. Training our model with default parameters (see Appendix C) recovers the ground truth (see Fig. 1) whereas when literals are predefined as univariate value comparisons (e.g. 0 < 0.2), we learn a longer DNF. This is because each conjunction represents a rectangle in the feature space ( 0, 1), and many of them are needed to adequately approximate the sloped decision boundary, 0/ 1 = 1 (Fig. 1b). Therefore, by improving the expressivity of the rule model with the ability to represent ratio as a single literal rather than a conjunction of many, we simplified the model and improved accuracy.
We summarize our contribution as follows: i) We propose a neural network architecture (R2N) that learns a DNF together with the literals it uses. The literals represent halfspaces, whose boundary hyperplanes are learned by the network. ii) We demonstrate that compared to SOTA algorithms (RIPPER, BRCG, DR-Net, etc.) we improve sparsity and interpretability of the learned rule model both for a set of benchmark problems where the underlying decision models are known as well as where they are not.
Our work contributes to the large body of work on neuro-symbolic rule learning systems that represent atoms and clauses as individual nodes in a neural network (NN) and that learn rules as configurations of weights on the edges that link these nodes. This approach is diferent from existing distillation-based approaches that construct a simpler interpretable network to mimic a) the behavior of a complex black-box model [8, 9]. While they generate post-hoc explanations that only approximate a model, R2N and the like natively learn explainable rules: the rules do not approximate the NN, they are equivalent to it by construction.
The representation of rules in R2N is essentially the same as in C-IL2P [10] and followers (e.g. [11, 12, 13]). R2N difers from C-IL2P and similar systems in two main ways: whereas they focus on approximating logic programs and their semantics in discrete domains (although infinite and continuous domains can also be dealt with, it remains in a probabilistic setting [ 14]), R2N learns crisp classification rules in continuous numerical domains, like [ 15, 16]. However, our approach difers from [ 15] in two regards: i) the encoding and ii) the binarization of the rules as we discuss in Section 4.
In addition, R2N learns a set of literals that map the -dimensional continuous numerical
input space to an -dimensional Boolean space in which the rule models are learned. Similar
neuro-symbolic systems require binarized input data using predefined predicates [ 10, 15, 16, 17];
are limited to learning univariate threshold values [18]; or learn latent relations in a finite
Herbrand base [
Extending the branching conditions from simple value comparisons to linear halfspaces has been proposed for decision trees [23]. While it is possible to translate the resulting decision tree to a DNF, such mapping usually results in excessively long rules, hindering interpretability. Furthermore, single literal learning layer that grounds the learned literals using hyperplanes in R2N can be replaced with an arbitrarily complex NN (learning hypersurfaces) at the cost of interpretability.
The rule model that we consider for binary classification is a DNF, whose formal grammar is defined by the following production rules, r u l e m o d e l → if D N F then class = True; else class = False
D N F → c o n j u n c t i o n | c o n j u n c t i o n ∨ D N F c o n j u n c t i o n → l i t e r a l | l i t e r a l ∧ c o n j u n c t i o n
l i t e r a l → 1| ... | | +1 | ... | The underlined terms are terminal symbols, and the t y p e w r i t e r terms are the non-terminal symbols. Among the predicates (of arbitrary arity) in our dictionary of literals, some have learnable parameters, { 1,..., }, e.g., coeficients of a hyperplane defining a halfspace, and some do not, { +1 ,..., }, meaning they are pre-determined (see Fig. 2). We call the subset of literals with learnable parameters learned literals, and those without learnable parameters predefined literals. Note that negations are not part of the rule language. Therefore, negated predicates, if desired, must be explicitly included in the dictionary of literals.
The Relational Rule Network (R2N) is composed of two modules connected sequentially: 1. The literal learning module that learns halfspaces to be used as literals of the rule language. 2. The rule learning module that maps the binary vector of evaluated literals to a single binary prediction of the class label, in such a way that it encodes an equivalent logical formula in disjunctive normal form (DNF).
clear.
Any predefined literals we want to use, including categorical value comparisons, are directly supplied to the input layer of the rule learning module. See Fig. 2 for an illustration.
We introduce the following notation for the rest of this paper: • : Numerical input variable . • (x): The -th literal in our rule language. Learned literals ( = 1, ..., ) represent halfspaces in the N-dimensional space of x. We omit the argument when the context is • : The -th conjunction formed by a combination of literals.
Unless stated otherwise, normal-faced lower-case variables with subscripts (e.g., ) represent scalar components of its bold-faced counterparts, representing vectors (lower-case; x) or matrices (upper-case; X). All vectors are column vectors.
To enrich the vocabulary of our rule language, we consider a neural network layer that learns predicates representing halfspaces of the numerical feature space. These learned predicates can then be used as literals in the rule language. The literal learning module is represented by a single layer perceptron with a learnable bias and weight vector w we wish to learn (See Fig. 2). Extending this to multiple output nodes using matrix notation, () for each halfspace that the transformation is represented by (x) = ( x W() + b ) , (2) where W() is the weight matrix, b the corresponding biases, is the sigmoid activation function applied component-wise, and is a temperature parameter that changes according to a cooling schedule. Observing that (/ )
converges1 to the Heaviside step function as → 0 , we efectively approach strict binarization at the end of the cooling schedule (step function is used during testing), while avoiding zero gradients during training.
The rule learning module maps the binary vector of literals to a single binary prediction of the class label, in such a way that it encodes an equivalent logical formula in DNF. We specify this rule learning module as a two-layer neural network architecture respectively implementing an AND and a subsequent OR operation, similar to [10, 15].
The AND-layer maps a binary vector of literals = ( 1, ..., )to another binary vector ( 1, ..., ) whose components represent conjunctions made from some combination of the input literals. This combination is specified by a binary vector w indicating which of the literals are present in conjunction . The -th component of w is 1 if literal is included in conjunction and 0 otherwise [16]. 1It pointwise converges on ℝ ⧵ {0}.
↦
⋀ and ↦ 1 − min {∑ (1 − ), 1} are equivalent. Proof: See Appendix A
The AND-layer implements transformation (3) as a computational graph. Although the parameter we want to eventually learn is the binary weight matrix W, we learn it indirectly through reparameterizing it with a scaled sigmoid function that converges to a Heaviside step function in the limit, similarly as in the literal learning module. The learnable parameter for each binary weight is continuous and unconstrained: Proposition 1. Let be binary parameter and be Boolean variables whose values can be represented by binary values. Then the mappings (3) (4) (5) (6) = ( / ).
The resulting computational graph defined by equations ( 3) and (4) is diferentiable with nonzero derivatives. Note that ensuring non-zero gradients during the backwards pass, rather than using a straight through estimator, as in [15], is essential to ensure robust training, as described in [24].
The OR-layer maps a binary vector z to a single binary value by implementing a logical disjunction operation among select components of z. The binary weights w() of this layer encode which of the conjunctions learned in the AND-layer are to be included in the final disjunction. We seek a diferentiable approximation that approaches the non-diferentiable OR operation in the limit, similar to what we have done for the AND-layer.
Proposition 2. Let () be binary parameters and be Boolean variables. Then the mappings z ↦
⋁ are equivalent. Proof: See Appendix B
The binary weight vector w() is learned exactly the same way as we learn the weight matrix W of the AND-layer, through reparameterizing the binary weights using a scaled sigmoid: ()
= ( / ).
The OR-layer implements the computational graph defined by equations ( 5) and (6), where are the continuous and free learnable parameters.
The 2-layer network composing the AND and OR layers can be represented as a composition of the two diferentiable functions ( 3) and (5). As a direct result of Propositions 1 and 2, this network implements the evaluation of the DNF ↦ ⋁
⋀ . output of the decoded DNF is negligible for reasonably cold temperatures ( = 10 −4). Therefore at the end of training we learn a crisp DNF as classifcation rule.
() can be retrieved by inspecting the sign of the learned parameters
Examples
TRUE IF 1) ( 0 > 0.25) ∨ ( 1 < 0.5) 2) ( 0/ 1 > 0.5) ∨ ( 4 < 0.25) 3) ( 0 + 0.5 1 > 0.5) ∨ ( 4 < 0.25) 4) ( 0 < 0.2 ∧ 1 + 2 > 0.5)∨ ( 4/ 3 > 1 ∧ 1 < 0.5) 5) ( 4 < 0.2 ∧ 0/ 1 > 0.5)∨ (0.5 3 + 0.2 1 > 0.5) ∨ ( 0 < 0.2)
Examples Magic Heloc Adult
House Accuracy, number of conjunctions in the DNF ( ) and average number of literals per conjunction ( ) for (top) the examples with known ground truth and (bottom) four datasets taken from the UCI ML database. Note that for the columns with an ∗, the benchmark accuracy and ( , ) are taken from [15] to ensure a fair comparison.
In this section we study the accuracy and rule complexity for a set of benchmark problems (i)
where the underlying DNF is known and (ii) where this is not the case. We compare with three
SOTA methods: RIPPER [6], DR-Net [15] and BRCG [
We first consider five simple DNFs with increasing complexity (see Table
1) and compare the
prediction accuracy, number of conjunctions in the DNF ( ) and average number of literals per
conjunction ( ) of the R2N with SOTA methods. We generate a dataset of 104 samples from
the underlying rules where the five input features ( 0, ..., 4) are randomly sampled between
[
The three benchmark methods (RIPPER, DR-Net and BRCG) all require binarizing the numerical input features, hence trading of accuracy and length of the optimal DNF (fewer pre-defined literals will result in more compact rule models, but cruder approximations of the decision boundary). We selected the default parameters to make a fair comparisons in this case (See Appendix F for a detailed description), but these methods inherently require this accuracy/DNF complexity trade-of. RIPPER and DR-Net provide a comparable accuracy, yet provide DNFs that are considerably longer than R2N while BRCG provides more compact DNFs, but compromises significantly on the prediction accuracy. Note that this discrepancy is particularly important when the decision boundaries cannot be captured by univariate value comparisons as pre-defined literals (Ex. 2-5 in Table 1). In all cases, the rule language is not expressive enough to describe the linear decision boundary accurately with a sparse set of univariate literals.
Next we consider four datasets for which the underlying rule models are unknown (Taken
from the UCI ML-repository, [
In Appendix G and D we show the sensitivity of our approach with respect to the size of the dataset/noise level and sparsity parameters. Overall we show that the obtained rule model and its near-optimal accuracy can still be obtained for noise-levels (randomly flipping a fraction of the labels in the dataset) up to 10% and for training set sizes of the order of 103 training samples.
The method presented in this paper extends the vocabulary of rule-learning algorithms by learning literals that represent halfspaces. R2N can also serve in other applications as part of the domain vocabulary (or ontology); for instance as input predicates for other rule models like RIPPER or BRCG. We show that using these learned literals from R2N as input for RIPPER reduces the number of rules that it learns as compared to RIPPER with univariate value comparisons for all examples listed in Table 1 (see Appendix H). Note that while in general rules with fewer 2Comparisons are taken directly from [15] conjunctions and literals per conjunction can be considered more easily interpretable, true interpretability might have to be examined by subject matter experts.
Although learning literals defined through hyperplanes has been shown to be a good first step towards improving the expressiveness of the rules while retaining interpretability, they are by no means suficient for all practical applications. The framework we present can be extended to non-linear decision boundaries. A simple yet powerful example of this involves black-box function approximators (e.g. MLPs and LSTMs) to learn non-linear literals using our general machinery from Section 4 for retaining diferentiability. While this results in literals that are not explicitly interpretable, the final DNF that use these literals can still be understood and audited by humans who can then try to understand the learned literals in light of the rules that use them. As a concrete example, consider an application where the input data is sequential and the ground-truth class assignments depend on complex aggregates such as variance (e.g., () > 1 ⇒ ) or counts (e.g. ( > 2) ≤ 3 ⇒ ). Halfspace predicates are inadequate for representing these relationships. However LSTMs can learn binary “non-linear” predicates from the data, that can then be used as literals in the rule model. Post-hoc analysis of these literals can then shed light on their meaning, reducing the complex problem of interpreting the entire model to a simpler problem of interpreting individual literals in the context of an a priori understandable rule model.
This work has been partially funded by the French government as part of project PSPC AIDA 2019-PSPC-09, in the framework of the “Programme d’Investissement d’Avenir”. [6] W. W. Cohen, Fast efective rule induction, in: Machine learning proceedings 1995, Elsevier, 1995, pp. 115–123. [7] E. Angelino, N. Larus-Stone, D. Alabi, M. Seltzer, C. Rudin, Learning certifiably optimal rule lists for categorical data, Journal of Machine Learning Research 18 (2018) 1–78. URL: http://jmlr.org/papers/v18/17-716.html. [8] G. Hinton, O. Vinyals, J. Dean, Distilling the knowledge in a neural network, NIPS Deep
Learning and Representation Learning Workshop (2015). [9] J. R. Zilke, E. L. Mencía, F. Janssen, Deepred–rule extraction from deep neural networks, in: International Conference on Discovery Science, Springer, 2016, pp. 457–473. [10] A. S. Avila Garcez, G. Zaverucha, The connectionist inductive learning and logic programming system, Applied Intelligence 11 (1999) 59–77. [11] M. V. França, G. Zaverucha, A. S. d’Avila Garcez, Fast relational learning using bottom clause propositionalization with artificial neural networks, Machine learning 94 (2014) 81–104. [12] K. Gao, K. Inoue, Y. Cao, H. Wang, Learning first-order rules with diferentiable logic program semantics, arXiv preprint arXiv:2204.13570 (2022). [13] G. Marra, M. Diligenti, F. Giannini, M. Gori, M. Maggini, Relational neural machines, arXiv preprint arXiv:2002.02193 (2020). [14] V. Belle, Symbolic logic meets machine learning: A brief survey in infinite domains, in:
International Conference on Scalable Uncertainty Management, Springer, 2020, pp. 3–16. [15] L. Qiao, W. Wang, B. Lin, Learning accurate and interpretable decision rule sets from neural networks, Proceedings of the AAAI Conference on Artificial Intelligence 35 (2021) 4303–4311. URL: https://ojs.aaai.org/index.php/AAAI/article/view/16555. [16] F. Beck, J. Fürnkranz, An investigation into mini-batch rule learning, arXiv preprint arXiv:2106.10202 (2021). [17] L. Fu, Rule generation from neural networks, IEEE Transactions on Systems, Man, and
Cybernetics 24 (1994) 1114–1124. doi:1 0 . 1 1 0 9 / 2 1 . 2 9 9 6 9 6 . [18] Z. Wang, W. Zhang, N. Liu, J. Wang, Scalable rule-based representation learning for interpretable classification, Advances in Neural Information Processing Systems 34 (2021). [19] G. Sourek, V. Aschenbrenner, F. Zelezny, O. Kuzelka, Lifted relational neural networks, arXiv preprint arXiv:1508.05128 (2015). [20] S. Kramer, E. Frank, Bottom-up propositionalization., in: ILP Work-in-progress reports, 2000. [21] M.-A. Krogel, S. Rawles, F. Železnỳ , P. A. Flach, N. Lavrač, S. Wrobel, Comparative evaluation of approaches to propositionalization, in: International Conference on Inductive Logic Programming, Springer, 2003, pp. 197–214. [22] R. Manhaeve, S. Dumancic, A. Kimmig, T. Demeester, L. De Raedt, Deepproblog: Neural probabilistic logic programming, Advances in Neural Information Processing Systems 31 (2018). [23] H. Zhu, P. Murali, D. Phan, L. Nguyen, J. Kalagnanam, A scalable mip-based method for learning optimal multivariate decision trees, in: Advances in Neural Information Processing Systems, volume 33, Curran Associates, Inc., 2020, pp. 1771–1781. URL: https: //proceedings.neurips.cc/paper/2020/file/1373b284bc381890049e92d324f56de0-Paper.pdf. [24] Y. Bengio, N. Léonard, A. Courville, Estimating or propagating gradients through stochastic neurons for conditional computation, arXiv preprint arXiv:1308.3432 (2013).
As the functions are binary-valued, it sufices to show that one function evaluating to 1 is equivalent to the other function evaluating to 1. () ⋀ = 1 ⟺ ∀ ( = 1) → ( = 1)
Our loss function has a mean-square error component together with components that promote
sparsity of the obtained rule model. The overall loss function is:
ℒ
+ ‖W‖1 + ‖w() ‖1 + ‖W() ‖
1
where ‖ ⋅ ‖1 is the 1-norm. Increasing reduces the sparity of the learned literals, increasing
shortens conjunctions, and increasing shortens the disjunction. For simplicity, we choose
a single regularization penalty for all the diferent layers =
= = . Unless stated
otherwise, we use = 10 −2 for training on synthetic datasets (with known ground truth) and a
more conservative value of = 10 −3 for the UCI ML datasets [
We use the Adam optimizer from the PyTorch ecosystem with default learning rate and parameters to optimize Eq. 12. In order to avoid local minima throughout the training routine, we randomly re-initialize the weights of the neural network every 104 epochs and run the network for 2.5 × 105 epochs in total. The training is done with a fixed batch size of 100. We select the epoch with the lowest loss function on the training set and report the prediction accuracy at that stage for the test-set (train/test split of 80/20). (8) (9) (10) (11) (12)
As mentioned in the section on the literal learning module, to ensure smooth training as well as reaching binary output of the literal learning layer, we propose a cooling schedule of the sigmoid activation function with high temperature in the beginning allowing larger gradients to exist across a wider range of the input so that training can occur. As the temperature approaches zero, the sigmoid is progressively scaled and approaches the Heaviside function in the limit, so that we achieve strict binarization in the end. The temperature is cooled down with a factor = 0.995 at every subsequent epoch for all the examples presented in the paper.
The number of output nodes of the literal learning module = 10 while the number of nodes in the rule learning module is = 25 . Increasing or decreasing these numbers would impact the expressivity of the network but we empirically observed that varying this number in the range 10-50 did not show a significant sensitivity to these values.
In the examples presented in Table 1, the number of conjunctions in the DNF is always smaller
than the number of possible conditions in the hidden layer of the rule learning module. As
described in the Appendix C, the loss function of R2N contains sparsity regulation on the
weights of the literal learning, AND and OR-layer, controlling the sparsity of the resultant DNF.
To assess the role of the sparsity promoting parameter, , we trained the R2N for values of in
the range [
In this section we show the DNFs obtained with R2N and discuss how they are obtained. The
DNF associated to the learned rule model can be extracted directly from the binary weight matrix
W and w() , while the values of the learned literals are extracted from the weight matrix W() .
Since the values of W() are constrained with a sparsity penalty (see Appendix C), most values
are small, yet not strictly zero. We therefore threshold all the values that have a normalized
coeficient that is smaller than 2.5% of the magnitude of the largest coeficient in a predicate.
For instance, for example 5 in Table 1, the unprocessed output of R2N is given by,
This can be simplified by identifying and removing all the constant false ( ⊥) or true (⊤) predicates
(always true or false), e.g., 0.5 0 − 0.2 1 − 2 − 0.4 3 + 0.1 4 > −540 → ⊤, into,
This section describes the configuration settings for the three baselines: DR-Net [ 15], RIPPER
[6], and BRCG [
size 8000 and evaluated on a common test set of size 2000, and used the equi-quantile feature binarizer included in the BRCG repository3 with 40 bins.
For BRCG, we use the publicly available implementation from the AI Explainability 360 repository4. The algorithm uses two parameters 1 and 2 to penalize the learning of more and longer clauses respectively. We set 1 = 2 = 0.001, which is the default value recommended in the implementation. We also use the default values for the maximum number of iteration (100), maximum number of columns generated per iteration (10), and maximum degree (10) and width (5) parameters for the beam search.
For DR-Net we use the implementation by the authors5 with the default parameters except for the number of training epochs, which was increased from 2000 to 10000 according to the authors’ recommendation to learn sparse rules. For RIPPER, we used the wittgenstein implementation6. But instead of using its internal binarizer, we binarized it upfront using the aforementioned feature binarizer.
For evaluating the predictive accuracy for the synthetic examples in Table 1 in the main text we also report the values obtained from a MLP (Multi Layer Perceptron). We used a simple two layer architecture, with 10 neurons in the hidden layer, trained for 104 epochs with default optimizer parameters (Adam optimizer).
Data from which rule models are learned are oftentimes noisy and sparse. To assess the robustness of our approach w.r.t. number of training examples, we plot the prediction accuracy 3https://github.com/Trusted-AI/AIX360/blob/master/aix360/algorithms/rbm/features.py 4https://github.com/Trusted-AI/AIX360 5https://github.com/Joeyonng/decision-rules-network 6https://github.com/imoscovitz/wittgenstein/tree/master/wittgenstein with quantile binning with learned literals Number of conjunctions obtained with RIPPER by using quantile binning and the learned literals obtained from R2N for the 5 synthetic examples presented in Table 1 on the test set for Ex. 4 and 5 of Table 1 as function of the size of the training set (Fig. 3) and ifnd that, even for a training set size of (10 3)we obtain a good accuracy (> 0.95%). This shows that our method is not overly sensitive to the size of the training dataset, a common problem with neural-network based models.
Alternatively, when we add white noise to the data provided to the algorithm (randomly lfipping a fraction of the labels in the dataset) we find that for both examples the accuracy of the test-set approaches near-optimal accuracy up to noise levels of 10% (Fig. 3: The solid line indicates optimal performance, note that since the data is noisy, this line is the upper limit for the performance).
The relational literals that are learned by R2N can also serve in other applications as part of the domain vocabulary (or ontology); for instance as input literals for other rule learning algorithms, ensuring interoperability with existing rule learning workflows. To showcase how this can augment algorithms like RIPPER, we used the learned literals from R2N as input literals for RIPPER and found that for all synthetic examples in Table 1, the number of rules learned is considerably less as compared to RIPPER with univariate value comparisons. As we display in with an improvement in accuracy for 4 of the 5 cases (not shown in the table), demonstrating that the learned literals are not only specific to R2N but can also benefit other rule learning