下载文档原格式
模式识别与机器学习期末考查思考题1：简述模式识别与机器学习研究的共同问题和各自的研究侧重点。
机器学习是研究让机器（计算机）从经验和数据获得知识或提高自身能力的科学。
机器学习和模式识别是分别从计算机科学和工程的角度发展起来的。
然而近年来，由于它们关心的很多共同问题（分类、聚类、特征选择、信息融合等），这两个领域的界限越来越模糊。
机器学习和模式识别的理论和方法可用来解决很多机器感知和信息处理的问题，其中包括图像/视频分析、（文本、语音、印刷、手写）文档分析、信息检索和网络搜索等。
近年来，机器学习和模式识别的研究吸引了越来越多的研究者，理论和方法的进步促进了工程应用中识别性能的明显提高。
机器学习：要使计算机具有知识一般有两种方法；一种是由知识工程师将有关的知识归纳、整理，并且表示为计算机可以接受、处理的方式输入计算机。
另一种是使计算机本身有获得知识的能力，它可以学习人类已有的知识，并且在实践过程中不总结、完善，这种方式称为机器学习。
机器学习的研究，主要在以下三个方面进行：一是研究人类学习的机理、人脑思维的过程；和机器学习的方法；以及建立针对具体任务的学习系统。
机器学习的研究是在信息科学、脑科学、神经心理学、逻辑学、模糊数学等多种学科基础上的。
依赖于这些学科而共同发展。
目前已经取得很大的进展，但还没有能完全解决问题。
模式识别：模式识别是研究如何使机器具有感知能力，主要研究视觉模式和听觉模式的识别。
如识别物体、地形、图像、字体（如签字）等。
在日常生活各方面以及军事上都有广大的用途。
近年来迅速发展起来应用模糊数学模式、人工神经网络模式的方法逐渐取代传统的用统计模式和结构模式的识别方法。
特别神经网络方法在模式识别中取得较大进展。
理解自然语言计算机如能“听懂”人的语言（如汉语、英语等），便可以直接用口语操作计算机，这将给人们带来极大的便利。
计算机理解自然语言的研究有以下三个目标：一是计算机能正确理解人类的自然语言输入的信息，并能正确答复（或响应）输入的信息。
Lecture5 答案作业一：写出上下文无关文法，其终止符集V T={a,b}能生成语言L(G)={ab,ba,aba,bab,abab,baba,…}答案：上下文无关文法：G=(V,T,S,P)，V={S,A,B},T={a,b},P如下：S->aAb|aAba|bBa|bBabA->baA|∈B->abB|∈作业二：求一有限态自动机，它只能接受由“偶数个a”与/或“偶数个b”组成的任意字符串，例如：aa, bb, abab, abba, baba等。
答案：其中文法为：G=(V,T,S,P)，V={S,A,B,C}，T={a,b},P如下：S->aA|bBA->aS|bC|aB->aC|bS|bC->aB|bA其有限态自动机为：作业三：自己定义基元，用PDL文法生成0到5的字符，字符笔划用七划样式。
答案：文法G = (V N, V T, P, S)，其中V N={S,S0,S1,S2,S3,S4,S5,A,B,C,D}，V T={ a↓, b→, (, ),+,*,~,-}，P：S->S0|S1|S2|S3|S4|S5，A->((~a+b)+a)，B->((a+b)+~a)，C->(b+a)，D->((~b+a)+b) S0->A*B，S1->(a+a)，S2->C+D，S3->((C-b)+a)-b，S4->((a+b)-a)+a，S5->D+a+(~b)作业四：试用树文法生成单位边长的立方体，定义三个基元为立方体的三种方向的边。
答案：对于该树状结构。
可以对应有一个上下文无关文法G=({S, A}, {$, a, b, c}, P, S)P: S->$AAA，A->aAA，A->bA，A->c,A->cAA,A->aA,A->b,A->bAA,A->cA,A->a则G T’=({S, A}, {$, a, b, c, (, )}, P’, S)P’: S->($AAA)，A->(aAA)，A->(bA)，A->(c),A->(cAA),A->(aA),A->(b),A->(bAA), A->(cA),A->(a)由G生成：S=>$AAA=>$aAAAA=>$abAAAA=>$abcAAA=>$abccAA=>$abcccAAA=>$abcccaAAA =>$abcccabAA=>$abcccabbA=>$abcccabbbAA=>$abcccabbbcAA=>$abcccabbbcaA=>$abcc cabbbcaa由G T’生成：S=>($AAA)=>($(aAA)AA)=>($(a(bA)A)AA)=>($(a(b(c))A)AA)=>($(a(b(c))(c))AA)=>( $(a(b(c))(c))(cAA)A)=>($(a(b(c))(c))(c(aA)A)A)=>($(a(b(c))(c))(c(a(b))A)A)=>($( a(b(c))(c))(c(a(b))(b))A)=>($(a(b(c))(c))(c(a(b))(b))(bAA))=>($(a(b(c))(c))(c(a (b))(b))(b(cA)A))=>($(a(b(c))(c))(c(a(b))(b))(b(c(a))A))=>($(a(b(c))(c))(c(a(b) )(b))(b(c(a))(a)))作业五：给出字符串样本集为{aaacc, aaacb, aacc, bacb, aaa, abc, bb, cc}推断一个有限态文法。
Contents卷一、模式识别机经 (3)卷二、2008~2009秋_模式识别_张学工_期末B (5)卷三、2007~2008秋_模式识别_张学工_期末B (7)卷四、2007~2008秋_模式识别_张学工_期末A (10)卷五、2006~2007秋_模式识别_张学工_期末B (11)卷六、2005~2006秋_模式识别_张学工_期末 (12)卷七、2004~2005秋_模式识别_张学工_期末 (13)卷八、2003~2004秋_模式识别_张学工_期末 (14)卷九、1999~2000春_模式识别_张学工_期末 (14)附录、名词以及原理 ................................................... 错误!未定义书签。
卷一、模式识别机经１．设计最小错误率分类器：如果12(|)(|)P x P x ωω>则x 为1ω反之12(|)(|)P x P x ωω<则x 为2ω（特别的，当12(|)(|)P x P x ωω=，可以接受x 为任何一类也可以拒绝。
在连续情况下这种情况几乎完全不出现。
1122(|)()(|)(|)()(|)()i i i p x P P x p x P p x P ωωωωωωω=+，112212,(|)(|),(|)(|)when P x P x x when P x P x ωωωωωω>⎧∈⎨<⎩ 2．画图如下，红色表示1(|)P x ω（[5,10]均匀分布的后验概率），蓝色表示2(|)P x ω（N(0,9)的后验概率）（注意图是错的——作者）（图是错的）3．最小错误分类器有许多局限性。
其一，其只考虑到错误率的限制，并未考虑到实际情况中不同错误的代价等等，为了克服这类局限性，学者们在最小错误率之外又设计了最小风险分类器、限定一类错误率令另一类错误率最小的分类器等；其二，其只能用于监督学习，要求已知分类情况，并且要满足I.I.D 条件即样本与总体分布相符；其三，其要求必须知道先验概率，许多实际问题的先验概率是难以得到的。
中国科学院大学课程编号:712008Z 试 题 专 用 纸 课程名称：机器学习任课教师：卿来云———-—-————-————-—————---———-—--————-——————--—-—姓名学号 成绩一、基础题（共36分）1、请描述极大似然估计MLE 和最大后验估计MAP 之间的区别。
请解释为什么MLE 比MAP 更容易过拟合。
（10分)2、在年度百花奖评奖揭晓之前,一位教授问80个电影系的学生，谁将分别获得8个奖项（如最佳导演、最佳男女主角等）。
评奖结果揭晓后，该教授计算每个学生的猜中率，同时也计算了所有80个学生投票的结果。
他发现所有人投票结果几乎比任何一个学生的结果正确率都高。
这种提高是偶然的吗？请解释原因。
（10分）3、假设给定如右数据集，其中A 、B 、C 为二值随机变量，y 为待预测的二值变量。
(a) 对一个新的输入A =0, B =0， C =1,朴素贝叶斯分类器将会怎样预测y ?（10分）(b) 假设你知道在给定类别的情况下A 、B 、C 是独立的随机变量,那么其他分类器（如Logstic回归、SVM 分类器等）会比朴素贝叶斯分类器表现更好吗?为什么?（注意：与上面给的数据集没有关系。
）（6分） 二、回归问题。
（共24分) 现有N 个训练样本的数据集(){}1,Ni i i x y ==,其中,i i x y 为实数.1． 我们首先用线性回归拟合数据。
为了测试我们的线性回归模型，我们随机选择一些样本作为训练样本,剩余样本作为测试样本。
现在我们慢慢增加训练样本的数目，那么随着训练样本数目的增加,平均训练误差和平均测试误差将会如何变化？为什么？（6分） 平均训练误差：A 、增加 B 、减小 平均测试误差：A 、增加 B 、减小2． 给定如下图(a)所示数据。
粗略看来这些数据不适合用线性回归模型表示。
因此我们采用如下模型:()exp i i i y wx ε=+，其中()~0,1i N ε。
1、贝叶斯分类器贝叶斯分类器的定义：在具有模式的完整统计知识的条件下，按照贝叶斯决策理论进行设计的一种最优分类器。
贝叶斯分类器的分类原理：通过某对象的先验概率，利用贝叶斯公式计算出其后验概率，即该对象属于某一类的概率，选择具有最大后验概率的类作为该对象所属的类。
贝叶斯分类器是各种分类器中分类错误概率最小或者在预先给定代价的情况下平均风险最小的分类器。
贝叶斯的公式：什么情况下使用贝叶斯分类器：对先验概率和类概率密度有充分的先验知识，或者有足够多的样本，可以较好的进行概率密度估计，如果这些条件不满足，则采用最优方法设计出的分类器往往不具有最优性质。
2、K近邻法kNN算法的核心思想:如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。
假设有N个已知样本分属c个类,考察新样本x在这些样本中的前K个近邻，设其中有个属于类，则类的判别函数就是决策规则:若则∈什么情况下使用K近邻法:kNN只是确定一种决策原则，在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别,并不需要利用已知数据事先训练出一个判别函数，这种方法不需要太多的先验知识。
在样本数量不足时，KNN法通常也可以得到不错的结果。
但是这种决策算法需要始终存储所有的已知样本，并将每一个新样本与所有已知样本进行比较和排序，其计算和存储的成本都很大。
对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。
3、PCA和LDA的区别Principal Components Analysis(PCA)：uses a signal representation criterionLinear Discriminant Analysis(LDA)：uses a signal classification criterionLDA：线性判别分析，一种分类方法。
它寻找线性分类器最佳的法线向量方向，将高维数据投影到一维空间，使两类样本在该方向上的投影满足类内尽可能密集，类间尽可能分开。
题型：1.填空题5题填空题2.名词解释4题3.问答题4题4.计算作图题3题5.综合计算题1题备注1：没有整理第一章和第六章，老师说不考的备注2：非线性判别函数相关概念P69概率相关定义、性质、公式P83以后最小错误率贝叶斯决策公式P85最小风险贝叶斯P86正态贝叶斯P90综合计算有可能是第六次作业一、填空题物以类聚人以群分体现的是聚类分析的基本思想。
模式识别分类：1.从实现方法来分模式识别分为监督分类和非监督分类；2.从理论上来分，有统计模式识别，统计模式识别，模糊模式识别，神经网络模式识别法聚类分析是按照不同对象之间的差异，根据距离函数的规律做模式分类的。
模式的特性：可观察性、可区分性、相似性模式识别的任务：一是研究生物体（包括人）是如何感知对象的，二是如何用计算机实现模式识别的理论和方法。
计算机的发展方向：1.神经网络计算机－－模拟人的大脑思维；2.生物计算机－－运用生物工程技术、蛋白分子作芯片；3.光计算机－－用光作为信息载体，通过对光的处理来完成对信息的处理。
训练学习方法：监督学习、无监督学习（无先验知识，甚至类别数也未知）。
统计模式识别有：1.聚类分析法（非监督）；2.判决函数法/几何分类法(监督)；3.基于统计决策的概率分类法 - 以模式集在特征空间中分布的类概率密度函数为基础，对总体特征进行研究，以取得分类的方法数据的标准化目的：消除各个分量之间数值范围大小对算法的影响模式识别系统的基本构成：书P7聚类过程遵循的基本步骤：特征选择；近邻测度；聚类准则；聚类算法；结果验证；结果判定。
相似测度基础：以两矢量的方向是否相近作为考虑的基础,矢量长度并不重要。
确定聚类准则的两种方式：阈值准则，函数准则基于距离阈值的聚类算法——分解聚类：近邻聚类法；最大最小距离聚类法类间距离计算准则:1）最短距离法2）最长距离法 3）中间距离法4）重心法5）类平均距离法6）离差平方和法P24系统聚类法——合并的思想用于随机模式分类识别的方法，通常称为贝叶斯判决。
模式识别期末复习笔记模式识别ch2 贝叶斯决策1.贝叶斯公式2.贝叶斯决策的特例a)先验概率相同（均匀先验概率）：决策仅依赖于类条件概率密度b)类条件概率密度相同：决策仅依赖于先验概率3.计算题（医学测试⽅法）4.计算题（车⾝⾼低）5.贝叶斯决策的最优性a)最⼩化误差概率的⾓度i.每次均选择概率⼤的类做判断结果，因此错误概率永远是最⼩的b)最⼩化风险的⾓度i.每次均选择条件风险最⼩的结果，因此总风险最⼩6.对于两类分类问题，最⼩风险贝叶斯决策a)可以基于似然⽐进⾏决策b)p(x|ω1)p(x|ω2)≥λ12?λ22λ21?λ11p(ω2)p(ω1)则判断为1类，否则为2类c)似然⽐超过某个阈值（θ），那么可判决为ω1类7.0-1损失（误判是等价的）：最⼩化风险就是最⼤化后验，也就是选择后验最⼤的a)最⼩化误差概率与最⼩化风险等价，即选择最⼤后验的分类，即满⾜最⼩误差概率，也满⾜最⼩风险8.先验概率未知时如何设计风险最⼩的分类器？a)使先验概率取任意值时的总风险的最坏情况尽可能⼩b)极⼩化极⼤准则：i.极⼩化指的是贝叶斯风险，因为它是总风险的最⼩值ii.极⼤化指的是使贝叶斯风险达到最⼤iii.贝叶斯风险是和先验有关的，其最⼤也就是其极值，就是导数等于0 的时候c)极⼩化极⼤风险是最坏的贝叶斯风险9.从最⼩化误差概率的意义上讲，贝叶斯是最优的；贝叶斯决策得到的总风险也是最⼩的10.判别函数a)对于两类分类，根据判别函数的正负进⾏类的判断；对于多类问题，两两组成两类问题b)两类问题下：g(x)=g1(x)?g2(x)i.若g(x)≥0，即g1(x)≥g2(x)，则判断为1类，否则为2类c)g1(x)，g2(x)的设计i.最⼩总风险贝叶斯分类器1.g1(x)=?R(α1|x)，风险的相反数ii.最⼩误差概率贝叶斯分类器1. g 1(x )=p (ω1|x )2. g 1(x )=p (x|ω1)p (ω1)3. g 1(x )=log(p (x|ω1))+log(p (ω1))11.12. 计算题（决策边界为何下偏）ch3 参数估计1. 模式分类的途径（截图）2. 当可⽤数据很多以⾄于减轻了先验知识的作⽤时，贝叶斯估计可退化为最⼤似然估计。
