{'fraction_non_alphanumeric': 0.046149032695416384, 'fraction_numerical': 0.01168065912290765, 'mean_word_length': 4.126436781609195, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Integrating Probabilistic, Taxonomic and Causal Knowledge in Abductive Diagnosis

We propose an abductive diagnosis theory that integrates probabilistic, causal and taxonomic knowledge. Probabilistic knowledge allows us to select the most likely explanation; causal knowledge allows us to make reasonable independence assumptions; taxonomic knowledge allows causation to be modeled at different levels of detail, and allows observations be described in different levels of precision. Unlike most other approaches where a causal explanation is a hypothesis that one or more causative events occurred, we define an explanation of a set of observations to be an occurrence of a chain of causation events. These causation events constitute a scenario where all the observations are true. We show that the probabilities of the scenarios can be computed from the conditional probabilities of the causation events. Abductive reasoning is inherently complex even if only modest expressive power is allowed. However, our abduction algorithm is exponential only in the number of observations to be explained, and is polynomial in the size of the knowledge base. This contrasts with many other abduction procedures that are exponential in the size of the knowledge base.


Introduction
Abduction is the inference to the best explanation. To arrive at the best explanation, an abductive reasoner must make use of information from disparate sources. For the problem of abductive diagnosis, efforts have been made to integrate probabilistic and causal knowl edge [Cooper, 1984;Peng and Reggia, 1987;Pearl, 1988;Lin and Goebel, 1990a], causal and taxonomic knowl edge [Patil, 1987;Kautz, 1987]. None of these, however, is able to accommodate all three kinds of knowledge. The difficulties of integrating causal and taxonomic knowledge include the following: 1. Although the links in belief networks [Pearl, 1988;Cooper, 1984] are not limited to causal links, "isa" links cannot be treated in the same ways as other links in the belief networks. (We elaborate in Sec tion 6.2.) 2. Probability alone is not enough to rank explana tions. For example, the probability of getting sick is never less than that of getting a cold. However, the former is not necessarily a better diagnosis than the latter.
We propose an abductive diagnosis theory that in tegrates probabilistic, causal, and taxonomic knowl edge. Probabilistic knowledge allows us to select the most likely explanation; causal knowledge allows us to make reasonable independence assumptions; taxonomic knowledge allows causation to be modeled at different levels of detail and observations be described at different levels of precision.

�. ·
Our model represents domain knowledge with a causal network. Unlike most other approaches, where a causal explanation is a hypothesis that one or more causative events occurred, we defi ne an explanation of a set of observations to be the occurrence of a chain of causa tion events. These causation events constitute a scenario where all the observations are true. We show that the probabilities of the scenarios can be computed from the conditional probabilities of the causation events.
Computational inefficiency has been a major difficulty with abductive reasoning systems. Abductive reason ing is inherently complex even if only modest expressive power is allowed. Our algorithm, however, is exponen tial only in the number of observations to be explained, and is polynomial in the size of the knowledge base. This contrasts with many other abduction procedures that are exponential in the size of the knowledge base.
In the next section, we explain the notion of causation event. Section 3 introduces the concept of scenario. In Section 4, we show that the probability of a scenario can be computed from the conditional probability of causa tion events. In Section 5, the problem of finding the most probable explanation is solved by relating it to the Steiner Problem in Graphs [Dreyfus and Wagner, 1972]. Relationship to other research is discussed in Section 6. Our contributions to abductive diagnosis are sum marized in Section 7.

Causation events
The concept of causation event was first introduced by Peng and Reggia [Peng and Reggia, 1987] to explicitly represent the statement "x actually caused y. " A causa tion event C"'-+ e is true "iff both [the cause event] c and [ the effect event] e occur and e is actually being caused by c [Peng and Reggia, 1987, p.149]." One of the mo tivations for distinguishing causation events from other events in a probabilistic causal world is that C"'-+ e cannot be expressed by a Boolean expression of the events c and e, because in situations where both c and e occur, C"'-+ e may still be false.
Unfortunately, Peng and Reggia's definition of cau sation event does not provide a way to judge whether a causation event occurred, because, unlike other basic events, causation events are usually unobservable. We can only observe the co-occurrence of the cause and ef fect.
Here we present a definition of causation event follow ing a suggestion from PearF. First, note that causation can be modeled at different levels of details [Patil, 1987]. A causation event at one level of representation may cor respond to a chain of micro causation events at a more refined level. If c ..._ _. e corresponds to a chain of micro causation events c-... .. it, it-... .. i2, ... in"'-+ e then, when c..._. . e occurs, not only must c and e must occur, but also must the intermediate micro events it, ... , in. With this definition, c and e must be true if C"'-+ e is true.

3
Knowledge representation We use a language< E, C, H >to represent the domain knowledge, where 1. E is a finite, non-empty set of events, each repre senting the presence of a disorder, a symptom or a pathological state. 2. C C E x E is the set of causation events.
3. H C E X E is the "isa" relation in E. C and H are disjoint. We use e1 � e2 to denote that et is an e2 and � * to denote the reflexive and transitive closure of the "isa" relation. The diagrammatic form of the language is a causal network where each node represents an element in E. Elements inC and H are represented by causal and "is a" links respectively. Figure 1 shows an example of causal network.
Definition 3.1 (scenario) A scenano as a pair (culprit, c ausations), where culprit E E, and causations C C. Participants in a scenario are the events in E that must be true in the scenario. We define scenario and its participants recursively as follows: 1 Personal communication  2. Let (a, a) be a scenario. Let c0 be a maximally specific event in participants( a, a) , i.e., -,3d ::j: co, d�*co, d E participants( a, a) . Let Ct be an event such that co�*Ct. The condition 2.c ensures that the scenario ( Ct, {3) is not preempted by a more specifi c scenario when com bined with (a, a) . When such (c3, {3') exists, at least some part of ( c2 , "Y ) is related to co via a more specifi c class. Ct is called the reference class of co with respect to ( c2, "Y). This notion of reference class is a generaliza tion of the one in [Kyburg Jr., 1982], where the reference class is with respect to a property.
In Figure  Given a set of observations, explanations are scenarios where the observations are true. Such a scenario can be regarded as a tentative reconstruction of the causal evolution which has led to the observations.  I  I  I  I  I  I  I  I  I  I  I  I  I  I  I  I  I  I  I   I   I   I   I   I   I   I   I   I   I   I   I   I   I   I   I   I   I • ct 5. a non-scenario Multiple independent disorders To allow for mul tiple independent disorders, we can add a distinguished event T to the set of disorders D and causation events T..,... d for all disorder d such that d has no other causes. T is always true and T ..._ _. . d is true iff d is true. When T is the culprit of a scenario, the scenario may contain multiple independent disorders. 4

Probabilities of scenarios
A probability space is a triple (0, A, P) [Galambos, 1988], where n is the sample space, A is a u-field of subsets of n and p is a real-valued probability function P: A .... .. .. [0, 1].
In the probability space we use, n consistists of as signments of truth values to the elements in E U C, i.e., n = {!If: C U H �--+ {0, 1}}. The set of events, A, con sists of all subsets of n. Corresponding to each element e of EUC, there is a basic event in A: {!If En, f(e) = 1}. Without confusion, we also denote this basic event by e. It can be seen that all the events may be constructed by intersection and complement operations on the basic events.
Let x E E, x ..,... y E C and a = {Xi ..._ _. . Yi I i = 1, ... , n, Xi..._ _. . Yi E C}, we write P(x), P(x..,... y), and P( a) to denote the probabilities of x, x--... . y and a re spectively. A scenario is true if and only if the culprit event is true and all the causation events in the scenario are true. Therefore the probability of a scenario (a, a) is P(a, a) , the joint probability of its culprit a and the causation events a.

Independence assumption
Let (a, a), co and (c1,/3) be defined as in Definition 3.1. Then we assume (a, a) is conditionally independent of /3 42 given c1: P(/3lc1, a, a)= P(/3icl) Intuitively, this ass umption means that whatever caused c1 can only influence the effects of c1 via c1. This assumption is similar to the axioms of belief networks in [Pearl, 1988]. Estimating the conditional probabilities In [Lin and Goebel, 1990b], we have shown that under rea sonable assumptions about causal influence, P(elc) -P(c .... .. .. elc) < P(e). Therefore, when P(e) is significantly less than P(elc), which is usually the case, P(c ..._ _. . elc) can be approximated by P(elc).

5
Finding the most probable explanation We now quantify the causal link from node x to node y by a weight log( p(�lx) ) and associate weight 0 with "isa" links and a weight log( P C x ) ) with each node x. Then for any explanation (a, a), log( P( l , a) ) is the to tal weight of all the links in (a, a) plus the weight of the root. Since maximizing P( a, a) is equivalent to minimiz ing log( P( ; , a) ), the problem of finding the most proba ble explanation becomes that of finding the minimum weight explanation. The latter problem is a variation of a graph-theoretic problem known as the Steiner Problem in Graphs which can be formally stated as follows: It is well known that the Steiner Problem in Graphs is NP-Complete [Garey and Johnson, 1979, p . 208]. This, however, does not imply that our model is computa tionally intractable. The admissible inputs must also be taken into consideration lLevesque, 1989). A crucial observation here is that the number of observations to be explained in a single case is usually small, much smaller than the number of nodes in the network.
In [Lin and Goebel, 1990a], we present an algorithm for finding the most probable explanations in networks without "isa" links. The algorithm simulates a set of pro cesses distributed over the nodes in the networks. Each process performs the same local algorithm, which con sists of receiving, processing and sending messages that are transmitted across the edges . The messages contain optimal solutions for smaller subproblems. These sub solutions are combined at the receiver node to generate larger optimal solutions, which in turn are sent further. The worst case complexity is 0(3kn+ 2ke), where k is the number of observations to be explained, n and e are the number of nodes and edges in the network, respectively. The average complexity is reduced by exploiting the lo cality of the nodes to be connected. The nodes that are unrelated to the observations will not be involved in the computation at all.
The algorithm in [Lin and Goebel, 1990a] can be ex tended to deal with taxonomic structure in the network by adding local constraints to the process at each node. The transmission and combination of the messages are governed by the local constraints such that only the weight of valid scenarios are computed and minimized. The complexity of the revised algorithm is 0(3kn+k 2k e). 6 Relationship to other research 6.1

Early expert systems
Research on abductive diagnosis was pioneered by early expert systems such as CASNET [Weiss et al., 1978] and INTERNIST [Miller et al., 1982] . The need for integrat ing probabilistic, causal and taxonomic knowledge has been recognized in the design of these systems [Fin in and Morris, 1988]. Although these systems have achieved sig nificant results, they have often been criticized for their use of poorly defined and unjustified weighting schemes and scoring heuristics as well as unreasonable assump tions about probability distributions. In contrast, the weighting and scoring scheme in our model are based on formal probability theory. We have also provided a clear specification of the diagnosis task.

Belief Network
Belief networks [Pearl, 1988] are directed acyclic graphs in which each node represents a random variable (or un certain quantity) which can take on two or more possi ble values . Causal explanations are instantiations of the variables of the causal network and are obtained by a distributed message propagation. The propagation al gorithm, however, is designed for singly connected net works, (i.e. networks with no undirected loops) [Pearl, 1988]. Although he also proposed two extensions to mul tiply connected networks (clustering and conditioning), both methods are liable to exponential complexity [Hen rion, 1987].
Another problem with the belief revision procedure is that an explanation consists of instantiations for all the variables in the network. This implies that every piece of evidence must be propagated to the entire network, even to the totally irrelevant sections of the knowledge base [Pearl, 1988, p . 259]. As was discussed in [Lin and Goebel, 1989], our message passing algorithm is able to exploit the locality of the observations to be explained. The nodes that are unrelated to the observations are not activated during the message passing process. (1) (2) Figure 3: Isa link must be treated differently "Isa" links cannot be trivially included in belief net works because an a � b cannot be simply treated as a link for which P(bla) = 1. Comparing (1) and (2) in Figure 3, for example, the influence of d on e via a should be preempted by the link from d toe, whereas in (2), the influence of d' one' via the two paths should be combined.

Evidential recognition
Shastri [Shastri, 1989] has studied evidential reasoning in a network representation language. Nodes in his net work represent concepts, and there are two kinds of links: "isa" links and "has-property" links. A "has-property" link from concept c to the value v of a property p denotes that the concept c may have v as the value for property p. The num_ ber of instances of c is denoted by #c and the number of those having v as the value for property p is denoted by #c [p, v]. An example is given in Figure 4. The number in the box is the number of known instances of the concept. The number by an edge is the number of instances having that property value.
An important feature of the representation language is the partial specification of statistical information. If #c [p, v ] is not specifi ed for a concept c, it may be inher ited from a maximally specific super class c' of c with   I  I  I  I  I  I  I  I  I  I  I  I  I  I  I  I  I  I  I   I   I   I   I   I   I   I   I   I   I   I   I   I   I   I   I I I I Figure 4: Knowledge about fruits #c'fp, v] specified. c' is said to be relevant to c with respect to [p, v].
Evidential recognition may be described as follows: given a set of candidate concepts C-SET= {cl> c 2 , ••. , en} and a description DESCR= {fpl> v1], [p 2 , v 2 ], ..• , fpm, vm]}, where [pi, vi] is a property value pair, find c* E C-SET such that c• is the most likely concept described by DESCR among C-SET. For example, given C-SET= {apple, grape}, DESCR= { [has-color, green], [has-taste, sour]}, find which of apple and grape is more likely. Ev idential recognition is abductive in the sense that one is seeking the concept that best exemplifies the described properties.
Shastri identified two sets of assumptions which when satisfied, allows the most probable concept to b� com puted using the principle of maximum entropy. The first is the "Unique relevant concept" assumption [Shas � ri, 1989, p.33 7], i.e., for each property-value pair fp, v] m DESCR, there exists a unique concept relevant to a candidate concept c with respect to fp, v]. The sec ond assumption is more complex; checking whether a given C-SET satisfies the assumption may take exponen tial time in the worst case.
The representation language in [Shastri, 1989] is in adequate to represent causal knowledge because unlike properties, which are directly associated with concepts, symptoms may be indirectly caused by disorders. There fore, Shastri's representation language does not provide any mechanism to model causal chaining. Note further, that the user is required to supply the set of candidate concepts C-SET.
Our algorithm for diagnosis may also be used for evi dential recognition in Shastri's network. To do this, we associate log( # t , v ] ) with the "has-property" link from concept c to property value v and log( �c) with node c.
The most probable concept is found by connecting the nodes representing the property values in DESCR, using our algorithm for diagnosis. When the "Unique relevant concept" assumption is satisfied, Vc E C-SET, there is only one sce nario (c, a) containing DESCR. The total weight of this scenario is log( #c ) + I:(p,v]eDES CRlog ( #�f:.vJ ) 44 where Cp is the relevant concept of c with respect to fp, v]. The minimization of the weight is equiv alent to maximization of the score in [Shastri, 1989, p.33 7 ] : # c TI [p,v]eDE SCR #'if.�·"1. Therefore , our algo rithm gives the same answer as Shastri's.

Conclusion
We have described a model of abductive diagnosis that is relatively efficient, and that can make use of causal probabilistic and taxonomic knowledge about a proble� domain. Our representation is based on an elaboration of Peng and Reggia's idea of "causation event," extended to account for the intuition behind multiple levels of cau sation.
The network form of causation relations is similar to Pearl's belief networks, but uses a Steiner Tree algorithm to identify scenarios which constitute the required ex planations for observed symptoms. In addition, a nat ural independence assumption allows relatively efficient computation of the probability of the most likely sce nario without requiring that probabilities be propagated throughout the complete network.
Finally, we provide a definition of scenario that ac commodates the notion of taxonomic knowledge by pro viding a restriction to most specific scenarios. The ex tended definition permits us to express taxonomic rela tions amongst events, and retain the probabilistic rank ing of scenarios.
Much work remains, including the application of our model to provide important feedback about the clarity of the model's semantics, as well as further evidence of its practical efficiency.