课件第4章模式识别基础

1、Media and Cognition电子工程系利: liyali13进模式识别系统Ø 数据获取：信号空间Ø 预处理Ø 特征提取和选择：特征空间Ø 分类决策：模式空间寻找有利于分类的本质特征2分类学习/测试模式识别系统决策例如：传感器的感文本切割、脑电波的部分与整体关系基元例如：摄像机、麦克风阵列传感器因素：带宽、灵敏度、失真、信噪比、延迟等等输入3传感器分割器特征提取器分类器后处理器模式识别系统决策输入4传感器分割器特征提取器类内一致性：来自同一类别的不同样本特征值相近类间差异性：来自不同类别的样本特征值有很大差异表征能力、鉴别性、特征维度分类器后处理

2、器模式识别系统决策输入5传感器分割器特征提取器分类器根据特征提取器提取的特征向量给被测试对象(样本)赋予类别标记后处理器模式识别系统决策输入6传感器分割器特征提取器分类器根据特征提取器提取的特征向量给被测试对象(样本)赋予类别标记后处理器模式识别系统决策输入7传感器分割器特征提取器上下文信息： 鱼在水里游 鸟在天空飞 人在地上走分类器根据上下文信息对分类进行调整后处理器第四章模式识别基础4.1 统计模式识别4.2决策4.3 参数估计方法4.4 非参数估计方法4.1 统计模式识别Ø 模式(pattern)u 人们在一定条件环境下，根据一定需要，对自然事物的一种抽象的分类概念。W=w1,

3、 w2,wM u 模式集合记为：Ø 样本(sample, object) 是自然界的具体事物，具有一定的类别特性，是抽象模式的具体体现。X = ()T 样本的观测量记为：NØ 模式识别：寻求样本观测量与类别属性的g(x)= wi：样本类别9模式识别10基本问题:模式类的性Ø 临界点的数量与总的点数相比很少Ø 集合内的任意两点的连线,上的点属于同一集合Ø 集合内的每一个点都有足够大的邻域,在邻域内只包含同一集合的点分类难度提升，分类错误率增加（a）没有临界点（b）有较多临界点（c） 临界点过多114.1.2 统计模式识别：经验误差Ø 错

4、误率(error rate)与精度(accuracy)：u 错误率：分类错误的样本占样本总数的比例u 假设𝑚个样本中有𝑎个样本分类错误，则𝐸 = 𝑎 𝑚u 精度：1-错误率1 𝑎 𝑚Ø 误差(error)：u 学习器的实际输出与样本的真实输出之间的差异u 训练误差/经验误差(empirical error)u 测试误差/泛化误差(generalization error)124.1.2 统计模式识别：过拟合Ø 过拟合(overfitting)与欠拟合(underf

5、itting)：u 欠拟合：训练样本的性质没学好，表现为训练误差大u 过拟合：训练样本学的”太好”，缺乏对本质的理解，出现泛化性能下降134.1.2 统计模式识别：系统评价指标Ø 分类结果的矩阵Ø率Recall、准确率PrecisionTPTPRecall=, Precison=TP + FNTP + FPØ 真阳性率(True Positive Rate)、假阳性率(False Positive Rate)TPFPTPR=, FPR=TP + FNTP + FP14真实类别类别正例反例正例TP(真正例)FN(假反例)反例FP(假正例)TN(真反例)4.1.2 统

6、计模式识别：系统评价指标Ø ROC曲线u ROC（Receiver Operator Characteristic）曲线，称为受试者工作特征曲线，又称为接收者操作特性曲线，是以真阳性率(true positive rate, TPR)为纵坐标，假阳性率（false positive rate, FPR）为横坐标绘制的曲线。15Q1: 什么样的ROC曲线代表高性能的模式识别系统？4.1.3 统计模式识别：测试方法Ø 交叉验证方法(CrossValidation)u CV是用来验证分类器的性能一种统计分析方法，将原始数据(dataset)进行分组,一部分做为训练集(traini

7、ng set),另一部分做为验证集(validation set)u K-折交叉验证（K-fold Cross Validation） 将原始数据分成K组(一般是均分)，将每个子集数据分别做一次验证集,其余的K-1组子集数据作为训练集，这样得到K个模型 K个模型最终的验证集的分类准确率的平均数作为分类器的性能指标eave-One-Out）u 留一 每个样本单独作为验证集,其余的N-1个样本作为训练集16统计模式识别统计模式识别结构模式识别类条件概率函数P(x|i)17非参数参数非参数参数非监督学习监督学习已知决策理论未知神经网络4.1 统计模式识别Ø 基本概念(小结)u 错误率，精度

8、u 误差、经验误差、泛化误差u 过拟合、欠拟合矩阵率、准确率uuu ROC曲线、AUC数值u 测试方法18第四章模式识别基础4.1 统计模式识别4.2决策4.3 参数估计方法4.4 非参数估计方法4.2决策：数学基础Ø 条件概率和概率：u 假设A和B是一个样本空间中的两个B发生的条件下，A发生的条件概率为，在假定P ( A, B) P ( B)概率为P ( A B)=A和B的uP ( A, B) =P ( A B ) P (B ) =P (BA) P ( A)204.2决策：数学基础Ø定理：u 假设𝐴1和𝐴2是互斥的两个生的概率（边际概率）为

9、全空间，且𝐴1 𝐴2= 𝑆，𝐵发P ( B) =P (BA1 ) P ( A1 ) +P (BA2 ) P ( A2 )u 两的定理定理为：P ( Ai ) P (BAi )P ( AiB)=, i = 1, 2P ( A1 ) P (BA1 )+P ( A2 ) P (BA2 )的定理定理为：u 𝑛P ( Ai ) P (BAi )P ( AiB)=, i = 1, 2, nP ( A1 ) P (BA1 )+P ( A2 ) P (BA2 )+P ( An ) P (BAn )214.2决策：数学基础Ø

10、;定理：的u 两定理定理为：P ( Ai ) P (BP ( B)Ai )P ( AiB)=, i = 1, 2u 模式识别中的P (wi定理表示：P (wi ) P ( x wi )x)=, i = 1, 2P ( x)先验概率似后验概率posterior= prior ´ likelihoodevidence22通过观测𝑥将先验概率𝑃 𝜔𝑖 转化为后验概率𝑃 𝜔𝑖|𝑥4.2决策：数学基础Ø(正态)分布：23Q2： why Gaussian?4.

11、2决策Ø决策u 概率框架下实施决策的基本方法决策：在所有相关概率已知的条件下，考虑如何利用已知概率，以最小化误判损失函数为目标来选取最优的类别标记u24Duda, Hart, Stork, Pattern Recognition4.2 贝叶斯决策ìï P (w1x) x)判定为w2判定为w1P (errorx)= íØ 误分类ïîP (w2Ø 平均误差概率¥¥P (error ) = ò P (error, x)dx= ò P (error | x )P ( x ) dx-&

12、#165;-¥ìïP (w1x) > P (w2x) x)判定为w1íP (w x) < P (w判定为wïî122x), P (w2x)=minP (w1x)P (error贝叶斯决策函数一般形式ìïP ( x w1 ) P (w1 ) > P ( x w2 ) P (w2 )判定为w1íP ( x w) P (w) < P ( x w ) P (w )判定为wïî2511222Gi (x) = p( x | i ) p(i )4.2决策Ø 正态分布

13、条件下的决策u 假设类条件概率密度函数为正态分布u 判别函数定义为:u 取对数后判别函数为:264.2决策4.2决策Ø 正态分布条件下的决策假设各类先验概率相等，协方差矩阵的三种情况= 𝜎2𝐼= (1) 𝑖(2) 𝑖最小距离分类器最小马氏距离分类器马氏距离 Mahalanobis distance= (x - )T -1(x - )d 2iii(3) 𝑖𝑖 𝑗 ，二次判别函数 𝑗284.2决策Ø 正态分布条件下的u 情况1：𝑖 =

14、𝜎2𝐼决策294.2决策Ø 正态分布条件下的u 情况2：𝑖 = 决策g (x) = - 1 (x - )T -1(x - ) + ln p( )iiiii24.2决策314.2决策Ø 正态分布条件下的决策u 情况3：𝑖 𝑗𝑖 𝑗g (x) = - 1 (x - )T -1 (x - ) - 1 ln + ln p( )iiiiii22324.2决策334.2决策Ø线性判别函数(Linear Discriminant Function, LDF)g (x)

15、 = - 1 (x - )T -1(x - ) - d ln(2) - 1 ln + ln p( )iiiiii222假设各类协方差矩阵都相等，去除判别函数公式中对各类别相同的项，并忽略先验概率，得到线性判别函数(x) = AT x + bgLDFiib = - 1 T -1 A =-1 i0iii0i2344.2决策Ø二次判别函数(Quadratic Discriminant Function,QDF)假设各类的协方差阵𝑖不相等,得二次判别函数:(x) = - 1 (x - )T -1(x - ) - 1 ln gQDFiiii22对判别函数取负数并乘以系数2，利用

16、协方差矩阵的特征分解，得到：)T -1(x - (x) = -2g(x) = (x - ) + ln gQDFQDFMMMMn= åi=1 1nÕi=1(x -i) + lnT2iMi354.2决策Ø二次判别函数(Quadratic Discriminant Function,QDF)对判别函数取负数并乘以系数2，利用协方差矩阵的特征分解， 得到：(x) = -2g(x) = (x - )T -1(x - ) + ln gQDFQDFMMMMn= åi=1nnÕ 1(x -i) + lnT2iMi=1iå，M、T其中，为对应第

17、19894; （原类别下标i暂且省略）=MiiiM类均值和协i=方1 差矩阵的最大似然估计； 的特征值及对应特M（ii = 1,., n）、i征向量为，特征值为降序排列。从式中可以看出，计算结果对于较小特征值的估计误差更为敏感36MQDF： 第一种类型Ø MQDF（ Modified Quadratic Discriminant Function ）u 在协方差矩阵的对角线上加一个小的常量 h2 ，保证矩阵的（非奇异性），由此取代协方差矩阵的最大似然估计，即为：P= M+ h2 In1nåi=1 (x - ) + ln Õ(i +h )(x) =T22gMQDF1

18、iM2 +hi=1i37MQDF： 第二种类型Ø 用 h2（i ³ k +1;i £ n），k为主子代替较小特征值i空间截断维数k1n1kåi=1åi=k +1Õ i )i=1(x) =(x - ) +(x - ) + ln(h2(n-k )T2T2gMQDF2iMiM2hiØ 利用nåi (x - 2=x - MT2)Mi=1é2 ùh21kk- å(1-)i (x - M ) ú + ln(hÕ i )i=122(n-k )gMQDF2 (x) = h2 

19、34; x - MTëûi=1iØh2可以有多种取值方式，比如取所有较小特征值 （ii ³ k +1;i £ n）的平均值38实例：脱机手写汉字识别Ø 脱机手写汉字识别的u 统计方法：维数和过训练39MQDF分类器特征提取预处理基于线性判别分析LDA 的特征降维限定式的工整手写Block PrintingManuscript Writing手稿式的自由手写31便笺式的随意手写 Cursive Scripts线性鉴别分析实验Ø 目的：选择合适的特征压缩维数 结果： 条件：9599.6原始输入392 维笔画边缘方向特征94.49

20、9.5分类器最近距离分类器93.899.5Top 1 Choice (Left)Top 10 Choices (Right)93.299.450100150200250300350最近距离分类器的识别率 随特征压缩维数的变化曲线41MQDF实验Ø 目的：选择合适的MQDF主子空间截断维数k 结果： 条件：96LDA特征压缩维数：12895.895.695.495.295104070100MQDF 识别率随主子空间维数 k 的变化曲线424.2决策(小结)Ø 数学基础：Ø 名词概念：u 先验概率、后验概率、似然概率定理、分布决策：先验概率至后验概率的转化uØ

21、; 正态分布下的u 三种情况分析u 欧式距离、马氏距离u 线性判别函数、二次判别函数u 拓展：MQDF决策43第四章模式识别基础4.1 统计模式识别4.2决策4.3 参数估计方法4.4 非参数估计方法4.3 参数估计方法：最大似然估计Ø决策：根据先验概率𝑃𝑃 𝑥|𝜔𝑖设计最优分类器；𝜔𝑖和类条件概率u 问题：实际应用中，概率(密度函数)很难获取Ø 参数估计：利用训练样本估计决策问题中的先验概率和条件密度函数，在此基础上设计分类器。Ø 先验概率估计：离散二

22、项式分布nP ( z , zzw) = Õ P (w)é1- P (w)ù1- zz,ikikëûi1i 2iniiik =1n1n()åk =1Þ P w =ziik454.3 参数估计方法：最大似然估计Ø 假设有样本集𝐷，服从参数为𝜃的概率分布，𝐷中包含有𝑛个抽取的样本，则n()p x q)(Õk =1p D q=kØ 对数似然函数：n()(q)åk =1( )l q ºln p D q =ln p xk&#

23、216; 最大似然估计：q= arg max l (q)q464.3 参数估计方法：最大似然估计Ø 假设有样本集𝐷，服从参数为𝜃的概率分布，𝐷中包含有𝑛个抽取的样本，则n()(q)Õk =1p D q=p xkØ 对数似然函数：n()ln p x q)(å( )l q º ln p D q =kk =1nln p x q)=0(åk =1( )Ñ l q ºÑØ 最大似然估计：qqkq= arg max l (q)q474.3 参数

24、估计方法：最大似然估计Ø 多元正态分布u 概率密度函数p(x) N (m, S)112p(12(2p)S2u 情况1：均值未知，协方差矩阵已知n= 1 åm =qx1knk =1u 情况2：均值和协方差矩阵均未知1nnå xkk =1n1m=q =S =q =å(x -m)(x-m)T12kknk =1484.3 参数估计方法：最大似然估计Ø 多元正态分布u 概率密度函数p(x) N (m, S)1exp- 1 (x - m)T S-1(x - m) 2，S) =p(d(2p) 212Su 情况1：均值𝜇未知，协方差矩阵已知m)

25、 = - 1 ln éë(2p)dS ùû - 1 (x - m)T S-1(x - m)kkln p(22ßÑm) = S-1(x - m)ln p(xukkßk最大似然估计nnåÑk =1m) = åS-1(x- m) = 0nln p(x()ln p x q)(å( )l q º ln p D q=ukik =1i=1nm = 1 å xÞq= arg max l (q)kn49k =1q4.3 参数估计方法：最大似然估计Ø 多元正态分布u

26、 概率密度函数p(x) N (m, S)1exp- 1 (x - m)T S-1(x - m) 2，S) =p(d(2p) 212Su 情况2：均值𝜇、协方差矩阵未知(单变量推导) = - 1 ln(2pq ) -1(x -q)2ln p(xk2k12q22ßéêùúú 1q ( xk-q1 ) = ê2Ñln p(xêúk(x -q)21最大似然估计ê-+k1únl (q) º ln p (D q) = åln p ( x q)2q2q2

27、ëû22ii=1q= arg max l (q)50q4.3 参数估计方法：最大似然估计Ø 多元正态分布u 概率密度函数p(x) N (m, S)1exp- 1 (x - m)T S-1(x - m) 2，S) =p(d(2p) 212Su 情况2：均值𝜇、协方差矩阵未知(单变量推导)éêùúú1 ( xn1(x -q1 ) = 0-q)åk =1k1qk极值条件q) = ê2ÑÞln p(x2êúk(x -q)2(xk -q1 )12&#

28、234;-+k1ún1n-åk =1+ åk =1ß2q2q2= 0ëû22qq222最大似然估计n()(q) m =q=å( )l q º ln p D q =ln p x1nn1nnåk =1åk =1(x - m)2s=q =2ix ,i=11k2kq= arg max l (q)51q4.3 参数估计方法：最大似然估计Ø 多元正态分布u 概率密度函数p(x) N (m, S)1exp- 1 (x - m)T S-1(x - m) 2，S) =p(d(2p) 212Su 情况2：

29、均值𝜇、协方差矩阵未知(多变量拓展)n= 1 åm =qx1knk =1n= 1 åS =q-m)(xk -m)T(xk2nk =1最大似然估计n()ln p x q)(å( )l q º ln p D q =ii=1q= arg max l (q)52q4.3 参数估计方法：最大似然估计Ø 多元正态分布u 概率密度函数p(x) N (m, S)112p(12(2p)S2u 情况1：均值未知，协方差矩阵已知n= 1 åm =qx1knk =1u 情况2：均值和协方差矩阵均未知1nnå xkk =1n1m=q

30、=S =q =å(x -m)(x-m)T12kknk =1534.3 参数估计方法：无偏估计Ø 多元正态分布u 概率密度函数p(x) N (m, S)112p(12(2p)S2u 协方差矩阵的最大似然估计n= 1 åS =q(x -m)(xk-m)T2knk =1样本均值n -1é 12 ùnåe(x - x ) ú =s ¹ s22有偏估计êknnëk =1û最大似然估计值的期望544.3 参数估计方法：无偏估计Ø 多元正态分布u 概率密度函数p(x) N (m, S)11

31、2p(12(2p)S2u 协方差矩阵的渐进无偏估计nC = 1å(x -m)(xk-m)Tkn -1k =155样本协方差矩阵Sample covariance matrix4.3 参数估计方法Ø 第一部分小结：u 最大似然估计n()ln p x q)(å( )l q º ln p D q =ii=1q= arg max l (q)q分布假设的最大似然估计(情况1、2)u1nnå xkk =1n1m=q =S =q =å(x -m)(x -m)T12kknk =1u 无偏估计nC = 1å(xk - m)(x - m)Tkn

32、 -156k =14.3.2 参数估计方法：混合模型Ø模型（Gaussian Mixture M混合）多峰分布的假设拟合4.3.2 参数估计方法：混合模型Ø模型（Gaussian Mixture M混合）多峰分布的假设拟合4.3.2 参数估计方法：混合模型Ø模型（Gaussian Mixture M混合）多峰分布的假设拟合4.3.2 参数估计方法：混合模型Ø模型（Gaussian Mixture M混合）混合分布的概率密度估计问题：u1. 所有样本都来自于K种类别，K已知；2. 每种类别的先验概率 P (w j ) 未知；p (x w j , j )，但参3. 类条件概率的数学形式已知数 j 未知；4. 样本类别未被标记。K()()()åj =1p x =w, P wp xjjj4.3.2 参数估计方法：混合模型实际字符样本特征分布的非MNIST样本集训练样本数：60,000性测试样本数：10,0000312图像规一化为28×28456789手写数字09的特征分布在前二维主分量平面上的投影显示614.3.2 参数估计方法：混合模型Ø 混合模型比模型具有更强的描述能力，但其需要的参数也成倍增加，实际中通常对节点方差矩阵结构进行约束KKåpkk