A Potts Spin MFT Network Solving Multiple Causal Interactions

1 Prologue

Causal reasoning (also known as abduction [Tha­ gard, 1989; Ayeb et al., 1998)) is ubiquitous in di­ agnosis [Peng and Reggia, 1989], scientific reasoning [Thagard, 1989], natural language processing [Char­ niak, 1987], etc. The intuition behind causal rea­ soning can be stated as follows ([Goel et al., 1995; Ayeb et al., 1998)) . Given an elementary cause c, an observable effect e and the knowledge that c causes e, causal reasoning consists in hypothesizing that c occurred. The key feature of causal reason­ ing is to infer a set of composite causes from the elementary ones. These composite causes are said to form a scenario (explanation in [Thagard, 1989; Goel et al., 1995)). Unfortunately, computation of a best scenario is NP-complete [Bylander et al., 1991]. Hence, the computational time becomes prohibitive, particularly in the presence of incompatibility inter­ actions [Goel et al., 1995; Bylander et al., 1991].

Artificial Neural Networks (ANNs) are biologi­ cally motivated computational models that turned out to be efficient in solving many NP-complete optimization problems. Mean Field Theory (MFT) [Peterson and Anderson, 1987] is receiving an in­ creasing attention, mainly due to its robustness in solving many large-scale NP-complete optimization problems other methods failed to solve in general; e.g. the"Traveling Salesman" and the "Graph Par­ titioning" [Peterson and Soderberg, 1989]. MFT is a combination of the Simulated Annealing (SA) of the Boltzmann machine [Kirkpatrick et al., 1983] and the Hopfield's network [Hopfield, 1984] . Hopfield's network is mainly characterized by the simplicity of its neurons and its efficient hardware implemen­ tation. However, a major drawback of Hopfield's network is its deterministic nature so that the net­ work gets easily trapped into poor local minima as the problem size increases. SA is a stochastic hill­ climbing algorithm that uses a gradient descent com­ bined with probabilistic movements. The simulated annealing process consists of first melting the system at high temperatures, then slowly decrease its tem­ perature until the neurons "crystallize" and formu­ late a solution for the case at hand. However, due to the stochastic and annealing processes, the compu­ tational time could be unacceptable. Merging both Hopfield 's network and SA, MFT has shown to be ef­ ficient in finding optimal solutions for academic and real-world NP-complete problems. Another impor­ tant issue of MFT is its ability to compute optimal (or near optimal) solutions in practical time spans even for large-scale problems.

In the current work, we use Potts spin MFT an­ nealed networks to address the open, independent and incompatibility classes of causal reasoning. The strong feature of the current work is the character­ ization of the reasoning process in these classes by an energy function. The remainder of this paper is organized as follows. In section 2, we outline the minimal preliminary material and give a real-world causal problem. In Section 3.1, we formulate the energy function for open, independent and incom­ patibility causal problems. In section 3.2, we use MFT Potts modeling and mean field equations to minimize our energy function. Section 3.3 describes our algorithm and section 3.4 gives illustrations. Fi­ nally, the paper is concluded in section 4.

2 Background

The main purpose of this section is to formalize the open, independent and incompatibility classes of causal reasoning and to give an introductory causal problem.

2.1 Preliminaries

A causal problem is entirely described by a set of possible effects £ = { e1, · · · , em}, a set of possible causes C = { c1 , · · · , en}, and a set of causal inter­ actions R . Several and multiple causal interactions could be modeled in R and thereby several classes of causal problems could introduced. Formal defini­ tions follow.

Definition 2.1 We use <p E R to denote a causal interaction in n.

• <p is an independent interaction if it is expressed w as: c f--t e
• <p is an incompatibility interaction if it is expressed w' as: ci 1\ Ck f--t ..l

where w {resp. w') is a real number measuring the strength of the causality {resp. incompatibility) be­ tween cause c and effect e (resp. causes Ci and ck)

·

In Definition 2.1, ..l denotes the null effect, i.e. an effect that can never be observed. Now, we express the concept of a manifestation (observation in [Tha­ gard, 1989; Goel et al., 1995)) for a causal problem as follows.

Definition 2.2 Let CP(£,C, R) be a causal prob­ lem. A manifestation M M for CP is a three-tuple (Ep, EA, Eu), where Ep, EA and EA are the three finite sets of present, absent and unknown effects, respectively ·

According to Definition 2.2, each possible effect in £ is assigned a state. It is present if it is known to occur, it is absent if it is known not to occur, and it is unknown if we have no "knowledge" about it. In a practical situation, an effect is unknown if its "value" cannot be accessed for some reasons 1 . Now, we are ready to define the independent, open and incompatibility classes of causal problems as follows.

Definition 2.3 Let CP(£,C, R) be a causal prob­ lem. Let MM(Ep,EA,Eu) be a manifestation for CP, then

• CP belongs to the independent class if V<p E R, <p is an independent interaction.
• CP belongs to the incompatibility class if 3<p E R such that <p is an incompatibility interaction.
• CP belongs to the open class if EA i= 0 ·

1 Among reasons; let us mention safeness, time.

Now, we need the following notation inspired from [Bylander et al., 1991] to define the concept of a scenario (explanation in [Thagard, 1989; Peng and Reggia, 1989)).

Definition 2.4 Assume that cause c covers effects e1 and e2, i.e. c A e1, c A e2. We define COVER, a function from C to£, as: CovER(c)d~ { e1 , e2}. If C denotes a subset of elementary causes, then COVER( C) d;j U cEC COVER(c). ·

Definition 2.5 Let CP(E,C, R) be an independent, incompatibility and/ or open causal problem. Let MM(Ep,EA,Eu) be a manifestation for CP. A scenario for C P w. r. t. M M is a subset of elemen­ tary causes C E C such that: {i) Ep ~ COVER(C) ; {ii} C is minimal; {iii}..lf/. COVER(C); {iv} EA n CovER( C) is minimal. If among all scenarios, C optimizes a given belief function measuring the over­ all quality of scenarios, then C is called a best sce­ nario. ·

In Definition 2.5, the minimality criterion is taken w.r.t. set cardinality. One should remark the poten­ tial conflict between criteria (i), (ii), (iii) and (iv). Unfortunately, it is not always guaranteed to meet all these criteria in a single scenario. This explains why characterization of a best scenario carries cer­ tain arbitrariness [Goel et al., 1995]. However, a precedence relationship could be adopted. For our concern, we adopt a decreasing precedence relation for criteria (i) to (iv) with criterion (i) assigned the highest precedence.

2.2 A Medical Causal Problem

('I'll laryngitis ~ inflamed-throat ('1'2) laryngitis ~ expectoration ('I' a) laryngitis ~ cough ('1'4) laryngitis ~ lost-voice ('l's) pneumonia ~ fever ('1'6) pneumonia 2;~ cough ('1'7) pneumonia ~ headache ('l's) pneumonia. ~ dyspnea 'R= (<pg) pneumOnia ~ expectoration ('1'1o) pneumonia g thoracic-pain ('l'u) sinu3iti8 ~ headache ('1'12) sinusiti8 ~ noise-pain ('1'13) sinusitis ~ nasal...discharge ('1'14) tonsillitis ~ inflamed-throat ('1'15) tonsillitis~ fever ('1'16) sinusitis A pneumonia g..L ('1'17) laryngitis A tonsill i tis ~ 1.

For the sake of illustration, we consider CPMn(C, £, R), a relatively small causal prob­ lem from the medical domain. £ = {cough, dyspn ea , expectoration, fever, inflamed-throat, headache, lost-voice, nasaLdischarge, nose-pain, thoracic-pain } are the possi­ ble symptoms (effects in our model). C ={laryngitis, pneumonia, sinusitis, tonsillitis} are the possible diseases (causes in our model). The set of causal interac­ tions R is summarized in Figure 1. For instance, the causal interaction cps teUs us that pneumania causes dyspnea with the maximal causality 1, whereas cp17 tells us that laryngitis and tansillitis are incom­ patible diseases with a relatively high degree, 0.85. This means that laryngitis and tansillitis are in­ coherent and cannot coexist together. One should remark that the causal interactions in CPMn (as well as in our modeling) are a matter of degree rather than being either/or (cause/not-cause, com­ patible/incompatible). This allows flexibility since real-world causal interactions are generally modeled from scratch.

3 Proposal

3.1 Formulation of the Energy Function

Let MM(Ep,EA,Eu) be a manifestation for CP(t',C, R), the causal problem at hand. We use j and l to index all quantities related to effects, while we use i, k and n to index all quantities related to causes. card( X) denotes the cardinality of the finite set X . Wij E]O, 1] is the strength of the causality be­ tween cause c; and effect ej. We denote by B;k E]O, 1] the strength of the incompatibility (or incoherence) between causes c; and Ck. 1J! = ( 'l/J1, · · · , '1/Jt) measures our belief in the presence (resp. absence) of effects in Ep (resp. EA)· Unknown effects (Eu) have a null certainty degree, i.e. 'l/;j = 0 Vej E Eu. For each present effect ej, we associate a set of discrete variables Sij, defined as follows :

The variables Sij are called Ising spin variables. S is the vector of variables Sij.

We define the "cover level" of a cause c; w.r.t. M M as follows:

where Cij = Wij'l/lj Vj. E; is null if c; does not cover any of the present effects. The vector of cover levels is E = [E1, E2, ···,EN f. Hence, the cover level of all possible causes in C is computed by:

Maximizing J1 (S) is equivalent to putting "on" all Ising spin variables. Hence, for each effect one or more Ising spin variables, and thereby one or more causes, are active. This kind of competition is re­ ferred to in ANNs as winner-takes-others (WTO), since more than one competing cause are active at the end of the competition. However, a winner­ takes-all (WTA) competition is necessary to ensure that a cause takes exclusivity in the coverage of a given effect, and thereby meet the minimal cardi­ nality criterion. One possible way is to considerably limit the resources of competition between causes, i.e. to activate the minimal number of Ising spin variables for each present effect. The number of ac­ tive Ising spin for effect ej is given by r j = Li Sij . However, in order to ensure a coverage of ej, at least one corresponding Ising spin must be active. For this, we define the following constraint:

Maximizing J1(S) in (4) under the constraint h(S) in (5) will push each cause to maximize its individual cover level and to take the exclusivity in covering the present effects. Causes with the highest cover levels are more likely to win the competition than those with the lowest ones.

The open class of causal reasoning is modeled as follows. For each cause c;, we define a penalty factor A; by:

Ai = 1 if C; does not cover any absent effect, and A; « 1 otherwise. We use these factors to weight the cover levels of causes. Thus, we redefine equation (4) to:

where A = diag[AI. ···,AN]· From equation (7), one can see that causes are strongly penalized if they cover some absent effects. Consequently, these causes enter the competition less effectively, and therefore are more likely to loose it, than other causes than do not cover absent effects.

In computation of a scenario, we should avoid si­ multaneous activation of incompatible causes. For this, we define the following constraint:

where e = [Bik] is the matrix of incompatibility in­ teractions. We should note that e is null-diagonal, i.e. B;; = 0. In fact, each cause is totally com­ patible with itself by definition. Minimizing J3 (S) would prevent a simultaneous activation of incoher­ ent causes. Particularly, h (S) is null if all active causes are totally coherent.

Using equations (7), (5) and (8), we characterize the reasoning process in the open, independent and incompatibility classes of causal reasoning by the fol­ lowing energy function:

where a and f3 are Lagrangian multipliers used to weight the distinct constraints in the energy func­ tion J(S) . Due to the precedence relationship be­ tween the coverage (see Definition 2.5), minimal cardinality and coherence criteria, one must have 0 < a < (3 < 1. Minimization of the energy function J(S) in equation (9) leads to inference of a minimal set of coherent causes covering the present effects and avoiding coverage of the absent ones.

Obviously, minimization of the energy function J(S) in equation (9) is not a trivial matter due to the huge number of possible states. A state is defined by the Ising spin variables Sij. Naturally, the complexity of the search space is problem-/case­ dependent. Hereafter, w.e derive its expression in the worst-case, i.e. assuming that all effects are present and that each effect is covered by all possible causes. In this case, the dimension of the search space is 2NcxNe , where Nc = card(C), and Ne = card(£). Consequently, the remaining task is to employ a ro­ bust method to optimize our energy function: by robustness here, we mean the ability of finding op­ timal solutions in practical time spans. Evidently, the use of sequential search approaches is inappro­ priate and indeed impossible for large-scale causal problems. Gradient descent methods which are local in scope are not applicable since they can be easily trapped into poor local minima. Mean Field an­ nealing techniques have been shown to be robust in solving large-scale combinatorial optimization prob­ lems as the the "Traveling Salesman" and "Graph Multi-Partitioning" [Peterson and Soderberg, 1989], to cite just a few. For details about MFT methods, we refer the interested reader to the specialized lit­ erature, for example [Peterson and Anderson, 1987], [Peterson and Soderberg, 1989). In the next section, we use MFT Potts spin modeling to derive the me­ chanics of our model.

3.2 Potts spin MFT Modeling

The Ising spin variables Sij are replaced by continu­ ous variables Vij representing their thermal averages; i.e. Vij =< Sj >r, where T is said the annealing "temperature" of the system. At a given T, the probability Vij obeys a Boltzmann distribution:

where ¢ij is given by:

The variables ¢ij are called the mean field variables. Vij are called Potts spin variables and their proba­ bilistic interpretation is evident.

Due to equation (10), the energy of the network J(V) in equation (9) is transformed to:

Let us first remark that due to equation (10), the constraints ri = 1 holds automatically. That's why we have omitted the a-term in (12). Due to the continuous nature of Vij, the last term in (12) is added to force Vij variables to converge either to 0 or 1 - see [Wang and Ansari, 1997) for a similar approach. Using equations (11) and (12), the mean field variables ¢ij are given by:

Using equation (10), we can see that Vij -+ 1/"'j when T -+ +oo, with "'j being the number of causes covering ej . As (T-+ 0), fixed points {0, 1} emerge. Potts spin MFT modeling has many advantages for causal reasoning. First, due to formula (10), the di­ mension of the search space is reduced from 2NcxN. to N:'·. Second, it ensures that a present effect ej is always covered by some active causes since I:m Vmj = 1 always holds. In the next section, we describe the mechanics of our algorithm.

3.3 The Algorithm

Our algorithm is summarized in Figure 2. In the initialization phase, we compute the >..i factors due to absent effects. Moreover, we set T 0 , p and (3. We should note that one can use a progressive (3 to emphasize constraint violations at low tempera­ tures, i.e. (3 <X 1 /T. The Potts spin variables are initialized to their high-thermal averages and some small random bias is added to "break the symme­ try" of the system of neurons (if any). In fact, in

Figure 2: Solving Multiple Causal Interactions

some cases, more than one equivalent solutions ex­ ist for the causal problem at hand, and without an unbiased start the algorithm is unable to choose a direction to follow.

Thereafter, we update synchronously mean field and Potts spin variables. In computing Potts spin variables, we use a "time-step" p to avoid the "flip­ flop" behavior of the synchronous mode [Peterson and Soderberg, 1989]. However, one has to set pas close as possible to 1 since this results in a slower convergence by a factor p.

The algorithm terminates when all Potts spin vari­ ables saturate at 0/1, the rate of change A or the temperature of the system are both small enough. In figure 2, JC is the total number of Potts spin vari­ ables and is given by JC = L:ejEEp "-j· Regarding the saturation criteria :E, one can see that:

The output of our algorithm consists of those causes surviving the competition; i.e. whose cover levels are not null. Hereafter, we illustrate the mechanics of our algorithm on a medical causal problem.

3.4 Illustration

In this section, we run our algorithm on CPMn, the medical problem introduced in section 2.2. In our simulation, we used the following parameters: the cost-term {3 = 0.5, the initial temperature T(O) = 2.0, the "time-step" p = 1.0. Moreover, we have used the annealing scheme Tt+l = 0.92 Tt, where t is the "time-counter".

We considered a manifestation MM(Ep, EA, Eu), where Ep = {cough, expectoration, inftamed_throat, headache, losLvoice, nose_pain}, EA = {dyspnea, fever} and Eu = { nasaLdischarge, thoracic_pain}. nose-pain somewhat occurs. This is modeled by assigning nose_pain a degree of certainty 1/Jnose_pain = 0.4. The rest of the present effects are assumed to occur with a relatively high degree of certainty, 0.9. dyspnea and fever are absent with relatively weak degrees of certainty: 1/Jdysvnea = 0.2 and 1/Jtever = 0.3. Re­ member that unknown effects ( nasaLdischarge and thoracic-pain in this case) are automatically assigned a null degree of certainty by the algorithm. The computed scenario for M M by our algorithm is SCENARIOMD ={laryngitis, sinusitis} since these are the diseases (causes) winning the competition­ see Figure 3. laryngitis enters the competition with a strong activation since it ensures coverage of the majority of the effects in Ep. This allowed laryngitis to endure the competition more effectively than the rest of the diseases and to be included in SCENMD· In contrast, tonsillitis starts to compete with a weak activation since it only covers inftamed_throat. In ad­ dition, tonsillitis is penalized since it covers the ab­ sent effect fever. Hence, tonsillitis does not survive the competition for long and is dragged down toward 0 around the 7th iteration - see Figure 3. sinusitis and pneumonia start the competition with the same activation level. However, sinusitis sustain the com­ petition mainly due to its exclusivity in covering the present effect nose_pain - see Figure 1. Due to its in­ compatibility with sinusitis, and to its coverage of the absent effects dyspnea and f~ver, pneumonia is slowly "weakened" as the competition continues and "dies" around the 16th iteration- see Figure 3. One should remark that SCENMD (1) ensures coverage of all present effects, (2) is composed only of coherent dis­ eases, (3) avoids cover of all absent effects, and (4) is minimal w.r.t. set cardinality since removing either sinusitis or laryngitis from SCENMD will lead only to a partial coverage of Ep. Remark that SCENMD is the best scenario that can be proposed. In fact, other scenarios as {tonsillitis, sinusitis} or {tonsillitis, sinusitis, pneumonia} will respectively lead only to a partial coverage of E p or to a scenario including incoherent diseases.

4 Epilogue

In this paper, we presented a Potts spin MFT an­ nealing model for mechanization of causal reason­ ing in the open, independent and incompatibility classes. We characterized the reasoning process in these classes by an energy function to be minimized by means of Mean Field equations. The main contri­ butions of this paper can be summarized as follows. To our knowledge, it is the first proposal in the lit­ erature that models an explicit energy function for independent, open and incompatibility causal prob­ lems; and use MFT Potts spin modeling to encode its dynamics. The use of MFT Potts spin method has many advantages for causal reasoning. First, it au­ tomatically ensures a total coverage of the present ef­ fects. To date, no existing neural model in the liter­ ature meets this criterion, particularly in large-scale causal problems. Second, it is able to find, in practical time spans, optimal solutions since it avoids efficiently poor local minima of the energy function. Third, its inherent parallelism renders the hardware implementation of the model possible and indeed de­ sirable. We have numerically compared our model to a recent abductive model presented in [Ayeb et al., 1998] on a large-scale medical problem composed of 26 diseases, 56 symptoms and 465 causal interac­ tions; using a huge battery of 1000 cases. Simulation results revealed that our model performs better than the model in [Ayeb et al., 1998] in computing opti­ mal scenarios, in much less CPU time. Due to the space limit, these benchmarks will not be reported herein .

As one should expect, there are some shortcom­ ings in the current work. An important issue is extension of our model to include cancellation and monotonic interactions [Bylander et al., 1991], which have to be addressed in future research. Remem­ ber that cancellation interactions involve not only causes, but also effects [Bylander et al., 1991]. Re­ garding additive interactions, they suggest cooper­ ation between causes [Goel et al., 1995]. Unfor­ tunately, additive/cancellation interactions cannot straightforwardly implemented by means of spin ( ei­ ther Potts or Ising) modeling.

Finally, use of MFT methods raises the problem of a so-called "critical temperature" [Peterson and Soderberg, 1989]. During the thermostatic opera­ tion of MFT equations, a critical temperature Tc is reached at which each Potts spin begins to move predominantly to 0 or 1. Estimating Tc can save time since annealing at temperatures much higher than Tc is in vain [Peterson and Soderberg, 1989]. Unfortunately, we found no general methodology in the literature for estimating Tc . Most proposals esti­ mate Tc empirically using many assumptions which are valid only for the tackled problem. However, the methodology adopted in [Peterson and Soderberg, 1989] seems to be applicable for many combinato­ rial optimization problems and could be adapted to our case. In [Peterson and Soderberg, 1989], Tc was estimated by forming a small signal model of the system of spins and finding the eigenvalues of the matrix which expresses the interactions between the linearized neurons. Unfortunately, computing the eigenvalue of the interaction matrix is difficult espe­ cially in large-scale causal problems and if the goal is to infer scenarios within reasonable time scales. Most importantly, is that the interaction matrix is case-dependent, i.e. it varies from one manifesta­ tion to another given the same causal interactions. Hence, it is unworthy to proceed this way since the computational burden will not be negligible. How­ ever, it would be more appropriate to estimate Tc (or even an upper bound of it) from the set of causal strengths (independent and incompatibility) since these do not vary from one case to another. The last point is under investigations.

Acknowledgment

The author wish to thank Prof. Bo Soderberg for his helpful discussions about MFT. Mr L. B. Romdhane is supported by a joint CIDA/ ACDI and MUET (Montreal) fellowship.