Motivated by basic ideas from formal concept analysis, we propose two ways to directly encode closure operators on finite sets in a 3-layered feed forward neural network. ∗Sebastian Rudolph is supported by the Deutsche Forschungsgemeinschaft (DFG) under the ReaSem project.
The scientific interest in the integration of symbolic
methods based on computational logic with artificial neural
networks (also known as connectionist systems) has grown
significantly in the last years. As a motivating goal of those
efforts appears to combine the advantages of both approaches:
While symbolic systems are superior in dealing (i.e.,
representing and reasoning) with structured data, connectionist
systems
The well-known neural-symbolic learning cycle
In Section 2 we will introduce the basic notions closure operator and implication and show their correspondence. Section 3 will sketch the elementary ideas of formal concept analysis, based on which we will unfold our representation approach. Very briefly, Section 4 will recall the notion of a 3-layered feedforward network. Section 5 then combines the approaches and provides two ways of encoding a formal context’s closure operator into a neural network of the specified kind. In Section 6, we show how the approach can be applied to propositional logic programs, where it can be used to compute models. Finally, in Section 7, we conclude and give topics for ongoing research. 2
In this section, we will introduce two notions – closure operator and implications – and show their tight correspondence.
The following considerations are based on an arbitrary set M . Intuitively, it may be conceived as a set of features or attributes or atomic propositions, depending on the modelled problem. Many of the definitions and theoretical results presented in this and the next section apply to arbitrary sets, however, when it comes to questions of practical realization and computability, finiteness of M has to be presumed.
We will first define the fundamental notion of a closure operator. Roughly speaking, applying such an operator to a set can be understood as a minimal extension of that set in order to fulfill certain properties.
Definition 1 Let M be an arbitrary set. A function ϕ : P (M ) → P (M ) (where P (M ) denotes the powerset of M ) will be called • EXTENSIVE, if A ⊆ ϕ(A) for all A ⊆ M , • MONOTONE, if from A ⊆ B follows ϕ(A) ⊆ ϕ(B) for all A, B ⊆ M , and • IDEMPOTENT, if ϕ(ϕ(A)) = ϕ(A) for all A ⊆ M . If ϕ is extensive, monotone, and idempotent, we will call it a CLOSURE OPERATOR. In this case, we will additionally call • ϕ(A) the CLOSURE of A, • A CLOSED, if A = ϕ(A).
The family of all closed sets is also called CLOSURE SYSTEM. Furthermore, any closure system constitutes a lattice with set inclusion as the respective order relation.
Mark that the notion of a closure operator is rather intuitive in both human associative thinking and classical (at least monotonic) logics.1
In the sequel, we show, in which way closure operators are closely related to implications.
Definition 2 Let M be an arbitrary set. An IMPLICATION on M is a pair (A, B) with A, B ⊆ M . To support intuition, we write A _ B instead of (A, B).2
For C ⊆ M and a set I of implications on M , let CI denote the smallest set with C ⊆ CI that additionally fulfills
A ⊆ CI implies B ⊆ CI for every implication A _ B in I.3 If C = CI, we call C I-CLOSED.
It is well known that for a given set A ⊆ M and implication
set I, AI can be computed in linear time with respect to |I|
An elementary observation from logic becomes particularly obvious in this setting: a contradiction implies everything. Thus, if, say, two elements a, b ∈ M are contradictory, this can be expressed by the implication {a, b} _ M . In the sequel, we will use the shorthand a, b _ ⊥ for these special cases. 3
The mathematical theory of formal concept analysis mainly deals with conceptual hierarchies which are generated from basic data structures encoding object-attribute relationships. Thereby, it provides a rather applied access to lattice theory For a comprehensive introduction into formal concept analysis, see [Ganter and Wille, 1997].
In this section, we sketch the basic definitions and some results from formal concept analysis, as far as they are needed for this work. We start by defining the central underlying data structure.
Definition 3 A (FORMAL) CONTEXT K is a triple (G, M, I ) with • an arbitrary set G called OBJECTS, • an arbitrary set M called ATTRIBUTES, • a relation I ⊆ G × M called INCIDENCE RELATION We read gI m as: “object g has attribute m”.
1For example, in classical first order logic, taking the set of all consequences cons(Φ) := {ϕ | Φ |= ϕ} of a formula set Φ is a closure operator.
2To facilitate reading we will occasionally omit the parentheses, i.e., we will write a, b _ c instead of {a, b} _ {c}.
3Note, that this is well-defined, since the mentioned properties are closed wrt. intersection.
4A naïve way to achieve this: given ϕ, let I = {A _ ϕ(A) | A ⊆ M }.
Intuitively, a formal context is represented by a so-called cross table, where each row is associated to an object, each column to an attribute, and crosses indicate which object has which attributes.
Definition 4 Let K = (G, M, I ) be a formal context. We define a function (.)I : P (G) → P (M ) with
AI := {m | gI m for all g ∈ A} for A ⊆ G. Furthermore, we use the same notation to define the function (.)I : P (M ) → P (G) where
BI := {g | gI m for all m ∈ B} for B ⊆ M .
For convenience, we sometimes write gI instead of {g}I and mI instead of {m}I .
Applied to an object set, this function yields all attributes common to these objects; by applying it to an attribute set we get the set of all objects having those attributes. The following facts are consequences of the above definitions:
• (.)II is a closure operator on G as well as on M . • For A ⊆ G, AI is a (.)II -closed set and dually • for B ⊆ M , BI is a (.)II -closed set.
The next definition shows how a conceptual hierarchy can be built from a formal context.
Definition 5 Given a formal context K = (G, M, I ), a FORMAL CONCEPT is a pair (A, B) with A ⊆ G, B ⊆ M , A = BI , and B = AI .
We call the set A EXTENT and the set B INTENT of the concept (A, B).
Let (A1, B1) and (A2, B2) be formal concepts of a formal context. We call (A1, B1) a SUBCONCEPT of (A2, B2) (written: (A1, B1) ≤ (A2, B2)) if A1 ⊆ A2. Then, (A2, B2) will be called SUPERCONCEPT of (A1, B1).
Proposition 2 The concept intents of a formal concept are exactly those attribute sets closed with respect to (.)II .
It is well known from FCA that the set of all formal concepts of a formal context together with the subconceptsuperconcept-order form a complete lattice, the so called concept lattice. 4
In this section, we recall the notion of a particular neural network giving a formal definition that we will build upon in the subsequent sections.
Definition 6 A 3-LAYERED FEEDFORWARD NETWORK is defined as a tuple N = (I, H, O, t, w) where • I, H, O are finite disjoint sets called INPUT NODES, HIDDEN NODES, and OUTPUT NODES,
R is the THRESHOLD FUNCTION, • t : (I ∪ H ∪ O) →
and • w : (I × H) ∪ (H × O) → R is the WEIGHT FUNCTION.
Clearly, neural networks are intended as computational models, i.e. they are designed to calculate something. Hence given a neural network we can define a function capturing its computational behaviour.
Definition 7 Given a 3-layered feedforward network N as specified in Definition 6, the ASSOCIATED NETWORK FUNCTION fN : P (I) → P (O) is defined in the following way: For a given argument set S, we define the set AS ⊆ I ∪ H ∪ O of ACTIVATED NEURONS as follows (using the shortcut χA(a) = |{a} ∩ A|): • for every i ∈ I, we set i ∈ AS exactly if χS (i) − t(i) > 0, • for every h ∈ H, we set h
Pi∈I χA(i)wih − t(h) > 0, and • for every o ∈ O, we set h
Ph∈H χA(i)who − t(o) > 0.
Finally, we set fN (S) = AS ∩ O. ∈ ∈
This definition exactly mirrors the usual way of calculating with neural networks, presuming the Heaviside step function as activation function.
In the sequel, we aim at the special case of simulating a closure operator ϕ : P (M ) → P (M ) with this kind of neural network, i.e., input and output layer correspond to the same set (namely M ). 5
The basic idea for this paper is to use formal contexts to represent closure operators. In particular (as we have seen in Section 3), for a formal context K = (G, M, I), the function (.)II : P (M ) → P (M ) is a closure operator on M . Moreover, any closure operator on a finite set M can be represented by an appropriate formal context.5
So, in this section, we propose two canonical ways to translate a formal context into a 3-layered feedforward network, which – given a set A ⊆ M – computes its closure AII .
The intuition hereby is to identify the hidden layer neurons with the object set of the formal context. We realize the (.)II operator by first applying (.)I to A (which by definition yields an object set represented by the activated neurons in the hidden layer) and, afterwards, applying (.)I to AI thus obtaining the closure of the attribute set at the output layer. Definition 8 For a given formal context K = (G, M, I), we define a corresponding 3-layered feedforward network NK in the following way: • I = {im | m ∈ M } • O = {om | m ∈ M } • H = {hg | g ∈ G} • t(i) := 0.5 for all i ∈ I • wimhg = whgom =
5One method, how to construct a formal context with this property will be explicated in Section 6. • t(n) := −0.5 for all n ∈ H ∪ O
Next, we will prove that indeed the associated network function fNK corresponds to the closure operator (.)II , i.e., for all A ⊆ M , we have that AII = {m | om ∈ fNK ({im˜ | m˜ ∈ A})} Proposition 3 Let K = (G, M, I) be a formal context and NK the corresponding neural network. Then 1. for every A ⊆ M , activating (exactly) the set {im | m ∈ A} of input neurons leads to an activation of (exactly) the set {hg | g ∈ AI } of hidden neurons and 2. for every B ⊆ G, activating (exactly) the set {hg | g ∈ B} of hidden neurons leads to an activation of (exactly) the set {om | m ∈ BI } of output neurons.
Proof: Consider the hidden layer neuron hg representing the object g ∈ G. Now, since AI = {g | gIm for all m ∈ A} we have that g ∈ AI exactly if g has all attributes from A. Obviously, this is the case if and only if
X χAA (im)wimhg = m∈M
X wimhg = 0 > −0.5.
m∈A The second claim is proved in exactly the same manner.
The next corollary then follows immediately be the definition of (.)II as twofold application of (.)I .
This approach is quite close to formal concept analysis since the neurons of the hidden layer directly correspond to the object set of the represented formal context. The negative weights are necessary due to the fact that (.)I is (in both variants) an antitone function (i.e. A ⊆ B implies BI ⊆ AI ).
However, this can be overcome by a simple “work around”: instead of mirroring the functions A 7→ AI and B 7→ BI (for A ⊆ M and B ⊂ G), one could use the functions A 7→ M \ AI and B 7→ (M \ B)I instead. Both of them are monotone and can hence be modelled with only positive weights, and still their composition yields the wanted operator (.)II . In the sequel, we will elaborate this idea.
Definition 9 For a given formal context K = (G, M, I), we define a corresponding 3-layered feedforward network N˜K in the following way: • I = {im | m ∈ M } • O = {om | m ∈ M } • H = {hg | g ∈ G} • t(i) := 0.5 for all i ∈ I • t(om) := −0.5 + |{g ∈ G | ¬gIm}| for all om ∈ O • wimhg = whgom = • t(h) := 0.5 for all h ∈ H 0 if gIm 1 otherwise.
Proposition 4 Let K = (G, M, I) be a formal context and N˜K the corresponding neural network. Then 1. for every A ⊆ M , activating (exactly) the set {im | m ∈ A} of input neurons leads to an activation of (exactly) the set {hg | g ∈ G \ AI } of hidden neurons and
2. for every B ⊆ G, activating (exactly) the set {hg | g ∈ B} of hidden neurons leads to an activation of (exactly) the set {om | m ∈ (G \ B)I } of output neurons. 1. Consider the hidden layer neuron hg representing the object g ∈ G. Now, since AI = {g | gIm forall m ∈ A}, we have that g ∈ AI exactly if g has all attributes from A. Obviously, this is the case if and only if
X wmg = 0 < 0.5.
m∈A
Therefore, any hg being activated must be in G \ AI . 2. Now, consider the output layer neuron om representing the attribute m ∈ M . If B is activated in the hidden layer, om will be activated exactly if X wgm = |{g ∈ B | ¬gIm}| > −0.5+|{g ∈ G | ¬gIm}| g∈B Yet, due to B ⊆ G, this can only be the case iff {g ∈ B | ¬gIm}| = |{g ∈ G | ¬gIm}| which is equivalent to the statement that gIm for all g ∈ G \ B. Hence, om is activated exactly if m ∈ (G \ B)I .
Corollary 2 N˜K computes (.)II .
Proof: Due to the preceding proposition, applying N˜K to an attribute set A will first activate the hidden neurons representing G \ AI and then the output neurons representing (G \ (G \ AI ))I = (AI )I = AII 2
As already mentioned, using this type of network will activate exactly those hidden layer neurons not contained in AI , if A is entered.
An interesting feature of both presented networks is their symmetry: for all m ∈ M and g ∈ G, wimhg = whgom . Although this puts structural constraints on the neural network and might therefore hamper the application of learning strategies, it might be useful from a quite different point of view: in cases, where the neural network will be hardwired, input and output layer could be identified and calculation be done in a “back-and-forth manner” using the links twice for every calculation. 6
In this section, we will show, how the presented strategy can be applied in a propositional logic programming scenario.
Logic programming is especially suited for this approach, since • any logic program essentially consists of a set of implications and hence • entailment can (at least in the negation-free case) therefore be described by a closure operator on the ground facts.
Consequently, one can assign to every logic program an operator TP which applied to a set of ground facts intuitively calculates the immediate consequences by “applying” each implication once. The entailment closure operator can then be simulated by iteratively applying TP until a fixed point is reached. [Hitzler et al., 2004] presents an approach to encode TP into a recurrent 3-layered neural network, by assigning every implication to a node of the middle layer. To make this clear, consider the following example.
Imagine, some kind of animal has to be determined via some tests. Let furthermore the only available tests be to indicate whether the animal is a mammal, a bird, a monkey, a donkey, an owl, a fowl or a frog. Hence M := {donkey, monkey, mammal, frog, bird, owl, fowl}. Then the implications presented in Fig. 1 characterize the setting: _ _ _ _ monkey donkey owl fowl monkey, donkey owl, fowl mammal, bird mammal, frog bird, frog mammal mammal bird bird _ ⊥ _ ⊥ _ ⊥ _ ⊥ _ ⊥ 2
Following [Hölldobler and Kalinke, 1994], the neural network corresponding to the TP -operator representing those implications interpreted as a logic program would look like the one represented in Fig, 2.
0.5 0.5 1.5 1.5 1.5 1.5 1.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5
0.5
The set {donkey, f owl} demonstrates that, in general, TP may have to be applied several times to calculate the closure, since
TP ({donkey, fowl}) = {donkey, mammal, fowl, bird} 0.5 0.5 0.5 0.5 0.5 0.5 0.5 -0.5 -0.5 -0.5 -0.5 -0.5 -0.5 -0.5 -0.5 -0.5 -0.5 -0.5 -0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 and
TP ({donkey, mammal, fowl, bird}) = M.
Now we consider how our method would apply. So, we have to find a formal context K = (G, M, I), where AII = AI for all A ⊆ M . One possibility to do so is to consider the lattice of all I-closed sets. Fig. 3 represents this.
mammal bird monkey donkey frog owl fowl
Yet, a well-known result of FCA provides a direct way to find a minimal set of objects for a formal context that is supposed to generate a given lattice. One has to take all supremum-irreducible elements as objects. Looking at the diagram, the supremum-irreducible elements are exactly those having only one lower neighbour. In our particular case, these are exactly all upper neighbours of the bottom element. Hence, we can derive the formal context depicted in Fig. 4. l w o ×
In our paper, we presented two new canonical ways for generating neural networks that compute the closure operator of a given finite set. We thereby provide a method to support the representation part of the neural-symbolic learning cycle by presenting an encoding strategy for a kind of background knowledge generically occurring in the area of knowledge processing.
In contrast to other methods, where the closure is approximated iteratively (using a recurrent network), the networks presented in our approach will calculate it directly, i.e., by a single run of the network.
Moreover, as shown by our example, there are cases where this kind of representation is also advantageous in terms of the number of hidden layer neurons needed. In general, this approach seems to be especially beneficial, if the number of implications becomes large.
Naturally, the proposed method requires preprocessing of the implicative information to be encoded. Depending on how this information is given, it has to be transformed into a formal context. The way we presented here – namely generating the whole lattice of the closed sets and identifying the supremum-irreducible elements of it – is certainly not optimal with respect to time costs (in the worst case, the size of the lattice can be 2|M|). So one important field of future research is to find more efficient methods to convert implicative knowledge into small contexts.