COM07043_2011级_人工智能基础(A卷)_标准答案

1课程编号：COM07043北京理工大学2013-2014学年第一学期2011级人工智能基础期末试题A卷班级学号姓名成绩一、判断题（10分，每小题1分）1.按StrongAI的观点，可以认为Google自动汽车是智能的。（）2.BP神经网络学习算法的优化目标是使实际输出与期望输出之间的误差平方和最小化。（√）3.蚁群优化算法中，每个人工蚂蚁都需要构建自己的解。（√）4.StateSpace和And/OrGraph只是两种不同的问题表示方法，但其解决问题的思路是一样的。（）5.Self-OrganizingFeatureMap(SOFM)神经网络可用于聚类。（√）6.通过Breadth-FirstSearch算法一定能找到最优解。（√）7.归结演绎推理方法是一种反证法。（√）8.DecisionTree中的非叶节点对应于属性值。（）9.GeneticAlgorithms属于表现型进化算法。（）10.k-中心点聚类算法中，每个簇用其均值来代表。（）二、填空题（20分，每空2分）1.从计算实质上来说，SupervisedLearning是对函数的学习。2.所有HeuristicSearch方法想要解决的基本问题都是利用启发式信息，在一个解空间中，通过探索有限数量的解来找到最优解。3.EvolutionaryAlgorithms中，通过选择操作降低解的多样性以便使算法收敛，通过遗传操作增加解的多样性以便发现全局最优解。4.将语句“所有瞎眼老鼠都没有尾巴”用First-OrderLogic(FOL)来表示，可以是xtaillessxblindxmousex，将其转换为合取范式是xtaillessxblindxmouse。5.MinimumDescriptionLength准则是奥卡姆剃刀原则的体现。在利用2该准则解决决策树学习问题时，需要考虑两个编码长度，分别是决策树的编码长度和例外数据的编码长度6.常用数据采样手段提高聚类算法的效率。三、计算题（50分）1．在下图所示的图结构上，S为起始节点，G为目标节点，边上的数字表示从某节点到另一节点的距离。现要求计算从S到G的最短路径。兹给出各点对应的启发函数值如下表所示：点SABCDG启发距离2220812100问题如下：1）以上启发函数符合A*算法的可容许性条件吗？请回答并说明原因。[3分]答：符合，因为可容许性条件是：h(n)=h*(n)，h(n)为当前结点到目标结点的估值，即题中给出的启发函数。h*(n)为实际问题的代价值，对于每一点，均满足这个条件h(n)=h*(n)，因此，此启发函数符合A*算法的可容许性条件2）如果以上启发函数符合A*算法的可容许性条件，请用A*搜索方法求解该问题。给出搜索图，在图上标注每个节点的启发函数值（h值）和估价函数值（f值），以及节点扩展顺序。[7分]3SGDBCAh=22,f=22h=50,f=50h=20,f=23h=12,f=20h=10,f=21h=8,f=25h=27,f=27节点扩展顺序：S—C—D—G2.下图所示为一棵GameTree，其中末一行的数字是节点的静态估值。如按从左到右顺序进行剪枝搜索。请在图上标注搜索与剪枝过程，包括节点上的倒推值和被剪去的分枝（在剪枝处用×做标记）。在此基础上说明计算的最终目标是什么。[10分]21338656MAXMINABCDEFGHIJLMNOK44PQ4Q21338656MAXMINABCDEFGHIJLMNOK4P238626641计算的最终目标：在A状态下，确定合适的走法，即走B好还是走C好。根据以上搜索过程，可知走C好。3.某公司招聘工作人员，A、B、C三人面试，经面试后公司表示如下想法：（1）三人中至少录取一人。（2）如果录取A而不录取B，则一定录取C。（3）如果录取B，则一定录取C。求证：用Resolution推理方法证明公司一定录取C。[10分]答：首先表示事实和知识如下：（1）CBA（2）CBA（3）CB并将其转化为合取范式如下：①CBA②CBA③CB然后，表示结论并取反：④C最后，执行归结过程如下：①④归结，得⑤BA；5②④归结，得⑥BA③④归结，得⑦B⑤⑥归结，得⑧B⑦⑧归结，得NIL因此，结论取反不成立，即公司一定录取C.答：1)将问题中提供的知识用谓词表示如下：Admission(x):表示x被录用；┐Admission(x):表示x未被录用Admission(x)→trueAdmission(A)∧┐Admission(B)→Admission(C)Admission(B)→Admission(C)2)用谓词表示结论的否定┐Admission(C)3)将上述谓词公式转化为子句集如下：Admission(x)┐Admission(A)∨Admission(B))∨Admission(C)┐Admission(B)∨Admission(C)4)按谓词逻辑的归结原理对此子句集进行归结，归结反演树如图┐Admission(A)∨Admission(B))∨Admission(C)┐Admission(B)∨Admission(C)┐Admission(A)∨Admission(C)Admission(x)Admission(A)A/x┐Admission(C)Admission(C)NIL因此，公司一定录取C.64.假设根据以下三个因素来判断计算机的质量（好或坏）：（1）计算机运行起来是否有噪声，设其用N来表示，其取值为true或false;（2）计算机是否容易死机，设其用F来表示，其取值为true或false;（3）应用程序在该计算机上运行时是否速度很慢，设其用A来表示，其取值为true或false。现对于该问题，提供了如下数据：问题如下：1）要求学习一个决策树来解决该问题。请根据上述数据，基于信息增益方法为决策树选择根节点。[10分]答：1）首先，计算样本的熵。从表格中，我们发现一共8个样本，取值为ok的样本有5个，取值为bad的有3个，因此，样本里有5个正例，3个反例，记为S(5+,3-)，所以，样本的熵为：58832253Entropy()loglog0.954488S（公式要改）其次，分别以N,F和A作为根节点，计算其信息增益：13324412554222231242222246246254132N:Entropyloglogloglog55843142Entropyloglogloglog448Entropylog10.79568332F:0.905684464221A:8l686ogFFN221122loglo10.938722g7GainS,EntropySEntropy0.9544GainS,EntropySEntropy0.9544GainS,0.7956=En0.15880.9056=0.04880.9387=0.0tropySEntr15opy0.95474NFANFA因此，选用为N作为根结点（确认以上计算结果）2）根据上述数据，利用m-估计法（m=2）学习一个朴素贝叶斯分类器。利用该朴素贝叶斯分类器，判断当N=false,F=true,A=true时，计算机是好还是坏，并观察你的判断结果与表中所给出的数据是否一致？[10分]答：类先验概率P(ok)=5/8，P(bad)=3/8.设jh表示类别，取值为“bad”或者“ok”。iw表示第i种因素的真假有无。譬如，对于N来说，其true与false分别用N和┐N表示。ijn表示jh类训练样本中iw出现的次数，jn表示用于jh类训练样本的总数，m=2则m-估计的计算公式为()(1|)/(2)iijjjPwhnn由训练样本可知：P(N│ok)=2/7，P(┐N│ok)=5/7，P(N│bad)=3/5，P(┐N│bad)=2/5P(F│ok)=3/7，P(┐F│ok)=4/7，P(F│bad)=3/5，P(┐F│bad)=2/5P(A│ok)=2/7，P(┐A│ok)=5/7，P(A│bad)=2/5，P(┐A│bad)=3/5若设all为bad与ok的集合，则相应的分类公式为(,)1()P|jallNBhokbadjijihargmaxPhwh对于N=false,F=true,A=true,jhok时，PP(Nok)P(Fok)P(Aok)0.0874ok┐│││（以上数据已变化，修改）jhbad时，PP(Nbad)P(Fbad)P(Abad)0.096bad┐│││（以上数据已变化，修改）8因此，判断结果为bad，与所给数据库一致。（以上数据已变化，再确认）四、算法题（20分）1.要求采用人工神经网络对字符T进行识别，其识别任务是：当输入任意一个大小为20×20的二值图像时，神经网络能判断其是否为字符T。这里，二值图像中每个点取值为1或0，当取值为1时表示该点为黑色，否则为白色。下图给出了一幅输入图像的例子：问题如下：1）请给出能用于完成上述字符识别任务的人工神经网络的结构（不考虑其权值）。[5分]答：采用三层感知器对字母进行识别。其中，第一层为输入层，接受输入的字符图像，图像大小为20×20，因此，输入神经元有400个，每个输入神经元对应于图像中的一个像素。第二层为隐含层，其神经元个数确定为200个。最后一层为输出层，仅包含一个神经元，该神经元输出1表示输入的是字母T，0则表示不是字母T.2）请设计一种进化算法来学习你所设计出的上述神经网络中的权值：2-1）给出该进化算法的伪代码。[10分]2-2）说明该算法运行所需的数据条件及其学习过程。[5分]答：2-1）采用进化规划算法优化上述神经网络：将网络中所有神经元之间的连接权值连接起来作为一个个体。相应伪码如下：随机生成10个个体。对于每个个体，在训练数据上进行分类，统计识别率，作为其适应度。Do统计最优适应度值对于每个个体，按照高斯扰动方法进行突变，获得10个新个体。9对于每个新个体，在训练数据上进行分类，统计识别率，作为其适应度。在10个旧个体和10个新个体上，按随机型q-竞争法选择出10个个体。While到达最大迭代次数or最优适应度值连续10代没有变化。2-2）数据条件：有标注的字符图像集合，其中每个元素是一幅图像及其类别标注（是T或不是T）。学习过程：收集数据并标注；在数据集合上执行上述算法。额外答案：粒子群优化算法Foreach粒子初始化EndDoForeach粒子计算适应度if此适应度值好于此粒子对应的历史最佳适应度将此值作为此粒子历史最佳适应值pBest。End____选择粒子群体中所对应的最好适应度作为gBest____Foreach粒子根据该粒子当前飞行速度、该粒子最好适应度以及群体最好适应度，改变该粒子飞行速度，并调整其位置。____EndWhile算法到达最大迭代次数or适应度值小于给定的误差值用PSO算法优化BP神经网络权值的具体描述为：首先应将网络中所有神经元之间的连接权值编码成实数码串来表示一个粒子个体。网络中包含了400个待优化的权值以及一个阈值，则每个粒子个体将由401个参数组成的向量来表示。其次，初始化粒子群。初始化粒子群的规模、最大迭代次数、粒子个体极值等相关参数，并按照粒子群规模随机产生一定数量的粒子个体。初始化粒子的位置、速度。同时初始化粒子个体极值10和粒子群体极值。然后，利用PSO进行学习从而优化神经网络。在神经网络的权值优化过程中，给定的样本空间往往要分为两部分：一部分作为训练样本集；一部分作为测试样本集。计算每一个神经网络在训练集上产生的误差，并以此作为适应度函数，用来计算粒子个体的适应度值。计算当前时刻粒子群体对应的最好适应度以及每个粒