Negative statements considered useful

Knowledge bases (KBs) about notable entities and their properties are an important asset in applications such as search, question answering and dialog. All popular KBs capture virtually only positive statements, and abstain from taking any stance on statements not stored in the KB. This paper makes the case for explicitly stating salient statements that do not hold. Negative statements are useful to overcome limitations of question answering systems that are mainly geared for positive questions; they can also contribute to informative summaries of entities. Due to the abundance of such invalid statements, any effort to compile them needs to address ranking by saliency. We present a statistical inference method for compiling and ranking negative statements, based on expectations from positive statements of related entities in peer groups. Experimental results, with a variety of datasets, show that the method can effectively discover notable negative statements, and extrinsic studies underline their usefulness for entity summarization. Datasets and code are released as resources for further research.     

Parallel belief revision: Revising by sets of formulas

The area of belief revision studies how a rational agent may incorporate new information about a domain into its belief corpus. An agent is characterised by a belief state K, and receives a new item of information α which is to be included among its set of beliefs. Revision then is a function from a belief state and a formula to a new belief state.We propose here a more general framework for belief revision, in which revision is a function from a belief state and a finite set of formulas to a new belief state. In particular, we distinguish revision by the set $\{\alpha ,\beta \}$ from the set $\{\alpha \wedge \beta \}$. This seemingly innocuous change has significant ramifications with respect to iterated belief revision. A problem in approaches to iterated belief revision is that, after first revising by a formula and then by a formula that is inconsistent with the first formula, all information in the original formula is lost.This problem is avoided here in that, in revising by a set of formulas S, the resulting belief state contains not just the information that members of S are believed to be true, but also the counterfactual supposition that if some members of S were later believed to be false, then the remaining members would nonetheless still be believed to be true. Thus if some members of S were in fact later believed to be false, then the other elements of S would still be believed to be true. Hence, we provide a more nuanced approach to belief revision. The general approach, which we call parallel belief revision, is independent of extant approaches to iterated revision. We present first a basic approach to parallel belief revision. Following this we combine the basic approach with an approach due to Jin and Thielscher for iterated revision. Postulates and semantic conditions characterising these approaches are given, and representation results provided. We conclude with a discussion of the possible ramifications of this approach in belief revision in general.     

Handling failing RDF queries: from diagnosis to relaxation

Recent years have witnessed the development of large knowledge bases (KBs). Due to the lack of information about the content and schema semantics of KBs, users are often not able to correctly formulate KB queries that return the intended result. In this paper, we consider the problem of failing RDF queries, i.e., queries that return an empty set of answers. Query relaxation is one cooperative technique proposed to solve this problem. In the context of RDF data, several works proposed query relaxation operators and ranking models for relaxed queries. But none of them tried to find the causes of an RDF query failure given by Minimal Failing Subqueries (MFSs) as well as successful queries that have a maximal number of triple patterns named Ma \(\underline{x}\) imal Succeeding Subqueries (XSSs). Inspired by previous work in the context of relational databases and recommender systems, we propose two complementary approaches to fill this gap. The lattice-based approach (LBA) leverages the theoretical properties of MFSs and XSSs to efficiently explore the subquery lattice of the failing query. The matrix-based approach computes a matrix that records alternative answers to the failing query with the triple patterns they satisfy. The skyline of this matrix directly gives the XSSs of the failing query. This matrix can also be used as an index to improve the performance of LBA. The practical interest of these two approaches are shown via a set of experiments conducted on the LUBM benchmark and a comparative study with baseline and related work algorithms.     

A general framework for measuring inconsistency through minimal inconsistent sets

Hunter and Konieczny explored the relationships between measures of inconsistency for a belief base and the minimal inconsistent subsets of that belief base in several of their papers. In particular, an inconsistency value termed MIV _C , defined from minimal inconsistent subsets, can be considered as a Shapley Inconsistency Value. Moreover, it can be axiomatized completely in terms of five simple axioms. MinInc, one of the five axioms, states that each minimal inconsistent set has the same amount of conflict. However, it conflicts with the intuition illustrated by the lottery paradox, which states that as the size of a minimal inconsistent belief base increases, the degree of inconsistency of that belief base becomes smaller. To address this, we present two kinds of revised inconsistency measures for a belief base from its minimal inconsistent subsets. Each of these measures considers the size of each minimal inconsistent subset as well as the number of minimal inconsistent subsets of a belief base. More specifically, we first present a vectorial measure to capture the inconsistency for a belief base, which is more discriminative than MIV _C . Then we present a family of weighted inconsistency measures based on the vectorial inconsistency measure, which allow us to capture the inconsistency for a belief base in terms of a single numerical value as usual. We also show that each of the two kinds of revised inconsistency measures can be considered as a particular Shapley Inconsistency Value, and can be axiomatically characterized by the corresponding revised axioms presented in this paper.     

On the completeness of the semigraphoid axioms for deriving arbitrary from saturated conditional independence statements

Conditional independence (CI) statements occur in several areas of computer science and artificial intelligence, e.g., as embedded multivalued dependencies in database theory, disjunctive association rules in data mining, and probabilistic CI statements in probability theory. Although, syntactically, such constraints can always be represented in the form I(A,B|C)$I(A,B|C)$, with A, B, and C subsets of some universe S, their semantics is very dependent on their interpretation, and, therefore, inference rules valid under one interpretation need not be valid under another. However, all aforementioned interpretations obey the so-called semigraphoid axioms. In this paper, we consider the restricted case of deriving arbitrary CI statements from so-called saturated ones, i.e., which involve all elements of S. Our main result is a necessary and sufficient condition under which the semigraphoid axioms are also complete for such derivations. Finally, we apply these results to the examples mentioned above to show that, for these semantics, the semigraphoid axioms are both sound and complete for the derivation of arbitrary CI statements from saturated ones.     

A Formal Model of Multi-Agent Belief-Interaction

A semantics is presented for belief revision in the face of common announcements to a group of agents that have beliefs about each other’s beliefs. The semantics is based on the idea that possible worlds can be viewed as having an internal-structure, representing the belief independent features of the world, and the respective belief states of the agents in a modular fashion. Modularity guarantees that changing one aspect of the world (a belief independent feature or a belief state) has no effect on any other aspect of the world. This allows us to employ an AGM-style selection function to represent revision. The semantics is given a complete axiomatisation (identical to the axiomatisation found by Gerbrandy and Groeneveld for a semantics based on non-wellfounded set theory) for the special case of expansion.     

Cross-domain probabilistic inference in a clinical decision support system: examples for dermatology and rheumatology

Introduction

Maintaining a large diagnostic knowledge base (KB) is a demanding task for any person or organization. Future clinical decision support system (CDSS) may rely on multiple, smaller and more focused KBs developed and maintained at different locations that work together seamlessly. A cross-domain inference tool has great clinical import and utility.

Methods

We developed a modified multi-membership Bayes formulation to facilitate the cross-domain probabilistic inferencing among KBs with overlapping diseases. Two KBs developed for evaluation were non-infectious generalized blistering diseases (GBD) and autoimmune diseases (AID). After the KBs were finalized, they were evaluated separately for validity.

Result

Ten cases from medical journal case reports were used to evaluate this “cross-domain” inference across the two KBs. The resultant non-error rate (NER) was 90%, and the average of probabilities assigned to the correct diagnosis (AVP) was 64.8% for cross-domain consultations.

Conclusion

A novel formulation is now available to deal with problems occurring in a clinical diagnostic decision support system with multi-domain KBs. The utilization of this formulation will help in the development of more integrated KBs with greater focused knowledge domains.     

Repertoire Contraction

The basic assumption of repertoire contraction is that only some of the logically closed subsets of the original belief set are viable as contraction outcomes. Contraction takes the form of choosing directly among these viable outcomes, rather than among cognitively more far-fetched objects such as possible worlds or maximal consistent subsets of the original belief set. In this first investigation of repertoire contraction, postulates for various variants of the operation are introduced. Necessary and sufficient conditions are given for when repertoire contraction coincides with AGM contraction or with operations generated by AGM-style contraction on a belief base. A close connection is shown to hold between repertoire contraction and specified meet contraction.     

Reasoning tractably about explicit belief: A model‐theoretic approach

Existing epistemic logics such as the logic of implicit and explicit belief and the logic of awareness adopt a deductive‐theoretic approach for characterizing belief. In this approach, an agent represents the state of the world with a conjunction of axioms in its knowledge base (KB) and evaluates queries by trying to prove or disprove that they follow from KB. This paper presents a multivalued epistemic logic (MEL) that allows agents to reason both deductively and model theoretically about implicit and explicit belief. By characterizing an agent's KB with a class of finite models, the set of formulas that an agent believes can be determined by checking their validity in all these models. This rests on the fact that MEL has a complete axiomatization (sentences that are true in all these models will also be provable). In this paper, the soundness, completeness, and decidability of MEL are proven. Furthermore, a polynomial time model‐checking algorithm for determining the satisfiability of a sentence at a particular state in a given model of MEL is also presented. © 2000 John Wiley & Sons, Inc.     

Towards specifying norms

A normative statement (or norm) is one whichshould hold orusually holds, as opposed to ordinary statements whichactually oralways hold. The need for normative statements in computer science specifications is described, and different kinds of norms that can occur in an action-based system are classified. A language and logic for expressing such norms is described, We show that it allows the specifier to reason about the system's behaviour even when it fails to satisfy the norms. The logic used is based on Modal Action Logic [6,4,7,11], and has two additions for expressing norms. The first of these additions is the use ofdeontic axioms. The second is the use of an ordering between axioms of a specification to stipulate priorities. Such orderings of axioms are calledordered theory presentations. We show that they arise naturally fromstructured specifications.The author acknowledges support of the British Science and Engineering Research Council on theForest project.     

A Formal Model of Multi-Agent Belief-Interaction

A semantics is presented for belief-revision in the face of common announcements to a group of agents that have beliefs about each other's beliefs. The semantics is based on the idea that possible worlds can be viewed as having an internal structure, representing the belief independent features of the world, and the respective belief states of the agents in a modular fashion. Modularity guarantees that changing one aspect of the world (a belief independent feature or a belief state) has no effect on any other aspect of the world. This allows us to employ an AGM-style selection function to represent revision. The semantics is given a complete axiomatisation (identical to the axiomatisation found by Gerbrandy and Groeneveld for a semantics based on non-wellfounded set theory) for the special case of expansion.     

信念修正的完全和可操作的方法

给出了命题逻辑上信念修正的两种可操作的完全方法.首先对R-演算的规则进行了修改,使得对任何一个极大协调的子集都通过这组规则得到.然后,给出了求得所有的极小不协调子集的一组规则.最后,给出一个过程,该过程能求得所有的极大协调子集.因为这两种方法都能求得所有的极大协调子集,所以把它们称为完全的.     

On the revision of probabilistic beliefs using uncertain evidence

We revisit the problem of revising probabilistic beliefs using uncertain evidence, and report results on several major issues relating to this problem: how should one specify uncertain evidence? How should one revise a probability distribution? How should one interpret informal evidential statements? Should, and do, iterated belief revisions commute? And what guarantees can be offered on the amount of belief change induced by a particular revision? Our discussion is focused on two main methods for probabilistic revision: Jeffrey's rule of probability kinematics and Pearl's method of virtual evidence, where we analyze and unify these methods from the perspective of the questions posed above.     

A sketch of a dynamic epistemic semiring

This paper proposes a semiring formulation for reasoning about an agent’s changing beliefs: a dynamic epistemic semiring (DES). A DES is a modal semiring extended with epistemic-action operators. The paper concentrates on the revision operator by proposing an axiomatisation, developing a basic calculus and deriving the classical AGM revision axioms in the algebra. Iterated action is also considered.     

A Collaborative Environment for Authoring Large Knowledge Bases

Collaborative knowledge base (KB) authoring environments are critical for the construction of high-performance KBs. Such environments must support rapid construction of KBs by a collaborative effort of teams of knowledge engineers through reuse of existing knowledge and software components. They should support the manipulation of knowledge by diverse problem-solving engines even if that knowledge is encoded in different languages and by different researchers. They should support large KBs and provide a scalable and interoperable development infrastructure. In this paper, we present an environment that satisfies many of these goals.We present an architecture for scalable frame representation systems (FRSs). The Generic Frame Protocol (GFP) provides infrastructure for reuse of software components. It is a procedural interface to frame representation systems that provides a common means of accessing and modifying frame KBs. The Generic KB Editor (GKB-EDITOR) provides graphical KB browsing, editing, and comprehension services for large KBs. Scalability of loading and saving time is provided by a storage system (PERK) which submerges a database management system in an FRS. Multi-user access is controlled through a collaboration subsystem that uses a novel optimistic concurrency control algorithm. All the results have been implemented and tested in the development of several real KBs.     

A Thorough Axiomatization of a Principle of Conditional Preservation in Belief Revision

Although the crucial role of if-then-conditionals for the dynamics of knowledge has been known for several decades, they do not seem to fit well in the framework of classical belief revision theory. In particular, the propositional paradigm of minimal change guiding the AGM-postulates of belief revision proved to be inadequate for preserving conditional beliefs under revision. In this paper, we present a thorough axiomatization of a principle of conditional preservation in a very general framework, considering the revision of epistemic states by sets of conditionals. This axiomatization is based on a nonstandard approach to conditionals, which focuses on their dynamic aspects, and uses the newly introduced notion of conditional valuation functions as representations of epistemic states. In this way, probabilistic revision as well as possibilistic revision and the revision of ranking functions can all be dealt with within one framework. Moreover, we show that our approach can also be applied in a merely qualitative environment, extending AGM-style revision to properly handling conditional beliefs.