模式识别习题答案

1、1、PCA和LDA的区别？PCA是一种无监督的映射方法，LDA是一种有监督的映射方法。PCA只是将整组数据映射到最方便表示这组数据的坐标轴上，映射时没有利用任何数据内部的分类信息。因此，虽然做了PCA后，整组数据在表示上更加方便（降低了维数并将信息损失降到了最低），但在分类上也许会变彳#更加困难；LDA在增加了分类信息之后，将输入映射到了另外一个坐标轴上，有了这样一个映射，数据之间就变得更易区分了（在低纬上就可以区分，减少了很大的运算量），它的目标是使得类别内的点距离越近越好，类别间的点越远越好。3、最大似然估计和贝叶斯方法的区别？p（x|X）是概率密度函数，X是给定的训练样本的集合，在哪种情

2、况下，贝叶斯估计接近最大似然估计？最大似然估计把待估的参数看做是确定性的量，只是其取值未知。利用已知的样本结果，反推最有可能（最大概率）导致这样结果的参数值（模型已知，参数未知）。贝叶斯估计则是把待估计的参数看成是符合某种先验概率分布的随机变量。对样本进行观测的过程，把先验概率密度转化为后验概率密度，利用样本的信息修正了对参数的初始估计值。当训练样本数量趋于无穷的时候，贝叶斯方法将接近最大似然估计。如果有非常多的训练样本，使得p（x|X）形成一个非常显著的尖峰，而先验概率p（x）又是均匀分布，此时两者的本质是相同的。4、为什么模拟退火能够逃脱局部极小值？在解空间内随机搜索，遇到较优解就接受，遇

3、到较差解就按一定的概率决定是否接受，这个概率随时间的变化而降低。实际上模拟退火算法也是贪心算法，只不过它在这个基础上增加了随机因素。这个随机因素就是：以一定的概率来接受一个比单前解要差的解。通过这个随机因素使得算法有可能跳出这个局部最优解。5、最小错误率和最小贝叶斯风险之间的关系？基于最小风险的贝叶斯决策就是基于最小错误率的贝叶斯决策，换言之，可以把基于最小错误率决策看做是基于最小风险决策的一个特例，基于最小风险决策本质上就是对基于最小错误率公式的加权处理。6、SOM的主要功能是什么？怎么实现的？是winner-all-take-all策略吗？SOM是一种可以用于聚类的神经网络模型。自组织映射

4、（SOM）或自组织特征映射（SOFM）是一种使用非监督式学习来产生训练样本的输入空间的一个低维（通常是二维）离散化的表示的人工神经网络（ANN）。自组织映射与其他人工神经网络的不同之处在于它使用一个邻近函数来保持输入控件的拓扑性质。SOM网络中，某个输出结点能对某一类模式作出特别的反应以代表该模式类，输出层上相邻的结点能对实际模式分布中相近的模式类作出特别的反映，当某类数据模式输入时，对某一输出结点产生最大刺激（获胜结点），同时对获胜结点周围的一些结点产生较大刺激。在训练的过程中，不断对获胜结点的连接权值作调整，同时对获胜结点的邻域结点的连接权值作调整；随着训练的进行，这个邻域范围不断缩小，直

5、到最后，只对获胜结点进行细微的连接权值调整。不是winner-all-take-all策略。获胜结点产生刺激，其周围的结点也会产生一定程度的兴奋。7、期望算法需要哪两步？请列出可能的公式并做必要的解释。E-Step和M-Step。E-Step叫做期望化步骤，M-Step为最大化步骤。整体算法的步骤如下所示：1、初始化分布参数。2、（E-Step）计算期望E,利用对隐藏变量的现有估计值，计算其最大似然估计值，以此实现期望化的过程。3、（M-Step）最大化在E-步骤上的最大似然估计值来计算参数的值4、重复2,3步骤直到收敛。Q|/)=Ezlogp(X,Z16)1x,eF-step,根据之前的。值

6、求数据的期望0(i=argmaxQ(010(11)M-step:求0使期望最大化，作为下一次E-step的0值。8、在核密度估计(kerneldensityestimation)中，核独立就代表特征独立吗？朴素贝叶斯分类器的基本假设是什么？不能。(？)TheNa?/eBayesclassifiermakestheassumptionthatthefeaturesareclass-conditionallyindependent。DP(x|u)i)=nP(x(d)|u)j)d=19、假设数据维度(dimensionality)比给定的训练样本的个数多很多，请用PCA使计算复杂度依赖于数据的数量，

7、而不是依赖于数据的维度。1)计算协方差矩阵，得到协方差矩阵2)求协方差矩阵的特征值和特征向量3)选择主成分，将特征值按照从大到小的顺序排序，选择其中最大的 的k个特征向量分别作为列向量组成特征向量矩阵。k个，然后将其对应4)将样本点投影到选取的特征向量上。10、假设一个数据集(covariance matrix)的协方差矩阵是1)这个协方差矩阵的每个元素有什么意义？协方差矩阵的每个元素是各个向量元素之间的协方差，数据集是二维的，四个元素从左到右从上到下分别是向量的第一个和第一个元素之间的协方差，12,21,222)计算这数据集两个主成分(principalcomponents)Q2二E|Xi-

8、F(XJX2一旦丫川矩阵：AH=XA,H是特征向量矩阵的特征方程的表达式为|入E-A|二0(入-1)(入-1)-1/4=0入=3/2或者1/23)为什么PCA能够移除特征之间的相关性？PCA在降维的时候要尽量保存数据集中的有效信息，映射的方法是基变换，数据集在某个基上的投影值(也是在这个基上的坐标值)越分散，方差越大，这个基保留的信息也就越多。信息量保存能力最大的基向量一定是就是数据集的协方差矩阵的特征向量，并且这个特征向量保存的信息量就是它对应的特征值。11、一个K-class分类模型的先验概率是p(3k)=%k,并且类概率密度是p(xgk)。给定一个训练集Xn,tnn=1,2,3N,tni

9、sabinarytargetvectoroflengthkthatusesthe1-of-kcodingscheme,sothatisxnisfromclasswk,tnk=1,andtnj=0,forallotherj,jwk。彳反设数据点的描绘是独立于这个模型的，用最大似然估计在先验概率是兀k=Nk/N的情况下求解，Nk是数据点的数量由3k确定。解：12、对于下列模式：(0,0)T,(1,1)T,(-1,-1)T,(2,2)T,(-2,-2)T,(1,-1)T,(-1,1尸,使用K-L转换(或者说就是PCA)降低特征维数至一维，并给出详细的计算步骤。Step1:求x和y的平均值。然后对于所

10、有的样例，都减去对应的均值。X的均值是0,y的均值是0X:01-12-21-1Y:01-12-2-11n-1,不是n,所以错的)Step2：求协方差矩阵(应该除以9Step3:求协方差矩阵的特征值和特征向量特征值：20/74/7特征向量：(入E-A)X=0,入=20/7时，特征向量是1,1T,入=4/7时，特征向量是1,-1TStep4:将特征值按照从大到小的顺序排序，选择其中最大的k个，然后将其对应的k个特征向量分别作为列向量组成特征向量矩阵。所以选入=20/7,特征向量矩阵是1,1T。Step5:将样本点投影到选取的特征向量上。计算的步骁是；finalDai：a=DataAdJust+El

11、genVectorDataAdjust就是减去均值后的样本矩阵，Eigenvector就是特征向量矩阵最后的结果就是02-24-40013、使用基本分支定界法去执行牛!征选择的先决条件(prerequisite)是什么？为什么它先决条件是假设单调性，增加特征只会增加目标函数的值。在这样的假设条件下，增加特征的顺序对结果不会造成影响，就避免去搜索仅仅特征顺序不同的解，减少了计算代价。14、在特征选择方面，SFS(sequentialforwardselection)和SBS(sequentialbackwardselection)有什么区别？当最佳的特征子集从大量的特征中选出以后，两种方法哪一个

12、是令人满意的？特征子集X从空集开始，每次选择一个特征x加入特征子集X,使得特征函数J(X)最优。简单说就是，每次都选择一个使得评价函数的取值达到更优的特征加入，是一种简单的贪心算法。从特征全集。开始，每次从特征集。中剔除一个特征x,使得剔除特征x后评价函数值达到最优。SFS适用于最佳特征子集包含的牛I征个数较少的情况。SBS适用于最佳特征子集包含特征个数较多的情况。SFS缺点是只能加入特征而不能去除特征。SBS序列后向选择与序列前向选择正好相反，它的缺点是特征只能去除不能加入。另外，SFS与SBS都属于贪心算法，容易陷入局部最优值。双向搜索(BDS,BidirectionalSearch):算

13、法描述：使用序列前向选择(SFS)从空集开始，同时使用序列后向选择(SBS)从全集开始搜索，当两者搜索到一个相同的特征子集C时停止搜索。增L去R选择算法(LRS):该算法有两种形式：算法从空集开始，每轮先加入L个特征，然后从中去除R个特征，使得评价函数值最优。(LR)算法从全集开始，每轮先去除R个特征，然后加入L个特征，使得评价函数值最优。(L1,i=1,2,，N最大化Margin非线性SVM勺基本思想是低维线性不可分，把它投影到高维空间中使线性可分。是的，可移除，因为它对构成超平面不做贡献。先聚类，找出中心点，对中心点用SVM进行分类，以减轻负载。16、非线性SVM否和径向基函数(radia

14、lbasisfunction)具有一些相似性，如果有的话是什么？SVMRBF超平面表达方式一样，都是将低维线性不可分的数据映射到高维。只是优化时目标函数不同，SVM是最大化Margin,RBF是最小化错误率。17、如果需要设计一个脸部识别系统并且在这个系统中输入的图片样本的维度和训练样本的数量相比通常非常高，都有哪些处理步骤？对于每一步，你能列出一个或者多个解决方法吗？怎么评价你设计的这个系统的错误率？图像输入：使用摄像头或者从图库中获取。图像预处理：由于光照，环境以及人为影响，大多数情况下，系统采集的原始照片来自不同背景，不同条件，收到随机的干扰，这些图片不能被直接利用。光线补偿、高斯平滑处

15、理。特征提取：可以使用PCA进行特征提取。训练分类器：使用SVM寸已知样本进行分类。后处理如何评价：采用交叉验证，对原始数据进行分组，一部分做为训练集(trainset),另一部分做为验证集(validationset),首先用训练集对分类器进行训练，在利用验证集来测试训练得到的模型(model),以此来做为评价分类器的性能指标。18、Givenasetofdatapointsxn,wecandefinetheconvexhulltobethesetofallpointsxgivenbyx=EnnxnwhereEnn=1,an0.Considerasecondsetofpointsyntoge

16、therwiththeircorrespondingconvexhull.Showthatiftheirconvexhullintersect,thetwosetsofpointsx1andy1cannotbelinearlyseparable.感知器学习：能够处理线性可分的情况，如果线性不可分，则不具有收敛性，其优化准则是最小化错误。MSE能够保证收敛性，但线性可分时不一定能够找到实现分类的超平面，其优化准则是最小化训练数据到超平面的平方和。20、多层感知器中，什么方法用来避免过拟合?权重衰减，及早终止，增加噪声。21、在RBF（径向基函数）中，为什么在线性转换之后要跟一个非线性转换？哪些非

17、监督方法能够用来选择RBFcenter?低维线性不可分，映射到高维线性可分。随机选择、聚类、密度估计22、结构风险最小化的基本原则是什么？同时最小化经验风险和VC纬度，使二者达到平衡。23、在kerneldensityestimation中，核独立就表明特征独立吗？最大似然估计是怎样被用来为KDE选才Ibandwidthparameter的？朴素贝叶斯分类器的基本假设是什么？基本的KNNT法对噪声特征敏感，哪种方法能够用来改进这个？不是；结合似然函数进行交叉验证。经常使用留一交叉验证的方法最大化伪似然。特征是类条件独立的，公式在上面。对特征设置权重，以表达该特征的信息内容或作用价值。如果度量相似度的距离公式中对特征赋予不同权重，特征的权重一般根据各个特征在分类中的作用确定，或者根据特征在训练样本中的分类作用确定。24、考虑错误率，随机子抽样（randomsubsampling）方法和自助抽样法（BootstrapMethod）的区别？随机二次抽样：无放回的采样，一次数据只会被选择一次。自助法：有放回的采样，一个数据可能被选择多次，更符合现实情况（在每次验证时增大方差）25、ShowthatifX1andX2aretwo