人工智能知识表示.ppt

Artificial Intelligence,一,),状态空间表示法,状态空间表示法是,知识表达的基本方法,。所谓状态是用来表示系统状态、事实等叙述型知识的一组变量或数组。所谓操作是用来表示引起状态变化的过程型知识的一组关系或函数。状态空间利用状态变量和操作符号，表示系统或问题的有关知识的符号体系，可用,三元组（,S,，,O,，,G,）来描述,.,问题求解：从起始状态出发，经过一系列操作交换，达到目标状态，即状态空间搜索问题。状态空间的一个解是一个有限的规则序列，它使初始状态转化为目标状态，解不一定唯一。,6.1,已经学过的知识表达方法,二,),与或图表示法,与或图基于人们求解问题时的两种思维方法：,分解,与树：将复杂的大问题分解为一组简单的小问题，将总问题分解为若干子问题。若所有的子问题都解决了，则总问题也解决了，这是与的逻辑关系。,变换,或树：将较难的问题变换为较易的等价或等效的问题。若一个难问题可以等价变换为几个容易问题，则任何一个容易问题解决了，也就解决了原有的难问题，这是或的逻辑关系。,三,),产生式系统,产生式系统是一种最早被使用且直到现在仍被广泛使用的知识表示方法,.,在产生式系统中，知识分为两部分：用事实表示静态知识,;,用产生式规则表示推理过程和行为,.,三个基本部分组成：一个综合数据库（事实库）、一组产生式规则（规则集）和一个控制系统（控制器）。,四,),逻辑表达方法,逻辑是最早也是最广泛用于知识表示的模式之一,.,原因在于,1),包含,:,一个公理系统，说明什么关系和蕴含可以形式化；一个演绎结构，即推理规则集合,.,2),逻辑及其形式系统的演绎都保证正确,.,3),演绎可以完全机械化，它是定理证明中使用得较为成功的一种技术,.,优点,:,严格性 通用性 自然性 模块性,缺点,:,效率低 灵活性差,6.2,知识表示的概念与含义,从知识的观点，智能表现在：知识的获取能力,知识的处理能力,知识的运用能力。,要使计算机系统具有人的智能能力，则必须以人的知识为基础。因此，什么是知识，这是,AI,首先要解决的问题。,知识是人们对自然现象的认识和从中总结出来的规律、经验。,表示是使用人造的体系对自然界事物的运算规律进行概括与抽象的模型。,知识表示是概括智能的模型，知识表示是人工智能研究的一个重要课题，不同的知识有不同的表示方法,合理的知识表示可以使问题的求解变得容易，并且有较高的求解效率。,6.3,知识类型和知识模型的变换,知识类型：知识的表达就是研究知识的形式化方法。人类所拥有的知识需要用适当的方法来表示，才能够在计算机中存储、检索、运用、增删和修改。在,AI,中，知识可分为,3,种类型：,1,）、叙述型知识。有关系统状态、环境和条件，问题的概念、定义和事实的知识。,2,）、过程型知识。有关系统状态变化、问题求解过程的操作、演算和行动的知识。,3,）、控制型知识。有关如何选择相应的操作、演算和行动的比较、判断、管理和决策的知识。,例如：,对于从北京到上海，是乘飞机还是坐火车的问题，有关的知识可以归结如下：,叙述型知识,：北京、上海、飞机、火车、时间、费用,过程型知识,：乘飞机、坐火车,控制型知识,：乘飞机较快、较贵；坐火车较慢、较便宜。,知识模型的变换：,对于不同的知识表达方法，则有各种,不同的形式化知识模型。,同构变换可使问题更明确，便于求解，同构问题的解答等价于原始问题的解答。,同态变换可使问题更加简化，易于求解。原始问题有解，则同态问题有解，同态问题无解，则原始问题无解，它们之间是蕴涵关系。,通过同构或同态变换，可以把原始问题转化为比较清晰、简单的同构或同态问题，如下图所示,例、方格棋盘分割问题，如下图所示,1,）、原始问题：在,2n2n,的方格棋盘中，去掉对顶角上两个小方格后，如图（,a,）所示，问能否将它分割为若干,12,的小长方块？,(“,组合爆炸”,),。,2,）、同构问题：,将棋盘中小方格相间着色,，将其化为同构问题，如图（,b,）所示，由此可见，,无论,n,为何值，对顶角上两个小方格是同色的,，去掉它们后，小白格和小黑格的数目之间的差值为,2,。,由于每个（,12,）长方块只能包括一个小白格和小黑格，,因此无论如何分割，最后剩下的必定是同色的两个小方格，无法分割成原始问题要求的小长方块,。,3,）同态问题：,引入序对（小黑格数，小白格数），用以表示待分割的棋盘的状态，化为同态问题,，,1.,初态：（,2n,2,，,2n,2,-2,）；,2.,目标：（,0,，,0,）；,3.,分割操作：每次操作，分割出一个小长方块，割去一个小黑格和一个小白格，使状态变量都减去,1,，如第一次分割，使原始状态变成状态（,2n,2,-1,，,2n,2,-3,）。显然，经过,2n,2,-2,次操作后，状态变为（,2,，,0,），不可能达到所求的目标状态（,0,，,0,）。,6.4,语义网络,6.4.1,语义网络的概念和特性,概念：语义网络是一种采用网络形式表示人类知识的方法。形式上，一个语义网络是一个带标识的有向图，其中带有标识的节点表示问题领域中的物体、概念、事件、动作或态势，节点之间的有向弧也带有标识，表示节点之间的语义联系。有时又将弧称为联想弧，所以语义网络又称为联想网络。,语义网络是自然语言,/,逻辑语言中语义含义的一种结构化表示方法。,优点有自然性,联想性,效率较高,;,缺点有不严格,不便于表达判断性知识,深层知识,.,6.4.2,语义网络的知识表达,1,、基本命题的语义网络表示,在语义网络中，节点一般划分为实例节点和类节点两种类型。有向弧用于刻画节点之间的语义联系，是语义网络组织知识的关键。比较典型的语义联系有：,以个体为中心组织知识的语义联系,1,）,实例联系,。用于表示类节点与所属实例节点之间的联系，通常标识为,ISA,。例如“燕子是一只鸟”可以表示为：,2,）,泛化联系,：用于表示一种类节点（如鸟）与更抽象的类节点（如动物）之间的联系，通常用,AKO,（,A Kind Of,）表示。通过,AKO,可以将问题领域中的所有类节点组织成一个,AKO,层次网络。泛化联系允许低层类型,继承,高层类型的属性，这样可以将公用属性抽象到较高层次。减少了对存储空间的要求。,3,）聚集联系：,用于表示某一个体与其组成成分之间的联系，通常用,part-of,表示,。聚集联系基于概念的分解性，将高层概念分解为若干低层概念的集合。,翅膀,鸟,Part-of,4,）属性联系：,用于表示个体、属性及其取值之间的联系，通常用有向弧表示属性，用这些弧指向的节点表示各自的值。,如下图所示，约翰的性别是男性，年龄为,30,岁等。,以谓词关系为中心组织知识的语义联系,从本质上讲,语义网络节点之间的连接是二元关系,一元和多元关系很容易转换为语义网络,.,如 鸟是动物,.,Animal(bird),一元,ISA(bird,animal),二元,火箭和活塞在本周一场,NBA,篮球比赛中的比分是,92:104,其逻辑表示法为,score(,火箭,活塞,92:104).,多元,方法,:,可以引入一个类,:,篮球比赛,和一个个体,:NBA,火箭,-,活塞本周比赛,将多元关系表示成二元关系的组合,.,2,、连接词在语义网络中的表示方法,任何具有表达谓词公式能力的语义网络，除具备表达基本命题的能力外，还必须具备表达命题之间的“与”、“或”、“非”以及“蕴涵”关系的能力。,（,1,）合取。,合取命题通过引入“与”节点来,表示。如命题,give(John,Mary,“,战争与和平”,),read(Mary,“,战争与和平”,),可以表示为下图所示的带“与”节点的语义网络。,（,2,）析取。,析取命题通过引入“或”节点来表示。,例如命题,John is a programmer or Mary is a lawyer,可以表示为下图所示的语义网络。,其中，,OC1,和,OC2,为两个具体的职业关系，分别对应,John,为,programmer,及,Mary,为,lawyer,。,（,3,）否定。,对于基本联系的否定可以直接采用,ISA,，,AKO,及,part-of,的有向弧来标注,。通常,需要通过引进“非”节点来表示。如命题,give(John,Mary,“,战争与和平”,),read(Mary,“,战争与和平”,),可以表示为下图所示的语义网络。,（,4,）蕴含。,通过引入蕴含关系节点来表示规则中前提条件和结论之间的因果联系,。从蕴含关系节点出发，一条弧指向命题的前提条件，记为,ANKE,，另一条弧指向该规则的结论，记为,CONSE,。如规则“如果车库起火，那么用,CO,2,或沙来灭火”可以表示为下图所示的语义网络。,3,、变元和量词在语义网络中的表示方法,存在量词在语义网络中直接用,ISA,弧表示。而全称量词就要用分级网络的分块来表示,。,例如，命题：,The dog bite the postman,这句话意味着所涉及的是存在量词。下图（,a,）给出了相应的语义网络。网络中,D,节点表示一特定的狗；,P,表示一特定的邮递员；,B,表示一特定的咬人事件。咬人事件,B,包括两部分，一部分是攻击者，另一部分是受害者。节点,D,，,B,和,P,都是用,ISA,弧与概念节点,DOG,，,BITE,以及,POSTMAN,相连，因此表示的是存在量词。,如果我们进一步要表示：,Every dog has bitten a postman 这个事实，用谓词逻辑可表示为,（,x,）DOG（x）,（,y）POSTMAN（y）,BITE（x，y）,上述谓词公式中包含有全称量词,。方法是利用分级把网络分割成空间分层集合。每一个空间对应于一个或几个变量的范围。下图（b）是上述事实的语义网络.,分级网络,:,引入一个类节点,GS,它是对客观世界的一般性描述,;,要表示的语句是,GS,的一个个体,(,实例,)G,如果,G,中含有,n,个全称变量,G,在网络中有,n+1,条弧射出,:,第一条,:,格式（,FORM,）,它指向全称量词管辖的子网络,(S1,是一个特定的分割，它表示一个断言：,A dog has bitten a postman);,后,n,条,:,分别,指向被全称量化的变量,;,这样的语义网络表示对每一条狗存在一个咬人事件,B,和一个邮递员,P,，使得,D,是,B,中的攻击者，而,P,是受害者。,为进一步说明如何表示量化变量，可考虑如何表示下述事实：,Every dog has bitten every postman,。,只需对图（,b,）做简单的修改，增加一条,弧与节点,P,相连。这样做的含义是每条狗咬了每个邮递员，如图（,c,）所示。,6.8,框架,6.8.1,基本概念,1975,年,由,M.Minsky,提出，用于表示客观事物的层次关系,.,与语义网络一样，是一种结构化表示方法。,人们通常使用一种,通用的数据结构的形式来存储以往的经验。这样的数据结构，称为框架,.,一个框架系统中,一般都含有多个框架,.,6.8.2,框架的结构,框架（,frame,）由框架名和一组用于描述对象各方面具体属性的槽（,slot,）组成。每个槽又拥有一定数量的侧面，每个侧面又拥有若干个侧面值。约束条件是为了给,框架,槽,侧面附加说明信息的,可提高框架结构的表达能力和推理能力。由此，一个框架可以形式地表示如下：,FRAME,槽名,A,：侧面名,A,1,：值,A,11,值,A,12,值,A,13,侧面名,A,2,：值,A,21,值,A,22,值,A,23,槽名,B,：侧面名,B,1,：值,B,11,值,B,12,值,B,13,侧面名,B,2,：值,B,21,值,B,22,值,B,23,槽名,C,：侧面名,C,1,：值,C,11,值,C,12,值,C,13,侧面名,C,2,：值,C,21,值,C,22,值,C,23,约束条件,:,约束条件,1,约束条件,2,约束条件,3,我们看一个一层一层嵌套的框架结构,前,2,个描述的是概念,最后一个描述的是具体实例,.,例,1,：描述学校的框架,框架名：,类 属：,类 型,:,范围,(,大学,中学,小学,),位 置,:(,省,市,),面 积：单位,(,平方米,),教工人数：,学生人数：,例,2,：描述大学的框架,框架名：,类 属：,类 型,:,范围,(,综合性,专科性,),专 业,:,默认值,:,综合,学 院 数：,教 学 楼：,教工人数：,职工人数：,学生人数：,位 置,:(,省,市,),面 积：单位,(,平方米,),例,3,：描述北京工业大学的框架,框架名：,类 属：,名 称,:,北京工业大学,专 业,:,综合,学 院 数：,15,教 学 楼：,18,办 公 楼,:10,学生宿舍,:10,教工宿舍,:9,教工人数：,3000,职工人数：,5000,学生人数：,20000,位 置,:,北京市,面 积：,10000,万平方米,建校时间,:1960,年,9,月,