搜索
1第二部分知识表示方法2知识是一切智能行为的基础，也是人工智能的重要研究对象。要使计算机具有智能，就必须使它具有知识，而要使计算机具有知识，首先必须解决知识的表示问题。知识表示包括知识表示的概念和知识表示方法。对知识表示方法，又可根据所表示知识的确定化程度，分为确定性知识表示和不确定性知识表示。31.知识与知识表示的概念2.状态空间法3.问题规约法4.谓词逻辑法5.语义网络法6.框架表示法内容提要41.知识与知识表示的概念一.知识1）.知识的属性2）.知识的类型二.知识表示1）.知识表示的要求2）.知识表示观点3）.知识表示的方法5知识是人们在改造客观世界的实践中积累起来的认识和经验。通常，人们对客观世界的描述是通过数据和信息来实现的。数据和信息是两个密切相关的概念。数据是信息的载体和表示，信息是数据在特定场合下的含义，或者说信息是数据的语义。一.知识6知识是对信息进行智能性加工所形成的对客观世界规律性的认识。把有关信息关联在一起所形成的信息结构称为知识。“信息”与“关联”是构成知识的两个要素。信息之间关联的形式可以多种多样，其中最常用的一种形式是：如果……，那么……。例如，“如果他学过人工智能课程，那么他应该知道什么叫知识”。7（1）真假性与相对性1）.知识的属性：•真假性是指可以通过实践或推理来证明知识为真或为假。•相对性是指知识的真与假是相对于某些条件、环境及时间而言的，即知识一般不是无条件的真或无条件的假，而是相对于一定条件的。8知识的不确定性包括不完备性、不确定性与模糊性：（2）不确定性•知识的不完备性是指在解决问题时不具备解决该问题所需要的全部知识。•知识的不确定性是指知识所具有的既不能完全被确定为真，又不能完全被确定为假的特性。•知识的模糊性是指知识的“边界”不明确的特性。9•矛盾性是指同一个知识集中的不同知识之间相互对立或不一致，即从这些知识出发，会推出不一致的结论。•相容性是指同一个知识集中的所有知识之间互相不矛盾。（3）矛盾性和相容性10•可表示性是指知识可以用适当的形式表示出来。例如语言、文字、图形、神经元网络等。•可利用性是指知识可以被用来解决各种各样的问题。（4）可表示性与可利用性11（1）按知识的性质：2）.知识的类型：•概念•命题•公理•定理•规则•方法12•常识性知识：是指通用通识的知识。即人们普遍知道的、适应于所有领域的知识。•领域性知识：是指面向某个具体专业的专业性知识，这些知识只有该领域的专业人员才能够掌握和运用它。（2）按知识的作用范围：13•事实性知识：也称叙述性知识，是用来描述问题或事物的概念、属性、状态、环境及条件等情况的知识。•过程性知识：是用来描述问题求解过程所需要的操作、演算或行为等规律性的知识，它指出在问题求解过程中如何使用那些与问题有关的事实性知识，即用来说明在那些叙述性知识成立的时候该怎么办。•控制性知识：也称元知识或超知识，是关于如何运用已有知识进行问题求解的知识，因此，也称为关于知识的知识。（3）按知识的作用14•表层知识是指客观事物的现象以及这些现象与结论之间关系的知识。•深层知识是指事物本质、因果关系内涵、基本原理之类的知识。例如，理论知识、理性知识等。（4）按知识的层次15•确定性知识：是可以给出其真值为“真”或“假”的知识。这些知识是可以精确表示的知识。•不确定性知识：是指具有“不确定”特性的知识。不确定性的概念包含不精确、不完备和模糊。（5）按知识的确定性16•逻辑性知识：是反映人类逻辑思维过程的知识，例如人类的经验性知识。它对应着逻辑思维。•形象性知识：是通过事物的形象建立起来的知识，它对应着形象思维。例如，一个人的相貌，要用文字来描述非常困难，但要亲眼见到这个人，就很容易在头脑中形成这个人的概念。（6）按知识的结构及表现形式17所谓知识表示是对知识的一种描述，即用一些约定的符号把知识编码成一组计算机可以接受的数据结构。所谓知识表示过程就是把知识编码成某种数据结构的过程。同一知识可以有多种不同的表示形式，而不同表示形式所产生的效果又可能不一样。二.知识表示18（1）表示能力知识表示能力是指能否正确、有效地将问题求解所需要的各种知识表示出来。知识表示能力包括以下三个方面：一是知识表示范围的广泛性；二是领域知识表示的高效性；三是对非确定性知识表示的支持程度。1）.知识表示的要求19（2）可利用性知识的利用是指使用知识进行推理，以求得问题的解。知识的可利用性包括对推理的适应性和对高效算法的支持性。（3）可组织性与可维护性知识的组织是指把有关知识按照某种方式组成一种知识结构。知识维护是指在保证知识的一致性与完整性的前提下对知识所进行的增加、删除、修改等操作。20（4）可实现性所谓可实现性是指知识表示要便于在计算机上实现，便于直接由计算机对其进行处理。（5）自然性与可理解性自然性是指知识表示形式要符合人们的日常习惯和思维方式。可理解性是指所表示的知识应易读、易懂、易获取、易维护。21（1）陈述性观点陈述性知识表示（Declarativeknowledgerepresentation）是指以陈述的方式把知识用一定的数据结构表示出来，即把知识看作一种特殊的数据，知识表示说明描述的对象是什么，不涉及如何运用知识的问题。2）.知识表示观点：22（2）过程性观点过程性知识表示（Proceduralknowledgerepresentation）是指以程序（亦称为过程）的方式把知识表示出来，即把知识寓于程序之中，把知识表示和运用知识结合起来。23知识表示方法又称为知识表示技术，其表示形式被称为知识表示模式。目前，使用较多的知识表示方法有:•状态空间法•问题归约法•谓词逻辑法•语义网络法•框架表示法•剧本表示法•过程表示法•面向对象表示法3）.知识表示方法：24一.问题的状态描述二.状态图示法三.状态空间表示举例2.状态空间法25对人工智能研究中运用的问题求解方法进行综合分析，可以发现许多问题求解方法是采用试探搜索方法的。是通过在某个可能的解空间内寻找一个解来求解问题的。这种基于解答空间的问题表示和求解方法就是状态空间法。状态空间法是以状态和算符为基础来表示和求解问题的。26实例：十五数码难题一.问题的状态描述如何把初始棋局变换为目标棋局？27最直接的求解方法：尝试各种不同的走步，直到偶然得到目标棋局为止，即试探搜索。28对十五数码难题的问题描述和求解过程进行分析：初始状态：初始棋局[11，9，4，15，1，3，0，12，7，5，8，6，13，2，10，14]操作符：走步右移棋子3，下移棋子4，左移棋子12，….（60条）或者：移动空格（4条）目标状态：目标棋局[1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，0]状态空间法：从某个初始状态开始，每次加一个操作符，递增地建立起操作符的试验序列，直到达到目标状态为止。状态图：初始状态可达到的各状态所对应的节点组成的图。29问题状态的描述：状态：为描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合，其矢量形式如下：Q=[q0，q1，…，qn]状态变量：状态集合中的每个元素qi（i=0,1,…,n）。具体状态：给定每个分量的一组值。如Qk=[q0k，q1k，…，qnk]操作符：使问题从一种状态变换到另一种状态的手段，也叫算符。算符可以是走步、过程、规则、数学算子、运算符号或逻辑符号等。问题的状态空间：表示该问题全部可能状态及其关系的图。它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。状态空间可记为三元组（S，F，G）30图论中的几个术语：图；有向图；后继节点（后裔）；父辈节点（祖先）；路径（长度为k的路径）；节点nj是从节点ni可达到的路径；代价；两节点间路径的代价。当用一个图来表示某个状态空间时，图中各节点标上相应的状态描述，而有向弧线旁边标上算符。寻找从一种状态变换为另一种状态的某个算符序列问题等价于寻找图的某一路径问题。二.状态图示法31图的显式说明：图中的各节点及其具有代价的弧线由一张图或表明确给出。图的隐式说明：图中的节点集合是无限的，但起始节点是已知的，而且引入后继算符的概念是方便的。把后继节点算符作用于任一节点可以产生该节点的全部后继节点和各连接弧线的代价。搜索某个状态空间以求得算符序列的一个解答过程，就是使隐式图足够大的一部分变为显式以便包含目标的过程，这是状态空间问题求解的基础。问题的表示对求解工作量有很大的影响。32问题的状态表示方法涉及在状态描述中如何应用变量。须用一个包含变量的表达式来描述状态的全部集合，而不仅仅描述一个状态。用常量取代表达式中的变量，就可得到一个具体的状态描述。用来描述一个状态集合的含有变量的表达式，叫做状态描述模式。33三.状态空间表示举例实例：猴子摘香蕉问题acb箱子34问题状态的表示：四元组（W，x，Y，z）W：猴子的水平位置。W=a，b，c。x：当猴子在箱子顶上时取x=1；否则取x=0。Y：箱子的水平位置。Y=a，b，c。z：当猴子摘到香蕉时取z=1；否则取z=0。初始状态：（a，0，b，0）目标状态：（c，1，c，1）35算符集合：goto(b)：猴子走到水平位置b。（a，0，b，z）goto(U)（b，0，b，z）pushbox(c)：猴子把箱子推到水平位置c。（b，0，b，z）pushbox(V)（c，0，c，z）climbbox：猴子爬上箱顶。（c，0，c，z）climbbox（c，1，c，z）grasp：猴子摘到香蕉。（c，1，c，0）grasp（c，1，c，1）算符的适用性条件：强加于操作的实用性条件。如：应用算符pushbox(c)时，要求猴子与箱子必须在同一位置36操作序列：{goto(b)，pushbox(c)，climbbox，grasp}猴子摘香蕉问题的状态空间图37练习题(野人和传教士渡河问题）：有3个传教士和3个野人来到河边，打算乘一艘小船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去？383.问题归约法一.问题规约的描述二.与或图表示三.问题归约机理39问题归约法：有许多问题可以通过一系列变换变为一个子问题集；这些子问题的解可以直接得到；通过解决这些子问题，从而就解决了初始问题。40实例：梵塔问题一.问题的归约描述如何由初始配置变换为目标配置？123123初始配置目标配置41求解思路：把原始问题归约为一个比较简单的问题的集合ABC123ABC123111122ABC123ABC123122322ABC123ABC123322333要把所有圆盘都移至柱子3，必须先把圆盘C移至柱子3；而且在移动圆盘C至柱子3之前，柱子3必须是空的。只有在移开圆盘A和B之后，才能移动圆盘C；而且圆盘A和B不能在柱子3。因此，应该把A和B移到柱子2上。把圆盘C从柱子1移动到柱子3，并继续解决其余部分的移动问题。（移动A、B-2）（移动C-3）（移动A、B-3）42通过以上分析，把原始问题归约为3个子问题：（1）移动A、B-2双圆盘问题：可进一步归约（2）移动C-3单圆盘问题：可直接求解--本原问题（3）移动A、B-3双圆盘问题：可进一步归约与或图：可以有效说明问题归约法的求解过程。梵塔问题归约图43问题归约描述：采用问题归约法描述与求解问题，问题归约表示由三部分组成：（1）一个初始问题描述如：[（111），（333）]（2）一套把问题变换为子问题的操作符—问题归约算符如：移动A、B-2等（3）一套本原问题描述如：[（122），（322）]本原问题：是可直接求解或具有已知解答的问题，出现本原问题即可停止搜索。问题归约法的实质：从目标（要解决的问题）出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个本原问题集合。问题归约的目的：最终产生具有明显解答的本原问题。44二.与或图表示用问题归约法描述和求解问题的过