Inductive rule learning is arguably among the most traditional paradigms in machine learning. Although we have seen considerable progress over the years in learning rule-based theories, all state-of-the-art learners still learn descriptions that directly relate the input features to the target concept. It could nevertheless be the case that more structured representations, which form deep theories by forming intermediate concepts, could be easier to learn, in very much the same way as deep neural networks are able to outperform shallow networks, even though the latter are also universal function approximators. In this paper, we investigate into networks with weights and activations limited to the values 0 and 1. For the lack of a powerful algorithm that optimizes deep rule sets, we empirically compare deep and shallow rule networks with a uniform general algorithm, which relies on greedy mini-batch based optimization. Our experiments on both artificial and realworld benchmark data indicate that deep rule networks may outperform shallow networks.
Dating back to the AQ algorithm [
In this paper, we argue that one of the key factors for
the strength of deep learning algorithms is that latent
variables are formed during the learning process. However,
while neural networks excel in implementing this ability
in their hidden layers, which can be effectively trained via
backpropagation, there is essentially no counter-part to this
ability in inductive rule learning. We therefore set out to
verify the hypothesis that deep rule structures might be
easier to learn than flat rule sets, in very much the same way as
deep neural networks have a better performance than
singlelayer networks [
The remainder of the paper is organized as follows:
Sect. 2 elaborates why deep rule learning is of
particular interest and refers to related work. We propose a new
network approach in Sect. 3 and test it in Sect. 4. The
results are concluded in Sect. 5, followed by possible
future extensions and improvements in Sect. 6. An extended
version of this paper containing an elaborate discussion of
related work, more details on the methods, and additional
experiments is available as [
Rule learning algorithms typically provide flat lists that directly relate the input to the output. Consider, e.g., the following example: the parity concept, which is known to be hard to learn for heuristic, greedy learning algorithms, checks whether an odd or an even number of R relevant attributes (out of a possibly higher total number of attributes) are set to true. Figure 1a shows a flat rulebased representation1 of the target concept for R = 5, which requires 2R 1 = 16 rules. On the other hand, a structured representation, which introduces three auxiliary predicates (parity2345, parity345 and parity45 as shown in Figure 1b), is much more concise using only 2 (R 1) = 8 1We use a Prolog-like notation for rules, where the consequent (the head of the rule) is written on the left and the antecedent (the body) is written on the right. For example, the first rule reads as: If x1, x2, x3 and x4 are all true and x5 is false then parity holds. parity :- x1, x2, x3, x4, not x5. parity :- x1, x2, not x3, not x4, not x5. parity :- x1, not x2, x3, not x4, not x5. parity :- x1, not x2, not x3, x4, not x5. parity :- not x1, x2, not x3, x4, not x5. parity :- not x1, x2, x3, not x4, not x5. parity :- not x1, not x2, x3, x4, not x5. parity :- not x1, not x2, not x3, not x4, not x5. parity :- x1, x2, x3, not x4, x5. parity :- x1, x2, not x3, x4, x5. parity :- x1, not x2, x3, x4, x5. parity :- not x1, x2, x3, x4, x5. parity :- not x1, not x2, not x3, x4, x5. parity :- not x1, not x2, x3, not x4, x5. parity :- not x1, x2, not x3, not x4, x5. parity :- x1, not x2, not x3, not x4, x5. (a) A flat unstructured rule set for the parity concept :- x4, x5.
:- not x4, not x5. parity345 :- x3, not parity45. parity345 :- not x3, parity45. parity2345 :- x2, not parity345. parity2345 :- not x2, parity345. parity parity :- x1, not parity2345.
:- not x1, parity2345. (b) A deep structured rule base for parity using three auxiliary predicates rules. We argue that the parsimonious structure of the latter could be easier to learn because it uses only a linear number of rules, and slowly builds up the complex target concept parity from the smaller subconcepts parity2345, parity345 and parity45.
To motivate this, we draw an analogy to neural network learning, and view rule sets as networks. Conventional rule learning algorithms learn a flat rule set of the type shown in Figure 1a, which may be viewed as a concept description in disjunctive normal form (DNF): Each rule body corresponds to a single conjunct, and these conjuncts are connected via a disjunction (each positive example must be covered by one or more of these rule bodies). This situation is illustrated in Figure 2a, where the 5 input nodes are connected to 16 hidden nodes - one for each of the 16 rules that define the concept - and these are then connected to a single output node. Analogously, the deep parity rule set of Figure 1b may be encoded into a deeper network structure as shown in Figure 2b. Clearly, the deep network is more compact and considerably sparser in the number of edges. Of course, we need to take into consideration that the optimal structure is not known beforehand and presumably needs to emerge from a fixed network structure that offers the possibility for some redundancy, but nevertheless we expect that such structured representations offer similar advantages as deep neural networks offer over single-layer networks.
It is important to note that deep structures do not
increase the expressiveness of the learned concepts. Any
formula in propositional logic (and we limit ourselves to
propositional logic in this project) can be converted to a
DNF formula. In the worst case (a so-called full DNF),
each of the input variables appears exactly once in all of
the inputs, which essentially corresponds to enumerating
all the positive examples. Thus, the size of the number of
conjuncts in a DNF encoding of the inputs may grow
exponentially with the number of input features. This is in many
ways analogous to the universal approximation theorem [
For our studies of deep and shallow rule learning, we define
rule-based theories in a networked structure, which we
describe in the following. We build upon the shallow
twolevel networks we have previously used for experimenting
with mini-batch rule learning [
A conventional rule set consisting of multiple conjunctive rules that define a single target concept, corresponds to a logical expression in disjunctive normal form (DNF). An equivalent network consists of three layers, the input layer, one hidden layer (= AND layer) and the output layer (= OR layer), as, e.g., illustrated in Figure 2a. The input layer receives one-hot-encoded nominal attribute-value (a) shallow representation (b) deep representation pairs as binary features (= literals), the hidden layer conjuncts these literals to rules and the output layer disjuncts the rules to a rule set. The network is designed for binary classification problems and produces a single prediction output that is true if and only if an input sample is covered by any of the rules in the rule set.
For generalizing this structure to deeper networks, we need to define multiple layers. While the input layer and the output layer remain the same, the number and the size of the hidden layers can be chosen arbitrarily. Note that we can still emulate a shallow DNF-structure by choosing a single hidden layer. In the more general case, the hidden layers are treated alternately as conjunctive and disjunctive layers. We focus on layer structures starting with a conjunctive hidden layer and ending with a disjunctive output layer, i.e. networks with an odd number of hidden layers. In this way, the output will be easier to compare with rule sets in DNF. Furthermore, the closer we are to the output layer, the more extensive are the rules and rule sets, and the smaller is the chance to form new combinations from them that are neither tautological nor contradictory. As a consequence, the number of nodes per hidden layer should be lower the closer it is to the output layer. This makes the network shaped like a funnel. 3.2
In the following, we assume the network to have n + 2 layers, with each layer i containing si nodes. Layer 0 corresponds to the input layer with s0 = jxj and layer n + 1 to the output layer with sn+1 = 1. Furthermore, a weight w(jik) is identified by the layer i it belongs to, the node j from which it receives the output, and the node k in the successive layer i + 1 to which it passes the activation. Thus, the weights of each layer can be represented by an si si 1-dimensional matrix W (i) = [w(jik)]. In total, there are åi=0 sisi+1 Boolean n weights which have to be learned, i.e., have to be set to true (resp. 1) or false (resp. 0). If weight w(jik) is set to true, this means that the output of node j is used in the conjunction (if i mod 2 = 0) or disjunction (if i mod 2 = 1) that defines node k. If it is set to false, this output is ignored by node k.
In the beginning, these weights need to be initialized. This initialization process is influenced by two hyperparameters: average rule length (l¯) and initialization probability (p), where l¯ only affects the number of weights that are set to 1 in the first layer. Here we use the additional information which literals belong to the same attribute to avoid immediate contradictions within the first conjunction. Let jA j be the number of attributes, then each attribute is selected with the probability l¯=jA j so that on average for l¯ literals of different attributes the corresponding weight will be set to true. In the remaining layers, the weights are set to true with the probability p. Additionally, at least one outgoing weight from each node will be set to true to ensure connectivity. This implies that, regardless of the choice of p, all the weights in the last layer will always be initialized with true because there is only one output node. Note that, as a consequence, shallow DNF-structured networks will not be influenced by the choice of p, since they only consist of the first layer influenced by l¯ and the last layer initialized with true. The prediction of the network can be efficiently computed using binary matrix multiplications ( ). In each layer i, the input features A(i) are multiplied with the corresponding weights W (i) and aggregated at the receiving node in layer i + 1. If the aggregation is disjunctive, this directly corresponds to a binary matrix multiplication. According to De Morgan’s law, a ^ b = :(:a _ :b) holds. This means that binary matrix multiplication can be used also in the conjunctive case, provided that the inputs and outputs are negated before and after the multiplication. Because of the alternating sequence of conjunctive and disjunctive layers, binary matrix multiplications and negations are also always alternated when passing data through the network, so that a binary matrix multiplication followed by a negation can be considered as a NOR-node. Thus, the activations A(i+1) can be computed from the activations in the previous layers as A(i+1)
A˜(i)
W (i) (1) where X˜ = J X denotes the element-wise negation of a matrix X (J denotes a matrix of all ones). Hence, internally, we do not distinguish between conjunctive and disjunctive layers within the network, but have a uniform network structure consisting only of NOR-nodes. However, for the sake of the ease of interpretation, we chose to represent the networks as alternating AND and OR layers.
In the first layer, we have the choice whether to start with a disjunctive layer or a conjunctive one, which can be controlled by simply using the original input vector (A(0) = x) or its negation (A(0) = x˜) as the first layer. Also, if the last layer is conjunctive, an additional negation must be performed at the end of the network so that the output has the same ”polarity” as the target values. In our experiments, we always start with a conjunctive and end with a disjunctive layer. In this way, the rule networks can be directly converted into conjunctive rule sets. 3.4
Following [
When all mini-batches are processed, the procedure is repeated for a fixed number of epochs. Only the composition of the mini-batches is changed in each epoch by shuffling the training data before proceeding. After all epochs, the weights of the networks are reset to the optimum found so far, and a final optimization on the complete training set is conducted to eliminate any overfitting on mini-batches. The returned network can then be used to predict outcomes of any further test instances. 4
In this section we present the results of differently structured rule networks on both artificial and real-world UCI datasets, with the goal of investigating the effect of differences in the depth of the networks. 4.1
As many standard UCI databases can be solved with very
simple rules [
We use a dataset of ten Boolean inputs named a to j and generate all possible 210 combinations as training or test samples. These samples are extended by the ten negations :a to : j via one-hot-encoding and finally passed to a funnel-shaped deep rule network with n = 5 and s = [32; 16; 8; 4; 2]. The weights of the network are set by randomly initializing the network and then training it on two randomly selected examples, one assigned to the positive and one to the negative class, to ensure both a positive and negative output is possible. If the resulting ratio of positively predicted samples is still less than 20% or more than 80%, the network is reinitialized with a new random seed to avoid extremely imbalanced datasets. 4.2
We first conducted a few preliminary experiments on three
of the artificial datasets to set suitable default values for the
hyperparameters of the deep and shallow networks. The
detailed grid search including figures comparing different
hyperparameter settings are presented in the extended
version of this paper [
In the main experiments, we use a combination of 15 artificial datasets with seeds we already used in the prior hyperparameter grid search and 5 artificial datasets with new seeds to detect potential overfitting on the first datasets. All datasets are tested using five epochs, a batch size of 50 and an unlimited number of flips per batch. We also ensured for all of the generated datasets that the DNF concept does not contain more than 20 rules, so that it can be theoretically also be learned by the tested shallow network with s1 = 20 (and therefore also for the two deep networks, since their first layer is already bigger).
Figure 3 shows the development of the accuracies on the training set averaged on all 20 datasets over the number of processed mini-batches, whereby after every ten mini-batches a new epoch starts. The base accuracy before processing the first mini-batch and after the full batch optimization are omitted. We can see that the deep networks not only deliver higher accuracies but they also converge slightly faster than the shallow one. The orange curve of DRNC(3) runs a little higher than the blue one of DRNC(5), whereas the green curve of RNC has some distance to them, especially during the first two epochs.
Table 1 shows the accuracies of the three networks. For each dataset, the best accuracy of the three network classifiers is highlighted in bold. We can see a clear advantage for the two deep networks both when considering the average accuracy and the amount of highest accuracies. The results clearly show that the best performing deep networks outperform the best performing shallow network in all but 4 of the 20 generated datasets. Both the average rank and the average accuracy of the deep networks is considerably better than the corresponding values for RNC. This also holds for pairwise comparisons of the columns (DRNC(5) vs. RNC 15:5, DRNC(3) vs. RNC 15:5).
The Friedman-test for the ranks yields a significance of more than 95%. A subsequent Nemenyi-Test delivers a critical distance of 0.741 (95%) or 0.649 (90%), which shows that DRNC(3) and RNC are significantly different on a level of more than 95% and DRNC(5) and RNC on a level of more than 90%. The corresponding critical distance diagram (CD=0.741) is shown in Figure 4. We thus find it safe to conclude that deep networks outperform shallow networks on these datasets.
In the two right-most columns of Table 1 we also show
a comparison to the state-of-the-art rule learner RIPPER
[
For an estimation how the rule networks perform on
realworld datasets, we select nine classification datasets
(carevaluation, connect-4, kr-vs-kp, monk 1-3, mushroom,
tictac-toe and vote ) from the UCI Repository [
The results are shown in Table 2. We can again observe
that the deep 5-layer network DRNC(5) outperforms the
shallow network RNC. Of all rule networks, DRNC(5)
provides the highest accuracy on the connect-4, monk-1,
monk-3, mushroom and vote datasets, whereas DRNC(3)
performs best on car-evaluation and monk-2 and RNC on
kr-vs-kp and tic-tac-toe. The latter two datasets are also
interesting: tic-tac-toe clearly does not require a deep
structure, because for solving it, the learner essentially needs
to enumerate all three-in-a-row positions on a 3 3 board.
This is similar to connect-4, where four-in-a-row positions
have to be recognized. However, in the former case, there
is only one matching tile for an intermediate concept
consisting of two tiles, while in connect-4 there are several,
which can potentially be exploited by a deeper network. In
the kr-vs-kp dataset, deep structures are also not helpful
because it consists of carefully engineered features for the
KRKP chess endgame, which were designed in an iterative
process so that the game can be learned with a decision
tree learner [
Our experiments on both artificial and real-world benchmark data indicate that deep rule networks outperform shallow networks. The deep networks obtain not only a higher accuracy, but also need less mini-batch iterations to achieve it. Moreover, in preliminary experiments in the hyperparameter grid search, we have seen indications that the deep networks are generally more robust to the choice of the hyperparameters than shallow networks. On the other hand, we also had some cases on real-world data sets where deep networks failed because a poor initialization resulted in indiscriminate predictions.
Overall, we interpret these results as evidence that an investigation of deep rule structures is a promising research goal, which we hope could yield a similar boost in performance in inductive rule learning as could be observed by moving from shallow to deep neural networks. However, this goal is still far ahead. 6
In this work, it was not our goal to reach a state-of-the-art predictive performance, but instead we wanted to evaluate a very simple greedy optimization algorithm on both shallow and deep networks, in order to get an indication on the potential of deep rule networks. Nevertheless, several avenues for improving our networks have surfaced, which we intend to explore in the near future.
One of the main drawbacks of the presented deep rule networks is the extremely high runtime due to the primitive flipping algorithm. A single flip needs a recalculation of all activations in the network, even if only a few them will be affected by this flip whereby the matrix multiplication could be minimized considerably. Conversely, this knowledge can be used to find a small subset of flips that affects a certain activation. On the other hand, the majority of possible flips does not have any effect on this activation or the accuracy at all. This effect will typically remain unchanged after a few more flips are done. Therefore an exhaustive search of all flips is only needed in the first iteration, while afterwards just a subset of possible flips should be considered which can be built either in a deterministic or probabilistic way.
Due to this lack of backpropagation, the flips are evaluated by their influence on the prediction when executed. However, when looking at a false positive, we can only correct this error by making the overall hypothesis of the network more specific. In order to achieve a generalization of the hypothesis, only flips from false to true in conjunctive layers or flips from true to false in disjunctive layers have to be taken into account. In this way, all flips are split into ”generalization-flips” and ”specialization-flips” of which only one group has to be considered at the same time. This improvement as well as the above mentioned selection of a subset of flips might also allow us to perform two or more flips at the same time so that a better result than with the greedy approach can be achieved.
An even more promising approach starts one step
earlier in the initialization phase of the network. Instead of
specifying the structure of the network and finding optimal
initialization parameters l¯ and p for it, a small part of the
data could be used to create a rough draft version of the
network. The Quine-McCluskey algorithm [
All these approaches share some significant advantages over the network approach we developed so far. First of all, the decision which class value will be treated as positive or negative does not have to be made manually any longer. Second, they automatically deliver a suitable initialization of the network, which otherwise would have to be improved by similar approaches like used in neural networks [e.g., 14] to achieve a robust performance. Third, the general structure of the network is not limited to a fixed size and depth where each node is strictly assigned to a specific layer. Instead of generating nodes that become useless after a few flips have been processed and that should be removed, we can thereby start with a small structure which can be adapted purposefully by copying and mutating good nodes and pruning bad ones. However, it remains unclear whether these changes still lead to improvements in performance or if the network in the given structure is already optimal. Acknowledgments. We are grateful to Eneldo Loza Mencía, Michael Rapp, Eyke Hüllermeier, and Van Quoc Phuong Huynh for inspiring discussions, fruitful pointers to related work, and for suggesting the evaluation with artificial datasets.