190
Mathematical Aspects of Logic Programming Semantics
connection from the i-th unit of the input layer to the j-th unit of the hidden
layer, and θ j is the threshold of the j-th unit of the hidden layer.
It is our aim to establish results in the following sections on the representation and approximation of various semantic operators, the T P -operator in
particular, by input-output functions of 3-layer feedforward networks. Some
of our results rest on the following theorem, which is due to Funahashi, see
[Funahashi, 1989].
7.2.2 Theorem (Funahashi) Suppose that φ : R → R is a non-constant,
bounded, monotone increasing and continuous function. Let K ⊆ R
n be compact, let f : K → R be a continuous function, and let ε > 0. Then there exists a
3-layer feedforward network F with squashing function φ whose input-output
mapping f F : K → R satisfies max x∈K d(f (x), f F (x)) < ε, where d is a metric
which induces the natural topology
9 on R.
In other words, each continuous function f : K → R can be uniformly
approximated by input-output functions of 3-layer (feedforward) networks.
Furthermore, on a point of terminology, suppose given ε > 0. We will write
Y approximates X up to ε if d(Y, X) < ε, where d is some appropriate
metric for the objects X, Y in question.
10 There are two cases here where
the definition just given will be applied, as follows. In the first case, X is a
semantic operator and Y is an operator which we are using to approximate X;
d is either the uniform metric used in Theorem 7.2.2 or the metric λ discussed
in Section 7.5.2. In the other case, X is a fixed point of a semantic operator and
Y is an interpretation which we are using to approximate X; d is the metric
d l determined by a level map (taking values in ω) as in Definition 5.1.3, see
again Section 7.5.2 and also Section 7.5.6. We will paraphrase the import of
Theorem 7.2.2, noting that it holds for all ε > 0, by writing that approximating
networks exist for f . Furthermore, for our purposes later, it will suffice to
assume that K is a compact subset of the set of real numbers, so that n can
be taken to be equal to 1 in the statement of the theorem.
An n-layer recurrent network F consists of an n-layer feedforward network
such that the number of units in the input layer is equal to the number of units
in the output layer. Furthermore, each unit in the output layer is connected
with weight 1 to the unit in the corresponding position in the input layer.
Figure 7.3 shows a 3-layer recurrent network. The subnetwork consisting of
the three layers and the connections between the input and the hidden layer
as well as between the hidden and the output layer is a 3-layer feedforward
network called the kernel of F.
Notice that any neural network in which the number of units in the input
layer is equal to the number of units in the output layer can be made recurrent just by adding the necessary obvious connections with weight 1. Notice
9 For example, d(x, y) = |x − y|.
10 The fact that d is symmetric will not render this definition ambiguous, because in
practice it will be clear which object is which.
Mathematical Aspects of Logic Programming Semantics
connection from the i-th unit of the input layer to the j-th unit of the hidden
layer, and θ j is the threshold of the j-th unit of the hidden layer.
It is our aim to establish results in the following sections on the representation and approximation of various semantic operators, the T P -operator in
particular, by input-output functions of 3-layer feedforward networks. Some
of our results rest on the following theorem, which is due to Funahashi, see
[Funahashi, 1989].
7.2.2 Theorem (Funahashi) Suppose that φ : R → R is a non-constant,
bounded, monotone increasing and continuous function. Let K ⊆ R
n be compact, let f : K → R be a continuous function, and let ε > 0. Then there exists a
3-layer feedforward network F with squashing function φ whose input-output
mapping f F : K → R satisfies max x∈K d(f (x), f F (x)) < ε, where d is a metric
which induces the natural topology
9 on R.
In other words, each continuous function f : K → R can be uniformly
approximated by input-output functions of 3-layer (feedforward) networks.
Furthermore, on a point of terminology, suppose given ε > 0. We will write
Y approximates X up to ε if d(Y, X) < ε, where d is some appropriate
metric for the objects X, Y in question.
10 There are two cases here where
the definition just given will be applied, as follows. In the first case, X is a
semantic operator and Y is an operator which we are using to approximate X;
d is either the uniform metric used in Theorem 7.2.2 or the metric λ discussed
in Section 7.5.2. In the other case, X is a fixed point of a semantic operator and
Y is an interpretation which we are using to approximate X; d is the metric
d l determined by a level map (taking values in ω) as in Definition 5.1.3, see
again Section 7.5.2 and also Section 7.5.6. We will paraphrase the import of
Theorem 7.2.2, noting that it holds for all ε > 0, by writing that approximating
networks exist for f . Furthermore, for our purposes later, it will suffice to
assume that K is a compact subset of the set of real numbers, so that n can
be taken to be equal to 1 in the statement of the theorem.
An n-layer recurrent network F consists of an n-layer feedforward network
such that the number of units in the input layer is equal to the number of units
in the output layer. Furthermore, each unit in the output layer is connected
with weight 1 to the unit in the corresponding position in the input layer.
Figure 7.3 shows a 3-layer recurrent network. The subnetwork consisting of
the three layers and the connections between the input and the hidden layer
as well as between the hidden and the output layer is a 3-layer feedforward
network called the kernel of F.
Notice that any neural network in which the number of units in the input
layer is equal to the number of units in the output layer can be made recurrent just by adding the necessary obvious connections with weight 1. Notice
9 For example, d(x, y) = |x − y|.
10 The fact that d is symmetric will not render this definition ambiguous, because in
practice it will be clear which object is which.