Computational Complexity of Hypothesis Assembly

I. Introduction

The problem of abductive reasoning (as proposed by the philosopher C.S. Peirce) has been a topic of much recent interest in Artificial Intelligence (Miller 1982, Reggia 1983, Charniak 1985). The general task faced by an abductive reasoning system is to find the best explanation of a set of data or observations, i.e., the best way to account for a set of data. Most of the work in Artificial Intelligence in this area has focused on a specific kind of abduction, which we call hypothesis assembly. The hypothesis assembly task assumes as given a set of hypotheses with some knowledge about what sorts of data each can account for, and finds the subset of these hypotheses that best accounts for the problem data. At the Ohio State Laboratory for Artificial Intelligence, Josephson et . al. (1985) have been developing an approach for abduction based upon hypothesis assembly.

In this paper we will begin by presenting a mathemati­ cal idealization of this approach. From this we will analyze the complexity and correctness of the algorithm. Then we will examine how well this idealization matches with real world concepts of abduction. In particular, we will examine a system called RED, based upon this approach, which per­ forms antibody identification in the domain of red blood cell typing, as described in (Josephson 1984), (Josephson 1985) and (Smith 1985), and show how the general mathematical results respond to questions that have been raised (Mostow 1985) about its complexity.

This work has been supported by the National Li­ brary of Medicine under grant LM-04298, the National Sci­ ence Foundation through a Graduate Fellowship, and the Defense Advanced Research Projects Agency, RADC con­ tract F30602-85-C-0010. Computer facilities were enhanced through gifts from Xerox Corporation.

II. Mathematical Idealization of Abduction

Definitions

In order to motivate the following definitions, we will ex­ amine briefly the domain of the current implementation of RED, the domain of blood bank antibody analysis. The pri­ mary data consists of results of several lab tests on blood samples. The blood bank technologist knows how antibod­ ie3 can account for various reactions. The lab tests have the property that if antibody A accounts for some reaction r, and antibody B accounts for reaction q, then the presence of both antibodies A and B accounts for both reactions r and q. This property of a domain will be referred to as independence of hypotheses.

More formally, we define a domain for hypothesis as­ sembly as a the triple (H, !vi, e), where H is a finite set of hypothe3e!, !vi is a finite set of manije!tation!, and e is a map from subsets of H to subsets of M. e(S) is in­ terpreted as the ezplanatory power of a set of hypotheses, and is the set of manifestations for which those hypothe­ ses can account. An assembly problem is specified by a subset Mo ~ M. Mo is interpreted as the set of observed manifestations 1 · In these terms, we have

The Ind~pendence Auumption:

If S and T are subsets of H, then

Although many domains satisfy the independence as­ sumption, we wish to strengthen our result by replacing the independence assumption with two assumptions, which when taken together are weaker than the independence as­ sumption.

1 In what follow~, we will use the notation e(S) where we should, strictly speaking, write e(S)n!vf0 , for the restriction of e(S) to the observed manifestations.

The Monotonicity Auumption:

If S and T are subsets of H,

Clearly any domain that satisfies the independence as­ sumption also satisfies the monotonicity assumption.

The Accountability A$$Umption

For a hypothesis h E H, it is possible to know what manifestations h can account for. Formally, the function a: H-+ M*

can be computed as easily as e (polynomial calls to e).

Notice that if the independence assumption holds, then a(h) = e(h), so the accountability assumption holds.

Central to the success of any hypothesis assembly al­ gorithm is the following assumption:

The Computability A$$Umption:

For any subsetS of H, e(S) can be computed.

Clearly the complexity of this computation is central to the complexity of the assembly task, since it is difficult to ask for a set of hypotheses that accounts for some set of manifestations if it is difficult to compute what is accounted for by a set of hypotheses. In cases in which independence holds, this computation can be done in linear time by sim­ ply having a table that tabulates e for each individual hy­ pothesis, so that e( S) can be computed by taking the union of e(s) for s E S . This has allowed the current RED mech­ anism, the set covering algorithm of Reggia (Reggia 1983), and Internist (Miller 1982) to safely ignore the complexity of the computation of e. In fact, the incremental nature of all these algorithms allows them to compute e(S) in con­ stant time, since the usual case is that some set T is to be extended with another hypothesis s, with e(T) already known, so that the computation of e(T U { s}) can be done by simply looking up e( { s} ). For the complexity analysis which follows, we will assume an oracle for the function e, that is, we make the calculations counting one step for each evaluation of e.

B. Description of the hypothesis assembly algorithm

We now describe the algorithm for abduction by hy­ pothesis assembly. The algorithm has four phases; screening, hypothesis collection, parsimony and critique.

The input to the algorithm is the set of observed man­ ifestations, Mo. The output is a set of hypotheses that constitute a 'best' explanation of the data.

The screening phase determines plausibilitie$ (i.e., prima facie likelihoods) for the veracity of the hypotheses. Hypotheses with very low plausibilities are ruled out for further consideration. In this discussion we wish to exam­ ine and analyze the assembly phases of the algorithm, so we will omit a description of the screening phase. When we discuss applications, we will see one way to accomplish screening.

The collection phase works in the following way:

Let (H, M, e) be a domain for hypothesis assembly; let Mo <;;; M be a problem in that domain.

M', H' and m are variables in the following algorithm.

Let M' = Mo be the observed manifestations (the manifes­ tations to be explained).

Let H' be the empty set (working set of hypotheses). Until M' is empty, do the following:

Let m be the most salient hypothesis in M'. Find the most plausible hypothesis h that offers to account form, i.e., mE a(h). Adjoin h to H'. Compute the reactions accounted for by H'.

Let M' be M' \ e(H'), i.e., M' is the set of mani­ festations yet to be explained.

The set H' is the assembled explanation of the observed manifestations.

The parsimony phase works in the following way:

For each hypothesis h in H' (the working hypothesis set), starting from the least plausible to the most plausible, do the following:

H' is now a parsimonious set of hypotheses, that is, it has no redundant parts. Note that this does not guarantee that H' is a complete explanation of least cardinality.

The critique phase determines whether a hypothesis is euential to the explanation, that is, there is no way to ac­ count for the observed data without using that hypothesis. This phase works as follows:

For each hypothesis h in H' do the following:

Set G := H'\{h}. Repeat the collection algorithm (above) using G as working hypothesis , with hy­ pothesis h marked as unusable.

If collection completes (that is, there is a compos­ ite hypothesis that does not use h which explains Mo), then his not essential.

If collection fails to complete, then hypothesis h is essential.

C. Complexity of the Assembly mechanism

We begin by analyzing the time complexity of the assembly phase.

The collection algorithm can be analyzed as follows:

Let h be the number of hypotheses that were not ruled out; let m be the number of manifestations observed.

For each manifestation, we select a hypothesis that of­ fers to explain that manifestation, and evaluate the result­ ing composite. There are m such manifestations, and selec­ tion of a hypothesis takes at most h calls to the oracle a (for a linear search). The computation of M'\e(H') can be done in 0( m log m) steps (sort both sets, and merge the results). Thus, the complexity of this step is O(m(h + mlogm)).

Each time a new hypothesis is added to the working composite hypothesis H', it is necessary to evaluate e(H'), so there are O(m) calls to the oracle e.

Next we analyze the parsimony algorithm:

At most h hypotheses are considered for redundancy, so there are O(h) calls to the oracle e. At each such step, we must compare the explained set of manifestations to the observed set, that can be done in time O(mlogm) (first sort both sets, then compare elementwise), so the entire complexity is O(hm log m) .

Notice that this algorithm does not guarantee that we have found a compound hypothesis of smallest size that accounts for the observed data. This problem, which is the task of the Reggia et. al. set covering program (Reg­ gia 1983), can be shown to be NP-complete ·(reduction to vertex cover). This algorithm simply guarantees that the parsimonious solution has no proper subset that is also a solution.

Now we analyze the critic for essential hypotheses:

The critic takes each of the hypotheses in the work­ ing hypothesis and marks it as unusable, then repeats the assembly algorithm. There are at most h hypotheses in the composite hypothesis, so this is at most h times the complexity of assembly, that is, 0( hm( h + m log m) ).

D. Correctness of the algorithm

That the collection mechanism produces a composite hypothesis that accounts for all of the observed findings (provided, of course, that such a collection exists) is obvi­ ous from the loop condition. It is also clear that the critique algorithm will find all indispensable hypotheses , and all hy­ potheses deemed to be essential are in fact indispensable. The parsimony algorithm needs some justification.

We say that a composite hypothesis is a par3imoniou3 explanation of some findings if no proper subset of it can account for those findings . The parsimony mechanism en­ sures that there is no single hypothesis that can be excluded from the composite without losing the capability of explain­ ing some finding. It is possible to construct a domain in which a composite hypothesis has a proper subset that can account for all findings (that is, the composite hypothesis is not parsimonious), yet no single hypothesis is by itself.re­ dundant (that is, there is no hypothesis such that it alone can be removed without losing explanatory power) . If the monotonicity assumption is true, this can not happen.

Suppose that S is a non-parsimonious composite hy­ pothesis. Then for some subset R of S,

Now, for any r E R, we have

So by monotonicity, we have

i.e.,

So for all r E R, r is itself redundant, that is, the RED mechanism will find a redundant hypothesis in S. Hence we conclude that if S is not parsimonious, then RED will eliminate some hypothesis from it. .

III. Adapting the formal model to real-world abduction

A. The Abductive Answer

An abductive problem solver applied to actual problems tries to produce a best explanation for the observed data. Unfortunately, there is no hard and fast rule for demon­ strating that a particular explanation is best . Human prob­ lem solvers argue about whether one explanation is better than another. Hence the best we can do to argue that the answer given by this algorithm is best is to list the features which recommend it.

The answer given by this approach is guaranteed to cover all the data. Every observation will be explained.

The answer will be parsimonious in the sense that it will have no superfluous parts. It is not necessarily the smallest answer, i.e., the answer with the least parts.

The answer will be plausible, since more plausible hy­ potheses are preferred over less plausible ones. The algorithm prefers a large number of plausible hypotheses over a smaller number of less plausible ones. The algorithm will identify essential hypotheses, so when part of the answer is provably correct, the algorithm determines this.

Again, we cannot prove that such an answer is a 'best' explanation in any given situation, these are just the points by which one could argue for this answer. In the long run, the best answer is the one that is in fact the true situation. So now let us examine an application of this method to an actual domain.

B. A Real-:World application - Red blood antibody identification

1. Description of the domain

One of the jobs done by a blood-bank technologist is to identify antibodies in a patient's serum to antigens that might appear on red blood cells. This is typically done by combining samples of patient serum with red blood cells that contain certain antigens. Some of these combinations will show reactions, others will not. The presence of certain antibodies in the patient serum will account for certain re­ actions. The reactions are additive in the sense that if the presence of one antibody explains one reaction, and pres­ ence of another antibody explains another, then the pres­ ence of both antibodies explains both reactions. If both antibodies can account for a weak result in some reaction, then the presence of both can account for a strong result in that reaction. Also, some pairs of antibodies ca~not oc­ cur together. The task of the pathologist is to decide what antibodies are present, given a certain reaction pattern.

2. Satisfaction of Assumptions

We now examine how well this task meets the assump­ tions of the formal model presented in the first part of this paper.

Computability of e- The pattern of antigens appearing on the test cells is available in table form. This informa­ tion determines which antibo.dies account for any of the reactions. More detailed knowledge of the chemistry of the reactions allows us to build a table to tell the strengths of the reactions.

Independence - The additive nature of the reactions means that for separate reactions, the independence as­ sumption is met. Since the model does not allow for parts of manifestations to be explained, we cannot really say that the additivity of reaction strengths is included in the inde­ pendence assumption.

Monotonicity- If we view a weak result for some reac­ tion as a separate result from a strong result for the same reaction, then we can say that the phenomenon of additive reaction strengths satisfies the monotonicity assumption. That is, each antibody alone explains the manifestation of 'weak reaction'. Together, they can explain either a 'weak reaction', or a 'strong reaction'.

Accountability - Since the domain nearly satisfies the independence assumption, it is not surprising that we can calculate a nearly as easily as we can in the independent sit­ ·uation. That is, if an antibody can account for any strength result for some reaction, then it can potentially contribute to an explanation of any other strength result for that re­ action.

Incompatibility of Hypothe$e$ - Implicit in the formal model is the assumption that any collection of hypotheses is possible. This domain has a restriction that invalidates this assumption. It can be shown that hypothesis collection in general under such a constraint is an NP-complete prob­ lem (see appendix). There are two reasons why this is nof a problem in this domain. One is that the collection problem is not exponential in the number of hypotheses, or even the number of hypotheses left after screening, but in the num­ ber of incompatible pairs remaining after screening. This tends to be quite a small number. Also, since the screen­ ing rates hypotheses by plausibility, the algorithm is likely to stumble upon the correct answer early in the collection process.

3. Implementation

The algorithm for this domain is presently imple­ mented as follows:

Screening- this phase is done by a hierarchical classifi­ cation system similar to the MDX system (Chandra 1983).

Collection - this phase is done as in the text, with the exception that when a hypothesis is to be entered that is incompatible with some hypothesis already in the collec­ tion, the conflict is resolved by throwing out the hypothesis which is already in the set. A check is made for loops each time a hypothesis conflict arises. This is, in the worst case, a most plausible-first, brute force search. The computa­ tions of e and a are done from a table of singleton values; since the independence assumption holds (almost), we can compute the value of e of a set from the value of e at each element.

Parsimony and Critique - These phases are <.ione as described in the text.

The collection and parsimony phases are repeated, us­ ing the essential hypotheses as a starting point.

This algorithm matches the one in the text, except for the problem of incompatible hypotheses. So, with that ex­ ception (that was discussed above), the time complexity of the RED algorithm is polynomial in the number of anti­ bodies and reactions.

4. Availability of Knowledge

We have seen that in the blood typing domain that the assumptions required by this model are easily satisfied. We now examine these assumptions to estimate how likely it is that they will extend to yet other domains.

Without the computability of e, it would be impossi­ ble to evaluate whether an answer constituted a complete explanation, much less to construct such an answer. Many existing abduction systems (e.g. Set-covering model (Reg­ gia 1983) and Internist (Miller 1982)) depend strongly upon this assumption.

The independence assumption makes computations easy, since we only need to know values of e for singleton sets. Di~gnostic domains are likely to satisfy this assump­ tion, since devices are often decomposable into indepen­ dent parts, and hypotheses about these parts are often independent. The set covering model (Reggia 1983) relies strongly on this assumption. Internist (Miller 1982) re­ lies on this, but it would only take a simple change to In­ ternist to cope with more unruly domains, provided that they satisfy the monotonicity and accountability assump­ tions.

The monotonicity assumption is weaker than the in­ dependence assumption, hence is more likely to hold. It allows for some interaction of hypotheses, so long as no manifestations are canceled.

The accountability assumption is also weaker than in­ dependence, so is more likely to hold. This simply requires that we know to what manifestations a hypothesis can con­ tribute.

In a more unruly domain, in which the monotonicity assumption fails to hold, that is, when several hypotheses together fail to account for data that some of them do sep­ arately (e.g., due to subtractive interactions between the hypotheses), all of these assembly techniques will have dif­ ficulty. It can be shown that certain types of subtractive in­ teraction problems are NP-complete. In such cases, it may be fruitful to find different knowledge so that the problem is no longer one of assembly. One approach along this line is ABEL, a system described in (PATIL, 1982), which at­ tempts to make this problem tractable by making use of elaborate causal structures.

Conclusion

An important characteristic of problems that are dealt with in Artificial Intelligence is that domain knowledge is necessary to make the computations feasible. If an ap­ proach is to be widely applicable, it is necessary to know what knowledge is necessary to ensure that the approach will yield correct answers in a reasonable time.

In this paper, we have constructed a formal model of the approach to abductive reasoning illustrated by the RED system. From this model, we have identified when the available knowledge will allow application of this ap­ proach. Under the assumption that the knowledge is of this form (that is, it satisfies the assumptions of monotonicity, accountability and computability), we have demonstrated the tractability and correctness of the computation.

H := V

M:=E

Mo := E

C := { (v, e) I v is an endpoint of edge e}

Clearly an explanation of this diagnostic problem is also a cover of the graph G, of minimum cardinality. Also clearly this transformation is polynomial in the size of G.

NP-completeness of hypothesis assembly with Incompatible Hypotheses

An hypothesis assembly problem under constraints of incompatible hypotheses can be specified as a 5-tuple (H, M, C, I , M0 ), where

H and !vi are finite sets of hypotheses and manifestations respectively,

C is a relation, C ~ H x M, a table for computing e, I is a set of unordered pairs of elements of H, and Mo ~ M.

For a subsetS~ H, we write e(S) for the set {m E M I 3g E S s.t. (h, m) E C}

The interpretation of these sets is that H is a set of hy­ potheses that can account for certain manifestations in M, (h, m) E C (i.e., mE e(h)) means that h can account form. { ht, h2} E I means than hypotheses h1 and h2 are incom­ patible. Mo is the set of observed manifestations. A com­ plete explanation is a set S, S ~ H such that Mo ~ e(S), and such that there is no pair ht, h2 E S with { ht, h2} E I .

Appendix I

Proofs of theorems

NP-Completeness of the Reggia algorithm

After Reggia (1983) (using the notational conventions of this paper), we have the following definitions:

a diagno3tic problem is a 4-tuple (H,M,C,M0 ).

H, M are finite sets of hypotheses and manifestations respectively,

Cis a relation, C ~ H x M,

IV/0 ~ !vi, the 'observed manifestations'.

For a subset S ~ H, we write e(S) for the set {mE M I 3h E S s.t. (h,m ) E C}

An Ezplanation for a diagnostic problem is a set S ~ H such that Mo ~ e(S), lSI ~ ITI, for any T ~ H s.t. M0 ~ e(T).

We wish to show that given a diagnostic problem, find­ ing an explanation is NP-complete. We give a reduction . from minimal node cover.

Minimum node cover: Given a graph G = (V, E), find a set V' ~ V of smallest cardinality s.t . Ve E E, E has an endpoint in V'.

We form a diagnostic problem from the graph G as follows:

Set We prove NP-completeness of this problem by reduc­ tion from 3SAT (Garey 1979).

3SAT: Given a statement in propositional calculus in disjunctive normal form, in which each term has at most three factors, find an assignment of the variables that makes the statement have value 'True'.

We form an hypothesis assembly problem from a 3SAT problem by mapping factors in a 3SAT problem to hypothe­ ses and mapping terms to manifestations as follows:

Let P be a statement in propositional calculus in dis­ junctive normal form· where each term has at most three factors. Let { u1, u2, ... Un} be the variables used in P, let t be the number of terms in P.

We now construct an instance of the hypothesis as­ sembly problem under incompatibility constraints with 2n hypotheses and t manifestations.

If we find a complete explanation S for this problem, then we claim that the assignment

will be a solution to P.

For any j, 1 ::; j ::; t, ~i E A/0 , so there is some hE S with ~i E e(h) .

Case I. If h = h;, then h; E S, so u; is True, and since ~i E e( h;), we have, from the construction of C (and hence, e), that u; is a factor in the j 1 " term of P, hence the j 1 " term of P has value True.

Case II. If h = h;, then hi E S. {h;,hi} E I, soh; rf_ S, and hence u; is False, and sinc.e ~i E e( hi), we have that · u; is a factor in the j th term of P, hence again the j th term of P has value True.

Since every term of P has value True, so does P.

A similar argument shows that there exists a valid as­ sembly corresponding to each satisfying assignment.

Clearly the construction of this problem from P is a deterministic polynomial process. Also it is clear that com­ plete explanation construction under incompatibility con­ straints is NP, so hypothesis assembly with incompatible hypotheses is NP-complete.