Integrating forward-chaining rules with operations and permanent knowledge bases

Traditionally, rule-based forward-chaining systems are considered to be standalone, working on a volatile memory. This paper focuses on the integration of forward-chaining rules with command-driven programming paradigms in the context of permanent, integrated knowledge bases. A system architecture is proposed that integrates the data management functions of large computerized knowledge bases into a module called a knowledge base management system (KBMS). Experiences we had in integrating rules with operations into a prototype KBMS called DALI are surveyed. For this integration, a new form of production rule, called the activation pattern controlled rule, is introduced, which augments traditional forward-chaining rules by a second, additional left-hand side, which allows making rules sensitive to calls of particular operations. Activation pattern controlled rules play an important role in DALI's system architecture, because they facilitate the storage of knowledge that has been specified relying on mixed programming, a combination of data-driven, command-driven, and preventive programming. The general problems of implementing permanent knowledge bases that contain rules and operations are discussed, and an algorithm for implementating activation pattern controlled rules, called IPTREAT, a generalization of the TREAT algorithm, is provided. Furthermore, the paper intends to clarify the differences between traditional, volatile rule-based systems and rule-based systems that are geared toward knowledge integration by supporting a permanent knowledge base.This paper is an extended and significantly revised version of a paper entitled Integrating Rules into a Knowledge Base Management System, which was presented at the First International Conference on Systems Integration, April 1990 [1].     

Rule-based consistency enforcement for knowledge-based systems

A rule-based approach for the automatic enforcement of consistency constraints is presented. In contrast to existing approaches that compile consistency checks into application programs, the approach centralizes consistency enforcement in a separate module called a knowledge-base management system. Exception handlers for constraint violations are represented as rule entities in the knowledge base. For this purpose, a new form of production rule called the activation pattern controlled rule is introduced: in contrast to classical forward chaining schemes, activation pattern controlled rules are triggered by the intent to apply a specific operation but not necessarily by the result of applying this operation. Techniques for implementing this approach are discussed, and experiments in speeding up the system performance are described. Furthermore, an argument is made for more tolerant consistency enforcement strategies, and how they can be integrated into the rule-based approach to consistency enforcement is discussed     

R++: adding path-based rules to C++

Object-oriented languages and rule-based languages offer two distinct and useful programming abstractions. However, previous attempts to integrate data-driven rules into object-oriented languages have typically achieved an uneasy union at best. R++ is a new, closer integration of the rule-based and object-oriented paradigms that extends C++ with a single programming construct, the path-based rule, as a new kind of class member. Path-based rules-data-driven rules that are restricted to following pointers between objects-are like automatic methods that are triggered by changes to the objects they monitor. Path-based rules provide a useful level of abstraction that encourages a more declarative style of programming and are valuable in object-oriented designs as a means of modeling dynamic collections of interdependent objects. Unlike more traditional pattern-matching rules, path-based rules are not at odds with the object-oriented paradigm and offer performance advantages for many natural applications     

基于改进规则激活率的扩展置信规则库推理方法

数据驱动的扩展置信规则库系统,是在传统置信规则库的基础上利用关系数据来生成规则,使用该方法构建规则库简单有效。然而,该方法激活的规则存在不一致与不完整,并且该方法无法处理零激活的输入。鉴于此,本文提出基于改进规则激活率的扩展置信规则库方法,通过高斯核改进个体匹配度计算方法,权衡激活规则的一致性与完整性,并利用k近邻思想解决规则零激活问题。最后,本文选取非线性函数拟合实验和输油管道检漏实验来检验所提方法的效率和准确度。实验结果表明该方法既保证了扩展置信规则库系统的推理效率,也提高了推理结果的精度。     

Syllabification rules versus data-driven methods in a language with low syllabic complexity: The case of Italian

Linguistic rules have been assumed to be the best technique for determining the syllabification of unknown words. This has recently been challenged for the English language where data-driven algorithms have been shown to outperform rule-based methods. It may be possible, however, that data-driven methods are only better for languages with complex syllable structures. In this study, three rule-based automatic syllabification systems and two data-driven automatic syllabification systems (Syllabification by Analogy and the Look-Up Procedure) are compared on a language with lower syllabic complexity – Italian. Comparing the performance using a lexicon containing 44,720 words, the best data-driven algorithm (Syllabification by Analogy) achieved 97.70% word accuracy while the best rule set correctly syllabified 89.77% words. These results show that data-driven methods can also outperform rule-based methods on Italian syllabification, a language of low syllabic complexity.     

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.     

Self-stabilizing real-time OPS5 production systems

We examine the task of constructing bounded-time self-stabilizing rule-based systems that take their input from an external environment. Bounded response-time and self-stabilization are essential for rule-based programs that must be highly fault-tolerant and perform in a real-time environment. We present an approach for solving this problem using the OPS5 programming language as it is one of the most expressive and widely used rule-based programming languages. Bounded response-time of the program is ensured by constructing the state space graph so that the programmer can visualize the control flow of the program execution. Potential infinite firing sequences, if any, should be detected and the involved rules should be revised to ensure bounded termination. Both the input variables and internal variables are made fault-tolerant from corruption caused by transient faults via the introduction of new self-stabilizing rules in the program. Finally, the timing analysis of the self-stabilizing OPS5 program is shown in terms of the number of rule firings and the comparisons performed in the Rete network.     

Effect of rule weights in fuzzy rule-based classification systems

This paper examines the effect of rule weights in fuzzy rule-based classification systems. Each fuzzy IF-THEN rule in our classification system has antecedent linguistic values and a single consequent class. We use a fuzzy reasoning method based on a single winner rule in the classification phase. The winner rule for a new pattern is the fuzzy IF-THEN rule that has the maximum compatibility grade with the new pattern. When we use fuzzy IF-THEN rules with certainty grades, the winner is determined as the rule with the maximum product of the compatibility grade and the certainty grade. In this paper, the effect of rule weights is illustrated by drawing classification boundaries using fuzzy IF-THEN rules with/without certainty grades. It is also shown that certainty grades play an important role when a fuzzy rule-based classification system is a mixture of general rules and specific rules. Through computer simulations, we show that comprehensible fuzzy rule-based systems with high classification performance can be designed without modifying the membership functions of antecedent linguistic values when we use fuzzy IF-THEN rules with certainty grades     

A rule-based system for automatic seismic discrimination

This paper proposes a rule-based system for automatic seismic discrimination, i.e. classification of earthquakes and underground nuclear explosions. It incorporates rule-based deduction, pattern recognition and signal processing for an effective identification. The seismological knowledge and heuristics are represented by a set of production rules. Facts and assertions of the production rules are derived from seismic signals using signal processing and pattern recognition methods. Due to the uncertainty nature of this problem there are certainly factors associated with both antecedents and the rules. The control strategy is data-driven, i.e. forward-chaining for better efficiency. This approach can be applied to other signal and image interpretation problems.     

Maintaining data-driven rules in databases

A new model with invariant-based language effectively handles data-driven rules in databases and uses the rules' inherent semantic properties and supporting mechanisms to meet high-level language requirements. It is an extension of the basic PARDES model developed by Opher Etzion in 1990 to support derivations and integrity constraints in databases. The model's invariant-based language, unlike other programming languages, can follow data-driven rules' semantic properties. Such rules are activated by modifications of data items in a database, and they play an important role in many applications that maintain complex relationships between data items or interdependencies between parts of the database. Applications include expert systems, real-time databases, simulations, and decision-support systems. The authors present requirements for choosing an adequate programming style that uses data-driven rules. These requirements are based on software-engineering criteria such as compatibility with a high-level language and verifiability of the rule language. The authors show that contemporary database programming styles fail to meet these requirements, and they present the invariant-based language as a viable solution     

Playing with Maude

This paper is an introduction to rule-based programming in Maude. We illustrate in particular the use of operator attributes to structure the state of a system, and the difference between equations and rules. We use well-known mathematical games and puzzles for our examples illustrating the expressive power of Maude.     

Adaptive fuzzy rule-based classification systems

This paper proposes an adaptive method to construct a fuzzy rule-based classification system with high performance for pattern classification problems. The proposed method consists of two procedures: an error correction-based learning procedure, and an additional learning procedure. The error correction-based learning procedure adjusts the grade of certainty of each fuzzy rule by its classification performance. That is, when a pattern is misclassified by a particular fuzzy rule, the grade of certainty of that rule is decreased. On the contrary, when a pattern is correctly classified, the grade of certainty is increased. Because the error correction-based learning procedure is not meaningful after all the given patterns are correctly classified, we cannot adjust a classification boundary in such a case. To acquire a more intuitively acceptable boundary, we propose an additional learning procedure. We also propose a method for selecting significant fuzzy rules by pruning unnecessary fuzzy rules, which consists of the error correction-based learning procedure and the concept of forgetting. We can construct a compact fuzzy rule-based classification system with high performance     

Purely neural,rule-based diagnostic systems. I. Production rules

This is the first of two articles presenting an approach to rule-based expert systems for diagnostic tasks exploiting a purely neural architecture. Here, we outline the methodological options motivating this approach, and describe a forward and backward chaining mechanism on a system of production rules. This inference engine is furnished with an informative justification module, which exploits the fact that most individual neurons get a precise semantic assignment in terms of the literals appearing in production rules. the control and synchronization functions needed to schedule these processes are carried out by a neural network, too. © 1995 John Wiley & Sons, Inc.     

On rules with existential variables: Walking the decidability line

We consider positive rules in which the conclusion may contain existentially quantified variables, which makes reasoning tasks (such as conjunctive query answering or entailment) undecidable. These rules, called ??-rules, have the same logical form as tuple-generating dependencies in databases and as conceptual graph rules. The aim of this paper is to provide a clearer picture of the frontier between decidability and non-decidability of reasoning with these rules. Previous known decidable classes were based on forward chaining. On the one hand we extend these classes, on the other hand we introduce decidable classes based on backward chaining. A side result is the definition of a backward mechanism that takes the complex structure of ??-rule conclusions into account. We classify all known decidable classes by inclusion. Then, we study the question of whether the union of two decidable classes remains decidable and show that the answer is negative, except for one class and a still open case. This highlights the interest of studying interactions between rules. We give a constructive definition of dependencies between rules and widen the landscape of decidable classes with conditions on rule dependencies and a mixed forward/backward chaining mechanism. Finally, we integrate rules with equality and negative constraints to our framework.     

The Achievement of Knowledge Bases by Cycle Search

Forward chaining is an algorithm that is particularly simple and therefore used in many inference systems. It computes the facts that are implied by a set of facts and rules. Unfortunately, this algorithm is not complete with respect to negation. To solve this problem, it is possible, in the context of propositional calculus, to automatically add the rules needed to make forward chaining complete. This transformation is a logical compilation of knowledge bases. This article presents a new method, based on a cycle search in a graph associated to the set of rules to compile, which allows a precise identification of what is needed for completeness.     

Combining Aspect-Oriented and Strategic Programming

Properties such as logging, persistence, debugging, tracing, distribution, performance monitoring and exception handling occur in most programming paradigms and are normally very difficult or even impossible to modularize with traditional modularization mechanisms because they are cross-cutting. Recently, aspect-oriented programming has enjoyed recognition as a practical solution for separating these concerns. In this paper we describe an extension to the Stratego term rewriting language for capturing such properties. We show our aspect language offers a concise, practical and adaptable solution for dealing with unanticipated algorithm extension for forward data-flow propagation and dynamic type checking of terms. We briefly discuss some of the challenges faced when designing and implementing an aspect extension for and in a rule-based term rewriting system.     

Modular Structural Operational Semantics with Strategies

Strategies are a powerful mechanism to control rule application in rule-based systems. For instance, different transition relations can be defined and then combined by means of strategies, giving rise to an effective tool to define the semantics of programming languages. We have endowed the Maude MSOS Tool (MMT), an executable environment for modular structural operational semantics, with the possibility of defining strategies over its transition rules, by combining MMT with the Maude strategy language interpreter prototype. The combination was possible due to Maude's reflective capabilities. One possible use of MMT with strategies is to execute Ordered SOS specifications. We show how a particular form of strategy can be defined to represent an OSOS order and therefore execute, for instance, SOS specifications with negative premises. In this context, we also discuss how two known techniques for the representation of negative premises in OSOS become simplified in our setting.     

General purpose inference engine for canonical graph models

The design and implementation of a General Purpose Inference Engine for canonical graph models that is both flexible and efficient is addressed. Conventional inference techniques (e.g. forward chaining, backward chaining and mixed strategies) are described, and new modes of flexibility through the provision of inexact matching between data and assertions/rules are explained. In GPIE, scanning/searching of the rules in the rule base is restricted to a minimum during execution, but at the expense of compilation of the rule set prior to execution. The generality of the rule set is transparent to the inference engine, thereby permitting reasoning at various levels. This research demonstrates that a graph-based inference engine offering flexible control structures and inxact matching can complement intermediate notations, such as conceptual graphs, offering the expressive power of a rich knowledge representation formalism. The availability of an extendible graph processor for building appropriate canonical graph models presents the exciting prospect of a general purpose reasoning engine.