Abductive Model-Based Diagnosis (MBD) provides an intuitive approach to fault identification by reasoning on a description of the system to be diagnosed. Nevertheless, its computational complexity hinders a vast adoption and thus motivates further evaluation of efficient methods. In this paper, we investigate the structural metrics inherent to models and diagnosis problems generated on the basis of Failure Mode Effect Analysis (FMEA). Proceeding on the metrics developed, we investigate their potential as classification features to identify the most suitable diagnosis algorithm for a particular diagnosis problem. Evaluated on artificial and practical samples, our approach shows that the classifier trained on the described metrics is able to indicate the most efficient method in case of a specific diagnosis scenario.
Growing complexity of technical systems complicates an effective as well as efficient fault identification, causing automated diagnosis to be of increasing interest from a theoretical as well as applied point of view. An extensive body of research has concerned itself with model-based diagnosis (MBD) [Reiter, 1987] which reasons on causes for observed anomalies using a description of the system. The abductive approach within this framework exploits a model of how failures manifest themselves within the system [Console et al., 1991]. By relying on the concept of entailment, abductive reasoning provides consistent root causes for failure indicators in an intuitive way.
Abduction is not merely relevant in the field of diagnostics, but has been applied to diverse fields such as planning [Poole and Kanazawa, 1994] or ontology debugging [Lambrix et al., 2013]. Various approaches to compute abductive explanations have been developed over the last decades, such as set covering [Patil et al., 1982; Guan and Jiang, 2013], abductive logic programming [Kakas et al., 1992; Denecker and De Schreye, 1998], proof-tree completion [McIlraith, 1998], or consequence finding [Marquis, 2000].
Authors are listed in alphabetical order.
Within this paper we address two methods: abductive MBD and the parsimonious set covering theory. In the latter a simple diagnosis problem comprises a set of causes, manifestations, and a causal associative network connecting these disjoint sets. A diagnosis is defined as the disorders which cover, i.e. explain, a given set of symptoms. The parsimonious set covering approach has been formalized and later extended to include Bayesian probabilities [Peng and Reggia, 1990]. Several refinements to the basic theory have been proposed such as the improvement of models with additional knowledge or the inclusion of more complex covering relations [Baumeister and Seipel, 2002].
Abduction is a hard problem with an exponential number of solutions in the worst case. Even though certain model representations are tractable [Nordh and Zanuttini, 2008], computing solutions for instances of reasonable size and complexity remains a challenge. Therefore, in this paper we investigate the algorithm selection problem [Rice, 1975] for abductive diagnosis. Algorithm selection addresses the issue of choosing the best performing method for a particular problem instance and advocates for the importance of structural properties of the problem space to determine the preferred approach [Smith-Miles, 2009]. It has been applied for example in SAT solving [Xu et al., 2008], graph coloring problems [Musliu and Schwengerer, 2013], or treedecomposition [Morak et al., 2012]. Our problem space is restricted to propositional Horn clause models generated from Failure Mode Effect Analysis (FMEA), which is a failure assessment available in practice. The formal descriptions of these models present certain structural traits, which are used as features in the algorithm selection process. Based on these model attributes and a set of experiments, a machine learning classifier was trained to decide on the most run time efficient abductive reasoning algorithm for a distinct diagnosis problem. We embedded the selection process within a metaalgorithm, which generates the structural metrics for a given diagnosis scenario, categorizes it on the previously trained classifier and computes the diagnoses using the “best” algorithm according to the prediction. 2
Within this section we present two abductive diagnosis methods, namely abductive MBD building on propositional Horn clauses and the simple set covering approach. We show that these two formalizations in their restricted form can be interchanged. In abductive MBD a system description holds information on how failures affect system variables. On basis of the knowledge and given an observable anomaly, the task is to search for a set of causes, which together with the model logically entail the observation. Furthermore, the explanations have to be consistent with the underlying theory. Since abductive inference is an intractable problem, research has focused on logical subsets which allow to compute explanations in polynomial time [Eiter and Gottlob, 1995]. Based on these findings we focus on a propositional Horn clause formalization [Friedrich et al., 1990].
(KB) is a tuple (A,Hyp,Th) where A denotes the set of propositional variables, Hyp A the set of hypotheses, and Th the set of Horn clause sentences over A.
A knowledge base provides the underlying model for our reasoning, where the set of hypotheses comprises the propositional variables constituting a cause or explanation. The remaining propositional variables. i.e. fA n Hypg, are effects or symptoms and the theory determines the relations between hypotheses and effects.
Example 1: Hyp = fh1; h2; h3g, A = fh1; h2; h3; o1; o2; o3g, T h = h1 ! o1; h2 ! o1; h2 ! o2; h3 ! o2; h3 ! o3
An abduction problem considers a knowledge base KB and a set of observations, i.e. current symptoms, for which explanations should be computed.
Definition 2 (Propositional Horn Clause Abduction Problem (PHCAP)) Given a knowledge base (A,Hyp,Th) and a set of observations Obs A then the tuple (A,Hyp,Th,Obs) forms a Propositional Horn Clause Abduction Problem (PHCAP).
PHCAP (A,Hyp,Th,Obs). A set Hyp is a solution if and only if [ Th j= Obs and [ Th 6j= ?. A solution is parsimonious or minimal if and only if no set 0 is a solution.
A solution to the PHCAP is an abductive diagnosis, as it provides hypotheses consistently explaining the occurrence of an observation.
Example 1 (cont): Let us assume we can observe o1 and o3, i.e. Obs = fo1; o3g. The solution to the PHCAP, i.e. the abductive diagnoses, are 1 = fh1; h3g and 2 = fh2; h3g.
An Assumption-Based Truth Maintenance Systems (ATMS) [de Kleer, 1986] is able to compute abductive explanations. Based on a directed graph, where propositional variables are nodes and the edges are determined by the theory, each node owns a label which stores the hypotheses implying said node. Whenever a new clause is added to the theory, the ATMS updates its nodes’ labels and further maintains a consistent state. By adding a rule of the type o1 ^ : : : ^ on ! explain containing all elements of Obs on the left hand side and a new variable on the right hand side, the ATMS computes the abductive solution as the label of explain. 2.2 Peng and Reggia [1990] developed the parsimonious set covering theory as a formal approach to abductive diagnosis relying on an associative network of causal connections between disorders and manifestations. A simple diagnosis problem is defined as a 4-tuple P =< D; M; C; M + >, where D is the set of disorders, M denotes the set of manifestations, C describes the relations in the causation network and M + comprises the current set of observations. Considering the definitions of the previous subsection D refers to Hyp. Further, the manifestations M , describe the remaining propositions not included within the hypotheses which are in fact the effects. The causal relations C are given by the theory, i.e. there exists a relation between a disorder di and a manifestation mj whenever there is a clause di ! mj contained within the theory. Since M + provides the distinguished subset of symptoms observed it corresponds to Obs. As the mapping between a PHCAP and a set covering problem is straightforward, we will use the wording as defined in the previous subsection, e.g. Hyp refers to the set of hypotheses, causes, disorders, etc. For clarity we add one additional set missing from the logic-based framework, i.e. M , which we define as fA n Hypg. The simple set covering model is equivalent to logic-based abduction with a theory restricted to definite Horn clauses [McIlraith, 1998].
Example 1: (cont) Considering our example from before, the diagnosis problem can be reduced to set covering: Hyp = fh1; h2; h3g, M = fo1; o2; o3g, Obs = fo1; o3g and T h = f< h1; o1 >; < h2; o1 >; < h2; o2 >; < h3; o2 >; < h3; o3 >g.
In order to define a solution to a diagnosis problem within this framework, we define for every hypothesis the set effects(hi) = fmj j < hi; mj >2 T hg, i.e. the set of objects directly caused by hi, and respectively for each effect, i.e. mj , the set causes(mj ) = fhij < hi; mj >2 T hg, i.e. the set of objects which can directly cause mj [Peng and Reggia, 1990]. Thus, for any subset of disorders HypI , we can determine the objects directly caused by it as effects(HypI ) = effects(hi) Along similar lines, we can observe that [ hi2HypI [ mj2MJ causes(MJ ) = causes(mj) Example 1 (Cont): For example causes(o1) = fh1; h2g and effects(fh1; h2g) = fo1; o2g.
MJ M if MJ effects(HypI ) and there exists no Hyp0I HypI with MJ effects(Hyp0I ).
A cover relation exists between a disorder and a manifestation whenever the latter is causally inferred from the former and is subset minimal. While minimality is not a necessary condition for a cover in the original definition, we enforce this parsimonious criteria as we are only interested in minimal diagnoses [Peng and Reggia, 1990].
lem P . A set Hyp is said to be a diagnosis iff covers Obs.
Example 1 (Cont): In case we have the same observations as before, i.e. o1 and o3, we can obtain the set covering diagnoses by determining the disorder sets HypI where effects(HypI ) cover Obs, which are effects(fh1; h3g) = fo1; o2; o3g and effects(fh2; h3g) = fo1; o2; o3g. Hence, the diagnoses are 1 = fh1; h3g and 2 = fh2; h3g.
As it has been shown previously, set covering is equivalent to the hitting set (HS) problem [Karp, 1972]. Let S be a collection of sets, then a set h Ssi2S si is a hitting set for S such that 8si 2 S : h \ si 6= ; [Greiner et al., 1989]. Since a cover states that a certain disorder causally infers a manifestation, we can utilize the set causes(mj ) as previously defined as a similar cover indicator. For each manifestation the set causes(mj ) contains the information on all disorder causing mj . By computing the hitting set of causes(mj ) we derive a disjunction of all disorders included, i.e. each disorder constitutes a possible solution. In case we obtain a set of observable manifestations m1; : : : ; mn 2 Obs, the hitting sets of all causes(mj ) 2 Obs comprises the diagnoses. This is apparent, as to account for all current manifestations one disorder causing each manifestation has to be present within a single solution. Again we focus on parsimonious solutions, therefore we are solely interested in subset minimal hitting sets (MHS) [Peng and Reggia, 1990].
agnosis problem P . A set Hyp is said to be a minimal diagnosis iff is a MHS of S, where 8mj 2 Obs : causes(mj ) 2 S.
Example 1 (Cont): The causes sets for the current manifestations are causes(o1) = fh1; h2g and causes(o3) = fh3g, thus causes(o1) 2 S and causes(o3) 2 S. The MHS of S correspond to 1 and 2. 3
Since developing suitable system models for MBD is a tedious task, there are approaches taking advantage of knowledge available to automatically generate system descriptions [Sterling et al., 2014]. A recent technique utilizes the information captured within FMEAs as the basis of their abduction models [Wotawa, 2014]. FMEA is of increasing interest as a systematic assessment of reliability on a component level [Catelani et al., 2010]. It encapsulates possible faults as well as the way they reveal themselves in different system variables [Hawkins and Woollons, 1998]. Therefore, it provides information on causal relations between failures and their symptoms, which in turn can be used as a knowledge base in an abductive diagnosis context [Wotawa, 2014]. 3.1
On basis of the relation between causes and effects recorded in the FMEA, a mapping function creates a propositional KB as described in the previous section, comprising a set of variables, hypotheses, and a propositional Horn clause theory [Wotawa, 2014]. Example 2 shows an FMEA with three component-based faults and their effects. In the KB each component-fault mode pair is represented by a propositional variable mode(C; M ), where C is the component and M is
Fan Fan IGBT
Corrosion TMF HCF
P turbine T cabinet, P turbine
T cabinet, T nacelle the fault mode. These propositional variables form the set Hyp of the KB, while the set of variables A encompasses all of these hypotheses as well as propositional variables representing the recorded effects. In order to create a Horn theory T h, the mapping function generates for each row in the FMEA a set of clauses. Each clause is an implications from the hypothesis, i.e. the component-fault mode pair, to one single effect variable. Thus, for example, for the second row of Table 1 two clauses are generated. The theory then is the union over all developed Horn clauses.
Example 2: For the example given in Table 1 we derive the following set of hypotheses, variables and Horn clauses: Hyp =
mode(F an; Corrosion); mode(F an; T M F ); mode(IGBT; HCF ) A =
mode(F an; Corrosion); T cabinet; P turbine; : : : T h = 8 mode(F an; Corrosion) ! P turbine; 9 >>>< mmooddee((FFaann;; TTMMFF)) !! PT tcuarbibnineet;; >>>= >>>: mmooddee((IIGGBBTT;;HHCCFF)) !! TT cnaabcienlelte; >>>;
For a detailed discussion on how to obtain the KB from
FMEAs we refer to the paper by Wotawa [
In this section we present the structural metrics extracted
from the models and utilized as attributes in classification.
Analyzing the structure of the Horn theory, we can observe
that the models constructed on basis of FMEAs with the
mapping function presented by Wotawa [
Based on the theory, we can easily represent the model as a hypergraph H = (V; E), where V is the set of vertices and E denotes the set of hyperedges with 8e 2 E : e V . Concerning our models the node set comprises all propositional variables, while hyperedges are determined by the theory; for each clause there exists a hyperedge containing the propositional variables of the clause, i.e. 8a 2 A : a 2 V and 8c 2 T h : Sl2c jlj 2 E where jj is a function mapping literals to the underlying propositions ignoring negations, i.e., j:pj = p and jpj = p for all p 2 A. Furthermore, we can assign a label to each vertex within a hyperedge e, as follows:
fvg if v 2 Hyp label(v) = S label(x) otherwise
:x2E^x6=v Obviously, in case we examine the vertices representing manifestations, the labels correspond to the causes-sets, since both contain the hypotheses inducing the corresponding manifestation. Hence, we can utilize the label of the current observations in computing the abductive diagnoses by means of hitting sets. Note, that we choose this representation to be able to handle intermediate effects, i.e. manifestations leading to additional symptoms, which are not represented in the simple set covering theory. In this paper, however, we focus on the simple structure as inherent to models created from FMEAs.
Figure 1 shows the hypergraph built for Example 1. On top of the DAG and hypergraph representation of the models, we can extract certain metrics relating to the underlying structure. An intuitive measure is the number of causes in the model, since abductive reasoning is exponential in the size of Hyp. Furthermore, basic quantities include the number of effects and relations occurring in the model.
Outdegree and Indegree Considering the directed graph determined by the theory we can compute the outdegree of each hypothesis node, i.e. the number of effects caused by said node, as well as the indegree of each effect, i.e. the number of hypotheses implying said manifestation. Using the set covering formalization we can define outdegree(hi) = jeffects(hi)j and similarly indegree(mj ) = jcauses(mj )j. Collected over the entire model, these measures provide an intuitive metric of the basic magnitude of the theory and the connectedness of the graph.
Covering and Overlap We can easily determine a covering metric for any given pair of hypotheses by building the ratio between common manifestations and the total number of manifestations caused by the hypotheses: covering(hi; hj) = jeffects(hi) \ effects(hj)j
jeffects(hi) [ effects(hj)j In a similar manner, we define the overlap of two effects as their shared causes in relation to all their causes: overlap(oi; oj) = jcauses(oi) \ causes(oj)j jcauses(oi) [ causes(oj)j Reggia, 1990]. Whenever a pathognomonic symptom is involved, we cannot compute an overlap relation, as there cannot be any shared hypotheses.
Independent Diagnosis Subproblem Independent diagnosis subproblems occur whenever the directed graph or hypergraph are not connected, i.e. there exist subproblems within the model which have disjoint hypotheses and effect sets. Note that if all effects are pathognomonic, then each cause-effect relation represents its own diagnosis subproblem and thus the diagnosis model is orthogonal. Imagine the clause h2 ! o2 missing from the theory of Example 1. In this case we would have two independent diagnosis subproblems, namely one including h1; h2 and o1 and the other one is h3; o2 and o3.
Path Length Another measure of connectedness within the model is the path length on the hypergraph. In particular, we measure the length of paths between nodes representing hypotheses. Note, that for a model there are possibly several hypergraphs depending on the number of independent diagnosis subproblems, thus we disregard paths between nodes belonging to different diagnosis subproblems.
topology of the model is of interest, but also the structure of the current diagnosis problem, we measure the effect covering among the elements of Obs and determine the number of diagnosis subproblems involved, in case several exist. 4
Since abductive reasoning belongs to the NP-hard problems, a research area of interest is to discover efficient methods to compute explanations. Thus, we investigate the feasibility to utilize the metrics defined in the previous section to train a classifier able to select the most time efficient approach for a particular diagnosis scenario. The general idea of the metaalgorithm based on algorithm selection is straightforward; we train a classifier on a distinct training set and whenever the diagnosis process is triggered by a detected anomaly, we retrieve the trained classifier, collect the metrics of the particular PHCAP and create the attributes for classification based on the measures. By providing these features to the machine learning algorithm, we in turn retrieve a predicted best algorithm for this scenario. Subsequently, we can instantiate the diagnosis engine with the corresponding abduction method as well as diagnosis problem and compute the abductive explanations. Algorithm 1 describes our meta-approach.
procedure METAB (A; Hyp; T h; Obs) modelweka retrieveModel() f [] retrieveMetrics(A; Hyp; T h; Obs) algorithm classify(f; modelweka)
Set diagnose(algorithm; A; Hyp; T h; Obs) return Set end procedure In case there is a unique hypothesis explaining an observation, this is referred to as a pathognomonic effect [Peng and To evaluate the feasibility of the meta-technique we conducted experiments on two different data sets which we will
explain in detail in the upcoming subsection. For the machine learning part of our meta-algorithm we employed the Waikato Environment for Knowledge Analysis (WEKA) library [Hall et al., 2009], which provides a vast number of classification methods. The abductive reasoning algorithms forming our prediction categories are an ATMS as well as several HS algorithms, namely the Binary Hitting Set Tree (BHSTree) [Lin and Jiang, 2003], HSDAG [Reiter, 1987], HST [Wotawa, 2001] and the Boolean approach [Lin and Jiang, 2003]. To collect runtime data for the training and test set for classification, we exploited a Java implementation of an ATMS as well as a Java implementation1 of BHSTree and Python implementations [Quaritsch and Pill, 2014]2 of the remaining HS methods. 4.1
Our data for classification originate from two separate sources; on the one hand a small corpus of FMEAs and on the other hand generated artificial examples. The former comprises publicly available as well as internally used FMEAs recording fault knowledge from diverse domains. We automatically mapped these failure assessments to abductive knowledge bases, which we can use for logic-based as well as set covering abduction. All in all we conducted experiments on twelve FMEAs with various numbers of hypotheses (4 jHypj 32), effects (5 jM j 30) and clauses (12 jT hj 105). For each experiment we randomly chose the number of observations as well as the manifestations themselves from the effects available within the model. A total of 2120 experiments where conducted on the FMEA sample set.
In case of the artificial portion of our classification data, we produced examples with a varying number of hypotheses (10 jHypj 500), effects (4 jM j 13001) and clauses (100 jT hj 13500). Furthermore, we chose the effect overlap randomly as well as the out degree of the disorders. Due to the implementation of the artificial example generator, we do not observe several independent diagnosis subproblems within these models. We collected the data on 252 experiments with jObsj ranging from 1 to 25. Clearly, the majority of these models is larger in size than the FMEA examples and thus computationally more expensive.
With each experiment run we collected the following 27 metrics in accordance to the previous section: the number of hypotheses, number of effects, number of clauses, outde1http://www.ist.tugraz.at/modremas/index.html 2http://modiaforted.ist.tugraz.at/downloads/pymbd.zip Classification Method jTraining Setj
jTest Set j
Total Test Time Correctly Classified Instances Incorrectly Classified Instances
Mean absolute error
FMEA Multilayer Perceptron 1696 424 5ms 308 (72.64 %) 116 (27.36 %) 0.17
AI Multinomial Logistic
Regression 210 42 < 1 ms 30 ( 71.43 %) 12 ( 28.57 %) 0.17 gree of hypotheses (average, maximum, standard deviation), indegree of effects (average, maximum, standard deviation), hypothesis covering for each pair of hypotheses of the entire model (average, maximum, standard deviation), effect overlap for each pair of manifestations (average, maximum, standard deviation), path length between hypotheses on basis of the hypergraph (average, maximum, standard deviation), number of independent diagnosis subproblems and based on the current observations the size of Obs, the indegree of the current observation nodes (average, maximum, standard deviation), the effect overlap (average, maximum, standard deviation) and number of independent diagnosis problems. All these metrics build our feature vector for the classification. The variable to be predicted is the algorithm, i.e. ATMS, BHSTree, HSDAG, HST, or Boolean, which would be the most efficient on the current diagnosis problem.
Each experiment data series was split into a training set comprising 80% of the data and a test set of 20%. Dividing the data, we made sure to split it in such a way that the test set comprises models of various sizes. Before selecting the classification method, we performed cross validation on several classification algorithms available in WEKA on the training data. Based on the accuracy obtained we decided to use a multilayer perceptron as the classifier for the FMEA-based models and multinomial logistic regression for the artificial examples.
As can be seen in Table 3 the classification based on the metrics reaches a satisfactory success rate on the FMEA-based as well as artificial examples. The confusion matrix in Table 2 shows the number of correctly and wrongly classified instances. The rows represent the actual number of instances, i.e. the number of samples the corresponding algorithm was the most efficient, while the columns show the predicted outcome. For example, the cell in the first row in column three states “25=4”, meaning that for the FMEA-based samples 25 times the classifier predicted BHSTree to be the most effi100000 )s m 10000 i(n iem1000 t n uR 100 e v ta 10 i l u Cum 1 0.1 cient approach when in fact the Boolean algorithm was the fastest. For the artificial samples 4 examples where wrongly classified as BHSTree instead of the Boolean approach.
Note that for the FMEA samples HST and HSDAG were never predicted or actually measured to be the best performing algorithm, the same holds for the ATMS in the artificial examples. Further, we can see that the Boolean approach was the most efficient, followed by BHSTree on both test sets. The confusion matrix further shows that the neural network had difficulties in classifying instances where the ATMS succeeded, as it categorizes it in nearly 41% incorrectly and the same holds for the HSDAG in the artificial examples. Yet, whenever the classifier categorizes the problem incorrectly, the suggested algorithm is the second or third most efficient.
To discover whether our meta-approach provides an efficiency improvement, we compared computation time on both test sets for all methods, i.e. our meta-algorithm and each abductive reasoning technique. The runtime for the metaalgorithm is determined by first, the computation of the metrics, second the time it takes to create the feature vector, supply it to the classifier and predicting the best algorithm and third the diagnosis time of the suggested procedure. Figure 2 shows the cumulative runtime for the test data with the x-axis representing samples from the test set. As can be seen from the figure, our meta-algorithm is not able to outperform on average (2.22 ms) all direct diagnosis methods (Boolean approach 0.48 ms, BHSTree 1.36 ms, HSDAG 1.09 ms, ATMS 3.14 ms, HST 2643.17ms) for the FMEA-based examples. The reason being that the mean time to collect the metrics of the PHCAP requires 1.71 ms on the tested examples, which is close the actual diagnosis time of these problems. In case of the artificial examples our approach performs well, i.e. on average the meta-algorithm is the most efficient. Due to the size of these samples, the computation of the properties only demands a fraction of the actual diagnosis run time. On average our algorithm requires 72674.36 ms and is 99.9% faster than the ATMS and BHSTree, 71.53 % faster then HST, 56.58% faster than the HSDAG and 2.77% faster than the Boolean Computation time of abductive diagnosis depends primarily on the underlying model. Thus, we investigated algorithm selection, as a form to predict the best performing method based on the structural properties of problem instances. We explore metrics inherent to the structure of FMEA-based models, which form the feature vector for a classifier as part of a meta-approach. Evaluated on a test set, the metrics led to a satisfactory selection of the best algorithm for a particular diagnosis problem. In case of the FMEA-based samples our meta-algorithm was restrained by the time necessary to construct the feature vector and thus could not outperform all abduction methods. Our approach shows its value when operating on larger problem instances, where it performs well and in fact is the most efficient in comparison.
Despite the satisfactory classification results, there are certain metrics worth investigating such as treewidth based on the decomposition of the hypergraph as well as different attribute combinations to determine the metrics most suited. Regarding the restricted representation class, we plan on expanding our approach to more expressive models.
The work presented in this paper has been supported by the FFG project Applied Model Based Reasoning (AMOR) under grant 842407 and by the SFG project EXPERT. We would further like to express our gratitude to our industrial partner, Uptime Engineering GmbH.