人工智能(研究生)2013年试题_标准答案

1课程编号：21-081200-108-07北京理工大学2013-2014学年第一学期研究生《人工智能》期末试题班级学号姓名成绩1.学习（30分+5分）下图给出了两类数据，分别如图中和所示。另外，图中两条黑色粗实线分别代表横、纵坐标轴，其交点为原点。第1题图现要求对上述数据进行分类。(1)[10分]如果采用DecisionTree实现分类，请说明该DecisionTree的非叶节点、叶节点和边分别是什么，并计算以下两个值：(a)该数据集的Entropy;(b)当根节点选择根据x的值是否大于0来进行决策时，所对应的InformationGain。解：1）非叶节点为x与y，叶节点为类别，边为x与y的取值区间；2）两类样本分别为6个和9个，因此：69151522Entropy()logl6969(0.74)0.972151og(1.325)1515S3）254478728222Entropy(0)(loglo72584g)(log4157715log)88x((1.81)(0.49))72584((415771581)(1))0948.GainS,EntropySEntropy0.9720.940.032xx2(2)[10分]如果采用NaïveBayesianClassifier实现分类，并将x，y的取值分别离散化为“大于0”和“小于等于0”两种情况，请给出需要学习的数值及其结果，进而判断当0,0yx时的分类结果解：已知样本a={a1,a2}，其中a1为属性x的值,a2为属性y的值。类别集合C={黑框，白球}若给出某一测试用例m，则需计算P(黑框|m)与P(白球|m)，并据此来进行判别，但若要计算这两个概率值，则需要计算各个类条件概率，下面为具体的学习过程。Step1.根据给出的训练集，统计各类别以及各类别下各个特征属性的条件概率估计：xy0/1Step2.由于各个属性间是独立的，则根据贝叶斯定理有如下推导：xy0/1则可推导出样本xy0/1的类别。对于样本m={x0,y=0}判别其类别的过程如下：xy0/1因此，当x0,y=0则将其判别为白球类别。(3)[10分]如果采用NeuralNetwork实现分类，请画出能对上述数据进行分类的网络结构（不含权值），并说明如何根据上述数据学习得到该网络中的权值。解：采用多层感知器。该神经网络的输入神经元个数为2，分别表示x与y的值，输出神经元个数为1，1表示类别为黑框，0表示白球。隐含层神经元个数为4。则其结构如下：3xy0/1可利用BP学习算法来进行学习（最小二乘法、权值计算使用梯度下降等）。(4)（附加题）[5分]能否使用Clustering技术解决上述分类问题？如能，应怎样解决？解：可以采用聚类技术求解。用k-means算法将以上数据聚成两类，获得相应聚类中心。分类时，根据数据到聚类中心的距离来进行判定。可以用聚类算法。但由于数据是凹型数据，因此，直接用k-means算法无法得到满意，因此，可考试将此数据集映射到高维空间，使其变成凸型数据之后再对其使用类似于k-means的算法进行聚类。另外一种方法则是采用可以处理凹型数据的聚类算法，譬如PCCA（PerronClusterClusterAnalysis）方法。2.搜索（30分+5分）给定函数：22212111,xxxxf。要求计算该函数的最小值，其中21,xx的取值范围为]5,5[。(1)[10分]如果采用GradientDescent方法求解，请描述其中一次迭代过程。解：梯度下降法的基本思想为：假设我们要求函数的最小值，首先需要选取一个初始点，然后下一点的产生是沿着梯度直线方向，这里是沿着梯度的反方向（因为是求最小值）。梯度下降法的迭代公式为：1kkkkaas,其中，ks表示的是梯度的反方向，k表示的是在梯度方向上的搜索步长。梯度可以通过对函数求导取得，步长的确定比较麻烦，太大容易发散，太小收敛速度太慢。因此步长的选择需要沉思熟虑。另外，算法迭代的停止条件是梯度向量的幅值接近0即可。根据以上思想，对以下函数进行最小值求解。22(1,2)(11)(21)fxxxx，其中1[5,5]x以及2[5,5]x4由于此问题是存在约束条件下的最小值问题，在此条件下无法直接利用梯度下降法对其进行优化，需要将其进行转化，转化无约束条件下进行求解。因此有两种方法解决，一是采用拉格朗日定理对其转化，另一种是加入一个惩罚项，对超出约束条件的点进行惩罚。这里可采用加入惩罚项来解决。因此，将上述函数转化为以下函数表示：2[5,5]1[5,001000005]1[5,5]2[50010000000,5](1,2)(1,2)(1,2)(1,2)xxxxTxxfxxgxxgxx其中(1,2)gxx为处罚项。若x1与x2均在此约束范围内惩罚项的值为0，对函数值没有影响。下面是具体的一次迭代过程：首先，设置初始值为x1=0,x2=0.其次，计算梯度向量，对x1与x2求偏导：12,222212ffxxxx然后，计算下一点的值：22211122)'(()222()'()2xxxxxx由于此值均在约束条件下，所以21'(0',)xgx此次迭代结束。(2)[10分]设计一个求解该问题的EvolutionaryAlgorithm。解：/*初始化遗传算法参数*/constintmaxGeneration;//进化代数，即迭代次数constintsizeGene;//种群规模doublepcross;//交叉概率选择，0和1之间5doublepmutation;//变异概率选择，0和1之间int*bestGene;//适应度最好的染色体doublebestFitness;//记录进化中最高的适应度structgene//每个染色体的结构{Doublevalue[2];//存的是x1与x2的值;intfitness;//适应度函数值};doubleFitness()/*适应度函数计算*/{doublefit=22(11)(21)xx;}main(){//初始化种群fori=0,isizeGene;i++{随机产生一个初始解//此处产生种群时，需注意两点：一是产生的染色体是实数型，另一点是其值需要在约束条件范围内计算其适应度}//进化开始t=1//进化代数6do{选择;交叉;变异;重新计算适应度函数F();bestGene=此代进化中适应度最高的染色体//记录最优解进化代数t=t+1;}while(适应度函数F()收敛||tmaxGeneration)//进化结束bestGene存储的即为最佳路径;}(3)[10分]设计一个求解该问题的SwarmIntelligenceAlgorithm。解：在所设计的算法中，粒子群体规模设置为20，其中每个粒子的位置表示一种21,xx的取值，用实数表示，个体适应度值为22(11)(21)xx。最大迭代次数设置为100。具体算法流程如下：Step1.在[-5,5]区间中随机生成20组两两一对的4个实数，作为粒子21xx和的初始位置和飞行速度。Step2.计算每个粒子的适应度。Step3.统计截止当前时刻，粒子群体对应的最好适应度以及每个粒子对应的最好适应度。Step4.对于每个粒子，根据该粒子当前飞行速度、该粒子最好适应度以及群体最好适应度，改变该粒子飞行速度，并根据更新后速度调整其位置。Step5.重复Step2-4，直到迭代次数超过100次。Step6.输出所得到的解答：群体最好适应度为所求得的函数最小值，该适应度对应的粒7子位置为所求得的21,xx值。(4)（附加题）[5分]请用一种统一的算法结构来总结以上三种算法。解：通过对解的变化，来访问不同的解，直至获得最优解（参考新教材第6章）构造及初始化解空间，选择一种启发式信息，迭代求解直到算法收敛或满足一定的迭代次数。所得到的解即为找到的最优解。A初始点的选取；B计算在此自变量下函数的值；C判断是否符合终止条件，若符合则终止，相应的函数值即为所求的解，若不符合，则根据某种搜索准则，选择下一次自变量的值，再次计算函数值，直至符合终止条件。其中，搜索准则严重影响了迭代终止的时间与解的质量，也就是常提及的收敛速度及最优解的全局性与局部性。3.综合应用（40分）现要求设计一个智能系统，用于根据摄像头拍摄的路况进行汽车自动驾驶。假设摄像头输入的图像为20×20大小的二值图像，其中每个点取值为1或0，当取值为1时表示该点为黑色，否则为白色。根据此输入，该智能系统从8种控制指令中选择一种指令输出，这8种指令包括起步、直行、左转、右转、加速、减速、刹车、停车。请给出该智能系统的设计结果，包括Perception部分、Performance部分、Evaluation部分以及Learning部分。其中Performance部分只需说明软件部分即可，即只需设计从接受输入的图像到产生控制指令的部分，忽略后面的机械控制等硬件部分。解：（1）Perception部分：摄像头，向系统中输入路况图像。（2）Performance部分：即为从Perception部分接收的图像后，根据learning部分学习得到的模型判别给出需要执行的操作。此处采用多层感知器，其结构如下：12400...12...20018其中，第一层为输入层，接受输入的字符图像，图像大小为20×20，因此，输入神经元有400个，每个输入神经元对应于图像中的一个像素。第二层为隐含层，其神经元个数确定为200个。最后一层为输出层，为1个神经元，输出为1-8的整数，对应8种指令即起步、直行、左转、右转、加速、减速、刹车、停车。（3）Evaluation部分：根据车辆自动驾驶时的操作性能，即不必人干预的程度，查看操作是否正确。正确与否的标准是与人面对Perception时所做的操作是否一致。（4）Learning部分：给出训练数据集（有操作的图像集合，其中每个元素是一幅图像及其相应8种操作标注）的基础上，采用人工神经网络结构用于完成汽车自动驾驶任务的学习，其结构如Performance部分所述。其中神经网络中的各个权值采用进化规划算法来学习。首先，将网络中所有神经元之间的连接权值连接起来作为一个个体。其次，迭代学习，相应伪码如下：随机生成10个个体。对于每个个体，在训练数据上进行分类（相当于多类划分），统计识别率，作为其适应度。Do统计最优适应度值对于每个个体，按照高斯扰动方法进行突变，获得10个新个体。对于每个新个体，在训练数据上进行分类，统计识别率，作为其适应度。在10个旧个体和10个新个体上，按随机型q-竞争法选择出10个个体。While到达最大迭代次数or最优适应度值连续10代没有变化。最后，最好适应度（即统计识别率最高）为所求得的解，即相应的指令操作。附：可采用神经网络的算法进行学习。具体过程为：采用单层感知器对图像进行识别。9首先确定输入输出数据。将待识别的图像转化成网络所能接受的输入数据。可采用20×20的点阵处理，其元素值为1或0。因此，有400个输入点。输出为一个十进制值，可将其转化成8位的字符串，其表示起步，直行，左转，右转，加速，减速，刹车以及停车相应操作，其值为1时，表示执行此操作，其值为0时，表示不执行此操作，注意，此表示形式能够表示多种操作同时进行的行为。激活函数为阈值函数，可根据训练样本集自定义一种阈值函数。使其满足某种条件下输出某个值。其次，给出容许的目标误差及最大训练次数。最后，确定权值与阈值。可采用粒子群优化算法优化BP神经网络权值。具体描述为：先将网络中所有神经元之间的连接权值编码成实数码串来表示一个粒子个体。网络中包含了400个待优化的权值以及一个阈值，则每个粒子个体将由401个参数组成的向量来表示。初始化粒子群之后利用PSO进行学习从而优化