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

1课程编号：COM07043北京理工大学2011-2012学年第一学期2009级人工智能基础期末试题A卷标准答案一、判断题（10分，每小题1分）1.由于存在反向传播，BP神经网络为反馈型网络。（×）2.进化计算方法中的“群体”和群智能优化方法中的“群体”没有区别。（×）3.蚁群优化算法中，蚂蚁根据信息素对路径的选择是确定性的。（×）4.自组织特征映射网的学习方式为误差修正型学习。（×）5.强化学习是一种特定的监督学习方法。（×）6.离散函数可表示为决策树的形式。（√）7.代表StrongAI的思想实验是图灵测试。（×）8.机器学习的计算实质是函数估计。（√）9.A*算法中，在满足可容许性条件的前提下，启发式函数值越大越好。（√）10.机器学习中的奥坎姆剃刀原则表明应优先选择形式更为复杂的函数。（×）二、填空题（20分，每空2分）1.NouvelleAI的计算目标是在状态或感知和行动或反应之间建立映射关系。2.ParticleSwarmOptimization算法中的启发式信息是其他粒子的求解结果。3.给定两组数据，其中第一组数据为5,3,4,2,第二组数据为0,1,1,0，则用于分类这两组数据的感知器可以是：1x2xy11w12w3。4.语句“每个人都爱他的父亲或母亲”的一阶谓词逻辑表达式可以是xFatherxLovesxMotherxLovesxPersonx,,。5.给定二维数据集：A1(2,10),A2(2,5),B1(5,8),B2(7,5)2用k-均值聚类聚成两簇（采用欧几里德距离，初始时用A1,B1作为簇的均值），则迭代一次后，簇均值变为(2,10)和(14/3,6)。6.当前，计算模式的两个发展趋势是随机和并行。7.给定博弈树如下：51479631120MAXMINABCDEFGHIJKLMNO根据该博弈树，通过极大极小搜索所确定的当前行动方案是B或AB。如按从右到左顺序进行剪枝，则剪去的边有无。三、计算题（40分，每小题10分）1.兹有以下知识:（1）小李喜欢吃牛排，或者小李喜欢吃土豆。（2）如果小李既喜欢吃牛排又喜欢吃土豆，那么小李是一个不偏食的人。（3）如果某人喜欢吃牛排，那么他喜欢吃土豆。（4）如果某人喜欢吃土豆，那么他喜欢吃牛排。应用归结演绎推理方法证明：小李是一个不偏食的人。解：1）定义谓词eat(x,y)x喜欢吃y；not(s)s是一个不偏食的人；常量J：约翰；D：牛排；E：土豆2）表达知识（1）eat(J,D)∨eat(J,E)（2）eat(J,D)∧eat(J,E)→Not(J)（3）),(),()(ExeatDxeatx3（4）),(),()(DxeatExeatx3）将上述谓词化为子句：①eat(J,D)∨eat(J,E)②┓eat(J,D)∨┓eat(J,E)∨Not(J)③┓eat(x,D)∨eat(x,E)④┓eat(x,E)∨eat(x,D)4）结论求反并做为子句：⑤┓Not(J)5）执行归结：①③eat(J,E)⑥①④eat(J,D)⑦②⑥┓eat(J,D)∨Not(J)⑧⑦⑧Not(J)⑨⑤⑨Nil2.在如下图所示的GridWorld问题中：（1）灰色实心块表示障碍；（2）除了走到（4，3）与（4，2）处，可分别得到+1和-1的即时收益外，其余各处的即时收益均为0。请使用折扣为0.9的折扣收益计算该问题中的Q值，进而确定各状态下的最优行动。不考虑（4，3）与（4，2）处的Q值和行动。43.根据文档中是否包含“我”字来判断该文档是否是我所喜欢的文档。以往统计数据表明：在所有文档中，只有20%的文档是我所喜欢的。在我喜欢的文档中，包括“我”字的概率是98%；在我不喜欢的文档中，包含“我”字的概率是32%。现有一篇文档，其中包含“我”字，请根据贝叶斯决策规则，确定该文档是否是我所喜欢的文档。需给出计算过程。解：需比较我likeP与我likeP的大小来进行决策likePlikePPlikePlikePlikeP我我我我同理有likePlikePlikeP我我由于：196.02.098.0likePlikeP我256.08.032.0likePlikeP我因此，我我likePlikeP，应确定该文档不是我所喜欢的文档。54.给定数据集合及其决策结果如下：样本决策结果属性A1属性A2属性A31No3352Yes3613503Yes1514304No142265No237246Yes4188其中，根据A1,A2和A3的属性值是否大于10来进行决策。基于该数据集，利用最大信息增益准则生成一棵决策树。给出该决策树及其计算过程。（提示：6.13log2）解：第一步：A1的期望熵=21log2121log216242log4242log42642222=1A2的期望熵=22log226241log4143log4364222=04log1log614log3log432222=0.2+0.33=0.55A3的期望熵=31log3132log326331log3132log32632222=31log3132log3222=3log1log313log2log322222=0.4+0.53=0.93根据以上三个属性的期望熵，可知应选择A2作为决策树的根节点。第二步：根据A2的属性值是否大于10，以上样本集被分成两个子集。其中，对应于A2的属性值大于10的样本为2,3,4,6，对应于A2的属性值小于10的样本为1,5。由于1,5两个样本对应的决策结果都为No,因此可在决策树根节点的该分支上增加No的叶节点。对于样本2,3,4,6：6A1的期望熵=31log3132log324311log1141222=31log4132log21022=1log-3log412log-3log212222=0.3+0.4=0.7A3的期望熵=21log2121log214222log2242222=0+0.5=0.5根据以上两个属性的期望熵，可知应选择A3作为决策树根节点属性值大于10的分支的根节点。第三步：根据A3的属性值是否大于10，样本2,3,4,6被分成两个子集。其中对应于A3的属性值大于10的样本为2,3，对应于A2的属性值小于10的样本为4,6。由于2,3两个样本对应的决策结果都为Yes,因此可在决策树根节点的该分支上增加Yes的叶节点。对于样本4,6,可继续通过A1的属性值加以区分，并分别对应于No和Yes的叶节点。至此，决策树生成完毕，最终得到的决策树是：A2NoA2Yes7四、算法题（30分，每小题15分）1.在基于剪枝的计算机博弈程序中，在搜索深度被限定为一致的前提下，决定其下棋水平的关键因素是什么？能否利用机器学习技术解决该问题？如能，请设计出解决方案。解：决定其下棋水平的关键因素是棋局状态的估价函数，可以利用机器学习技术解决该问题。解决方案如下：采用多层前向神经网络评价棋局状态，其输入为当前棋局，输出为当前棋局的评估值。采用进化计算对该神经网络进行优化，优化目标是最大化博弈程序的胜率。首先，初始化若干个神经网络，其中节点权值按随机方式生成。然后利用其中每个神经网络对棋局状态进行评价，并在此基础上进行剪枝，从而得到一个计算机博弈程序。让每个神经网络对应的博弈程序与其他博弈程序或人进行博弈，统计其胜率，作为该神经网络的适应度。在此基础上，利用选择算子、交叉算子和变异算子对上述神经网络种群进行优化，直到达到所预期的最大胜率（适应度）或最大进化代数为止，此时输出胜率（适应度）最好的神经网络作为最终结果。2.给定函数：1009006023xxxxf，其中限定x为[0,31]区间中的实数。设计一种粒子群优化算法求解xf的最大值以及对应的x值。解：在所设计的算法中，粒子群体规模设置为20，其中每个粒子的位置表示一种x的取值，用实数表示，个体适应度值为1009006023xxx。最大迭代次数设置为100。具体算法流程如下：Step1.在[0,31]区间中随机生成20组成对的实数，作为粒子的初始位置和飞行速度。Step2.计算每个粒子的适应度。Step3.统计截止当前时刻，粒子群体对应的最好适应度以及每个粒子对应的最好适应度。Step4.对于每个粒子，根据该粒子当前飞行速度、该粒子最好适应度以及群体最好适应度，改变该粒子飞行速度，并根据更新后速度调整其位置。Step5.重复Step2-4，直到迭代次数超过100次。Step6.输出所得到的解答：群体最好适应度为所求得的函数最大值，该适应8度对应的粒子位置为所求得的的x值。