Verification of Knowledge-Based Systems Using Predicate/Transition Nets

As expert-system technology gains broader acceptance, the need to build and maintain large-scale knowledge-based systems (KBSs) will assume greater importance. Traditional approaches to KBS verification generally contain no predicate/transition (PrT) net models, thus making them slow for the large-scale KBS with chained errors. This paper proposes an attractive alternative to KBS verification, in which the KBS is modeled as a PrT-net model. Then, the least fixpoint semantics of the PrT-net model can be introduced into the KBS for the purpose of speeding up the computations of the KBSs. The significance of this paper is that seven propositions are formulated to detect errors of redundancy, subsumption, unnecessary condition, circularity, inconsistency, dead end, and unreachable goal. Thus, the performance of a computer-aided-design tool for KBSs can be improved to some extent. Meanwhile, specification languages, including Programming in Logic, Frame-and-Rule-Oriented Requirements Specification Language, and the like, are suitable to this approach.     

Using KBS verification techniques to demonstrate the existence of rule anomalies in ADBs

As the field of verification and validation for knowledge-based systems (KBSs) has matured, much information, technology, and theory has become available. Though not all of the problems with respect to KBSs have been solved, many have been identified with solutions that can be used in an analogous manner in situations where the application is not necessarily a traditional KBS. As one example, the “active” component in an active database (ADB) consists of rules that execute as a result of database accesses and updates. In this paper, we demonstrate that anomalies found to impact the correctness of a KBS can also exist in ADBs. We first compare the rule structure of a KBS with the rule structures of various ADBs. To show their existence, we convert the rule syntax of the ADBs into a consistent format for analysis and anomaly detection. Once converted, we apply KBS verification techniques to isolate these anomalies. Due to the more increasing use of triggered rules in ADBs, this work illustrates the danger these anomalies can pose and the ever increasing need for ADB verification techniques to exist.     

Knowledge modelling for a generic refinement framework

Refinement tools assist with debugging the knowledge-based system (KBS), thus easing the well-known knowledge acquisition bottleneck, and the more recently recognised maintenance overhead. The existing refinement tools were developed for specific rule-based KBS environments, and have usually been applied to artificial or academic applications. Hence, there is a need for tools which are applicable to industrial applications. However, it would be wasteful to develop separate refinement tools for individual shells; instead, the KrustWorks project is developing reusable components applicable to a variety of KBS environments. This paper develops a knowledge representation that embodies a KBS's rulebase and its reasoning, and permits the implementation of core refinement procedures, which are generally applicable and can ignore KBS-specific details. Such a representation is an essential stage in the construction of a generic automated knowledge refinement framework, such as KrustWorks. Experience from applying this approach to Clips, PowerModel and Pfes KBSs indicates its feasibility for a wider variety of industrial KBSs.     

Modeling in the design of a KBS validation system

We describe and illustrate the modeling issues in the design of a system for validation of knowledge based systems (KBSs). the domain of such a validation system is “KBSs and their validation problems.” the basic idea in our solution is the following. Since different KBSs may use different knowledge representation languages, we first represent the target KBS (i.e., the KBS to be validated) in a general formal model of KBS, and then validate it in this form. the advantage of this strategy is that validation problem solving needs only to refer to the common language of the general formal model. We present a set of possible conceptual abstraction levels in such a model, and argue that each level is associated with a related view on validation problems. Since high level characterizations are difficult to abstract from current knowledge representation languages, we consider the formal aspects of modeling mainly at the “lowest” level, the so-called inference primitive level. We illustrate the approach by formalizing a solution for selected modeling issues at this level.     

Verification of non-monotonic knowledge bases

Non-monotonic Knowledge-Based Systems (KBSs) must undergo quality assurance procedures for the following two reasons: (i) belief revision (if such is provided) cannot always guarantee the structural correctness of the knowledge base, and in certain cases may introduce new semantic errors in the revised theory; (ii) non-monotonic theories may have multiple extensions, and some types of functional errors which do not violate structural properties of a given extension are hard to detect without testing the overall performance of the KBS. This paper presents an extension of the distributed verification method, which is meant to reveal structural and functional anomalies in non-monotonic KBSs. Two classes of anomalies are considered: (i) structural anomalies which manifest themselves within a given extension (such as logical inconsistencies, structural incompleteness, and intractabilities caused by circular rule chains), and (ii) functional anomalies related to the overall performance of the KBS (such as the existence of complementary rules and some types of rule subsumptions). The corresponding verification tests are presented and illustrated on an extended example.     

高性能知识库构造环境

知识库系统(KBS)开发环境的特点是简便性和领域适应性。我们认为如果在KBS开发环境中既有抽象结均,又有多种集成工具,则该环境将会非常有效。本文介绍一个KBS 开发环境DECISION-E,它有一个适应应用领域KBS 的清晰、灵活的抽象结构,而且还有许多集成工具。这种结构使得DECISION-E能建立多种现实领域中的KBS,并使建立的KBS能较全面地反映应用领域的性质。集成工具将辅助设计者建立KBS,支持KBS 的问题求解并进行多种事务处理。在DECISIGN-E 中还采用了下面的一些特殊技术:不同层次的知识表达方法,多推理机,推理中断处理,基于全局黑板的分布式问题求解,基于知识的建模及数据抽象,演绎数据库管理方法。     

Applying rule-base anomalies to KADS inference structures

The literature on validation and verification of knowledge-based systems contains a catalogue of anomalies for knowledge-based systems, such as redundant, contradictory or deficient knowledge. Detecting such anomalies is a method for verifying knowledge-based systems. Unfortunately, the traditional formulation of the anomalies in the literature is very specific to a rule-based knowledge representation, which greatly restricts their applicability. In this paper, we show how the traditional anomalies can be reinterpreted in terms of conceptual models (in particular KADS inference structures). For this purpose, we present a formalisation of KADS inference structures which enables us to apply the traditional rule-base anomalies to these inference structures. This greatly improves the usefulness of the anomalies, since they can now be applied to a much wider class of knowledge-based systems. Besides this reformulation and wider applicability of the traditional anomalies, further contributions of this paper are a novel formalisation of KADS inference structures and a number of improvements to the existing formalisation of the traditional anomalies.     

A binary encoded incidence matrix representation for KBS Verification

An advanced binary encoded incidence matrix representation, to support KBS Verification and Validation (KBS V & V), is described. The representation has two very important advantages over traditional incidence matrix representation techniques. Firstly the storage capacity required by the binary encoded matrices is substantially less (97%) than that required using more conventional incidence matrix representations. Secondly the representation supports much more efficient processing. Both a traditional and the advanced incidence matrix representation are described as built into two KBS V & V systems, IMVER-1 and IMVER-2. The similarity between the two systems provides an appropriate mechanism for comparing the two representations. Two algorithms, one for inference verification and one for structural verification, are analysed with respect to the IMVER representations. Consequently some time complexity measures are determined based on the number of matrix element comparisons required when the algorithms are tested against a range of “balanced” rulebases. The overall conclusion is that the advanced binary representation, as implemented in the IMVER-2 system, when tested against realistically sized rulebases, utilizes significantly fewer (around 96%) comparisons than that required by the traditional representation technique incorporated into the IMVER-1 system.     

A hybrid system applied to epidemic screening

Although many knowledge-based systems (KBSs) focus on single-paradigm approaches to encoding knowledge (such as production rules), human experts rarely use a single type of knowledge to solve a real-world problem. A human expert usually combines a number of reasoning mechanisms. In recent years, rule-based reasoning (RBR), case-based reasoning (CBR) and model-based reasoning (MBR) have emerged as important and complementary reasoning methodologies in the intelligent systems area. For complex problem solving, it is useful to integrate RBR, CBR and MBR. In this paper, a hybrid epidemic screening KBS which integrates a deductive RBR system, an inductive CBR system and a quantitative MBR system is proposed. The system has been tested using real epidemic screening variables and data.     

Design of knowledge-based systems with a knowledge-based assistant

The authors propose a model for an intelligent assistant to aid in building knowledge-based systems (KBSs) and discuss a preliminary implementation. The assistant participates in KBS construction, including acquisition of an initial model of a problem domain, acquisition of control and task-specific inference knowledge, testing and validation, and long-term maintenance of encoded knowledge. The authors present a hypothetical scenario in which the assistant and a KBS designer cooperate to create an initial domain model and then discuss five categories of knowledge the assistant requires to offer such help. They discuss two software technologies on which the assistant is based: an object-oriented programming language, and a user-interface framework     

Logical Object as a Basis of Knowledge Based Systems

This paper presents a framework called logical knowledge object (LKO),which is taken as a basis of the dependable development of knowledge based systems(KBSs).LKO combines logic programming and object-oriented programming paradigms,where objects are viewed as abstractions with states,constraints,behaviors and inheritance.The operational semantics defined in the style of natural semantics is simple and clear.A hybrid knowledge representation amalgamating rule,frame,semantic network and blackboard is available for both most structured and flat knowledge.The management of knowledge bases has been formally specified.Accordingly,LKO is well suited for the formal representation of knowledge and requirements of KBSs.Based on the framework,verification techniques are also explored to enhance the analysis of requirement specifications and the validation of KBSs.In addition,LKO provides a methodology for the development of KBSs,applying the concepts of rapid prototyping and top-down design to deal with changing and incomplete requirements,and to provide multiple abstract models of the domain,where formal methods might be used at each abstract level.     

Using Rule Quality Measures for Rule Base Refinement in Knowledge-Based Predictive Maintenance Systems

Abstract

As today’s manufacturing domain is becoming more and more knowledge-intensive, knowledge-based systems (KBS) are widely applied in the predictive maintenance domain to detect and predict anomalies in machines and machine components. Within a KBS, decision rules are a comprehensive and interpretable tool for classification and knowledge discovery from data. However, when the decision rules incorporated in a KBS are extracted from heterogeneous sources, they may suffer from several rule quality issues, which weakens the performance of a KBS. To address this issue, in this paper, we propose a rule base refinement approach with considering rule quality measures. The proposed approach is based on a rule integration method for integrating the expert rules and the rules obtained from data mining. Within the integration process, rule accuracy, coverage, redundancy, conflict, and subsumption are the quality measures that we use to refine the rule base. A case study on a real-world data set shows the approach in detail.     

A hybrid knowledge-based system applied to epidemic screening

Although many knowledge-based systems (KBSs) focus on single-paradigm approaches to encoding knowledge (such as production rules), experts rarely use a single type of knowledge in solving a problem. More often, an expert will apply a number of reasoning mechanisms. In recent years, rule-based reasoning (RBR), case-based reasoning (CBR) and model-based reasoning (MBR) have emerged as important and complementary reasoning methodologies in artificial intelligence. For complex problem solving, it is useful to integrate RBR, CBR and MBR. In this paper, a hybrid KBS which integrates a deductive RBR system, an inductive CBR system and a quantitative MBR system is proposed for epidemic screening. The system has been tested using real data, and results are encouraging.     

Knowledge-based systems from a socio-cognitive 1 perspective

Abstract

Recent trends in the design and development of knowledge-based systems KBSs are discussed with special emphasis on issues that relate to situated knowledge. A knowledge base is regarded as a model of expertise that acknowledges the embeddedness of expert knowledge in social interaction and in the workplace in general. KBS development is viewed as an instance of socio-technical design. Experience from several European projects is recounted to illustrate the issues addressed. Suggestions for KBS development are presented as methodological guidelines, with special emphasis on systems employing case-based reasoning.     

Knowledge-based support in help-desk environments

How much does a knowledge based system improve help desk interactions? To investigate the relationship between a KBS and a help desk and to provide a first step in determining the return on investment of KBSs in general, we conducted a study that showed as accurately as possible the impact of a KBS on one of Hewlett-Packard's customer support centers. We organized the study to verify three main assumptions: it takes less time to resolve a call when the analyst uses the KBS; the time saving shows up as a weekly decrease in overall interaction time; using a KBS allows the analyst to solve more kinds of problems than not using it     

Knowledge-based systems from a socio-cognitive 1 perspective

. Recent trends in the design and development of knowledge-based systems KBSs are discussed with special emphasis on issues that relate to situated knowledge. A knowledge base is regarded as a model of expertise that acknowledges the embeddedness of expert knowledge in social interaction and in the workplace in general. KBS development is viewed as an instance of socio-technical design. Experience from several European projects is recounted to illustrate the issues addressed. Suggestions for KBS development are presented as methodological guidelines, with special emphasis on systems employing case-based reasoning.     

A patterned approach for linking knowledge-based systems to external resources

Knowledge-based systems (KBSs) have been developed and used in industry and government as assistance systems, voting partner systems, and embedded applications. As web-based systems change the face of software implementations, these closed, internal KBSs need to be integrated into multicomponent applications that provide updated and extensible services. Therefore, KBSs must be adapted to an environment in which data and control are exchanged with external processes and resources; complementing other participating systems or using them to refine its own results. This integration can be a daunting task. If improperly done, it can result in an inefficient and unmanageable composite application. One approach to simplifying this task is the use of architectural patterns for integration. These patterns are assembled from functional entities that resolve component interoperability conflicts. In this paper, we describe an architectural pattern called the Knowledge Director pattern, which directs the integration of a closed KBS into a broader application environment.     

On subsumption in distributed derivations

In this paper we study the subsumption inference rule in the context of distributed deduction. It is well known that the unrestricted application of subsumption may destroy the fairness and thus the completeness of a deduction strategy. Solutions to this problem in sequential theorem proving are known. We observe that in distributed automated deduction, subsumption may also thwartmonotonicity, a dual property of soundness, in addition to completeness. Not only do the solutions for the sequential case not apply, even proper subsumption may destroy monotonicity in the distributed case.We present these problems and propose a general solution that treats subsumption as a composition of a replacement inference rule,replacement subsumption, and a deletion inference rule,variant subsumption. (Proper subsumption, in this case, becomes a derived inference rule.) We define a newdistributed subsumption inference rule, which has all the desirable properties: it allows subsumption, including subsumption of variants, in a distributed derivation, while preserving fairness and monotonicity. It also works in both sequential and distributed environments.We conclude the paper with some discussion of the different behavior of subsumption in different architectures.     

Using goals to design and verify rule bases

The design of rule-based systems is often plagued by errors and anomalies. The verification and validation (V and V) processes to detect errors and anomalies in a rule base are complex. Methods that are general enough for comprehensive anomaly detection suffer from heavy computation. Special methods for V and V that have reduced computational needs lack in their scope and applicability. Most of the existing verification tools perform their checking based on the syntax of rule base encoding often ignoring useful meta knowledge of the domain. In this paper, we propose a way to abstract domain knowledge using goals. At the design level, goals are realized in a rule base using one of several design schemes, where a design scheme is a goal-to-hypothesis mapping satisfying certain constraints. At the implementation level, goals are inferred using partially ordered rule sequences called paths. Verification of a rule base can be performed by identifying certain rule aberrations, that can be indicative of the rule base anomalies circularity, ambivalence, redundancy, and deficiency. A case study is presented to highlight that the goal-based approach is useful for preventing rule subsumption (a form of redundancy) and for enhancing the (run time) performance of a rule base.