Probabilistic logic under coherence: complexity and algorithms

In previous work [V. Biazzo, A. Gilio, T. Lukasiewicz and G. Sanfilippo, Probabilistic logic under coherence, model-theoretic probabilistic logic, and default reasoning in System P, Journal of Applied Non-Classical Logics 12(2) (2002) 189–213.], we have explored the relationship between probabilistic reasoning under coherence and model-theoretic probabilistic reasoning. In particular, we have shown that the notions of g-coherence and of g-coherent entailment in probabilistic reasoning under coherence can be expressed by combining notions in model-theoretic probabilistic reasoning with concepts from default reasoning. In this paper, we continue this line of research. Based on the above semantic results, we draw a precise picture of the computational complexity of probabilistic reasoning under coherence. Moreover, we introduce transformations for probabilistic reasoning under coherence, which reduce an instance of deciding g-coherence or of computing tight intervals under g-coherent entailment to a smaller problem instance, and which can be done very efficiently. Furthermore, we present new algorithms for deciding g-coherence and for computing tight intervals under g-coherent entailment, which reformulate previous algorithms using terminology from default reasoning. They are based on reductions to standard problems in model-theoretic probabilistic reasoning, which in turn can be reduced to linear optimization problems. Hence, efficient techniques for model-theoretic probabilistic reasoning can immediately be applied for probabilistic reasoning under coherence (for example, column generation techniques). We describe several such techniques, which transform problem instances in model-theoretic probabilistic reasoning into smaller problem instances. We also describe a technique for obtaining a reduced set of variables for the associated linear optimization problems in the conjunctive case, and give new characterizations of this reduced set as a set of non-decomposable variables, and using the concept of random gain. This paper is a substantially extended and revised version of a preliminary paper that appeared in: Proceedings of the Second International Symposium on Imprecise Probabilities and Their Applications (ISIPTA '01), pp. 51–61, 2001.     

Probabilistic Reasoning Under Coherence in System P

In this paper we apply a probabilistic reasoning under coherence to System P. We consider a notion of strict probabilistic consistency, we show its equivalence to Adams' probabilistic consistency, and we give a necessary and sufficient condition for probabilistic entailment. We consider the inference rules of System P in the framework of coherent imprecise probabilistic assessments. Exploiting our coherence-based approach, we propagate the lower and upper probability bounds associated with the conditional assertions of a given knowledge base, obtaining the precise probability bounds for the derived conclusions of the inference rules. This allows a more flexible and realistic use of System P in default reasoning and provides an exact illustration of the degradation of the inference rules when interpreted in probabilistic terms. We also examine the disjunctive Weak Rational Monotony rule of System P⁺ proposed by Adams in his extended probabilistic logic. Finally, we examine the propagation of lower bounds with real -values and, to illustrate our probabilistic reasoning, we consider an example.     

New tractable classes for default reasoning from conditional knowledge bases

This paper refines the tractability/intractability frontier of default reasoning from conditional knowledge bases. It presents two new tractable cases with relation to lexicographic entailment. In particular, we have introduced nested conditional knowledge bases and co-nested conditional knowledge bases, which are meaningful conditional knowledge bases. Both tractable classes presented in this paper can be recognized in linear time.     

COMPSPEN:对形状性质与数据约束进行融合推理的分离逻辑求解器

分离逻辑是经典霍尔逻辑的针对操作指针和动态数据结构的扩展,已经广泛用于对基础软件(比如操作系统内核等)的分析与验证.分离逻辑约束自动求解是提升对操作指针和动态数据结构的程序的验证的自动化程度的重要手段.针对动态数据结构的验证一般同时涉及形状性质(比如单链表、双链表、树等)和数据性质(比如有序性、数据不变性等).主要介绍能对动态数据结构的形状性质与数据约束进行融合推理的分离逻辑求解器COMPSPEN.首先介绍COMPSPEN的理论基础,包括能够同时描述线性动态数据结构的形状性质和数据约束的分离逻辑子集SLID_data、SLID_data的可满足性和蕴涵问题的判定算法.然后,介绍COMPSPEN工具的基本框架.最后,使用COMPSPEN工具进行了实例研究.收集整理了600个测试用例,在这600个测试用例上将COMPSPEN与已有的主流分离逻辑求解器Asterix、S2S、Songbird、SPEN进行了比较.实验结果表明COMPSPEN是唯一能够求解含有集合数据约束的分离逻辑求解器,而且总体来讲,能对线性数据结构上的同时含有形状性质和线性算术数据约...     

Robust reasoning with rules that have exceptions: From second-order probability to argumentation via upper envelopes of probability and possibility plus directed graphs

Rules having rare exceptions may be interpreted as assertions of high conditional probability. In other words, a rule If X then Y may be interpreted as meaning that Pr(Y∣X) 1. A general approach to reasoning with such rules, based on second-order probability, is advocated. Within this general approach, different reasoning methods are needed, with the selection of a specific method being dependent upon what knowledge is available about the relative sizes, across rules, of upper bounds on each rule's exception probabilities Pr(?Y∣X). A method of reasoning, entailment with universal near surety, is formulated for the case when no information is available concerning the relative sizes of upper bounds on exception probabilities. Any conclusion attained under these conditions is robust in the sense that it will still be attained if information about the relative sizes of exception probability bounds becomes available. It is shown that reasoning via entailment with universal near surety is equivalent to reasoning in a particular type of argumentation system having the property that when two subsets of the rule base conflict with each other, the effectively more specific subset overrides the other. As stepping stones toward attaining this argumentation result, theorems are proved characterizing entailment with universal near surety in terms of upper envelopes of probability measures, upper envelopes of possibility measures, and directed graphs. In addition, various attributes of entailment with universal near surety, including property inheritance, are examined.     

基于知识话题模型的文本蕴涵识别

该文分析了现有基于分类策略的文本蕴涵识别方法的问题,并提出了一种基于知识话题模型的文本蕴涵分类识别方法。 其假设是: 文本可看作是语义关系的组合,这些语义关系构成若干话题;若即若文本T蕴涵假设H,说明 T 和 H 具有相似的话题分布,反之说明T 和 H 不具有相似的话题分布。基于此,我们将 T 和 H 的蕴涵识别问题转化为相关话题的生成过程,同时将文本推理知识融入到抽样过程,由此建立一个面向文本蕴涵识别的话题模型。实验结果表明基于知识话题模型在一定程度上改进了文本蕴涵识别系统的性能。     

Defeasible reasoning and logic programming

The general conditions of epistemic defeat are naturally represented through the interplay of two distinct kinds of entailment, deductive and defeasible. Many of the current approaches to modeling defeasible reasoning seek to define defeasible entailment via model-theoretic notions like truth and satisfiability, which, I argue, fails to capture this fundamental distinction between truthpreserving and justification-preserving entailments. I present an alternative account of defeasible entailment and show how logic programming offers a paradigm in which the distinction can be captured, allowing for the modeling of a larger range of types of defeat. This is possible through a natural extension of the declarative and procedural semantics of Horn clauses.     

融合语言知识与深度学习的文本蕴含识别

文本蕴含技术在自然语言处理中得到了广泛应用,但存在词对推理能力差的问题（例如,句对中出现反义词对无法判断反义关系等）。重点研究了词对知识向量的获取问题,包括融合多特征及有监督的词对关系向量获取、采用TransR的词对关系表示获取、反义词向量表示获取等三种方法,并将知识向量引入到文本蕴含识别模型中的词对齐和注意力机制部分。有关实验表明,上述方法相比经典模型有了较大的提升。     

一种计算逻辑结果支持度的新方法

在R.Haenni构造的概率推理系统中,给出了一种基于条件概率思想计算逻辑结果支持度的新方法,将该方法应用于一个逻辑电路中元件是否正常的可能性判定。     

The entailment principle for dempster—shafer granules

We discuss the rule of inference called the entailment principle which plays a significant role in the possibilistic type reasoning used in the theory of approximate reasoning. We extend this principle to situations in which the knowledge is a type of combination of possibilistic and probabilistic information which we call Dempster—Shafer granules. We discuss the conjunction of these D—S granules and show that Dempster's rule of combination is a special application of conjunction followed by a particular implementation of the entailment principle.     

Outlier detection for simple default theories

It was noted recently that the framework of default logics can be exploited for detecting outliers. Outliers are observations expressed by sets of literals that feature unexpected properties. These observations are not explicitly provided in input (as it happens with abduction) but, rather, they are hidden in the given knowledge base. Unfortunately, in the two related formalisms for specifying defaults — Reiter's default logic and extended disjunctive logic programs — the most general outlier detection problems turn out to lie at the third level of the polynomial hierarchy. In this note, we analyze the complexity of outlier detection for two very simple classes of default theories, namely NU and DNU, for which the entailment problem is solvable in polynomial time. We show that, for these classes, checking for the existence of an outlier is anyway intractable. This result contributes to further showing the inherent intractability of outlier detection in default reasoning.     

Lp, a logic for representing and reasoning with statistical knowledge

This paper presents a logical formalism for representing and reasoning with statistical knowledge. One of the key features of the formalism is its ability to deal with qualitative statistical information. It is argued that statistical knowledge, especially that of a qualitative nature, is an important component of our world knowledge and that such knowledge is used in many different reasoning tasks. The work is further motivated by the observation that previous formalisms for representing probabilistic information are inadequate for representing statistical knowledge. The representation mechanism takes the form of a logic that is capable of representing a wide variety of statistical knowledge, and that possesses an intuitive formal semantics based on the simple notions of sets of objects and probabilities defined over those sets. Furthermore, a proof theory is developed and is shown to be sound and complete. The formalism offers a perspicuous and powerful representational tool for statistical knowledge, and a proof theory which provides a formal specification for a wide class of deductive inferences. The specification provided by the proof theory subsumes most probabilistic inference procedures previously developed in AI. The formalism also subsumes ordinary first-order logic, offering a smooth integration of logical and statistical knowledge.     

Resource-Bounded Paraconsistent Inference

In this paper, a new framework for reasoning from inconsistent propositional belief bases is presented. A family of resource-bounded paraconsistent inference relations is introduced. Such inference relations are based on S-3 entailment, an inference relation logically weaker than the classical one and parametrized by a set S of propositional variables. The computational complexity of our relations is identified, and their logical properties are analyzed. Among the strong features of our framework is the fact that tractability is ensured each time |S| is bounded and a limited amount of knowledge is taken into account within the belief base. Furthermore, binary connectives , behave in a classical manner. Finally, our framework is general enough to encompass several paraconsistent multi-valued logics (including S-3, J ₃ and its restrictions), the standard coherence-based approach to inconsistency handling (based on the selection of consistent subbases) and some signed systems for paraconsistent reasoning as specific cases.     

Independence and Possibilistic Conditioning

There is not a unique definition of a conditional possibility distribution since the concept of conditioning is complex and many papers have been conducted to define conditioning in a possibilistic framework. In most cases, independence has been also defined and studied by means of a kind of analogy with the probabilistic case. In [2,4], we introduce conditional possibility as a primitive concept by means of a function whose domain is a set of conditional events. In this paper, we define a concept of independence associated with this form of conditional possibility and we show that classical properties required for independence concepts are satisfied.     

Structural and probabilistic knowledge for abductive reasoning

Different ways of representing probabilistic relationships among the attributes of a domain ar examined, and it is shown that the nature of domain relationships used in a representation affects the types of reasoning objectives that can be achieved. Two well-known formalisms for representing the probabilistic among attributes of a domain. These are the dependence tree formalism presented by C.K. Chow and C.N. Liu (1968) and the Bayesian networks methodology presented by J. Pearl (1986). An example is used to illustrate the nature of the relationships and the difference in the types of reasoning performed by these two representations. An abductive type of reasoning objective that requires use of the known qualitative relationships of the domain is demonstrated. A suitable way to represent such qualitative relationships along with the probabilistic knowledge is given, and how an explanation for a set of observed events may be constituted is discussed. An algorithm for learning the qualitative relationships from empirical data using an algorithm based on the minimization of conditional entropy is presented     

Formal Nonmonotonic Theories and Properties of Human Defeasible Reasoning

The knowledge representation and reasoning of both humans and artificial systems often involves conditionals. A conditional connects a consequence which holds given a precondition. It can be easily recognized in natural languages with certain key words, like “if” in English. A vast amount of literature in both fields, both artificial intelligence and psychology, deals with the questions of how such conditionals can be best represented and how these conditionals can model human reasoning. On the other hand, findings in the psychology of reasoning, such as those in the Suppression Task, have led to a paradigm shift from the monotonicity assumptions in human inferences towards nonmonotonic reasoning. Nonmonotonic reasoning is sensitive for information change, that is, inferences are drawn cautiously such that retraction of previous information is not required with the addition of new information. While many formalisms of nonmonotonic reasoning have been proposed in the field of Artificial Intelligence, their capability to model properties of human reasoning has not yet been extensively investigated. In this paper, we analyzed systematically from both a formal and an empirical perspective the power of formal nonmonotonic systems to model (i) possible explicit defeaters, as in the Suppression Task, and (ii) more implicit conditional rules that trigger nonmonotonic reasoning by the keywords in such rules. The results indicated that the classical evaluation for the correctness of inferences has to be extended in the three major aspects (i) regarding the inference system, (ii) the knowledge base, and (iii) possible assumed exceptions for the rule.     

重言衍推系统的试探法自动证明

提出针对重言衍推系统的模仿人类思维方式的生成可读证明的算法:试探法.试探法将待证的命题逐步分解成子命题并构造一颗证明树,对重言衍推系统中的定理证明取得了较好的效果.