| |
ISSN 1320-0682 | |||
| Volume 02 | April 1995 | |||
Joachim Diederich and Alan B. Tickle
Neurocomputing Research Centre
School of Computing Science
Queensland University of Technology
Brisbane Q 4001 Australia
Email: joachim@fit.qut.edu.au
Explanation is a key function in artificial intelligence systems. It is used to update knowledge structures in case-based reasoning when a prediction fails, that is, for failure-driven learning. Explanation is also used to clarify the results of a reasoning process to a user. This user is not a domain expert in some cases but has the responsibility of accepting or rejecting a solution produced by an AI system. Furthermore, explanation can be used for knowledge-intensive learning whenever a complete domain theory is given.
The term "explanation" refers to an explicit structure which can internally be used for reasoning and learning, and externally for the explanation of results to a user. In rule-based systems, for instance, explanation includes intermediate steps of the reasoning process; that is, a trace of rule firings, a proof structure, etc. This structure can be used to answer "How" questions. For instance, how was solution w produced by an inference system? Because conditions x and y were satisfied after the first data entry and have led to the conclusions w and z which satisfied the condition k, and so on. This type of explanation, though limited, is absolutely crucial for the user acceptance of an inference system.
Experience with expert systems has shown that users demand an explanation of a result produced by an expert system and do not accept a solution without explanation [2]. Consequently, efforts were made in the expert systems area to allow explanations which are, at least to some degree, meaningful and coherent. Although symbolic AI has successfully introduced various forms of user explanation, the transparency of an explanation is by no means guaranteed. A poorly organised rule base, for instance, with hundreds of premises per rule, completely destroys the transparency of explanations based on rule traces [3], that is, rule comprehensibility. Therefore, explanations based on rule traces are now widely recognised as too rigid and inflexible [4, 5,6].
Explanations based on rule traces always reflect the current structure of the knowledge base, often have references to internal procedures (for example, calculations), might include repetitions (for example, if an inference was made more than once), and the granularity of the explanation is often wrong [4].
Moore & Swartout [6] complain that the early use of canned text or templates as part of user explanations is too rigid, that systems always interpret questions in the same way, and that there is a lack of response strategies. Although there are efforts to take advantage of natural-language dialogues with mixed initiatives, user-models and explicitly planned explanation strategies [6], there is little doubt that current systems are still too inflexible, unresponsive, incoherent, insensitive and too rigid [7]. Consequently, if user explanation is done by generating rule sets (in symbolic AI and ANNs), rule quality and comprehensibility are important issues [8].
Neural networks are useful computational methods for pattern recognition, adaptive behaviour (including machine learning and generalisation), probabilistic and plausible reasoning, data fusion, etc. Furthermore, neural networks promise efficient processing by exploiting massive parallelism and fault tolerant behaviour. In pattern recognition, the ability of neural networks to extract important features from data during a learning or training period, plus the possibility to use these features for recognition and generalisation, have triggered interest in this class of computational models.
Using a set of examples from a given problem domain, comprising inputs and their corresponding outputs, an artificial neural network can be trained to learn the relationship between the input-output pairs. The knowledge acquired about the problem domain during the training process is encoded within the ANN in two forms: 1) the network architecture itself (for example, number of "hidden" units) and 2) a set of numeric parameters ("weights"). The trained network can then be used to generalise over a set of previously unseen examples.
In general, the ANN functions as a "black box", with input being presented on one side and a decision/classification being produced at the other. The internal structure, or architecture of the network, means the functioning of the ANN is hardly transparent to the user. While it is the network architecture that underpins the rich problem-solving capability of ANNs, it also makes the corresponding task of interpreting and, more importantly, explaining, the network solution difficult to realise.
Rule extraction techniques
seek to clarify to the user how the network arrived at its
decision by decoding the internal state(s) of the ANN. To
date, most of the effort has been directed towards presenting
the explanations as a set of rules expressed using
conventional (that is, two-valued Boolean) symbolic logic in the
form if 
then
else
.
A substantial effort has also been
directed towards expressing the knowledge embodied in the ANN,
using concepts drawn from "fuzzy" logic. This allows rules to
be expressed in a form which deal with what are termed
"partial" truths; for example, if 
then
MIGHT-BE-TRUE, or
if 
then
COULD-POSSIBLY-BE-TRUE. A topic which is closely
allied to rule extraction from artificial neural networks is
that of using ANNs to "refine" existing symbolic rules. The
starting point in this process is an initial knowledge (rule)
base which may not necessarily be complete or even correct.
In this case, the ANN is used to produce a "better"
representation of the problem domain from which a "refined"
set of symbolic rules can be extracted.
The adaptation of ANNs to the task of rule refinement has been an important development, leading to situations in which the extracted rules have out-performed the ANN on which they were based [8].
Rule quality refers to the accuracy, fidelity, and comprehensibility of the extracted rules [8]. A rule set is accurate if it can correctly classify previously unseen examples. A rule set displays high fidelity if it can mimic the behaviour of the network from which it was extracted by capturing all of the information embodied in the ANN. The comprehensibility of a rule set is determined by measuring three attributes of the rule set:
1) The size of the rule set in terms of the number of rules.
2) The number of antecedents per rule.
3) The consistency of the rule set.
The essential task of using ANNs for inductive inference is to
transform the knowledge embodied within the architecture and
weights of the trained network into a set of symbolic (for example,
propositional if-then) rules. A number of different
strategies have been developed for performing this task. For
example, one approach (which is termed "decompositional") is to
search for combinations of input values which, when
satisfied, cause a given (hidden or output) unit within the
ANN to become "active" irrespective of the state of other
inputs to the unit. This approach yields a separate set of
conjunctive rules of the form,
if A and B and C and 
, then
TRUE for each hidden and output unit in the ANN [9].
An example for a decompositional rule-extraction technique is introduced in [10]. This technique uses "constrained error back propagation (CEB)" which constitutes a special class of ANNs constructed with "local functions". These local functions behave in a manner similar in concept to radial basis functions. While the basic underlying motif for rule extraction in CEBP is decompositional, in this case it is possible to exploit the characteristic properties of local functions to clearly identify dominant inputs (and, hence, rules).
An alternative approach [11] is to treat the trained ANN as a "black box" and to view rule extraction as a learning task, where the target concept is the function computed by the network. This approach uses the trained ANN to create a directed set of examples from which the underlying rules can be extracted (in the ensuing discussion this algorithm will be referred to as EXAMPLES/SUBSET). A third approach [12] employs linear programming to determine whether or not a set of constraints on the activation values for the network's input and output units is consistent or not (this is referred to as the VIA - Validity Interval Analysis - algorithm). Using this motif, the negated representation of a potential rule determines the constraints, and a rule is deemed to be valid if there is no way for the network to satisfy the negation of the rule (that is, the set is inconsistent).
"Decompositional" and "learning-based" rule extraction techniques can be combined. An example is DEDEC [13], which is similar in concept to that of the EXAMPLES/SUBSET approach of Craven and Shavlik discussed previously; that is, it uses the trained ANN to create examples from which the underlying rules can be extracted. However, an important difference is that it extracts additional information from the trained ANN by subjecting the resultant weight vectors to further analysis (that is, a "partial" decompositional approach). This information is then used to direct the strategy for generating a (minimal) set of examples for the learning phase. It also utilises an efficient algorithm for the rule extraction phase.
Mozer and Smolensky [14] point out that it is much easier to understand the behaviour of a feedforward perceptron in terms of simple rules than in a large number of weights and activation values. Their skeletonisation techniques aim to determine the relevance of individual units in feedforward networks and to remove redundant units. The result of the procedure is a minimal network which consists of only those units which really contribute to the solution (that is, represent relevant features). Thereby, generalisation is restricted and it should be easier to understand the behaviour of a network in terms of simple rules. This method, however, has advantages in those cases only where the number of input units and "relevant features" is reasonably small. The number and complexity of rules does not facilitate explanation otherwise.
A more sophisticated weight elimination procedure has been introduced by Weigend, Huberman & Rumelhart [15]. Their method involves the extension of the conventional back-propagation learning rule to a more complex cost function. The method begins with a feedforward network that is too large for a given problem, and associates a cost with each connection in the network. If a given performance on the training set can be obtained with fewer weights, the cost function will encourage the reduction and eventual elimination of as many connections as possible [15]. Furthermore, weight elimination is extended to unit elimination and can remove the least important hidden units from a network. In some cases, when only a few hidden units are left, it is possible to identify the important input features and to explain which features contribute to a classification or prediction.
The CSN used in this study is operating in two different modes, "inference" and "explanation". During inference, intermediate activation patterns of a spreading activation process are recorded and saved. During explanation, intermediate activation patterns over the CSN are reproduced and relations are made explicit; that is, "explanation" is not a simple replay of activation patterns, but a partial or full reproduction of inference states which makes those relations which have been used during inference explicit.
The network used in this study has been described in full detail in [16]; a complete description of the explanation component can be found in [1] and [17]. The network has four modules; each module is a n-layer network with mutual excitatory connections between neighbouring layers (in both directions) and inhibitory connections within layers. Each layer is a "k winner take all" (k-WTA) network. Competition among units in a layer results in the strong activation of a winner unit, but several units might be active simultaneously if they receive strong excitation. The total network has four "spaces"; that is, three network modules with the architecture described above and an additional single space containing a set of units without internal organisation (the instance space).
In detail, there is a space for the representation of structured objects, a space for the representation of attributes, a space for the representation of values of attributes, and the instance space mentioned above. All representations are localist; there is a single unit for the representation of each object, attribute, value or instance. On the network level, there are two classes of units in each space: concept units and relay units. Concept units may have one of two states, "free" or "committed".
A concept unit in the "free" state is called a free unit. Committed units build a hierarchy; that is, committed object, attribute and value units are embedded in a multilayer network system and form a straightforward spreading activation network. Only this network of committed units is relevant here (the free units are used to learn new knowledge and to integrate this knowledge in the CSN). Committed units are not only connected with units in the same space, but also with units in other spaces. Object, attribute and value units are connected by binder units. There is one single binder unit for each connection between an object, attribute and value. Relay units connect those concept units which have no direct connections; that is, which are separated by at least one layer.
Figure 1: The architecture of the network. The CSN consists of
object, attribute, value and instance space; the simple explanation
component includes relation and history space. Not all links are
shown.
The brief description above explains why intermediate states in a spreading activation CSN are meaningful. The input causes a flow of activation along the links of the inheritance hierarchy, which corresponds to a sequential application of the superclass/subclass relation plus property retrieval. Each intermediate state is the result of the use of this relation. Furthermore, it is possible to record and replay intermediate states during processing by use of "recruitment learning"; that is, patterns of activation are "frozen" into the weight of a single unit representing a particular time step (the weight is set to the input value at the corresponding time step).
The explanation component uses this kind of recruitment learning with fast weight change to save intermediate states in reasoning, and uses them for simple explanations. These user-oriented explanations can be given with various degrees of granularity. The objective of this work is to extend the functionality of connectionist semantic networks and to provide CSNs with the ability to give a "meaningful" response to "How" questions. In summary, the explanation component allows the following functions:
- (a) Reproduction of inference processes, even when the CSN has been changed.
- (b) Partial reproduction of inference processes.
- (c) Delayed reproduction of inheritance processes.
- (d) The combination of several inference processes in a single space.
- (e) The superposition of intermediate activation patterns (by clamping on two or more "history units" during explanation).
- (f) Stationary intermediate activation patterns without activated auxiliary units.
The explanation component is implemented by two additional modules, called history space and relation space, which are added to the CSN described above. The history space is a layered network and uses a special form of recruitment learning with fast weight change. See [16] for a description of recruitment learning techniques. The reason for the layered architecture of the history space is to allow various levels of granularity in explanations.
The relation space is a set of units with links from units in the CSN and with links to all first layer units in the history space. Each unit in the relation space represents explicitly a relation encoded in the CSN. For instance, standard type units might represent "subclass/superclass", "concept/feature" and "instance/feature" relations.
It is also necessary to restrict the type of spreading activation process used as part of the CSN. A very strong decay process is effective in each CSN unit soon after this unit has reached near maximum activation. This decay reduces the activation of that unit significantly. The network effect is that at most one unit of the connectionist inheritance hierarchy is fully activated. The reason for this strong decay process is to avoid crosstalk in explanation patterns. "Crosstalk" refers to the confusion of features owned by two or more concepts.
The history space is a network with several layers. Each unit in the first layer has symmetric links to all units in the connectionist semantic network, with exception of auxiliary unit types such as relay units.
Units in the first layer of the history space are organised as a chain; that is, the first unit has an excitatory link to the second unit, the second unit has a link to the third, and so on. Units in the first layer have an activation function which allows a high output for a single update step only, the unit turns itself off after one update with a strong positive output. Furthermore, input lines from and to units in the first layer do fast weight change; that is, the weight is set to the input value at the very moment when the unit has a high output. In the remainder of this section, two degrees of granularity are possible for explanation. This makes three more layers necessary.
Units in the second history space layer are connected to first layer units and are used to allow fine-grained explanation. Second layer units are organised as a chain in the same way as first layer units, but with a delay of propagation to the next unit. Furthermore, there is a one-to-one connectivity between second and first layer units; that is, the first second layer unit is connected to the first unit in the first layer, and so on.
The third layer is used to allow low-grained explanation. It is organised as the second layer, but with sparse connectivity to the first layer. For instance, the first 3rd layer unit has a connection to the first 1st layer unit, the second 3rd layer unit has a link to the 4th first layer unit, and so on with an increment of 3.
The fourth and final layer consists of single units representing the granularity of explanation. In our architecture, the 4th layer has two units only. The first 4th layer unit is connected to the 1st second layer unit and the second 4th layer unit is connected to the 1st third layer unit (see Figure 1).
As mentioned above, the relation space consists of a set of units representing relations which are used in the CSN. The object space, for instance, represents a taxonomy of concepts; that is, it encodes "subclass/superclass" relations. Therefore, a single unit in the relation space must represent this kind of relation. Links from an object unit to an attribute and feature unit represent a "concept/feature" relation, and again a single unit in the relation space represents this relation. Units in the CSN have additional links to the corresponding units in the relation space; that is, whenever activation flows over a "subclass/superclass" link (or the intermediate relay unit) in the object space, the corresponding unit in the relation space will be activated too. Units in the relation space have full connectivity to first layer units in the history space and vice versa.
Once again, each unit in the first layer of the history space is active for one time step. This unit does fast weight change during this single time step and sends a signal to the next first layer unit to turn it on. This requires synchronous processing in the history space.
Fast weight change allows storage of a temporary pattern of activation in the weights of a single unit. In other words, the activation pattern over the connectionist semantic network is "burned" into the links of that unit.
The number of units in the first history space layer has to be large enough to allow storage of all activation patterns until the final solution is reached. Captured activation patterns are used for explanation. This is possible because the inheritance hierarchy as part of the connectionist semantic network is semantically meaningful. Therefore, each step in reasoning is meaningful; that is, each step in the activation spreading in the concept hierarchy and the resulting activation of properties. The architecture of the history space allows saving this limited reasoning process and its use for explanation.
Clamping on the first 4th layer unit will lead to the sequential reproduction of all intermediate states of the reasoning process and makes this accessible for explanation (for example, for a presentation to the user). Clamping on the second 4th layer unit will lead to the sequential reproduction of some intermediate states of the reasoning process and, therefore, explanation with lower granularity. In other words, the user has the possibility to choose among several degrees of explanation, but might loose valuable information if the low-grained mode is used.
A brief overview of explanation in symbolic AI was given and the importance of rule-extraction techniques was outlined. It has been shown that connectionist systems benefit from the explicit encoding of relations and the use of structured networks. Structured connectionist systems using spreading activation have the advantage that intermediate states in processing are semantically meaningful and can be used for explanation.
Explanation and Collective Computation
This document was generated using the LaTeX2HTML translator Version 95.1 (Fri Jan 20 1995) Copyright © 1993, 1994, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
l2h -dir dieder explain.tex.
The translation was initiated by Pam Milliken on Tue Sep 24 13:48:54 EST 1996