Abstract
This paper introduces LAB (Learning for ABduction), a novel inductive learning system designed to acquire knowledge bases for multi-disorder diagnosis. Unlike traditional systems that learn deductive rules (symptoms $\rightarrow$ disorder), LAB learns abductive rules (disorder $\rightarrow$ symptoms), allowing it to outperform standard algorithms like ID3 and even human-expert systems in complex, multi-fault medical domains.
Introduction
Most symbolic machine learning assumes a deductive model: an example belongs to a category if it satisfies a specific logical pattern. In medical diagnosis, this translates to "if symptoms X and Y are present, then the patient has disease Z." However, this approach struggles with multiple-disorder diagnosis, where a patient might have several conditions simultaneously, and their symptoms are a combined "cover" of those conditions.
The authors argue that abduction—reasoning from effects (symptoms) back to causes (disorders)—is a more natural fit for these problems. The challenge is that building abductive knowledge bases manually is difficult and time-consuming. LAB addresses this gap by automatically inducing these causal rule bases from sets of training examples.
The LAB Algorithm
LAB operates within the framework of Parsimonious Covering, a model where a diagnosis is the smallest set of disorders that accounts for all observed symptoms. Key components include:
- Rule Representation: LAB learns rules in the form $disorder \rightarrow manifestation$. This mirrors clinical reasoning (e.g., "Strokes in the thalamus cause sensory loss").
- Hill-Climbing Search: The system uses a greedy hill-climbing approach to build the rule base. It starts with rules derived from single-disorder cases and iteratively adds rules from a pool of potential candidates that maximize "intersection accuracy."
- Intersection Accuracy: To evaluate progress, LAB uses a metric averaging precision and recall. This is more robust than standard accuracy in multi-label settings where "no disorder" is a common but uninformative correct prediction for many individual labels.
- BIPARTITE Integration: LAB uses the BIPARTITE algorithm as a "black box" to perform abductive inference, testing how well the current rule base explains the training data during learning.
Experimental Evaluation
The system was evaluated using a real-world medical dataset of Stroke Diagnosis Data, consisting of 50 patient cases involving brain damage. The domain includes 25 possible brain areas (disorders) and 37 symptom types (expanded to 155 attribute-value pairs). LAB was compared against ID3, PFOIL (a propositional version of FOIL), a standard backpropagation neural network, and a manually crafted expert knowledge base containing 648 rules.
Results and Discussion
LAB demonstrated significant advantages in the multi-disorder diagnostic task. By learning rules in the causal direction ($Cause \rightarrow Effect$), the system naturally handles cases where multiple causes overlap. Deductive systems ($Effect \rightarrow Cause$) often fail when symptoms from different disorders appear together.
As shown in the figures, LAB achieved significantly higher intersection accuracy than ID3, PFOIL, and Backprop when training sets were small (under 20–30 examples). Notably, LAB surpassed the performance of the expert-generated knowledge base after only 15 training examples.
While LAB's rule base was larger than PFOIL's, it was significantly simpler and more interpretable than the decision trees generated by ID3, as the rules directly represent causal relationships. LAB also tended toward high sensitivity, rarely missing a present disorder, which is often preferable in clinical settings.
Conclusion and Future Work
Despite its success, LAB has limitations. Its greedy hill-climbing search can get stuck in local optima, and it is computationally more expensive than deductive learners due to the repeated abductive inference steps. Future work will explore handling causal chaining, rules with multiple antecedents, and integrating probabilistic abduction to better rank multiple possible diagnoses.
Summary updated