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

2019/12/1,史忠植高级人工智能,1,高级人工智能,2019/12/1,史忠植高级人工智能,2,第二章人工智能逻辑,2.1逻辑-重要的形式工具2.2非单调逻辑2.3默认逻辑2.4限定逻辑2.5自认知逻辑2.6真值维护系统2.7情景演算的逻辑基础2.8动态描述逻辑,描述逻辑DescriptionLogics,2019/12/1,史忠植高级人工智能,4,主要内容,什么是描述逻辑？为什么用描述逻辑？描述逻辑的研究进展描述逻辑的体系结构描述逻辑的构造算子描述逻辑的推理问题我们的工作,2019/12/1,史忠植高级人工智能,5,1什么是描述逻辑(DL)？,一种基于对象的知识表示的形式化，也叫概念表示语言或术语逻辑。建立在概念和关系(Role)之上概念解释为对象的集合关系解释为对象之间的二元关系源于语义网络和KL-ONE是一阶逻辑FOL的一个可判定的子集具有合适定义的语义(基于逻辑),2019/12/1,史忠植高级人工智能,6,特点,是以往表示工具的逻辑重构和统一形式化框架系统(Frame-basedsystems)语义网络(SemanticNetworks)面向对象表示(OOrepresentation)语义数据模型(Semanticdatamodels)类型系统(Typesystems)特征逻辑(FeatureLogics)具有很强的表达能力是可判定的，总能保证推理算法终止,2019/12/1,史忠植高级人工智能,7,描述逻辑的应用,概念建模查询优化和视图维护自然语言语义智能信息集成信息存取和智能接口工程的形式化规范术语学和本体论规划,2019/12/1,史忠植高级人工智能,8,2为什么用描述逻辑？,若直接使用一阶逻辑，而不附加任何约束，则：知识的结构将被破坏，这样就不能用来驱动推理对获得可判定性和有效的推理问题来说，其表达能力太高，（也许是太抽象了）对兴趣表达，但仍然可判定的理论，其推理能力太低。,DL的重要特征是：很强的表达能力；可判定性，它能保证推理算法总能停止，并返回正确的结果。,2019/12/1,史忠植高级人工智能,9,在众多知识表示的形式化方法中，描述逻辑在十多年来受到人们的特别关注，主要原因在于以下三点:它们有清晰的模型-理论机制;它们很适合于通过概念分类学来表示应用领域；它们提供了很用的推理服务。它们可以被认为是从基于框架的表示形式化向着精确的语义特征方向发展。此外，描述逻辑将分类学中表示和推理（专业推理）与在分类学中项的事实或实例的表示和推理（断言推理）区别开来。,2019/12/1,史忠植高级人工智能,10,3描述逻辑的研究进展描述逻辑的基础研究研究描述逻辑的构造算子、表示和推理的基本问题，如可满足性、包含检测、一致性、可判定性等。一般都在最基本的ALC的基础上在扩展一些构造算子，如数量约束、逆关系、特征函数、关系的复合等。TBox和Abox上的推理问题、包含检测算法等。Schmidt-Schaub和Smolka首先建立了基于描述逻辑ALC的Tableau算法，该算法能在多项式时间内判断描述逻辑ALC概念的可满足性问题。,2019/12/1,史忠植高级人工智能,11,描述逻辑的扩展研究A.Artale和E.Franconi(1998)提出了一个知识表示系统，用时间约束的方法将状态、动作和规划的表示统一起来。为了能让描述逻辑处理模态词，F.Baader将模态操作引入描述逻辑，证明了该描述逻辑公式的可满足性问题是可判定的。Wolter等对具有模态算子的描述逻辑进行了深入系统的调查分析，并证明在恒定的领域假设下多种认知和时序描述逻辑是可判定的。另外如时序扩展(Artale,Wolter)、模糊扩展(Straccia)等。,2019/12/1,史忠植高级人工智能,12,描述逻辑的应用研究描述逻辑在许多领域中被作为知识表示的工具，如信息系统（Catarci,1993）数据库（Borgida,1995;Bergamaschi1992;Sheth,1993）软件工程(Devambu,1991)网络智能访问（Levy，1996；Blanco，1994）规划（Seida,1992）等Horrocks对表达能力较强的描述逻辑进行了研究，并建立了一些逻辑框架和系统，如FaCT，SHIQ等。他和DieterFensel等人将描述逻辑、语义网和DAML结合起来，提出了DAML+OIL，其中以描述逻辑作为核心的表示和推理基础。并在XML及其RDF上面进行了扩展，用描述逻辑来研究语义网络和本体论。,2019/12/1,史忠植高级人工智能,13,4描述逻辑的体系结构,一个描述逻辑系统包含四个基本组成部分：1）表示概念和关系（Role）的构造集2）Tbox关于概念术语的断言3）Abox关于个体的断言4）Tbox和Abox上的推理机制。,2019/12/1,史忠植高级人工智能,14,概念解释为一个领域的子集例子：所有在校学习的人员的集合构成“学生”概念又如：孩子，已婚的，哺乳动物等概念x|Student(x)，x|Married(x),关系(Roles)属性(二元谓词，关系)例子：朋友，爱人，|Friend(x,y)，|Loves(x,y),1）DL的基本元素概念和关系,2019/12/1,史忠植高级人工智能,15,知识库,TBox(模式)ManHumanMaleHappy-fatherHumanHas-child.Female,Abox(数据)John:Happy-father:Has-child,推理系统,接口,2019/12/1,史忠植高级人工智能,16,2）TBox语言是描述领域结构的公理的集合,定义:引入概念的名称AC,ACFatherManhas-child.HumanHumanAnimalBiped包含：声明包含关系的公理CD(CDCD，DC)has-degree.Mastershas-degree.Bachelors一个解释I满足：CDiffCI=DICDiffCIDI一个解释I满足TBoxTiff它满足T中的每个公理(IT),2019/12/1,史忠植高级人工智能,17,概念表示实体(一元谓词，类)例子：学生，已婚的x|Student(x)，x|Married(x)BirdAnimal,ManHuman,关系(Roles)属性(二元谓词，关系)例子：朋友，爱人|Friend(x,y)，|Loves(x,y),TBox实例,2019/12/1,史忠植高级人工智能,18,概念断言表示一个对象是否属于某个概念a:C例如：Tom是个学生，表示为Tom:Student或者Student(Tom)John:Manhas-child.Female,关系断言表示两个对象是否满足一定的关系:R例如：John有个孩子叫Mary:has-child,3）ABox语言（断言部分）是描述具体情形的公理的集合,2019/12/1,史忠植高级人工智能,19,一个解释I满足：a:CiffaICI:RiffRI一个解释I满足ABoxAiff它满足A中的每个公理记为：IA一个解释I满足知识库=iff它满足T和A记为：I,2019/12/1,史忠植高级人工智能,20,4）语法和语义,2019/12/1,史忠植高级人工智能,21,一般地，描述逻辑依据提供的构造算子，在简单的概念和关系上构造出复杂的概念和关系。通常DL至少包含以下算子：合取()，吸取()，非()量词约束：存在量词()，全称量词()最基本的DL称之为ALC例如，ALC中概念Happy-father定义为：Manhas-child.Malehas-child.Femalehas-child.(DoctorLawyer),5DL中的构造算子,2019/12/1,史忠植高级人工智能,22,DL中的其它算子,另外，有两个类似于FOL中的全集(true)和空集(false)的算子,2019/12/1,史忠植高级人工智能,23,在DL中添加算子,一般地，在描述逻辑中添加不同的算子，则得到不同表达能力的描述逻辑，其复杂性问题也不尽相同。例如，在ALC的基础上添加逆(-)算子，则构成ALCI若再加上数量约束算子(n,n)，则构成ALCIQ。若在描述逻辑中添加时序算子，则构成为时序描述逻辑(TemporalDescriptionLogic)，例如，可以添加：Until算子U：CUDSince算子S：CSD还可以加入其它算子，如模态算子，等。,2019/12/1,史忠植高级人工智能,24,6描述逻辑中的推理,1)一致性（协调性consistency）2)可满足性(satisfiability)3)包含检测（subsumption）4)实例检测(instancechecking)5)Tableaux算法6）可判定性7）计算复杂性,2019/12/1,史忠植高级人工智能,25,1)一致性检测(Consistency),知识库是协调的吗？即检测是否有的模型(解释)I？,C关于TboxT是协调的吗？即检测是否有T的模型I使得C？,2019/12/1,史忠植高级人工智能,26,2)概念可满足性(Satisfiablity),对一个概念C，如果存在一个解释I使得CI是非空的，则称概念C是可满足的，否则是不可满足的。检验一个概念的可满足性，实际上就是看是否有解释使得这个概念成立。例如：概念MaleFemale，即需要检测是否有性别既是男的又是女的这样的人。若确实是没有这种两性人，则我们断言，这个概念是不可满足的。又如概念：studentworker，它是可满足的。即代表那些在职学生的集合。,定理：概念C是可满足的，当且仅当C不包含于。,2019/12/1,史忠植高级人工智能,27,在知识库中检测：CD？即检测CIDI是否在所有的解释中成立？,3)概念包含(Subsumption),例如：birdanimalcomputerequipment,在Tbox中检测：CD？即检测CIDI是否在TboxT的所有解释中成立？,2019/12/1,史忠植高级人工智能,28,CDiffCD是不可满足的。CTDiffCD关于T是不可满足的。C关于T是一致的iffCTAA,包含与可满足性的关系,CD,2019/12/1,史忠植高级人工智能,29,4）实例检测(Instancechecking),概念的实例：Student(John)，或者表示为John:Student关系的实例：Father(John,Mary)实例检索：检索属于某个概念的所有实例的集合,2019/12/1,史忠植高级人工智能,30,5）可满足性检测算法Tableaux算法,1)规则:Sx: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)规则:Sy:CS，若x:R.C在S中，xRy在S中成立，且y:C不在S中。,2019/12/1,史忠植高级人工智能,31,例子：检测概念的可满足性：(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)规则矛盾所以这个概念是不可满足的。,2019/12/1,史忠植高级人工智能,32,6）可判定性,描述逻辑中的可满足性问题是可判定的。其它推理问题基本上可以归结为可满足性问题。,7）计算复杂性,描述逻辑中的推理问题其计算复杂性一般是多项式时间的。但通常由于构造的不同，其复杂性也有一定的差异。,2019/12/1,史忠植高级人工智能,33,我们的工作,带缺省的描述逻辑定义一个缺省规则是形如这样的表达式，其中C、D、E为概念名，x是一个变元。C(x)称为前提条件，D(x)称为检验条件(缺省)，E(x)称为缺省的结论。定义1.2一个知识库是一个三元组，其中T为Tbox，A为Abox，D为缺省规则集。,2019/12/1,史忠植高级人工智能,34,面向主体的动态描述逻辑,描述逻辑最开始只是用来表示静态知识的。为了考虑在时间上的变化，或者在一定动作下的变化，以及保持其语言的相对简单性，很自然地我们需要通过相应的模态算子来扩展它，以保留其命题模态状态。,提出面向主体的动态描述逻辑，用来描述主体中的动态知识以及推理。,描述逻辑,动态逻辑,主体,面向主体的动态描述逻辑,201