哈工大模式识别课件

模式识别授课老师：刘家锋第一章绪论一、模式识别的概念什么是模式识别？模式识别探讨的内容？二、模式识别的应用工业用途：产品质量检验，设备故障检测，智能机器人的感知系统；商业用途：钱币的自动识伪，信函的自动分拣，电话信息查询，声控拨号；医学用途：对心电、脑电、CT等信号进行处理和识别，自动进行疾病的诊断；平安领域：生理特征鉴别(Biometrics)，网上电子商务的身份确认，对公安对象的刑侦和鉴别；二、模式识别的应用军事领域：巡航导弹的景物识别，战斗单元的敌我识别；办公自动化：文字识别技术和声音识别技术；数据挖掘：数据分析；网络应用：文本分类。三、相关领域人工智能：ArtificialIntelligence(AI)模式识别：PatternRecognition(PR)机器学习：MachineLearning人工神经网络：NeuralNetwork(NN)计算机视觉：ComputerVision(CV)四、模式识别的过程什么是特征？什么是特征？什么是特征？特征抽取特征抽取特征的分布特征的分布五、模式识别系统分类训练六、模式识别问题的描述给定一个训练样本的特征矢量集合：分别属于c个类别：设计出一个分类器，能够对未知类别样本x进行分类分类方法模式识别方法的分类有监督学习（有老师学习）：预先已知训练样本集中每个样本的类别标号；无监督学习（无老师学习）：预先不知道训练样本集中每个样本的类别标号；七、参考书目RichardDuda,PeterHart,DavidStork,PatternClassification,2ndedition,JohnWiley,2001《模式分类》，机械工业出版社，RichardO.Duda《模式识别》（其次版），清华高校出版社，边肇祺，张学工；期刊IEEETransactiononPatternAnalysisandMachineIntelligence，PAMI；PatternRecognition；PatternRecognitionLetter；模式识别与人工智能；讲义下载: 22

用户名:prai

密码:prai其次章贝叶斯决策理论2.1最小错误率准则各种概率及其关系先验概率：后验概率：类条件概率：贝叶斯公式：两个类别，一维特征两类问题的错误率视察到特征x时作出判别的错误率：两类问题最小错误率判别准则：多类问题最小错误率判别x属于ωi的错误率：判别准则为：则：贝叶斯最小错误率准则Bayes判别准则：，则贝叶斯分类器的错误率估计例2.1对一大批人进行癌症普查，设ω1类代表患癌症，ω2类代表正常人。已知先验概率：

以一个化验结果作为特征x:{阳性，阴性}，患癌症的人和正常人化验结果为阳性的概率分别为：

现有一人化验结果为阳性，问此人是否患癌症？2.2最小平均风险准则贝叶斯分

类器问题的提出有c个类别ω1,ω2,...,

ωc,将ωi类的样本判别为ωj类的代价为λij。将未知模式x判别为ωj类的平均风险为：最小平均风险判别准则利用Bayes公式，构造判别函数：贝叶斯分类器例2.2

对一大批人进行癌症普查，设ω1类代表患癌症，ω2类代表正常人。已知先验概率：

以一个化验结果作为特征x:{阳性，阴性}，患癌症的人和正常人化验结果为阳性的概率分别为： 判别代价：λ11=0,λ22=0,λ12=100,λ21=25

现有一人化验结果为阳性，问此人是否患癌症？2.3贝叶斯分类器的其它版本先验概率P(ωi)未知：微小化极大准则；约束确定错误率（风险）：Neyman-Pearson准则；某些特征缺失的决策：连续出现的模式之间统计相关的决策：2.4正态分布的贝叶斯分类器单变量正态分布密度函数（高斯分布）：多元正态分布函数正态分布的判别函数贝叶斯判别函数可以写成对数形式：类条件概率密度函数为正态分布时：状况一：判别函数可以写成：此分类器称为距离分类器，判别函数可以用待识模式x与类别均值μi之间的距离表示：状况二：判别函数可以写成：可以简化为： 称为线性分类器线性分类器两类问题，1维特征，先验概率相同时：线性分类器两类问题，高维特征，先验概率相同时：线性分类器两类问题，1维特征，先验概率不同时：线性分类器两类问题，高维特征，先验概率不同时：状况三：随意判别函数可以写成：分类界面为2次曲线（面）二次分类曲线二次分类曲面第三章概率密度函数的参数估计3.0引言贝叶斯分类器中最主要的问题是类条件概率密度函数的估计。问题可以表示为：已有c个类别的训练样本集合D1，D2，…，Dc，求取每个类别的类条件概率密度。概率密度函数的估计方法参数估计方法：预先假设每一个类别的概率密度函数的形式已知，而具体的参数未知；最大似然估计(MLE,MaximumLikelihoodEstimation)；贝叶斯估计(BayesianEstimation)。非参数估计方法。3.1最大似然估计样本集D中包含n个样本：x1，x2，…,xn，样本都是独立同分布的随机变量(i.i.d，independentidenticallydistributed)。对类条件概率密度函数的函数形式作出假设，参数可以表示为参数矢量θ：似然函数由独立同分布假设，样本集D出现的概率为：定义对数似然函数：最大似然估计最大似然估计就是要找寻到一个最优矢量，使得似然函数最大。正态分布的似然估计Gauss分布的参数由均值矢量μ和协方差矩阵Σ构成，最大似然估计结果为：3.2贝叶斯估计已有独立同分布训练样本集D；已知类条件概率密度函数p(x|θ)的形式，但参数θ未知；已知参数θ的先验概率密度函数p(θ)；求在已有训练样本集D的条件下，类条件概率密度函数p(x|D)。贝叶斯估计与最大似然估计的差别最大似然估计认为θ是一个确定的未知矢量；贝叶斯估计认为θ是一个随机变量，以确定的概率分布取全部可能的值。贝叶斯估计的一般理论由于参数矢量θ是一个随机变量，所以类条件概率可以用下式计算：依据贝叶斯公式，有：单变量正态分布的贝叶斯估计已知概率密度函数满足正态分布，其中方差σ2已知，均值μ未知，假设μ的先验概率满足正态分布，即：均值的后验概率经推导可得，在已知训练样本集合D的条件下，参数μ的分布：均值的后验概率均值的后验概率仍满足正态分布，其中：均值分布的变更类条件概率密度的计算3.3期望最大化算法(EM算法)EM算法的应用可以分为两个方面：训练样本中某些特征丢失状况下，分布参数的最大似然估计；对某些困难分布模型假设，最大似然估计很难得到解析解时的迭代算法。基本EM算法令X是视察到的样本数据集合，Y为丢失的数据集合，完整的样本集合D=XY。由于Y未知，在给定参数θ时，似然函数可以看作Y的函数：基本EM算法由于Y未知，因此我们须要找寻到一个在Y的全部可能状况下，平均意义下的似然函数最大值，即似然函数对Y的期望的最大值：基本EM算法begininitialize

，T，i0；

doii+1

E步：计算;

M步：

until

return

混合密度模型一个困难的概率密度分布函数可以由多个简洁的密度函数混合构成：最常用的是高斯混合模型(GMM，GaussMixture

Model)：GMM模型产生的2维样本数据两个高斯函数的混合混合密度模型的参数估计混合密度模型的参数可以表示为：参数的估计方法：利用最优化方法干脆对似然函数进行优化，如梯度下降法；引入未知隐变量Y对问题进行简化，将Y看作丢失的数据，运用EM算法进行优化。GMM模型的参数估计首先引入隐含数据集合:其中：代表第i个训练样本是由第个高斯函数产生的，将Y作为丢失数据集合，接受EM算法进行迭代估计。GMM参数的EM估计算法设定混合模型数M，初始化模型参数，阈值T，i0；用下列公式迭代计算模型参数，直到似然函数变更小于T为止：EM算法的性质EM算法具有收敛性；EM算法只能保证收敛于似然函数的局部最大值点（极值点），而不能保证收敛于全局最优点。隐含Markov模型

(HiddenMarkovModel,HMM)有一些模式识别系统处理的是与时间相关的问题，如语音识别，手势识别，唇读系统等；对这类问题接受一个特征矢量序列描述比较便利，这类问题的识别HMM取得了很好的效果。输入语音波形视察序列信号的特征须要用一个特征矢量的序列来表示：其中的vi为一个特征矢量，称为一个视察值。一阶Markov模型一阶Markov模型由M个状态构成，在每个时刻t，模型处于某个状态w(t)，经过T个时刻，产生出一个长度为T的状态序列WT=w(1),…,w(T)。一阶Markov模型的状态转移模型在时刻t处于状态wj的概率完全由t-1时刻的状态wi确定，而且与时刻t无关，即：Markov模型的初始状态概率模型初始于状态wi的概率用表示。完整的一阶Markov模型可以用参数

表示，其中：一阶Markov模型输出状态序列的概率模型输出状态序列的概率可以由初始状态概率与各次状态转移概率相乘得到。例如：W5=w1,w1,w3,w1,w2，则模型输出该序列的概率为：一阶隐含Markov模型隐含Markov模型中，状态是不行见的，在每一个时刻t，模型当前的隐状态可以输出一个视察值。隐状态输出的视察值可以是离散值，连续值，也可以是一个矢量。HMM的工作原理HMM的内部状态转移过程同Markov模型相同，在每次状态转移之后，由该状态输出一个视察值，只是状态转移过程无法视察到，只能视察到输出的视察值序列。以离散的HMM为例，隐状态可能输出的视察值集合为{v1,v2,…,vK}，第i个隐状态输出第k个视察值的概率为bik。例如：T=5时，可能的视察序列V5=v3v2v3v4v1HMM的工作过程HMM的参数表示状态转移矩阵：A，M*M的方阵；状态输出概率：B，M*K的矩阵；初始概率：π，包括M个元素。

M个状态，K个可能的输出值。HMM的三个核心问题估值问题：已有一个HMM模型，其参数已知，计算这个模型输出特定的视察序列VT的概率；解码问题：已有一个HMM模型，其参数已知，计算最有可能输出特定的视察序列VT的隐状态转移序列WT；学习问题：已知一个HMM模型的结构，其参数未知，依据一组训练序列对参数进行训练；估值问题一个HMM模型产生视察序列VT可以由下式计算：rmax=MT为HMM全部可能的状态转移序列数；为状态转移序列输出视察序列的概率；为状态转移序列发生的概率。估值问题的计算计算困难度：HMM估值算法的简化HMM的前向算法初始化：迭代计算：结束输出：计算困难度：解码问题解码问题的计算同估值问题的计算类似，最直观的思路是遍历全部的可能状态转移序列，取出最大值，计算困难度为：O(MTT)。同样存在着优化算法：Viterbi算法。Viterbi算法因为须要回朔最优路径，所以建立一个矩阵Φ，其元素保存第t步，第i个状态在第t-1步的最优状态。初始化：迭代计算：结束：路径回朔：Viterbi算法图示学习问题HMM的学习问题： 已知一组视察序列(训练样本集合)：

如何确定最优的模型参数θ，使得模型产生训练集合V的联合概率最大 这同样是一个最大似然估计问题，须要接受EM算法。图示变量说明：表示在t-1时刻HMM处于状态ωi，并且从1t-1时刻之间产生视察序列V1t-1的概率；：表示在t时刻HMM处于状态ωj，并且从t+1T时刻之间产生视察序列Vt+1T的概率；变量说明输出视察序列VT时，在t-1时刻HMM处于ωi状态，在时刻t处于ωj状态的概率：前向-后向算法(Baum-Welch算法)迭代公式： 初始概率： 状态转移概率： 输出概率：HMM的其它问题连续HMM模型：在视察序列中每个视察值是一个特征矢量，相应的模型中输出概率b就须要用一个概率密度函数描述，其函数形式须要假设，通常运用GMM。训练问题：通常可以用每个训练样本分别计算γ值，然后分子和分母部分分别进行累加，最终统一进行参数修正；模型的拓扑结构：模型结构可以依据实际问题的须要来设计，在初始化状态转移矩阵A时，将某些元素设为0即可。“左-右”模型结构带跨越的“左-右”结构HMM模型第四章概率密度函数的非参数估计4.1基本思想4.1基本思想令R是包含样本点x的一个区域，其体积为V，设有n个训练样本，其中有k个落在区域R中，则可对概率密度作出一个估计：相当于用R区域内的平均性质来作为一点x的估计，是一种数据的平滑。有效性当n固定时，V的大小对估计的效果影响很大，过大则平滑过多，不够精确；过小则可能导致在此区域内无样本点，k=0。此方法的有效性取决于样本数量的多少，以及区域体积选择的合适。收敛性构造一系列包含x的区域R1,R2,…，对应n=1,2,…，则对p(x)有一系列的估计：当满足下列条件时，pn(x)收敛于p(x)：区域选定的两个途径Parzen窗法：区域体积V是样本数n的函数，如：K-近邻法：落在区域内的样本数k是总样本数n的函数，如：Parzen窗法和K-近邻法4.2Parzen窗方法定义窗函数1维数据的窗函数概率密度函数的估计超立方体中的样本数：概率密度估计：窗函数的要求上述过程是一个内插过程，样本xi距离x越近，对概率密度估计的贡献越大，越远贡献越小。只要满足如下条件，就可以作为窗函数：窗函数的形式窗函数的宽度对估计的影响hn称为窗的宽度窗函数的宽度对估计的影响识别方法保存每个类别全部的训练样本；选择窗函数的形式，依据训练样本数n选择窗函数的h宽度；识别时，利用每个类别的训练样本计算待识别样本x的类条件概率密度：接受Bayes判别准则进行分类。Parzen窗的神经网络实现神经元模型简化神经元模型Parzen窗函数的神经元表示窗函数取Gauss函数，全部的样本归一化，令神经元的权值等于训练样本，即：则有：概率神经网络(PNN,ProbabilisticNeuralNetwork)PNN的训练算法begininitializej=0;n=训练样本数，aij=0dojj+1normalize:train:wjxjif

thenaji1untilj=nPNN分类算法begininitializek=0;x待识模式

dokk+1

if

aki=1then

untilk=nreturnend径向基函数网络(RBF,RadialBasisFunction)RBF与PNN的差异PNN模式层神经元数等于训练样本数，而RBF小于等于训练样本数；PNN模式层到类别层的连接权值恒为1，而RBF的须要训练；PNN的训练过程简洁，只需一步设置即可，而RBF一般须要反复迭代训练；径向基函数网络的训练RBF的训练的三种方法：依据阅历选择每个模式层神经元的权值wi以及映射函数的宽度σ，用最小二乘法计算模式层到类别层的权值；用聚类的方法设置模式层每个神经元的权值wi以及映射函数的宽度σ，用最小二乘法计算模式层到类别层的权值；通过训练样本用误差订正算法迭代计算各层神经元的权值，以及模式层神经元的宽度σ；4.3近邻分类器后验概率的估计 Parzen窗法估计的是每个类别的类条件概率密度，而k-近邻法是干脆估计每个类别的后验概率。 将一个体积为V的区域放到待识样本点x四周，包含k个训练样本点，其中ki个属于ωi类，总的训练样本数为n，则有：k-近邻分类器k-近邻分类算法设置参数k，输入待识别样本x；计算x与每个训练样本的距离；选取距离最小的前k个样本，统计其中包含各个类别的样本数ki；

k-近邻分类，k=13最近邻规则分类规则：在训练样本集中找寻与待识别样本x距离最近的样本x'，将x分类到x'所属的类别。最近邻规则相当于k=1的k-近邻分类，其分类界面可以用Voronoi网格表示。Voronoi网格距离度量距离度量应满足如下四特性质：非负性：自反性：当且仅当对称性：三角不等式：常用的距离函数欧几里德距离：(EucideanDistance)常用的距离函数街市距离：(ManhattanDistance)常用的距离函数明氏距离：(MinkowskiDistance)常用的距离函数马氏距离：(MahalanobisDistance)常用的距离函数角度相像函数：(AngleDistance)常用的距离函数海明距离：(HammingDistance)

x和y为2值特征矢量：D(x,y)定义为x,y中使得不等式成立的i的个数。最近邻分类器的简化最近邻分类器计算的时间困难度和空间困难度都为O(dn)，d为特征维数，通常只有当样本数n特殊大时，分类效果才会好。简化方法可以分为三种：部分距离法；预分类法；剪辑近邻法。部分距离法定义： Dr(x,y)是r的单调不减函数。令Dmin为当前搜寻到的最近邻距离，当待识别样本x与某个训练样本xi的部分距离Dr(x,xi)大于Dmin时，Dd(x,xi)确定要大于Dmin，所以xi确定不是最近邻，不须要接着计算Dd(x,xi)。预分类（搜寻树）预分类（搜寻树）在特征空间中首先找到m个有代表性的样本点，用这些点代表一部分训练样本；待识别模式x首先与这些代表点计算距离，找到一个最近邻，然后在这个最近邻代表的样本点中找寻实际的最近邻点。这种方法是一个次优的搜寻算法。剪辑近邻法最近邻剪辑算法begininitializej=0;D=dataset;n=numberoftrainingsamplesconstructthefullVoronoidiagramofDdojj+1;FindtheVoronoineighborsofXj

ifanyneighborisnotfromthesameclassasXj

thenmarkXjuntilj=nDiscardallpointsthatarenotmarkedConstructtheVoronoidiagramoftheremainingsamplesend剪辑近邻法剪辑近邻法RCE网络RCE网络的训练算法begininitializej=0,n=#patterns,ε=smallpattern,λm=maxradius，aij=0dojj+1trainweight:

wj=xj

if

thenaji=1

findnearestpointnotin

ωi:setradius:untilj=nRCE网络的分类算法begininitializej=0,k=0,x,dojj+1ifthenuntilj=nifcategoryofallisthesamethenreturnthelabel else“ambiguous”label第五章线性判别函数5.1线性判别函数和判别界面线性不行分状况线性判别函数x=(x1,x2,…,xd)t:特征矢量；w=(w1,w2,…,wd)t:权矢量；w0：偏置(bias)。线性判别函数的增广形式y=(1,x1,x2,…,xd)t:增广的特征矢量；a=(w0,w1,w2,…,wd)t:增广的权矢量；两类问题线性判别准则线性分类器的分类界面分类界面的几何说明线性分类界面H是d维空间中的一个超平面；分类界面将d维空间分成两部分，R1，R2分别属于两个类别；判别函数的权矢量w是一个垂直于分类界面H的矢量，其方向指向区域R1

；偏置w0与原点到分类界面H的距离有关：多类问题（状况一）每一类模式可以用一个超平面与其它类别分开；这种状况可以把c个类别的多类问题分解为c个两类问题解决，须要c个线性分类界面；第i类与其它类别之间的判别函数：多类问题（状况一）分类界面多类问题（状况一）判别规则若存在i，使得gi(x)>0，gj(x)<0，j≠i，则判别x属于ωi类；其它状况，拒识。多类问题（状况二）每两个类别之间可以用一个超平面分开；c个类别的问题须要c(c-1)/2个线性分类界面；第i类与第j类之间的判别函数为：多类问题（状况二）分类界面多类问题（状况二）判别准则假如对随意j≠i，有gij(x)≥0，则决策x属于ωi。其它状况，则拒识。多类问题（状况三）状况三是状况二的特例，不存在拒识区域。多类问题（状况三）判别函数c个类别须要c个线性函数：判别准则：5.2线性判别函数的学习问题的提出：假设有一个包含n个样本的集合y1,y2,…,yn,一些标记为ω1,另一些标记为ω2，用这些样原来确定一个判别函数g(y)=aty的权矢量a。在线性可分的状况下，希望得到的判别函数能够将全部的训练样本正确分类；线性不行分的状况下，判别函数产生错误的概率最小。训练样本的规范化非规范化：规范化：解区域的几何说明(特征空间中）特征空间中：矢量a是垂直于分类界面的矢量：解区域的几何说明(权空间中）权空间中，atyi=0是一个通过原点的超平面，yi是法向量，而a是空间中一个点。一般求解方法—梯度下降法求解不等式组接受的最优化的方法：定义一个准则函数J(a)，当a是解向量时，J(a)为最小；接受最优化方法求解标量函数J(a)的微小值。最优化方法接受最多的是梯度下降法，设定初始权值矢量a(1)，然后沿梯度的负方向迭代计算：其中η(k)称为学习率，或称步长。5.3感知器算法(Perceptron)最直观的准则函数定义是最少错分样本数准则：

JN(a)=样本集合中被错误分类的样本数；感知器准则以错分样本到判别界面距离之和作为准则：感知器算法(批量调整版本)begininitialize,,θ,k0do

kk+1

untilreturnaend感知器算法(单样本调整版本)begininitialize,k0dok(k+1)modnifyk

ismisclassifiedbyathenuntilallpatternsproperlyclassifiedreturnaend例5.1有两类模式的训练样本：

ω1：{(0,0),(0,1)}

ω2：{(1,0),(1,1)}

用感知器算法求取判别函数，将两类样本分开。感知器算法的特点当样本线性可分状况下，学习率合适时，算法具有收敛性；收敛速度较慢；当样本线性不行分状况下，算法不收敛，且无法推断样本是否线性可分。5.4最小平方误差算法(LMSE)LMSE方法的基本思想是将求解线性不等式组的问题转化为求解线性方程组：最小平方误差的准则函数定义误差矢量e，用e长度的平方作为准则函数：权值矢量的求解(伪逆求解法)称为伪逆矩阵例5.2有两类模式的训练样本：

ω1：{(0,0),(0,1)}

ω2：{(1,0),(1,1)}

用LMSE算法求取判别函数，将两类样本分开。权值矢量的求解(迭代求解法)begininitializea(0),b,θ,η(•),k0；

dokk+1；

untilreturnaendLMSE算法的特点算法的收敛依靠η(k)的衰减，一般取η(k)=η(1)/k；算法对于线性不行分的训练样本也能够收敛于一个均方误差最小解；取b=1时，当样本数趋于无穷多时，算法的解以最小均方误差靠近贝叶斯判别函数；当训练样本线性可分的状况下，算法未必收敛于一个分类超平面。LMSE算法5.5支持矢量机(SVM,SupportVectorMachine)函数间隔：样本xi到分类界面g(x)=0的函数间隔定义为：几何间隔：最优分类界面样本集与分类界面之间的间隔定义为样本与分类界面之间几何间隔的最小值。最优分类界面：给定线性可分样本集，能够将样本分开的最大间隔超平面。支持矢量距离最优分类界面最近的这些训练样本称为支持矢量；最优分类界面完全由支持矢量确定，然而支持矢量的找寻比较困难。SVM的准则函数给定两类问题的线性可分样本集合{(y1,z1),…,(yn,zn)}，其中z为样本的类别标号：能够将样本线性分开的分类界面满足： 亦即可以通过调整权值w和w0将样本集合的最小函数间隔调整为1。SVM的准则函数样本集到分类界面的几何间隔：最大，亦即||w||最小，所以SVM可以变为如下的优化问题：在满足 的条件下，最小化准则函数：Kuhn-Tucker构造法构造Lagrange函数分别对参数w和w0求导：Kuhn-Tucker构造法因此有：带入Lagrange函数，有：Kuhn-Tucker构造法因此SVM的优化问题可以转化为一个经典的二次规划问题： 约束条件：SVM解的探讨这是一个典型的不等式约束条件下的二次优化问题，其解法的基础是Kuhn-Tucker定理；首先求解的是n个Lagrange乘子，n为训练样本数。但依据Kuhn-Tucker定理，有：满足第2个条件的yi称为支持矢量。SVM解的探讨依据找到的支持矢量yi以及相应的Lagrange乘子αi，计算权矢量w：偏置w0可以用支持矢量满足的条件求得：5.6多类别线性判别函数的学习方法一：依据5.1节介绍的前两种状况，分别转换为c个两类问题，或c(c-1)/2个两类问题分别处理；方法二：对于状况三，可以接受Kesler构造法训练；方法三：设计感知器网络进行识别。Kesler构造法（扩展的感知器算法）初始化c个权向量ai(1)，k1；输入增广特征矢量yk（只增加一维1，不变更特征的符号），计算c个判别函数的输出：修改权矢量：

若yk属于ωi类，而存在di(yk)≤dj(yk)，则：

ai(k+1)=ai(k)+yk；

aj(k+1)=aj(k)-yk

al(k+1)=al(k)，l≠j,i重复上述过程，直到全部样本被正确分类为止。两类问题的感知器网络多类问题的感知器网络两层感知器网络的训练样本给定样本集合(y1,t1),(y2,t2),…,(yn,tn)，其中yi为增广特征矢量，ti称为期望输出；c个输出层神经元时，可设定期望输出为：

第1类样本：(1,-1,-1,-1)第2类样本：(-1,1,-1,-1)

第3类样本：(-1,-1,1,-1)第4类样本：(-1,-1,-1,1)编码输出时：

第1类样本：(-1,-1)

第2类样本：(-1,1)

第3类样本：(1,-1)

第4类样本：(1,1)两层感知器网络的训练方法可以接受最小均方误差算法，权值调整公式为：

其中A为权值矢量矩阵，ti为第i个样本yi

的期望输出矢量。5.7线性分类器的局限性线性分类器的分类实力不强，能够很好地解决线性可分的问题，而对非线性可分的问题无法解决，如著名的异或问题：解决途径广义线性判别函数；分段线性判别函数；多层感知器；核函数方法。广义线性判别函数增加特征的高次项，将低维特征转化为高维特征；2维特征的二次判别函数。XOR问题的二次函数解广义线性判别函数的实质广义线性判别函数的构造方法：首先将原始特征通过一个非线性映射，映射到一个高维空间，然后在高维空间中构造线性判别函数。广义线性判别函数的问题对于一个具体问题，很难确定判别函数的阶数；当原始特征维数较大时，会造成“维数灾难”；分段线性判别函数（一）分段线性判别函数（二）H1H2H3H4树形决策分类第六章多层神经网络6.1多层感知器网络

（MLP，MultilayerPerceptron）神经元模型f称为激活函数解决异或问题的多层感知器

输入层隐含层输出层多层感知器的分类原理隐含层实现对输入空间的非线性映射，输出层实现线性分类；非线性映射方式和线性判别函数可以同时学习。激活函数—阈值函数激活函数—线性函数激活函数—对数Sigmoid函数激活函数—双曲正切Sigmoid函数标准的三层感知器网络多层感知器网络的设计选定层数：通常接受三层网络，增加网络层数并不能提高网络的分类实力；输入层：输入层节点数为输入特征的维数d，映射函数接受线性函数；隐含层：隐含层节点数须要设定，一般来说，隐层节点数越多，网络的分类实力越强，映射函数一般接受Sigmoid函数；输出层：输出层节点数可以等于类别数c，也可以接受编码输出的方式，少于类别数c，输出函数可以接受线性函数或Sigmoid函数。三层网络的判别函数形式第k个输出层神经元的输出，其中d为特征维数，nH为隐层节点数。6.2MLP的训练--误差反向传播算法

（BP，Backpropagationalgorithm）BP算法的实质是一个均方误差最小算法(LMS)符号定义：训练样本x，期望输出t=(t1,…,tc)，网络实际输出z=(z1,…,zc)，隐层输出y=(y1,…,ynH)，第k个神经元的净输出netk。目标函数：迭代公式：输出层隐含层隐含层迭代公式输出层：隐含层：误差反向传播BP算法—批量修改begininitializenH，w，θ，η，r0dorr+1m0;Δwji0;Δwkj0domm+1xmselectpattern

ΔwjiΔwji+ηδjxi;ΔwkjΔwkj+ηδkyjuntilm=n

wjiwji+Δwji;wkjwkj+Δwkjuntil||▽J(w)||<θreturnwendBP算法的一些好用技术激活函数的选择：一般可以选择双曲型的Sigmoid函数；目标值：期望输出一般选择(-1,+1)或(0,1)；规格化：训练样本每个特征一般要规格化为0均值和标准差；权值初始化：期望每个神经元的-1<net<+1，因此权值一般初始化为；学习率的选择：太大简洁发散，太小则收敛较慢；冲量项：有助于提高收敛速度。6.3多层感知器网络存在的问题BP算法的收敛速度一般来说比较慢；多层感知器网络存在的问题BP算法只能收敛于局部最优解，不能保证收敛于全局最优解；多层感知器网络存在的问题当隐层元的数量足够多时，网络对训练样本的识别率很高，但对测试样本的识别率有可能很差，即网络的推广实力有可能较差。多层感知器网络存在的问题6.4提高收敛速度的方法一个比较直观的想法是通过增高校习率来提高收敛速度，但这样有可能造成算法发散。梯度下降法目标函数的一阶泰勒级数绽开：目标函数增量：使目标函数下降最大：牛顿法目标函数的二阶泰勒级数绽开：H是Hessian矩阵，求取目标函数增量的极大值：Quickprop算法分别对每个参数进行优化，权值增量由上一步的增量迭代计算：共轭梯度法满足如下条件的两个方向α和β称为关于矩阵H互为共轭方向：对于二次优化函数，权值沿着随意一个初始方向移动到最小点，然后再沿着该方向关于H的共轭方向移动到最小点即可达到全局最小点。共轭梯度法在第一个梯度方向上移动，找寻到这个方向上的局部微小点；在共轭方向上计算其次个搜寻方向：如算法未收敛，则接着在共轭方向上计算下一个搜寻方向。Levenberg-Marquardt算法定义：权值增量：其中I为单位矩阵，μk为参数，J为Jacobi矩阵：6.4找寻全局最优点全局最优点的搜寻一般接受随机方法：模拟退火算法模拟进化计算–遗传算法模拟退火思想模拟退火算法是由Kirkpatrick于1983年提出的，它的基本思想是将优化问题与统计热力学中的热平衡问题进行类比；固体在降温退火过程中，处于能量状态E的概率P(E)听从Boltzmann分布：其中T是固体的温度，k为Boltzmann常数波尔兹曼分布模拟退火算法

（SA,SimulatedAnnealing）模拟退火算法可以用来优化能量函数E(w)，其中w为参数；首先设定一个较高的温度T(1)，随机初始化参数w1，计算能量E(w1)；对参数赐予一个随机扰动△w，w2=w1+△w，计算能量E(w2)；假如E(w2)<E(w1)，则接受变更，否则依据如下概率接受变更：渐渐降低温度T(k)，直到0为止。模拟退火算法应用于MLP的训练初始化温度T(0)，t0，随机初始化权值w0；应用BP算法搜寻局部最优解w(t)，计算局部最优解目标函数值E(t)；随机修正权值w’(t)=w(t)+△w，计算修正后的目标函数值E’(t)；若E’(t)<E(t)，则确认修改，w(t)=w’(t)，E(t)=E’(t)；否则依据概率P=exp(-E’(t)/T(t))确认修改；温度下降：T(t)=T(0)/[1+ln(t+100)]，如4，5步确认修改，转移到2，否则转移到3，直到温度下降到确定阈值为止；模拟退火算法示例Ew模拟退火算法示例遗传算法

（GA，GeneticAlgorithm）遗传算法是由Holland于1975年提出的，它主要模拟自然界生物“适者生存，优胜劣汰”的进化规则；遗传算法主要是应用于各种组合最优问题的求解，经过确定的改进之后，也可以应用于MLP的权值学习。基本名词染色体：用一个二进制串表示；种群：多个染色体构成一个种群；适应度：对每个染色体的评价，这是一个被优化的函数；复制：上一代的染色体不发生任何变更，干脆复制到下一代的种群中；交叉：两条染色体混合，产生两条新的染色体，交叉发生的概率：Pco；变异：一条染色体在某些位变更自身，01或10，染色体在每一位上发生变异的概率：Pmut；基本遗传算法begininitializePco,Pmut，随机初始化L个染色体作为初始种群；do计算种群中每个染色体的适应度fi，i=1,…,L；依据适应度对种群中的染色体排序；从前向后选择染色体，依据概率Pco进行交叉，依据概率Pmut进行变异；生成N个新的染色体，同原种群中的染色体构成一个新的种群，淘汰掉适应度最差的N个染色体；until达到确定的进化代数为止；return适应度最高的染色体。GA应用于MLP权值学习染色体表达： 干脆接受神经元的权值作为基因片段，而不转化为二进制串。

g={w11,w12,w13;w21,w22,w23;w31,w32,w33}遗传算子定义交叉：位置交叉：线性插值交叉：遗传算子定义变异：在染色体的每个位置上随机产生一个小的扰动，产生出新的染色体。第七章统计学习理论的本质7.1统计学习的本质系统S为探讨对象，通过一系列的观测样原来求得学习机LM，使得LM的输出能够尽量精确的预料S的输出y。 (x1,y1)，(x2,y2)，…，(xn,yn)风险学习机LM的输出与输入x之间可以看作是一个函数关系：一般须要将函数限定在特定的一组函数中求取。定义风险：均方误差：似然函数：期望风险y与x之间存在确定的依靠关系，可以用一个未知的联合概率F(x,y)描述。期望风险定义为：统计学习的目的就是要找寻到一个最优的函数f(x,w*)，使得R(w*)最小。阅历风险期望风险一般来说无法计算，在工程上转而计算阅历风险：求取最优参数w*，使得阅历风险Remp(w*)最小。当学习过程具有一样性时，统计学有如下关系：期望风险与阅历风险的关系7.2函数集的VC维与推广性的界统计学习的推广实力不仅同训练样本数n有关系，而且同学习机的函数集选择有关系，“简洁”的函数集合推广实力强，“困难”的函数集合推广实力差。当函数集过于“困难”时，很简洁产生“过学习”现象：对于训练样本风险很小，而对非训练样本风险却很大。过学习VC维打散：假如存在一个有h个样本的样本集能够被一个函数集中的函数依据全部可能的2h种形式分为两类，则称函数集能够将样本数为h的样本集打散；VC维：假如函数集能够打散h个样本的样本集，而不能打散h+1个样本的样本集，则称函数集的VC维为h。d维空间中线性函数的VC维：h=d+1；正弦函数集合{sin(wx)}的VC维：h=∞。推广性的界函数集合的VC维描述了函数的困难程度，利用VC维可以确定推广性的界，下列不等式右半部分至少以概率1-η成立： 其中h为函数集合的VC维，n为训练样本数。当n/h较小时，置信范围较大；n/h较大时，置信范围较小：7.3提高推广实力的方法提高推广实力的本质方法是由原来只优化阅历风险变为优化期望风险的上界：过学习欠学习结构风险最小化原则

（SRM，StructuralRiskMinimization）首先把函数集分解为一个函数子集序列： 各个子集依据VC维的大小排序： 在子集序列中找寻阅历风险与置信范围之和最小的子集，这个子集中使阅历风险最小的函数就是所求的最优函数。SRM在线性分类器上的应用（SVM）d维空间中的线性函数的VC维为d+1，但当限制判别界面的分类间隔时，其VC有可能更小。定理：在d维空间中，设全部n个样本都在一个超球范围之内，超球的半径为R，那么γ-间隔分类超平面集合的VC维h满足如下不等式：而间隔，因此依据SRM的原则，只需在保证阅历风险为0的条件下（超平面能够正确分类全部训练样本），最小化权值矢量的长度。验证技术（Validation）当无法计算函数集的VC维时，可以接受验证技术。将样本集分为训练集和验证集，用训练集的样本训练网络，用验证集的样本测试网络，找寻一个验证集风险最小的模型和参数。权值衰减试验表明，多层感知器网络中比较小的权值往往能够提高系统的推广实力，因此在训练过程中可以有意地衰减权值：或者接受一个等价的目标函数：第八章成分分析与核函数8.0问题的提出一般来说，在建立识别系统时，抽取的原始特征往往比较多，特征的维数比较大，这会给识别器的训练带来很大的困难，因此希望能够接受某种方法降低特征的维数。这些方法可以称作成分分析的方法。成分分析方法主要包括：主成分分析；多重判别分析；独立成分分析；人脸识别举例8.1主成分分析

（PCA，PrincipalComponentAnalysis）PCA是一种最常用的线性成分分析方法；PCA的主要思想是找寻到数据的主轴方向，由主轴构成一个新的坐标系（维数可以比原维数低），然后数据由原坐标系向新的坐标系投影。PCA的其它名称：离散K-L变换，Hotelling变换；PCA的思想v1v2e1e2PCA的思想v1v2e1e2PCA算法利用训练样本集合计算样本的均值m和协方差矩阵S；计算S的特征值，并由大到小排序；选择前d’个特征值对应的特征矢量作成一个变换矩阵E=[e1,e2,…,ed’]；训练和识别时，每一个输入的d维特征矢量x可以转换为d’维的新特征矢量y：

y=Et(x-m)。PCA的探讨由于S是实对称阵，因此特征矢量是正交的；将数据向新的坐标轴投影之后，特征之间是不相关的；特征值描述了变换后各维特征的重要性，特征值为0的各维特征为冗余特征，可以去掉。例8.1

有两类问题的训练样本：

将特征由2维压缩为1维。x1x2e1e2特征人脸e1e2e3e4e5e6e7e8PCA重构原图像d’=151020501002008.2多重判别分析

（MDA,MultipleDiscriminantAnalysis）x1x2e1e2MDA与PCAPCA将全部的样本作为一个整体对待，找寻一个均方误差最小意义下的最优线性映射，而没有考虑样本的类别属性，它所忽视的投影方向有可能恰恰包含了重要的可分性信息；MDA则是在可分性最大意义下的最优线性映射，充分保留了样本的类别可分性信息；MDA还被称为：FDA(FisherDiscriminantAnalysis)或LDA(LinearDiscriminantAnalysis)。Fisher线性判别准则样本x在w方向上的投影：定义类内散布矩阵：定义类间散布矩阵：Fisher线性判别准则：wFDA算法利用训练样本集合计算类内散度矩阵Sw和类间散度矩阵SB；计算Sw-1SB的特征值；选择非0的c-1个特征值对应的特征矢量作成一个变换矩阵W=[w1,w2,…,wc-1]；训练和识别时，每一个输入的d维特征矢量x可以转换为c-1维的新特征矢量y：

y=Wtx。3类问题FDAFDA的探讨经FDA变换后，新的坐标系不是一个正交坐标系；新的坐标维数最多为c-1，c为类别数；只有当样本数足够多时，才能够保证类内散度矩阵Sw为非奇异矩阵（存在逆阵），而样本数少时Sw可能是奇异矩阵。8.3成分分析的其它问题独立成分分析(ICA,IndependentComponentAnalysis)：PCA去除掉的是特征之间的相关性，但不相关不等于相互独立，独立是更强的要求。ICA试图使特征之间相互独立。多维尺度变换(MDS,MultidimensionalScaling)典型相关分析(CCA,CanonicalCorrelationAnalysis)偏最小二乘(PLS,PartialLeastSquare)线性PCA的神经网络实现8.4核函数及其应用空间的非线性映射建立一个R2R3的非线性映射计算R3中2个矢量的内积：定义核函数：，则：输入空间特征空间核函数上个例子说明：特征空间中两个矢量之间的内积可以通过定义输入空间中的核函数干脆计算得到。这就启示我们可以不必定义非线性映射Φ而干脆在输入空间中定义核函数K来完成非线性映射。这样做的条件是：定义的核函数K能够对应于特征空间中的内积；识别方法中不须要计算特征空间中的矢量本身，而只须计算特征空间中两个矢量的内积。Hibert-Schmidt理论作为核函数应满足如下条件： 是下的对称函数，对随意，且 有：

成立，则可以作为核函数。此条件也称为Mercer条件。常用的核函数GaussianRBF：Polynomial：Sigmoidal：Inv.Multiquardric：核函数应用于线性分类器

（SVM的非线性版本）SVM的求解，最终归结为如下目标函数的优化：可以引入非线性映射Φ，则目标函数变为：而权矢量为：判别函数：支持矢量机的实现核函数应用于PCA（KPCA）

训练样本集合。定义核函数；计算维矩阵K，其元素：然后计算矩阵K的特征值和特征向量，保留其中的非0的特征值；特征空间中的第i个主轴基向量为：输入特征矢量x在特征空间中第i个轴上的投影：非线性PCA的神经网络实现第九章非度量方法8.1度量方法与非度量方法度量方法：特征以连续或离散数值的方式描述；样本可以看作是度量空间(距离空间)中的点；样本之间的距离可以作为相像性的度量；接受统计学的方法构造识别器。非度量方法特征(属性)可以是数值，也可以是符号；很难定义距离来衡量属性之间的相像程度；常用的非度量方法判定树串匹配文法方法（结构模式识别）…9.2判定树的概念水果的属性描述：(颜色,尺寸,形态,味道)判定规则:西瓜=绿色∧大苹果=(绿色∧中等大小)∨(红色∧中等大小)判定树的特点中间节点对应一个属性，节点下的分支为该属性的可能值；叶节点都有一个类别标记，每个叶结点对应一个判别规则；判定树可以产生合取式规则，也可以产生析取式规则；判定树产生的规则是完备的，对于任何可分的问题，均可构造相应的判定树对其进行分类。9.3通用的判定树生成算法CART：ClassificationandRegressionTree已知示例集合（样本集合），生成判别树，能够对示例中的样本分类，也要能够对将来的样本进行分类。例9.1示例天气温度湿度风力打网球1SunnyHotHighWeakNo2SunnyHotHighStrongNo3Ove