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

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