Spatial reasoning in a fuzzy region connection calculus

Although the region connection calculus (RCC) offers an appealing framework for modelling topological relations, its application in real-world scenarios is hampered when spatial phenomena are affected by vagueness. To cope with this, we present a generalization of the RCC based on fuzzy set theory, and discuss how reasoning tasks such as satisfiability and entailment checking can be cast into linear programming problems. We furthermore reveal that reasoning in our fuzzy RCC is NP-complete, thus preserving the computational complexity of reasoning in the RCC, and we identify an important tractable subfragment. Moreover, we show how reasoning tasks in our fuzzy RCC can also be reduced to reasoning tasks in the original RCC. While this link with the RCC could be exploited in practical reasoning algorithms, we mainly focus on the theoretical consequences. In particular, using this link we establish a close relationship with the Egg-Yolk calculus, and we demonstrate that satisfiable knowledge bases can be realized by fuzzy regions in any dimension.     

Attribute dependencies for data with grades I*,†

This paper examines attribute dependencies in data that involve grades, such as a grade to which an object is red or a grade to which two objects are similar. We thus extend the classical agenda by allowing graded, or “fuzzy”, attributes instead of Boolean, yes-or-no attributes in case of attribute implications, and allowing approximate match based on degrees of similarity instead of exact match based on equality in case of functional dependencies. In a sense, we move from bivalence, inherently present in the now-available theories of dependencies, to a more flexible setting that involves grades. Such a shift has far-reaching consequences. We argue that a reasonable theory of dependencies may be developed by making use of mathematical fuzzy logic, a recently developed many-valued logic. Namely, the theory of dependencies is then based on a solid logic calculus the same way classical dependencies are based on classical logic. For instance, rather than handling degrees of similarity in an ad hoc manner, we consistently treat them as truth values, the same way as true (match) and false (mismatch) are treated in classical theories. In addition, several notions intuitively embraced in the presence of grades, such as a degree of validity of a particular dependence or a degree of entailment, naturally emerge and receive a conceptually clean treatment in the presented approach. In the first part of this two-part paper, we discuss motivations, provide basic notions of syntax and semantics and develop basic results which include entailment of dependencies, associated closure structures and a logic of dependencies with two versions of completeness theorem.     

Inverse subsumption for complete explanatory induction

Modern explanatory inductive logic programming methods like Progol, Residue procedure, CF-induction, HAIL and Imparo use the principle of inverse entailment (IE). Those IE-based methods commonly compute a hypothesis in two steps: by first constructing an intermediate theory and next by generalizing its negation into the hypothesis with the inverse of the entailment relation. Inverse entailment ensures the completeness of generalization. On the other hand, it imposes many non-deterministic generalization operators that cause the search space to be very large. For this reason, most of those methods use the inverse relation of subsumption, instead of entailment. However, it is not clear how this logical reduction affects the completeness of generalization. In this paper, we investigate whether or not inverse subsumption can be embedded in a complete induction procedure; and if it can, how it is to be realized. Our main result is a new form of inverse subsumption that ensures the completeness of generalization. Consequently, inverse entailment can be reduced to inverse subsumption without losing the completeness for finding hypotheses in explanatory induction.     

面向行动的信念更新

基于可能模型方法 ( possible m odel approach,简称 PMA) ,提出了面向行动的信念更新的概念 ,证明了在信息完备的情境演算系统中 ,一个一阶公式在情境 s下成立当且仅当它属于情境 s下的信念集 .这一结果为有效避免情境演算推理中二阶归纳公理的使用提供了一条可行的途径 ,也为基于意向驱动的 agent模型的建立以及面向 agent的程序设计语言 AOPL ID( agent-oriented programm ing language with intention driver)的提出提供了必要的理论基础.     

文本蕴涵的推理模型与识别模型

该文首先介绍一个逼近文本蕴涵关系的推理模型,它由带有推理规则集的蕴涵型式知识库和相关的概率评价构成。接着介绍习得推理规则和蕴涵型式及其概率的几种方法,包括从平行或单一语料库中学习和从网络文件中学习。然后介绍基于词汇概率的蕴涵识别模型,包括通过构建词汇蕴涵的概率模型和基于词汇所指的语义匹配模型来逼近文本蕴涵的几种方法。最后介绍基于句法的语义分析模型,包括基于依存树节点匹配、论元结构或原子命题匹配等处理模型。     

Probabilistic Default Reasoning with Conditional Constraints

We present an approach to reasoning from statistical and subjective knowledge, which is based on a combination of probabilistic reasoning from conditional constraints with approaches to default reasoning from conditional knowledge bases. More precisely, we introduce the notions of z-, lexicographic, and conditional entailment for conditional constraints, which are probabilistic generalizations of Pearl's entailment in system Z, Lehmann's lexicographic entailment, and Geffner's conditional entailment, respectively. We show that the new formalisms have nice properties. In particular, they show a similar behavior as reference-class reasoning in a number of uncontroversial examples. The new formalisms, however, also avoid many drawbacks of reference-class reasoning. More precisely, they can handle complex scenarios and even purely probabilistic subjective knowledge as input. Moreover, conclusions are drawn in a global way from all the available knowledge as a whole. We then show that the new formalisms also have nice general nonmonotonic properties. In detail, the new notions of z-, lexicographic, and conditional entailment have similar properties as their classical counterparts. In particular, they all satisfy the rationality postulates proposed by Kraus, Lehmann, and Magidor, and they have some general irrelevance and direct inference properties. Moreover, the new notions of z- and lexicographic entailment satisfy the property of rational monotonicity. Furthermore, the new notions of z-, lexicographic, and conditional entailment are proper generalizations of both their classical counterparts and the classical notion of logical entailment for conditional constraints. Finally, we provide algorithms for reasoning under the new formalisms, and we analyze its computational complexity.     

中文文本蕴含类型及语块识别方法研究

文本蕴含识别（RTE）是判断两个句子语义是否具有蕴含关系的任务.近年来英文蕴含识别研究取得了较大发展,但主要是以类型判断为主,在数据中精确定位蕴含语块的研究比较少,蕴含类型识别的解释性较低.从中文文本蕴含识别（CNLI）数据中挑选12 000个中文蕴含句对,人工标注引起蕴含现象的语块,结合语块的语言学特征分析归纳了7种具体的蕴含类型.在此基础上,将中文蕴含识别任务转化为7分类的蕴含类型识别和蕴含语块边界-类型识别任务,在深度学习模型上达到69.19%和62.09%的准确率.实验结果表明,所提出的方法可以有效发现中文蕴含语块边界及与之对应的蕴含类型,为下一步研究提供了可靠的基准方法.     

Non-structural subtype entailment in automata theory

Decidability of non-structural subtype entailment is a long-standing open problem in programming language theory. In this paper, we apply automata theoretic methods to characterize the problem equivalently by using regular expressions and word equations. This characterization induces new results on non-structural subtype entailment, constitutes a promising starting point for further investigations on decidability, and explains for the first time why the problem is so difficult. The difficulty is caused by implicit word equations that we make explicit.     

基于语义规则的中文矛盾关系识别方法

文本蕴涵是文本理解与语义推理的基础,近来在计算机语言领域受到了极大关注。矛盾关系是蕴涵关系的一种否定,二者都是语义学的主要研究内容。在文本蕴涵关系识别的基础之上,研究了如何识别文本矛盾关系,提出了一种基于语义规则的矛盾检测方法。实验表明,基于语义规则的矛盾检测方法对于中文矛盾关系识别是可行的,同时矛盾关系相对精确的识别也增强了文本蕴涵识别的准确性。