Introduction
Model-based diagnosis (MBD) is a robust framework for identifying faults in complex systems. However, its practical application is often hindered by the "cold start" problem: the requirement for a precise, manually crafted model of the system's nominal behavior. In many real-world scenarios, developing such models is either prohibitively expensive or technically unfeasible.
This paper proposes a novel approach to bridge this gap by learning "safe" partial models directly from normal observations—data collected during the system's healthy operation. By leveraging the abundance of normal data, the proposed method can identify components that are guaranteed to be faulty when the system eventually deviates from its learned healthy state.
Methodology
Partial Model Learning and Safety
The core idea is to learn a set of local rules for each component or subsystem. For a component $C$, the learner observes pairs of inputs $I$ and outputs $O$. If the system is deterministic, any future observation where $C$ receives $I$ but produces an output $O' \neq O$ constitutes absolute proof that $C$ is faulty. This provides a "safe" diagnostic guarantee: any component flagged as "surely faulty" is mathematically certain to be so, assuming the initial observations were indeed from a healthy state.
Topological Subsystems
In many practical systems, internal variables are not fully observable (lack of "full probing"). To address this, the authors utilize the system's topology—the connection map between components—to define "observable subsystems."
As shown in Figure 1, components are grouped into subsystems where the inputs and outputs are measurable. If a subsystem's inputs match a previously seen healthy pattern but its output differs, the algorithm concludes that at least one component within that specific subsystem must be faulty.
PAC Learning Framework
To provide theoretical grounding, the authors apply the Probably Approximately Correct (PAC) learning framework. They demonstrate that the number of normal observations required to achieve a high diagnostic confidence scales efficiently—specifically, logarithmically—with the number of system components.
Experimental Evaluation
The approach was evaluated using the ISCAS '85 benchmark circuits, standard models for hardware logic diagnosis. These include the 74181 (a 4-bit ALU with 65 components) and the c3540 (a larger circuit with over 1,500 components). Faults were injected into these models to test the algorithm's ability to detect them after learning from varying amounts of normal data.
Key Results
Scaling and Multi-Fault Performance
The experiments confirmed that diagnostic accuracy improves significantly as the number of normal observations increases. Furthermore, the method is not limited to single-fault scenarios.
As illustrated in Figure 6, the fault detection rate increases steadily with the number of observations across different fault multiplicities. Even in complex triple-fault scenarios, the algorithm maintains a high detection rate given sufficient training data. On the large c3540 circuit, the algorithm identified surely faulty components in approximately 27% of cases using only 4,096 observations and minimal internal probing.
Discussion and Future Work
The proposed method offers a scalable, data-driven alternative to traditional MBD. Its primary strength lies in its "safety" and its ability to utilize the most common type of system data: normal operating logs.
However, several areas for future research remain:
- Deterministic Assumption: The current framework assumes deterministic behavior. Extending this to noisy or stochastic systems is a key next step.
- Continuous Domains: Adapting the logic from discrete bits to continuous variables (e.g., sensor readings) will require integrating function-learning techniques.
- Cyclic Topologies: The current subsystem logic is optimized for directed acyclic graphs; handling feedback loops presents additional temporal challenges.
By focusing on what is "surely faulty" rather than attempting a complete but potentially erroneous diagnosis, this approach provides a reliable tool for human operators managing complex, evolving systems.
Summary updated