Multiple Dimensions of Generalization In Model-Based Troubleshooting

Randall Davis, Paul ResnickAAAI 1993

Model-based diagnosis (MBD) is a robust technique for identifying faults in complex systems by comparing observed behavior against first-principles models. However, its computational intensity often limits its real-time applicability. This paper, originally published in 1993 by Davis and Resnick at the MIT AI Lab, proposes a method to significantly enhance MBD efficiency by learning multiple, diverse generalizations from single diagnostic successes.

Problem Statement: The Efficiency Gap in MBD

MBD systems typically re-derive reasoning patterns for every new problem, even if it is fundamentally similar to a previous one. While standard machine learning requires large datasets, Explanation-Based Learning (EBL) can learn from single examples. However, EBL usually produces only one specific type of generalization. The authors address this "multiple explanation opportunity," exploring how a rich domain model can be used to derive various useful rules from a single failure instance.

Methodology: Multi-Dimensional Generalization

The approach combines EBL with symbolic fault envisionment. EBL generalizes "conflict sets"—groups of components whose internal logic is inconsistent with observed outputs—by replacing concrete values with variables. This allows the system to identify similar conflicts in the future without re-propagating values.

Symbolic fault envisionment simulates specific fault models (e.g., a "stuck-at-1" error) using variables to predict symptoms across a wide range of inputs. The novelty lies in generalizing across four distinct dimensions:

  1. Reasoning Patterns: Generalizing the logic that led to a conflict set.
  2. Specific Fault/Component Pairs: Learning the symptoms of a specific component failing in a specific way.
  3. Role Equivalence: Recognizing that identical components (like bit-slices in an adder) will exhibit similar fault behaviors.
  4. Fault Families: Proactively deriving rules for related faults (e.g., "stuck-at-0") after observing one member of the family ("stuck-at-1").

Experimental Setup

The researchers evaluated their approach using simulated digital circuits of varying complexity.

Figure 1: A simple multiplier-adder circuit used as Example 1 in the study.
  • Example 1: A small circuit consisting of multipliers and adders (tested with 100 cases).
  • Example 3: A complex carry-lookahead adder (tested with 150 cases).

Key Insights: Defining Similarity

Generalization is essentially a commitment to a definition of similarity. By providing the system with multiple "domain theories" (structural, functional, and fault-based), the authors allow it to see one example as "the same" as many different future problems. To avoid the "utility problem"—where too many rules slow down the system—learned rules must be recurrent (happen often), manifest (cheap to recognize), and exploitable (provide diagnostic power).

Results and Performance Gains

The system achieved significant performance improvements across both test cases. In the complex carry-lookahead adder experiment, the system generated 221 different rules. While only an average of 3.15 rules were applicable to any given problem, they provided enough focus to bypass expensive internal computations.

Table 1: Performance comparison between non-learning and learning diagnostic modes across two circuit examples.

As shown in the results table, the learning system achieved a 28% speedup on the simple circuit and a 20% speedup on the complex adder. The authors calculated that for the complex adder, a generalized rule only needs to be applicable in 1 out of 211 cases to result in a net performance gain.

Conclusion and Future Work

This research demonstrates that model-based systems can learn aggressively from single examples by exploiting structural and functional symmetries. Future work includes automating the discovery of component roles and moving toward higher-level diagnostic languages (e.g., "off-by-one" errors) to make rules more intuitive and powerful.

Summary updated

BibTeX
@inproceedings{davis1993multiple,
  author = {Randall Davis and Paul Resnick},
  title = {{Multiple Dimensions of Generalization In Model-Based Troubleshooting}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure