模式识别概率密度估计

1 第三章概率密度函数的估计 2 前一章我们讨论了各种决策规则 在设计分类器时 总是假定先验概率和类条件密度函数是已知的 在实际工作中 先验概率和类条件密度函数都可能未知 需要利用样本设计分类器 3 利用样本设计分类器的方法有两种 从样本中估计先验概率和类条件密度函数 然而按前一章的方法 2 不作估计 直接利用样本设计分类器 在用第一种方法时 需要从收集的样本中去估计先验概率和类条件密度函数 这就要用到估计理论 讨论如何估计 估计的方法 估计的好坏 性质 4 从样本中估计概率密度函数时 有以下一些情况 概率密度估计 参数估计 分布形式已知 但参数要估计 非参数估计 分布形式未知 直接估计密度函数 有监督的参数估计 样本类别已知 无监督的参数估计 样本类别未知 最大似然估计 把待估参数看作是确定的 贝叶斯估计 把待估参数看作是随机的 Parzen窗估计 KN近邻估计 KN近邻分类法 5 参数估计中的一些基本概念 统计量 针对不同的要求所构造的样本的函数 包含了总体的信息 参数空间 未知参数全部可允许值的集合 点估计 构造一个统计量作为待估参数的值 即估计参数值 区间估计 估计待估参数可能取值的区间 6 3 1常数参数的估计 一般要估计的参数可能是标量 向量 矩阵 不失一般性 假定待估参数是向量 在最大似然估计中 把待估参数看作是确定的常数 而贝叶斯估计则把看作是随机变量 它的先验密度是已知的 7 一 最大似然估计 令是随机向量x的密度函数中的向量参数 其分量是标量 记x的密度函数为 令是观测x所得到的N个样本 在估计问题中 这些样本本身也是随机变量 可以用一个联合密度函数表示 假定这些样本是独立的 是的函数 它是的似然函数 8 只要导数存在 使似然函数最大的可以通过解下面的似然方程或对数似然方程得到 的最大似然估计是 在N个观测样本的基础上 选择这样的 它使似然函数最大 换句话说 选择的应使落在 样本 的附近小区域内最大 当均匀分布时 发生概率最大 N个观测样本 9 由于对数函数是单调增的 所以这两个方程完全是等价的 用时哪个方便 就用哪个 例1 计算机通道输出请求出现率的估计 假定计算机的某一通道输出请求的时间间隔T按如下的指数函数分布 假定观察了N 1个请求 间隔时间为 希望估计参数 的大小 称为到达率 10 解 输出请求间的间隔假定为独立的 似然函数 联合密度函数 为 而 对数似然方程 11 例2 多元正态密度函数均值的估计 上面的例子估计了一个标量参数 本例估计一个向量参数 已知随机变量x是正态分布的 协方差矩阵K已知 均值m未知 给出N个样本x 1 x 2 x N 求均值的最大似然估计 解 似然函数是样本的联合密度函数 12 对数似然函数为样本联合密度函数的对数 将上式对m求导并令它等于0 有 K是一个常数矩阵 即均值的最大似然估计等于样本均值 13 例3 已知x服从均匀分布 似然函数为 解 给出了N个样本x 1 x 2 x N 在用求导数的方法解似然方程时 求极值 有时可能遇到一些问题 有多个极值点 或没有极值点 下面看一个例子 14 对数似然函数为 欲使上两式等于0 必须无穷大才行 而因为不能大于最小的样本值 不能小于最大的样本值 15 同时为使似然函数最大 要最小 而最小的可能值是 似然函数在最大值的地方没有零斜率 16 二 估计量的性质 注意语言中的断句 分词 参数的一个估计量是样本的函数 所以估计量本身也是一个随机向量 因此可以在统计的意义上描述它的性质 建立评价 估计好坏 的标准 无偏性 unbiased 若 则称是无偏的 否则称为有偏的 若 则称是渐进无偏的 17 一致性 consistent 若对任意小的正数 有 称估计的序列为在概率上收敛于 则称是一致的 有的人定义一致性为 这称为在均方 meansquare 意义上收敛于 18 有效性 efficient 若和都是的估计 当时 称估计比有效 样本容量N固定 使取得最小值的估计 在大多数情况下 可以认为这两种定义等价 实际上 的定义比 更强 即当 称为的有效估计 19 Cramer Rao定理 如果是的任一无偏估计 则估计的任一分量的方差满足 式中 是下面矩阵J的逆矩阵的对角线元素 如果是无偏的 且比有效 则是一致估计 可以证明 最大似然估计是一致的 矩阵J称为Fisher信息矩阵 20 满足 或 的等式的估计是所有估计中最有效的 称为最小方差估计 当最小方差估计存在时 它一定是最大似然估计 称为Cramer Rao不等式 当是标量时 式化为 21 证明 由于是无偏的 有 是最小方差估计的必要和充分条件是 式中是一个矩阵 它的元素是的函数 但不能是的函数 22 将上式对求导 有 a 23 由前面的定义 构造一个随机向量 由 式和有 24 由于相关矩阵是半正定的 上式的行列式大于 等于0 i 1 1 i 1 2i 3奇数 25 式中是J的i行i列的代数余子式 J的逆矩阵的对角线元素 当为最小方差估计时 相关矩阵的行列式为0 zi的分量是线性相关的 所以有 例4 例2中关于均值的估计是无偏的 解 26 若各个样本x i 是独立的 它们也是不相关的 所以估计的协方差矩阵是 的协方差减小 27 它比有效 又由于无偏 是m的最小方差估计 是m的一致估计 又由于 具有的形式 28 如果对待估参数有一些先验知识 这时可以把待估参数看作一个随机向量 用一个密度函数来刻画 那么这时可以使用贝叶斯估计 3 2贝叶斯估计 最大似然估计把待估参数看作确定的量 它用于对未知参数没有先验知识或不愿意作某些假定的时候 贝叶斯估计和贝叶斯决策是一样的思路 一 贝叶斯估计 29 引入一个连续的损失函数 定义贝叶斯风险为 式中 贝叶斯风险 条件风险 30 这时 若假定是非负的 也是非负的 最小和最小R是等价的 而 使它们最小的估计称贝叶斯估计 注意 它和前面的是不同的 这里是参数 是联合密度函数 31 前式 是一样的 对于所有实际的应用 用符号 是为了表示是一个随机向量 32 二 常用的损失函数 均方估计和最大后验估计 为了求贝叶斯估计 我们需要先定义 先给出 损失函数的形式 不同的损失函数会带来不同的贝叶斯估计值 下面分析两种常用的损失函数的形式 平方误差损失函数和均方估计 误差的二次函数 33 而 为了得到使最小的 只要 即估计是的后验密度的均值 这个估计称为均方估计 因为它使均方误差最小 34 求解均方估计的步骤可以归纳如下 确定的先验分布 而 由样本集 求联合分布 利用贝叶斯公式 求的后验分布 求 35 均匀损失函数和最大后验估计 损失函数为 当时 这时 当时 36 区域是 任意小 这样 为使最小 积分项应最大 而积分项 所以应使 最大 称为最大后验估计 由贝叶斯公式 如果先验概率是均匀的 在感兴趣区 这时最大等价于最大 这时最大后验估计即最大似然估计 37 例5 正态分布均值的贝叶斯估计 令x 1 x 2 x N 是从已知协方差矩阵Kx和未知均值m的正态分布中抽取的 假定均值本身的分布为正态N m0 Km 分布 先验密度 利用贝叶斯公式 可得后验密度 是正态的 其均值为 38 由于既是后验密度的均值 也是后验密度的最大值 所以既是均方估计也是最大后验估计 当都是一维时有 39 40 样本均值和先验均值的线性组合 系数和为1 且都是正的 41 当N 0时 全部由先验均值定 当时 由样本均值定 当时 先验信息非常可靠 当时 先验的推测不可靠 一般情况下 c为小于无穷大的非负实数 当样本足够多时 对 m0的假设就不重要了 由先验均值定 由样本均值定 42 这节讨论直接从样本中估计密度函数的方法 主要介绍两种方法 3 3概率密度函数估计的非参数方法 非参数估计 前两节讲的参数估计方法要求 假定 密度函数的形式是已知的 但实际工作中往往是 密度函数的形式不知道 密度函数的形式不是典型的常见分布 不能写成某些参数的函数 43 一 Parzen窗估计 Parzen窗法 KN近邻法 先估计类条件密度函数 然后用在似然比检验中 由类条件密度函数的估计 直接导致似然比检验 基本思路 以一维随机变量的密度函数的估计为例 对随机变量x 假定得到了N个独立的样本 x 1 x 2 x N 它的密度函数p x 可以用一个直方图近似 每一小区间的宽度为 中点为 44 样本落在小区间内的概率可以近似为 如果样本数足够多 则概率 上述事件 可以用频率 近似 所以密度可以用近似 45 把上述的思路一般化 定义如下的窗函数 则是以为中心的x的函数 对落在内的样本 其函数值均为 对落在方窗外的样本 函数值为0 46 这时 一个样本贡献 共有K个 换个角度 即是N个窗的迭加 函数r称为核函数 势函数或者Parzen窗函数 核函数 窗函数 也可以是其它的形状 常用的有 47 48 矩形窗估计出的容易产生不连续 钉子状 spiked 为了满足使估计出的是正的 而且积分为1 是密度函数 窗函数要满足 下面对上述方法作些理论和实际应用上的分析 如果把区间2h 在多维时是体积V 固定 当样本数越来越多时 概率 但得到的密度却是空间的平均值 而非某一点的 49 要得到 而不是的平均值 则体积V 2h 0 但当V0时 若样本数有限 则 假定有相当多的样本N可以利用 这时由于 下标表示总样本数 50 这时若满足 窗函数若满足 使空间平均密度点的 频率收敛于概率 落在小区域内的样本同总数相比是低阶无穷大 51 比更快的0 这时 是渐近无偏和均方一致的 随机向量密度函数的估计 定量的分析 另种分析方法 有一随机向量x R是包含待估密度点的一个小区域 记x在R内的概率P 根据积分中值定理 为 式中是区域R的体积 而是区域R中的某一点 52 当是连续的 且R取的足够小时 有 所以 为了从一组样本x 1 x 2 x N 中估计P 我们要看N个样本中有多少落在区域R内 假定各样本独立 则N个样本中有K个落在R中的概率服从二项分布 53 上述二项分布的均值和方差为 P的最大似然估计 是要求 使得 最大 对 求导 并令其等于0 有 54 这个估计是无偏的 这个估计也是一致的 无偏且有效 因为估计的方差为 当N变大时 方差变为无限小 所以有效 无偏且有效一致估计 55 由估计出的 有 Parzen窗估计定义区域R是超立方体 定义核函数为 而 56 这时 式为 核函数的选择和一维时一样 也可选择其它的函数 如 57 在选择核函数或核函数的参数时 应该注意的是 若核函数太 窄 则估计出的密度有可能不连续 呈现钉子状 若核函数太 宽 则估计出的密度有可能太平滑 不能显示分布的细节 在实际问题中 核函数的选择取决于 待估密度函数的形式 样本数的多少 58 二 KN 近邻估计 在Parzen窗估计中 由于核和体积是固定的 所以若样本分布不均匀 就不能得到满意的估计 解决的办法是 不使用固定的区域 而是固定落在区域内的样本数 例如KN个 而区域则由的邻域中正好包含KN个样本定 之所以用符号KN 表示K的选择和总样本数有关 当把KN近邻法估计出的密度函数直接用于分类时 可以导致非常简单和有效的分类法 59 这样作的好处是 KN近邻估计的公式仍然为 样本多的地方 体积用的小些 提高分辨率 样本少的地方 体积用的大些 中间补些值 平滑一些 60 近邻法在以下的条件下 将收敛于 61 三 近邻分类法 以两类问题为例 1和 2 定义体积V是一个超球 中心在 半径是r 区域是 令每类的超球的半径所确定的超球正好包含该类的K个样本 是前面讲过的任一种距离 令Ni i 1 2 是每类的样本数 62 先验概率的估计是 利用 密度估计公式 和最小错误率贝叶斯决策公式 63 即 对每类固定的样本数 K 包含该类K个样本的体积分别为V1和V2 然后比较V1和V2的大小 64 若V2 V1 在附近 1类的样本多 则 1 若V1 V2 在附近 2类的样本多 则 2 这种决策形式是样本数固定 比体积 groupedform 另一种更方便的形式是 在 待估点 周围选一体积V 它正好包含K个总样本数 1和 2的 这样 两类的体积相同 但在这一体积内包含的 1和 2的样本数不同 分别为K1和K2 65 依贝叶斯规则 有 即 在同一个超球内 哪类的样本多 就把归到哪类 66 注意 K一般取奇数 防止出现K1 K2的情况 K K1 K2 这种形式 称为pooledform 非常简单 它不需要计算体积 只要计算的K个近邻中 哪类的样本多就行了 另外 KN近邻分类的性能也不错 当样本数时 1 近邻法 最近邻法 的错误率不超过最小错误率贝叶斯决策的错误率的二倍 当K 1时 错误率还要低 但以贝叶斯错误率为下界 67 近邻法分类的主要问题是 当特征维数和样本数大时 寻找K近邻的计算量大 关于如何减少计算量和近邻的快速搜索算法 关于近邻法的错误率分析等 下一章专门讲 把近邻法推广到多类问题中是很直接的 假定有Nc类 先验概率的估计为 N是样本总数 各类的密度估计为 因此判别函数为 68 对于pooled法 体积正好为包含有K个总样本 K1 K2 KNc K 因此等价的判别函数为 决策规则为哪个Ki大 就把Ki分到该类 69 3 4分类器错误率的实验估计 前面我们已经提过 分类器错误率的计算和估计有三种方法 1 按理论公式计算 2 估算错误率的上限 当先验概率已知 类条件密度已知 定下决策规则后 按错误率的公式计算 要作多重积分 介绍了Bhattacharyya界和Chernoff界 3 实验估计 70 由于前两种情况计算上的困难 且要求知道密度函数 所以实际工作中常用的是实验估计 即利用样本来估计错误率 需要分析 如何利用样本 估计出的错误率的性质如何 分两种情况讨论 1 已设计好分类器时 如何用样本估计错误率 2 未设计好分类器时 如何把样本分为两部分 一部分用来设计分类器 另一部分用来检验分类器 71 一 已设计好分类器时的错误率的估计 利用考试样本检验分类器时 直观上认为错误率 从估计理论上看 还需要分析 错分样本数 样本总数 1 这个估计性质如何 2 这个估计是最好的吗 3 当检验样本数增多时 估计结果会有改善吗 表现在什么地方 下面分两种情况讨论 72 1 先验概率Pr 1 和Pr 2 未知 随机抽样作为检验集 当不知Pr 1 和Pr 2 时 随机取N个样本 假定错分了K个 用表示真实的错误率 则K服从二项分布 的最大似然估计 是的最大似然估计 73 由于K是随机变量 也是随机变量 而 是无偏的 由于时 有效 一致 74 2 先验概率Pr 1 和Pr 2 已知时 选择抽样 当已知两类的先验概率Pr 1 和Pr 2 时 可以分别抽取N1 Pr 1 N和N2 Pr 2 N个样本作检验集 设K1和K2分别为N1和N2中被错分类的 因为K1和K2是相互独立的 故 其中 i 1 2 是 i类的真实错误率 75 利用同样方法 得 i 1 2的最大似然估计为 而总的估计错误为 的期望和方差为 无偏 76 以上得到了未知先验概率时的估计量和已知先验概率时的估计量 哪一种更好呢 它们都是无偏的 比较一下它们的方差 选择抽样的错误率的估计的方差要小 合理 77 以上对于两类的讨论可以推广到多类 归纳以上的分析 有 上述错误率的估计在最大似然估计的意义上最好 这些估计都是错误率的无偏估计量 随样本数的增加 置信区间相应地减小 78 二 未设计好分类器时错误率的估计 如何划分设计样本集和检验集 实际工作中 能够得到