人工智能及其应用知识.pptx
《人工智能及其应用知识.pptx》由会员分享，可在线阅读，更多相关《人工智能及其应用知识.pptx（113页珍藏版）》请在冰点文库上搜索。
第二章知识表示,本章主要讨论知识表示问题，介绍7种知识表示方法：
状态空间法、问题归约法、谓词演算法、语义网络法、框架表示、本体技术、过程表示。
掌握状态空间法、问题归约法、谓词演算法、语义网络法的要点及其之间的关系，了解框架表示、本体技术、过程表示。
知识表示的基本概念,知识表示：
研究用机器表示知识的可行性、有效性的一般方法，是一种数据结构与控制结构的统一体，既考虑知识的存储又考虑知识的使用。
知识表示可看成是一组描述事物的约定，以把人类知识表示成机器能处理的数据结构。
人工智能系统所关心的知识,事实有关问题环境的一些事物的知识，常以“是”的形式出现。
如事物的分类、属性、事物间关系、科学事实、客观事实等。
如雪是白色的、鸟有翅膀、张三李四是好朋友、这辆车是张三的。
规则有关问题中与事物的行动、动作相联系的因果关系知识，是动态的，常以“如果那么”形式出现。
控制有关问题的求解步骤、技巧性知识，告诉怎么做一件事。
元知识有关知识的知识，是知识库中的高层知识。
包括怎样使用规则、解释规则、校验规则、解释程序结构等知识。
2.1状态空间法,问题求解问题求解（problemsolving）是个大课题，它涉及归约、推断、决策、规划、常识推理、定理证明和相关过程的核心概念。
在分析了人工智能研究中运用的问题求解方法之后，就会发现许多问题求解方法是采用试探搜索方法的。
也就是说，这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。
状态空间法：
基于解答空间的问题表示和求解方法，它是以状态和算符（operator）为基础来表示和求解问题的。
2.1状态空间法,1.问题求解技术两个主要的方面
（1）问题的表示：
如果描述方法不对，对问题求解会带来很大的困难；
（2）求解的方法：
采用试探搜索方法。
2.状态空间法三要点
（1）状态（state）
（2）算符（operator）（3）状态空间方法,2.1状态空间法,2.1.1问题状态描述1.定义状态（state）：
为描述某类不同事物间的差别而引入的一组最少变量q0，q1，qn的有序集合，其矢量形式如下：
Q=q0,q1,qnT式中每个元素qi（i=0,1,n）为集合的分量,称为状态变量,给定每个分量的一组值就得到一个具体的状态,如Qk=q0k,q1k,qnkT式中每个元素qi（i=0,1，n）为集合的分量，称为状态变量。
算符：
使问题从一种状态变化为另一种状态的手段称为操作符或算符。
操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。
问题的状态空间（statespace）：
是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。
可把状态空间记为三元状态（S，F，G）。
2.1状态空间法,2.状态空间表示详释让我们先用数码难题（puzzleproblem）来说明状态空间表示的概念。
由15个编有1至15并放在44方格棋盘上的可走动的棋子组成。
棋盘上总有一格是空的，以便可能让空格周围的棋子走进空格，这也可以理解为移动空格。
图中绘出了两种棋局，即初始棋局和目标棋局，它们对应于该下棋问题的初始状态和目标状态。
如何把初始棋局变换为目标棋局呢？
问题的解答就是某个合适的棋子走步序列，如左移棋子12，下移棋子15，右移棋子4，等等。
2.1状态空间法,2.状态空间表示详释状态空间法：
从某个初始状态开始，每次加一个操作符，递增的建立起操作符的试验序列，直到达到目标状态为止。
寻找状态空间的全部过程包括从旧的状态描述产生新的状态描述，以及此后检验这些新的状态描述，看是否达到了该目标状态。
对于最优化问题找到任一目标状态是不够的，必须按某个准则实现最优化路径。
P26完成目标状态的三件事：
状态描述方式，特别是初始状态描述；操作符集合及其对状态描述的作用；目标状态的特性。
2.1状态空间法,2.1.2状态图示法为了对状态空间图有更深入的了解，这里介绍一下图论中的几个术语和图的正式表示法。
1.图论中的几个术语节点（node）：
图形上的汇合点，用来表示状态、事件和时间关系的汇合，也可用来指示通路的汇合；弧线（arc）：
节点间的连接线；有向图（directedgraph）：
一对节点用弧线连接起来，从一个节点指向另一个节点。
后继节点（descendantnode）与父辈节点（parentnode）：
如果某条弧线从节点ni指向节点nj，那么节点nj就叫做节点ni的后继节点或后裔，而节点ni叫做节点nj的父辈节点或祖先。
2.1状态空间法,2.1.2状态图示法1.图论中的几个术语路径：
某个节点序列（ni1,ni2,nik）当j=2，3，k时，如果对于每一个ni，j-1都有一个后继节点nij存在，那么就把这个节点序列叫做从节点ni1至节点nik的长度为k的路径。
代价：
用c（ni,nj）来表示从节点ni指向节点nj的那段弧线的代价。
两节点间路径的代价等于连接该路径上各节点的所有弧线代价之和。
显式表示：
各节点及其具有代价的弧线由一张表明确给出。
此表可能列出该图中的每一节点、它的后继节点以及连接弧线的代价。
隐式表示：
节点的无限集合si作为起始节点是已知的。
后继节点算符也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价。
2.1状态空间法,2.1.2状态图示法2.图的显式和隐式表示一个图可由显式说明也可由隐式说明。
显然，显式说明对于大型的图是不切实际的，而对于具有无限节点集合的图则是不可能的。
此外，引入后继节点算符的概念是方便的。
后继节点算符也是已知的，它能作用于任一节点以产生该节点的全部后继节点和各连接弧线的代价把后继算符应用于si的成员和它们的后继节点以及这些后继节点的后继节点，如此无限制地进行下去，最后使得由和si所规定的隐式图变为显示图。
问题的表示对求解工作量有很大的影响。
人们显然希望有较小的状态空间表示。
许多似乎很难的问题，当表示适当时就可能具有小而简单的状态空间。
2.1状态空间法,2.1.2状态图示法根据问题状态、操作符和目标条件选择各种表示，是高效率问题求解必须的。
各种问题都可以用状态空间加以表示，并用状态空间搜索法来求解。
2.1状态空间法,2.1.2状态图示法1.产生式系统（ProductionSystem）一个总数据库（globaldatabase）：
它含有与具体任务有关的信息；随着应用情况的不同，这些数据库可能小得像数字矩阵那样简单，或许大得如检索文件结构那么复杂。
一套规则：
它对数据库进行操作运算。
每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。
用规则来改变数据库就象用算符来改变状态一样。
一个控制策略：
它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。
控制策略由控制系统选择和确定。
推销员旅行问题,总数据库：
到目前为止所访问的城市；规则对应于决策：
即下一步走向城市，下一步走向城市，下一步走向城市，一条规则必须能把某个数据库变为一个合法数据库，否则不适应这个数据库；任一以为起点和终点，并出现所有其它城市的总数据库，都满足终止条件,2.1状态空间法,2.1.2状态图示法2.状态空间表示举例例2猴子和香蕉问题（monkeyandbananaproblem）在一个房间内有一只猴子（可把这只猴子看做一个机器人）、一个箱子和一束香蕉。
香蕉挂在天花板下方，但猴子的高度不足以碰到它。
那么这只猴子怎样才能摘到香蕉呢?
图2.4表示出猴子、香蕉和箱子在房间内的相对位置。
猴子和香蕉.用一个四元表列（W,X,Y,Z）来表示这个问题的状态，其中W猴子的水平位置X当猴子在箱子顶上时取X=1；否则取X=0Y箱子的水平位置Z当猴子摘到香蕉时取Z=1；否则取Z=0图2.4猴子和香蕉问题,2.1状态空间法,2.1.2状态图示法这个问题中的操作（算符）如下：
（1）goto（U）猴子走到水平位置U，或者用产生式规则表示为：
（W，0，Y，z）（U，0，Y，z）（2.3）即应用操作goto（U），能把状态（W，0，Y，z）变换为状态（U，0，Y，z）。
（2）pushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z）（V，0，V，z）（2.4）应当注意的是，要应用算符pushbox（V），就要求产生式规则的左边，猴子与箱子必须在同一位置上，并且，猴子不是在箱子顶上。
这种强加于操作的适用性条件，叫做产生式规则的先决条件。
2.1状态空间法,2.1.2状态图示法这个问题中的操作（算符）如下：
（3）climbbox猴子爬上箱顶，即有（W，0，W，z）（W，1，W，z）（2.5）在应用算符climbbox时也必须注意到，猴子和箱子应当在同一位置上，而且猴子不在箱顶上。
（4）grasp猴子摘到香蕉，即有（c,1,c,0）（c,1,c,1）（2.6）其中，c是香蕉正下方的地板位置，在应用算符grasp时，要求猴子和箱子都在位置c上，并且猴子已在箱子顶上。
2.1状态空间法,对于规则
（2），只有当算符pushbox（V）的先决条件，即猴子与箱子在同一位置上而且猴子不在箱顶上这些条件得到满足时，算符pushbox（V）才是适用的。
这一操作算符的作用是猴子把箱子推到位置V。
在这一表示中，目标状态的集合可由任何最后元素为1的表列来描述。
令初始状态为（a,0,b,0）这时，goto（U）是唯一适用的操作，并导致下一状态（U,0,b,0）。
现在有3个适用的操作，即goto（U），pushbox（V）和climbbox（若U=b）。
猴子和香蕉问题的状态空间图,2.2问题归约法,2.2.1问题归约描述先把问题分解为子问题和子-子问题，然后解决较小的问题。
对该问题的某个具体子集的解答就意味着对原始问题的一个解答。
问题归约表示的组成部分：
一个初始问题描述；一套把问题变换为子问题的操作符；一套本原问题描述。
问题归约的实质：
从目标（要解决的问题）出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。
2.2问题归约法,2.2.1问题归约描述梵塔难题有3个柱子（1，2和3）和3个不同尺寸的圆盘（A，B和C）。
在每个圆盘的中心有一个孔，所以圆盘可以堆叠在柱子上。
最初，3个圆盘都堆在柱子1上：
最大的圆盘C在底部，最小的圆盘A在顶部。
要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。
这个问题的初始配置和目标配置如图2.6所示。
2.2问题归约法,解题过程：
将原始问题归约为一个较简单问题集合，要把所有圆盘都移至柱子3，我们必须首先把圆盘C移至柱子3；而且在移动圆盘C至柱子3之前，要求柱子3必须是空的。
只有在移开圆盘A和B之后，才能移动圆盘C；而且圆盘A和B最好不要移至柱子3，否则就不能把圆盘C移至柱子3。
因此，首先应该把圆盘A和B移到柱子2上。
然后才能够进行关键的一步，把圆盘C从柱子1移至柱子3，并继续解决难题的其余部分。
将原始难题归约（简化）为下列子难题：
移动圆盘A和B至柱子2的双圆盘难题，如图（a）所示。
2.2问题归约法,图2.7梵塔问题解答（a）,图2.8梵塔问题解答（b）,图2.9梵塔问题解答（c）,2.2问题归约法,梵塔问题归约图：
子问题2可作为本原问题考虑，因为它的解只包含一步移动。
应用一系列相似的推理，子问题1和子问题3也可被归约为本原问题，如图2.10所示。
这种图式结构，叫做与或图（AND/ORgraph）。
它能有效地说明如何由问题归约法求得问题的解答。
梵塔问题归约图,2.2问题归约法,2.2.1问题归约描述问题归约描述问题归约方法应用算符把问题描述变换为子问题描述，问题描述可以用多种数据结构形式，包括表列、树、字符串、矢量、数组等。
梵塔问题采用包含两个数列的表列来描述,（113）,（333）表示把配置（113）变换为配置（333）。
用状态空间表示的三元组合（S，F，G）来规定与描述问题，有关子问题可以当作状态空间中的两个一定的“脚踏石”之间寻找路径来辨别。
梵塔问题中的子问题（111）=（122），（122）=（322），（322）=（333），规定了最后的路径将要通过“脚踏石”状态（122）和（322）。
2.2问题归约法,2.2.2与或图表示与图、或图、与或图：
一般地，我们用一个类似图的结构来表示把问题归约为后继问题的替换集合，这种结构图叫做问题归约图，或叫与或图。
如下图所示:
（引入附加节点使含有一个以上后继问题的每个集合能够聚集在它们各自的父辈节点之下。
）,子问题替换集合结构图,与或图,2.2问题归约法,2.2.2问题归约描述一些关于与或图的术语：
终叶节点：
对应于原问题的本原节点。
或节点：
只要解决某个问题就可解决其父辈问题的节点集合，如（M，N，H）。
与节点：
只有解决所有子问题，才能解决其父辈问题的节点集合，如（B,C）和（D,E,F）各个结点之间用一端小圆弧连接标记。
2.2问题归约法,2.2.2问题归约描述与或图：
由与节点及或节点组成的结构图。
可解节点的一般定义：
（1）终叶节点是可解节点（因为它们与本原问题相关连）。
（2）如果某个非终叶节点含有或后继节点，那么只要当其后继节点至少有一个是可解的时，此非终叶节点才是可解的。
（3）如果某个非终叶节点含有与后继节点，那么只有当其后继节点全部为可解时，此非终叶节点才是可解的。
图2.15与或图例子,2.2问题归约法,2.2.2问题归约描述不可解节点的一般定义:
（1）没有后裔的非终叶节点为不可解节点。
（2）如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不可解的。
（3）如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点才是不可解的。
2.2问题归约法,2.2.2问题归约描述与或图构成规则
（1）与或图中的每个节点代表一个要解决的单一问题或问题集合。
图中所含起始节点对应于原始问题。
（2）对应于本原问题的节点，叫做终叶节点，它没有后裔。
（3）对于把算符应用于问题A的每种可能情况，都把问题变换为一个子问题集合；有向弧线自A指向后继节点表示所求得的子问题集合，如下图所示，把问题A归约为3个不同的子问题集合N，M，H（或节点）。
图2.16与或树,2.2问题归约法,2.2.2问题归约描述与或图构成规则（4）一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的各个节点。
由于只有当集合中所有的项都有解时，这个子问题的集合才能获得解答，所以这些子问题节点叫做与节点。
（5）在特殊情况下，当只有一个算符可应用于问题A，而且这个算符产生具有一个以上子问题的某个集合时，由上述规则3和规则4所产生的图可以得到简化。
因此，代表子问题集合的中间或节点可以被略去，如右图所示。
图2.16与或树,2.3谓词逻辑法,2.3.1谓词演算（PredicateCalculus）1.语法和语义（Syntax&Semantics）谓词逻辑的基本组成部分：
谓词符号、变量符号、函数符号和常量符号，并用圆括号、方括号、花括号和逗号隔开，表示论域内的关系。
原子公式（atomicformulas）由若干谓词符号和项组成的谓词演算。
原子公式是谓词演算基本积木块。
例如，要表示机器人（ROBOT）在号房间（r1）内，如图2.19所示，可以应用原子公式:
2.3谓词逻辑法,2.3.1谓词演算（PredicateCalculus）1.语法和语义（Syntax&Semantics）当机器人ROBOT移到房间r2时，原子公式可以表示为：
INROOM（ROBOT,r2）这两个原子公式的通用形式就是又如,“李的母亲和他的父亲结婚”这句话的原子公式表示如下：
2.3谓词逻辑法,2.3.1谓词演算（PredicateCalculus）2.连词和量词（Connective&Quantifiers）
（1）连词与合取（conjunction）合取就是用连词把几个公式连接起来而构成的公式。
合取项是合取式的每个组成部分。
例：
LIKE（I，MUSIC）LIKE（I，PAINTING）（我喜爱音乐和绘画。
）,2.3谓词逻辑法,2.3.1谓词演算（PredicateCalculus）2.连词和量词（Connective&Quantifiers）或析取（disjunction）析取就是用连词把几个公式连接起来而构成的公式。
析取项是析取式的每个组成部分。
例：
PLAYS（LILI，BASKETBALL）PLAYS（LILI，FOOTBALL）（李力打篮球或踢足球。
）,2.3谓词逻辑法,2.3.1谓词演算（PredicateCalculus）2.连词和量词（Connective&Quantifiers）
（1）连词蕴涵=表示如果-那么的语句。
用连词=连接两个公式所构成的公式叫做蕴涵。
IF=THEN前项后项（左式）（右式）例：
RUNS（LIUHUA，FASTEST）=TWINS（LIUHUA，CHAMPION）（如果刘华跑得最快，那么他取得冠军）非（NOT）表示否定，、均可表示否定。
例：
INROOM（ROBOT，r2）（机器人不在2号房间内。
）,2.3谓词逻辑法,2.3.1谓词演算（PredicateCalculus）2.连词和量词（Connective&Quantifiers）
（2）量词全称量词（UniversalQuantifier）若一个原子公式P（x），对于所有可能变量x都具有T值，则用（x）P（x）表示。
例：
（x）ROBOT（x）=COLOR（x,GRAY）（所有的机器人都是灰色的）（x）Student（x）=Uniform（x,Color）（所有学生都穿彩色制服）,2.3谓词逻辑法,2.3.1谓词演算（PredicateCalculus）2.连词和量词（Connective&Quantifiers）
（2）量词存在量词（ExistentialQuantifier）若一个原子公式P（x），至少有一个变元X，可使P（X）为T值，则用（x）P（x）表示。
例：
（x）INROOM（x,r1）（1号房间内有个物体）量化变元（QuantifiedVariables）被量化了的变元x-约束变量。
2.3谓词逻辑法,2.3.2谓词公式（PredicateFormulas）1.谓词公式的定义原子谓词公式：
用P（x1,x2,xn）表示一个n元谓词公式，其中P为n元谓词，x1,x2,xn为客体变量或变元。
通常把P（x1,x2,xn）叫做谓词演算的原子公式，或原子谓词公式。
分子谓词公式：
可以用连词把原子谓词公式组成复合谓词公式，并把它叫做分子谓词公式。
合适公式（WFF,well-formedformulas）的递归定义：
（1）原子谓词公式是合适公式。
（2）若A为合适公式，则A也是一个合适公式。
（3）若A和B都是合适公式，则（AB）,（AB）,（A=B）,（AB）也都是合适公式。
（4）若A是合适公式，x为A中的自由变元，则（x）A,（x）A都是合适公式。
（5）只有按上述规则
（1）至（4）求得的那些公式，才是合适公式。
2.3谓词逻辑法,2.3.2谓词公式（PredicateFormulas）1.谓词公式的定义例题：
对于所有的x，如果x是整数，则x或为正的或者为负的。
（x）（I（x）=（P（x）N（x）I（x）表示x是整数，P（x）表示x是正数，N（x）表示x是负数。
2.3谓词逻辑法,2.3.2谓词公式（PredicateFormulas）2.合适公式的性质合适公式的真值：
p36表2-1真值表,2.3谓词逻辑法,2.3.3置换与合一（Substitution&Unification）1.置换在谓词逻辑中，有些推理规则可应用于一定的合适公式和合适公式集，以产生新的合适公式。
一个重要的推理规则是假元推理，这就是由合适公式W1和W1=W2产生合适公式W2的运算。
另一个推理规则叫做全称化推理，它是由合适公式（x）W（x）产生合适公式W（A），其中A为任意常量符号。
假元推理：
全称化推理：
综合推理：
2.3谓词逻辑法,2.3.3置换与合一（Substitution&Unification）1.置换置换：
用项（A）替换函数表达式中的变量（x），记为ES，即表示一个表达式E（Expression）用一个置换S（Substitution）而得到的表达式的置换。
例1表达式Px,f（y）,B的4个置换为s1=z/x,w/ys2=A/ys3=q（z）/x,A/ys4=c/x,A/y我们用Es来表示一个表达式E用置换s所得到的表达式的置换。
于是，我们可得到Px,f（y）,B的4个置换的例，如下：
Px,f（y）,Bs1=Pz,f（w）,BPx,f（y）,Bs2=Px,f（A）,BPx,f（y）,Bs3=Pq（z）,f（A）,BPx,f（y）,Bs4=Pc,f（A）,B,2.3谓词逻辑法,2.3.3置换与合一（Substitution&Unification）2.性质可结合律（LS1）S2=L（S1S2）（L表示一表达式）（S1S2）S3=S1（S2S3）置换是可结合的。
用s1s2表示两个置换s1和s2的合成。
L表示一表达式，则有（Ls1）s2=L（s1s2）以及（s1s2）s3=s1（s2s3）即用s1和s2相继作用于表达式L是同用s1s2作用于L一样的。
一般说来，置换是不可交换的，即s1s2s2s13.合一（unification）P38合一：
寻找项对变量的置换，以使两表达式一致。
可合一：
如果一个置换s作用于表达式集Ei的每个元素，则我们用Eis来表示置换例的集。
我们称表达式集Ei是可合一的。
2.3谓词逻辑法,2.3.3置换与合一（Substitution&Unification）例:
表达式集Px,f（y）,B,Px,f（B）,B的合一者为:
s=A/x,B/y因为Px,f（y）,Bs=Px,f（B）,B=PA,f（B）,B即s使表达式成为单一形式:
PA,f（B）,B,但最简单的合一者为:
s=B/Y,2.4语义网络法,语义网络是1968年Quilian在研究人类联想记忆时提出的心理学模型，认为记忆是由概念间的联系来实现的。
1972年，Simmons首先将语义网络表示法用于自然语言理解系统。
语义网络的结构：
语义网络是知识的一种图解表示，它由节点和弧线或链线组成。
节点用于表示实体、概念和情况等，弧线用于表示节点间的关系。
组成部分:
1词法部分：
决定表示词汇表中允许有哪些符号，它涉及各个节点和弧线。
2结构部分：
叙述符号排列的约束条件，指定各弧线连接的节点对。
3过程部分：
说明访问过程，这些过程能用来建立和修正描述，以及回答相关问题。
4语义部分：
确定与描述相关的（联想）意义的方法即确定有关节点的排列及其占有物和对应弧线。
2.4语义网络法,2.4.1二元语义网络的表示（RepresentationofTwo-ElementSemanticNetwork）1.表示简单的事实例1.所有的燕子都是鸟,2.4语义网络法,2.4.1二元语义网络的表示（RepresentationofTwo-ElementSemanticNetwork）2.表示占有关系和其它情况P40例2.小燕是一只燕子，燕子是鸟；巢-1是小燕的巢，巢-1是巢中的一个。
3.选择语义基元试图用一组基元来表示知识，以便简化表示，并可用简单的知识来表示更复杂的知识。
2.4语义网络法,例3.我椅子的颜色是咖啡色的；椅子包套是皮革；椅子是一种家具；椅子是座位的一部分；椅子的所有者是X；X是个人，如下图所示：
2.4语义网络法,2.4.2多元语义网络的表示语义网络是一种网络结构。
节点之间以链相连。
多元语义网络表示的实质：
把多元关系转化为一组二元关系的组合，或二元关系的合取。
如果所要表示的知识是一元关系，例如，要表示李明是一个人，这在
升级会员 