Model-Based Diagnosis (MBD) approaches often yield a large number of diagnoses, severely limiting their practical utility. This paper presents a novel active testing approach based on MBD techniques, called FRACTAL (FRamework for ACtive Testing ALgorithms), which, given a system description, computes a sequence of control settings for reducing the number of diagnoses. The approach complements probing, sequential diagnosis, and ATPG, and applies to systems where additional tests are restricted to setting a subset of the existing system inputs while observing the existing outputs. This paper evaluates the optimality of FRACTAL, both theoretically and empirically. FRACTAL generates test vectors using a greedy, next-best strategy and a low-cost approximation of diagnostic information entropy. Further, the approximate sequence computed by FRACTAL's greedy approach is optimal over all poly-time approximation algorithms, a fact which we confirm empirically. Extensive experimentation with ISCAS85 combinational circuits shows that FRACTAL reduces the number of remaining diagnoses according to a steep geometric decay function, even when only a fraction of inputs are available for active testing.

Almost all approaches to model-based diagnosis presume that the system being diagnosed behaves non-intermittently and analyze behavior over a small number (often only one) of time instants.  In this paper we show how existing approaches to model-based diagnosis can be extended to diagnose intermittent failures as they manifest themselves over time. In addition, we show where to insert probe points to best distinguish among the intermittent faults those that best explain the symptoms and isolate the fault in minimum expected cost.

Logic reasoning approaches to fault diagnosis account for the fact that a component c j may fail intermittently by introducing a parameter g j that expresses the probability the component exhibits correct behavior. This component parameter g j , in conjunction with a priori fault probability, is usedin a Bayesian framework to compute the posterior fault candidate probabilities. Usually, information on g j is not known a priori. While proper estimation of g j can have a great impact on the diagnostic accuracy, at present, only approximations have been proposed. We present a novel framework, BARINEL, that computes exact estimations of g j as integral part of the posterior candidate probability computation. BARINEL’s diagnostic performance is evaluated for both synthetic and real software systems. Our results show that our approach is superior to approaches based on classical persistent fault models as well as previously proposed intermittent fault models.

We propose a new approach for Temporal Diagnosis Problems. This approach is an extension of  Bouzid and Ligeza's  method for temporal diagnosis problems. In this latter work, the authors define a Temporal Causal Graph (TCG) where time delays are expressed as temporal instants. We extend the TCG by including two quantitative relations in order to handle temporal intervals. We call ExTCG this new model. Solving a temporal diagnosis problem represented by the ExTCG consists of finding all possible explanations. It is performed using a backtrack search algorithm. In many diagnosis applications, the generation of all possible explanations is not necessary. For this reason, we augment the ExTCG in order to consider the degree of causality between symptoms. We call weighted ExTCG this extended model. Solving it consists of finding the explanation  having the highest probability to occur. Through a real world diagnosis application in medicine, we illustrate the weighted ExTCG and its corresponding solving algorithm.

We propose a new approach for Temporal Diagnosis Problems. This approach is an extension of  Bouzid and Ligeza's  method for temporal diagnosis problems. In this latter work, the authors define a Temporal Causal Graph (TCG) where time delays are expressed as temporal instants. We extend the TCG by including two quantitative relations in order to handle temporal intervals. We call ExTCG this new model. Solving a temporal diagnosis problem represented by the ExTCG consists of finding all possible explanations. It is performed using a backtrack search algorithm. In many diagnosis applications, the generation of all possible explanations is not necessary. For this reason, we augment the ExTCG in order to consider the degree of causality between symptoms. We call weighted ExTCG this extended model. Solving it consists of finding the explanation  having the highest probability to occur. Through a real world diagnosis application in medicine, we illustrate the weighted ExTCG and its corresponding solving algorithm.

Web servers on the Internet need to maintain high reliability, but the cause of intermittent failures of web transactions is non-obvious. We use Bayesian inference to diagnose problems with web services. This diagnosis problem is far larger than any previously attempted: it requires inference of 10^4 possible faults from 10^5 observations. Further, such inference must be performed in less than a second. Inference can be done at this speed by combining a variational approximation, a mean-field approximation, and the use of stochastic gradient descent to optimize a variational cost function. We use this fast inference to diagnose a time series of anomalous HTTP requests taken from a real web service. The inference is fast enough to analyze network logs with billions of entries in a matter of hours.

The eighteenth annual International Workshop on Principles of Diagnosis was held in Nashville, Tennessee, May 29–31, 2007. Papers presented at the workshop covered a variety of theories, principles, and computational techniques for diagnosis, monitoring, testing, reconfiguration, fault-adaptive control, and repair of complex systems. This year's workshop emphasized inter-actions and exchange of ideas and experiences between researchers and practitioners whose backgrounds included AI, control theory, systems engineering, software engineering, and related areas.

The eighteenth annual International Workshop on Principles of Diagnosis was held in Nashville, Tennessee, May 29–31, 2007. Papers presented at the workshop covered a variety of theories, principles, and computational techniques for diagnosis, monitoring, testing, reconfiguration, fault-adaptive control, and repair of complex systems. This year’s workshop emphasized inter-actions and exchange of ideas and experiences between researchers and practitioners whose backgrounds included AI, control theory, systems engineering, software engineering, and related areas.

Many computer aided diagnosis (CAD) problems can be best modelled as a multiple-instance learning (MIL) problem with unbalanced data: i.e., the training data typically consists of a few positive bags, and a very large number of negative instances. Existing MIL algorithms are much too computationally expensive for these datasets. We describe CH, a framework for learning a Convex Hull representation of multiple instances that is significantly faster than existing MIL algorithms. Our CH framework applies to any standard hyperplane-based learning algorithm, and for some algorithms, is guaranteed to find the global optimal solution. Experimental studies on two different CAD applications further demonstrate that the proposed algorithm significantly improves diagnostic accuracy when compared to both MIL and traditional classifiers. Although not designed for standard MIL problems (which have both positive and negative bags and relatively balanced datasets), comparisons against other MIL methods on benchmark problems also indicate that the proposed method is competitive with the state-of-the-art.

Many computer aided diagnosis (CAD) problems can be best modelled as a multiple-instance learning (MIL) problem with unbalanced data: i.e., the training data typically consists of a few positive bags, and a very large number of negative instances. Existing MIL algorithms are much too computationally expensive for these datasets. We describe CH, a framework for learning a Convex Hull representation of multiple instances that is significantly faster than existing MIL algorithms. Our CH framework applies to any standard hyperplane-based learning algorithm, and for some algorithms, is guaranteed to find the global optimal solution. Experimental studies on two different CAD applications further demonstrate that the proposed algorithm significantly improves diagnostic accuracy when compared to both MIL and traditional classifiers. Although not designed for standard MIL problems (which have both positive and negative bags and relatively balanced datasets), comparisons against other MIL methods on benchmark problems also indicate that the proposed method is competitive with the state-of-the-art.