第四章 统计分类器及学习 在距离分类器和判别函数分类器中，我们都是把模式看作是维欧氏空间中的一个点，而且统一类别的模式在空间中聚集在一定的区域，不同模式的区域在空间中具有一定的分离性。在本章所讨论的统计分类器中，我们仍然认为模式是欧氏空间中的一个点，但是每一类模式不是分布在空间中的一个确定区域，而是可能分布在整个空间，只不过空间中每一点属于某一类的概率不同，属于这一类的可能性大一些，属于另一类的可能性小一些。我们可以利用这样的性质来建立统计分类器。 4.1 概率论基本知识 本章中我们使用的主要数学工具是概率论，因此先来复习一些概率论的知识。 一、事件 自然界的事件可以分为确定性事件和不确定性事件，确定性和不确定性主要体现在事件的概念和发生上。概念是确定的，发生也是确定的，这是确定事件，例如在标准大气压下，水加热到100度就会开；概念是确定的，发生是不确定的，称为随机事件，例如掷骰子事件；还有一些事件的概念本身就不确定，这类事件称为模糊事件，例如年青人的概念是不确定的，遇到的人是年青人的事件就是模糊事件。 对模糊事件的处理，在模式识别中也占有重要的地位，本章中我们只讨论随机事件。 二、随机变量 随机事件的数量表示称为随机变量。取值为离散的称为离散随机变量，例如掷硬币，只可能出现正、反两面，分别用0和1表示；取值为连续的称为连续随机变量，例如测量物体的长度。 三、频率和概率 设为联系于某个试验的随机事件，试验在相同的条件下重复次，其中次事件发生，则发生的频率为，计为：。 由于事件的随机性，的频率也是一个随机变量。但是当很大时，频率会趋向一个稳定值，称为的概率，即。 四、联合概率和条件概率 联合概率：设是两个随机事件，和同时发生的概率称为联合概率，记为：； 条件概率：在事件发生的条件下，事件发生的概率称为条件概率，记为：； 乘法定理：条件概率与联合概率之间存在如下关系：； 五、概率密度函数 概率分布函数：设为连续型随机变量，定义分布函数； 概率密度函数：如果存在一个非负函数使得成立，则称为的概率密度函数。 同时有：，。 六、全概公式和贝叶斯公式 互不相容事件：如果试验时，若干个随机事件中任何两个事件都不可能同时发生，则称它们是互不相容的。 全概公式：若事件只能与两两不相容的事件之一同时发生，则有：  贝叶斯公式： 当为连续随机变量，为离散随机变量时：。 4.2 最小错误率准则贝叶斯分类器 在下面的讨论中，我们都假设为类别未知样本，用维特征矢量来表示，现有个类别，先验概率和类条件概率已知。我们要根据先验概率和条件概率将分类到某一类中去。  一、最小错误率准则 进行分类就必须要有一个分类准则。由于每一个类别都是分布在整个空间中，因此有可能是任何一个类别，现在我们把它判别为某一类，必然要带来错误，一般来情况下我们希望这种错误的概率越小越好。将分类为类所产生的误判概率为：  要使得判别的错误率最小，也就是寻找一个类别，使得，这就等价于后验概率最大。  然而后验概率我们并不知道，但是可以利用贝叶斯公式转换为先验概率和类条件概率：  由于每一类都相同，对比较大小没有影响，因此可以取判别函数：  判别规则为： 若，则 这就是贝叶斯分类器的判别准则。 下面来看一下的情况，判别准则可以写成：  进一步可以写成：  令：，，则有：  其中：称为似然比，称为似然比的阈值。 例4.1 二、贝叶斯分类器的错误率估计 有了贝叶斯分类器的判决准则后，我们还可以计算出误判的概率。  以一维特征和两类别情况为例来进行说明。错误率是有两部分产生的，一部分是实际应该属于而将误判为类（对应于右面部分），一部分实际应该属于类而被误判为类（对应左面部分）。因此有：  4.3 最小平均风险准则贝叶斯分类器 前面我们以最小错误率为准则建立的贝叶斯分类器，然而对某些问题来说这样的准则并不适合。这是因为每次误判所带来的后果并不一样，有一些类别被误判的后果非常严重，而另一些类别被误判的后果却并不严重，例如对于癌症诊断问题，如果一个癌症患者被误判为正常，那么后果非常严重，有可能耽误治疗；而一个正常人被误诊为患有癌症，后果并不很严重，随着进一步的诊断，可以改变这种误判。 下面我们就来介绍一种依据最小平均风险准则的贝叶斯分类器。 设由个类别，。首先我们需要根据实际问题定义一组数据，表示将类的样本误判为类的代价，这应该是一个的矩阵。然后我们可以用下面的公式计算将未知模式判别为类的平均风险：  其中为用加权的后验概率。因为当我们将分类为时，它有可能是类的任何一类，因此总的平均风险就是对加权后的后验概率求和。我们的判决准则应该是选择一个平均风险最小的类别作为输出的决策类别。因此可以构造判别函数：。 现在的问题同最小错误率准则一样，我们并不知道后验概率，而是已知先验概率和条件概率，因此我们还需要使用贝叶斯公式将后验概率转换为先验概率：  因为是公共项，对比较大小没有影响，因此可以舍去：  现在还是看一下两类问题的情况： 将判别为类的平均风险为：  将判别为类的平均风险为：  当时，判别为类；当时，判别为类。以第一种情况进行推导：  即：  定义似然比：，定义阈值：。 这样就可以得到最小平均风险准则下的贝叶斯判决条件： 若，则； 若，则。 例4.2 4.4 贝叶斯分类器的学习 贝叶斯分类器的工作原理非常简单，完全是根据待识模式对各个类别的后验概率来分类的，判别为后验概率最大的类别。后验概率可以根据贝叶斯公式转化为先验概率和类条件概率。下面我们来研究贝叶斯分类器的学习问题，也就是说如何通过训练样本集来得到和的问题。 对于一个具体问题来说，和我们并不知道，而是已知各个类别的训练样本集合：，。表示第个类别的第个训练样本，第类共有个训练样本。 一般来说比较容易得到，因为类别数是有限的，可以通过统计多个样本得到各个类别出现的几率，用它来近似概率，比如可以根据大量病例统计出在普通人中癌症的患病率，也可以根据先验知识来确定，比如掷两枚样币同时出现正面的概率。 然而类条件概率的获得却往往是一个比较困难的事情。如果是离散型的时候，问题相对来说还比较简单一些，如果样本量足够多的话，可以分别统计出各个类别中出现某个特征矢量的几率。然而当为一个连续型的特征是矢量时，问题就会非常复杂。因为这种情况下我们要找到的是条件概率密度函数，而概率密度函数可以是任意形式，而我们的训练样本的数量毕竟是有限的，因此不可能很好的拟合出概率密度函数。因此我们往往采用一些简化的办法。 这些简化办法中最重要的一点就是要对所求的概率密度函数的形式作出一定的限制，假设概率密度函数符合某种概率模型，而概率模型是可以用一组参数来描述的，这样我们就可以使用数理统计的方法，利用训练样本来估计这组参数，有了模型参数，就可以得到概率密度数。下面介绍几种常用的概率模型及其估计方法。 一、高斯模型（Gaussian Model ） 高斯模型也称为正态分布模型，是一种最常见的概率模型，自然界中很多物理现象都符合正态分布假设，比如说我们对一个物理量的测量。维的正态分布函数可以表示为：  正态分布函数完全可以有两个参数来描述： 均值矢量：； 协方差矩阵： 正态分布的参数的估计方法非常简单，根据数理统计的理论，虽然均值和协方差都需要求一个数学期望，也就是当数量趋近于无穷大时求平均，但是当样本量足够大时可以用有限样本的算术平均来近似，即：   例4.3 二、混合高斯模型 （Mixed Gaussian Model, GMM） 正态分布模型的训练和使用非常简单，然而对于一个实际问题来说，特征的分布函数并不一定满足正态分布，其分布形式可能非常复杂，并且往往呈现一种多峰情况，如下图所示。这时再用高斯模型来描述它的概率密度函数就会产生很大的误差。为了描述这些复杂的分布函数，我们可以采用简单函数的线性组合来逼近复杂函数。GMM模型就是用多个高斯函数的线性组合来描述复杂的分布函数。 我们可以用来表示一个高斯分布函数，为均值矢量，为协方差矩阵。那么一个GMM概率密度函数可以表示为： ，其中 上述GMM模型是由各高斯模型线性组合而成，为组合系数。例如下图就是由两个高斯函数组合而成：   GMM分布函数的训练要比单个高斯模型复杂得多，这里需要训练的参数有，和，而值是要预先确定的。GMM的训练一般采用EM迭代算法(Expectation Maximization Algorithm)，称为期望最大化算法。 三、隐含Markov模型 （Hidden Markov Model, HMM） 在实际问题中，有时我们遇到的识别对象是连续信号，例如语音信号。下图分别显示了三个元音的一段采样信号，’a’, ‘o’, ‘e’。 这样的连续信号，如果还是用特征矢量来描述，无法反映出信号之间的时间相关性，往往需要用一个随机过程来描述。对于连续信号，一般是采用分段来处理的，例如以512点为一段，称为一帧信号。在每一帧信号中抽取出特征，构成特征矢量，例如语音信号中可以抽取Fourier变换系数，信号通过零点的次数等等作为这一帧的特征。这样一段信号就可以用一个特征矢量的序列来表示，一般称为观察序列：  其中的称为观察值，是一个特征矢量。 如果我们要对这样的模式构造贝叶斯分类器，也要知道每个类别的条件概率，然而对于这样的观察序列，显然无法用高斯模型或高斯混合模型来描述，需要有一个新的模型—隐含Markov模型来描述。对每一个类别建立一个HMM，有这样一个HMM可以计算出观察序列在每个类别的条件概率，再结合类的先验概率，就可以构造出一个贝叶斯分类器。 下面简单介绍一下HMM的基本知识，在随机过程中，每一时刻的取值只与之前的过程有关，而与之后的过程无关，这样的过程称为Markov过程，只与前一时刻的值有关，则称为一阶Markov过程。    HMM的模型结构可以多种多样，下面先以语音识别中常用“左-右”模型为例介绍一下。  每一个HMM都是由若干个隐状态构成的，隐状态之间可以进行转移，所以HMM是一个状态转移模型。这里表示的三个隐状态的HMM，每一个状态在下一时刻可以转移到下一个状态，也可以转移到自身状态。 隐状态是不可见的，我们所能够看见的是观察序列，每一个隐状态可以输出任何观察值，只不过输出每个观察值得概率不同。例如在时刻，模型处于第个状态，这时第个状态输出的概率可以表示为：。同时第个状态在时刻有可能转移到多个状态，转移到每个状态的概率不同，例如由第个状态转移到第个状态的概率为。 同时HMM开始的第一个状态也是不确定的，有可能开始于任何状态，开始于第个状态的概率可以表示为：。 这样一个HMM就可以用一个三元组表示：  其中为一个的方阵，称为状态转移矩阵，为模型的状态数。为由一组个概率密度函数构成的矢量，为维矢量，称为初始概率分布。明显应该有： ，, 现在我们关心的是两个问题：识别问题和训练问题。 识别问题 识别问题可表述为如果我们已知一个HMM模型，如何计算该模型输出待识模式观察序列的概率：。 因为HMM是一个状态转移模型，每一个时刻处于一个状态，每个状态可以输出任何的观察值，因此每一种可能的状态转移过程都可能输出这个观察序列。现在我们假设观察序列的长度为5，看一看3个状态的“左-右”模型有哪些可能的状态转移。简单起见，假设模型只能以第一个状态为初始状态，以第三个状态为结束状态： ，， ，， 可能的状态转移过程有6个，如果没有必须开始于第1个状态的要求，可能的状态转移过程会更多。这样我们就需要计算出每一个可能的状态转移过程输出观察序列的概率，然后取其中的最大值作为模型输出该观察序列的概率。例如第一种状态转移过程输出观察序列的概率为：  这样计算起来非常复杂，计算量大概是数量级。这里可以采用Viterbi优化搜索算法，将计算量减少到数量级。 训练问题 HMM的训练问题可以表示为在给定一组观察序列的条件下，如何得到模型，使得模型输出全部训练样本的总概率最大，一般模型中状态数十需要预先给定的。 这个问题也是一个复杂的问题，需要采用迭代算法Baum-Welch算法，实际上也是一种EM算法来求解。 同时其中中每个元素的概率函数形式也需要选择，可以选择高斯函数，高斯混合函数等等。 模型结构问题 对于识别问题来说，模型结构也需要选择，前面介绍的“左-右”模型只是其中的一种，下面再给出两种结构，带有跨越的“左-右”模型和全连接模型。