基于Spark的大规模语义规则后向链推理系统

近年来,语义网数据快速增长,适合于处理静态小规模语义数据的前向链语义推理技术暴露出了需对数据进行频繁更新等问题。面对大规模动态语义网数据,对数据更新不敏感的后向链语义推理开始成为新的研究热点。后向链语义推理由查询目标驱动,在查询时根据规则集推理出查询结果。后向链语义推理具有推理过程复杂、规则扩展深度大等特点,在大规模语义数据上推理的效率和可扩展性上有一定的挑战。该文立足于已有的后向链推理技术,详细分析了语义推理规则集的特点,并结合当前主流的大数据处理平台Spark,设计了一套较为高效并且可扩展的大规模并行化语义规则后向链推理系统。该文的主要研究工作分为三个部分: (1)采用预计算本体数据闭包的方法,避免了本体模式在实时推理阶段的重复推理; (2)在后向链语义推理的逆向推理和查询阶段设计了优化措施,进一步提高了推理效率; (3)设计实现了一种基于Spark平台的大规模分布式RDFS/OWL后向链语义推理系统。实验数据显示,该文提出的RDFS/OWL后向链语义推理系统在合成数据集LUBM和真实数据集DBpedia上都表现出了良好的推理性能,在亿条三元组上的推理开销是几秒到几十秒,并且表现出了良好的数据可扩展性和节点可扩展性。     

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.     

Fuzzy cognitive maps

Fuzzy cognitive maps (FCMs) are fuzzy-graph structures for representing causal reasoning. Their fuzziness allows hazy degrees of causality between hazy causal objects (concepts). Their graph structure allows systematic causal propagation, in particular forward and backward chaining, and it allows knowledge bases to be grown by connecting different FCMs. FCMs are especially applicable to soft knowledge domains and several example FCMs are given. Causality is represented as a fuzzy relation on causal concepts. A fuzzy causal algebra for governing causal propagation on FCMs is developed. FCM matrix representation and matrix operations are presented in the Appendix.     

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.     

Qualitative reasoning based on fuzzy relative orders of magnitude

This paper proposes a fuzzy set-based approach for handling relative orders of magnitude stated in terms of closeness and negligibility relations. At the semantic level, these relations are represented by means of fuzzy relations controlled by tolerance parameters. A set of sound inference rules, involving the tolerance parameters, is provided, in full accordance with the combination/projection principle underlying the approximate reasoning method of Zadeh. These rules ensure a local propagation of fuzzy closeness and negligibility relations. A numerical semantics is then attached to the symbolic computation process. Required properties of the tolerance parameter are investigated, in order to preserve the validity of the produced conclusions. The effect of the chaining of rules in the inference process can be controlled through the gradual deterioration of closeness and negligibility relations involved in the produced conclusions. Finally, qualitative reasoning based on fuzzy closeness and negligibility relations is used for simplifying equations and solving them in an approximate way, as often done by engineers who reason about a mathematical model. The problem of handling qualitative probabilities in reasoning under uncertainty is also investigated in this perspective.     

基于医疗智能诊断混合算法的推理机设计

根据医学专家对疾病诊断的思维特点,通过对医疗智能诊断推理机的设计与实现方法的探讨,提出了一种利用正、反向推理相结合的方式对疾病进行初步诊断和鉴别诊断的推理策略。     

Using mixed-type reasoning in computer-aided process planning for feature interactions

This paper describes a process-planning model using mixed-type reasoning designed for processing prismatic parts on CNC machine tools in a batch manufacturing environment. This mixed-type reasoning handles feature interactions by combining forward chaining for feature sequencing and backward chaining for the construction of a process plan. In such a model, the human problem-solving strategies are decoupled from the tools for analysis and sorting algorithms. Two databases are used to contain the results from forward and backward chaining. The process-planning algorithm combines the processes of modeling the given information in four stages: (1) defining the important information for features and feature-related concerns; (2) interpreting and rearranging the given feature according to the given constraints and sorting guideline; (3) sequencing the features; (4) attaching the needed operations to the features in machine/process/feature/set-up/tool/time/cost format.     

A connectionist inference model for pattern-directed knowledge representation

In this paper we propose a connectionist model for variable binding. The model is topology dependent on the graph it builds based on the predicates available. The irregular connections between perceptron-like assemblies facilitate forward and backward chaining. The model treats the symbolic data as a sequence and represents the training set as a partially connected network using basic set and graph theory to form the internal representation. Inference is achieved by opportunistic reasoning via the bidirectional connections. Consequently, such activity stabilizes to a multigraph. This multigraph is composed of isomorphic subgraphs which all represent solutions to the query made. Such a model has a number of advantages over other methods in that irrelevant connections are avoided by superimposing positionally dependent sub-structures that are identical, variable binding can be encoded and multiple solutions can be extracted simultaneously. The model also has the ability to adapt its existing architecture when presented with new clauses and therefore add new relationships/rules to the model explicitly; this is done by some partial retraining of the network due to the superimposition properties.     

Fuzzy backward reasoning using fuzzy Petri nets

Chen, Ke and Chang (1990) have presented a fuzzy forward reasoning algorithm for rule-based systems using fuzzy Petri nets. In this paper, we extend the work of Chen, Ke and Chang (1990) to present a fuzzy backward reasoning algorithm for rule-based systems using fuzzy Petri nets, where the fuzzy production rules of a rule-based system are represented by fuzzy Petri nets. The system can perform fuzzy backward reasoning automatically to evaluate the degree of truth of any proposition specified by the user. The fuzzy backward reasoning capability allows the computers to perform reasoning in a more flexible manner and to think more like people.     

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.     

An expert system for aided design of ship systems automation

The paper presents a structure and functions of an expert system for aided design of ship systems automation. The system was developed on basis of a detailed analysis of the design process of ship systems automation. The system includes: knowledge bases regarding methods and procedures of ship systems automation design, databases of automated objects, control devices and elements, requirements of classification societies, and a subsystem for simulation investigations co-operating with the Matlab Simulink package and a knowledge base. In the creation of the system the shell expert system Exsys Developer was used. This system is characterised by a rule-oriented representation of knowledge, backward and forward chaining inference methods, various confidence modes to handle uncertain reasoning including fuzzy logic, and possibility of co-operation with other software and databases. The databases were made using the MS Access software.     

A Reasoning System of Ternary Projective Relations

This paper introduces a reasoning system based on a previously developed model for ternary projective relations between spatial objects. The model applies to spatial objects of the kind point and region is based on basic projective invariants and takes into account the size and shape of the three objects that are involved in a relation. The reasoning system proposes a set of permutation and composition rules, which allow the inference of unknown relations from given ones.     

Fuzzy arithmetic-based interpolative reasoning for nonlinear dynamic fuzzy systems

FAIR (fuzzy arithmetic-based interpolative reasoning)—a fuzzy reasoning scheme based on fuzzy arithmetic, is presented here. Linguistic rules of the Mamdani type, with fuzzy numbers as consequents, are used in an inference mechanism similar to that of a Takagi–Sugeno model. The inference result is a weighted sum of fuzzy numbers, calculated by means of the extension principle. Both fuzzy and crisp inputs and outputs can be used, and the chaining of rule bases is supported without increasing the spread of the output fuzzy sets in each step. This provides a setting for modeling dynamic fuzzy systems using fuzzy recursion. The matching in the rule antecedents is done by means of a compatibility measure that can be selected to suit the application at hand. Different compatibility measures can be used for different antecedent variables, and reasoning with sparse rule bases is supported. The application of FAIR to the modeling of a nonlinear dynamic system based on a combination of knowledge-driven and data-driven approaches is presented as an example.     

推理过程的可视化研究

文章利用可视化技术,选择L系统为规则库的形式描述,实现推理的可视化。在知识表示方面,采用图形化的方法—逻辑演绎图,并将可视化因子加入规则。而在反向推理中,采用了模糊推理路径。最后用面向对象的方法实现。     

An inference network for bidirectional approximate reasoning basedon an equality measure

An inference network is proposed as a tool for bidirectional approximate reasoning. The inference network can be designed directly from the given fuzzy data (knowledge). If a fuzzy input is given for the inference network, then the network renders a reasonable fuzzy output after performing approximate reasoning based on an equality measure. Conversely, due to the bidirectional structure, the network can yield its corresponding reasonable fuzzy input for a given fuzzy output. This property makes it possible to perform forward and backward reasoning in the knowledge base system     

An example of expert system on numerical modelling system in coastal processes

With the advent of artificial intelligence technology as well as the widespread popularity of desktop microcomputers in recent years, integration of this new technology with the traditional numerical modelling system becomes a current trend in order to solve various engineering problems. It renders a more intelligent and user-friendly system on the problem domain. In this paper, a knowledge-based expert system on numerical modelling system for coastal water processes is delineated. Expert system application, as a key branch of artificial intelligence technology, is integrated with traditional numerical modelling for simulating flow and water quality phenomenon in coastal waters. The knowledge bases are classified into five major types, namely, a variety of models, relations between various model parameters and real physical conditions, feasible options of model parameters, question base as a user-interface directing the user to depict the actual physical conditions, and the rules of inference deducing the feasible choice of model and its parameters. A hybrid expert system shell, Visual Rule Studio, is employed as an ActiveX Designer under Microsoft Visual Basic environment because it combines the advantages of both production rules and object-oriented programming technology. Both forward chaining and backward chaining are used collectively during the inference process, which is mainly driven by premises and conditions with the highest factors of confidence. The inference engine will drive the decision tree to explore the most probable option of numerical model and parameters matching the real problem specifications. It is shown that the application and integration of the knowledge-based expert system technology into numerical modelling for coastal processes can provide substantial assistance to novice users for selection of numerical model as well as parameters.     

Detection of potential inconsistencies in knowledge bases

We present a new computational approach to the problem of detection of potential inconsistencies in knowledge bases. For such inconsistencies, we characterize the sets of possible input facts that will allow the knowledge based system to derive the contradiction. the state-of-the-art approach to a solution of this problem is represented by the COVADIS system which checks simple rule bases. the COVADIS approach relies on forward chaining and is strongly related to the way ATMS computes labels for deducible facts. Here, we present an alternative computation method that employs backward chaining in a kind of abductive reasoning. This approach gives a more focused reasoning, thus requiring much less computation and memory than COVADIS. Further, since our method is very similar to SLD-resolution, it is suitable for handling the more powerful knowledge base form represented by Horn claause bases. Finally, our method is easily extended to uncertain knowledge bases, assuming that the uncertainty calculus is modeled by possibilistic logic. This extension allows us to model the effect of user defined belief thresholds for inference chains.     

Interval-valued fuzzy backward reasoning

The importance and efficiency of backward reasoning in nonfuzzy reasoning has been stressed for a long time, especially in the case of expert systems and decision-support systems. The extension of this reasoning method to fuzzy theory, however, has never been considered. In this paper, the authors propose a definition of fuzzy backward reasoning based on the generalized modus ponens and show the necessity of considering interval-valued fuzzy backward reasoning. Then, the authors propose solving methods for fuzzy backward reasoning in the case of a rule with one or several conditions as well as in the case of several rules     

Automated generation of readable proofs with geometric invariants

We present a set of rules based on full-angles as the basis of automated geometry theorem proving. We extend the idea of eliminating variables and points to the idea of eliminating lines. We also discuss how to combine the forward chaining and backward chaining to achieve higher efficiency. The prover based on the full-angle method has been used to produce short and elegant proofs for more than one hundred difficult geometry theorems. The proofs of many of those theorems produced by our previous area method are relatively long.This work was supported in part by the NSF Grants CCR-9117870, CCR-9420857 and the Chinese NSF.