NSP: a Neuro–Symbolic Processor Ernesto Burattini1 , Massimo De Gregorio2 , Victor M. G. Ferreira3 , and Felipe M. G. Fran¸ca4 1
Dipartimento di Scienze Fisiche, Universit` a degli Studi di Napoli “Federico II”, Complesso universitario di Monte Sant’Angelo, Via Cinthia, I80126, Napoli, Italy
[email protected] 2 Istituto di Cibernetica “Eduardo Caianiello”, CNR, via Campi Flegrei 34, Comprensorio Olivetti – Ed. 70, I80078 Pozzuoli (NA), Italy
[email protected] 3 Department of Informatics Graduate School of Information Science and Electrical Engineering, Kyushu Univ. 6–1 Kasuga Koen, Kasuga, 816–8580, Fukuoka, Japan,
[email protected] 4 Programa de Engenharia de Sistemas e Computa¸ca ˜o, PESC/COPPE, Universidade Federal do Rio de Janeiro, Caixa Postal 68511 21945–970, Rio de Janeiro, RJ, Brazil
[email protected]
Abstract. This paper presents an implementation methodology of weighted ANNs whose weights have already been computed. The validation of this technique is made through the synthesis of circuits implementing the behaviour of specialised ANNs compiled from sets of logical clauses describing different logical problems. A Neuro–Symbolic Language (NSL) and its compiler5 have been designed and implemented in order to translate the neural representation of a given logical problem into the corresponding VHDL code, which in turn can set devices such as FPGA (Field Programmable Gate Array). The result of this operation leads to an electronic circuit called NSP (Neuro–Symbolic Processor) that effectively implements a massively parallel interpreter of logic programs.
1
Introduction
One of the main obstacles on implementing weighted binary ANNs in hardware is its impact in both silicon area (A) and time of propagation (T ) – the AT 2 parameter. Nevertheless, weightless ANNs, or Boolean neural networks, can be naturally accommodated by existing digital systems, i.e., implementations in conventional hardware or software. Digital implementations of weighted ANNs by use of the multiplication– summation–thresholding’s scheme are very expensive in terms of silicon area and propagation time. Some previous works have focused on optimising parts of this computation, like the comparison mechanism [1], varying the depth (maximum number of layers from one input to one output) and size (number of neurons of the ANN) of the comparison neuron net, all seeking to minimise AT 2 . 5
Copyright n. 001109/D801353 - 23/12/98.
J. Mira (Ed.): IWANN 2003, LNCS 2687, pp. 9-16, 2003. c Springer-Verlag Berlin Heidelberg 2003
10
Ernesto Burattini et al.
This work focuses on reducing, as much as possible, the size of neurons (in terms of silicon area), what may also lead to delay reductions, by use of a simple methodology for binary digital implementations of ANNs. The method consists of substituting the traditional scheme of summation–evaluation of the threshold by a digital circuit mimicing the functionality of the whole neuron. The proposed synthesis mechanism can be naturally integrated into automatic or semi–automatic CAE tools and will be shown how this strategy may lead to great area and delay reductions [2]. In the following sections, we introduce both the neuron and the neural network models, then we show how monotonic and non-monotonic logical inferences can be implemented by means of ANNs and, finally, we describe the compiler that translates the whole network into the respective VHDL code.
2
The ANN model
The neuron model adopted here is the Weighted–Sum non–Linear Thresholded Element of McCulloch and Pitts [3]. Its state transition function is defined as follows: k 1 if x > 0 pi (t + 1) = I (ai,j · pi (t) − si ) ; I [x] = (1) 0 if x ≤ 0 j=1
where pi (t) represents the state (1 or 0) of neuron pi at time t, ai,j the coupling coefficient or weight between neurons pi and pj , whose values may be positive (excitation) or negative (inhibition), si the threshold of neuron pi . One may look for logical operations that may be performed by means of elements defined as in (1), where each element of this kind provides a localist neural representation of a propositional literal from some set P = {p1 , . . . , pn }. As stated in Aiello et al. [4], the two possible truth–values of a literal p are represented by means of two distinguished neurons p and ¬p: the first is activated if and only if the corresponding literal is supposed to be true, the second if and only if it is supposed to be false. In the latter case of course we are entering the field of non–monotonic logic. The presence of both p and ¬p allows us also to check if an explicit contradiction arises on the basis of previous inferences. Inactivity of these neurons means that we do not have information about the truth–value of the corresponding literal. A similar approach has been proposed in the past by von Neumann [5] (Double Line Trick ) to take into account non–monotonic behaviour [6]. The kind of production rule we shall consider here is a conditional expression of the form p1 ∧ . . . ∧ pk → c
(2)
and can be represented as a net having k neurons p1 , . . ., pk connected to a neuron c (see Fig. 1) with the following settings: ai,c = 1 where 1 ≤ i ≤ k and the threshold of c sc = k − where 0 < < 1.
NSP: A Neuro-symbolic Processor
11
p1 a1,c
…
ai,c
pi
c
… ak,c pk Fig. 1. Neural rule model
Using this representation of rules as basic building block, one can design a neural production system, organised into five different layers of neurons, capable of carrying out search on a knowledge base of facts and production rules. A specific example of such system, for a set of three rules, is represented in Fig. 2.
b
c
b
d
c
¬d
d
a
¬d
e
a
IN
e
DB
d* d''
d' b Rules b→d e∧¬d→a a∧b∧c→d excitatory impulses inhibitory impulses
c
¬d
a
e
KB
d∧¬d ctrl d
C
a end
d
a
OUT
Fig. 2. NFC – Neural Forward Chaining
The neural network model reported in Fig. 2, is the one called NFC (Neural Forward Chaining) introduced in Aiello et al. [4] and it is based on a unified LCA (Localist Connectionist Architecture) approach [7] of rule–based systems proposed by Burattini et al. [8] in 1992.
12
Ernesto Burattini et al.
The NFC model performs parallel forward inference processes for propositional rule–based systems. Moreover, for each set of logical clauses there exists the corresponding NFC neural network, which is generated by a compiler program based on the Neuro–Symbolic approach introduced by Aiello et al. [9]. The NFC computation captures the symbolic meaning of the corresponding set of logical clauses. The non–monotonic NFC model (grounded on the same principles of monotonic one), is based on an appropriate use of inhibitions, to implement a parallel non–monotonic reasoning (in this case, inhibitions play a key role in asserting and retracting facts [10]). The NSL (Neuro–Symbolic Language), partially introduced in [10] and reported in [11], allows us to express non–monotonic rules, such us “pc is true if P∧ is true, unless Q∨ is true” (where P∧ is the conjunction p1 ∧ . . . ∧ pn of n literals and Q∨ the disjunction q1 ∨ . . . ∨ qm of m literals). This non–monotonic rule is denoted by the non–monotonic operator6 UNLESS (P∧ , Q∨ , pc ) whose neural representation is reported in Fig. 3.
m
-n
Q∨
n-ε
pc
n P∧ +1
Fig. 3. UNLESS (P∧ , Q∨ , pc ) neural representation
3
A hardware implementation of a neural rule
The rules presented in the previous section, feed a compiler which, by its turn, builds a customised ANN architecture (neural rule) by defining the input weights of all interconnections and thresholds of each neuron defined in the process. From each set of input weights and threshold function of each neuron, an equivalent logic circuit is synthesised (see Fig. 4), based on each neuron’s reactions to all possible inputs to it, up to the point in which the whole target ANN is converted into a set of interconnected digital circuit blocks (each block corresponding to one neuron) [2]. We used flip–flops because each neuron has to store its previous output, but the functionality of the neuron is enclosed in the Combinational Logic block. 6
The set of NSL non–monotonic operators is reported in [11].
… pk
p1
…
c ak,c
pk
a1,c
a1,c
Σ
ak,c
I/O
… ak,c
Flip-Flop
p1 a1,c
Combinational logic
NSP: A Neuro-symbolic Processor
13
I/O
Fig. 4. The method proposes the substitution of the multipliers–adders–comparator’s scheme by a combinational logic that implements a truth table
Differently from pRAM (probabilistic RAM ) and DPLM (Dynamically Programmable Logic Module) models and implementations [12] [13], the neuron mapped in hardware may have no learning capabilities. It is assumed that the interconnection structure, all weights and neuron’s thresholds are pre–defined and well determined by the compiler. The resulting network is a digital circuit and its outputs are global composite Boolean functions of ANN’s inputs. This combinational processing is fully parallel and potentially asynchronous, which may allow extremely fast execution. Furthermore, the area used to synthesise the whole ANN is greatly reduced by a factor of 5.0 compared with actual implementations in hardware of the summators, multipliers and comparators (using a standard cell library).
4
From NFC to FPGA
Let be b→d e∧d→a ¬d ∧ c → a d∧a→b a set of rules expressing a logical problem. The rules can be written in terms of IMPLY s operators of the NSL in the following way: IMPLY (b, d), IMPLY (e∧d, a), IMPLY (¬d ∧ c, a), IMPLY (d ∧ a, b). The compiler, that has been designed and implemented by the authors of this paper, accepts a set of NSL operators. Each of them, is translated into an ANN that captures the symbolic meaning of the corresponding NSL operator. From the set of neurons forming the ANNs, the compiler produces the respective VHDL code. The correspondence between one neuron and the respective VHDL code does not depend on the particular neuron. The ANN is formed by homogeneous neurons whose architectures do not depend on the particular layer they belong to. For instance, the following code is produced for the neuron eKB of the layer KB. library IEEE; use IEEE.std_logic_1164.all; entity neuron_ekb is
14
Ernesto Burattini et al.
port( clk, reset, edb : in std_logic; ekb : inout std_logic); end neuron_ekb; architecture SYN_USE_DEFA_ARCH_NAME of neuron_ekb is ... ... ... ... ... ... end SYN_USE_DEFA_ARCH_NAME;
Once all the operators have been translated into the corresponding ANNs, the compiler generates (see below) the whole VHDL project of the NFC associated to the starting set of rules.7 library IEEE; use IEEE.std_logic_1164.all; ENTITY abt IS PORT( clk, reset, ain, bin, cin, din, ein, not_din : IN STD_LOGIC; aout, bout, dout , ctrl, S_end : OUT STD_LOGIC); END abt; ARCHITECTURE structural OF abt IS component neuron_adb port( clk, reset, ain : in std_logic; adb : inout std_logic); end component; ... ... ... SIGNAL adb, bdb, cdb, ddb, edb, not_ddb : STD_LOGIC; SIGNAL ckb, ekb, not_dkb, dkb, bkb, akb2, akb1, akbstar : STD_LOGIC; ... ... ... BEGIN U1: neuron_adb PORT MAP( clk, reset, ain, adb); U2: neuron_bdb PORT MAP( clk, reset, bin, bdb); ... ... ... aout
