哈工大模式识别课件PPT格式课件下载.pptx
- 文档编号:4010168
- 上传时间:2023-05-02
- 格式:PPTX
- 页数:320
- 大小:7.23MB
哈工大模式识别课件PPT格式课件下载.pptx
《哈工大模式识别课件PPT格式课件下载.pptx》由会员分享,可在线阅读,更多相关《哈工大模式识别课件PPT格式课件下载.pptx(320页珍藏版)》请在冰点文库上搜索。
预先已知训练样本集中每个样本的类别标号;
无监督学习(无教师学习):
预先不知道训练样本集中每个样本的类别标号;
模式识别绪论,七、参考书目,RichardDuda,PeterHart,DavidStork,PatternClassification,2ndedition,JohnWiley,2001模式分类,机械工业出版社,RichardO.Duda模式识别(第二版),清华大学出版社,边肇祺,张学工;
模式识别绪论,期刊,IEEETransactiononPatternAnalysisandMachineIntelligence,PAMI;
PatternRecognition;
PatternRecognitionLetter;
模式识别与人工智能;
讲义下载:
ftp:
/202.118.251.122用户名:
prai密码:
prai,模式识别,第二章贝叶斯决策理论,模式识别绪论,2.1最小错误率准则,模式识别绪论,各种概率及其关系,先验概率:
后验概率:
类条件概率:
贝叶斯公式:
模式识别绪论,两个类别,一维特征,模式识别绪论,两类问题的错误率,观察到特征x时作出判别的错误率:
两类问题最小错误率判别准则:
模式识别绪论,多类问题最小错误率,判别x属于i的错误率:
判别准则为:
则:
模式识别绪论,贝叶斯最小错误率准则,Bayes判别准则:
,则,模式识别绪论,贝叶斯分类器的错误率估计,模式识别绪论,例2.1,对一大批人进行癌症普查,设1类代表患癌症,2类代表正常人。
已知先验概率:
以一个化验结果作为特征x:
阳性,阴性,患癌症的人和正常人化验结果为阳性的概率分别为:
现有一人化验结果为阳性,问此人是否患癌症?
模式识别绪论,2.2最小平均风险准则贝叶斯分类器,问题的提出有c个类别1,2,.,c,将i类的样本判别为j类的代价为ij。
将未知模式x判别为j类的平均风险为:
i!
=jLij=0,模式识别绪论,最小平均风险判别准则,利用Bayes公式,构造判别函数:
模式识别绪论,贝叶斯分类器,模式识别绪论,例2.2,对一大批人进行癌症普查,设1类代表患癌症,2类代表正常人。
阳性,阴性,患癌症的人和正常人化验结果为阳性的概率分别为:
判别代价:
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算法,1.begininitialize,,T,i0;
3.,;
4.,2.doii+1E步:
计算M步:
5.until,6.return,模式识别绪论,混合密度模型,一个复杂的概率密度分布函数可以由多个简单的密度函数混合构成:
最常用的是高斯混合模型(GMM,GaussMixtureModel):
模式识别绪论,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=v3v2v3v4v1,模式识别绪论,HMM的工作过程,模式识别绪论,HMM的参数表示,状态转移矩阵:
A,M*M的方阵;
状态输出概率:
B,M*K的矩阵;
初始概率:
,包括M个元素。
M个状态,K个可能的输出值。
模式识别绪论,HMM的三个核心问题,估值问题:
已有一个HMM模型,其参数已知,计算这个模型输出特定的观察序列VT的概率;
解码问题:
已有一个HMM模型,其参数已知,计算最有可能输出特定的观察序列VT的隐状态转移序列WT;
学习问题:
已知一个HMM模型的结构,其参数未知,根据一组训练序列对参数进行训练;
模式识别绪论,估值问题,一个HMM模型产生观察序列VT可以由下式计算:
rmax=MT为HMM所有可能的状态转移序列数;
为状态转移序列输出观察序列的概率;
为状态转移序列发生的概率。
模式识别绪论,估值问题的计算,计算复杂度:
模式识别绪论,HMM估值算法的简化,模式识别绪论,HMM的前向算法,1.初始化:
2.迭代计算:
3.结束输出:
计算复杂度:
模式识别绪论,解码问题,解码问题的计算同估值问题的计算类似,最直观的思路是遍历所有的可能状态转移序列,取出最大值,计算复杂度为:
O(MTT)。
同样存在着优化算法:
Viterbi算法。
模式识别绪论,Viterbi算法,1.因为需要回朔最优路径,所以建立一个矩阵,其元,素保存第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的类条件概率密度:
4.采用Bayes判别准则进行分类。
模式识别绪论,Parzen窗的神经网络实现,神经元模型,模式识别绪论,简化神经元模型,模式识别绪论,Parzen窗函数的神经元表示,窗函数取Gauss函数,所有的样本归一化,令神经元的权值等于训练样本,即:
则有:
模式识别绪论,概率神经网络(PNN,ProbabilisticNeuralNetwork),模式识别绪论,PNN的训练算法,begininitializej=0;
n=训练样本数,aij=0dojj+1normalize:
train:
wjif,xjthenaji1,6.untilj=n,模式识别绪论,PNN分类算法,1.begininitializek=0;
x,待识模式,4.,2.dokk+13.ifaki=1thenuntilk=nreturn,7.end,模式识别绪论,径向基函数网络(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;
4.,模式识别绪论,k-近邻分类,k=13,模式识别绪论,最近邻规则,分类规则:
在训练样本集中寻找与待识别样本x距离最近的样本x,将x分类到x所属的类别。
最近邻规则相当于k=1的k-近邻分类,其分类界面可以用Voronoi网格表示。
模式识别绪论,Voronoi网格,模式识别绪论,距离度量,距离度量应满足如下四个性质:
非负性:
自反性:
当且仅当对称性:
三角不等式:
模式识别绪论,常用的距离函数,欧几里德距离:
(EucideanDistance),模式识别绪论,常用的距离函数,街市距离:
(ManhattanDistance),模式识别绪论,常用的距离函数,明氏距离:
(MinkowskiDistance),模式识别绪论,常用的距离函数,马氏距离:
(MahalanobisDistance),模式识别绪论,常用的距离函数,角度相似函数:
(AngleDistance),模式识别绪论,常用的距离函数,海明距离:
(HammingDistance)x和y为2值特征矢量:
成立的i的个,D(x,y)定义为x,y中使得不等式数。
模式识别绪论,最近邻分类器的简化,最近邻分类器计算的时间复杂度和空间复杂度都为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;
FindtheVoronoineighborsofXjifanyneighborisnotfromthesameclassasXjthenmarkXjuntilj=nDiscardallpointsthatarenotmarkedConstructtheVoronoidiagramoftheremainingsamplesend,模式识别绪论,剪辑近邻法,模式识别绪论,剪辑近邻法,模式识别绪论,RCE网络,模式识别绪论,RCE网络的训练算法,begininitializej=0,n=#patterns,=smallpattern,m=maxradius,aij=0dojj+1trainweight:
wj=xjifthenaji=1findnearestpointnotini:
setradius:
untilj=n,模式识别绪论,模式识别绪论,RCE网络的分类算法,1.begininitializej=0,k=0,x,3.,then,isthe,2.dojj+1ifuntilj=nifcategoryofallsame,6.,7.,thenreturnthelabelelse“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:
增广的权矢量;
模式识别绪论,两类问题线性判别准则,模式识别绪论,线性分类器的分类界面,W的方向决定分类界面,长度与分类界面无关,只与偏置大小有关。
模式识别绪论,分类界面的几何解释,线性分类界面H是d维空间中的一个超平面;
分类界面将d维空间分成两部分,R1,R2分别属于两个类别;
判别函数的权矢量w是一个垂直于分类界面H的矢量,其方向指向区域R1;
偏置w0与原点到分类界面H的距离有关:
模式识别绪论,多类问题(情况一),每一类模式可以用一个超平面与其它类别分开;
这种情况可以把c个类别的多类问题分解为c个两类问题解决,需要c个线性分类界面;
第i类与其它类别之间的判别函数:
模式识别绪论,多类问题(情况一)分类界面,模式识别绪论,多类问题(情况一)判别规则,若存在i,使得gi(x)0,gj(x)0,ji,则判别x属于i类;
其它情况,拒识。
模式识别绪论,多类问题(情况二),每两个类别之间可以用一个超平面分开;
c个类别的问题需要c(c-1)/2个线性分类界面;
第i类与第j类之间的判别函数为:
模式识别绪论,多类问题(情况二)分类界面,模式识别绪论,多类问题(情况二)判别准则,如果对任意ji,有gij(x)0,则决策x属于i。
其它情况,则拒识。
模式识别绪论,多类问题(情况三),情况三是情况二的特例,不存在拒识区域。
模式识别绪论,多类问题(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈工大 模式识别 课件