最大似然估计和贝叶斯参数估计ppt课件.ppt

Chapter 3: 最大似然估计和贝叶斯参数估计,要点：,重点掌握最大似然估计和贝叶斯参数估计的原理; 熟练掌握主成分分析和Fisher线性分析; 掌握隐马尔可夫模型; 了解维数问题;,贝叶斯框架下的数据收集 在以下条件下我们可以设计一个可选择的分类器 :P(i) (先验)P(x | i) (类条件密度)不幸的是，我们极少能够完整的得到这些信息!从一个传统的样本中设计一个分类器 先验估计不成问题 对类条件密度的估计存在两个问题：1）样本对于类条件估计太少了；2） 特征空间维数太大了，计算复杂度太高。,1,3.1 引 言,如果可以将类条件密度参数化，则可以显著降低难度。例如：P(x | i)的正态性P(x | i) N( i, i)用两个参数表示 将概率密度估计问题转化为参数估计问题。估计最大似然估计 (ML) 和贝叶斯估计；结果通常很接近, 但是方法本质是不同的。,最大似然估计将参数看作是确定的量，只是其值是未知! 通过最大化所观察的样本概率得到最优的参数用分析方法。贝叶斯方法把参数当成服从某种先验概率分布的随机变量，对样本进行观测的过程，就是把先验概率密度转化成为后验概率密度，使得对于每个新样本，后验概率密度函数在待估参数的真实值附近形成最大尖峰。在在参数估计完后，两种方法都用后验概率P(i | x)表示分类准则!,当样本数目增加时，收敛性质会更好； 比其他可选择的技术更加简单 。假设有c类样本，并且 1）每个样本集的样本都是独立同分布的随机变量；2）P(x | j) 形式已知但参数未知，例如P(x | j) N( j, j)；3）记 P(x | j) P (x | j, j)，其中,3.2 最大似然估计,最大似然估计的优点：,3.2.1 基本原理,使用训练样本提供的信息估计 = (1, 2, , c), 每个 i (i = 1, 2, , c) 只和每一类相关 。假定D包括n个样本, x1, x2, xn的最大似然估计是通过定义最大化P(D | )的值 “值与实际观察中的训练样本最相符”,2,2,最优估计 令 = (1, 2, , p)t 并令 为梯度算子 the gradient operator我们定义 l() 为对数似然函数：l() = ln P(D | )新问题陈述:求解 为使对数似然最大的值,对数似然函数l()显然是依赖于样本集D, 有：最优求解条件如下:,令:,来求解.,P(xk | ) N(, )(样本从一组多变量正态分布中提取) = ，因此:的最大似然估计必须满足:,2,3.2.3 高斯情况： 未知,乘 并且重新排序, 我们得到: 即训练样本的算术平均值!结论: 如果P(xk | j) (j = 1, 2, , c)被假定为d维特征空间中的高斯分布; 然后我们能够估计向量 = (1, 2, , c)t 从而得到最优分类!,2,未知 和 ，对于单样本xk = (1, 2) = (, 2),3.2.3 高斯情况： 和 均未知,对于全部样本，最后得到:联合公式 (1) 和 (2), 得到如下结果:,2,2的最大似然估计是有偏的 （渐进无偏估计） 的一个基本的无偏估计是:,2,3.2.4 偏差估计,模型错误会怎么样？,达不到最优！,在最大似然估计中 被假定为固定值在贝叶斯估计中 是随机变量目标: 计算 P(i | x, D) 假设样本为D，贝叶斯方程可以写成 ：,3.3贝叶斯估计,3.3.1 类条件密度,因此，核心工作就是要估计,先验概率通常可以事先获得，因此每个样本只依赖于所属的类，有：,故：,即：只要在每类中，独立计算就可以确定x的类别。,假设 的形式已知, 参数的值未知，因此条件概率密度 的函数形式是知道的；假设参数是随机变量，先验概率密度函数p()已知，利用贝叶斯公式可以计算后验概率密度函数p( | D) ；希望后验概率密度函数p( | D) 在的真实值附件有非常显著的尖峰，则可以使用后验密度p( | D) 估计 ；,4,3.3.2 参数的分布,注意到,4,3.3.2 参数的分布,如果p( | D) 在某个值 附件有非常显著的尖峰，则,即: 如果条件概率密度具有一个已知的形式，则利用已有的训练样本，就能够通过p( | D) 对p(x | D) 进行估计。,单变量情形的 p( | D),3.4 贝叶斯参数估计: 高斯过程,复制密度,贝叶斯学习,结论:,单变量情形的 p(x|D),多变量情形:,复制密度,多变量学习,3.5 贝叶斯参数估计：一般理论,(x | D) 的计算可推广于所有能参数化未知密度的情况中，基本假设如下:假定 p(x | ) 的形式未知，但是的值未知。被假定为满足一个已知的先验密度 P()其余的 的信息 包含在集合D中，其中D是由n维随机变量x1, x2, , xn组成的集合，它们服从于概率密度函数p(x)。,基本的问题是:计算先验密度p( | D) ，然后 推导出 p(x | D)。,问题:p(x | D)是否能收敛到p(x)，计算复杂度如何？,递归贝叶斯学习,该过程称为参数估计的递归贝叶斯方法，一种增量学习方法。,例1：递归贝叶斯学习,例1：递归贝叶斯学习,例1: Bayes vs. ML,唯一性问题,(x|q) 是唯一的： 后验概率序列 p(q|Dn) 收敛到 delta 函数；只要训练样本足够多，则 p(x|q) 能唯一确定q 。在某些情况下，不同 q 值会产生同一个 p(x|q) 。 p(q|Dn) 将在 q 附近产生峰值，这时不管p(x|q) 是否唯一， p(x|Dn)总会收敛到p(x) 。因此不确定性客观存在。,最大似然估计和贝叶斯参数估计的区别,最大似然估计 贝叶斯参数估计计算复杂度 微分 多重积分可理解性 确定易理解 不确定不易理解先验信息的信任程度 不准确 准确例如 p(x|q) 与初始假设一致 与初始假设不一致,分类误差,贝叶斯错误或不可分错误，例如 P(x | i) ；模型错误；估计错误，训练样本个数有限产生。,Gibbs 算法,在较弱的假设条件下，Gibbs算法的误差概率至多是贝叶斯最优分类器的两倍。,统计量任何样本集的函数；充分统计量即是一个样本集 D 的函数s ，其中 s 包含了有助于估计参数 q的所有所有信息，即 p(D|s, q) 与 q无关；如果q 是随机变量，则,3.6 充分统计量,反过来也成立。,因式分解定理：,一个关于参数q 的统计量s是充分统计量当且仅当概率分布函数 P(D|q) 能够写成乘积形式：P(D|q) = g(s, q) h(D) 其中 g(.,.) 和h(.)是两个函数。,例子：多维高斯分布,证明：必要性,注意到 对于一个给定的样本，只有一个s与之对应。,充分性：,核密度（Kernel density）,把 P(D|q) 分解成 g(s,q)h(D) 不是唯一的：如果f(s) 是一个函数, g(s,q)=f(s)g(s,q) 和 h(D) = h(D)/f(s) 也是等价的分解；这种二义性可以用定义核密度函数的方法来得到消除：,例子：多维高斯分布,核密度与参数估计,对于最大似然估计情形，只需最大化 g(s,q)，因为： P(D|q) = g(s, q) h(D) 对于贝叶斯估计情形：如果我们对q的先验概率不确定, p(q) 通常选择均匀分布, 则p(q|D) 几乎等于核密度；如果p(x|q) 可辩识时, g(s,q) 通常在某个值处有明显的尖峰，并且如果p(q) 在该值处连续并且非零, 则p(q|D) 将趋近核密度函数。,充分统计量与指数族函数,分类问题通常涉及50或100维以上的特征. 分类精度取决于维数和训练样本的数量考虑有相同协方差矩阵的两组多维向量情况:,3.7 维数问题,如果它们的先验概率相同，则贝叶斯误差概率为：,如果特征是独立的，则有:最有用的特征是两类均值之间的距离大于标准方差的那些特征;在实际观察中我们发现，当特征个数增加到某个临界点后会导致更糟糕的结果而不是好的结果: 我们的模型有误，或者由于训练样本个数有限导致分布估计不精确，等等。,可分性与特征维数,计算复杂度,分类的计算复杂度,分类阶段比学习阶段简单。,训练样本不足时的方法,降维重新设计特征提取模块;选择现有特征的子集;将几个特征组合在一起;假设各个类的协方差矩阵都相同,将全部数据都归到一起;寻找协方差矩阵 S 更好的估计;如果有合理的先验估计 S0, 则可以用如下的伪贝叶斯估计 ; 设法将S0对角化: 阈值化或假设特征之间统计独立;,过拟合的概念,正确的拟合思想是；一开始用高阶的多项式曲线来拟合，然后依次去掉高阶项来逐渐简化模型，获得更光滑的结果。,缩并(Regularized Discriminant Analysis),Best Representative Point,Projection Along a Line,Best Projection to a Line Through the Sample Mean,Best Representative Direction,Principal Component Analysis (PCA),Concept of Fisher Linear Discriminant,Fisher Linear Discriminant Analysis,Fisher Linear Discriminant Analysis,Fisher Linear Discriminant Analysis,Fisher Linear Discriminant Analysis for Multivariate Normal,Concept of Multidimensional Discriminant Analysis,Multiple Discriminant Analysis,Multiple Discriminant Analysis,Multiple Discriminant Analysis,Multiple Discriminant Analysis,Expectation-Maximization (EM),Finding the maximum-likelihood estimate of the parameters of an underlying distribution from a given data set when the data is incomplete or has missing valuesTwo main applicationsWhen the data indeed has missing valuesWhen optimizing the likelihood function is analytically intractable but when the likelihood function can be simplified by assuming the existence of and values for additional but missing (or hidden) parameters,Expectation-Maximization (EM),Full sample D = x1, . . ., xnxk = xkg, xkb Separate individual features into Dg and Db D is the union of Dg and DbForm the function,Expectation-Maximization (EM),begin initialize q0, T, i 0 do i i + 1 E step: Compute Q(q; q i) M step: q i+1 arg maxq Q(q,q i) until Q(q i+1;q i)-Q(q i;q i-1) T return q qi+1end,Expectation-Maximization (EM),Example: 2D Model,Example: 2D Model,Example: 2D Model,Example: 2D Model,Generalized Expectation-Maximization (GEM),Instead of maximizing Q(q; q i), we find some q i+1 such thatQ(q i+1;q i)Q(q ;q i) and is also guaranteed to convergeConvergence will not as rapidOffers great freedom to choose computationally simpler stepse.g., using maximum-likelihood value of unknown values, if they lead to a greater likelihood,Hidden Markov Model (HMM),Used for problems of making a series of decisionse.g., speech or gesture recognitionProblem states at time t are influenced directly by a state at t-1More reference:L. A. Rabiner and B. W. Juang, Fundamentals of Speech Recognition, Prentice-Hall, 1993, Chapter 6.,First Order Markov Models,First Order Hidden Markov Models,Hidden Markov Model Probabilities,Hidden Markov Model Computation,Evaluation problemGiven aij and bjk, determine P(VT|q)Decoding problemGiven VT, determine the most likely sequence of hidden states that lead to VTLearning problemGiven training observations of visible symbols and the coarse structure but not the probabilities, determine aij and bjk,Evaluation,HMM Forward,HMM Forward and Trellis,HMM Forward,HMM Backward,HMM Backward,Example 3: Hidden Markov Model,Example 3: Hidden Markov Model,Example 3: Hidden Markov Model,Left-to-Right Models for Speech,HMM Decoding,Problem of Local Optimization,This decoding algorithm depends only on the single previous time step, not the full sequenceNot guarantee that the path is indeed allowable,HMM Decoding,Example 4: HMM Decoding,Forward-Backward Algorithm,Determines model parameters, aij and bjk, from an ensemble of training samplesAn instance of a generalized expectation-maximization algorithmNo known method for the optimal or most likely set of parameters from data,Probability of Transition,Improved Estimate for aij,Improved Estimate for bjk,Forward-Backward Algorithm(Baum-Welch Algorithm),成分分析与辨别式 组合特征从而降低特征空间的维数 线形组合通常比较容易计算和处理 将高维数据投影到一个低维空间里去 使用两种分类方法寻找理想一点的线性传递 PCA (主成份分析) “在最小均方误差意义下的数据的最优表示的映射”MDA (多类判别分析) “在最小均方误差意义下的数据的最有分类的映射”,8,隐藏马尔可夫模型 : 马尔可夫链目标: 建立一系列决策 Processes that unfold in time, states at time t are influenced by a state at time t-1应用: 语音识别, 姿势识别,部分语音追踪和DNA 排序 所有无记忆的随机过程 T = (1), (2), (3), , (T) 为状态序列我们可以得到 6 = 1, 4, 2, 2, 1, 4 这个系统能够再现不同阶段的状态而且不是所有的状态都需要巡视,10,一阶马尔可夫模型所有序列的结果都由传递概率表示 P(j(t + 1) | i (t) = aij,10,10, = (aij, T)P(T | ) = a14 . a42 . a22 . a21 . a14 . P(1) = i)例子: 语音识别“production of spoken words”Production of the word: “模式” 由音素表示/p/ /a/ /tt/ /er/ /n/ / ( / = silent state) Transitions from /p/ to /a/, /a/ to /tt/, /tt/ to er/, /er/ to /n/ and /n/ to a silent state,10,隐性马尔可夫模型 (HMM)可视状态与隐藏状态的相互影响 bjk= 1 对所有 j 当 bjk=P(Vk(t) | j(t).这个模型存在三个问题 估计问题 解码问题学习问题,估计问题该模型生产出一列可视状态VT是有可能的，即:当每个r指示T个隐藏状态所组成的一组特殊序列,使用方程 (1) 和 (2), 我们能够写成:例子: 令 1, 2, 3 为隐藏状态; v1, v2, v3 为可视状态 V3 = v1, v2, v3 为可视状态序列 P(v1, v2, v3) = P(1).P(v1 | 1).P(2 | 1).P(v2 | 2).P(3 | 2).P(v3 | 3)+ (总的可能项数= 所有的可能性 (33= 27) 的情况 !),第一概率:第二概率:P(v1, v2, v3) = P(2).P(v1 | 2).P(3 | 2).P(v2 | 3).P(1 | 3).P(v3 | 1) + +因此:,1(t = 1),2(t = 2),3(t = 3),v1,v2,v3,2(t = 1),1(t = 3),3(t = 2),v3,v2,v1,解码问题 (最优状态序列)假设VT为可视状态序列，解码问题就是找出最有可能的隐藏状态序列 .这个问题用数学的方式表示如下 :找出单个的“最佳”状态序列 (隐藏状态),注意最后的总和消失了，因为我们只想找到唯一的一个最佳情况,当: = ,A,B = P(1) = ) (最初的状态概率) A = aij = P(t+1) = j | (t) = i) B = bjk = P(v(t) = k | (t) = j)在之前的例子中，这些计算与最佳路径的选择一致:1(t = 1),2(t = 2),3(t = 3), 2(t = 1),3(t = 2),1(t = 3)3(t = 1),1(t = 2),2(t = 3), 3(t = 1),2(t = 2),1(t = 3) 2(t = 1),1(t = 2),3(t = 3),学习问题 (参数估计) 第三个问题涉及到找出一种方法调整模型参数 = ,A,B使之满足一个特定的最优标准。我们需要找出最好的模型。 然后最大化可视序列的概率 :我们使用一个迭代的过程比如Baum-Welch或者Gradient来得到一个最优解,