Computing Effect-to-Cause/Cause-to-Effect Diagnoses Within NdL
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Neural Networks. Pages 1332-1337.
© 1993 International Joint Conferences on Artificial Intelligence
Abstract
The computation of effect-to-cause (called also deductive) diagnoses is rather straighforward whatever the considered framework- logical, neural , etc. This paper focuses on the computation of cause-to-effect (called also abductive) diagnoses. Ultimately, we show how mechanize the abduction within a neural framework and illustrate our mechanization by illustrati ve examples. Finally, we present instructive lessons learnt from our experimentation with NdL (a Neural Diagnosis Laboratory) and point out the innovative features of this work as well as the important issues deserving further investigations.
- [Appolloni et al., 1990] B. Appolloni, G. Avanzini, N. Cesa-Bianchi, and G. Ronchini. Diagnosis of Epilepsy via Backpropagation. In Proceedings of the International Joint Conference on Neural Networks, pages 11-539-11542, Washington, DC (USA), 1990.
- [Ayeb et al., 1993] B. e. Ayeb, P. Marquis, and M. Rusi- nowitch. Preferring Diagnoses By Abduction. IEEE, Transactions on Transcations on Systems, Man and Cybernetics, 23, May 1993.
- [Ayeb, 1992] B. e. Ayeb. Diagnosis of Complex Indus- trial Devices. In ACM Symposium on Applied Com- puting, pages 512-520, Kansas (USA), 1992.
- [Ayeb, 1994] B. e. Ayeb. Towards Systematic Con- struction of Diagnostic Systems for Large Industrial Plants-Two parts. To appear in IEEE Transactions on KDE, 1994.
- [Baylander et al., 1991] T. Baylander, D. Allemang, M. C. Tanner, and J. R. Josephon. The Compu- tational Complexity of Abduction. Artificial Intelli- gence, 49:25-60, 1991.
- [Breuer and Friedman, 1976] M. A. Breuer and A. Friedman. Diagnosis and Reliable Design of Digital Systems. Computer Science Press, Rockville, MD, 1976.
- [Carpenter and Grossberg, 1987] G. A. Carpenter and S. Grossberg. A Massively Parallel Architecture for a Self-Organizing Neural Pattern Recognition Machine. Computer Vision, Graphics, and Image Processing, 37:54-115, 1987.
- [Console et al., 1989] L. Console, D. T . Dupre, and P. Torasso. A Theory of Diagnosis for Incom- plete Causal Models. In Proceedings of the Inter- national Joint Conference on Artificial Intelligence, pages 1311-1317, Detroit, Michighan (USA), 1989. IJCAI
- [Cox and Pietrzykowski, 1987] P. T. Cox and T. Pietrzykowski. General Diagnosis by Abductive Inference. In Symposium on Logic Pro- gramming, pages 183-189, 1987.
- [de Kleer and Williams, 1987] J. de Kleer and B. C. Williams. Diagnosing Multiple Faults. Artificial In- telligence, 32:97-130, 1987.
- [Gaudill, 1990] M. Gaudill. Using Neural Nets: Di- agnostic Expert Nets. AI Expert, September:43-47, 1990.
- [Goel et al., 1988] A. Goel, J. Ramanujam, and P. Sa- dayappan. Towards a "neural" Architecture of Abduc- tive Reasoning. In Proceeding of Second International Conference on Neural Networks, pages 1-681-I-688, 1988.
- [Grossberg, 1988] S. Grossberg. Nonlinear Neural Net- works: Principles, Mechanisms, and Architectures. Neural Networks, 1(1):17-60, 1988.
- [Hopfield and Tank, 1985] J. J. Hopfield and D. W. Tank. Neural Computation of Decisions in Optimiza- tion Problems. Biological Cybernetics, 52:141-152, 1985. 1338 Neural Networks [Jakubowicz and Ramannujam, 1990] 0. Jakubow- icz and S. Ramannujam. A Neural Network Model for Fault-Diagnosis of Digital Circuits. In Proceedinl' of the International Joint Conference on Neural Nel- works, pages 11-611-11615, Washington, DC (USA), 1990.
- [Josephson et al., 1987] J. R. Josephson, B. Chan- drasekaran, J. W . Smith, and M. C. Tanner. A Mech- anism for Forming Compositte Explanatory Hypothe- ses. IEEE Transcations on Transcations on System~, Man and Cybernetics, 17:445-454, 1987.
- [Kosko, 1988] B. Kosko. Bidirectional Associative Mem- ories. IEEE Transactions on Systems, Man, and Cr- bernetics, SMC-18:49-60, 1988.
- [N.H. Goddard and K. J. Lynne and T. Mintz, 1988] N. H. Goddard and K. J. Lynne and T. Mints. Rochester Connectionist Simulator. Technical Report TR-233, University of Rochester, New York, 1988.
- [Peng. and Reggia, 1987] Y. Peng. and J. A. Reggia. A Probalistic Causal Model for Diagnostic Problem Solving (Two Parts). IEEE Transcations on Thza. scations on Systems, Man and Cybernetics, 17:146- 162/395-406, 1987.
- Peng. and Reggia, 198Q] Y. Peng. and J. A. Reggia. A Connectionist Model for Diagnostic Problem Solving. IEEE Transcations on Systems, Man and Cybernetic•, 19:285-289, 1989.
- [Poole, 1988] D. Poole. Representing Knowledge for Logic-Based Diagnosis. In ICOT, editor, International Conference on Fifth Generation Computer System•, pages 1282-1290, 1988.
- [Raiman and de Kleer, 1992] Raiman and J. de Kleer. Critical Reasoning. In Proceedings of the International Workshop On Diag- nosis DX 9!!, pages 1-5, Orcas, WA (USA), 1992.
- [Reiter, 1987] R. Reiter. A Theory of Diagnosis from First Principles. Artificial Intelligence, 32:57-95, 1987.
- [Tagamets and Reggia, 1989] M.A. Tagamets and J. A. Reggia. A data flow implementation of a competition- based connectionist model. Journal of Parallel an~ Distributed Computing, 6:704-714, 1989.
- [Thagard, 1989] P. Thagard. Explanatory coherence. Behavioral and Brain Sciences, 12:435-502, 1989.
- [Wald. et al., 1989] J . Wald., M. Farach, M. Tagameta., and J. A. Reggia. Generating Plausible Diagnoe- tic Hypotheses with Self-Processing causal Networks. Journal of Experimental & Theoritical Artificial fa. tellgence , 2:91-112, 1989.
- [Wang and Ayeb, 1992] S. Wang and B. e. Ayeb. Diag• nosis: Hypothetical Reasoning With A Competition• Based Neural Architecture . In Proceedings of the International Joint Conference on Neural Networb, pages 1-7-1-12, Baltimore, MA (USA), 1992.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Prologue
Many research activities are devoted to diagnosis where different methods have been explored. Among these methods, let us mention default trees [Breuer and Friedman, 1976], model-based diagnosis [de Kleer and Williams, 1987; Reiter, 1987; Raiman and de Kleer, 1992; Ayeb eta/., 1993], empirical-based diagnosis [Peng. and Reggia, 1987; Ayeb, 1994] associative neural net works [Appolloni et a/., 1990; Jakubowicz and Raman nujam, 1990; Gaudill, 1990]. From an abs~ract point of view, diagnostic methods can be charactenzed by the framework and the nature of knowledge used. The fra~e work delimits the adopted approach and the startmg background such as logical, neural , data analysis, etc. The nature of knowledge specifies whether we make use offault trees, statistical data, behavior models, empirical associations, etc.
In this paper we consider two kinds of framework, log ical and neural, and make use of one nature of knowl edge i.e., empirical associations. Therefore, like in [Peng. and Reggia, 1987] we define a diagnostic problem (DP for short) as a three-tuple DP = (C, £, 'R), whe~e C = { c1 , .. ·, en} , is a finite set representing the possi ble causes; £ = { e1 , · · ·,em} , is a finite set representing the possible effects; 'R = {(ci,ei)fci E C 1\ ei E £},is a subset of the Cartesian product C x £ representing the relationships between causes and effects.
· NdL is an acronym of Neural diagnosis Laboratory which is a component of ·dL. This research is partially supported under FRAI Grants (0238A; 0291A) and NSERC grants (OGP0121468; EQP0121469) .
Let DP = (C, £ , 'R) be a given diagnostic problem, then an observation for DP is defined as a subset E - {e · .. . e · } of £ representing observed effects. - }l! ' }k Now considering a couple (DP, E), we define the concept of a solution (or a diagnosis) . Intuitively, a diagnosis is a subset of causes explaining the observed effects. The meaning of erplain depends on our intuitive interpreta tion of the diagnostic knowledge embedded in 'R and .its representation types. In fact, there are two ways to m terpret the given diagnostic knowledge and ultimately two definitions of what is a diagnosis.
The first way consists in interpreting this knowledge embedded in 'R as a set of empirical associations relat ing effects to causes. Within a logical framework, 'R will be represented as a set of formulas Kd of the following form: ei 1 1\ · · · 1\ ei· ~ Cj . Within a neural f~amework 'R will be mapped into a neural network havmg effect cells as its inputs and cause cells as its outputs. Here, we call a diagnosis for a given couple (DP, E) as being an effect-to-cause diagnosis. Clearly, the computa tion of effect-to-cause diagnoses is straightforward both in neural and logical frameworks. Typically, within a logical framework an effect-to-cause diagnosis .6.,t ca~ be obtained by direct deduction from the set Kd U E :-1.:., .6.d is a subset of C such that Kd U E F .6.d. W1thm a neural framework, the diagnostic problems are further reduced to mere classification problems. Hence, a Per ceptron like neural networks can be very effective to gen erate the effect-to-cause diagnoses. That is why most of diagnostic neural proposals [Appolloni et a/., 1990; Gaudill 1990· Jakubowicz and Ramannujam, 1990], fall ' ' into this category.
The second way consists in interpreting this knowledge embedded in 'R as a set of empirical associations relating causes to effects. In this case, we call a diagnosis for a given couple (DP, E) as being a cause-to-effect dia~· nosis. Specifically, within a logical framework, 'R w11l be represented as a set of formulas Ka of the following form: Ci ~ ei 1 1\ · · · 1\ ei· . A cause-to-effect diagnosis for (DP, E) is a subset .6.0 such th:"t .6.a U Ka. F ~· and .6.0 C Cis minimal w.r.t set inclusiOn or cardmahty se~. Clearly many difficulties arise both in neural and logi cal frameworks. In particular, a more complex reasoning process is required to generate cause-to-effect diagnoses. Typically, within a logical framework , we must require an abductive (called also hypothetical) reasoning since mere deduction is not sufficient. Similarly, within a neu ral framework, cause-to-effect diagnoses cannot be ob tained by a simple association mechanism since diagnos tic problems cannot be reduced to a mere classification. That is why very few proposals have been suggested to address cause-to-effect diagnoses computation.
In fact, the intuition of effect-to-cause and cause-to effect diagnoses can be outlined as follows. The set of causes in an effect-to-cause diagnosis can be viewed as an evidence explaining the presence of the observed ef fects , while the set of causes in a cause-to-effect diag nosis can be viewed as a (minimal) conjecture explain ing the presence of the observed effects. Of course, the interpretation of cause-to-effect diagnoses is more natu ral since the effect-to-cause diagnoses tend to loose the "structure" of knowledge [Poole, 1988]. Despite the dif ferent meanings conveyed by effect-to-cause and cause to-effect diagnoses, both have been used in many di agnostic applications. Within a logical framework, let us mention the diagnostic expert system MYCIN (effect to-cause diagnoses) and the abduction based diagnoses [Cox and Pietrzykowski, 1987; Ayeb et al. , 1993] (cause to-effect diagnoses). Within a neural framework, most of proposals such as [Appolloni et al., 1990; Jakubow icz and Ramannujam, 1990; Jakubowicz and Ramannu jam, 1990] generate effect-to-cause diagnoses. Nowadays there are few proposals, namely [Peng. and Reggia, 1989; Goel et al., 1988], aiming at the generation of cause to-effect diagnoses within a connectionist/neural frame work. There is no accident since the mechanization of abduction raises many difficulties and challenges regard less the adopted framework, neural or logical.
The purpose of this paper is three-fold. First, bridge the gap between the neural framework and the conven tional one. Second, propose an effective neural model mechanizing the abductive reasoning. Third, present in structive lessons learnt from our experimentation with NdL 1 · The rest of this paper is organized as follows. Sec tion 2 points out the background and principles of this work. Section 3 presents our neural model to mechanize abductive reasoning. Section 4 shows the computation of abductive diagnoses of some illustrative examples within NdL. Section 5 briefly analyses our model and points out the important issues deserving further investigation.
2 NdL: A Brief Background
According to its definition, a cause-to-effect diagno sis (called also hypothetical or abductive [Cox and Pietrzykowski, 1987; Ayeb et al., 1993] diagnosis) is a conjecture of causes explaining all the observed effects. Clearly, a pair (DP, E) may admit several abductive di agnoses, hereafter called diagnostic candidates. An important issue is then to define some criteria pointing out the best diagnosis among the diagnostic candidates. Two criteria are usually adopted in literature: parsimony covering and maximal plausibility. Parsimony covering states that the best diagnosis must include a minimal set of causes. Such a minimality can be considered w.r.t set inclusion or cardinality set. Maximal plausibility states that the best diagnosis must have the most likelihood w.r.t a given belief function. Depending on each case, the belief function can be attached individually to causes or to causal relationships. In fact, there is a potential conflict between these criteria since the parsimony cov ering (resp. maximal plausibility) represents a global (resp. local) optimization. Fortunately, such a con flict can be resolved by adopting a precedence relation between them. Unfortunately, the soundness of these criteria is case-dependent and is based on several, how ever conventional, assumptions-see [Console et al. , 1989; Goel et al., 1988; Peng. and Reggia, 1987] for more details. In this work, we adopt these conventional as sumptions and characterize the best diagnosis in terms of minimal cardinality and maximal plausibility.
1 NdL (Neural Diagnosis Laboratory) is a component of ·dL which is written in C++ with an interface to Rochester system tool [N. H. Goddard and K. J. Lynne and T. Mintz, 1988]. Since the computation of effect-to-cause diagnoses is straightforward, in this paper NdL focuses only on the com putation of cause-to-effect or abductive diagnoses.
In order to model a diagnostic process generating such best diagnoses, the neural network should support com plex patterns of interaction between effects and causes, among causes and possibly among effects. This pro cess should allow those cells representing most plausible causes to be activated and those which are not to be in hibited. The role of competition has long been endorsed [Peng. and Reggia, 1989]. The main issue is how to model it. A simple form of competition is to sum up in puts to each cell and take the most "excited" cell or cells as the results of the competition without any transient adaptation. The precision of this form depends heav ily on the connection weights (prewired knowledge) and does not allow the network to sufficiently "relax" . Es sential causes may be kicked out if their initial activation strengths are not high. Equilibrium based competition provides better chance for network rPlaxation. However, as being pointed out in [Peng. and Reggia, 1989], it is very difficult, if not impossible, to model, through simple inhibitory connections with static weights, complex rela tionships such as competition between two causes when a common effect shows up and cooperation between them otherwise. It is also very difficult to model the "essential ness and/or plausibility" of a cause. Thus, the network should involve a dynamical activation mechanism that takes into account varieties of factors to model a desired phenomena of winners-take-others.
Our proposal is based on fundamental neural activa tion principles, discussed in [Grossberg, 1988], and a gen eralized synaptic adaptation rule of Hebb. Cells in our neural model are based on a shunting equation. Inter actions among cause cells and between cause cells and effect cells are emulated. All the cause cells which have one of the observed effects are activated at the begin ning by the active effect cells. Activities of cause cells reflect the network's belief on the plausibilities of the causes. Temporal adaptation and normalization of the weights between cause and effect cells are modeled to reflect the changes in the distribution of cells' activities, while adaptation of the weights between cause cells reg ulates inhibition strengths. Both together act in favor of those cells having the strongest support from observed effects or being indispensable to explain certain effects and allow to eliminate those causes that are not essential.
In the proposed neural architecture, cells in the net work are grouped into two main layers C representing all the possible effects, and C representing all the possi ble causes. Ultimately, we use the following conventions: the activity value Zi will denote the degree to which a cause or an effect holds. We shall use w;i to represent the weight of the (excitatory) connection between effect cell ei and cause cell c;- i.e., Wij stand for the fuzzy or uncertain (including probablistic) relationship between ei / Ci. Cause cells Ci and Ck will be connected if they have at least one common effect- i.e. iff there exists j such that w;i Wkj i= 0. The inhibitory strength between cause c; and Ck explaining their common effects will be quantified by Iik.
3 NdL: The Underlying Mechanics
The activity Zj of a given effect cell ei is set to a given constant t/Jj if the effect ei is in the given observation E -otherwise Zj is set to zero. Moreover, their activities will stay unchanged through out the reasoning process. In its turn Zi the activity of the cell Ci is governed bJ. the shunting competitive equation [Grossberg, 1988]: 1f = -Azi- Zi Ek Iik f(zk) + EjWij Zj, where A is a small positive real number (i.e., 0.1) representing the decay rate of the cell Ci. Let us rewrite the above equation as follows: ~ =-Ax;- z; IH; +EX;, where /Hi = Ek Iik f(zk) and EXi = Ej w;i Zj.
In fact, I Hi is the total inhibitory input to the cell Ci from all the other cells in the layer C. Its action on the activity of the cell c; is modulated by the activation level of the cell Ci itself. This guarantees smooth evo lution of cell activity and long transient period during which the network is devoted to the reasoning process. Conversely, EXi is the total excitatory input to the cell Ci from layer£. Observe that EX; is not modulated by Zi since EX; is a supporting evidence of the cause Ci. Note also that in absence of the excitatory inputs (i .e., EXi = 0), the activity Zi will converge to zero due to the decay parameter A.
The reasoning process is modeled by iterative updat ing of cells' activity. It can be summarized in two major stages. Steps 1 and 2 form the first stage for initializ ing all possible causes. Steps 3 to 6 form the second stage engaging the network into a competitive reasoning process. Here the different steps:
This first step consists of initializing the activity of effect cells ei by the input data. We should suppose that values t/lj be positive and normalized (i.e. bounded above).
This second step gives a formula to initialize cause cells Ci. It is obtained assuming that when the effects turn on, the network converges immediately to a sta\>le state before the competition process begins. This means ~ = 0 while IH; = 0 for all i .
This third step consists of resolving the system of non· linear differential equations in its stable state ( ~ = 0) assuming that the states of the cells vary smoothly from one iteration to another and the output of each cell /(zt) is approximately constant within a short time interval. An important property is that z; increases with EXi (depending on the connection of all weights W;j) and de creases with I Hi (depending on a great extent on the connection weights lit). Further more, when EX; > 0, we have Zi > 0.
This fourth step updates the connection weights to reflect the current variations of the network's belief on the plausibilities of the causes. The formula w;i + Wij + a Zj Zi together with the normalization w;i + w;i /llw.,j II consists of a redistribution of belief stre~g~hs w;i that ei is caused by Ci. Clearly, causes gammg greater belief are normally those that resist better the competition. On the other hand, the normalization for· mula ensures that an exclusive cause is always gaining the maximal belief, which is 1, no matter how strong the other competitive cells are.
The formula Ii,k +- l;,k - {3 D:z:; D:z:· aims at alter nating inhibitory connections. Keeping in mind that a connection l;t exists if and only if both c; and Ct have a common effect. The formula is applied only to a lit con· necting two causes that have a common effect appeared in the observation. If the activity Zi and Zt of such two causes vary in the opposite direction, then one of the causes seems to get more evidence and the inhibition weight is increased to locally accommodate the changes. On the other hand, if Zi and Zt both decrease or in crease, which is likely to happen at the beginning of the reasoning process, the network is still in the search of a right direction- especially when they both increase. This step is crucial since it implements a form of competition between cells without using the simplist winner-take-all approach. It allows to eliminate causes which don't re ceive enough support and which are not essential. In our experiments, a and {3 are chosen to 0.1 and stay unchanged during the reasoning process.
This fifth step is simply for pruning and eliminates those causal relations no more significant for the subse quent reasoning.
2 Note that 6z; (resp. 6z.) is the variation of X; (resp. %·) between two succeeding iterations.
The sixth step includes the termination test. The rea soning process is terminated when each of the remaining causes is exclusive. It is worth noting that a cause c; is temporarily exclusive if there is an effect ej such that c; is the only remained cause that has ej as an effect. Ex clusiveness is thus related to the temporal belief of the network. The goal of the network updating is to elimi nate those causes which are not considered to be essen tial and make every remaining cause exclusive w.r.t. at least one observed effect. Formally, exclusive( c;) holds iff 3ej 0 E E/Wij 0 > 0 A Wtj 0 = 0, V k -:f. i.
4 NdL: A Few Experiments
For the sake of illustration, let us consider the following mechanical diagnostic problem adapted from [Console et al., 1989] where we suppose that the mechanical knowl edge is expressed as a set of relationships between causes and effects instead of a causal network as in [Console et al., 1989].

To build the neural network (see Fig. 4.1 (b)) for our il lustrative example, NdL requires a formal specification given in Fig. 4.1 (a)- note that a complete specifica tion within NdL consists of six sections devoted to the syntactic level (e.g., network topology) as well as the semantic level (e.g., relationships interpretation, incom patibility of pairs of causes). However, only a snapshot of the specification is given to save space in this paper.
3 We have distinguished two types of relationships (i.e., MultCau5e and CanCau!e) to qualify the causal relation ships. For instance, the 1st. (resp. 3rd.) sentence of K tells us that an abnormal smoke (resp. abnormal vapour) from engine must (resp. should) be observed if the initial ca.use consists in an oil engine. Clearly, this interpretation is for the sake of illustration since one could introduce several qualifications (e.g., Lead!_To or MayManifed) expressing a variety of relationships. Such a discussion on the modeling issue is left for a subsequent long paper on NdLf*dL.


From a theoretical viewpoint, excitatory and in hibitory connection weights (i.e., Wi,j and l;t) can be initialized to any values. However, NdL does not initial ize these weights neither randomly nor in a brute force way but by first asking the user to select a initialization directive. NdL provides a variety of directives which help the network to quickly converge. Succinctly, a di rective is a mapping that quantifies the causal relation between causes and effects (excitatory connections) and those between causes (inhibitory connections). For our illustrative example, we select the following simple direc tive assigning 1 (resp. ! ) for an excitatory connection Wij between a cause c; and an effect e; depending on whether ei must (resp. might) be observed. The ratio nale behind this directive stems from the following fact: the excitatory connections must reflect our belief of the causal relation between causes and effects.
Considering the inhibitory connections l;t between two causes (say c; and ct), one common directive sug gested by NdL is to "normalize" the number of common effects between both causes. This directive is motivated by the following observation: since the connection weight between two causes reflect mutual inhibition strength it should be proportional to the number of the common effects. Nonetheless, NdL normalizes these numbers to yield small connection weights- otherwise the effect of inhibition will be so strong that the cause will not be sufficiently activated to sustain the competition process. Of course, if two causes do not share common effects then l;t does not exist- see Fig. 4.1b. Consider our illustrative example, Ioi1-engine...cou·e,H20_Ievel...couoe and J ·parlc_plug·-cau·e,corburettor_ccnue fcorbureuor_cau·e,·parlc_plug·-cau·e = 2/5
Icorburellor...cou·e.H20_IeveLcotue do not exist, whereas the other in
hibitory connections are: loil_engine_coule,·pork..plug·-cou·e = J,pork_plug·-cou·e,oil_engine_cou·e = 2/5 = 0.4; fotl_engtne_ca.ute,carburettor_catue = J carburet tor _cauae,oiLengine_caute = 1/5 = 0.2;
J·porlc_plug·-cau·e,H20.Jet~eLcau·e
1H20-level....coute,lpork_plug·-cou·e = 1/5 = 0.2;.
=
0.4;
=
Assume that we jobserve an abnormal status of lights and an abnormal acceleration, and notice a likely abnormal noise of engine. By starting NdL, a short dialog 4 leads to the specification of Eo = { ab-light1.1tatu·, ah.acceleration.engine, ah.noiu.engine} as the set of observed effects and Wo = { 1/lab_li 11h,_,, .. ,,., = 1/lob-Occelerotion_engine = 1, 1/lob_noi·e..engine = 0.5} as the initial activity of the cells corresponding to observed effects- step 1 of the reasoning.
Now, NdL enters the network in the competition pro cess summarized in Fig. 4.2.

..
~
.c:
"'
.,
1.0
0.1
0.6
~ . 0.4
0.2
10 20 JO 40 lO 60 70 10 90 100
Iter·tionJ
Fig. 4.2 (b): Weights Evolution.
The initial activities of cause cells are 0. 79 for carbu rettor, 0.52 for H20Jevel, 0.37 for spark_plugs and 0.32 for oiL.engine. Due to the mutual inhibition, oiLengine and spark_plugs causes are quickly eliminated as de picted in the evolution of the activities (Fig. 4.2 (a)) and the evolution of the excitation weights (Fig. 4.2 (b)). Conversely, carburet tor and H20Jevel causes are the winners of the competition process. From the Fig. 4.2 (b), one can see that for a surviving cause there is one weight that gradually converges to 1. This means that cause becomes exclusive- here carburettor is exclusive to gasoline....smell. At the end of this competition, NdL col lects the winners causes { carburettor, H20_/evel}, that is the final diagnosis.
Now let us consider two additional observations to point out an interesting behavior of NdL. Let E1 and E2
4 Unfortunately, we cannot report here sample snapshots of dialogs which are space consuming.
be two observations together with their initial1111 and t 2 specified as follows: E1 = ~ = {ab_acceleration_engine, ab_ignition_engine, ab_noi.5e_engine,
ab_ga.5oline_.5mell}, whereas Wt = { 1/lob_ignition_engine = 0.5,
.Pab_accelerotion-engine = t/Ja6_not·e-engine = t/Job_go·oline-·meU
= 1}, and 1112 = {"ob_ignition_engine = 1,
\bab_accelerotion_engine = t/Job_not·e....engine = ..Pob_go·oline-·mcU
= 0.5} . As before, NdL engages the network in a com
petition process summarized in Fig. 4.3.


This time NdL proposes { carburettor, spark_p/ug~J (resp. { carburettor, H20_/evel}) as the final diagnosis for E1 (resp. E2). From the formal viewpoint, both diag noses are pretty good. However if we take the interpre tation viewpoint we would prefer that both observations yield the same diagnosis { carburettor, spark_p/ugs} . The reason leading N dL to propose different diagnoses sterna from the following: our exclusivness criterion does not take the initial activities of effet cells (i.e., 111) into ac count. A slight adaptation of our neural model is under development.
5 Epilogue
Many challenges are raised by the mechanization of ab ductive reasoning regardless of the considered frame work, conventional or neural. For example, the com putational challenges within a conventional framework have been pointed out by many authors [Baylander d a/., 1991; Goel et a/., 1988; Console et a/., 1989; Ayeb d a/., 1993; Ayeb, 1992]. Considering a neural framework such a mechanization is difficult because it involves mul tiple and bidirectional inferences. Several causes may have a common observed effect, which one of them is the actual cause? Neither Perceptron-like associative neural networks nor more flexible models like ART [Carpenter and Grossberg, 1987], bidirectional associative networks [Kosko, 1988] can easily be used to produce the desired winners-take-others phenomena.
A common approach to model symbolic processing (e.g., abduction-based diagnosis) by neural networks, consists in mapping the original problem into the search ing for an ideal stable state of a dynamic neural system. This stable state usually correspond to the minimum en ergies of the system. This has been the basic principle used in [Hopfield and Tank, 1985] to resolve the Traveler Salesman Problem. The proposals suggested by Peng ~d Reggia [Peng. and Reggia, 1989] and by Goel et al. m [Goel eta/., 1988] are also based on this principle. Our proposal can also be analyzed in terms of minimization of an energy function. In fact, the main advantage of using an energy function is to model straightforwardly the process aiming at the construction of the best diag noses w.r.t minimal cardinality and maximal plausibil ity. _\Vithin. NdLa diagnosis is generated from the diag nostic candidates through competition and cooperation between causes. The plausibility of the best diagnosis results from the competition that strongly favors those causes either with a high strength or exclusive. Minimal cardinality also results from this competition process in that as long as there is a non-exclusive cause the com petition will continue.
Exponential explosion is often the main issue of abduc tive reasoning to find the best diagnosis w .r .t the adopted criteria. In fact, there are two methods to construct a neural (connectionist) system mechanizing the abduc tive reasoning. The conventional method consists of two steps: (1) propose a target/energy function modeling the adopted criteria; (2) design the architecture of the net work to optimize (maximize or minimize) the proposed function. Both proposals discussed earlier have adopted such a conventional method. The second less conven tion~! method also consists of two steps: (1) design the architecture of the network w.r.t the diagnostic problem at ~and; (2) analyze the network dynamics and the prop erties of the generated diagnosis. Our proposal adopts the second method. The main advantage of the con ventional method is to make available the target/energy function in a earlier stage. Unfortunately, such an ear lier availability imposes several constraints on the net work design and optimization mechanisms to be used. On the other hand, the second method offers the ad vantage of imposing serious constraints on the network architecture, allowing to take into account the charac teristics of the diagnostic problems. Nevertheless, such an advantage depends on the availability of means (e.g. an energy function) to analyze the network dynamics. That is why we suggest the following energy function for the proposed network. Consider the following function: Q L; z1 + f3 L; (L; w;; - VL; wl; ) 2 , where a and {3 are two given constants. Clearly, if the weights issued from each ~ffect are normalized with. the Euclidean nor~ (i .e., Li W;; = 1), then we can rewrite the above function as: Q L; zl + f3 L; (L; w;; - 1 ) 2 · Observe that both terms in the energy function are related to cardinality crite rion since each active cell of a diagnostic candidate contributes to each of them. The second term corresponds t~ the concept of exclusiveness since (L; w;; -1)2 = 0 iff 3ao such t~u':t W; 0; = 1 /1. w;; = 0, 'V i # i0 · Consequently, the exclusivity can be guaranteed provided that {3 is suf ficiently large w.r.t a . Yet, one could argue that the energy function does not explicitly take into account the plausibility criterion. However, this criterion is a built in part in the competition process. Indeed, the second phase of the proposed procedure ensures that only those cells with high sustained inputs, namely highly plausible causes, or ~ells which are/become exclusive, namely the only plausible causes for some effects, can survive the competition.
Before closing this paper, let us point out the distinc tive features of this work w.r.t related work 5 · The first distinctive feature of our proposal w.r.t those of [Peng. and Reggia, 1989] and [Goel et a/., 1988] stems from the additive updating rule while still having an energy function taking minimal cardinality and maximal plau sibility into account. This results in an effective neural network architecture. Note that the proposals of [Peng. and Reggia, 1989] and [Goel et a/., 1988] are rather connectionist network architecture (or high order neu ral network architecture) . In fact, this results from their multiplicative function to take minimal cardinality and maximal plausibility into account. The second feature of our proposal consists of the temporal adaptation of con nection weights. The connection weights are adapted t<:> .reflect the network's temporary belief on the plausi bility of causes. Thus, the competition between causes is modeled through two mechanisms, updating activities of units and updating weights. Clearly, this adaptation speeds up the convergence to generate the appropriate diagnosis. It also determines the termination condition without using arbitrary thresholds.
This work can be extended in several directions re lated to methodological, theoretical and developmental aspects. For example considering the methodological as pect, it seems important to study the different classes of diagnostic problems and define the appropriate criteria characterizing the best diagnosis of each class. In the same vein, addressing the mechanization issue of diag nosis is worthwhile. Of course, our goal does not aim at decreasing the exponential complexity of the diagnosis procedure in general. Rather, we should design an ef ficient and adequate mechanization taking into account the requirements of a given class of diagnostic problems Finally, let us mention another direction aiming at a distributed diagnostic problem solving where a complex problem is broken down into small pieces that can be solved either by a conventional diagnosis or by a neural one [Wang and Ayeb, 1992]. Such a direction is the long term goal of the ongoing project *dL where we combine in a skillful way both conventional and neural diagnosis.
Acknowledgment We are grateful to E. Jobidon who implemented the graphic interface of NdL.
~An experimental analysis w.r.t [Wald. et al., 1989; Tagamets and Reggia, 1989], &nd an extension of NdL to include non-monotonic abduction features [Josephson et al., 1987; Thagard, 1989; Bayl&nder et al., 1991] are under investigation.
@inproceedings{ijcai1993p184,
title = {Computing Effect-to-Cause/Cause-to-Effect Diagnoses Within NdL},
author = {Ayeb, Béchir el and Wang, Shengrui},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {1332--1337},
year = {1993},
note = {Neural Networks},
url = {https://ijcai.org/proceedings/1993/184},
}
TY - CPAPER TI - Computing Effect-to-Cause/Cause-to-Effect Diagnoses Within NdL AU - Ayeb, Béchir el AU - Wang, Shengrui T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 1332 EP - 1337 UR - https://ijcai.org/proceedings/1993/184 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: