We discuss how to extract symbolic rules from a given binary threshold feed-forward network. The proposed decompositional approach is based on an internal representation using binary decision diagrams. They allow for an e cient composition of the intermediate results as well as for an easy integration of integrity constraints into the extraction. We also discuss some experimental results indicating a good performance of the approach.
During the training process, neural networks acquire knowledge by generalising from raw data. Unfortunately, this learnt knowledge is hidden in the weights associated to the connections and humans have no direct access to it. One goal of rule extraction is the generation of a human-readable description of the output units behaviour with respect to the input units. Usually, the result is described in form of if-then rules, giving conditions that activate (or inactivate) a given output unit. Rule extraction from connectionist systems is still an open research problem, even though a number of algorithms exists. For an overview of di erent approaches we refer to [Andrews et al., 1995] and [Jacobsson, 2005]. Extraction techniques can be divided into pedagogical and decompositional approaches. While the rst conceives the network as a black box, the latter decomposes the network, constructs rules describing the behaviour of the simpler parts, and then re-composes those results.
In [Bader et al., 2007], we proposed the CoOpalgorithm, a decompositional approach for the extraction of propositional rules from feed-forward neural networks. Here, we discuss an extension of this approach. In this new extension, binary decision diagrams (BDD) are used to store intermediate results, i.e., rules extracted from single units (perceptrons). This representation has three advantages: 1. results are stored in a very compact form, 2. intermediate results can easily be combined, and 3. integrity constraints can easily be incorporated. 2
In this section, we introduce some necessary concepts. After de ning feed-forward neural network and the ruleextraction problem, we discuss binary decision diagrams.
Feed-forward arti cial neural networks (ANNs), also called connectionist systems, consist of simple computational units (neurons) which are connected. The set of units U together with the connections C U U form an acyclic directed graph. In this paper we concentrate on networks with units applying the 1-threshold function. Such a neural network can be represented as a 6-tuple hU; Uinp ; Uout ; C; !; i. Uinp ; Uout U denote input and output units of the network, i.e., are sources and sinks of the underlying graph. The functions ! : C ! R assign a weight to every connection and : U ! R a threshold to every unit. Every unit u has an activation value actu 2 f 1; +1g which is set from outside for input units, or computed based on the activation value of its predecessor units and the threshold (u) as follows: 1
c=(v;u)2C actv !(c) otherwise (u) Figure 1 shows a simple network serving as running example throughout the paper.
Because every unit can be active (actu = +1) or inactive (actu = 1) only, we can associate a propositional variable u to it, which is assumed to be true if and only if the unit u is active, and we use u to denote the negation of u. Furthermore, we can characterise network inputs as interpretations I Uinp of the propositional variables Uinp . We use actu(I) to denote the state of unit u if all input units contained in I are active and all other input units are inactive. Using this notation, we can de ne the rule extraction problem as follows: The rule extraction problem for a given node u of a feed-forward a b 0 d 2 e 4 f 4 4 2 g h ! a b c d e f c d e f threshold network hU; Uinp ; Uout ; C; !; i is the construction of a propositional formulae F over Uinp such that for all interpretations I we nd actu(I) = +1 if I j= F 1 otherwise I.e., we are looking for propositional formula stating necessary and su cient conditions (in terms of the activation of input units) such that the unit u is active.
Usually not all input combinations make sense in a given application domain, because some of them would correspond to invalid states of the world. We use the term valid inputs to denote the set of allowed input combinations. Even more important for the extraction is the fact that all training samples are taken from this subset. Therefore, the network learns to solve a task under the implicit conditions hidden in the selection of inputs. Integrity constraints are a way to make those conditions explicit during the extraction. An integrity constraint is a formula IC over Uinp describing the set of valid inputs V P(Uinp ) as follows: For all I Uinp we nd I j= IC if and only if I 2 V . Using integrity constraints, we can reformulate the extraction problem as follows: The rule extraction problem for a given network N and a given integrity constraint IC is the construction of a propositional formulae F over Uinp such that for all interpretations I with I j= IC we nd
Networks can be decomposed into their basic building blocks, namely single units together with their incoming connections. Those single units can be seen as simple sub-networks (perceptrons) consisting of a number of inputs and a single output unit, together with the corresponding weighted connections. To simplify the notations we use Pp = h ; I; !i to denote the perceptron corresponding to the unit p together with its threshold , the set of predecessor units I and the weight function !. Figure 2 shows the perceptron for the output unit g.
Binary decision diagrams (BDD) are a data structure to represent propositional formulae in a very compact way and to manipulate them easily. A nice introduction
Pg = h ; I; !i with
= 4 I = fc; d; e; f g 81 if x = c ><>2 if x = d >3 if x = e > :5 if x = f pf(2) = (b ^ ?) _ (:b ^ >) = :b pf(3) = (b ^ >) _ (:b ^ ?) = b pf(4) = (a ^ :b) _ (:a ^ b) can be found for example in [Andersen, 1999]. Intuitively, a BDD is a directed acyclic graph with a variable associated to every node and such that all nodes n 6= 0; 1 have exactly two successors, called high and low branch of n. The nodes 0 and 1 are the sinks of the graph. We use h ; 0; 1; R; N i to refer to a BDD with sinks 0 and 1, a set of nodes N and a root-node with identi er R. And we use hi; v; h; li to denote the node with identier i, with variable v = var(i), and with high and low branch pointing to the nodes with identi ers h and l, respectively.
Usually a BDD is assumed to be ordered and reduced. It is called ordered i there exists a linear order on the variables and the successors of a node are marked with variables that are bigger with respect to . It is called reduced if no two nodes for the same variable have identical high and low branch, and for no node high and low-branch coincide.
BDDs represent propositional formulae in if-then-else normal form. The corresponding formula for a given node is de ned recursively as follows: pf(0) := ?
pf(1) := > pf(i) := (var(i) ^ pf(h)) _ (: var(i) ^ pf(l))
From Perceptrons to Search Trees In this section, we discuss an algorithm to extract a BDD from a single unit such that the BDD represents necessary and su cient condition on the inputs to turn the unit active. Following [Bader et al., 2007], we de ne input patterns I as subsets of the inputs I of a given perceptron Pp = h ; I; !i which are assumed to be active. The inputs not contained in I can be either active or inactive. And we de ne the corresponding minimal input imin(I) as follows: imin(I) =
X !(a) a2I
X j!(a)j a2InI The minimal input is computed by adding the contribution of the xed inputs Pa2I !(a) and the minimal input caused by all other inputs. A perceptron is called positive, if all weights are positive. For the following constructions, we assume the perceptrons to be positive. In Section 5, we discuss how to apply the extraction to arbitrary perceptrons.
The construction of BDDs below is based on the search trees described in [Bader et al., 2007]. These search trees contain a node for every possible input pattern. Children of a given node correspond to input patterns which contain exactly one symbol more and all nodes are sorted with respect to their minimal inputs. If the minimal input of some node exceeds the threshold, that node is marked (I.e., the corresponding input pattern represents a su cient condition to turn the perceptron active). The complete tree is pruned by removing all those nodes for which no descendant is marked and all those nodes which are descendants of marked nodes. The construction of a pruned tree is shown in Algorithm 1. Figure 4 shows the full and the resulting pruned search tree on top of it.
Input: A positive perceptron Pp+.
Output: A pruned search tree. 1 Fix an order such that b c if !(b) !(c). 2 Create a root node for the empty input pattern. 3 Add a child labelled x for each input symbol x (sorted wrt. ). 4 foreach newly added node labelled y do 5 Add a new child c for every symbol z with y z (sorted wrt. ). 6 Label c with the corresponding pattern I. 7 Mark c if imin(I) > (p). 8 Remove all descendants of marked nodes. 9 Remove all nodes for which no descendant is marked.
Algorithm 1: Constructing a pruned search tree.
Exploiting the structure of these search trees, we can easily construct BDDs representing conditions to turn the perceptron active. I.e., we nd the perceptron to be active for all those input patterns which, understood as interpretation, turn the logic formula corresponding to the BDD true. e 5 fe;fg d
3 c 1 fd;fg fc;fg
-1 fd;eg c -3 fc;eg d
9 c 7 c 5 fd;e;fg fc;e;fg fc;d;fg c 1
fc;d;eg c 11 fc;d;e;fg 1 e -5 feg d
-7 fdg c -5 fc;dg c -9 fcg Before presenting an algorithm to construct BDDs from a given pruned search tree, we introduce some further notations. Every node in the search tree is represented as a pair hI; Ci with I being the corresponding input pattern and C being the set of children. id(n) denotes a unique identi er for the node n (e.g., the corresponding input pattern, or some index), this identi er is also used as internal index for the BDD nodes. We assume id(n) := 0 if there is no node n. var(n) denotes the symbol which is added to the input pattern at node n.
The construction of a BDD for a given search tree is shown as Algorithm 2. This algorithm transforms a search tree into a BDD, by traversing the tree in a leftdepth- rst manner. A node's high branch points to 1, if its minimal input exceeds the threshold. Otherwise, it points to its left-most child, or to 0 if there is no child. The low-branch points to the right sibling, or to 0 if there is none. The result for the perceptron Pg is shown in Figure 5. foreach other non-root node hI; Ci do
Add a node hid(n); var(n); id(c); li to N for the leftmost child c and l = id(rn) for the right sibling rn of n and l = 0 if there is none
Algorithm 2: Constructing a BDD.
Please note, that the BDD can be constructed without constructing the search tree rst. The tree is used only to describe the underlying ideas. All conditions tested in Algorithm 2 can be tested by expanding the tree stepby-step. Looking a little closer at the constructed search tree we nd that some sub-trees have an identical internal structure, which is exempli ed in Figure 6. If the condition tested in Line 13 of Algorithm 2 is ful lled, two neighbouring sub-trees are structured identically. mci(n) denotes the minimum of all minimal inputs associated to nodes below n. Please note, that mci(n) can be computed without expanding the sub-tree by looking at the associated input pattern.
The mentioned structural equivalence can be exploited by using a shortcut into the already constructed BDD and thus preventing the expansion of an identical subtree. Figure 6 contains a number of those shortcuts, e.g., one from node fbg to the node fc; ag, because the children of fbg are annotated the same way as the node below and right of fc; ag. Please note that this identity can be recognised without expanding the second subtree, i.e., the construction of whole tree below fbg can be avoided.
The condition on Line 13 is ful lled whenever the perceptron shows a so called n-of-m behaviour, i.e., if there are m inputs from which n su ce to turn the perceptron active. In this case, there will be n equivalent subtrees, which can be shortcut. As discussed in [Towell and Shavlik, 1993], this occurs quite frequently while training neural networks. g a b h a b 0 1 In the previous section, we have been concerned with positive perceptrons only. But we can easily turn every perceptron into a positive one, by multiplying negative weights by 1 and inverting the corresponding input symbols. By doing so, we can apply the algorithm to all output units of a given network, and obtain a BDD describing necessary conditions with respect to the predecessor units that turn the output unit active. But some of the input symbols may have been inverted. I.e., we need another algorithm to construct BDDs stating conditions which turn a perceptron inactive. Due to the symmetry of the threshold function, we nd this algorithm to be dual to Algorithm 1 and 2. I.e., by inverting the order and the inequalities we obtain an algorithm that constructs such a BDD.
Once we have extracted the BDD for a given output unit, we can continue by substituting the nodes testing non-input nodes (i.e., nodes not corresponding to input units of the network) by their corresponding BDDs. A non-negated node is replaced by the BDD as constructed above, and negated nodes are replaced by the dual BDDs. As mentioned above, BDDs have been designed to allow for an e cient manipulation of logic formulae. And in fact it is straightforward to compose the intermediate results into an overall diagram by simply replacing the nodes. But this is not the best approach, because the resulting `global' BDD would not be ordered any more. But while expanding the BDD, we can keep it ordered (and reduced) as described in [Andersen, 1999]. After expanding all non-input nodes, we obtain a nal BDD representing necessary and su cient conditions on the network's input to turn a given output unit active.
Using BDDs as internal data structure has some further advantages. We can actually extract all output units into the same global BDD. Doing so leads automatically to a sharing of intermediate results, because common substructures are contained only once within this BDD. Figure 7 shows the nal `global' BDD for the network from Figure 1. Please note that the right node labelled b is used for both output units g and h.
Furthermore, we can integrate integrity constraints in a straightforward fashion. Instead of starting with an empty BDD, we extract the output nodes into a BDD representing the integrity constraints. To exemplify this, a network has been trained to the Encode-Decoder task. It contains 8 input, 8 output units and 3 hidden units and is trained to learn the identity mapping for all inputs in which exactly one unit is active. I.e., the network has to learn a compressed representation within the hidden layer. But applying the algorithm presented above yields an unwanted result shown in Figure 8 on the left. Using the integrity constraint that at most one input is active at a time yields the BDD shown on the right. 900 nodes have to be constructed (including all intermediate results while constructing the BDD) for the `normal' BDD, but only 124 while using the integrity constraint. This shows the advantage of using integrity constraints right from the beginning of the extraction process. Usually they are used to re ne the extraction result afterwards. This would be possible here as well by simple computing the conjunction of the `normal' BDD with one representing the integrity constraint. But starting with the constraint avoids the construction of many intermediate nodes which would be removed afterwards. 6
To evaluate the approach a Prolog implementation has been used to gather some statistics. The results are shown in Table 1. The table shows average numbers for di erent numbers of inputs, the size of the full search tree, the number of minimal input patterns, the size of the corresponding BDD and the number of BDD nodes per input pattern. All numbers have been collected from 100 random perceptrons per size. The extraction using the full search tree is not feasible due to the exponential growth. The number of input patterns is a conservative lower bound for the size of the pruned search tree, because those trees have at least one node per minimal input pattern. The result shows that the use of BDD proposed here yields a very compact representation. Even though the number of nodes in the BDD grows, the ratio (node/IP) of size of the BDD and the number of minimal coalitions decreases. i4 i4 i4 i4 i4 i4 i4 i5 i6 i5 i6 i7 i5 i6 i7 i3 i5 i6 i7 i2 i3 i5 i6 i7 i8 o1 i1 i2 i3 i5 i6 i7 i8 i3 i5 i6 i7 i5 i6 i7 i5 i6 i7 i5 i6 o1 i1 i2 i3 i4 i5 i6 i7 i8 1 0 0 1 jBDDj 111 5 92 output units has been used for the experiment. The possible inputs have been constrained by a maxn integrity constraint for 0 n 6. The results are presented in Figure 9. For every n the experiment has been conducted for the same 100 randomised networks and the following numbers have been collected: the size of the sub-BDD encoding the constraint, the minimal, maximal and average size of the nal BDD. Please note that the numbers show the total number of internal nodes constructed for the BDD, i.e., including all necessary intermediate nodes. For n = 1, i.e., the biggest restriction, we obtain very small BDDs. The size of the BDD grows up to n = 4 and decreases again for n > 4. From those observations we can conclude that the incorporation of integrity constraints into the extraction process can lead to big savings in terms of nodes constructed for the nal BDD. Without their use during the extraction, we would have to construct the BDD corresponding to n = 6. This big BDD of 400 nodes would have to be re ned with respect to the constraints afterwards. There seem to be cases (e.g., for n = 4) where the use of integrity constrain yields larger BDDs, but nonetheless, the nal BDD does not have to be revised afterwards, and the di erence is not too big. 7
Conclusions and Future Work A novel approach for the extraction of propositional rules from feed-forward networks of threshold units has been presented. After decomposing the network into perceptrons, binary decision diagrams representing preconditions that activate or inactivate the perceptron have been extracted. Those intermediate representations can be composed using the usual algorithms for BDDs, or they can be combined during their construction by extracting one into the other. The latter approach does also allow for an incorporation of integrity constraints { already during the extraction of the intermediate results. As already mentioned in [Bader et al., 2007], the pruned search trees constructed above are related to the approach presented in [Krishnan et al., 1999]. But due to a di erent order, we do not need to expand them completely, which would otherwise be necessary.
The extraction as presented here is applicable to all feed-forward networks composed of binary threshold units computing 1-threshold function. This limitation can be softened by allowing arbitrary symmetric threshold functions. The symmetry is necessary to construct negative and positive forms of the perceptron without changing the global network function.
Finally, we discussed rst experimental results indicating a good performance of the approach. On the one hand, we obtain a very compact representation and on the other hand, we circumvent the construction of non-necessary intermediate results while incorporating integrity constraints right from the start.
Nonetheless, much remains to be done. In particular, the extraction for non-threshold units has to be studied. For the encoder-decoder experiments mentioned above the algorithm has simply been applied to networks computing the symmetric hyperbolic tangent as activation function. Interestingly, the result coincide with our expectations. This is due to the fact, that networks when trained to compute crisp decisions tend to behave like threshold networks. But the details of this need to be investigated in the future. Furthermore, a detailed analysis of the performance is necessary, in particular using networks trained for real-world problems. The approach as presented here detects equivalent sub-BDDs for nof-m patterns. But there are more cases for equivalent sub-BDDs [Mayer-Eichberger, 2008]. Those have to be integrated into the extraction procedure. It would also be interesting to study the evolution of a network during the training process by repeatedly applying the extraction method and compare the results.
Acknowledgements The author is thankful for the comments of Valentin Mayer-Eichberger and two anonymous reviewers.