哈尔滨工业大学：《模式识别》课程教学资源（PPT课件讲稿）第四章统计分类器及其学习.doc_大学文库

第四章统计分类器及学习在距离分类器和判别函数分类器中,我们都是把模式看作是N维欧氏空间中的一个点, 而且统一类别的模式在空间中聚集在一定的区域,不同模式的区域在空间中具有一定的分离性。在本章所讨论的统计分类器中,我们仍然认为模式是欧氏空间中的一个点,但是每一类模式不是分布在空间中的一个确定区域,而是可能分布在整个空间,只不过空间中每一点属于某一类的概率不同,属于这一类的可能性大一些,属于另一类的可能性小一些。我们可以利用这样的性质来建立统计分类器。 41概率论基本知识本章中我们使用的主要数学工具是概率论,因此先来复习一些概率论的知识。事件自然界的事件可以分为确定性事件和不确定性事件,确定性和不确定性主要体现在事件的概念和发生上。概念是确定的,发生也是确定的,这是确定事件,例如在标准大气压下, 水加热到100度就会开:概念是确定的,发生是不确定的,称为随机事件,例如掷骰子事件还有一些事件的概念本身就不确定,这类事件称为模糊事件,例如年青人的概念是不确定的, 遇到的人是年青人的事件就是模糊事件对模糊事件的处理,在模式识别中也占有重要的地位,本章中我们只讨论随机事件。、随机变量随机事件的数量表示称为随机变量。取值为离散的称为离散随机变量,例如掷硬币,只可能出现正、反两面,分别用0和1表示;取值为连续的称为连续随机变量,例如测量物体的长度。频率和概率设A为联系于某个试验的随机事件,试验在相同的条件下重复N次,其中M次A事件发生,则A发生的频率为MN,计为:(4)=MN 由于A事件的随机性,A的频率也是一个随机变量。但是当N很大时,频率会趋向一个稳定值,称为A的概率,即P(4)=lmJ(4 四、联合概率和条件概率联合概率:设A,B是两个随机事件,A和B同时发生的概率称为联合概率记为:P(AB); 条件概率:在B事件发生的条件下,A事件发生的概率称为条件概率,记为:P(4B) 乘法定理:条件概率与联合概率之间存在如下关系:P(AB)=P(AB)/P(B)

32 第四章统计分类器及学习在距离分类器和判别函数分类器中，我们都是把模式看作是 N 维欧氏空间中的一个点，而且统一类别的模式在空间中聚集在一定的区域，不同模式的区域在空间中具有一定的分离性。在本章所讨论的统计分类器中，我们仍然认为模式是欧氏空间中的一个点，但是每一类模式不是分布在空间中的一个确定区域，而是可能分布在整个空间，只不过空间中每一点属于某一类的概率不同，属于这一类的可能性大一些，属于另一类的可能性小一些。我们可以利用这样的性质来建立统计分类器。 4.1 概率论基本知识本章中我们使用的主要数学工具是概率论，因此先来复习一些概率论的知识。一、事件自然界的事件可以分为确定性事件和不确定性事件，确定性和不确定性主要体现在事件的概念和发生上。概念是确定的，发生也是确定的，这是确定事件，例如在标准大气压下，水加热到 100 度就会开；概念是确定的，发生是不确定的，称为随机事件，例如掷骰子事件；还有一些事件的概念本身就不确定，这类事件称为模糊事件，例如年青人的概念是不确定的，遇到的人是年青人的事件就是模糊事件。对模糊事件的处理，在模式识别中也占有重要的地位，本章中我们只讨论随机事件。二、随机变量随机事件的数量表示称为随机变量。取值为离散的称为离散随机变量，例如掷硬币，只可能出现正、反两面，分别用 0 和 1 表示；取值为连续的称为连续随机变量，例如测量物体的长度。三、频率和概率设 A 为联系于某个试验的随机事件，试验在相同的条件下重复 N 次，其中 M 次 A 事件发生，则 A 发生的频率为 M N ，计为： f A M N N ( ) = 。由于 A 事件的随机性， A 的频率也是一个随机变量。但是当 N 很大时，频率会趋向一个稳定值，称为 A 的概率，即 ( ) lim N ( ) N P A f A → = 。四、联合概率和条件概率联合概率：设 A B, 是两个随机事件， A 和 B 同时发生的概率称为联合概率，记为： P A B ( , ) ；条件概率：在 B 事件发生的条件下， A 事件发生的概率称为条件概率，记为： P A B ( ) ；乘法定理：条件概率与联合概率之间存在如下关系： P A B P A B P B ( ) = ( , ) ( ) ；

36 4.3 最小平均风险准则贝叶斯分类器前面我们以最小错误率为准则建立的贝叶斯分类器，然而对某些问题来说这样的准则并不适合。这是因为每次误判所带来的后果并不一样，有一些类别被误判的后果非常严重，而另一些类别被误判的后果却并不严重，例如对于癌症诊断问题，如果一个癌症患者被误判为正常，那么后果非常严重，有可能耽误治疗；而一个正常人被误诊为患有癌症，后果并不很严重，随着进一步的诊断，可以改变这种误判。下面我们就来介绍一种依据最小平均风险准则的贝叶斯分类器。设由 M 个类别， 1 2 , , ,   M 。首先我们需要根据实际问题定义一组数据 Lij ，表示将 i 类的样本误判为  j 类的代价，这应该是一个 M M 的矩阵。然后我们可以用下面的公式计算将未知模式 X 判别为  j 类的平均风险： ( ) ( ) 1 M j ij i i  L P = X X =   其中 L Pij i ( X) 为用 Lij 加权的后验概率。因为当我们将 X 分类为  j 时，它有可能是 M 类的任何一类，因此总的平均风险就是对加权后的后验概率求和。我们的判决准则应该是选择一个平均风险最小的类别作为输出的决策类别。因此可以构造判别函数： dj j (X X ) = − ( )。现在的问题同最小错误率准则一样，我们并不知道后验概率 P(i X) ，而是已知先验概率 P(i) 和条件概率 P(X i) ，因此我们还需要使用贝叶斯公式将后验概率转换为先验概率： ( ) ( ) ( ) ( ) 1 1 M j ij i i i L P P P  = X X =    X 因为 ( ) 1 P X 是公共项，对比较大小没有影响，因此可以舍去： ( ) ( ) ( ) 1 M j ij i i i  L P P = X X =    现在还是看一下两类问题的情况：将 X 判别为 1 类的平均风险为：  1 11 1 1 21 2 2 (X X X ) =   +   L P P L P P ( ) ( ) ( ) ( ) 将 X 判别为 2 类的平均风险为：

37  2 12 1 1 22 2 2 (X X X ) =   +   L P P L P P ( ) ( ) ( ) ( ) 当   1 2 (X X )  ( ) 时，判别 X 为 1 类；当   1 2 (X X )  ( ) 时，判别 X 为 2 类。以第一种情况进行推导： L P P L P P L P P L P P 11 1 1 21 2 2 12 1 1 22 2 2 (X X X X   +      +   ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 即： (L L P P L L P P 21 22 2 2 12 11 1 1 −    −   ) (X X ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 2 21 22 2 1 12 11 P P L L P P L L   −     − X X 定义似然比： ( ) ( ) ( ) 1 12 2 P l P  =  X X X ，定义阈值： ( ) ( ) ( ) ( ) 2 21 22 21 1 12 11 P L L P L L   − =   − 。这样就可以得到最小平均风险准则下的贝叶斯判决条件：若 l 12 21 (X)  ，则 X1 ；若 l 12 21 (X)  ，则 X2 。例 4.2 4.4 贝叶斯分类器的学习贝叶斯分类器的工作原理非常简单，完全是根据待识模式 X 对各个类别的后验概率 P(i X) 来分类的，判别为后验概率最大的类别。后验概率可以根据贝叶斯公式转化为先验概率 P(i) 和类条件概率 P(X i) 。下面我们来研究贝叶斯分类器的学习问题，也就是说如何通过训练样本集来得到 P(i) 和 P(X i) 的问题。对于一个具体问题来说， P(i) 和 P(X i) 我们并不知道，而是已知各个类别的训练样本集合： ( ) ( ) ( ) ( )  1 2 , , , i i i i i X X X X = N ，i M =1, 2, , 。 (i) X j 表示第 i 个类别的第 j 个训练样本，第 i 类共有 Ni 个训练样本。一般来说 P(i) 比较容易得到，因为类别数是有限的，可以通过统计多个样本得到各个类别出现的几率，用它来近似概率，比如可以根据大量病例统计出在普通人中癌症的患病率，也可以根据先验知识来确定，比如掷两枚样币同时出现正面的概率。然而类条件概率 P(X i) 的获得却往往是一个比较困难的事情。如果 X 是离散型的时候，问题相对来说还比较简单一些，如果样本量足够多的话，可以分别统计出各个类别中出

现某个特征矢量的几率。然而当X为一个连续型的特征是矢量时,问题就会非常复杂。因为这种情况下我们要找到的是条件概率密度函数p(X2),而概率密度函数可以是任意形式,而我们的训练样本的数量毕竟是有限的,因此不可能很好的拟合出概率密度函数。因此我们往往采用一些简化的办法这些简化办法中最重要的一点就是要对所求的概率密度函数的形式作出一定的限制,假设概率密度函数符合某种概率模型,而概率模型是可以用一组参数来描述的,这样我们就可以使用数理统计的方法,利用训练样本来估计这组参数,有了模型参数,就可以得到概率密度数。下面介绍几种常用的概率模型及其估计方法。高斯模型( Gaussian model) 高斯模型也称为正态分布模型,是一种最常见的概率模型,自然界中很多物理现象都符合正态分布假设,比如说我们对一个物理量的测量。N维的正态分布函数可以表示为: P(X2,) exp -(X-m )C-le 正态分布函数完全可以有两个参数来描述均值矢量:m=E[X] 协方差矩阵:C2=E[(x-m)x-m)]=E(xX)mm 正态分布的参数的估计方法非常简单,根据数理统计的理论,虽然均值和协方差都需要求一个数学期望,也就是当数量N趋近于无穷大时求平均,但是当样本量足够大时可以用有限样本的算术平均来近似,即: c(x-n)(x-m)点2 ∑x(x)-mm 例二、混合高斯模型( Mixed gaussian model,GMM) 正态分布模型的训练和使用非常简单,然而对于一个实际问题来说,特征的分布函数并不一定满足正态分布,其分布形式可能非常复杂,并且往往呈现一种多峰情况,如下图所示这时再用高斯模型来描述它的概率密度函数就会产生很大的误差。为了描述这些复杂的分布函数,我们可以采用简单函数的线性组合来逼近复杂函数。GMM模型就是用多个高斯函数的线性组合来描述复杂的分布函数我们可以用N(mC)来表示一个高斯分布函数,m为均值矢量,C为协方差矩阵。那么一个GMM概率密度函数可以表示为 p(x9)=∑N(m,c),其∑=1

38 现某个特征矢量的几率。然而当 X 为一个连续型的特征是矢量时，问题就会非常复杂。因为这种情况下我们要找到的是条件概率密度函数 p (X i) ，而概率密度函数可以是任意形式，而我们的训练样本的数量毕竟是有限的，因此不可能很好的拟合出概率密度函数。因此我们往往采用一些简化的办法。这些简化办法中最重要的一点就是要对所求的概率密度函数的形式作出一定的限制，假设概率密度函数符合某种概率模型，而概率模型是可以用一组参数来描述的，这样我们就可以使用数理统计的方法，利用训练样本来估计这组参数，有了模型参数，就可以得到概率密度数。下面介绍几种常用的概率模型及其估计方法。一、高斯模型（Gaussian Model ）高斯模型也称为正态分布模型，是一种最常见的概率模型，自然界中很多物理现象都符合正态分布假设，比如说我们对一个物理量的测量。 N 维的正态分布函数可以表示为： ( ) ( ) ( ) ( ) 1 2 1 2 1 1 exp 2 2 T i i i i N i p C  C   −  = − − −     X X m X m 正态分布函数完全可以有两个参数来描述：均值矢量： m X i i = E   ；协方差矩阵： ( )( ) ( ) T T T C E E i i i i i i i = − − = −     X m X m XX m m 正态分布的参数的估计方法非常简单，根据数理统计的理论，虽然均值和协方差都需要求一个数学期望，也就是当数量 N 趋近于无穷大时求平均，但是当样本量足够大时可以用有限样本的算术平均来近似，即： ( ) 1 1 Ni i i j j Ni = m X   ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 1 N N i i T T i i i i T i j i j i j j i i j j i i C N N = =    − − = −       X m X m X X m m 例 4.3 二、混合高斯模型（Mixed Gaussian Model, GMM）正态分布模型的训练和使用非常简单，然而对于一个实际问题来说，特征的分布函数并不一定满足正态分布，其分布形式可能非常复杂，并且往往呈现一种多峰情况，如下图所示。这时再用高斯模型来描述它的概率密度函数就会产生很大的误差。为了描述这些复杂的分布函数，我们可以采用简单函数的线性组合来逼近复杂函数。GMM 模型就是用多个高斯函数的线性组合来描述复杂的分布函数。我们可以用 N (m,C) 来表示一个高斯分布函数， m 为均值矢量， C 为协方差矩阵。那么一个 GMM 概率密度函数可以表示为： ( ) ( ) ( ) ( ) ( ) 1 K i i i i j j j j p a N = X m ,C  = ，其中 ( ) 1 1 K i j j a =  =

39 上述 GMM 模型是由 K 各高斯模型线性组合而成， j a 为组合系数。例如下图就是由两个高斯函数组合而成： p x N N ( ) = − + 0.7 10,2 0.3 (5,3) ( ) GMM分布函数的训练要比单个高斯模型复杂得多，这里需要训练的参数有 j a ，m j 和 Cj ，而 K 值是要预先确定的。GMM的训练一般采用EM迭代算法(Expectation Maximization Algorithm)，称为期望最大化算法。三、隐含 Markov 模型（Hidden Markov Model, HMM）在实际问题中，有时我们遇到的识别对象是连续信号，例如语音信号。下图分别显示了三个元音的一段采样信号，’a’, ‘o’, ‘e’。这样的连续信号，如果还是用特征矢量来描述，无法反映出信号之间的时间相关性，往往需要用一个随机过程来描述。对于连续信号，一般是采用分段来处理的，例如以 512 点为一段，称为一帧信号。在每一帧信号中抽取出特征，构成特征矢量，例如语音信号中可以抽取 Fourier 变换系数，信号通过零点的次数等等作为这一帧的特征。这样一段信号就可以用一个特征矢量的序列来表示，一般称为观察序列： 1 2 , , , O = O O ON 其中的 Oi 称为观察值，是一个特征矢量。如果我们要对这样的模式构造贝叶斯分类器，也要知道每个类别的条件概率 P O( i) ，然而对于这样的观察序列，显然无法用高斯模型或高斯混合模型来描述，需要有一个新的模型—隐含 Markov 模型来描述。对每一个类别建立一个 HMM，有这样一个 HMM 可以计算出观察序列 O 在每个类别的条件概率 P O( i) ，再结合类的先验概率 P(i) ，就可以构造出一个贝叶斯分类器。下面简单介绍一下 HMM 的基本知识，在随机过程中，每一时刻的取值只与之前的过程有关，而与之后的过程无关，这样的过程称为 Markov 过程，只与前一时刻的值有关，则称

移到每个状态的概率不同,例如由第i个状态转移到第j个状态的概率为an 同时HMM开始的第一个状态也是不确定的,有可能开始于任何状态,开始于第i个状态的概率可以表示为:z1 这样一个HMM就可以用一个三元组表示 A=(AB 其中A={an}为一个MxM的方阵,称为状态转移矩阵,M为模型的状态数。 B={(O)为由一组M个概率密度函数构成的矢量,丌={x}为M维矢量,称为初始概率分布。明显应该有: 1=1,∑a=1,b(O)dO=1 现在我们关心的是两个问题:识别问题和训练问题 1.识别问题识别问题可表述为如果我们己知一个HMM模型A=(ABπ),如何计算该模型输出待识模式观察序列O的概率:P(O4) 因为HMM是一个状态转移模型,每一个时刻处于一个状态,每个状态可以输出任何的观察值,因此每一种可能的状态转移过程都可能输出这个观察序列。现在我们假设观察序列的长度为5,看一看3个状态的“左-右”模型有哪些可能的状态转移。简单起见,假设模型只能以第一个状态为初始状态,以第三个状态为结束状态: 1→1→1→2→3,1→1→2→2→3,1→1→2→3→3 1→2→2→2→3,1→2→2→3→3,1→2→3→3→3 可能的状态转移过程有6个,如果没有必须开始于第1个状态的要求,可能的状态转移过程会更多。这样我们就需要计算出每一个可能的状态转移过程输出观察序列的概率,然后取其中的最大值作为模型输出该观察序列的概率。例如第一种状态转移过程输出观察序列的概率为: P(O2)=z(O)a1b(O2)a(O3)a2b2(O)a2(O3) 这样计算起来非常复杂,计算量大概是M数量级。这里可以采用 Viterbi优化搜索算法,将计算量减少到M2T数量级 2.训练问题 HMM的训练问题可以表示为在给定一组观察序列O,O(2,…,O)的条件下,如何得到模型λ=(A,B,丌),使得模型输出全部训练样本的总概率最大,一般模型中状态数M 需要预先给定的

41 移到每个状态的概率不同，例如由第 i 个状态转移到第 j 个状态的概率为 ij a 。同时 HMM 开始的第一个状态也是不确定的，有可能开始于任何状态，开始于第 i 个状态的概率可以表示为：  i 。这样一个 HMM 就可以用一个三元组表示：  = (A B, ,π) 其中 A = aij 为一个 M M 的方阵，称为状态转移矩阵， M 为模型的状态数。 B O =bi ( ) 为由一组 M 个概率密度函数构成的矢量， π = i 为 M 维矢量，称为初始概率分布。明显应该有： 1 1 M i i  =  = ， 1 1 M ij j a =  = , ( ) 1 i b d = O O O 现在我们关心的是两个问题：识别问题和训练问题。 1. 识别问题识别问题可表述为如果我们已知一个 HMM 模型  = (A B, ,π) ，如何计算该模型输出待识模式观察序列 O 的概率： P O(  ) 。因为 HMM 是一个状态转移模型，每一个时刻处于一个状态，每个状态可以输出任何的观察值，因此每一种可能的状态转移过程都可能输出这个观察序列。现在我们假设观察序列的长度为 5，看一看 3 个状态的“左-右”模型有哪些可能的状态转移。简单起见，假设模型只能以第一个状态为初始状态，以第三个状态为结束状态： 1 1 1 2 3 → → → → ，1 1 2 2 3 → → → → ，1 1 2 3 3 → → → → 1 2 2 2 3 →→→→ ，1 2 2 3 3 → → → → ，1 2 3 3 3 → → → → 可能的状态转移过程有 6 个，如果没有必须开始于第 1 个状态的要求，可能的状态转移过程会更多。这样我们就需要计算出每一个可能的状态转移过程输出观察序列的概率，然后取其中的最大值作为模型输出该观察序列的概率。例如第一种状态转移过程输出观察序列的概率为： P O b a b a b a b a b 1 1 1 1 11 1 2 11 1 3 12 2 4 23 3 5 (   ) = (O O O O O ) ( ) ( ) ( ) ( ) 这样计算起来非常复杂，计算量大概是 T M 数量级。这里可以采用 Viterbi 优化搜索算法，将计算量减少到 2 M T 数量级。 2. 训练问题 HMM 的训练问题可以表示为在给定一组观察序列 (1 2 ) ( ) ( ) , , , N O O O 的条件下，如何得到模型  = (A B, ,π) ，使得模型输出全部训练样本的总概率最大，一般模型中状态数 M 十需要预先给定的

哈尔滨工业大学：《模式识别》课程教学资源（PPT课件讲稿）第四章 统计分类器及其学习

哈尔滨工业大学：《模式识别》课程教学资源（PPT课件讲稿）第四章统计分类器及其学习