《变分与AdaBoost》由会员分享,可在线阅读,更多相关《变分与AdaBoost(100页珍藏版)》请在金锄头文库上搜索。
1、变分原理 & AdaBoost北京10月机器学习班 邹博 2014年12月28日1从贝叶斯推断说起o如果我们有一组观测数据 D,如何推断产生这些数据的模型 m?o考虑参数化模型m由模型的类别(如高斯分布,伽马分布,多项式分布等)与 模型的参数共同决定。2模型的选择o假设M为所有可能的模型集合(包括不同类别),那么选择3计算p(m|D)o根据贝叶斯公式op(m):模型的先验概率op(D|m):数据的似然op(D):数据的出现概率证据4先验概率p(m)o先验:贝叶斯规则倾向于选择能解释数据的最简单模型nOccam剃刀原理5进一步计算o似然o注:参数的后验概率6模型参数的估计o给出一组观测数据D,我
2、们总是能够通过估计参数来推测模型。7后验概率的估计o通常情况,取后验概率最大的参数值为估计值。o根据贝叶斯公式,参数后验概率为op(D)为归一化常数(normalizing constant)8通过估计参数来估计单点积分值o从经典的统计学角度看,概率是相对频率的,是真实世界的客观属性。因而每个模型被选择的概率是一样的,因而p()为常数。此时问题转化为:o这便是极大似然法(ML,Maximum Likelihood)。o从贝叶斯学派的角度看,每一个模型都有一个先验概率p(),但先验概率需事先给定。此时问题转化为:o这便是极大后验估计(MAP,Maximum A Posteriori)9目标函数带
3、积分o使用训练样本预测数据的概率密度:假设D与D条件独立,o新观测样本D的隐藏变量(hiddenvariable)x的后验分布10参数估计o考虑一个问题:有一组观测数据D,并且已知模型的形式,求参数与隐变量(或不可观测变量)Z=Z1,Z2.Zn的后验分布:P(Z|D)。11估计o能不能在误差允许的范围内,用更简单、容易理解(tractable)的数学形式Q(Z)来近似P(Z|D),即12两个随机变量的差异o如何度量Q(Z)与P(Z|D)之间的差异性(dissimilarity)13随机分布的距离o描述两个随机分布之间距离的度量,可以使用“相对熵”,或者称为Kullback-Leibler散度。
4、14相对熵o两个概率密度函数为p(x)和q(x)之间的相对熵定义为15带入K相对熵公式,推导oQ、P的KL散度为:o对数证据:o证据的下界16极大化下界o由于对数证据logP(D)被相应的Q所固定,为了使KL散度最小,则只要极大化L(Q)。通过选择合适的Q,使L(Q)便于计算和求极值。这样就可以得到后验P(Z|D)的近似解析表达式和证据(log evidence)的下界L(Q),又称为变分自由能(variational free energy)。17平均场理论(Mean Field Method)o数学上说,平均场的适用范围只能是完全图,或者说系统结构是well-mixed,在这种情况下,系统
5、中的任何一个个体以等可能接触其他个体。反观物理,平均场与其说是一种方法,不如说是一种思想。其实统计物理的研究目的就是期望对宏观的热力学现象给予合理的微观理论。物理学家坚信,即便不满足完全图的假设,但既然这种“局部”到“整体”的作用得以实现,那么个体之间的局部作用相较于“全局”的作用是可以忽略不计的。o根据平均场理论,变分分布Q(Z)可以通过参数和潜在变量的划分(partition)因式分解,比如将Z划分为Z1ZM.18泛函o设对于(某一函数集合内的)任意一个函数y(x),有另一个数J(y)与之对应,则称J(y)为y(x)的泛函。o泛函可以看成是函数概念的推广。这里的函数集合,即泛函的定义域,通
6、常要求y(x)满足一定的边界条件,并且具有连续的二阶导数这样的y(x)称为可取函数。19EulerLagrange方程20关于变分o什么是变分?o变分的研究范畴是什么?它的作用是什么?n下述第22页第58页来自:oHongxin Zhang,2007-06-14,State Key Lab of CAD&CG, ZJU2122232425262728293031323334353637383940414243444546474849505152535455565758混合高斯分布o假设现在有独立同分布(iid)的训练样本X符合下列混合高斯分布o如何求解高斯混合分布的三组参数59步骤一:选择无信
7、息先验分布60各个分布的说明oSymDir(.)表示K维对称Dirichlet分布;它是多项式分布(multinomial)的共轭先验分布。oW(.)表示Wishart分布;对一个多元高斯分布(multivariate Gaussian distribution),它是协方差矩阵的共轭先验。oMult(.)表示多项分布;多项式分布是二项式分布的推广,表示在一个K维向量中只有一项为1,其它都为0.oN(.)为高斯分布,在这里特别指多元高斯分布。61参数62各分步之间的关系:贝叶斯网络63贝叶斯网络的说明o小正方形表示不变的超参数,如0,0等;圆圈表示随机变量,如;圆圈内的值为已知量。其中K,D表
8、示K、D维的向量,D,D表示D*D的矩阵,单个K表示一个有K个值的多项分布变量;波浪线和一个开关表示变量xi通过一个K维向量zi来选择其他传入的变量(k,k)。64根据贝叶斯网络的性质o联合概率密度函数65每个因子o每个因子是:66步骤三:计算边缘密度(VB-marginal)67整理o两边取对数o归一化68计算的概率密度69Dirichlet分布o两边取对数oq()是Dirichlet分布.70Gaussian-Wishart分布71Gaussian-Wishart分布72迭代收敛73VBEM算法的步骤74提升方法o一个概念如果存在一个多项式的学习算法能够学习它,并且正确率很高,那么,这个概
9、念是强可学习的;o一个概念如果存在一个多项式的学习算法能够学习它,并且学习的正确率仅比随机猜测略好,那么,这个概念是弱可学习的;o强可学习与弱可学习是等价的。o在学习中,如果已经发现了“弱学习算法”,能否将他提升为“强学习算法”。75Adaboosto设训练数据集T=(x1,y1), (x2,y2)(xN,yN)o初始化训练数据的权值分布76Adaboost:对于m=1,2,Mo使用具有权值分布Dm的训练数据集学习,得到基本分类器o计算Gm(x)在训练数据集上的分类误差率o计算Gm(x)的系数77Adaboost:对于m=1,2,Mo更新训练数据集的权值分布o这里,Zm是规范化因子o它使Dm+
10、1成为一个概率分布78Adaboosto构建基本分类器的线性组合o得到最终分类器79误差上限o当G(xi)yi时,yi*f(xi)0,是上式最小的G(x)由下式得到:o其中,93权值的计算o求权值:o将G*(x)带入:o求导,得到94分类错误率o分类错误率为:95权值的更新o由模型o以及权值o可以方便的得到:96权值和错误率的关键解释o事实上,根据Adaboost的构造过程,权值调整公式为:o二者做除,得到o从而:97总结oAdaBoost的训练误差是以指数速率下降的oAdaBoost算法不需要事先知道下界,AdaBoost具有自适应性,它能适应若分类器格子的训练误差率。(“适应”Adaptive的由来)98参考文献oPattern Recognition and Machine Learning Chapter 10, Bishop M, Springer-Verlag, 2006oVariational Algorithms for approximate Bayesian Inference, Matthew J. Beal, 2003oHongxin Zhang,2007-06-14,State Key Lab of CAD&CG, ZJUo钱伟长,格林函数和变分法在电磁场和电磁波计算中的应用,上海大学出版社99 感谢大家!恳请大家批评指正!100