模式识别 Pattern Recognition

Presentation on theme: "模式识别 Pattern Recognition"— Presentation transcript:

1 模式识别 Pattern Recognition
IPL 武汉大学电子信息学院 模式识别 Pattern Recognition 第三章 概率密度密度的估计

2 第三章 概率密度的估计 IPL 内容目录 1 3.1 引言 3.2 参数估计 2 3.3 非参数估计 3 3.4 讨论 4

3 3.1 引言 分类器 功能结构 基于样本的Bayes分类器：通过估计类条件概率密度函数，设计相应的判别函数 基于样本的直接确定判别函数方法
MAX g1 . g2 gc x1 x2 xn a(x) 基于样本的Bayes分类器：通过估计类条件概率密度函数，设计相应的判别函数 基于样本的直接确定判别函数方法 第三章概率密度密度的估计

4 基于样本的Bayes分类器设计 Bayes决策需要已知两种知识： 知识的来源：对问题的一般性认识或一些训练数据
各类的先验概率P(ωi) 各类的条件概率密度函数p(x|ωi) 知识的来源：对问题的一般性认识或一些训练数据 基于样本的两步Bayes分类器设计 利用样本集估计P(ωi)和p(x|ωi) 基于上述估计值设计判别函数及分类器 面临的问题： 如何利用样本集进行估计 估计量的评价 第三章概率密度密度的估计

5 基于样本的Bayes分类器 训练 样本集 最一般情况下适用的“最优”分类器：错误率最小，对分类器设计在理论上有指导意义。
样本分布的 统计特征： 概率 密度函数 决策规则： 判别函数 决策面方程 最一般情况下适用的“最优”分类器：错误率最小，对分类器设计在理论上有指导意义。 获取统计分布及其参数很困难，实际问题中并不一定具备获取准确统计分布的条件。 第三章概率密度密度的估计

6 直接确定判别函数 基于样本的直接确定判别函数方法： 引言 针对各种不同的情况，使用不同的准则函数，设计出满足这些不同准则要求的分类器。
这些准则的“最优”并不一定与错误率最小相一致：次优分类器。 实例：正态分布最小错误率贝叶斯分类器在特殊情况下，是线性判别函数g(x)=wTx（决策面是超平面），能否基于样本直接确定w? 训练样本集 决策规则： 判别函数 决策面方程 选择最佳准则 第三章概率密度密度的估计

7 概率密度估计的方法 引言 类的先验概率的估计： 类条件概率密度估计的两种主要方法： 用训练数据中各类出现的频率估计 依靠经验
参数估计：概率密度函数的形式已知，而表征函数的参数未知，通过训练数据来估计 最大似然估计 Bayes估计 非参数估计：密度函数的形式未知，也不作假设，利用训练数据直接对概率密度进行估计 Parzen窗法 kn-近邻法 第三章概率密度密度的估计

8 3.2 参数估计 统计量：样本集的某种函数f(K)， K={x1, x2 ,…, xN}
参数空间：总体分布的未知参数θ所有可能取值组成的集合(Θ) 点估计的估计量和估计值： 第三章概率密度密度的估计

9 估计量的评价标准 估计量的评价标准：无偏性，有效性，一致性 无偏性：E( )=θ 有效性：D( )小，更有效
一致性：样本数趋于无穷时， 依概率趋于θ： 第三章概率密度密度的估计

10 3.2.1 最大似然估计 Maximum Likelihood (ML)
样本集可按类别分开，不同类别的密度函数的参数分别用各类的样本集来训练。 概率密度函数的形式已知，参数未知，为了描述概率密度函数p(x|ωi)与参数θ的依赖关系，用p(x|ωi,θ)表示。 估计的参数θ是确定而未知的，Bayes估计方法则视θ为随机变量。 独立地按概率密度p(x|θ)抽取样本集 K={x1, x2 ,…, xN}，用K估计未知参数θ 第三章概率密度密度的估计

11 似然函数 最大似然估计 似然函数： 对数(loglarized)似然函数： 第三章概率密度密度的估计

12 最大似然估计 最大似然估计 第三章概率密度密度的估计

13 最大似然估计示意图 最大似然估计 第三章概率密度密度的估计

14 计算方法 最大似然估计 最大似然估计量使似然函数梯度为0 ： 第三章概率密度密度的估计

15 一元正态分布例解 最大似然估计 第三章概率密度密度的估计

16 一元正态分布均值的估计 最大似然估计 第三章概率密度密度的估计

17 一元正态分布方差的估计 最大似然估计 第三章概率密度密度的估计

18 多元正态分布参数最大似然估计 最大似然估计 均值估计是无偏的，协方差矩阵估计是有偏的。 协方差矩阵的无偏估计是： 第三章概率密度密度的估计

19 3.2.2 贝叶斯估计-最大后验概率 用一组样本集D={x1, x2 ,…, xN}估计未知参数θ
未知参数θ视为随机变量，先验分布为 p(θ)，而在已知样本集D出现的条件下的后验概率为p(θ|D) 最大后验概率估计-Maximum a posteriori (MAP) 第三章概率密度密度的估计

20 决策问题与估计问题 决策问题: 样本x 决策ai 真实状态wj 状态空间A是离散空间 先验概率P(wj)
贝叶斯估计 决策问题: 样本x 决策ai 真实状态wj 状态空间A是离散空间 先验概率P(wj) 参数估计问题： 样本集D 估计量^s 真实参数s 参数空间S是连续空间 参数的先验分布p(s) 第三章概率密度密度的估计

21 贝叶斯(最小风险)估计 参数估计的条件风险：给定x条件下，估计量的期望损失 参数估计的风险：估计量的条件风险的期望
贝叶斯估计 参数估计的条件风险：给定x条件下，估计量的期望损失 参数估计的风险：估计量的条件风险的期望 贝叶斯估计：使风险最小的估计 第三章概率密度密度的估计

22 贝叶斯估计(II) 贝叶斯估计 损失函数定义为误差平方： 定理 3.1: 如果定义损失函数为误差平方函数，则有： 第三章概率密度密度的估计

23 贝叶斯估计的步骤 确定θ的先验分布 p(θ) 由样本集D={x1, x2 ,…, xN}求出样本联合分布：p(D|θ) 计算θ的后验分布
计算贝叶斯估计 第三章概率密度密度的估计

24 一元正态分布例解 样本集： K={x1, x2 ,…, xN} 用贝叶斯估计方法求μ的估计量 总体分布密度为： 均值μ未知，μ的先验分布为：
第三章概率密度密度的估计

25 一元正态分布例解(II) 贝叶斯估计 计算μ的后验分布： 计算μ的贝 叶斯估计： 第三章概率密度密度的估计

26 贝叶斯学习 贝叶斯学习：利用θ的先验分布 p(θ)及样本提供的信息求出θ的后验分布p(θ|K) ，然后直接求总体分布p(x|K)
第三章概率密度密度的估计

27 贝叶斯学习 Assume again that the unknown density p(x) has known parametric form (i.e., with parameters θ). The dependence of p(x) on θ is denoted as p(x/θ). p(x/D) would be the estimate of p(x/θ) given D 第三章概率密度密度的估计

28 贝叶斯学习 The above equation implies if we are less certain about the exact value of θ, we should consider a weighted average of p(x/θ) over the possible values of θ. Bayesian estimation approach estimates a distribution for p(x/D) rather than making point estimates like ML 第三章概率密度密度的估计

29 贝叶斯学习_步骤 Compute p(x/D) as follows:
From p(θ ), compute p(θ/D) using Bayes’ formula: Compute p(x/D) as follows: 第三章概率密度密度的估计

30 与ML解的关系 第三章概率密度密度的估计 Suppose p(θ/D) peaks very sharply at , and
then p(x/D) can be approximated as follows: (i.e., the best estimate is obtained by setting ) This is in fact the ML solution (i.e., p(D/θ) peaks at 第三章概率密度密度的估计

31 一元正态分布例解 计算μ的后验分布： 总体分布密度为： 均值μ未知，μ的先验分布为： 样本集： D={x1, x2 ,…, xN} 独立抽取
贝叶斯学习 总体分布密度为： 均值μ未知，μ的先验分布为： 样本集： D={x1, x2 ,…, xN} 独立抽取 计算μ的后验分布： 第三章概率密度密度的估计

32 一元正态分布例解 D不依赖于参数 第三章概率密度密度的估计

33 一元正态分布例解 (always lies between) 第三章概率密度密度的估计

34 一元正态分布例解 第三章概率密度密度的估计

35 一元正态分布例解 Bayesian Learning 第三章概率密度密度的估计

36 递归的贝叶斯学习 As the number of samples increases, p(x/D) converges to p(x/θ) -- develop an incremental algorithm: Dn: (x1, x2, …., xn-1, xn) Rewrite p(D/θ) as follows (using ) Dn-1 第三章概率密度密度的估计

37 递归的贝叶斯学习 Then, p(θ/D) becomes: n=1,2,… 第三章概率密度密度的估计

38 递归的贝叶斯学习 Training Data: p(θ/D4) peaks at p(θ/D0) 第三章概率密度密度的估计

39 递归的贝叶斯学习 ML estimate: Bayesian estimate: 第三章概率密度密度的估计

40 一元正态分布例解(II) 贝叶斯学习 直接计算总体密度： 第三章概率密度密度的估计

41 Bayes估计小结 Given a large number of samples, p(θ/Dn) will have a very strong peak at ; in this case: There are cases where p(θ/Dn) contains more than one peaks (i.e., more than one θ explains the data); in this case, the solution p(x/θ) should be obtained by integration. In general, p(x/Dn) converges to p(x/ θ) whether or not having one maximum. 第三章概率密度密度的估计

42 ML与Bayes估计的比较 Number of training data Computational complexity
The two methods are equivalent assuming infinite number of training data. For small training data sets, they give different results in most cases. Computational complexity ML uses differential calculus or gradient search for maximizing the likelihood. Bayesian estimation requires complex multidimensional integration techniques. 第三章概率密度密度的估计

43 ML与Bayes估计的比较 Solution complexity
Easier to interpret ML solutions (i.e., must be of the assumed parametric form). A Bayesian estimation solution might not be of the parametric form assumed. Prior distribution If the prior distribution p(θ) is uniform, Bayesian estimation solutions are equivalent to ML solutions. 第三章概率密度密度的估计

44 ML与Bayes估计的比较 Broad or asymmetric p(θ/D) General comments
In this case, the two methods will give different solutions. Bayesian methods will explicitly exploit such information. General comments There are strong theoretical and methodological arguments supporting Bayesian estimation. In practice, ML estimation is simpler and can lead to comparable performance. 第三章概率密度密度的估计

45 3.2.3 混合高斯模型 Mixed gaussian distribution 密度函数具有如下形式：正态模型的线性组合 需估计的参数：
参数 估计 Mixed gaussian distribution 密度函数具有如下形式：正态模型的线性组合 需估计的参数： 采用迭代法进行参数估计 第三章概率密度密度的估计

46 3.3 非参数估计 非参数估计：密度函数的形式未知，也不作假设，利用训练数据直接对概率密度进行估计。又称作模型无关方法。
参数估计需要事先假定一种分布函数，利用样本数据估计其参数。又称作基于模型的方法 两种主要非参数估计方法： 核函数方法 Parzen窗法 kN-近邻法 神经网络方法：PNN 第三章概率密度密度的估计

47 3.3.1 核函数方法 估计的目的：从样本集K= {x1, x2,…, xN}估计样本空间中任何一点的概率密度p(x)
非参数 估计 估计的目的：从样本集K= {x1, x2,…, xN}估计样本空间中任何一点的概率密度p(x) 基本方法：用某种核函数表示某一样本对待估计的密度函数的贡献，所有样本所作贡献的线性组合视作对某点概率密度p(x)的估计 第三章概率密度密度的估计

48 核函数方法图解 非参数 估计 第三章概率密度密度的估计

49 基本方法 非参数 估计 基本思想： 两种常用的方法： Parzen窗法: kN-近邻法: 第三章概率密度密度的估计

50 基本方法 P(X’)为P(X)在R内的变化值,P(X)就是要求的总体概率密度 R P(x) 第三章概率密度密度的估计

51 基本方法 假设有N个样本X=(X1, X2,… XN)T都是按照P(X)从总体中独立抽取的。若N个样本中有k个落入在R内的概率符合二项分布
数学期望： E(k)=k=NP 对 概率P的估计： 设P(x’)在R内连续变化,当R逐渐减小的时候,小到使P(x)在其上几乎没有变化时，则 第三章概率密度密度的估计

52 基本方法 ∴ ∴ 条件密度的估计 第三章概率密度密度的估计 讨论:①当V固定的时候N增加, k也增加，当 (V足够小)
∴ 条件密度的估计 (V足够小) 讨论:①当V固定的时候N增加, k也增加，当 只反映了P(x)的空间平均估计而反映不出空间的变化 ② N固定,体积变小 当 k=0时 当 所以起伏比较大,噪声比较大,需要对V进行改进 第三章概率密度密度的估计

53 基本方法 对体积V进行改进： 为了估计X点的密度,我们构造一串包括X的区域序列R1,R2,.. RN.对R1采用一个样本进行估计，对R2采用二个样本进行估计..。设VN是RN的体积，KN是N个样本落入VN的样本数则 密度的第N次估计： KN是N个样本落入VN的样本数 ∴PN(x)是P(x)的第N次估计 第三章概率密度密度的估计

54 基本方法 若PN(x)收敛于P(x)应满足三个条件： ① ，当N↑时，VN↓，N→∞，VN→0
这时虽然样本数多，但由于VN↓，落入VN内的样本KN 也减小，所以空间变化才反映出来  ② ，N ↑ ，kN ↑ ，N与KN同相变化 ③ ，KN的变化远小于N的变化。 因此尽管在R内落入了很多的样本，但同总数N比较, 仍然是很小的一部分。 第三章概率密度密度的估计

55 3.3.2 Parzen窗法 超立方体内样本数： 某点概率密度p(x)的估计 样本集KN= {x1, x2,…, xN}
非参数 估计 样本集KN= {x1, x2,…, xN} 区域RN是一个d维超立方体，棱长hN，体积VN= hNd 定义窗函数： 超立方体内样本数： 某点概率密度p(x)的估计 第三章概率密度密度的估计

56 核函数的选择 非参数 估计 核函数需满足归一化条件： 两种常用的核函数： 均匀核： 正态核： 第三章概率密度密度的估计

57 窗宽的选择 估计收敛的充要条件： 为保证估计依概率渐进收敛到真实的概率密度，即： hN是控制“窗”宽度的参数，根据样本的数量选择。
非参数 估计 hN是控制“窗”宽度的参数，根据样本的数量选择。 太大：平均化，分辨力低 太小：统计变动大 为保证估计依概率渐进收敛到真实的概率密度，即： 估计收敛的充要条件： 第三章概率密度密度的估计

58 不同窗宽的估计效果 非参数 估计 第三章概率密度密度的估计

59 Parzen窗法示例 非参数 估计 第三章概率密度密度的估计

60 有限样本的影响 均方误差最小(MSE)准则 N d N4/(d+4) 16 1 0.1 32 2 178 5 3162 10 3E+13
非参数 估计 均方误差最小(MSE)准则 N d N4/(d+4) 16 1 0.1 32 2 178 5 3162 10 3E+13 50 维数灾难(Curse of Dimensionality): 当维数较高时，样本数量无法达到精确估计的要求。 第三章概率密度密度的估计

61 3.3.3 kN-近邻法 均匀核函数Parzen估计，窗宽固定，不同位置落在窗内的样本点的数目是变化的。
非参数 估计 均匀核函数Parzen估计，窗宽固定，不同位置落在窗内的样本点的数目是变化的。 kN-近邻估计：把窗扩大到刚好覆盖kN个点。落在窗内的样本点的数目固定，窗宽是变化的。kN根据样本总数N选择。 概率密度估计表达式：点x处窗的“体积”是Vn： 第三章概率密度密度的估计

62 kN-近邻法举例 kN的选择： 渐进收敛容易保证； 有限样本性质、最小平方误差与Parzen窗几乎相同 第三章概率密度密度的估计
非参数 估计 kN的选择： 渐进收敛容易保证； 有限样本性质、最小平方误差与Parzen窗几乎相同 第三章概率密度密度的估计

63 3.4 讨论 概率密度函数包含了随机变量的全部信息，是导致估计困难的重要原因。
高维概率分布的估计无论在理论上还是实际操作中都是一个十分困难的问题。 进行模式识别并不需要利用概率密度的所有信息，只需要求出分类面。 先估计概率密度，再进行分类，可能走了“弯路”。 第三章概率密度密度的估计

64 习题 一元正态分布的最大似然估计： 用C/Java语言设计一程序片断，计算上题中的估计参数(μ,σ2)
假设样本x服从正态分布N(μ,σ2) 已获得一组样本 x1 , x2 , … , xN 用C/Java语言设计一程序片断，计算上题中的估计参数(μ,σ2) 试简述参数估计，非参数估计等概念间的关系 证明对正态总体的期望u的最大似然估计是无偏的，对方差s2的最大似然估计是有偏的。 第三章概率密度密度的估计

65 1.在给定样本的情况下，分别基于Parzen窗的方法和ML的方法估计这批样本的概率密度函数。
2.分别基于这两种方法的得到的概率密度函数构造分类器，对两类数据进行分类。比较他们的分类结果。 第三章概率密度密度的估计