Verification of rule-based expert systems

We are investigating the problem of establishing computational rather than syntactic properties of forward-chaining rule-based expert systems. We model an expert system as a computation on working memory, define its execution semantics, and present proof techniques suitable for those semantics. Specifically, we model execution as a Dijkstra guarded-do construct, and use Dijkstra's Invariance Theorem and weakest precondition predicate transformers to establish invariants (safety properties) and postconditions (liveness properties). Our approach is an application of well-developed methods developed by Dijkstra and others for the verification of procedural programs. This paper introduces the approach, reports some initial results, and discusses future work.     

Using directed hypergraphs to verify rule-based expert systems

Rule-based representation techniques have become popular for storage and manipulation of domain knowledge in expert systems. It is important that systems using such a representation are verified for accuracy before implementation. In recent years, graphical techniques have been found to provide a good framework for the detection of errors that may appear in a rule base. The authors present a graphical representation scheme that: 1) captures complex dependencies across clauses in a rule base in a compact yet intuitively clear manner and 2) is easily automated to detect structural errors in a rigorous fashion. Their technique uses a directed hypergraph to accurately detect the different types of structural errors that appear in a rule base. The technique allows rules to be represented in a manner that clearly identifies complex dependencies across compound clauses. Subsequently, the verification procedure can detect errors in an accurate fashion by using simple operations on the adjacency matrix of the directed hypergraph. The technique is shown to have a computational complexity that is comparable to that of other graphical techniques. The graphical representation coupled with the associated matrix operations illustrate how directed hypergraphs are a very appropriate representation technique for the verification task     

Integrating artificial neural networks with rule-based expert systems

The Rule-Based (RB) and the Artificial Neural Network (ANN) approaches to expert systems development have each demonstrated some specific advantages and disadvantages. These two approaches can be integrated to exploit the advantages and minimize the disadvantages of each method used alone. An RB/ANN integrated approach is proposed to facilitate the development of an expert system which provides a “high-performance” knowledge-based network, an explanation facility, and an input/output facility. In this case study an expert system designed to assist managers in forecasting the performance of stock prices is developed to demonstrate the advantages of this integrated approach and how it can enhance support for managerial decision making.     

Framework for building rule-based machine diagnostic expert systems

In the endeavour to build an expert system called XBAK using Personal Consultant Plus for the diagnosis of sophisticated equipment used in microchip manufacturing, a rule-based machine diagnostic expert system architecture was developed. The approach, features and technical implementation of this application-independent problem-solving structure are described. The architecture can be used as a framework for solving similar problems in the area of machine diagnostics.     

Improving the efficiency of rule-based expert systems by rule activation

Abstract

In this paper we test a hypothesis that has shown promise in enhancing the efficiency ( run-time) of rule-based systems. The results of our experiments suggest that the use of rule activation plays an active part in improving the performance of rule bases containing conflict sets.     

A token-flow paradigm for verification of rule-based expert systems

This paper presents a novel approach to the verification of rule-based systems (RBSs). A graph structure, called the rule-dependency graph (RDG), is introduced to describe the dependency relationship among the rules of an RBS, in which each type of improper knowledge forms a specific topological structure. Knowledge verification is then performed by searching for such topological structures through a token-flow paradigm. An algorithm is provided, which automatically generates a minimally sufficient set of literals as test tokens in the detection procedure. The proposed scheme can be applied to rules of non-Horn clause form in both propositional and first-order logic, and restrictions imposed by other graph-based approaches can be avoided. Furthermore, explicit and potential anomalies of RBSs can be correctly found, and efficient run-time validation is made possible.     

Parallel implementation of rule-based expert systems for interactive applications

A novel approach to parallel implementation of rule-based expert systems is presented in this paper. This approach is tailored for expert systems in interactive applications. Rule-based expert systems are modeled by state space and AND/OR graphs. The interdependences among rules are analyzed to guide rule-base partitioning and memory bank assignment. Parallel execution of rule-based expert systems is investigated in the environment of closely coupled multiprocessors. Algorithms are developed for the parallel execution of rules and for the allocation of data to memory banks in interactive applications.     

Uncertainty analysis of rule-based expert systems with Dempster-Shafer mass assignments

This article extends Dempster-Shafer Theory (DST) mass probability assignments to Boolean algebra and considers how such probabilities can propagate through a system of Boolean equations, which form the basis for both rule-based expert systems and fault trees. the advantage of DST mass assignments over classical probability methods is the ability to accommodate when necessary uncommitted probability belief. This paper also examines rules in the context of a probabilistic logic, where a given rule itself may be true with some probability in the interval [0,1]. When expert system knowledge bases contain rules which may not always hold, or rules that occasionally must be operated upon with imprecise information, the DST mass assignment formalism is shown to be a suitable methodology for calculating probability assignments throughout the system.     

Soliciting weights or probabilities from experts for rule-based expert systems

Rule-based expert systems attach a weight to each rule in order to represent uncertainty or strength of association. There are a number of schemes that are used to represent uncertainty in expert systems. Some of these methods allow the system designer to solicit either the probabilities, used to compute the weights, or to solicit the weights directly, or both.This paper presents results that indicate that if the weights are gathered directly, rather than using probabilities, then the weights may not meet the underlying conditions of the mathematical model of uncertainty on which the weights are based or the weights may imply highly unusual behavior for the underlying probabilities and implicit utility function.In one system it is found that there were violations of the mathematical properties of the model in over forty percent of the weights on the rules of the system. If the weights do not meet the constraints of the underlying mathematical models then such violations may yield inappropriate parameterization of other weights in order to make the model work. Further, such violations can lead to an inappropriate estimation of the probabilities of events by the system and yield inappropriate inferred weights.In another case it was found that a system was dominated by weights that suggest highly unusual behavior for the underlying probabilities.From an operational perspective these inconsistencies indicate the importance of the method used in gathering the weights, e.g. indirectly through the probabilities or directly through the weights. It also indicates the importance of validating and verifying the weights to ensure that the weights meet the needs of the underlying theory and do not force unusual relationships onto the underlying probabilities.     

Measuring the complexity of adaptive peer-to-peer systems

To improve the efficiency of peer-to-peer (P2P) systems while adapting to changing environmental conditions, static peer-to-peer protocols can be replaced by adaptive plans. The resulting systems are inherently complex, which makes their development and characterization a challenge for traditional methods. Here we propose the design and analysis of adaptive P2P systems using measures of complexity, emergence, self-organization, and homeostasis based on information theory. These measures allow the evaluation of adaptive P2P systems and thus can be used to guide their design. We evaluate the proposal with a P2P computing system provided with adaptation mechanisms. We show the evolution of the system with static and also changing workload, using different fitness functions. When the adaptive plan forces the system to converge to a predefined performance level, the nodes may result in highly unstable configurations, which correspond to a high variance in time of the measured complexity. Conversely, if the adaptive plan is less “aggressive”, the system may be more stable, but the optimal performance may not be achieved.     

A computational paradigm that integrates rule-based and model-based reasoning in expert systems

This article presents a new computational paradigm that integrates rule-based and model-based reasoning in expert systems. Our experience in expert systems research and development indicates that the rule-based technique is simple, elegant, and efficient; whereas the model-based approach is complex but powerful, CPU-consuming but robust. Combining both the rule-based and the model-based methods into one paradigm means having the best of both worlds. to achieve this goal, we have extended the Prolog unification algorithm to accommodate semantic unification. the resulting computational procedure is named R.M. This new inference procedure uses rule-based reasoning by default, and it automatically invokes model-based reasoning when all the rules become inapplicable, but it returns to rule-based reasoning whenever the rules become usable again. the idea behind this problem-solving strategy is to achieve maximum efficiency as well as robustness in expert systems. Examples are used throughout the article to illustrate our notions. the article also sketches an application in the domain of telecommunication networks maintenance and describes our experimental results.     

Overcoming deficiencies of the rule-based medical expert system

One of the current deficiencies of the rule-based expert system is its static nature. As these systems are applied to medicine, this shortcoming becomes accentuated by: the rapid speed at which new knowledge is generated, the regional differences associated with the expression of many diseases, and the rate at which patient demographics and disease incidence change over time. This research presents a solution to the static nature of the rule-based expert system by proposing a hybrid system. This system consists of an expert system and a statistical analysis system linked to a patient database. The additional feature of a rule base manager which initiates automatic database analysis to refresh the statistical correlation of each rule ensures a dynamic, current, statistically accurate rule base. The philosophical differences between data and knowledge are also addressed as they apply to this type of hybrid system. The system is then used to generate four rule bases from different knowledge sources. These rule bases are then compared.     

A rule-based expert system for earthquake prediction

Earthquake is a natural disaster which causes extensive damage as well as the death of thousands of people. Earthquake professionals for many decades have recognized the benefits to society from reliable earthquake predictions. Techniques like: mathematical modelling, hydrology analysis, ionosphere analysis and even animal responses have been used to forecast a quake. Most of these techniques rely on certain precursors like, stress or seismic activity. Data mining techniques can also be used for prediction of this natural hazard. Data mining consists of evolving set of techniques such as association rule mining that can be used to extract valuable information and knowledge from massive volumes of data. The aim of this study is to predict a subsequent earthquake from the data of the previous earthquake. This is achieved by applying association rule mining on earthquake data from 1979 to 2012. These associations are polished using predicate-logic techniques to draw stimulating production-rules to be used with a rule-based expert system. Prediction process is done by an expert system, which takes only current earthquake attributes to predict a subsequent earthquake. The rules generated for predicting the earthquake are mathematically validated as well as tested on real life earthquake data. Results from our study show that the proposed rule-based expert system is able to detect 100 % of earthquakes which actually occurred within 15 hours at-most within a defined range, depth and location. This work solely relies on previous earthquake data for predicting the next.     

Patterns of interaction in rule-based expert system programming

We study the effect of adding a rule to a rule-based heuristic classification expert system, in particular, a rule that causes an unforeseen interaction with rules already in the rule set. We show that it is possible for such an interaction to occur between sets of rules, even when no interaction is present between any pair of rules contained in these sets. A method is presented that identifies interactions between sets of rules, and an analysis is given which relates these interactions to rule-based programming practices which help to maintain die integrity of the knowledge base. We argue mat the method is practical, given some reasonable assumptions on the knowledge base.     

Enhanced high-level Petri nets with multiple colors for knowledgeverification/validation of rule-based expert systems

Exploring the properties of rule-based expert systems through Petri net models has received a lot of attention. Traditional Petri nets provide a straightforward but inadequate method for knowledge verification/validation of rule-based expert systems. We propose an enhanced high-level Petri net model in which variables and negative information can be represented and processed properly. Rule inference is modeled exactly and some important aspects in rule-based systems (RBSs), such as conservation of facts, refraction, and closed-world assumption, are considered in this model. With the coloring scheme proposed in this paper, the tasks involved in checking the logic structure and output correctness of an RES are formally investigated. We focus on the detection of redundancy, conflicts, cycles, unnecessary conditions, dead ends, and unreachable goals in an RES. These knowledge verification/validation (KVV) tasks are formulated as the reachability problem and improper knowledge can be detected by solving a set of equations with respect to multiple colors. The complexity of our method is discussed and a comparison of our model with other Petri net models is presented.     

A rule-based expert system for inferring functional annotation

Functional annotation is the process that assigns a biological functionality to a deoxyribonucleic acid (DNA) sequence. It requires searching in huge data sets for candidates, and inferring the most appropriate features based on the information found and expert knowledge. When humans perform most of these tasks, results are of a high quality, but there is a bottleneck in processing; when experts are largely replaced by automated tools, annotation is faster but of poorer quality. Combining the automatic annotation with expert systems (ESs) can enhance the quality of the annotation, while effectively reducing experts’ workload. This paper presents INFAES, a rule-based ES developed for mimicking the human reasoning in the inference stage of the functional annotation. It integrates knowledge on Biology and heuristics about the use of Bioinformatics tools. Its development adopts state-of-the-art methodologies to facilitate the acquisition and integration of new knowledge. INFAES showed a high performance when compared to the systems developed for the first large-scale community-based critical assessment of protein function annotation (CAFA) [1].     

Reliability testing of rule-based systems

Rule-based software systems are becoming more common in industrial settings, particularly to monitor and control large, real-time systems. The authors describe an algorithm for reliability testing of rule-based systems and their experience using it to test an industrial network surveillance system     

用于专家系统规则库的冗余校验方法研究

产生式规则是目前应用较多的一种知识表示方法。在用于确定发酵过程生物量软测量混合模型结构的专家系统中,当向产生式规则知识库添加新的规则时,冗余的存在会影响推理的效率以及推理的准确性。提出了一种用于该专家系统规则库的冗余校验方法,给出了冗余规则的判别、冗余规则的处理以及冗余校验的实现方法。实验结果表明,该冗余校验方法可以根据输入条件和已有规则,判断出新添加的规则是否冗余,并在消除冗余对推理效率影响的同时,降低模型复杂度,有利于优化混合模型的结构。     

Optimizing real-time equational rule-based systems

Analyzing and reducing the execution-time upper bound of real-time rule-based expert systems is a very important task because of the stringent timing constraints imposed on this class of systems. We present a new runtime optimization to reduce the execution-time upper bound of real-time rule-based expert systems. In order to determine rules to be evaluated at runtime, a predicate dependency list, which consists of a predicate, its active rule set and corresponding inactive rule set, is created for each predicate in a real-time rule-based program. Based on the predicate dependency list and the current value of each variable, the new runtime optimization dynamically selects rules to be evaluated at runtime. For the timing analysis of the proposed algorithm, we introduce a predicate-based rule dependency graph, a predicate-based enable-rule graph, and their construction algorithm. We also discuss the bounded time of the equational logic rule-based program using the predicate-based rule dependency graph as well as the predicate-based enable-rule graph. The implementation and performance evaluation of the proposed algorithm using both synthetic and practical real-time rule-base programs are also presented. The performance evaluation shows that the runtime optimizer reduces the number of rule evaluations and predicate evaluations as well as the response time upper bound significantly, and the new algorithm yields better execution-time upper bound compared to other optimization methods.