Thomas D. Wu

AAAI Conference 1991 Conference Paper

Domain Structure and the Complexity of Diagnostic Problem Solving

• Thomas D. Wu

Thomas De Wu MIT Laboratory for Computer Science 545 Technology Square Cambridge, Massachusetts 02139 approach offers increased efficiency for the diagnosis of This paper provides a quantitative analysis of domain structure and its effects on the complexity of diagnostic problem solving. It introduces a hypothesis about the modular structure of domains and proposes a measured called explanatory power. The distribution of explana tory power reveals the inherent structure of domains. We conjecture that such structure might facilitate problem solving, even when the problem solver does not exploit it explicitly. To test this hypothesis, we create a domain without structure by randomizing the distribution of explanatory power. We use the structured and randomized knowledge bases to study the effect of domain structure on two diagnostic algorithms, candidate generation and symptom clustering. The results indicate that inherent domain structure, even when not encoded explicitly, can facilitate problem solving. Such facilitation occurs for both the candidate generation and symptom clustering algorithms. Moreover, domain structure appears to benefit symptom clustering more than candidate generation, suggesting that the efficiency of symptom clustering derives in part from exploiting domain structure.

AAAI Conference 1990 Conference Paper

Efficient Diagnosis of Multiple Disorders Based on a Symptom Clustering Approach

• Thomas D. Wu

Diagnosis of multiple disorders can be made efficient using a new representation and algorithm based on symptom clustering. The symptom clustering approach partitions symptoms into causal groups, in contrast to the existing candidate generation approach, which assembles disorders, or candidates. Symptom clustering achieves efficiency by generating aggregates of candidates rather than individual candidates and by representing them implicitly in a Cartesian product form. Search criteria of parsimony, subsumption, and spanning narrow the symptom clustering search space, and a problem-reduction search algorithm explores this space efficiently. Experimental results on a large knowledge base indicate that symptom clustering yields a near-exponential increase in performance compared to candidate generation.

UAI Conference 1990 Conference Paper

Probabilistic evaluation of candidate sets for multidisorder diagnosis

• Thomas D. Wu