《人工智能》知识表示方法--课件

,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,河南农业大学,Artificial Intelligence(AI),人工智能,第二章：知识表示方法,预备知识,人类的智能活动过程主要是一个获得并运用知识的过程,按照符号主义的观点，,知识是一切智能行为的基础,，要使计算机具有智能，首先必须使它拥有知识,首先需要明确一下几个问题,什么是知识,知识的划分,人工智能系统中的知识,什么是知识表示,知识表示方法,知识的概念,知识的一般概念：,知识是人们在改造客观世界的实践中积累起来的,认识,和,经验,认识：,包括对事物现象、本质、属性、状态、联系等的认识,经验：,包括,解决问题的微观方法和宏观方法,微观方法：,如步骤、操作、规则、过程、技巧等,宏观方法：,如战略、战术、计谋、策略等,eg：,“,if,大雁向南飞，,then,冬天就要来临了。,”,这样一条知识就是人们经过长期的观察，将,“,大雁向南飞,”,与,“,冬天来临,”,这两条信息关联在一起。,“,雪是白色的,”,反映雪与颜色的一种关系。,知识的概念,知识、信息、数据及其关系,数据：,是信息的载体，本身无确切含义。如：,水的温度是100，木头的长度是2米，大楼的高度是100层,信息：,是数据的关联，赋予数据特定的含义，仅可理解为描述性知识。数据是没有联系的，孤立的，,只有当数据用来描述一个客观事物和客观事物的关系，形成有逻辑的数据流，他们才能被称为信息,。,知识：,可以是对,信息的关联,，也可以是,对已有知识的再认识,。如：西安7月1日气温为30度，12月1日气温为3度。当对这类信息进行归纳和对比就会发现西安每年7月气温比较高，12月气温比较低。于是有价值的信息沉淀并结构化后就形成了知识。,知识的划分,知识的划分,按知识的性质：,概念、命题、公理、定理、规则和方法,按知识的作用域：,常识性知识，领域性知识,按知识的等级：,零级知识：,事实性知识。用于描述事物的概念、定义、属性等；或用于描述问题的状态、环境、条件等。,一级知识：,过程性知识。用于问题求解过程的操作、演算和行为的知识。,表示方式：产生式、谓词、语义网络等。,二级知识：,控制性知识，元知识或超知识。是关于如何使用过程性知识的知识。,例如：推理策略、搜索策略、不确定性的传播策略。,知识的划分,按知识的层次：,表层知识：,描述客观事物的现象的知识。例如：感性、事实性知识,深层知识：,描述客观事物本质、内涵等的知识。例如：理论知识,按知识的确定性：,确定性知识：,可以说明其真值为真或为假的知识,不确定性知识：,包括不精确、模糊、不完备知识,不精确：,知识本身有真假，但由于认识水平限制却不能肯定知识的真假。,表示：用可信度、概率等描述,模糊：,知识本身的边界就是不清楚的。,例如：大，小等。表示：用可能性、隶属度来描述,不完备：,解决问题时不具备解决该问题的全部知识。,例如：医生看病,知识的划分,按人类的思维及认识方法：,逻辑性知识：,是反映人类逻辑思维过程的知识，一般具有因果关系或难以精确描述的特点，是人类的经验性知识和直观感觉；,如：人的为人处事的经验与风格,形象性知识：,通过事物的形象建立起来的知识。,如:什么是人？,按知识的获取方式：,显性知识：,指可通过文字、语言、图形、声音等形式编码记录和传播的知识；,如：教材、音视频光盘。,隐性知识：,指人们长期实践中积累获得的知识，不易用显性知识表达的知识。,如：每个人都有不同的审美观。,人工智能系统中的知识,一个智能程序高水平的运行需要有关的,事实知识、规则知识、控制知识和元知识。,事实知识：,是有关问题环境的一些事物的知识，常以“,是,”的形式出现。,如事物的分类、属性、事物间关系、科学事实、客观事实等,事实是静态的为人们共享的可公开获得的公认的知识，,在知识库中属低层的知识。,如：雪是白色的、鸟有翅膀、张三李四是好朋友、这辆车是张三的,规则知识：,是有关问题中与事物的行动、动作相联系的因果关系知识，是动态的，常以“,如果那么,”形式出现。,人工智能系统中的知识,控制知识：,是有关问题的求解步骤、技巧的知识，告诉人们怎么做一件事，也包括当有多个动作同时被激活时应选哪一个动作来执行的知识。,控制知识常与程序结合在一起出现，如一个问题求解的算法可以看做是一种知识表示。,元知识：,是有关知识的知识，是,知识库中的高层知识,。,包括怎样使用规则、解释规则、校验规则、解释程序结构等知识。,元知识与控制知识是有重迭的,，对一个大的程序来说，以元知识或说元规则形式体现控制知识更为方便，因为,元知识存于知识库中，而控制知识常与程序结合在一起出现，从而不容易修改,。,知识表示,知识表示：,是研究用机器表示知识的可行性、有效性的一般方法，是一种,数据结构,与,控制结构,的统一体，既考虑知识的,存储,又考虑知识的,使用,。,知识表示的要求：,表示能力：,能否,正确,、,有效,地表示问题。包括：表示范围的广泛性、领域知识表示的高效性、对非确定性知识表示的支持程度。,可利用性：,可利用这些知识,进行有效推理,。包括：对推理的适应性，对高效算法的支持程度。,可实现性：,要便于计算机直接对其进行处理,可组织性：,可以按某种方式把知识组织成,某种知识结构,可维护性：,便于对知识的增、删、改等操作,自然性：,符合人们的日常习惯,可理解性：,知识应易读、易懂、易获取等,内容提要,第二章：知识表示方法,1.,状态空间法,2.,问题归约法,3.,谓词逻辑法,4.,语义网络法,5.,其他方法,内容提要,第二章：知识表示方法,1.,状态空间法,2.,问题归约法,3.,谓词逻辑法,4.,语义网络法,5.,其他方法,状态空间法,人工智能虽然有多个研究领域，而且每个研究领域又各有自己的规律和特点，都可抽象为一个,“,问题求解,”,的过程。问题求解过程实际上是一个,搜索,过程。,问题求解技术主要是两个方面：,问题的表示,求解的方法,状态空间法,（State Space Representation）：,状态空间法就是用来表示问题及其搜索过程的一种方法。它是人工智能中最基本的形式化方法，用,“状态（state）”,和,“算符（operator）”,来表示问题。,状态空间法,状态空间法的三要素,(1)状态（state）：,描述某类不同事物间的差别而引入的一组最少变量 q,0,，q,1,，q,n,的有序集合，是表示问题解法中每一步问题状况的数据结构。有序集合中每个元素q,i,（i=0,1,.,n,）为集合的分量，称为,状态变量,。给定每个分量的一组值就得到一个具体的状态。,(2)算符（operator）：,使问题从一种状态变化为另一种状态的手段称为操作符或算符。,(3)状态空间方法：,是一个表示该问题,全部可能状态及其关系的图,，它包含三种说明的集合，即三元状态（S，F，G）。,S：所有可能的问题初始状态集合；F：操作符集合；G：目标状态集合。,状态空间法,状态空间法举例：,下棋、迷宫及各种游戏。,十五数码难题(15 puzzle)：,由15个编有1至15并放在4,4方格棋盘上的可走动的棋子组成。,11,9,4,15,1,3,12,7,5,8,6,13,2,10,14,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,初始棋局,目标棋局,十五数码难题,11,9,4,15,1,3,12,7,5,8,6,13,2,10,14,11,9,15,1,3,4,12,7,5,8,6,13,2,10,14,11,9,4,15,1,3,12,7,5,8,6,13,2,10,14,11,9,4,15,1,3,8,12,7,5,6,13,2,10,14,11,9,4,15,1,3,12,7,5,8,6,13,2,10,14,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,初始状态,目标状态,如何把初试棋局,变成目标棋局？,首先把适用的算符,用于初始状态，以产生新的状态,再把另一些适用算符用于这些新的状态；这样继续下去，直至产生目标状态为止,状态空间法,状态图示法：,状态空间的图示形式称为,状态空间图,。状态图中有几个术语。,节点(Node)：,图形上的汇合点，用来表示,状态,、,事件,和,时间关系的汇合,。,弧线(Arc)：,节点间的连接线，表示,算符,；,有向图(Directed Graph)：,一对节点用弧线连接起来，从一个节点指向另一个节点。,后继节点(Descendant node)与父辈节点(Parent node)：,如果某条弧线从节点n,i,指向节点n,j,，那么节点n,j,就叫做节点n,i,的,后继节点或后裔,，而节点n,i,叫做节点n,j,的,父辈节点或祖先,。,状态空间法,状态图示法：,状态空间的图示形式称为,状态空间图,。状态图中有几个术语。,路径(Path)：,某个节点序列(n,i1,n,i2,n,ik,)当,j,=2,3,k时，如果对于每一个n,i,j,-1,都有一个后继节点n,ij,存在，那么就把这个节点序列叫做从节点n,i1,至节点n,ik,的长度为k的路径。,代价(Cost)：,用c(n,i,n,j,)来表示从节点n,i,指向节点n,j,的 那段弧线的代价。,两节点间路径的代价,等于连接该路径上各节点的所有弧线代价之和。,图的显示说明/隐示说明：,指各节点及其具有代价的弧线可以/不可以由一张表明确给出。,显然，显示说明对于大型的图是不切实际的，而对于具有无限节点集合的图则是不可能的。,状态空间法,问题的表示对求解工作有很大影响。人们,希望有较小的状态空间表示,。,例如，对于十五数码问题：,可以规定15460条规则，即“上移棋子1，下移棋子1，左移棋子1，右移棋子1”，,如果用“上下左右移动空格”，则只需4条规则。所以，移动空格是一种较好的表示。,状态空间法,状态空间法举例：,猴子和香蕉问题：,在一个房间内有一只猴子、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢?,猴子和香蕉问题,解题过程,用一个四元表列（W，x，Y，z）来表示这个问题状态,W：猴子的水平位置；,x：当猴子在箱子顶上时取1；否则取0；,Y：箱子的水平位置；,z：当猴子摘到香蕉时取1；否则取0。,初始状态为(a,0,b,0)，目标状态为(c,1,c,1),这个问题的操作（算符）如下：,goto（U）表示猴子走到水平位置U,pushbox（V）猴子把箱子推到水平位置V,climbbox猴子爬上箱顶,grasp猴子摘到香蕉,猴子和香蕉问题,解题过程,该初始状态变换为目标状态的操作序列为：,Step1:goto(b),Step2:pushbox(c),Step3:climbbox,Step4:grasp,猴子和香蕉问题,状态空间图,(b,，,1,，,b,，,0),（,U,，,0,，,b,，,0,）,（,V,，,0,，,V,，,0,）,（,c,，,1,，,c,，,0,）,（,U,，,0,，,V,，,0,）,（,c,，,1,，,c,，,1,）,（,a,，,0,，,b,，,0,）,目标状态,goto,（,U,）,goto,（,U,）,U=b,，,climbbox,goto,（,U,）,U=b,pushbox,（,V,）,goto,（,U,）,U=V,V=c,，,climbbox,grasp,内容提要,第二章：知识表示方法,1.,状态空间法,2.,问题归约法,3.,谓词逻辑法,4.,语义网络法,5.,其他方法,问题归约法,问题归约（Problem Reduction）,是另外一种,基于状态空间,的问题描述与求解方法,已知问题的描述，通过一系列,变换,把此问题变为一个,子问题集合,这些子问题的解可以,直接得到（本原问题）,，从而解决了初始问题,问题归约法,问题归约法的组成部分,一个