知识与常识的表示和推理

一、引言无疑,常识(Common Knowledge)的表示和推理是知识领域中极其关键的研究问题,因为常识的特殊性质使它在多主体(Multi-agent)协同推理、通讯中起着重要的作用。可以看到,对于多主体的问题如三个聪明人问题,Conway问题乃至更一般的博奕理论,分布式处理等,都将涉及到超越个体知识和事实之上的更高层次的知识,这就是常识。常识     

常识表示与推理的探讨

常识问题的研究一直是计算机领域的一个难点和重点。为下一代软件环境建立常识基础的工作意义非凡,它会使计算机变得更聪明、克服软件系统的脆弱性、减少系统之间的通讯开销等。本文将介绍一常识表示与推理实验系统,并重点说明其中的表示语言、推理机制及知识库的组织方法等。     

一类定性定量综合集成推理的模糊控制算法设计

在控制系统中提出了定性变量及定量变量的新概念,并将二者的综合集成推理应用到模糊加权自调整控制算法的设计中。以倒立摆为被控对象的仿真结果表明,应用此控制算法的模糊控制器具有较好的控制效果,同时验证了该控制逄法具有较好的鲁棒性和自适应性。     

一种用于常识空间信息处理的定性空间关系模型

在空间信息处理中,一些常识空间信息通常结合多方面空间关系,而且这些空间关系是动态变化的.为了有效地表示这些复杂的空间关系,并对其进行推理,提出了一种结合拓扑、方向和大小关系的空间信息处理模型TDSC (topology-direction-size calculus),并基于TDSC模型提出了处理动态空间关系变化的表示推理框架.首先,利用同对象多属性的方法建立了融合大小、拓扑和方向关系的完备至斥基本关系表示;然后提出了复合表生成算法和推理算法,使得原有模型的表示和推理结果可以直接在新模型中使用.同时提出处理动态空间关系的邻域划分图,给出了邻域划分图的自动生成算法,以及TDSC模型的邻域划分图.最后给出基于TDSC模型邻域划分图的表示和推理框架,并结合实例说明框架的正确性和有效性.     

几何因果定性推理的基本原理和算法

因果定性推理是一种通过分析描述物理系统行为和关系的约束找出系统内部各个成分之间的因果结构的推理方法．本文提出一种基于约束和变量分析的因果定性分析模型和算法．该方法在产品设计中有广泛的应用,利用这个模型和算法可较好地解决参数化设计中的几何推理问题,还可用作概念设计的工具,用于完成复杂系统设计任务的划分及定序、设计变量之间相互依赖关系分析等工作．算法具有应用性强、效率和稳定性好、支持欠约束和多解问题等优点.     

集成多方面信息的定性空间推理及应用

以往的定性空间或时空推理工作多数面向单一时空方面,这不符合实际应用需要.提出了集成拓扑、尺寸和时间3方面信息的定性表示和推理技术,并应用到时空GIS中.给出了面向GIS的拓扑、尺寸和时间的表示方法,并研究了它们之间的依赖性.提出了集成这3方面信息的约束满足问题求解算法TriRSAT.在时空GIS中,把定性时空表示用于约束关系库,把TriRSAT算法用于时空数据一致性检查和时空查询.应用结果显示,该理论和方法能有效地集成处理多方面时空信息,在时空数据库、机器人导航等领域有着广泛的应用前景.     

定性空间推理的分层递阶框架

定性空间推理是定性推理和空间推理的重要组成部分 .拓扑和形状是定性空间推理研究的关键问题 .针对定性空间推理已有一般框架存在的问题 ,提出了定性空间推理的分层递阶框架 ,并结合拓扑和形状方面的定性空间推理研究工作阐述了所提出的框架的有效性和合理性 .最后总结了分层递阶框架的要点并提出了基于该框架的进一步研究工作 .     

面向知识图谱约束问答的强化学习推理技术

知识图谱问答任务通过问题分析与知识图谱推理,将问题的精准答案返回给用户,现已被广泛应用于智能搜索、个性化推荐等智慧信息服务中.考虑到关系监督学习方法人工标注的高昂代价,学者们开始采用强化学习等弱监督学习方法设计知识图谱问答模型.然而,面对带有约束的复杂问题,现有方法面临两大挑战:(1)多跳长路径推理导致奖励稀疏与延迟;(2)难以处理约束问题推理路径分支.针对上述挑战,设计了融合约束信息的奖励函数,能够解决弱监督学习面临的奖励稀疏与延迟问题;设计了基于强化学习的约束路径推理模型COPAR,提出了基于注意力机制的动作选择策略与基于约束的实体选择策略,能够依据问题约束信息选择关系及实体,缩减推理搜索空间,解决了推理路径分支问题.此外,提出了歧义约束处理策略,有效解决了推理路径歧义问题.采用知识图谱问答基准数据集对COPAR的性能进行了验证和对比.实验结果表明:与现有先进方法相比,在多跳数据集上性能相对提升了2%-7%,在约束数据集上性能均优于对比模型,准确率提升7.8%以上.     

对Allen的时间理论的某些改进

Ａｌｌｅｎ的时间理论因直观、易懂而倍受推崇，但它存在不能处理连续变化事件等缺欠。本文提出更为一般的时间理论框架，以扩展Ａｌｌｅｎ的理论，本框架的特点为：（１）将Ａｌｌｅｎ的理论纳入其中；（２）可由时间构造时区，并可处理时区和时间点；（３）以时间元素集的２Ｄ图形表示为基础的约束传播算法，既高效又可视化。     

方位关系约束满足问题的推理求解

约束满足问题（Constraint Satisfaction Problems CSP）是人工智能的一个研究领域,诸如空间查找、规划等问题都可转化为约束满足问题。方位关系是空间关系的重要组成部分,用以确定空间对象间的一种顺序。本文研究了空间方位关系模型,给出了方位关系约束的一般表示形式。在此基础上,利用组合表推理给出了方位关系约束满足问题的一个推理求解算法,该算法的时间复杂度为O（n^2）。     

Exact and approximate reasoning about temporal relations1

Allen gives an algebra for representing qualitative temporal information about the relationships between pairs of intervals. In this paper, we address a fundamental reasoning task that arises in applications of the algebra: Given (possibly indefinite) knowledge about the relationships between intervals, find all feasible relationships between two intervals. We call this the minimal labels problem. Finding the minimal labels can be viewed as computing the deductive consequences of our knowledge. Determining exact solutions to this problem has been shown to be (almost assuredly) intractable. Allen gives an approximation algorithm based on constraint propagation. We present new approximation algorithms; determine analytically under what conditions the algorithms are exact; and examine, through some computational experiments, the quality of the approximate solutions produced by the algorithms. We also give a simple test for predicting when the approximation algorithms will and will not produce good quality approximations. Finally, we survey three example applications of the interval algebra chosen from the literature to show where the results of this paper could be useful.     

A General Qualitative Framework for Temporal and Spatial Reasoning

To offer a generic framework which groups together several interval algebra generalizations, we simply define a generalized interval as a tuple of intervals. An atomic relation between two generalized intervals is a matrix of atomic relations of Interval Algebra. After introducing the generalized relations we focus on the consistency problem of generalized constraint networks and we present sets of generalized relations for which this problem is tractable, in particular the set of the strongly-preconvex relations.     

ON COMPUTING THE MINIMAL LABELS IN TIME POINT ALGEBRA NETWORKS

We analyze the problem of computing the minimal labels for a network of temporal relations in point algebra. Van Beek proposes an algorithm for accomplishing this task, which takes O (max( n ³, n² m) ) time (for n points and m ≠ -relations). We show that the proof of the correctness of this algorithm given by van Beek and Cohen is faulty, and we provide a new proof showing that the algorithm is indeed correct.     

Relation Algebras and their Application in Temporal and Spatial Reasoning

Qualitative temporal and spatial reasoning is in many cases based on binary relations such as before, after, starts, contains, contact, part of, and others derived from these by relational operators. The calculus of relation algebras is an equational formalism; it tells us which relations must exist, given several basic operations, such as Boolean operations on relations, relational composition and converse. Each equation in the calculus corresponds to a theorem, and, for a situation where there are only finitely many relations, one can construct a composition table which can serve as a look up table for the relations involved. Since the calculus handles relations, no knowledge about the concrete geometrical objects is necessary. In this sense, relational calculus is pointless. Relation algebras were introduced into temporal reasoning by Allen (1983, Communications of the ACM 26(1), 832–843) and into spatial reasoning by Egenhofer and Sharma (1992, Fifth International Symposium on Spatial Data Handling, Charleston, SC). The calculus of relation algebras is also well suited to handle binary constraints as demonstrated e.g. by Ladkin and Maddux (1994, Journal of the ACM 41(3), 435–469). In the present paper I will give an introduction to relation algebras, and an overview of their role in qualitative temporal and spatial reasoning.     

Reasoning situated in time I: basic concepts*

Abstract

The needs of a real-time reasoner situated in an environment may make it appropriate to view error-correction and non-monotonicity as much the same thing. This has led us to formulate situated (or step) logic, an approach to reasoning in which the formalism has a kind of real-time self-reference that affects the course of deduction itself. Here we seek to motivate this as a useful vehicle for exploring certain issues in commonsense reasoning. In particular, a chief drawback of more traditional logics is avoided: from a contradiction we do not have all wffs swamping the (growing) conclusion set. Rather, we seek potentially inconsistent, but nevertheless useful, logics where the real-time self-referential feature allows a direct contradiction to be spotted and corrective action taken, as part of the same system of reasoning. Some specific inference mechanisms for real-time default reasoning are suggested, notably a form of introspection relevant to default reasoning. Special treatment of ‘now’ and of contradictions are the main technical devices here. We illustrate this with a computer-implemented real time solution to R. Moore's Brother Problem.     

Lattice structure of temporal interval relations

Due to increasing interest in representation of temporal knowledge, automation of temporal reasoning, and analysis of distributed systems, literally dozens of temporal models have been proposed and explored during the last decade. Interval-based temporal models are especially appealing when reasoning about events with temporal extent but pose special problems when deducing possible relationships among events. The paper delves deeply into the structure of the set of atomic relations in a class of temporal interval models assumed to satisfy density and homogeneity properties. An order structure is imposed on the atomic relations of a given model allowing the characterization of the compositions of atomic relations (or even lattice intervals) as lattice intervals. By allowing the utilization of lattice intervals rather than individual relations, this apparently abstract result explicitly leads to a concrete approach which speeds up constraint propagation algorithms.     

Temporal Constraints: A Survey

Temporal Constraint Satisfaction is an information technology useful for representing and answering queries about temporal occurrences and temporal relations between them. Information is represented as a Constraint Satisfaction Problem (CSP) where variables denote event times and constraints represent the possible temporal relations between them. The main tasks are two: (i) deciding consistency, and (ii) answering queries about scenarios that satisfy all constraints. This paper overviews results on several classes of Temporal CSPs: qualitative interval, qualitative point, metric point, and some of their combinations. Research has progressed along three lines: (i) identifying tractable subclasses, (ii) developing exact search algorithms, and (iii) developing polynomial-time approximation algorithms. Most available techniques are based on two principles: (i) enforcing local consistency (e.g. path-consistency) and (ii) enhancing naive backtracking search.     

Representation and Reasoning with Multi-Point Events

Allen's Interval Algebra (IA) and Vilain & Kautz's Point Algebra (PA) consider an interval and a point as basic temporal entities (i.e., events) respectively. However, in many situations we need to deal with recurring events that include multiple points, multiple intervals or combinations of points and intervals. In this paper, we present a framework to model recurring events as multi-point events (MPEs) by extending point algebra. The reasoning tasks are formulated as binary constraint satisfaction problems. We propose a polynomial time algorithm (based on van Beek's algorithm) for finding all feasible relations. For the problem of finding a consistent scenario, we propose a backtracking method with a local search heuristic. We also describe an implementation and a detail empirical evaluation of the proposed algorithms. Our empirical results indicate that the MPE-based approach performs better than the existing approaches.