人工智能期末复习.docx

1.人工智能（学科）：Artificial Intelligence是计算机科学中涉及研究、设计和应用智能机器的一个分支。它的近期目标在于研究用机器来模仿和执行人脑的某些智能功能，并开发相关的理论和技术。在人工智能中，重点关注两个方面的内容：问题的表示（知识的表示）：即要找到问题的一种合适的表示方法在人工智能中，我们要涉及到：状态空间法、问题归约法、谓词逻辑法、样本向量法问题的求解：从问题表示方法出发，找到一个合理的办法来求解在人工智能中，常有的方法有：搜索法、推理法、计算方法2. 状态空间法：从某一个初始状态开始，每次施加一个操作符，递增地建立操作符序列，直到达到目标状态为止人工智能中，一种最基本的求解方法就是试探搜索法，即，通过在某个可能的解空间（例如，所有可能的走法）中寻找一个解。这种基于解空间的问题表示和求解方法就是状态空间法，其基础是状态和算符（算子）状态空间法表示问题的关键：状态与操作符状态：为了描述某一类不同事物间的差别而引入的一组最少变量的有序集合算符（操作符）：使问题从一个状态变换到另一状态的手段用状态空间法表达出原始问题后，欲解问题变成为：寻找从初始状态到目标状态的某一个操作符序列状态空间法的求解过程：用有向图来表示图是由节点（不一定是有限个的节点）的集合构成的注意：在图论中，图的定义中还包括边的集合无向图：一对节点可能互为后裔，边用线段来表示有向图：一对节点用弧线连接起来，并且从一个节点指向另一个节点对应关系：当用有向图来表示状态空间法时，对应关系：图中的一个节点对应于某一个状态图中的一个有向弧对应于某一个算符状态空间法的解：从初始状态到目标状态的操作符序列 图中的解：从起始节点到目标节点的一条路径问题：寻找从初始状态到目标状态的某个操作符序列转化为寻找图中初始节点（对应初始状态）到目标节点（对应于目标状态）的一条路径求解思路：边扩展节点边找解的搜索思想问题的状态空间：一个表示问题全部可能状态及其关系的图，它包含了三个集合： 所有可能的问题初始状态集合S 操作符集合F 目标状态集合G状态空间记作三元状态（S, F, G）3. 代价g(n) ：从起始节点 S 到某一节点 n 的路径的实际代价估值函数 f (n) ：从起始节点S、通过节点n、到达目标节点G的最小代价的一个估计值 f ( n ) = g ( n ) + h ( n )利用图论的技术，我们要解决两个问题：第一、找出初始节点到目标节点的一条路径。对应于寻找初始状态到目标状态的操作符序列（能够解决问题）第二、找出初始节点到目标节点的一条代价最小的路径。对应于寻找将初始状态变换到目标状态所用操作符代价之和最小的操作符序列（更好地解决问题）4. 图的搜索技术分：盲目搜索技术（宽度、深度、代价优先搜索技术）启发式搜索技术（有序搜索算法）差别：选取待扩展节点的规则不同，并且可以OPEN表的不同数据结构来体现算法有解的终止条件不同图搜索中的两个重要记号（符号）：OPEN 表：存放待扩展的节点CLOSED 表：存放已扩展的节点注意：在与或树搜索中也要用到这两张表盲目搜索技术盲目搜索是指无问题先验信息的搜索技术特点：OPEN表中节点的排列是人为规定的；一般只适合于求解比较简单的一些问题宽度优先：先扩展出来的节点优先（OPEN 为队列），后继节点有目标节点结束OPEN 表是存放待扩展的节点，从数据结构上来说，它是一个先进先出的队列CLOSED 表是存放已被扩展过的节点（包括有后继节点的非端节点和无后继节点的端节点）,可以看成只进不出的队列深度优先：后者扩展出来的节点优先（OPEN 为堆栈） ，且有深度限制，后继节点有目标节点结束OPEN表是一个堆栈，后进先出代价优先（等代价）：到起始节点代价小的节点优先（ OPEN 为线性表），具有最小代价的节点是目标节点时结束三种盲目搜索技术的比较主要差别：在于挑选要扩展节点的规则不同宽度优先搜索技术：先扩展出来的节点随后先扩展，OPEN表是队列深度优先搜索技术：后扩展出来的节点随后先扩展，OPEN表是堆栈等代价搜索技术：选取OPEN表中代价最小的节点先扩展，OPEN表是线性表（以局部代价的递增顺序排列）宽度和深度优先搜索的缺点：扩展节点的顺序是人为规定的，要扩展节点的数目可能非常大，占用大量的计算时间和内存空间，使得搜索效率低等代价搜索技术的 缺点选取已经搜索到的代价最小的节点来扩展，但是没有考虑目标状态，不知道离目标状态还有多远，还需要付出多大的代价启发式搜索技术有序算法：估价函数值小的节点优先有解的结束条件：具有最小估价函数值的节点是目标节点启发式搜索方法：利用启发信息的搜索方法有序搜索：在搜索过程总是选择“ 最有希望 ”的节点作为下一个被扩展节点的搜索技术在搜索过程中，OPEN表中节点按照其估价函数值以递增顺序排列，选择OPEN表中具有最小估价函数值的节点作为下一个待扩展的节点，这种搜索方法称为有序搜索估价函数：用来估算节点“ 希望 ”程度的函数估价函数的基本特性：一般情况下，估计函数值越大，希望程度就越低根据搜索过程、问题的启发信息来定义的，对搜索效率会产生较大的影响节点 n 的估价函数 f ( n ) 定义为从初始节点、经过 n 、到达目标节点的路径的最小代价的估计值，即 f ( n ) = g ( n ) + h ( n )g ( n ) 是从初始节点到达当前节点 n 的实际代价h ( n ) 是从节点 n 到目标节点的最佳路径的估计代价h ( n ) 体现出搜索过程中采用的启发式信息（背景知识），称之为启发函数g ( n ) 所占的比重越大，越趋向于宽度优先或等代价搜索；反之，h ( n ) 的比重越大，表示启发性能就越强例：八数码问题的估价函数 f ( n )= g ( n ) + h ( n )g ( n ) 定义为搜索树中 n 的深度h ( n ) 可以定义成不同形式（节点 n 的状态与目标状态之间数字不在位的个数（错放棋子的个数，不算空格）5.问题归约法、与或树搜索技术问题归约法：从已知问题的描述出发，通过一系列变换或分解将问题最终变为一个子问题集合，这些子问题的解可以直接得到，从而解决初始问题问题归约法表示问题的关键：原始问题描述、本原问题描述、操作符操作符：将问题转换或分解为子问题的手段本原问题：一组可以直接得出答案的简单问题问题归约法可以用一个三元组（S, O, P）来表示，其中： S：原始问题，即要解决的问题 P：本原问题集，其中的每一个问题是不用证明的或自然成立的，例如公理、已知事实等 O：操作算子集，用于将问题化为子问题问题归约法的基本思路是：应用一系列算符将原始问题的描述变换或分解成为子问题的描述问题的描述可以采用各种数据结构，如表、树、矢量、数组等与或图的特例：所有节点都是或节点，这时就是一般的图，即状态空间法用到的图除了起始节点外，所有节点只有一个父节点，此时称为与或树，问题归约法的求解过程：用与或图来表示“或节点”有解的条件是：只要有一个后继节点可解“或节点”无解的条件是：所有后继节点无解“与节点”有解的条件是：所有后继节点有解“与节点”无解的条件是：只要有一个后继节点无解判断节点是否可解的方法：终叶节点是可解节点无后继节点的非终叶节点是不可解节点用倒推的方法来逐步判断其他节点是否可解与或图有解的条件是：起始节点（根节点）可解（通过倒推来判断）与或图的解图：由最少可解节点所构成的子图，这些可解节点能够使问题的起始节点可解与或树：与或图的特例，除了根节点外，任何一个节点只有一个父节点与或图：除了起始节点，每一个节点允许有多个父节点与或树的搜索技术：宽度优先：先扩展出来的节点优先（OPEN表是队列）深度优先：后扩展出来的节点优先（OPEN表是堆栈），且有深度限制图、与或树的宽度、深度优先搜索算法之间的差别：图搜索技术是找到目标节点或无法扩展而结束算法与或树搜索技术是找到终叶节点后通过倒推来判断起始节点是否可解而结束算法6.博弈问题的表达、博弈树的搜索技术双人博弈问题的特殊之处：棋局：相当于状态空间法中的状态走棋：相当于问题归约法的节点扩展（生成或节点(自己)、与节点（别人）博弈树是一棵特殊的与或树，其节点对应棋局（相当于状态），与节点、或节点隔层交替出现博弈的特点：双方的智能活动，任何一方都不能单独控制博弈过程，而是由双方轮流实施其控制对策的过程博弈问题（求解过程）的表示：用博弈树来表示，它是一种特殊的与或树。节点代表博弈的格局（即棋局），相当于状态空间中的状态，反映了博弈的信息， 并且与节点、或节点隔层交替出现博弈树搜索的极大极小过程分成：宽度优先扩展节点（深度必为偶数），并计算最底层端节点的静态估计函数值用倒推的方法（自己下的棋取大者，对手下的棋取小者）计算出其余各层节点的静态估计函数值，最后决定走哪一步棋7.谓词逻辑与推理数理逻辑（符号逻辑）是用数学方法研究形式逻辑的一个分支。它通过符号系统来表达客观对象以及相关的逻辑推理。常用的是命题逻辑和谓词逻辑数理逻辑的主要分支：逻辑演算(包括命题演算和谓词演算)模型论证明论递归论公理化集合论数理逻辑和计算机科学有许多重合之处，两者都属于模拟人类认知机理的科学谓词逻辑是数理逻辑的基本形式，是基于谓词分析的一种形式化（数学）语言人工智能中的谓词逻辑法是指用一阶谓词来描述问题求解和定理证明（限于本课程）命题逻辑是研究命题及命题之间关系的符号逻辑系统。在命题逻辑中，表示单一意义的命题，称之为原子命题。原子命题通过 “联结词” 构成 复合命题。五个联结词： “” 表示 “非”复合命题P为真，当且仅当P为假。 “” 表示 “合取”复合命题“PQ”为真，当且仅当P和Q都为真。 “” 表示 “析取”复合命题“PQ”为真，当且仅当P、Q两者之一为真。 “” 表示 “蕴含”复合命题“PQ”为假，当且仅当P为真且Q为假。 “” 表示 “等价” 复合命题“PQ”为真，当且仅当P、Q同时为真、或者同时为假。命题变元：用符号P、Q等表示的不具有固定、具体含义的命题。它可以表示具有“真”、“假”含义的各种命题。命题变元可以利用联结词构成所谓的合适公式。 合适公式的定义若P为原子命题，则P为合适公式，称为原子公式。若P是合适公式，则P也是一个合适公式。若P和Q是合适公式，则PQ、 PQ 、PQ 、PQ都是合适公式。经过有限次使用规则1、2、3，得到的由原子公式、联结词和园括号所组成的符号串，也是合适公式。对于合适公式，规定下列运算优先级： 逻辑联结词的运算优先次序为： 、 、 同级联结词按出现顺序优先运算谓词演算1、语法与语义谓词逻辑的基本组成部分谓词变量函数常量园括号、方括号、花括号和逗号例“机器人（Robot）在第一个房间（Room1）内”，可以表示为： INROOM（ROBOT，r1）其中 INROOM是谓词 ROBOT和r1是常量谓词公式的定义：利用连词和量词可以将原子（谓词）公式组成复合谓词公式，称之为分子谓词公式、谓词合适公式、谓词公式、合适公式。对于命题合适公式和谓词合适公式有下列等价关系：否定之否定： （P） 等价于 P PQ 等价于 PQ狄-摩根定律 （PQ）等价于 PQ （PQ）等价于 PQ分配律 P(QR) 等价于 (PQ)(PR) P(QR) 等价于 (PQ)(PR)交换律 PQ 等价于 QP PQ 等价于 QP结合律 (PQ)R 等价于 P(QR) (PQ)R 等价于 P(QR)逆否律 PQ 等价于 QP对于谓词合适公式有下列等价关系： ($x)P(x) 等价于 (x)P(x) (x)P(x) 等价于 ($x)P(x) (x)P(x)Q(x) 等价于 (x)P(x)(x)Q(x)($x)P(x)Q(x) 等价于 ($x)P(x) ($x)Q(x) (x)P(x) 等价于 (y)P(y) ($x)P(x) 等价于 ($y)P(y)置换：形如 t1 / v1 , , tn / vn 的集合，称为一个置换，其中 vi 是不同的变量，ti是与vi不同的项（包括变量，常量或函数）例或例子：设 t1 / v1 , , tn / vn 为一个置换，E是一个原子谓词公式。则E表示将E中的 vi 同时用 ti（i=1,n）代入后所得到的结果，E称为E的一个例子置换的合成：设有两个置换t1 / x1, ,tn / xns1 / y1, ,sm / ym则和的合成是如下置换： t1/x1, , tn/xn, s1/y1, , sm/ym 其中，对于任何 tj=xj 者消去，yj 是 x1,xn 之一者消去，记为如何求 ti :s1/y1 , , sm/ym如果 ti 出现 y1, ., ym中的变量 yi ， 则用其对应的项 si 来代替。合一：设 s 是一个置换， Ei 是表达式（原子谓词公式）集合 。如果置换 s 使得 E1s=E2s=Eis=则我们称表达式集合 Ei 是可合一的，并称 s为 Ei 的合一者最一般的合一者：如果 s 是 Ei 的任意一个合一者，又存在某一个 s，使得 s = g s 或者 Ei s = Ei g s则称 g 是 Ei 的最通用（最一般）的合一者，记作mgu分歧集（或不一致集合）设有一非空有限公式集合F=F1,Fn，从F中各个公式的第一个符号同时向右比较，直到发现第一个彼此不尽相同的符号为止，从F中的各个公式中取出那些以第一个不一致符号开始的最大的子表达式为元素，组成一个集合D，称为F的分歧集（不一致集合）。 其中，F i ( i=1,n)是原子谓词公式合一算法： 设F为非空有限表达式集合，则可以按下列步骤求出mgu：置k=0，Fk=F,k=(空置换，即不含元素的置换)若Fk只有一个表达式，则算法终止，其中k就是要求的mgu找出Fk的分歧集Dk若Dk中存在元素ak和tk，其中ak是变元，tk是项，且ak不在tk中出现，则置： k+1=ktk/ak Fk+1=Fktk/ak k=k+1 然后转向算法终止，F的mgu不存在合一算法的流程图:谓词公式化成子句集（九步） 消去“蕴含”和“等价”连结词 AB = ABAB = (AB)(B A) 减少“非”连结词的辖域（将“”连结词直接作用到原子公式前）(A) A(AB) = AB(AB) = AB($x)A(x) = (x)(A(x)(x)A(x) = ($x)(A(x) 对变量标准化（约束变元改名）: 对约束变元改名，使得所有的约束变元名都不相同，保证每一个量词都有自己唯一的约束变元消去存在量词（引入斯科伦函数）化成前束范式: 将全称量词移到谓词公式的左边，使得每一个量词的辖域包括该量词后面的整个谓词公式(x)A(x)R = (x) (A(x)R)(x)A(x)R = (x) (A(x)R)(1x)A(x)(2z)B(z) =(1x) (2z) (A(x)B(z)(1x)A(x)(2z)B(z) =(1x) (2z) (A(x)B(z)说明：A(x), B(z), R中允许含有与x，z不同的自由变量将母式化成合取范式利用分配律将前束范式化成前束合取范式：P(QR) = (PQ)(PR) （析取合取）消去全称量词消去合取连结词母式为合取范式： A1 A2 An消去合取连结词，得到子句集： A1 , A2, , An子句：基本式（文字）的析取（只含）更改变量名，得到子句集更改变元名，使得一个变量符号不出现在一个以上的子句中，即不同的子句包含不同的约束变元名说明：到现在为止，谓词公式只包含三种连结词“合取”：“析取” “非” 设，是一个谓词公式，将量词记作（即$或）如果中包含部分公式 (x)，则中变元 x 的一切出现都称为 x 在 中的约束出现，相应地称 x 为约束变元（哑元、虚构变量、约束变量）中不在任何量词作用域内的变元 x ，称为变元 x 在 中的自由出现，相应地称 x 为自由变元（自由变量）子句集原子公式的定义：原子命题是原子公式如果t1,tn(n1)是项，P是谓词，则P(t1,tn)是原子公式其它表达式都不是原子公式子句的定义： 文字（或基本式）：“原子公式”或者“原子公式的非” 子句：一个或多个基本式的 析取子句形式的定义：一个谓词公式具有形式： ( x1 )( xn )( c1c2cm )其中，ci ( i = 1, , m )为子句 x1, , xn 是子句中出现的约束变元则，称谓词公式具有子句形式子句集的定义：(x1 )(xn )( c1c2cm )若谓词公式 具有子句形式，记 S = ( c1 , c2 , , cm )则，称 S 为谓词公式的子句集消解式：设c1 , c2是两个无公共变量的子句，令 c1= P(t11,t1n)P(tk1,tkn)c1 c2= P(t11,t1n)P(tm1,tmn)c2说明：谓词符号相同，变元不同若 P(t11,t1n), , P(tk1,tkn), P(t11,t1n), , P(tm1,tmn) 有最一般的合一者（或一致置换）（mgu）则称 c = ( c1 c2) 为c1 , c2的消解式消解演绎与消解反演设S是子句集，c是子句。若存在一个子句序列c1,cn满足 cn = c 任意一个 ci 或者属于 S 或者它前面的子句 ck, cl ( ik , il )的消解式则称 c1, , cn 是从子句集 S 到子句 c 的一个消解演绎当 c= 时的消解演绎称为（消解）反演反演的基本算法：把谓词公式转化为子句集S（所有子句的变量名不同）如空子句成为子句集的子句，则算法结束在子句集中选取两个不同的可以消解的子句ci , cj计算 ci , cj 的消解式 rij 把 rij 加到子句集中，形成新的子句集S转到给定一个公式集 S（前提条件）和目标公式 L（结论），通过反演来求证目标公式 L，其证明过程为：否定 L ，得到 L把 L 加到 S 中把新形成的集合 S ， L 化为子句集（各自化成子句集，变量改名）应用消解原理，导出一个表示矛盾的空子句原子公式：原子命题（0元谓词）和谓词基本式：原子公式或原子公式的非正基本式：不带“非号”的原子公式负基本式：带“非号”的原子公式Horn子句及Horn子句集：Horn子句：最多只含有一个正基本式的子句（只含一个正基本式或者不含正基本式）Horn子句集：每一个子句均为Horn子句的子句集8.Prolog语言是：以一阶谓词逻辑的Horn 子句集为语法，以Robinson的消解原理为工具，加上深度优先的控制策略而形成的人工智能通用程序设计语言Prolog中的语句分成三种形式：事实： P. （含义：无条件成立，恒为真 ）规则： P :- P1, P2, , Pn. （含义：若P1, , Pn均为真时，则P为真 ）问题（目标）：?- Q1, Q2, ,Qm . （含义：Q1, , Qm 同时为真吗？）Visual Prolog 程序的基本结构：domains（域段，说明变量类型，无句号、可以缺省）predicates. （谓词段，说明谓词，无句号）clauses. （子句段，程序主体，必须有句号）goal （目标段，表达目标或问题，必须有句号）Prolog的程序主要分为两部分： 前提部分：所有事实和规则 问题部分：目标子句序列第四部分 人工神经网络计算智能是一种智力方式的低层认知，它与人工智能的区别是认知层次从中层下降至低层。中层系统含有知识，低层系统则没有知识计算智能系统：系统只涉及数值（低层）数据，含有模式识别部分，不应用人工智能意义上的知识，而且具有下列特点：计算适应性、计算容错性、接近人的速度、误差率与人相近神经元的动作或工作原理： 求加权和 与阈值比较 用激活函数得到输出激活函数有：阶跃函数：(-, + )0,+1符号函数：(-, + )-1,+1线性函数：Sigmoid函数：(-, + )(0,+1)或者(-1,+1)Sigmoid函数的特点：第一、非线性、单调性（单调增）第二、无限次可微第三、当值很大时，可以近似阈值函数或符号函数第四、当值很小时，可以近似线性函数神经网络模型：反向传播神经网络（多层感知器反向传播训练算法）(BP)人工神经网络是由大量处理单元（人工神经元）相互连结组成的非线性、大规模、自适应的动力系统。它是在现代神经科学研究成果的基础上提出的，试图通过模拟大脑神经网络处理、记忆信息的方式，设计出一种新的机器使之具有像人脑那样的信息处理能力BP网络：针对分类与回归问题，如何确定网络结构反向传播算法的基本思想公式推导的关键技术BP网络的结构：BP网络包含：一个输入层若干中间层（隐层）一个输出层解决模式分类问题时，确定网络结构的原则输入层的神经元个数：输入样本的维数（有阈值数，加1）中间层的层数及其神经元个数：使用者确定输出层的神经元个数：类别数（多类取多个，两类取一个）激活函数：所有激活函数取Sigmoid函数解决回归问题时，确定网络结构的原则输入层的神经元个数：输入样本的维数（有阈值数，加1）中间层的层数及其神经元个数：使用者确定输出层的神经元个数：1激活函数：取Sigmoid函数或线性函数（输出层）目标函数：BP学习算法的目标就是最小化目标函数，其基本思想包含两个过程：正向传播过程反向传播过程正向传播过程:在正向传播过程中，输入信息（训练样本）从输入层经隐层逐层处理后，传递到输出层，每一层神经元的状态仅影响下一层的神经元的状态反向传播过程:如果输出层的神经元的输出值与期望输出不吻合，则转为反向传播过程，把误差信号沿原来连接的路径返回，并通过修改各层神经元的权值，使得误差达到最小在BP学习算法的推导中有三项关键技术：采用连续可微的变换函数（线性和Sigmoid函数） 应用链式求导法则求所有权值的偏导数设 y 为某些中间变量 xi 的函数，每个 xi 又为变量 z 的函数，则 y 对 z 的导数为 应用梯度法更新权值