On the consistency of knowledge bases: the COVADIS system

It is currently thought in the knowledge-based systems (KBS) domain that sophisticated tools are necessary for helping an expert with the difficult task of knowledge acquisition. The problem of detecting inconsistencies is especially crucial. The risk of inconsistencies increases with the size of the knowledge base; for large knowledge bases, detecting inconsistencies "by hand" or even by a superficial survey of the knowledge base is impossible. Indeed, most inconsistencies are due to the interaction between several rules via often deep deductions. In this paper, we first state the problem and define our approach in the framework of classical logic. We then describe a complete method to prove the consistency (or the inconsistency) of knowledge bases that we have implemented in the COVADIS system.     

An actor model for rule-based systems

Our research originates from a study of the possibilities of integrating rules and objects in knowledge-based systems. In the present work, we are interested in the interactionist perspective of an object. The stepwise reasoning of a diagnostic expert system, possibly involving subgoaling and interactions with the environment, can be easily codified by means of production rules over proposition literals. This set of rules can be graphically represented in a network manner denoting the relations between the rules. The individual nodes in the network can be expressed by means of autonomous objects and their relations, interpreted as possible communications between them. The objects are given a structure and a proper behaviour and cooperate for performing logical reasoning by means of forward and backward chaining inference processes. Therefore, designing this system implies addressing several basic issues such as inter-object communications and their synchronization. The problem here is not necessarily to develop a great intelligence locally but to develop strong networks of good communicators. This approach belongs to the interactionist representation current, where objects are called actors. In principle, the actors may carry out computation in parallel and provide a conceptual foundation for massively concurrent object-oriented paradigms. From this point of view, a system allowing for the simultaneous investigation of several rules and premises in the forward or the backward chaining would be significantly more efficient.     

Convex optimization approach to identify fusion for multisensortarget tracking

We consider the problem of identity fusion for a multisensor target tracking system whereby the sensors generate reports on the target identities. Since sensor reports are typically fuzzy, incomplete, or inconsistent, the fusion of such sensor reports becomes a major challenge. In this paper, we introduce a new identity fusion method based on the minimization of inconsistencies among the sensor reports by using a convex quadratic programming formulation. In contrast to Dempster-Shafer's evidential reasoning approach which suffers from exponentially growing complexity, our approach is highly efficient (polynomial time solvable). Moreover, our approach can fuse sensor reports of the form more general than that allowed by the evidential reasoning theory. Simulation results show that our method generates reasonable fusion results which are similar to that obtained via the evidential reasoning theory     

Redundancy detection in semistructured case bases

With the dramatic proliferation of case-based reasoning systems in commercial applications, many case bases are now becoming legacy systems. They represent a significant portion of an organization's assets, but they are large and difficult to maintain. One of the contributing factors is that these case bases are often large and yet unstructured or semistructured; they are represented in natural language text. Adding to the complexity is the fact that the case bases are often authored and updated by different people from a variety of knowledge sources, making it highly likely for a case base to contain redundant and inconsistent knowledge. We present methods and a system for maintaining large and semistructured case bases. We focus on a difficult problem in case base maintenance: redundancy detection. This problem is particularly pervasive when one deals with a semistructured case base. We discuss an information retrieval-based algorithm and an implemented system for solving this problem. As the ability to contain the knowledge acquisition problem is of paramount importance, our method allows one to express relevant domain expertise for detecting redundancy naturally and effortlessly. Empirical evaluations of the system demonstrate the effectiveness of the methods in several large domains     

Abductive Knowledge Base Updates for Contextual Reasoning

We show in this paper how procedures that update knowledge bases can naturally be adapted to a number of problems related to contextual reasoning. The fact that the update procedures are abductive in nature is favourably exploited to tackle problems related to human-computer dialogue systems. We consider as examples aspects of pronoun resolution,goal formulation , and the problem of restoring the consistency of a knowledge base after some knowledge update is carried out. We state these problems in terms of the update problem and abductive reasoning and show how procedures that update knowledge bases yield some interesting results. We also explain how these procedures can naturally be used to model various forms of hypothetical reasoning such as hypothesizing inconsistencies and performing some look ahead form of reasoning.We do not claim thaT the problems presented here are solved entirely within the update framework. However, we believe that the flexibility of the representation and of the problem-solving approach suggest that the problems could be solved by adding more details about each problem. What is most interesting in our understanding is that all the aforementioned problems are expressed and tackled within the same framework.     

Distributed reasoning with ontologies and rules in order-sorted logic programming

Integrating ontologies and rules on the Semantic Web enables software agents to interoperate between them; however, this leads to two problems. First, reasoning services in SWRL (a combination of OWL and RuleML) are not decidable. Second, no studies have focused on distributed reasoning services for integrating ontologies and rules in multiple knowledge bases. In order to address these problems, we consider distributed reasoning services for ontologies and rules with decidable and effective computation. In this paper, we describe multiple order-sorted logic programming that transfers rigid properties from knowledge bases. Our order-sorted logic contains types (rigid sorts), non-rigid sorts, and unary predicates that distinctly express essential sorts, non-essential sorts, and non-sortal properties. We formalize the order-sorted Horn-clause calculus for such properties in a single knowledge base. This calculus is extended by embedding rigid-property derivation for multiple knowledge bases, each of which can transfer rigid-property information from other knowledge bases. In order to enable the reasoning to be effective and decidable, we design a query-answering system that combines order-sorted linear resolution and rigid-property resolution as top-down algorithms.     

Reasoning about reasoning in a meta-level architecture

In this paper we discuss reasoning about reasoning in a multiple agent scenario. We consider agents that are perfect reasoners, loyal, and that can take advantage of both the knowledge and ignorance of other agents. The knowledge representation formalism we use is (full) first order predicate calculus, where different agents are represented by different theories, and reasoning about reasoning is realized via a meta-level representation of knowledge and reasoning. The framework we provide is pretty general: we illustrate it by showing a machine checked solution to the three wisemen puzzle. The agents' knowledge is organized into units: the agent's own knowledge about the world and its knowledge about other agents are units containing object-level knowledge; a unit containing meta-level knowledge embodies the reasoning about reasoning and realizes the link among units. In the paper we illustrate the meta-level architecture we propose for problem solving in a multi-agent scenario; we discuss our approach in relation to the modal one and we compare it with other meta-level architectures based on logic. Finally, we look at a class of applications that can be effectively modeled by exploiting the meta-level approach to reasoning about knowledge and reasoning.     

Computer based support of reasoning in the presence of fuzziness

Many important problems encountered in managerial decision making are unstructured, making them difficult to solve by preset algorithms. Much of the complexity of such problems is due to the reasoning that is needed to construct solution procedures for each problem instance. Thus, any Decision Support System (DSS) designed for such problems should support this reasoning activity, in addition to data access and computational activities. Yet, existing DSS generally do not provide much reasoning support. One of the difficulties faced in building automated systems to support such reasoning is that much of the knowledge typically available for unstructured problems is imprecise, where imprecision may be caused by either fuzziness, uncertainty, or both. In this paper, we address the problem of supporting problem solving with fuzzy knowledge. We develop a formal method for representing fuzzy knowledge, using a framework of mathematical logic. Using this method, fuzziness in all the major constructs needed to describe knowledge can be represented. Relationships can be constructed using fuzzy operators and terms, and components in relationships can be weighted by their relative significance. Also, computational procedures and data access procedures can be directly integrated into the reasoning process. Knowledge thus represented can be manipulated using suitable reasoning mechanisms. The fuzzy inference methods we present, enable the generation of acceptable solutions to problems even when some of the knowledge used is highly imprecise and/or incomplete. Other desirable features, such as explanation of solution procedures and user participation in problem solving, are also supported by our methodology. In addition, we develop bounding procedures, which convey the imprecision in the reasoning process, and also help to reduce the complexity of the search process by pruning poor solutions. Finally, we describe a prototype system which implements the methods developed in this paper. Using example problems processed by the system, we illustrate the versatility of these methods, and also highlight their major features and potential utility in practical applications.     

Knowledge spaces with graded knowledge states

Knowledge spaces represent a framework for assessment of knowledge with solid theoretical foundations, methodology, software tools, and practical applications. The underlying assumption in knowledge spaces is that a knowledge state of an individual is represented by a set of items which the individual has mastered. In this paper, we propose an extension of the theory of knowledge spaces which accounts for gradedness of knowledge states. Namely, we assume that a knowledge state is represented by a fuzzy (graded) set with degrees representing levels to which an individual has mastered the items. If 0 and 1 are the only degrees, our approach coincides with that of ordinary knowledge spaces. We develop basic concepts and results in the graded setting including bases of graded knowledge states and their computation and a logic of partial failure with its completeness theorem. We also present an illustrative example. The main aim of this paper is to demonstrate mathematical and computational feasibility of knowledge spaces with graded knowledge states.     

A general framework for time-aware decision support systems

In this paper we present a general framework for time-aware decision support systems. The framework uses the state-of-the-art tOWL language for the representation of temporal knowledge and enables temporal reasoning over the information that is represented in a knowledge base. Our approach uses state-of-the-art Semantic Web technology for handling temporal data. Through such an approach, the designer of a system can focus on the application intelligence rather than enforcing/checking data related restrictions manually. Also, there is an increased support for reuse of temporal reasoning tools across applications. We illustrate the applicability of our framework by building a market recommendations aggregation system. This system automatically collects market recommendations from online sources and, based on the past performance of the analysts that issued a recommendation, generates an aggregated recommendation in the form of a buy, hold, or sell advice. We illustrate the flexibility of our proposed system by implementing multiple methods for the aggregation of market recommendations.     

基于表示学习的开放域中文知识推理

知识库通常以网络的形式被组织起来,网络中每个节点代表实体,而每条连边则代表实体间的关系。为了利用这种网状知识库中的知识,往往需要设计专门的、复杂度较高的图算法。然而这些算法并不能很好适用于知识推理,尤其是随着知识库的知识规模不断扩大,基于网状结构知识库的推理很难较好地满足实时计算的需求。该文使用基于TransE模型的知识表示学习进行知识推理,包括对实体关系三元组中关系指示词以及尾实体的推理,其中关系指示词推理的实验取得了较好的结果,且推理过程无需设计复杂的算法,仅涉及向量的简单运算。另外,该文对原始TransE模型的代价函数进行改进,以更好地适用于开放域中文知识库表示学习。     

A NEW APPROACH FOR THE INCREMENTAL DEVELOPMENT OF RETRIEVAL FUNCTIONS FOR CBR

We present a new approach to the effective development of complex retrieval components for case-based reasoning systems (CBR). Our approach goes beyond the traditional CBR approach by allowing an incremental refinement of an existing retrieval knowledge base during routine use of the system. The refinement takes place through a direct expert-system interaction while the expert is accomplishing their given tasks. We lend ideas from ripple-down rules (RDR), a proven method for the very effective and efficient acquisition of classification knowledge during the routine use of a knowledge-based system (KBS).

In our approach the expert is only required to provide explanations of why, for a given problem, a certain case should be retrieved. Incrementally a complex retrieval knowledge base as a composition of many simple retrieval functions is developed. This approach is effective with respect to both the development of highly tailored and complex retrieval knowledge bases for CBR as well as providing an intuitive and feasible approach for the expert. The approach has been implemented in our CBR system MIKAS (Menu construction using an Incremental Knowledge Acquisition System) that allows to automatically construct a menu that is strongly tailored to the individual requirements and food preferences of a client.     

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.     

Hierarchical representation of problem-solving knowledge in a frame-based process planning system

In most frame-based reasoning systems, the information being manipulated is represetned using frames, but the problem-solving knowledge that manipulates the frames is represented as production rules. One problem with this approach is that rules are not always a natrual way to represent knowledge; another is that systems containing lots of rules may suffer from problems with “exponetial blowup” in the amount of computation required. This paper describes a way to address these problems by organizing the problem-solving knowledge not as rules, but in a particular kind of frame hierarchy. the approach described in this paper has been implemented in a problem-solving system called SIPP (Semi-Intelligent Process Planner), which produces plans of action for the manufacture of metal parts. the paper gives an overview of SIPP, compares its knowledge representation and problem solving methods to approaches used in other knowledge-based systems, and describes goals for further research.     

Semantic forgetting in answer set programming

The notion of forgetting, also known as variable elimination, has been investigated extensively in the context of classical logic, but less so in (nonmonotonic) logic programming and nonmonotonic reasoning. The few approaches that exist are based on syntactic modifications of a program at hand. In this paper, we establish a declarative theory of forgetting for disjunctive logic programs under answer set semantics that is fully based on semantic grounds. The suitability of this theory is justified by a number of desirable properties. In particular, one of our results shows that our notion of forgetting can be entirely captured by classical forgetting. We present several algorithms for computing a representation of the result of forgetting, and provide a characterization of the computational complexity of reasoning from a logic program under forgetting. As applications of our approach, we present a fairly general framework for resolving conflicts in inconsistent knowledge bases that are represented by disjunctive logic programs, and we show how the semantics of inheritance logic programs and update logic programs from the literature can be characterized through forgetting. The basic idea of the conflict resolution framework is to weaken the preferences of each agent by forgetting certain knowledge that causes inconsistency. In particular, we show how to use the notion of forgetting to provide an elegant solution for preference elicitation in disjunctive logic programming.     

On case-based learnability of languages

Case-based reasoning is deemed an important technology to alleviate the bottleneck of knowledge acquisition in Artificial Intelligence (AI). In case-based reasoning, knowledge is represented in the form of particular cases with an appropriate similarity measure rather than any form of rules. The case-based reasoning paradigm adopts the view that an Al system is dynamically changing during its life-cycle which immediately leads to learning considerations. Within the present paper, we investigate the problem of case-based learning of indexable classes of formal languages. Prior to learning considerations, we study the problem of case-based representability and show that every indexable class is case-based representable with respect to a fixed similarity measure. Next, we investigate several models of case-based learning and systematically analyze their strengths as well as their limitations. Finally, the general approach to case-based learnability of indexable classes of formal languages is prototypically applied to so-called containmet decision lists, since they seem particularly tailored to case-based knowledge processing.