下载文档原格式
“模式识别(三).PDF”课件课后上机选做作业参考解答(武大计算机学院袁志勇, Email: yuanzywhu@) 上机题目：两类问题，已知四个训练样本ω1={(0,0)T,(0,1)T}；ω2={(1,0)T,(1,1)T}使用感知器固定增量法求判别函数。
设w1=(1,1,1)Tρk=1试编写程序上机运行(使用MATLAB、 C/C++、C#、JA V A、DELPHI等语言中任意一种编写均可)，写出判别函数，并给出程序运行的相关运行图表。
这里采用MATLAB编写感知器固定增量算法程序。
一、感知器固定增量法的MATLAB函数编写感知器固定增量法的具体内容请参考“模式识别(三).PDF”课件中的算法描述，可将该算法编写一个可以调用的自定义MATLAB函数：% perceptronclassify.m%% Caculate the optimal W by Perceptron%% W1-3x1 vector, initial weight vector% Pk-scalar, learning rate% W -3x1 vector, optimal weight vector% iters - scalar, the number of iterations%% Created: May 17, 2010function [W iters] = perceptronclassify(W1,Pk)x1 = [0 0 1]';x2 = [0 1 1]';x3 = [1 0 1]';x4 = [1 1 1]';% the training sampleWk = W1;FLAG = 0;% iteration flagesiters = 0;if Wk'*x1 <= 0Wk =Wk + x1;FLAG = 1;endif Wk'*x2 <= 0Wk =Wk + x2;FLAG = 1;endif Wk'*x3 >= 0Wk=Wk-x3;FLAG = 1; endif Wk'*x4 >= 0Wk =Wk -x4; FLAG = 1; enditers = iters + 1; while (FLAG) FLAG = 0; if Wk'*x1 <= 0Wk = Wk + x1; FLAG = 1; endif Wk'*x2 <= 0Wk = Wk + x2; FLAG = 1; endif Wk'*x3 >= 0 Wk = Wk - x3; FLAG = 1; endif Wk'*x4 >= 0 Wk = Wk - x4; FLAG = 1; enditers = iters + 1; endW = Wk;二、程序运行程序输入：初始权向量1W , 固定增量大小k ρ 程序输出：权向量最优解W , 程序迭代次数iters 在MATLAB 7.X 命令行窗口中的运行情况： １、初始化1[111]T W = 初始化W 1窗口界面截图如下：２、初始化1kρ=初始化Pk 窗口界面截图如下：３、在MATLAB 窗口中调用自定义的perceptronclassify 函数由于perceptronclassify.m 下自定义的函数文件，在调用该函数前需要事先[Set path…]设置该函数文件所在的路径，然后才能在命令行窗口中调用。
2005-4-20IT&NLP Lily Shan1第3 章搜索推理技术讲师: 单丽莉IT&NLPhttp://2005-4-20IT&NLP Lily Shan 2第3 章搜索推理技术3.1 图搜索策略3.2 盲目搜索3.3 启发式搜索3.4 消解原理3.5 规则演绎系统3.6 产生式系统3.7 系统组织技术3.8 不确定性推理2005-4-20IT&NLP Lily Shan 33.1 图搜索策略3.1.1 问题求解的过程3.1.2 图搜索的一般过程443.1.1 问题求解的过程1.问题的表示: 主要采用状态空间法(状态空间图)和问题归约法(与或图).2.问题的求解: 通过在图(“状态空间图”或”与或图”)中进行搜索, 寻找一条路径的方法.–一般搜索: 从初始节点出发, 扩展节点, 并沿子节点推进, 继续扩展选择的子节点, 直到找到通向目标结点的路径, 或找到解树为止.肓目搜索:是按预定的控制策略进行搜索, 在搜索过程中获得的中间信息并不改变控制策略。
启发式搜索: 是在搜索过程中加入了与问题有关的启发性信息, 缩小问题的搜索范围，指导搜索朝着最有希望的方向前进，以尽快地找到问题的（最优）解.553.1.2 图搜索的一般过程数据结构: –OPEN: 未扩展节点表–CLOSED: 已扩展节点表算法过程(1)建立一个只含有起始节点S 的搜索图G, 把S 放到一个叫作OPEN 的未扩展节点表中;(2)建立一个叫做CLOSED 的已扩展节点表, 其初始为空表;(3)LOOP: 若OPEN 表是空表, 则失败退出;(4)选择OPEN 表上的第一个节点,把它从OPEN 表移出并放进CLOSED 表中,称此节点为节点n;(5)若n 为一目标节点,则有解并成功退出, 此解是追踪图G 中沿着指针从n 到S 这条路径而得到的(指针将在第(7)步中设置);2005-4-20IT&NLP Lily Shan 63.1.2 图搜索的一般过程(续)(6)扩展节点n, 同时生成不是n 的祖先的那些后继节点的集合M.把M 的这些成员作为n 的后继节点添入图G 中;(7)对那些未曾在G 中出现过的(即未曾在OPEN 表上或CLOSED 表中出现过的)M 成员设置一个通向n 的指针, 把M 的这些成员加进OPEN 表. 对已经在OPEN 或CLOSED 表上的每一个M 成员,确定是否需要更改通到n 的指针方向. 对已在CLOSED 表上的每个M 成员,确定是否需要更改图G 中通向它的每个后裔节点的指针方向;(8)按某一任意方式或按某个探试值, 重排OPEN 表;(9)Go Loop.7把S 放入OPEN 表OPEN 表为空?失败开始把第一个节点(n )从OPEN 表移至CLOSED 表n 是否为目标节点?成功把n 的后继节点n 放入OPEN 表的末端,提供返回节点n 的指针修改指针方向重排OPEN 表是否是否图3.1 图搜索过程框图2005-4-20IT&NLP Lily Shan 83.1.2 图搜索的一般过程(续)过程说明:①搜索图: 图搜索的一般过程生成一个明确图G, 称为搜索图.②搜索树: 图搜索的一般过程生成G 的一个子集T 称为搜索树. 由步骤(7)中设置的指针来确定.③G 中每个节点(S 除外)都有一个只指向G 中一个父辈节点的指针, 该父辈节点就定为树中那个节点的惟一父辈节点.④OPEN 表上的节点都是搜索图上未被扩展的端节点, 而CLOSED 表上的节点, 或者是已被扩展但没有生成后继节点的端节点, 或者是搜索树的非端节点.93.1.2 图搜索的一般过程(续)⑤步骤(8)对OPEN 表上的节点进行排序, 以便选出一个”最好”的节点作为步骤(4)扩展使用.①排序可以是任意的即肓目的(盲目搜索)②可以用启发信息为依据(启发式搜索)⑥当扩展某个节点时, 搜索图已经保存了从初始节点到该节点的搜索树.⑦每当被选作扩展的节点为目标节点时,这一过程就宣告成功结束. 这时, 从目标节点按指向父节点的指针不断回溯,能够重现从起始节点到目标节点的成功路径.⑧当搜索树不再剩有末被扩展的端节点时(即OPEN 表为空时), 过程就以失败告终. 从起始节点, 达不到目标节点.10⑨步骤(6)扩展节点时, 生成一个节点的所有后继节点.⑩步骤(7)的说明: 特别地用于启发式搜索S 0312图3.2 扩展节点1以前的搜索图45图3.3 扩展节点1以后的搜索图S 0312456788762005-4-20IT&NLP Lily Shan 113.2 盲目搜索3.2.1 宽度优先搜索3.2.1 深度优先搜索3.2.3 等代价搜索12宽度优先搜索: 如果搜索是以接近起始节点的程度来依次扩展节点, 那么这种搜索叫做宽度优先搜索(breadth -first search).SL OM FP FFQ N F图3.4 宽度优先搜索示意图2005-4-20IT&NLP Lily Shan133.2.1 宽度优先搜索(续)宽度优先搜索算法如下:(1)把起始节点放到OPEN 表中(如果该起始节点为一目标节点,则求得一个解答).(2)如果OPEN 是个空表, 则没有解,失败退出;否则继续.(3)把第一个节点(节点n) 从OPEN 表移出,并把它放入CLOSED 的扩展节点表中.(4)扩展节点n. 如果没有后继节点,则转向步骤(2).(5)把n 的所有后继节点放到OPEN 表的末端, 并提供从这些后继节点回到n 的指针.(6)如果n 的任一个后继节点是个目标节点, 则找到一个解答, 成功退出; 否则转向步骤(2);2005-4-20IT&NLP Lily Shan143.2.1 宽度优先搜索(续)宽度优先搜索算法说明:(1)搜索树: 搜索过程产生的节点和指针构成一棵隐式定义的状态空间图的子树, 称为搜索树.(2)如果问题有解, 宽度优先算法能够保证找到一条通向目标节点的最短路径(即找到最优解).(3)如要问题无解,对于有限图,该算法会失败退出;对于无限图,则永远不会终止15把S 放入OPEN 表OPEN 表是否为空表?失败起始把第一个节点n 从OPEN 表移至CLOSED 表扩展n , 把n 的后继节点n 放入OPEN 表的末端,提供返回节点n 的指针是否否图3.5 宽度优先算法框图是否有任何后继节点为目标节点?成功是2005-4-20IT&NLP Lily Shan16例: 八数码难题. 在3×3的方格棋盘上,分别放置了标有数字1,2,3,4,5,6,7,8的八张牌, 初始状态如图3.6 S 0所示, 目标状态如图3.6 S g 所示, 要求应用宽度优先搜索策略寻找从初始状态到目标状态的解路径.2831476512384765图3.6 八数码难题S 0S g177652834765231476528317652831475184683247652837465112314765231476588832476512837465112347658234176588324765183247651283746512837465112347658123476582834175628137652831576442831475283147566281376542831576428317546图3.7 八数码难题的宽度优先搜索树2005-4-20IT&NLP Lily Shan18深度优先搜索: 在搜索过程中, 首先扩展最新产生的(即最深的)节点, 这种搜索叫做深度优先搜索.SL OM FP FFQ N F图3.8 宽度优先搜索示意图193.2.2 深度优先搜索(续)节点深度定义:(1) 起始节点(即根节点)的深度为0.(2) 任何其他节点的深度等于其父辈节点的深度加1.深度界限:–为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去), 往往给出一个节点扩展的最大深度, 称为深度界限.–任何节点如果达到了深度界限,那么都将把它们作为没有后继节点来处理.–即使应用了深度界限, 深度优先搜索所求得的解答路径也不一定就是最短路径.2005-4-20IT&NLP Lily Shan203.2.2 深度优先搜索(续)含有深度界限的深度优先搜索算法:(1)把起始节点S 放到未扩展节点OPEN 表中. 如果此节点为一目标节点,则得到一个解.(2)如果OPEN 为一空表,则失败退出.(3)把第一个节点(节点n)从OPEN 表移到CLOSED 表.(4)如果节点n 的深度等于最大深度,则转向步骤(2).(5)扩展节点n, 产生其全部后裔,并把它们放入OPEN 表的前头.如果没有后裔,则转向步骤(2);(6)如果后继节点中有任一个为目标节点,则求得一个解,成功退出;否则,转向步骤(2);21OPEN 表是否为空?失败把OPEN 表中的第一个节点n 移入CLOSED 表扩展节点n , 把其后裔n 放入OPEN 表的前端,提供返回节点n 的指针是否否是否有任何后继节点为目标节点?成功是图3.9 有界深度优先搜索算法框图S 是否为目标节点?成功是否节点n 的深度是否等于深度界限?是否22765283476523147652831765283147518462314765231476588123476582341765812347658123476582834175628314752831475662813765283157644281376542831576428317546234176582341576828137654248137652813754628316754...图3.10 八数码难题深度界限为4的深度优先搜索树Return to f233.2.3 等代价搜索宽度优先的局限:–在宽度优先搜索中作了一种假设, 认为状态空间中各边的代价都相同, 且都为一个单位量.从而可用路径的长度代替路径的代价.–然而, 对许多问题这种假设是不现实的, 它们的状态空间中的各个边的代价不可能完全相同.例: 城市交通问题.–为此, 需要在搜索树中给每条边都标上其代价.代价树: 在搜索树中给每条边都标上其代价. 这种边上标有代价的树称为代价树.等代价搜索: 寻找从起始状态至目标状态的具有最小代价的路径问题, 叫做等代价搜索.–在等代价搜索算法中, 是沿着等代价路径断层进行扩展的.2005-4-20IT&NLP Lily Shan24例: 城市交通问题. 设有5个城市, 它们之间的交通路线如图3.11所示, 图中的数字表示两个城市之间的交通费用,即代价. 用等代价搜索, 求从A 市出发到E 市, 费用最小的交通路线.ABCDE342453图3.11 城市交通图2005-4-20IT&NLP Lily Shan 25解: 其代价搜索树如右下图:最优解: A,C,D,E AC1D134B2E2E3图3.12 城市交通图的代价搜索树2434523B1E1D2C2ABC DE342453图3.11 城市交通图2005-4-20IT&NLP Lily Shan 263.2.3 等代价搜索(续)记号–c (i , j ): 从节点I 到其后继节点j 的连接弧线代价.–g (i ):从起始节点S 到任一节点i 的路径代价(即是从起始节点S 到节点i 的最少代价路径上的代价).2005-4-20IT&NLP Lily Shan273.2.3 等代价搜索(续)等代价搜索算法:(1)把起始节点S 放到未扩展节点有OPEN 中.如果此起始节点为一目标节点,则求得一个解;否是令g(S )=0.(2)如果OPEN 是个空表,则没有解而失败退出.(3)从OPEN 表中选择一个节点I,使其g(i )为最小.如果有几个节点都合格,那么就要选择一个目标节点作为节点i(如果有目标节点的话);否则,就从中选一个作为节点i ,把节点i 从OPEN 表移至扩展节点表CLOSED 中.2005-4-20IT&NLP Lily Shan283.2.3 等代价搜索(续)等代价搜索算法:(4)如果节点i 为目标节点,则求得一个解.(5)扩展节点i .如果没有后继节点,则转向步骤(2);(6)对于节点i 的每个后继节点j ,计算g (j )=g (i )+c (i ,j ), 并把所有后继节点j 放进OPEN 表.提供回到节点i 的指针.(7)转向步骤(2).29OPEN 表是否为空?失败把具有最小g(i )值的节点i 从OPEN 表移至CLOSED 表扩展节点i , 计算其后继节点j 的g(j)值.把后继节点j 放进OPEN 表是否否i 是否为目标节点?成功是图3.13 等代价搜索算法框图S 是否为目标节点?成功是否否令g(s)=02005-4-20IT&NLP Lily Shan 303.3 启发式搜索3.3.1 启发式搜索策略和估价函数3.3.2 有序搜索3.3.3 A*算法2005-4-20IT&NLP Lily Shan 313.3 启发式搜索(续)盲目搜索存在的问题–扩展节点数目较多.–效率低, 耗费过多的计算时间和空间.–如果选择最有希望的节点加以扩展, 搜索效率将会大为提高.2005-4-20IT&NLP Lily Shan 323.3.1 启发式搜索策略和估价函数 启发性信息: 指那种与具体问题求解过程有关的, 并可指导搜索过程朝着最有希望方向前进的控制信息.–有效地帮助确定扩展节点的信息;–有效的帮助决定哪些后继节点应被生成的信息;–能决定在扩展一个节点时哪些节点应从搜索树上删除的信息.启发式搜索: 利用启发信息的搜索方法叫做启发式搜索.2005-4-20IT&NLP Lily Shan 333.3.1 启发式搜索策略和估价函数(续)估价函数(evaluation function): 用于度量节点的”希望”(此节点在通向目标结点的最佳路径上的”希望”)的量度. 记号f (n ) : 表示节点n 的估价函数值.–用函数f (n )的值来排列图搜索的一般算法中的OPEN 表中节点.–节点按递增顺序排列, 即优先扩展具有低估价值的节点, 根据低估价值节点更有可能处在最佳路径上.2005-4-20IT&NLP Lily Shan 343.3.2 有序搜索有序搜索: 应用某个算法(例如等代价法)选择OPEN 表上具有最小f 值的节点作为下一个要扩展的节点, 这种搜索方法叫做有序搜索或最佳优先搜索, 其算法就叫做有序搜索算法或最佳优先算法.–有序搜索总是选择最有希望的节点作为下一个要扩展的节点.2005-4-20IT&NLP Lily Shan 353.3.2 有序搜索(续)有序状态空间搜索算法:(1)把起始节点S 放到OPEN 表中, 计算f (S ),并把其值与节点S 联系起来.(2)如果OPEN 表是个空表,则失败退出,无解.(3)从OPEN 表中选择一个f 值最小的节点i .结果有几个节点合格,当其中有一个为目标节点时,则选择此目标节点,否则就选择其中任一个节点作为节点i .(4)把节点i 从OPEN 表中移出,并把它放入CLOSED 的扩展节点表中.(5)如果i 是个目标节点,则成功退出,求得一个解.363.3.2 有序搜索(续)(6)扩展节点i , 生成其全部后继节点.对于i 的每一个后继节点j :a)计算f (j ).b)如果j 既不在OPEN 表中,也不在CLOSED 表中,则用估价函数f 把它添入OPEN 表.从j 加一指向父辈节点i 的指针(以便找到目标节点时记住一个解答路径).c)如果j 已在OPEN 表或CLOSED 表上,则比较刚刚对j 计算过的f 值和前面计算过的该节点在表中的f 值.如果新的f 值较小,则I.以此新值取代旧值.II.从j 指向i ,而不是指向它的父辈节点III.如果节点j 在CLOSED 表中,则把它移回OPEN 表(7)转向(2),即GOTO(2);37把S 放入OPEN 表,计算f (s )OPEN 表=NIL?失败开始选取OPEN 表中f 值最小的节点i 放入CLOSED 表扩展节点i , 计算其后继节点j 的f (j)值.提供返回指针,利用f 值对OPEN 表重新排序,调整亲子关系及指针是否否i=S g成功是图3.14 有序搜索算法框图383.3.2 有序搜索(续)在有序搜索中–定义f (i )为节点i 的深度, 则退化为宽度优先算法搜索.–定义f (i )为从起始节点至节点i 这段路径的代价, 则退化为等代价搜索.估价函数的作用–f 的选择直接决定了有序搜索中被扩展节点的数目,即直接影响了搜索算法的效率.–对搜索结果具有决定性的作用.估价函数的选择–一个节点处在最佳路径上的概率；–求出任意一个节点与目标节点集之间的距离度量或差异度量；–根据格局（博弈问题）或状态的特点来打分。
题1：在一个10类的模式识别问题中，有3类单独满足多类情况1，其余的类别满足多类情况2。
问该模式识别问题所需判别函数的最少数目是多少？答：将10类问题可看作4类满足多类情况1的问题，可将3类单独满足多类情况1的类找出来，剩下的7类全部划到4类中剩下的一个子类中。
再在此子类中，运用多类情况2的判别法则进行分类，此时需要7*（7-1）/2=21个判别函数。
故共需要4+21=25个判别函数。
题2：一个三类问题，其判别函数如下：d1(x)=-x1, d2(x)=x1+x2-1, d3(x)=x1-x2-11.设这些函数是在多类情况1条件下确定的，绘出其判别界面和每一个模式类别的区域。
2.设为多类情况2，并使：d12(x)= d1(x), d13(x)= d2(x), d23(x)= d3(x)。
绘出其判别界面和多类情况2的区域。
3.设d1(x), d2(x)和d3(x)是在多类情况3的条件下确定的，绘出其判别界面和每类的区域。
答：三种情况分别如下图所示：1．2．3．题3：两类模式，每类包括5个3维不同的模式，且良好分布。
如果它们是线性可分的，问权向量至少需要几个系数分量？假如要建立二次的多项式判别函数，又至少需要几个系数分量？（设模式的良好分布不因模式变化而改变。
）答：（1）若是线性可分的，则权向量至少需要14N n =+=个系数分量； （2）若要建立二次的多项式判别函数，则至少需要5!102!3!N ==个系数分量。
题4：用感知器算法求下列模式分类的解向量w : ω1: {(0 0 0)T, (1 0 0)T, (1 0 1)T, (1 1 0)T} ω2: {(0 0 1)T, (0 1 1)T, (0 1 0)T, (1 1 1)T}解：将属于2w 的训练样本乘以(1)-，并写成增广向量的形式x1=[0 0 0 1]',x2=[1 0 0 1]',x3=[1 0 1 1]',x4=[1 1 0 1]';x5=[0 0 -1 -1]',x6=[0 -1 -1 -1]',x7=[0 -1 0 -1]',x8=[-1 -1 -1 -1]';迭代选取1C =，(1)(0,0,0,0)w '=，则迭代过程中权向量w 变化如下：(2)(0 0 0 1)w '=；(3)(0 0 -1 0)w '=；(4)(0 -1 -1 -1)w '=；(5)(0 -1 -1 0)w '=；(6)(1 -1 -1 1)w '=；(7)(1 -1 -2 0)w '=；(8)(1 -1 -2 1)w '=；(9)(2 -1 -1 2)w '=； (10)(2 -1 -2 1)w '=；(11)(2 -2 -2 0)w '=；(12)(2 -2 -2 1)w '=；收敛所以最终得到解向量(2 -2 -2 1)w '=，相应的判别函数为123()2221d x x x x =--+。
