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

第二章人工智能逻辑

第二部分史忠植中国科学院计算技术研讨所高级人工智能描述逻辑

DescriptionLogics主要内容◆什么是描画逻辑？◆为什么用描画逻辑？◆描画逻辑的研讨进展◆描画逻辑的体系构造◆描画逻辑的构造算子◆描画逻辑的推理问题◆我们的任务1/8/20243史忠植高级人工智能1什么是描画逻辑(DL)？ 一种基于对象的知识表示的方式化，也叫概念表示言语或术语逻辑。建立在概念和关系(Role)之上 －概念解释为对象的集合 －关系解释为对象之间的二元关系源于语义网络和KL-ONE是一阶逻辑FOL的一个可断定的子集具有适宜定义的语义(基于逻辑)1/8/20244史忠植高级人工智能特点◆是以往表示工具的逻辑重构和一致方式化 －框架系统(Frame-basedsystems) －语义网络(SemanticNetworks) －面向对象表示(OOrepresentation) －语义数据模型(Semanticdatamodels) －类型系统(Typesystems) －特征逻辑(FeatureLogics)◆具有很强的表达才干◆是可断定的，总能保证推理算法终止1/8/20245史忠植高级人工智能描画逻辑的运用◆概念建模◆查询优化和视图维护◆自然言语语义◆智能信息集成◆信息存取和智能接口◆工程的方式化规范◆术语学和本体论◆规划◆…1/8/20246史忠植高级人工智能2为什么用描画逻辑？假设直接运用一阶逻辑，而不附加任何约束，那么：◆知识的构造将被破坏，这样就不能用来驱动推理◆对获得可断定性和有效的推理问题来说，其表达才干太高，〔也许是太笼统了〕◆对兴趣表达，但依然可断定的实际，其推理才干太低。DL的重要特征是：◆很强的表达才干；◆可断定性，它能保证推理算法总能停顿，并前往正确的结果。1/8/20247史忠植高级人工智能在众多知识表示的方式化方法中，描画逻辑在十多年来遭到人们的特别关注，主要缘由在于以下三点:◆它们有明晰的模型-实际机制;◆它们很适宜于经过概念分类学来表示运用领域；◆它们提供了很用的推理效力。它们可以被以为是从基于框架的表示方式化向着准确的语义特征方向开展。此外，描画逻辑将分类学中表示和推理〔专业推理〕与在分类学中项的事实或实例的表示和推理〔断言推理〕区别开来。1/8/20248史忠植高级人工智能3描画逻辑的研讨进展◆描画逻辑的根底研讨 研讨描画逻辑的构造算子、表示和推理的根本问题，如可满足性、包含检测、一致性、可断定性等。 普通都在最根本的ALC的根底上在扩展一些构造算子，如数量约束、逆关系、特征函数、关系的复合等。 TBox和Abox上的推理问题、包含检测算法等。 Schmidt-Schaub和Smolka首先建立了基于描画逻辑ALC的Tableau算法，该算法能在多项式时间内判别描画逻辑ALC概念的可满足性问题。1/8/20249史忠植高级人工智能◆描画逻辑的扩展研讨 A.Artale和E.Franconi(1998)提出了一个知识表示系统，用时间约束的方法将形状、动作和规划的表示一致同来。 为了能让描画逻辑处置模态词，F.Baader将模态操作引入描画逻辑，证明了该描画逻辑公式的可满足性问题是可断定的。 Wolter等对具有模态算子的描画逻辑进展了深化系统的调查分析，并证明在恒定的领域假设下多种认知和时序描画逻辑是可断定的。 另外如时序扩展(Artale,Wolter)、模糊扩展(Straccia)等。1/8/202410史忠植高级人工智能◆描画逻辑的运用研讨描画逻辑在许多领域中被作为知识表示的工具，如 信息系统〔Catarci,1993〕 数据库〔Borgida,1995;Bergamaschi1992;Sheth,1993〕 软件工程(Devambu,1991) 网络智能访问〔Levy，1996；Blanco，1994〕 规划〔Seida,1992〕等 Horrocks对表达才干较强的描画逻辑进展了研讨，并建立了一些逻辑框架和系统，如FaCT，SHIQ等。他和DieterFensel等人将描画逻辑、语义网和DAML结合起来，提出了DAML+OIL，其中以描画逻辑作为中心的表示和推理根底。并在XML及其RDF上面进展了扩展，用描画逻辑来研讨语义网络和本体论。1/8/202411史忠植高级人工智能4描画逻辑的体系构造一个描画逻辑系统包含四个根本组成部分：1〕表示概念和关系〔Role〕的构造集2〕Tbox——关于概念术语的断言3〕Abox——关于个体的断言4〕Tbox和Abox上的推理机制。1/8/202412史忠植高级人工智能◆概念——解释为一个领域的子集例子：一切在校学习的人员的集合构成“学生〞概念 又如：孩子，已婚的，哺乳动物等概念{x|Student(x)}，{x|Married(x)}◆关系(Roles)——属性(二元谓词，关系)例子：朋友，爱人，{<x,y>|Friend(x,y)}，{<x,y>|Loves(x,y)}1〕DL的根本元素——概念和关系1/8/202413史忠植高级人工智能知识库TBox(方式)Man≐Human⊓MaleHappy-father≐Human⊓∃Has-child.Female⊓…Abox(数据)John:Happy-father<John,Mary>:Has-child推理系统接口1/8/202414史忠植高级人工智能2〕TBox言语 是描画领域构造的公理的集合定义:引入概念的称号A≐C,A⊑CFather≐Man⊓∃has-child.HumanHuman⊑Animal⊓Biped包含：声明包含关系的公理C⊑D(C≐DC⊑D，D⊑C)∃has-degree.Masters⊑∃has-degree.Bachelors一个解释I满足：C≐DiffCI=DI C⊑DiffCI⊆DI一个解释I满足TBoxTiff它满足T中的每个公理(I⊨T)1/8/202415史忠植高级人工智能◆概念——表示实体(一元谓词，类)例子：学生，已婚的{x|Student(x)}，{x|Married(x)} Bird⊑Animal,Man⊑Human◆关系(Roles)——属性(二元谓词，关系)例子：朋友，爱人{<x,y>|Friend(x,y)}，{<x,y>|Loves(x,y)}TBox实例1/8/202416史忠植高级人工智能◆概念断言——表示一个对象能否属于某个概念 a:C例如：Tom是个学生，表示为 Tom:Student 或者 Student(Tom) John:Man⊓∃has-child.Female◆关系断言——表示两个对象能否满足一定的关系 <a,b>:R例如：John有个孩子叫Mary <John,Mary>:has-child3〕ABox言语〔断言部分〕 是描画详细情形的公理的集合1/8/202417史忠植高级人工智能一个解释I满足：a:CiffaI∈CI<a,b>:Riff<aI,bI>∈RI一个解释I满足ABoxAiff它满足A中的每个公理记为：I⊨A一个解释I满足知识库=<T,A>iff它满足T和A记为：I⊨1/8/202418史忠植高级人工智能4〕语法和语义构造算子语法语义例子原子概念AAI⊆△IHuman原子关系RRI⊆△I

△Ihas-child对概念C,D和关系(role)R合取C⊓DCI∩DIHuman⊓Male析取C⊔DCI⋃

DIDoctor⊔Lawyer非¬C△I\C¬Male存在量词∃

R.C{x|∃y.<x,y>∈

RI∧y∈CI}∃

has-child.Male全称量词∀R.C{x|∀y.<x,y>∈

RI

y∈CI}∀

has-child.Doctor1/8/202419史忠植高级人工智能普通地，描画逻辑根据提供的构造算子，在简单的概念和关系上构造出复杂的概念和关系。通常DL至少包含以下算子： ◆合取(⊓)，汲取(⊔)，非(¬) ◆量词约束：存在量词(∃)，全称量词(∀)最根本的DL称之为ALC例如，ALC中概念Happy-father定义为： Man⊓∃has-child.Male ⊓∃has-child.Female ⊓∀has-child.(Doctor⊔Lawyer)5DL中的构造算子1/8/202420史忠植高级人工智能构造算子语法语义例子数量约束≥nR.C{x||{y|<x,y>∈

RI,y∈CI}

|≥n}≥3

has-child.Male≤nR.C{x||{y|<x,y>∈

RI,y∈CI}

|≤n}≤3

has-child.Male逆R-{<y,x>|<x,y>∈

RI}has-child-传递闭包R*(RI)*has-child*DL中的其它算子topT△IMale⊔

¬MaleBottom

Man⊓

¬Man另外，有两个类似于FOL中的选集(true)和空集(false)的算子1/8/202421史忠植高级人工智能在DL中添加算子普通地，在描画逻辑中添加不同的算子，那么得到不同表达才干的描画逻辑，其复杂性问题也不尽一样。例如，在ALC的根底上添加逆(-)算子，那么构成ALCI假设再加上数量约束算子(≥n,≤n)，那么构成ALCIQ。假设在描画逻辑中添加时序算子，那么构成为时序描画逻辑(TemporalDescriptionLogic)，例如，可以添加： Until算子U：CUD Since算子S：CSD还可以参与其它算子，如模态算子□，

，○等。1/8/202422史忠植高级人工智能6描画逻辑中的推理1)一致性〔协调性consistency〕2)可满足性(satisfiability)3)包含检测〔subsumption〕4)实例检测(instancechecking)5)Tableaux算法6〕可断定性7〕计算复杂性1/8/202423史忠植高级人工智能1)一致性检测(Consistency)◆知识库<T,A>是协调的吗？ 即检测能否有<T,A>的模型(解释)I？◆C关于TboxT是协调的吗？ 即检测能否有T的模型I使得C≠？1/8/202424史忠植高级人工智能2)概念可满足性(Satisfiablity)对一个概念C，假设存在一个解释I使得CI是非空的，那么称概念C是可满足的，否那么是不可满足的。检验一个概念的可满足性，实践上就是看能否有解释使得这个概念成立。例如：概念Male⊓Female，即需求检测能否有性别既是男的又是女的这样的人。假设确实是没有这种两性人，那么我们断言，这个概念是不可满足的。又如概念：student⊓worker，它是可满足的。即代表那些在职学生的集合。定理：概念C是可满足的，当且仅当C不包含于。1/8/202425史忠植高级人工智能◆在知识库中检测： C⊑D？ 即检测CI⊆DI能否在一切的解释中成立？3)概念包含(Subsumption)例如： bird⊑animal computer⊑equipment◆在Tbox中检测： C⊑D？ 即检测CI⊆DI能否在TboxT的一切解释中成立？1/8/202426史忠植高级人工智能C⊑DiffC⊓¬D是不可满足的。C⊑TDiffC⊓¬D关于T是不可满足的。C关于T是一致的iffC⊑TA⊓¬A包含与可满足性的关系¬DDCC⊓¬D＝1/8/202427史忠植高级人工智能4〕实例检测(Instancechecking)概念的实例： Student(John)，或者表示为John:Student关系的实例： Father(John,Mary) 实例检索：检索属于某个概念的一切实例的集合1/8/202428史忠植高级人工智能5〕可满足性检测算法——Tableaux算法1)⊓规那么:S→⊓{x:C1,x:C2}⋃S，假设x:C1⊓C2在S中，且x:C1和x:C2不在S中同时出现。2)⊔规那么:S→⊔{x:D}⋃S，假设x:C1⊔C2在S中，x:C1和x:C2都不在S中，且D=C1或者D=C2。3)∃规那么:S→∃{xP1y,…,xPky,y:C}⋃S，假设x:∃R.C在S中，R=P1⊓…⊓Pk，没有z使得xRz在S中成立，且z:C在S中，y为一个新变量。4)∀规那么:S→∀{y:C}⋃S，假设x:∃R.C在S中，xRy在S中成立，且y:C不在S中。1/8/202429史忠植高级人工智能例子：检测概念的可满足性：(∀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) ∀规那么 矛盾所以这个概念是不可满足的。1/8/202430史忠植高级人工智能6〕可断定性描画逻辑中的可满足性问题是可断定的。其它推理问题根本上可以归结为可满足性问题。7〕计算复杂性描画逻辑中的推理问题其计算复杂性普通是多项式时间的。但通常由于构造的不同，其复杂性也有一定的差别。1/8/202431史忠植高级人工智能SemanticWebArchitecture1/8/202432史忠植高级人工智能我们的任务◆带缺省的描画逻辑定义一个缺省规那么是形如这样的表达式，其中C、D、E为概念名，x是一个变元。C(x)称为前提条件，D(x)称为检验条件(缺省)，E(x)称为缺省的结论。定义1.2一个知识库是一个三元组<T,A,D>，其中T为Tbox，A为Abox，D为缺省规那么集。1/8/202433史忠植高级人工智能◆动态描画逻辑描画逻辑最开场只是用来表示静态知识的。为了思索在时间上的变化，或者在一定动作下的变化，以及坚持其言语的相对简单性，很自然地我们需求经过相应的模态算子来扩展它，以保管其命题模态形状。提出动态描画逻辑，用来描画主体中的动态知识以及推理。描画逻辑动态逻辑＋主体面向主体的动态描画逻辑1/8/202434史忠植高级人工智能以客观世界的方式化建模为研讨内容，提出一种一致的方式化框架，同时从静态和动态两个方面来描写世界的模型。为动态领域的建模提供一种有效的方式化实际工具；将世界中的概念、关系和个体，公理、现实和动作有机地整合在一同，构成一致的关联和运作机制，使动作与公理和现实相互作用，一致表示并进展推理；对概念、公式和动作都给出了一致的、适宜的语法和语义；主体与本体的结合动态描画逻辑DDL1/8/202435史忠植高级人工智能动态描画逻辑DDLDDL：语义环境中对效力过程方面的建模和推理效力改动环境的形状：前提条件和执行结果，Action效力描画：基于WorldModel，e.g.,描画效力的前提和结果的词汇来自WorldModel