变分与AdaBoost

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