第二章人工智能逻辑第二部分课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第二章 人工智能逻辑,第二部分,史忠植,中国科学院计算技术研究所,高级人工智能,10/3/2024,1,描 述 逻 辑,Description Logics,10/3/2024,2,主要内容,什么是描述逻辑？,为什么用描述逻辑？,描述逻辑的研究进展,描述逻辑的体系结构,描述逻辑的构造算子,描述逻辑的推理问题,我们的工作,10/3/2024,3,1 什么是描述逻辑(DL),？,一种基于对象的知识表示的形式化，,也叫概念表示语言或术语逻辑。,建立在概念和关系,(Role),之上,概念解释为对象的集合,关系解释为对象之间的二元关系,源于语义网络和,KL-ONE,是一阶逻辑,FOL,的一个可判定的子集,具有合适定义的语义,(,基于逻辑,),10/3/2024,4,特点,是以往表示工具的逻辑重构和统一形式化,框架系统,(Frame-based systems),语义网络,(Semantic Networks),面向对象表示,(OO representation),语义数据模型,(Semantic data models),类型系统,(Type systems),特征逻辑,(Feature Logics),具有很强的表达能力,是可判定的，总能保证推理算法终止,10/3/2024,5,描述逻辑的应用,概念建模,查询优化和视图维护,自然语言语义,智能信息集成,信息存取和智能接口,工程的形式化规范,术语学和本体论,规划,10/3/2024,6,2 为什么用描述逻辑？,若直接使用一阶逻辑，而不附加任何约束，则：,知识的结构将被破坏，这样就不能用来驱动推理,对获得可判定性和有效的推理问题来说，其表达,能力太高，（也许是太抽象了）,对兴趣表达，但仍然可判定的理论，其推理能力太低。,DL的重要特征是：,很强的表达能力；,可判定性，它能保证推理算法总能停止，并返回正确的结果。,10/3/2024,7,在众多知识表示的形式化方法中，描述逻辑在十多,年来受到人们的特别关注，主要原因在于以下三点:,它们有清晰的模型-理论机制;,它们很适合于通过概念分类学来表示应用领域；,它们提供了很用的推理服务。,它们可以被认为是从基于框架的表示形式化向着,精确的语义特征方向发展。此外，描述逻辑将分类,学中表示和推理（专业推理）与在分类学中项的事,实或实例的表示和推理（断言推理）区别开来。,10/3/2024,8,3,描述逻辑的研究进展,描述逻辑的基础研究,研究描述逻辑的构造算子、表示和推理的基本问题，,如可满足性、包含检测、一致性、可判定性等。,一般都在最基本的ALC的基础上在扩展一些构造算子，,如数量约束、逆关系、特征函数、关系的复合等。,TBox和Abox上的推理问题、包含检测算法等。,Schmidt-Schaub,和,Smolka,首先建立了基于描述逻辑,ALC,的,Tableau,算法，该算法能在多项式时间内判断描述,逻辑,ALC,概念的可满足性问题。,10/3/2024,9,描述逻辑的扩展研究,A.Artale,和,E.Franconi(1998),提出了一个知识表示系统，,用时间约束的方法将状态、动作和规划的表示统一起来。,为了能让描述逻辑处理模态词，,F.Baader,将模态操作,引入描述逻辑，证明了该描述逻辑公式的可满足性问题,是可判定的。,Wolter,等对具有模态算子的描述逻辑进行了深入系统,的调查分析，并证明在恒定的领域假设下多种认知和时序,描述逻辑是可判定的。,另外如时序扩展(Artale,Wolter)、模糊扩展(Straccia)等。,10/3/2024,10,描述逻辑的应用研究,描述逻辑在许多领域中被作为知识表示的工具，如,信息系统（,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上面进行了扩展，,用描述逻辑来研究语义网络和本体论。,10/3/2024,11,4,描述逻辑的体系结构,一个描述逻辑系统包含四个基本组成部分：,1,）表示概念和关系（,Role,）的构造集,2,）,Tbox关于概念术语,的断言,3,）,Abox关于个体,的断言,4,）,Tbox,和,Abox,上的推理机制。,10/3/2024,12,概念,解释为一个领域的子集,例子：所有在校学习的人员的集合构成“学生”概念,又如：孩子，已婚的，哺乳动物等概念,x,|,Student,(,x,)，,x,|,Married,(,x,),关系,(Roles)属性(二元谓词，关系),例子：朋友，爱人，,|,Friend,(,x,y,)，|,Loves,(,x,y,),1）DL的基本元素概念和关系,10/3/2024,13,知,识,库,TBox(模式),Man,Human,Male,Happy-father,Human,Has-child,.,Female,Abox(数据),John:Happy-father,:,Has-child,推理系统,接口,10/3/2024,14,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,C,I,=,D,I,C,D,iff,C,I,D,I,一个解释,I,满足,TBox T,iff 它满足,T,中的每个公理(,I,T,),10/3/2024,15,概念,表示实体(一元谓词，类),例子：学生，已婚的,x,|,Student,(,x,)，,x,|,Married,(,x,),Bird,Animal,Man,Human,关系,(Roles)属性(二元谓词，关系),例子：朋友，爱人,|,Friend,(,x,y,)，|,Loves,(,x,y,),TBox,实例,10/3/2024,16,概念断言,表示一个对象是否属于某个概念,a,:,C,例如：Tom是个学生，表示为,Tom,:,Student或者Student(,Tom,),John,:,Man,has-child,.,Female,关系断言,表示两个对象是否满足一定的关系,:,R,例如：John有个孩子叫Mary,:,has-child,3）ABox语言（断言部分）,是描述具体情形的公理的集合,10/3/2024,17,一个解释,I,满足：,a,:,C,iff,a,I,C,I,:R,iff,R,I,一个解释,I,满足,ABox,A,iff 它满足,A,中的每个公理记为：,I,A,一个解释,I,满足知识库,=,iff 它满足,T,和,A,记为：,I,10/3/2024,18,4）语法和语义,构造算子,语法,语义,例子,原子概念,A,A,I,I,Human,原子关系,R,R,I,I,I,has-child,对概念C,D和关系(role)R,合取,C,D,C,I,D,I,Human,Male,析取,C,D,C,I,D,I,Doctor,Lawyer,非,C,I,C,Male,存在量词,R.C,x|,y,.,R,I,y,C,I,has-child.Male,全称量词,R.C,x|,y,.,R,I,y,C,I,has-child.Doctor,10/3/2024,19,一般地，描述逻辑依据提供的构造算子，在简单的,概念和关系上构造出复杂的概念和关系。,通常DL至少包含以下算子：,合取(,)，吸取(,)，非(,),量词约束：存在量词(,)，全称量词(,),最基本的DL称之为,ALC,例如，ALC中概念Happy-father定义为：,Man,has-child,.,Male,has-child,.,Female,has-child,.,(,Doctor,Lawyer,),5,DL中的构造算子,10/3/2024,20,构造算子,语法,语义,例子,数量约束,n R.C,x|,y|,R,I,y,C,I,|,n,3,has-child.Male,n R.C,x|,y|,R,I,y,C,I,|,n,3,has-child.Male,逆,R,-,|,R,I,has-child,-,传递闭包,R*,(,R,I,),*,has-child*,DL中的其它算子,top,T,I,Male,Male,Bottom,Man,Man,另外，有两个类似于FOL中的全集(true)和空集(false)的算子,10/3/2024,21,在DL中添加算子,一般地，在描述逻辑中添加不同的算子，则得到不同,表达能力的描述逻辑，其复杂性问题也不尽相同。,例如，在ALC的基础上添加逆(-)算子，则构成,ALCI,若再加上数量约束算子(,n,n,)，则构成,ALCIQ,。,若在描述逻辑中添加时序算子，则构成为时序描述,逻辑(Temporal Description Logic)，例如，可以添加：,Until算子 U：,C,U,D,Since算子 S：,C,S,D,还可以加入其它算子，如模态算子,，,，,等。,10/3/2024,22,6 描述逻辑中的推理,1),一致性,（协调性consistency）,2),可满足性,(satisfiability),3),包含检测,（subsumption）,4),实例检测,(instance checking),5),Tableaux算法,6）,可判定性,7）,计算复杂性,10/3/2024,23,1)一致性检测(Consistency),知识库是协调的吗？,即检测是否有,的模型(解释),I,？,C,关于Tbox,T,是协调的吗？,即检测是否有,T,的模型,I,使得,C,？,10/3/2024,24,2)概念可满足性(,Satisfiablity,),对一个概念,C,，如果存在一个解释,I,使得,C,I,是非空的，则称概念,C,是可满足的，否则是不可满足的。,检验一个概念的可满足性，实际上就是看是否有解释使得这个概念成立。例如：概念Male,Female，即需要检测是否有性别既是男的又是女的这样的人。若确实是没有这种两性人，则我们断言，这个概念是不可满足的。,又如概念：student,worker，它是可满足的。即代表那些在职学生的集合。,定理：,概念,C,是可满足的，当且仅当,C,不包含于,。,10/3/2024,25,在知识库中检测,：,C,D,？,即检测,C,I,D,I,是否在所有的解释中成立？,3)概念包含(,Subsumption,),例如：,bird,animalcomputer,equipment,在Tbox中检测,：,C,D,？,即检测,C,I,D,I,是否在Tbox,T,的所有解释中成立？,10/3/2024,26,C,D,iff,C,D,是不可满足的。,C,T,D,iff,C,D,关于,T,是不可满足的。,C,关于,T,是一致的,iff,C,T,A,A,包含与可满足性的关系,D,D,C,C,D,10/3/2024,27,4）实例检测(Instance checking),概念的实例：,Student(John)，或者表示为 John,:,Student,关系的实例：,Father(John,Mary),实例检索：,检索属于某个概念的所有实例的集合,10/3/2024,28,5）可满足性检测算法Ta