Sub-symbolic to symbolic knowledge conversion

^{Sub-symbolic to symbolic knowledge conversion}

^{(1) Graduate School of Information Systems, University of Electro-Communications, Tokyo,}

^{(2) Bio-Medical Engineering Centre, 'Politehnica' University of Bucharest,}

^Abstract

^{Significant advantages can be gained by combining the symbolic knowledge of a domain theory (DT), with the empirical sub-symbolic knowledge stored in an ANN trained on examples. Rule extraction adds the needed explanation/comprehension component to the much prized ability of ANN to generalize over a learned set of examples. Compiling rules into the an ANN provides better initial conditions for training the network and can significantly improve the speed of learning. The mixed approach allows building hybrid systems that co-operatively combine ANN and AI techniques, increasing both robustness and flexibility. The paper gives an overview of the bases of ANN knowledge extraction under the form of logical functions}

^{1. Introduction}

^{Considerable effort has been dedicated to 'write' and 'read' symbolic information into and from artificial neural networks (ANNs) 1, 2, 4, 10-14, 16-17, 22-23, 26, 29, 30, 32, 36-38 . The motivation has been multifold. Primarily, ANNs have a good ability to represent 'empirical knowledge', like the one contained in a set of examples, but the information is expressed in a 'sub-symbolic' form -- i.e., in the structure, weights and biases of a trained ANN, not directly readable for the human user. Thus, an ANN behaves almost like a 'black box', providing no explanation to justify the decisions it takes in various instances. This forbids the usage of ANNs in 'safety-critical' domains, which include the economic and financial applications, and makes it difficult to verify and debug software that includes ANN components. On the other hand, knowledge conversion allows its 'portability' to other systems, both in symbolic (AI) and in sub-symbolic (ANN) forms. Hybrid Learning (HL) Systems that exploit simultaneously theoretical and empirical data 12-14, 16, 23, 31, 36 are more efficient than Explanation-Based Learning (EBL) systems ‑ that use only theoretical knowledge in symbolical form, or Empirical Learning (EL) systems ‑ handling the knwledge in the ostensive/empirical form. The EBL and EL approaches are complementary in many aspects, so they can mutually compensate weaknesses and alleviate inherent problems. In principle, HL Systems could assist the induction of scientific theories, helping discover salient features in the input data, whose importance could otherwise be over-looked. Hybrid systems for economic and financial applications, including time-series prediction, benefit from the cooperative use of symbolic rule-based AI modules and sub-symbolic, empirically trained, ANN modules. The basic steps of the mixed learning approach are: (1) compile/encode the available theoretical knowledge (domain theory -- DT) into an ANN, (2) use sets of examples to train the network, (3) extract the refined theory under symbolic form -- to be used in a classical AI system or to be reinserted into the ANN. The cycle can be repeated until some stopping criteria are satisfied.}

^{2. RULE IMPLEMENTATION}

^{2.1. Canonical Binary Functions}

^{The simplest way to implement discrete rules is in the form of binary logical functions. An n-variable binary logical function f: Bn B, n N, B = ; y = f(x1, x2, , xn) assigns a truth value F-false or T-true to its output (dependent, consequent) variable y, for each combination of the truth values of the input (independent, antecedent) variables x1, x2, , xn . Usually, numeric coding is used for the binary logical values true (T) and false (F): 0 and 1 (unipolar representation), or -1 and 1 (bipolar representation), respectively. As there are 2n distinct vectors x=( x1, x2, , xn) in the discrete input space Bn and 2 distinct vectors in the output space, there result distinct logical functions. This combinatorial explosion is the main cause of the complexity problem of arbitrary logical function implementation. A binary logical function f can also be seen as the characteristic function of the truth set Tf = . This approach readily allows the generalization to fuzzy logic, in connection with fuzzy set theory.}

^{A binary function f, constant with respect to m of its n variables, has the granularity y = 2n-m. A binary logical function f of granularity one, i.e. constant with respect to all its variables, is either a tautology, if  f = T, or a contradiction, if f = F. The family of one-variable binary logical functions comprises the identity I(x) = x, the negation N(x) = , the tautology T(x) = T, and the contradiction C(x) = F. The identity and the negation can be represented as instances of the same symbolical function f(x) = xe, where the exponent e is conventionally 1 for identity and -1 for the negation. The n-variable canonical binary functions have one of the entries in their truth table different of all the other entries. These functions are not constant with respect to any of their variables, so that the granularity is 2n. Consequently, there are 2n distinct conjunctive (AND, product) canonical binary functions, having a single T entry in the truth table, while all the other entries are F:}

^{Similarly, there are 2n disjunctive (OR, sum) canonical binary functions with a single F entry in their truth table and all the other entries equal to T:}

^{Because of their role in Boolean algebra, the conjunction and disjunction are often denoted by product and sum, respectively. The product and sum canonical binary function are related by the De Morgan theorems: Each functions is completely specified by the values of the set of symbolic exponents eh. The indices of the canonical binary function can be related to the symbolic exponents by the relation: k = , which corresponds to writing k in base 2.}

^{2.2. Normal Forms of Logical Functions}

^{Any binary logical function can be expressed in the disjunctive normal form:}

^{or in the conjunctive normal form:}

^{where the characteristic coefficients ak B; k = 0,,2n-1 uniquely specify the function. The expansion of a logical function in one of the normal forms actually provides the highest granulation analysis of its truth table. As known, Veitch diagrams ‑ in which the locations correspond to the canonical product or sum function components, while the entries are the characteristic coefficients ‑ can be used to minimize the expansions of the functions by combining the terms which differ only in the values of one variable.}

^{Fig. 1a presents the standard structure of a first order neuron, while Fig. 1b gives the simplified flow-graph representation of the neuron.}

^{The internal activation potential vi of neuron i is an affine function of its inputs:}

^{where bi is the bias (sometimes, the threshold qi = -bi is used), and wij are the weights of the links from the input xj , j=1,,n, to the neuron i.}

^{The (external) activation yi of the neuron (the output) is given by:}

^{where y(vi) is the activation function of the neuron, usually of the sigmoid type, either unipolar (7, Fig. 2.a) or bipolar (8, Fig 2.b.), depending on the chosen representation of the truth values. The slope parameter of the sigmoid is denoted by si}

^{To establish the state of a unit implementing a rule as a binary logical function, let us denote by P+ (P-) the set of satisfied (unsatisfied) positive antecedents (inputs) and by N+ (N-) the set of satisfied (unsatisfied) negative antecedents of the rule. The activation levels of the inputs are shown in table 2. The cardinals of these sets are denoted by the corresponding small letters, while p = p+ + p- and n = n+ + n- are the total positive and negative antecedents, respectively, and M = p++n+ -- the number of satisfied antecedents, out of the total of N = p + n antecedents.}

^{Let us also denote by the sum of the absolute values of the weights from the inputs in the set Q. For the unipolar implementation, the activation vi of the unit i , for a given arbitrary input vector, falls between the bonds:}

^{When implementing rules as logical functions, the same absolute value w is assigned to all the weights of the links from the related inputs, so that:}

^{The output of the unit is certainly true and, respectively, false for the border conditions:}  

^{vi min > Va , vi max < V i = -Va (13)}

^{In the ideal case (Ca = 1, Ci = 0, va=vi=0), it results:}

^{The corresponding relations for the bipolar implementation are:}

^and

^{which give in the ideal case}

^{Various symmetrical at-least-M-of-N logical functions can be implemented by Choosing different values of the bias bi (see section 2.5). The unipolar and bipolar implementation of conjunctive and disjunctive canonical functions (AND, OR) are shown in the figures 3 and 4, respectively.}

^{The unipolar implementation of the disjunctive canonical binary function does not allow the negation of the inputs inside the unit. When necessary, the negation of some inputs must be performed in an additional step, preceding the OR function. Figure 5 presents the ideal true-false separation planes in the three input variables case, for biases that generate the canonical symmetrical functions from OR (1-of-3) to AND (3-of-3), in both the unipolar and the bipolar implementation.}

^{The ANN implementation of the disjunctive normal form of a logical function is shown in figure 6 for the case of four variable logical functions.}

^{The network comprises an input layer with the four variables, a hidden layer with nodes corresponding to the conjunctive canonical functions (components) disposed in a Veitch like structure and an output layer containing the logical function to be implemented. The training of the network consists, in this case, only in the selection of the conjunctive canonical functions which contribute in the OR function of the output unit, while the links between the first two layers are kept frozen. After the training, the unnecessary nodes of the hidden layer are pruned The neighboring nodes with similar outputs can be combined in a procedure inspired from the logical function minimization. This structure is adequate for extracting rules with the SUBSET algorithm (3.2), but has the same intrinsic complexity problem.}

^{2.3. Shannon's Symmetrical Logical Functions}

^{Symmetrical functions have the property that any permutation of the variables does not change the output value of the function (e.g., fa = x1 x2 + x2 x3 + x3 x1, fb = x1x3 + x2x3 + ). Shannon numbers theorem states that any symmetrical function is fully defined by a set of numbers , so that if exactly bj, j=1,2, , k variables are true (or false), the function is true (or false). For instance, fa has the b numbers 2 and 3, while fb has b = 1. As b can take values form 0 to N ‑ the total number of variables, there are 2N+1 distinct symmetrical functions, out of which N+1 are exactly-M-of-N symmetrical canonical functions (i.e., that have only one b  number). If a symmetrical function contains one term of a canonical symmetrical function, it must contain all the terms of this canonical symmetrical function. A symmetrical function can be decomposed as a disjunction (or a conjunction) of canonical symmetrical functions uk (vk), each written in conjunctive (disjunctive) form, similarly to the normal forms expansions (3) and (4):}

^{where the characteristic coefficients ; = 0,…,N, uniquely define the symmetrical logical function.}

^{In the ANN approach, functions of the type at-least-M-of-N are implemented directly. Such functions can easily be expressed in terms of the exactly-M-of-N canonical symmetrical functions:}

^{The inverse relation is also immediate:}

^{The canonical symmetrical functions have the properties:}

^{The at-least-M-of-N functions are implemented with the same weights as the AND
(N-of-N) and OR (1-of-N) functions (figures 3 and 4), changing only the bias to b = (- M + 1/2)w in the unipolar case, and b = (N - 2M + 1)w – in the bipolar case (see 2.3). The uj “exactly-M-of-N” functions are conjunctions of two Uj functions (20). Figure 7 presents the structure of an ANN implementing a symmetrical logical function with four variables. When training such a network, only the links to the output node are modified according to the examples that define the considered logical function.}

^{Fig. 7. Symmetrical functions ANN implementation by decomposition
in canonical symmetrical functions}

^{The resulting network has an architecture adequate for the M-of-N algorithm (3.3).}

^{3. RULE EXTRACTION ALGORITHMS}

^{3.1 Classification of rule extraction algorithms}

^{There are two main approaches to knowledge extraction: (1) decompositional (structural analysis) methods ‑ which assign to each unit of the ANN a prepositional variable, and establish the logical links between these variables; (2) pedagogical (input-output mapping) methods, which treat the network as a black-box, without analysing its internal structure. From the algorithms in the literature, KBANN, KT, Connectionist Scientist Game, RULE NEG, RULE-OUT are based on the decompositional approach, while BRAINNE illustrates the pedagogical methods. This paper is focused on the decompositional approach, which puts in correspondence the ANN sub-symbolic structure with the theory symbolic structure.}

^{3.2 SUBSET Algorithm}

^{The method operates based on the relation (14) giving the ideal true-false border of an unipolar neural unit of an ANN: . This border relation is based on the realistic assumption that the levels of the input/output signals of neurons in a properly trained network, storing rules as logic functions, correspond to either true, or false, so that the activation potential is determined by the values of the weights. By finding subsets of the incoming links for which the sum of the weights, plus the bias, makes the internal activation potential high enough to bring the output variable at the true level, it is possible to formulate rules of the form: if (condition) then (proposition), where (condition) expresses the border relation in terms of its logic meaning, and (proposition) is the statement attached to the examined neuron. The main difficulty of the SUBSET algorithm consists in its combinatorial complexity, which results in an exceedingly large number of subsets and rules, many redundant. One way to alleviate the problem is setting an upper limit on the number of considered subsets.}

^{The steps of the SUBSET algorithm are (using the notations defined in 2.3):}

^{This algorithm is currently used by many rule eliciting systems, but -- even with the restriction imposed by gp and gn, which can adversely affect accuracy, it generates complicated sets of rules.}

^{Possible improvements are: keep frozen the parst of the network that correspond to the initial DT, and extract only the additional rules resulted from EL; - construct hierarchical rules, using logical function minimisation techniques, - start with predefined Veitch hidden layers, and use training only to select connected units.}

^{3.3. M-of-N Algorithm}

^{In real world problems, it is common to have sets of variables playing equivalent roles in the analysed system, so that there is an inherent symmetry of the rules to be extracted. This symmetry can greatly reduce the complexity of the extraction procedure. Moreover, imposing from start the symmetry restrictions predicted by the DT, simpler ANNs and learning algorithms result. The M-of-N method is based on the idealised relation (17): , where the bias is chosen bi = (N - 2 Mborder + 1) w , so that:}

^{The steps of the M-of-N algorithm are:}

^{Clustering of the links can efficiently be done by specialized algorithms, but if the existing DT gives the necessary hints, it is simpler to impose symmetry in the BP algorithm.}

^{4. CONCLUSIONS}

^{The paper presents an overview of the most frequently used knowledge-as-rules extraction algorithms and provides some design relations that give a better insight on the necessary conditions for an ANN to properly learn logical functions. The methods can be extended for continuously varying variables, by using the Locally Responsive Units approach. For certain problems and types of knowledge, when computing the internal activation potential, the additive aggregated input can be replaced with a multiplicative aggregated input, resulting in second order units which can better represent the knowledge 29 . When implementing fuzzy logical functions, it can be advantageous to use a min-max operator to evaluate the neuron’s (internal) activation potential, instead of the classical affine operator (5). An efficient training of the ANN must be able to change both the weights of the links and the structure of the network. The incremental approach has to be balanced with a step of pruning, to keep complexity as low as possible for the given problem. Maintaining constant some parts of the network during the training, while changing others, allows the refinement of the DT by finding only the additional rules 12 . This is to be preferred, whenever possible, to the changing of most/all the rules, which leads to loosing the meanings of the initial concepts in the DT.}

^{The implementation of symbolic AI rules in ANN form, and the rule extraction from the ANN sub-symbolic form are the two sides of a potentially powerful tool that jointly uses the theoretical and the empirical knowledge in solving real world problems. This approach seems to have significant advantages for the Stock Exchange Prediction problem.}

^REFERENCES