Approximate declarative semantics for rule base anomalies

Despite the fact that there has been a surge of publications in verification and validation of knowledge-based systems and expert systems in the past decade, there are still gaps in the study of verification and validation (V&V) of expert systems, not the least of which is the lack of appropriate semantics for expert system programming languages. Without a semantics, it is hard to formally define and analyze knowledge base anomalies such as inconsistency and redundancy, and it is hard to assess the effectiveness of V&V tools, methods and techniques that have been developed or proposed. In this paper, we develop an approximate declarative semantics for rule-based knowledge bases and provide a formal definition and analysis of knowledge base inconsistency, redundancy, circularity and incompleteness in terms of theories in the first order predicate logic. In the paper, we offer classifications of commonly found cases of inconsistency, redundancy, circularity and incompleteness. Finally, general guidelines on how to remedy knowledge base anomalies are given.     

Foundation and application of knowledge base verification

Anomalies such as redundant, contradictory, and deficient knowledge in a knowledge base are symptoms of probable errors. Detecting anomalies is a well-established method for verifying knowledge-based systems. Although many tools have been developed to perform anomaly detection, several important issues have been neglected, especially the theoretical foundations and computational limitations of anomaly detection methods, and analyses of the utility of such tools in practical use. This article addresses these issues by presenting a theoretical foundation of anomaly detection methods, and by presenting empirical results obtained in applying one anomaly detection tool to perform verification on five real-world knowledge-based systems. the techniques presented apply specifically to verifying rule-based knowledge bases without numerical certainty measures. © 1994 John Wiley & Sons, Inc.     

Methods and algorithms for verification of knowledge bases in integrated expert systems

In this paper, a brief analysis is presented and methods of verification of expert systems and conventional programs are compared. The specific features of the verification of knowledge bases of integrated expert systems are shown, methods and algorithms of detecting static and dynamic anomalies in the knowledge field are described.     

A tool-supported approach to inter-tabular verification

The use of decision tables to verify knowledge based systems (KBS) has been advocated several times in the validation and verification (V&V) literature. However, one of the main drawbacks of these systems is that they fail to detect anomalies that occur over rule chains. In a decision table based context this means that anomalies that occur due to interactions between tables are neglected. These anomalies are called inter-tabular anomalies. In this paper we investigate an approach that deals with inter-tabular anomalies. One of the prerequisites for the approach was that it could be used by the knowledge engineer during the development of the KBS. This requires that the anomaly check can be performed on-line. As a result, the approach partly uses heuristics where exhaustive checks would be too inefficient. All detection facilities that will be described have been implemented in a table-based development tool called . The use of this tool will be briefly illustrated. In addition, some experiences in verifying large knowledge bases are discussed.     

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 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.     

Formal Nonmonotonic Theories and Properties of Human Defeasible Reasoning

The knowledge representation and reasoning of both humans and artificial systems often involves conditionals. A conditional connects a consequence which holds given a precondition. It can be easily recognized in natural languages with certain key words, like “if” in English. A vast amount of literature in both fields, both artificial intelligence and psychology, deals with the questions of how such conditionals can be best represented and how these conditionals can model human reasoning. On the other hand, findings in the psychology of reasoning, such as those in the Suppression Task, have led to a paradigm shift from the monotonicity assumptions in human inferences towards nonmonotonic reasoning. Nonmonotonic reasoning is sensitive for information change, that is, inferences are drawn cautiously such that retraction of previous information is not required with the addition of new information. While many formalisms of nonmonotonic reasoning have been proposed in the field of Artificial Intelligence, their capability to model properties of human reasoning has not yet been extensively investigated. In this paper, we analyzed systematically from both a formal and an empirical perspective the power of formal nonmonotonic systems to model (i) possible explicit defeaters, as in the Suppression Task, and (ii) more implicit conditional rules that trigger nonmonotonic reasoning by the keywords in such rules. The results indicated that the classical evaluation for the correctness of inferences has to be extended in the three major aspects (i) regarding the inference system, (ii) the knowledge base, and (iii) possible assumed exceptions for the rule.     

Proving Consistency Assertions for Automotive Product Data Management

We present a formal specification and verification approach for industrial product data bases containing Boolean logic formulae to express constraints. Within this framework, global consistency assertions about the product data are converted into propositional satisfiability problems. Today"s state-of-the-art provers turn out to be surprisingly efficient in solving the SAT-instances generated by this process. Moreover, we introduce a method for encoding special nonmonotonic constructs in traditional Boolean logic. We have successfully applied our method to industrial automotive product data management and could establish a set of commercially used interactive tools that facilitate the management of change and help raise quality standards.     

From decision tables to expert system shells

Building and maintaining high quality knowledge based systems is not a trivial task. Decision tables have sometimes been recommended in this process, mainly in verification and validation. In this paper, however, it is shown how decision tables can also be used to generate, and not just to validate, knowledge bases and how the transformation process from decision tables to knowledge bases can be organized. Several options to generate rules or other knowledge representation from decision tables are described and evauluated.

The proposed generation strategy enables the knowledge engineer to concentrate on the acquisition and modelling issues and allows him to isolate the knowledge body from its implementation. The generation process has been implemented for two commercial tools, AionDS and KBMS and has been applied to real world applications.     

A semantical framework for hybrid knowledge bases

In the ongoing discussion about combining rules and ontologies on the Semantic Web a recurring issue is how to combine first-order classical logic with nonmonotonic rule languages. Whereas several modular approaches to define a combined semantics for such hybrid knowledge bases focus mainly on decidability issues, we tackle the matter from a more general point of view. In this paper, we show how Quantified Equilibrium Logic (QEL) can function as a unified framework which embraces classical logic as well as disjunctive logic programs under the (open) answer set semantics. In the proposed variant of QEL, we relax the unique names assumption, which was present in earlier versions of QEL. Moreover, we show that this framework elegantly captures the existing modular approaches for hybrid knowledge bases in a unified way.     

On nonmonotonic reasoning with the method of sweeping presumptions

Reasoning almost always occurs in the face of incomplete information. Such reasoning is nonmonotonic in the sense that conclusions drawn may later be withdrawn when additional information is obtained. There is an active literature on the problem of modeling such nonmonotonic reasoning, yet no category of method-let alone a single method-has been broadly accepted as the right approach. This paper introduces a new method, called sweeping presumptions, for modeling nonmonotonic reasoning. The main goal of the paper is to provide an example-driven, nontechnical introduction to the method of sweeping presumptions, and thereby to make it plausible that sweeping presumptions can usefully be applied to the problems of nonmonotonic reasoning. The paper discusses a representative sample of examples that have appeared in the literature on nonmonotonic reasoning, and discusses them from the point of view of sweeping presumptions.     

Anomalies in ontologies with rules

For the development of practical semantic applications, ontologies are commonly used with rule extensions. Prominent examples of semantic applications not only are Semantic Wikis, Semantic Desktops, but also advanced Web Services and agents. The application of rules increases the expressiveness of the underlying knowledge in many ways. Likewise, the integration not only creates new challenges for the design process of such ontologies, but also existing evaluation methods have to cope with the extension of ontologies by rules.Since the verification of Owl ontologies with rule extensions is not tractable in general, we propose to verify ontologies at the symbolic level by using a declarative approach: With the new language Datalog^?, known anomalies can be easily specified and tested in a compact manner. We introduce supplements to existing verification techniques to support the design of ontologies with rule enhancements, and we focus on the detection of anomalies that especially occur due to the combined use of rules and ontological definitions.     

Minimizing maintenance anomalies in expert systems

Expert systems are emerging as a powerful technology for solving many problems previously requiring human experts. However, maintenance has been identified as a major difficulty in expert system implementations. Surprisingly, the problem of maintenance has only recently begun to receive attention in expert systems research, though it has long been an issue in databases. Databases are in a constant state of change, and the prevention of maintenance anomalies is essential. As similar maintenance operations are performed on rule bases, this paper investigates techniques to avoid maintenance anomalies in expert system rule bases. The result is an expert system rule base structure that is appropriate for volatile production use. In addition to lower maintenance demands, this approach favorably impacts on verification, computational efficiency, and storage requirements.     

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.     

不完全知识下的概念聚类

概念聚类通常使用统计的或基于距离的方法,至于逻辑方法,在不完全知识下往往需要引入非单调性,众所周知在知识“太不完全”是使用非单调方法,将导致“多扩张”问题,本文提出了一种不完全知识下的交互式逻辑聚类方法,该方法在语言学上的应用已取得令人满意的效果。     

Process and Policy: Resource-Bounded NonDemonstrative Reasoning

This paper investigates the appropriateness of formal dialectics as a basis for nonmonotonic reasoning and defeasible reasoning that takes computational limits seriously. Rules that can come into conflict should be regarded as policies, which are inputs to deliberative processes. Dialectical protocols are appropriate for such deliberations when resources are bounded and search is serial.
AI, it is claimed here, is now perfectly positioned to correct many misconceptions about reasoning that have resulted from mathematical logic's enormous success in this century: among them, (1) that all reasons are demonstrative, (2) that rational belief is constrained, not constructed, and (3) that process and disputation are not essential to reasoning. AI mainly provides new impetus to formalize the alternative (but older) conception of reasoning, and AI provides mechanisms with which to create compelling formalism that describes the control of processes.
The technical contributions here are: the partial justification of dialectic based on controlling search; the observation that nonmonotonic reasoning can be subsumed under certain kinds of dialectics; the portrayal of inference in knowledge bases as policy reasoning; the review of logics of dialogue and proposed extensions; and the preformal and initial formal discussion of aspects and variations of dialectical systems with nondemonstrative reasons.     

Reusing JessTab rules in Protégé

Protégé provides a complete ontology and knowledge base management tool. Along with JESS, JessTab provides one method of rule-based reasoning over a Protégé ontology and knowledge base. However, once JessTab rules have been created for a knowledge base, they are explicitly tied to it as they name particular classes and slots, which greatly hinders their reuse with further knowledge bases. We have developed a two-phase process and a supporting tool to support the reuse of JessTab rule sets. The first phase involves changing the class and slot references in the rule set into an abstract reference; the second phase involves automatically mapping between the abstract rules and further knowledge bases. Once mappings have been defined and applied for all the classes and slots in the abstract rules, the new rule set can then be run against the new knowledge base. We have satisfactorily tested our tool with several ontologies and associated rule sets; moreover, some of these tests have identified possible future improvements to the tool.