人工智能逻辑(描述逻辑).ppt

1,高级人工智能,第二章 人工智能逻辑 史忠植 中国科学院计算技术研究所,描 述 逻 辑 Description Logics,Advanced Artificial Intelligence,第二章 人工智能逻辑,2.1 逻辑-重要的形式工具 2.2 非单调逻辑 2.3 默认逻辑 2.4 限定逻辑 2.5 自认知逻辑 2.6 真值维护系统 2.7 情景演算的逻辑基础 2.8 动态描述逻辑,主要内容, 什么是描述逻辑？ 为什么用描述逻辑？ 描述逻辑的研究进展 描述逻辑的体系结构 描述逻辑的构造算子 描述逻辑的推理问题 我们的工作,8.1 什么是描述逻辑(DL)？,一种基于对象的知识表示的形式化，也叫概念表示语言或术语逻辑。 建立在概念和关系(Role)之上 概念解释为对象的集合 关系解释为对象之间的二元关系 源于语义网络和KL-ONE 是一阶逻辑FOL的一个可判定的子集 具有合适定义的语义(基于逻辑),特点,是以往表示工具的逻辑重构和统一形式化 框架系统 (Frame-based systems) 语义网络 (Semantic Networks) 面向对象表示 (OO representation) 语义数据模型 (Semantic data models) 类型系统 (Type systems) 特征逻辑 (Feature Logics) 具有很强的表达能力 是可判定的，总能保证推理算法终止,描述逻辑的应用, 概念建模 查询优化和视图维护 自然语言语义 智能信息集成 信息存取和智能接口 工程的形式化规范 术语学和本体论 规划 ,8.2 为什么用描述逻辑？,若直接使用一阶逻辑，而不附加任何约束，则： 知识的结构将被破坏，这样就不能用来驱动推理 对获得可判定性和有效的推理问题来说，其表达 能力太高，（也许是太抽象了） 对兴趣表达，但仍然可判定的理论，其推理能力太低。,DL的重要特征是： 很强的表达能力； 可判定性，它能保证推理算法总能停止，并返回正确的结果。,在众多知识表示的形式化方法中，描述逻辑在十多年来受到人们的特别关注，主要原因在于以下三点 : 它们有清晰的模型-理论机制; 它们很适合于通过概念分类学来表示应用领域； 它们提供了很用的推理服务。 它们可以被认为是从基于框架的表示形式化向着精确的语义特征方向发展。此外，描述逻辑将分类学中表示和推理（专业推理）与在分类学中项的事实或实例的表示和推理（断言推理）区别开来。,3 描述逻辑的研究进展, 描述逻辑的基础研究 研究描述逻辑的构造算子、表示和推理的基本问题，如可满足性、包含检测、一致性、可判定性等。 一般都在最基本的ALC的基础上在扩展一些构造算子，如数量约束、逆关系、特征函数、关系的复合等。 TBox和Abox上的推理问题、包含检测算法等。 Schmidt-Schaub 和 Smolka首先建立了基于描述逻ALC的Tableau算法，该算法能在多项式时间内判断描述逻辑ALC概念的可满足性问题。, 描述逻辑的扩展研究 A.Artale和E.Franconi (1998)提出了一个知识表示系统，用时间约束的方法将状态、动作和规划的表示统一起来。 为了能让描述逻辑处理模态词，F.Baader将模态操作引入描述逻辑，证明了该描述逻辑公式的可满足性问题是可判定的。 Wolter等对具有模态算子的描述逻辑进行了深入系统的调查分析，并证明在恒定的领域假设下多种认知和时序描述逻辑是可判定的。 另外如时序扩展(Artale, Wolter)、模糊扩展(Straccia)等。, 描述逻辑的应用研究 描述逻辑在许多领域中被作为知识表示的工具，如 信息系统（Catarci,1993） 数据库（Borgida,1995; Bergamaschi 1992; Sheth, 1993） 软件工程(Devambu, 1991) 网络智能访问（Levy， 1996； Blanco，1994） 规划（Seida, 1992）等 Horrocks对表达能力较强的描述逻辑进行了研究，并建立了一些逻辑框架和系统，如FaCT，SHIQ等。他和Dieter Fensel等人将描述逻辑、语义网和DAML结合起来，提出了DAML+OIL，其中以描述逻辑作为核心的表示和推理基础。并在XML及其RDF上面进行了扩展，用描述逻辑来研究语义网络和本体论。,4 描述逻辑的体系结构,一个描述逻辑系统包含四个基本组成部分： 1）表示概念和关系（Role）的构造集 2）Tbox关于概念术语的断言 3）Abox关于个体的断言 4）Tbox和Abox上的推理机制。,1）DL的基本元素概念和关系, 概念 解释为一个领域的子集 例子：所有在校学习的人员的集合构成“学生”概念 又如：孩子，已婚的，哺乳动物等概念 x | Student(x) ，x | Married(x) , 关系(Roles) 属性(二元谓词，关系) 例子：朋友，爱人， | Friend(x,y) ， | Loves(x,y) ,知 识 库,TBox(模式) Man Human Male Happy-father Human Has-child.Female ,Abox(数据) John: Happy-father : Has-child,推理系统,接口,2）TBox语言是描述领域结构的公理的集合,定义: 引入概念的名称 A C, A C Father Man has-child.Human Human Animal Biped 包含：声明包含关系的公理 C D ( C D C D ，D C) has-degree.Masters has-degree.Bachelors 一个解释I满足： C D iff CI = DI C D iff CI DI 一个解释I满足TBox T iff 它满足T中的每个公理(IT), 概念 表示实体(一元谓词，类) 例子：学生，已婚的 x | Student(x) ，x | Married(x) Bird, 关系(Roles) 属性(二元谓词，关系) 例子：朋友，爱人 | Friend(x,y) ， | Loves(x,y) ,TBox实例, 概念断言 表示一个对象是否属于某个概念 a: C 例如：Tom是个学生，表示为 Tom : Student 或者 Student(Tom) John : Man has-child.Female, 关系断言 表示两个对象是否满足一定的关系 : R 例如：John有个孩子叫Mary : has-child,3）ABox语言-断言部分-是描述具体情形的公理的集合,一个解释I满足： a : C iff aI CI :R iff RI 一个解释I满足ABox A iff 它满足A中的每个公理记为： I A 一个解释I满足知识库 = iff 它满足T和A记为： I ,4）语法和语义,5 DL中的构造算子,一般地，描述逻辑依据提供的构造算子，在简单的概念和关系上构造出复杂的概念和关系。 通常DL至少包含以下算子： 合取( )，析取( )，非( ) 量词约束：存在量词( )，全称量词() 最基本的DL称之为ALC 例如，ALC中概念Happy-father定义为： Man has-child.Male has-child.Female has-child.(Doctor Lawyer),DL中的其它算子,另外，有两个类似于FOL中的全集(true)和空集(false)的算子,在DL中添加算子,一般地，在描述逻辑中添加不同的算子，则得到不同表达能力的描述逻辑，其复杂性问题也不尽相同。 例如，在ALC的基础上添加逆( - )算子，则构成ALCI若再加上数量约束算子(n , n )，则构成ALCIQ。 若在描述逻辑中添加时序算子，则构成为时序描述逻辑(Temporal Description Logic)，例如，可以添加： Until算子 U： C U D Since算子 S： C S D 还可以加入其它算子，如模态算子 ， ， 等。,6 描述逻辑中的推理,1) 一致性（协调性consistency） 2) 可满足性(satisfiability) 3) 包含检测（subsumption） 4) 实例检测 (instance checking) 5) Tableaux算法 6) 可判定性 7) 计算复杂性,1)一致性检测(Consistency),知识库是协调的吗？ 即检测是否有的模型 (解释) I ？, C关于Tbox T是协调的吗？ 即检测是否有T的模型 I 使得 C ？,2) 概念可满足性(Satisfiablity),对一个概念C，如果存在一个解释I使得CI是非空的，则称概念C是可满足的，否则是不可满足的。 检验一个概念的可满足性，实际上就是看是否有解释使得这个概念成立。例如：概念MaleFemale，即需要检测是否有性别既是男的又是女的这样的人。若确实是没有这种两性人，则我们断言，这个概念是不可满足的。 又如概念： studentworker，它是可满足的。即代表那些在职学生的集合。,定理：概念C是可满足的，当且仅当C不包含于。,在知识库中检测： C D？ 即检测 CI DI 是否在所有的解释中成立？,3) 概念包含(Subsumption),例如： bird animal computer equipment,在Tbox中检测： C D？ 即检测 CI DI 是否在Tbox T的所有解释中成立？,C D iff C D是不可满足的。 C T D iff C D关于T是不可满足的。 C 关于T是一致的 iff C T A A,包含与可满足性的关系,C D ,4）实例检测(Instance checking),概念的实例： Student (John)，或者表示为 John:Student 关系的实例： Father(John, Mary) 实例检索：检索属于某个概念的所有实例的集合。,5）可满足性检测算法Tableaux算法,1) 规则: S x:C1, x:C2S，若x:C1C2在S中，且x:C1和x:C2不在S中同时出现。 2) 规则: Sx:DS，若x:C1C2在S中，x:C1和x:C2都不在S中，且D= C1或者D= C2。 3) 规则: SxP1y,xPky, y:CS，若x:R.C在S中，R= P1Pk，没有z使得xRz在S中成立，且z:C在S中，y为一个新变量。 4) 规则: S y:CS，若x:R.C在S中，xRy在S中成立，且y:C不在S中。,例子：检测概念的可满足性： (has-child.Male) (has-child.Male)， 其检测过程为： (has-child.Male) (has-child.Male)(x) (has-child.Male)(x) 规则 (has-child.Male)(x) 规则 has-child (x, y) 规则 Male (y) 规则 Male (y) 规则 矛盾 所以这个概念是不可满足的。,6）可判定性,描述逻辑中的可满足性问题是可判定的。 其它推理问题基本上可以归结为可满足性问题。,7）计算复杂性,描述逻辑中的推理问题其计算复杂性一般是多项式时间的。但通常由于构造的不同，其复杂性也有一定的差异。,我们的工作,带缺省的描述逻辑 定义 一个缺省规则是形如 这样的表达式， 其中C、D、E为概念名，x是一个变元。C(x)称为前提条件，D(x)称为检验条件(缺省)，E(x)称为缺省的结论。 定义1.2 一个知识库是一个三元组，其中T为Tbox，A为Abox，D为缺省规则集。,面向主体的动态描述逻辑,提出面向主体的动态描述逻辑，用来描述主体 中的动态知识以及推理。,描述逻辑,动态逻辑,主体,面向主体的 动态描述逻辑,描述逻辑最开始只是用来表示静态知识的。为了考虑在时间上的变化，或者在一定动作下的变化，以及保持其语言的相对简单性，很自然地我们需要通过相应的模态算子来扩