贝叶斯分类器的学习贝叶斯分类器的学习引言引言贝叶斯分类器中最主要的问题是贝叶斯分类器中最主要的问题是类条件概率密度函数的估计。类条件概率密度函数的估计。问题可以表示为：已有问题可以表示为：已有c个类别的个类别的训练样本集合训练样本集合D1，D2，Dc，求取每个类别的类条件概率密度求取每个类别的类条件概率密度 。概率密度函数的估计方法概率密度函数的估计方法参数估计方法：预先假设每一个类别的概参数估计方法：预先假设每一个类别的概率密度函数的形式，而具体的参数未知；率密度函数的形式，而具体的参数未知；最大似然估计最大似然估计(MLE, Maximum Likelihood Estimation)；贝叶斯估计贝叶斯估计(Bayesian Estimation)。非参数估计方法。非参数估计方法。最大似然估计最大似然估计样本集样本集D中包含中包含n个样本：个样本：x1，x2， , xn，样本都是样本都是独立同分布独立同分布的随机变量的随机变量(，independent identically distributed)。对类条件概率密度函数的函数形式作出假设，对类条件概率密度函数的函数形式作出假设，参数可以表示为参数矢量参数可以表示为参数矢量：似然函数似然函数由独立同分布假设，样本集由独立同分布假设，样本集D出现的概率为：出现的概率为：定义对数似然函数：定义对数似然函数：最大似然估计最大似然估计最大似然估计就是要寻找到一个最最大似然估计就是要寻找到一个最优矢量优矢量 ，使得似然函数，使得似然函数 最大。最大。例例1假设手写数字样本满足正态分布，使用最小假设手写数字样本满足正态分布，使用最小错误率贝叶斯分类器进行识别，采用降维后错误率贝叶斯分类器进行识别，采用降维后的样本；的样本；正态分布正态分布最大似然估计结果为：最大似然估计结果为：混合密度模型混合密度模型一个复杂的概率密度分布函数可以由一个复杂的概率密度分布函数可以由多个简单的密度函数混合构成：多个简单的密度函数混合构成：高斯混合模型高斯混合模型 (Gaussian Mixed Model, GMM)N(,)表示一个高斯分布。表示一个高斯分布。 其中：其中：GMM模型产生的模型产生的2维样本数据维样本数据两个高斯函数混合两个高斯函数混合GMM的训练的训练K值要预先确定；值要预先确定；需要训练的参数：需要训练的参数：aj，j，j；训练算法一般采用训练算法一般采用EM迭代算法。迭代算法。Expectation Maximization AlgorithmGMM参数的参数的EM估计算法估计算法1.设定混合模型数设定混合模型数K，初始化模型参数，初始化模型参数 ，阈值，阈值T，i0；2.用以下公式迭代计算模型参数，直到似然函数变化用以下公式迭代计算模型参数，直到似然函数变化小于小于T为止：为止：隐含隐含Markov模型模型 (Hidden Markov Model, HMM)有一些模式识别系统处理的是与时间相有一些模式识别系统处理的是与时间相关的问题，如语音识别，手势识别，唇关的问题，如语音识别，手势识别，唇读系统等；读系统等；对这类问题采用一个特征矢量序列描述对这类问题采用一个特征矢量序列描述比较方便，这类问题的识别比较方便，这类问题的识别HMM取得取得了很好的效果。了很好的效果。输入语音波形输入语音波形观察序列观察序列信号的特征需要用一个特征矢量的序列信号的特征需要用一个特征矢量的序列来表示：来表示：其中的其中的vi为一个特征矢量，称为一个观为一个特征矢量，称为一个观察值。察值。一阶一阶Markov模型模型一阶一阶Markov模型由模型由M个状态构成，在每个时刻个状态构成，在每个时刻t，模型处于某个状态，模型处于某个状态w(t)，经过，经过T个时刻，产生个时刻，产生出一个长度为出一个长度为T的状态序列的状态序列WT=w(1),w(T)。一阶一阶Markov模型的状态转移模型的状态转移模型在时刻模型在时刻t处于状态处于状态wj的概率完全由的概率完全由t-1时时刻的状态刻的状态wi决定，而且与时刻决定，而且与时刻t无关，即：无关，即：Markov模型的初始状态概率模型的初始状态概率模型初始于状态模型初始于状态wi的概率用的概率用 表示。表示。完整的一阶完整的一阶Markov模型可以用参数模型可以用参数 表示，其中：表示，其中： 一阶一阶Markov模型输出状态序模型输出状态序列的概率列的概率模型输出状态序列的概率可以由初始状态模型输出状态序列的概率可以由初始状态概率与各次状态转移概率相乘得到。概率与各次状态转移概率相乘得到。例如：例如：W5=w1, w1, w3, w1, w2，那么模，那么模型输出该序列的概率为：型输出该序列的概率为：一阶隐含一阶隐含Markov模型模型隐含隐含Markov模型中，状态是不可见的，模型中，状态是不可见的，在每一个时刻在每一个时刻t，模型当前的隐状态可，模型当前的隐状态可以输出一个观察值。以输出一个观察值。隐状态输出的观察值可以是离散值，连隐状态输出的观察值可以是离散值，连续值，也可以是一个矢量。续值，也可以是一个矢量。HMM的工作过程的工作过程HMM的工作原理的工作原理HMM的内部状态转移过程同的内部状态转移过程同Markov模型相同，模型相同，在每次状态转移之后，由该状态输出一个观察在每次状态转移之后，由该状态输出一个观察值，只是状态转移过程无法观察到，只能观察值，只是状态转移过程无法观察到，只能观察到输出的观察值序列。到输出的观察值序列。以离散的以离散的HMM为例，隐状态可能输出的观察值为例，隐状态可能输出的观察值集合为集合为v1, v2, , vK，第，第i个隐状态输出第个隐状态输出第k个观察值的概率为个观察值的概率为bik。例如：例如：T=5时，可能的观察序列时，可能的观察序列V5=v3v2v3v4v1HMM的参数表示的参数表示状态转移矩阵：状态转移矩阵：A，M*M的方阵；的方阵；状态输出概率：状态输出概率：B，M*K的矩阵；的矩阵；初始概率：初始概率：，包括，包括M个元素。个元素。M个状个状态，K个可能的个可能的输出出值。HMM的三个核心问题的三个核心问题估值问题：已有一个估值问题：已有一个HMM模型，其参数，计算这模型，其参数，计算这个模型输出特定的观察序列个模型输出特定的观察序列VT的概率的概率 前向算前向算法，后向算法；法，后向算法；解码问题：已有一个解码问题：已有一个HMM模型，其参数，计算最模型，其参数，计算最有可能输出特定的观察序列有可能输出特定的观察序列VT的隐状态转移序列的隐状态转移序列WT Viterbi算法；算法；学习问题：一个学习问题：一个HMM模型的结构，其参数未知，模型的结构，其参数未知，根据一组训练序列对参数进行训练根据一组训练序列对参数进行训练 Baum-Welch算法；算法；估值问题估值问题一个一个HMM模型产生观察序列模型产生观察序列VT可以由下式计算：可以由下式计算：rmax=MT为为HMM所有可能的状态转移序列数；所有可能的状态转移序列数； 为状态转移序列为状态转移序列 输出观察序列输出观察序列 的概率；的概率； 为为 状态转移序列状态转移序列 发生的概率。发生的概率。 估值问题的计算估值问题的计算计算复杂度：计算复杂度：HMM估值算法的简化估值算法的简化HMM的前向算法的前向算法1.初始化：初始化：2.迭代计算：迭代计算：3.结束输出：结束输出：计算复杂度：计算复杂度：解码问题解码问题解码问题的计算同估值问题的计算类似，最直解码问题的计算同估值问题的计算类似，最直观的思路是遍历所有的可能状态转移序列，取观的思路是遍历所有的可能状态转移序列，取出最大值，计算复杂度为：出最大值，计算复杂度为：O(MTT)。同样存在着优化算法：同样存在着优化算法：Viterbi算法。算法。Viterbi算法1.因为需要回朔最优路径，所以建立一个矩阵因为需要回朔最优路径，所以建立一个矩阵，其元素，其元素 保存第保存第t t步，第步，第i i个状态在第个状态在第t-1t-1步的最优状态。步的最优状态。2.2.初始化：初始化：3.3.迭代计算：迭代计算：4.4.结束：结束：5.5.路径回朔：路径回朔：Viterbi算法图示算法图示“左左-右模型结构右模型结构带跨越的带跨越的“左左-右结构右结构HMM模型模型非参数估计的根本思想非参数估计的根本思想非参数估计的根本思想非参数估计的根本思想令令R是包含样本点是包含样本点x的一个区域，其体积为的一个区域，其体积为V，设有，设有n个训练样本，其中有个训练样本，其中有k落在区域落在区域R中，中，那么可对概率密度作出一个估计：那么可对概率密度作出一个估计：相当于用相当于用R区域内的平均性质来作为一点区域内的平均性质来作为一点x估估计，是一种数据的平滑。计，是一种数据的平滑。Parzen窗方法窗方法定义窗函数定义窗函数概率密度函数的估计概率密度函数的估计超立方体中的样本数：超立方体中的样本数：概率密度估计：概率密度估计：窗函数的形式窗函数的宽度对估计的影响窗函数的宽度对估计的影响识别方法识别方法1.保存每个类别所有的训练样本；保存每个类别所有的训练样本；2.选择窗函数的形式，根据训练样本数选择窗函数的形式，根据训练样本数n选择选择窗函数的窗函数的h宽度；宽度；3.识别时，利用每个类别的训练样本计算待识识别时，利用每个类别的训练样本计算待识别样本别样本x的类条件概率密度：的类条件概率密度：4.采用采用Bayes判别准那么进行分类。判别准那么进行分类。概率神经网络概率神经网络(PNN, Probabilistic Neural Network)PNN的训练算法的训练算法1.begin initialize j = 0; n =训练样本数，训练样本数，aij=02.do j j + 13. normalize :4. train : wjxj5. if then aji16.until j = nPNN分类算法分类算法1.begin initialize k = 0; x 待识模式待识模式2. do k k + 13. 4. if aki = 1 then 5. until k = n6. return 7.end径向基函数网络径向基函数网络(RBF, Radial Basis Function)RBF与与PNN的差异的差异1.PNN模式层神经元数等于训练样本数，而模式层神经元数等于训练样本数，而RBF小小于等于训练样本数；于等于训练样本数；2.PNN模式层到类别层的连接权值恒为模式层到类别层的连接权值恒为1，而，而RBF的需要训练；的需要训练；3.PNN的训练过程简单，只需一步设置即可，而的训练过程简单，只需一步设置即可，而RBF一般需要反复迭代训练；一般需要反复迭代训练；径向基函数网络的训练径向基函数网络的训练RBF的训练的三种方法：的训练的三种方法：1.根据经验选择每个模式层神经元的权值根据经验选择每个模式层神经元的权值wi以及映射函数以及映射函数的宽度的宽度，用最小二乘法计算模式层到类别层的权值，用最小二乘法计算模式层到类别层的权值；2.用聚类的方法设置模式层每个神经元的权值用聚类的方法设置模式层每个神经元的权值wi以及映射以及映射函数的宽度函数的宽度，用最小二乘法计算模式层到类别层的权，用最小二乘法计算模式层到类别层的权值值；3.通过训练样本用误差纠正算法迭代计算各层神经元的权通过训练样本用误差纠正算法迭代计算各层神经元的权值，以及模式层神经元的宽度值，以及模式层神经元的宽度；