An evolutionary algorithm for abductive reasoning

Abductive reasoning (or abduction) is the process of inferring hypotheses from observed data using a certain ‘knowledge’ encoded in the form of inference rules (or causal relations). Many important kinds of intellectual tasks, including medical diagnosis, fault diagnosis, scientific discovery, legal reasoning, and natural language understanding have been characterised as abduction. Unfortunately, abduction is 𝒩𝒫-hard. Genetic algorithms and biologically motivated computational paradigms inspired by the natural evolution turned out to be efficient in solving many hard problems while other existing approaches failed to solve in general. In this article, we present a genetic algorithm called HAKIM, for solving abduction problems. We encode an explanation in a chromosome-like structure, where every gene models a possible single hypothesis. Thereafter, we develop a fitness function that characterises the overall ‘quality’ of a chromosome representing an explanation; and then use standard genetic operators to compute a set of hypotheses that best explains the observed data. Simulation results on large-scale medical problems reveal the good performance of our model HAKIM.     

Combining Case-Based and Model-Based Reasoning for the Diagnosis of Complex Devices

A novel approach to integrating case-based reasoning with model-based diagnosis is presented. This approach, called Experience Aided Diagnosis (EAD), uses the model of the device and the results of diagnostic tests to index and match cases representing past diagnostic situations. Retrieved cases are then used to overcome errors created by the application of incorrect device models. The diagnostic methodology is described and applied to two real-world devices. Experimental results demonstrate the effectiveness of both the indexing schema and the matching algorithm. The paper discusses how these results can be generalized to multiple fault situations, to other types of device models, and to other applications in the field of an artificial intelligence.     

Practical abduction: characterization,decomposition and concurrency

Abstract

Abductive inferences seem to be ubiquitous in cognition, and cognitive agents often solve complex abduction tasks very rapidly. However, abduction characterized as ‘inference to the best explanation’ is in general computationally intractable. This paper describes three related ideas for understanding how intelligent agents might efficiently perform abduction tasks. First, we recharacterize the abduction task as inference to a confident explanation, where a confident explanation is internally consistent, parsimonious, distinctly more plausible than alternative explanations, and explains as much of the data as possible with high confidence. Second, we describe a decomposition of the task of synthesizing a confident explanation into several subtasks so that the synthesis starts from islands of relative certainty and then grows opportunistically. This decomposition helps in controlling the computational cost of accommodating interactions among explanatory hypotheses, especially incompatibility interactions. Third, we present a concurrent mechanism for synthesizing confident explanations. The mechanism exploits data and processing dependencies afforded by the decomposition of the synthesis task. The emphasis of this approach to abduction is on characterizing the constraints of the abduction task and exploiting these constraints for making abductive inferences. In describing this approach, we also clarify the precise class of abduction problems addressed by the RED-2 system, and report on some new experiments. The main result is a computational model that not only enables efficient abductive inferences but also accommodates explanatory interactions, uncertainty, and data collection.     

Human-like fault diagnosis using a neural network implementation of plausibility and relevance

In real systems, fault diagnosis is performed by a human diagnostician, and it encounters complex knowledge associations, both for normal and faulty behaviour of the target system. The human diagnostician relies on deep knowledge about the structure and the behaviour of the system, along with shallow knowledge on fault-to-manifestation patterns acquired from practice. This paper proposes a general approach to embed deep and shallow knowledge in neural network models for fault diagnosis by abduction, using neural sites for logical aggregation of manifestations and faults. All types of abduction problems were considered. The abduction proceeds by plausibility and relevance criteria multiply applied. The neural network implements plausibility by feed-forward links between manifestations and faults, and relevance by competition links between faults. Abduction by plausibility and relevance is also used for decision on the next best test along the diagnostic refinement. A case study on an installation in a rolling mill plant is presented.     

Multiagent simulation subsystem of diagnostic complexes based on device models

Application of the multiagent approach in diagnostic systems based on device behavior models is considered. The architecture of a multiagent diagnostic system, as well as the semantic and spatial methods of the distribution of a device model among the agents, is presented. Working algorithms for a simulation subsystem are given and the efficiency of the multi-agent approach in diagnostic systems based on device behavior models is estimated. The described approach is tested for the semantic distribution of a device model among the agents. Our results confirm the efficiency of applying the multi-agent approach in diagnostic systems based on device behavior models.     

HELIX: A helicopter diagnostic system based on qualitative physics

Future helicopter requirements, including expanded missions and single-pilot operation, will greatly increase the demands placed on the pilot. To meet these requirements without overwhelming the pilot, novel approaches to cockpit automation must be devloped. To assess the feasibility of applying Artificial Intelligence technology to helicopter cockpit automation, an expert system for status monitoring and diagnosis designated HELIX (HELicopter Integrated eXpert) has been developed.At the heart of the HELIX program is a Qualitative Reasoning System (QRS). The QRS is a general mechanism to support the creation of hierarchical device models and reasoning about device behaviour using Qualitative Physics. The HELIX qualitative model is represented as a set of constraints that define the normal behaviour of the engines, transmission, flight controls, and rotors of the helicopter. Aircraft health is assessed by determining whether observations (sensor readings and pilot control inputs) are consistent with the constraints of the model. If an inconsistency is detected, a process of systematic constraint suspension is used to test various failure hypotheses.Critical to the efficient operation of the HELIX program is the hierarchical model representation, which enables reasoning at various levels of abstraction. Using a top-down approach, the diagnostic process exploits the hierarchy by beginning fault isolation with the most reduced form of the model. To refine the diagnosis, a branch of the hierarchy may be expanded until a component-level diagnosis is made. The hierarchy also greatly reduces the complexity of multiple failure diagnosis. Rather than considering combinations of failures in all leaf components, the diagnosis can be restricted to combinations of branches in the hierarchy.HELIX has been successfully tested on a variety of simulated failures. By representing only the normal behaviour of the helicopter and testing hypotheses by constraint suspension, HELIX has been able to diagnose single or multiple failures without prior knowledge of failure modes. The approach represents a promising technique for automating the qualitative reasoning required to diagnose novel failures and may form the basis for extensive automation both in airborne and ground-based diagnostic systems.     

Modelling for an expert system and a parameter validation method

A model–based engineering diagnostic method is typically based on the evaluation of the residuals generated from a comparison of important variable values from a simulated system and the corresponding measured values from the system's performance. Consequently, a model should describe the dynamic behaviour of the system as accurately as possible using suitably selected parameter values. This implies the need for validation of the performance of the model by comparison with the measurements of the actual system. This process is especially important when the detection of faults is performed in real–time conditions. In this paper, the modelling process for hydraulic systems as well as a new parameter validation method that has been developed using the DASYLab data acquisition and control software for the estimation of the uncertain parameter values of the model is presented. This model validation process led to the establishment of a model–based expert system that is able to diagnose real–time faults working in parallel with actual dynamic industrial automated processes.     

Probabilistic Argumentation Systems and Abduction

Probabilistic argumentation systems are based on assumption-based reasoning for obtaining arguments supporting hypotheses and on probability theory to compute probabilities of supports. Assumption-based reasoning is closely related to hypothetical reasoning or inference through theory formation. The latter approach has well known relations to abduction and default reasoning. In this paper assumption-based reasoning, as an alternative to theory formation aiming at a different goal, will be presented and its use for abduction and model-based diagnostics will be explained. Assumption-based reasoning is well suited for defining a probability structure on top of it. On the base of the relationships between assumption-based reasoning on the one hand and abduction on the other hand, the added value introduced by probability into model based diagnostics will be discussed. Furthermore, the concepts of complete and partial models are introduced with the goal to study the quality of inference procedures. In particular this will be used to compare abductive to possible explanations.     

含约束的基于模型的诊断系统

在诊断空间中如何选取理想诊断是诊断系统面临的一个重要问题。在实际的诊断过程中,人们会利用限制条件排除不太可能的诊断,或者利用强制条件选取较优的诊断。按照这个思想,作者提出含约束的基于模型的诊断系统,通过增加依赖于应用领域的约束控制诊断空间,这是一种能够融入计算过程的选择诊断的机制,同时作者在系统拓扑结构的基础上给出了选取理想约束的理论依据。     

Computing extended abduction through transaction programs

To explain observations from nonmonotonic background theories, one often needs removal of some hypotheses as well as addition of other hypotheses. Moreover, some observations should not be explained, while some are to be explained. In order to formalize these situations, extended abduction was introduced by Inoue and Sakama (1995) to generalize traditional abduction in the sense that it can compute negative explanations by removing hypotheses and anti‐explanations to unexplain negative observations. In this paper, we propose a computational mechanism for extended abduction. When a background theory is written in a normal logic program, we introduce its transaction program for computing extended abduction. A transaction program is a set of non‐deterministic production rules that declaratively specify addition and deletion of abductive hypotheses. Abductive explanations are then computed by the fixpoint of a transaction program using a bottom‐up model generation procedure. The correctness of the proposed procedure is shown for the class of acyclic covered abductive logic programs. In the context of deductive databases, a transaction program provides a declarative specification of database update. This revised version was published online in June 2006 with corrections to the Cover Date.     

On rules of abduction

We present a logical theory of abduction based on the idea of recognizing explanation, or abduction, as a separate reasoning activity. We describe a formalism for writing rules of abduction; furthermore, we define a validity criterion for such rules. The criterion is based on the concept of invariants. This idea allows us to link abduction with induction and deduction. We believe that the three types of inference rules can best be understood in terms of symmetry, i.e. types of relations they preserve, namely: explainability, falsifiability and truth. We also formulate a model theory of abduction and link it with a proof theory. We discuss a variety of rules of abduction and argue that logical forms of abduction do not have to be restricted to the reversemodus ponens. These rules are used to describe such tasks as word-sense disambiguation and anaphora resolution in natural language processing, as well as abduction-based diagnosis.     

An Artificial Network Simulating Cause-to-Effect Reasoning: Cancellation Interactions and Numerical Studies

During the last few decades, a variety of models have been proposed to address causal reasoning (known also as abduction); most of these dealt with a probabilistic or a logical framework. Recently, a few models have been proposed within a neural framework. The investigation of neural approaches is mainly motivated by the computational burden of the causal reasoning task and by the satisfactory results given by neural networks in solving hard problems in general. A particular class of causal reasoning that raises several difficulties is the cancellation class. From an abstract point of view, cancellation occurs when two causes (hypotheses) cancel each other's explanation capabilities with respect to a given effect (observation). The present work is twofold. First, we extend an existing neural model to handle cancellation interactions. Second, we test the model on a large database and propose objective criteria to quantitatively evaluate the scenarios (explanations) produced. Simulation results show good performance and stability of the model. Received 17 November 1999 / Revised 12 May 2000 / Accepted in revised form 16 June 2000     

Using compiled knowledge to guide and focus abductive diagnosis

Several artificial intelligence architectures and systems based on “deep” models of a domain have been proposed, in particular for the diagnostic task. These systems have several advantages over traditional knowledge based systems, but they have a main limitation in their computational complexity. One of the ways to face this problem is to rely on a knowledge compilation phase, which produces knowledge that can be used more effectively with respect to the original one. We show how a specific knowledge compilation approach can focus reasoning in abductive diagnosis, and, in particular, can improve the performances of AID, an abductive diagnosis system. The approach aims at focusing the overall diagnostic cycle in two interdependent ways: avoiding the generation of candidate solutions to be discarded a posteriori and integrating the generation of candidate solutions with discrimination among different candidates. Knowledge compilation is used off-line to produce operational (i.e., easily evaluated) conditions that embed the abductive reasoning strategy and are used in addition to the original model, with the goal of ruling out parts of the search space or focusing on parts of it. The conditions are useful to solve most cases using less time for computing the same solutions, yet preserving all the power of the model-based system for dealing with multiple faults and explaining the solutions. Experimental results showing the advantages of the approach are presented     

The famous five factors in teamwork: a case study of fratricide

The purpose of this paper is to propose foundations for a theory of errors in teamwork based upon analysis of a case study of fratricide alongside a review of the existing literature. This approach may help to promote a better understanding of interactions within complex systems and help in the formulation of hypotheses and predictions concerning errors in teamwork, particularly incidents of fratricide. It is proposed that a fusion of concepts drawn from error models, with common causal categories taken from teamwork models, could allow for an in-depth exploration of incidents of fratricide. It is argued that such a model has the potential to explore the core causal categories identified as present in an incident of fratricide. This view marks fratricide as a process of errors occurring throughout the military system as a whole, particularly due to problems in teamwork within this complex system. Implications of this viewpoint for the development of a new theory of fratricide are offered.

Statement of Relevance: This article provides an insight into the fusion of existing error and teamwork models for the analysis of an incident of fratricide. Within this paper, a number of commonalities among models of teamwork have been identified allowing for the development of a model.     

Machine Learning on the Basis of Formal Concept Analysis

A model of machine learning from positive and negative examples (JSM-learning) is described in terms of Formal Concept Analysis (FCA). Graph-theoretical and lattice-theoretical interpretations of hypotheses and classifications resulting in the learning are proposed. Hypotheses and classifications are compared with other objects from domains of data analysis and artificial intelligence: implications in FCA, functional dependencies in the theory of relational data bases, abduction models, version spaces, and decision trees. Results about algorithmic complexity of various problems related to the generation of formal concepts, hypotheses, classifications, and implications.     

I-DSS: an intelligent diagnostic support system

An intelligent diagnostic support system (I-DSS) for decision-making support in diagnostic processes is presented. I-DSS can be placed between diagnosis carried out by a human diagnostician, without any automatic support, and diagnosis carried out in a fully automatic way. Fully automatic diagnosis may be appealing if used in very complex domains and if the user is non-expert. However, in the case of an expert user, a fully automatic approach is not suitable. In the fully automatic approach the system should be equipped with a strategic knowledge base (the knowledge needed for making the 'best' choice) and as a consequence the expert user is prevented from making decisions on the basis of his or her own experience. This restriction causes, in general, a sort of psychological rejection, on the part of the expert user, of the traditional fully automatic approach. This is particularly true in those domains, such as medicine, where there is more than one approach to the solution and it is seldom that one approach can be considered 'right' and the others 'wrong'. Experience related to diagnostic expert systems applications shows that, whenever trade-off problems arise in choosing between alternative actions, it is preferable to leave decisions to the expert. Starting from these considerations we present a system (I-DSS) which, without being 'intrusive', aims to be an effective support for the decision-maker during the diagnostic process.     

基于模糊神经网络的WSN无线数据收发单元故障诊断

在一些无线传感器网络(Wireless Sensor Network,WSN)安全监测系统中,节点长时间传输大量数据,导致无线数据收发单元容易出现功率下降和功率放大器(Power Amplifier,PA)被烧毁的现象,而此类故障的诊断方法一般比较复杂且低效。针对上述问题,在分析WSN单元级故障诊断的基础上,利用无线数据收发单元的电流模型,提出了一种基于模糊神经网络的无线数据收发单元故障诊断方法。首先,根据无线数据收发单元中发射消耗的电流与温度和供电电压的关系,建立电流模型;然后,利用聚类算法确定模糊神经网络模型结构,结合混合学习算法优化模糊规则的前件参数和后件参数;最后,提取训练完的模糊神经网络参数,以建立WSN节点故障诊断模型。实验结果表明,提出的无线数据收发单元故障诊断方法的计算量小,诊断准确度高;与高斯过程回归模型相比,其计算量降低了22.4%,诊断准确度提高了17.5%。