下载  >  人工智能  >  机器学习  > GMM与EM算法

GMM与EM算法 评分:

PDF文档对应于网易公开课上吴恩达教授主讲的机器学习(网址:http://open.163.com/special/opencourse/machinelearning.html)中高斯混合模型(GMM)与EM算法相关内容,补充了Jessen不等式的证明,以及GMM的似然函数最大化的参数的公式推导
如需转载请注明CSDN博客网址:htp:/blog.csdn. net/qq30091945 ∑{=}(0)-)( ∑{ 由于∑中=,那么我们必须利用拉格朗日乘数法来求解ψ。因此构造如下函 数 (9a)=∑∑{=}p+a(-∑.) 那么分别对a求偏导有: ∑ 那么我们可以得到: 带入上式有: ∑∑∑{=}∑{"=}a∑a 那么有: 如∑ 实际上,我们可以从上得知,如果()是已知的,那么高斯混合模型的最大似 然估计变得几乎与我们在估计高斯判别分析模型的参数时所具有的相同,除了这 里(正在起到类标签的作用。 然而,在我们的密度估计问题中,(是未知的。我们可以做什么? EM算法是一种迭代算法,有两个主要步骤。应用于我们的问题,在E步骤 如需转载请注明CSDN博客网址:htp:/ /blog. csdn. net/qq3001945 中,它试图“猜测(的值。在M步骤中,它根据我们的猜测更新模型的参数。 由于在M步骤中我们假设第一部分中的猜测是止确的,因此最大化变得容易。 下面是高斯混合模型的EM算法的伪代码: ∑ ∑Q(-) ∑ 在E步骤中,给定(并使用当前设置的参数最后结合贝叶斯准则,我们计 算得到参数(的后验概率: () |() 在这里(|0-=2)由样木在均值为,协方差矩阵为的高斯分 布上的概率给出;同时, 少)由φ给出。在E步骤中计算的)的值表 小我们对(的“软”猜测。 此外,通过将M步骤中的参数更新与我们确切知道O时的公式进行对比, 你可以发现它们是相同的,除了没有表明每个数据点来白哪个高斯分布的指小函 数{(=},而我们现在将其改为O) EM算法也让人联想到K- means聚类算法,除了代替“硬”聚类分配(),我 如需转载请注明CSDN博客网址:htp:/ blog. csdn. net/qq_30091945 们改为使用“软”赋值()。与K- means算法类似,它也容易陷入局部最优解, 因此在儿个不同的初始参数上重新初始化可能是一个好主意 很明显,EM算法具有非常自然的解释—一反复尝试猜测未知的;但是它 是如何产生的,我们可以对它做出任何保证,例如它是如何收敛的?因此接下来 我们将描述EM算法一般表示,这将使我们能够轻松地将其应用于其他还有隐含 变量的估计问题,也公提供给我们能够提供收敛的保证 不等式 为了更好地理解EM算法的原理,我们必须对子FM算法中运用广泛的 Jessen 不等式进行详细推导 设是一个定义域为实数集的函数。回想一下,如果y∈“()2,那么 是一个凸函数。当对于的向量输入,这是广义的条件,它的海森(hesi) 矩阵是半定,即≥。如果y∈"()>,那么我们说是严格凸函数 (在向量值情况下,相应的表述为必须是严格的半正定的,记为 那么 Jessen不等式可以这样表述为:是凸函数,即∨∈"()>,假定 是随机变量,那么有[()≥()。而且,如果是严格凸函数时,那 么当且仅当(=()=时,[(刀()(即当是常数时),其中 ()代表随机变量的数学期望。其实这是 Jessen不等式的一般形式,Jesn 不等式的加权形式为:Y∈"() ∈R =,那么 2()22 恒成立。同理,如果当是个凹函数时, Jessen不等式的 般形式为:∈“()s,假定是随机变量,那么有[()≤( 其加权形式为:∈"()≤ R+ 那么 恒成立。下面对利川数学归纳法来证明 Jessen不等式 如需转载请注明CSDN博客网址:htp:/ blog. csdn. net/qq_30091945 我们以是凸函数为例来证明 Jessen不等式的加权形式。证明过程如下: 那么()=()=()恒成立 时 ,由于"()≥,那么根据不等式性质我们有: )恒成立 当≥时,假设当=时∑()5(∑恒成立,那么只需 证明,当 时,∑()5∑ 那么 ,∈R∑ 时,显然有 ∑()-()∑() 综合1)、2)、3)有, Jessen不等式恒成立。同理可证是凹函数时的 Jessen 不等式恒成立。 f Fx)……÷-x f(b fEx E 为了更好地理解 Jessen不等式,我们来看上面的函数图。在图中,是由实 线表小的凸函数。是随机变量,各有0.5的概率取得变量和变量。因此, 如需转载请注明CSDN博客网址:htp:/ blog. csdn. net/qq_30091945 的期望值由和之间的中点给出。我们还可以看到(),()和([]) 在轴上的值。[(刀现在是()和()之间的中点。从我们的例子中,我 们看到,因为是凸函数,[()≥()恒成立 因此, Jessen不等式也可以这样理解,当指定函数是凸函数时,函数值的加 权平均大于等于自变量的加权平均后对应的函数值;当指定函数是凹函数时,函 数值的加权平均小于等于自变量的加权平均后对应的函数值。 算法 假设我们有一个评估问遇,其中有一个训练集{"…(当由个独立的样 本组成。我们希望利川数据来你拟合模型()的参数,其中似然函数为 ()=∑ 但是,明显寻找参数极大似然估计是难的。这里(是隐式随机变量:通常情 况下,若果知道了(),那么极大似然估计就会很容易。 在这种情况下,EM算法给出了一种有效的估计最大值似然的方法。最大化 (O)明显可能很困难,我们的策略是重复构造一个上确界E-step),然后优化这 个上下限M-step) 对于每一个,令是的函数,且有∑()=,()≥。那么根据 Jessen 不等式,我们有 ∑()=∑∑(0o) ≥∑∑() 具体地说,() 是凹函数,因为∈R+"() 现在,对于任何组分布,公式(3)为()给出了一个下界。有很多可 能的选择。我们应该用哪一种?如果我们有一些目前想猜测的参数θ,很自然地 让似然函数在θ处的下界变小是我们的目标。即我们将使上面的不等式在θ处等 号成立。 如需转载请注明CSDN博客网址:htp:/ blog. csdn.netq30091945 为了一个特殊θ是的上界变小,我们的推动过程中需要涉及 Jessen不等式去 等的条件。为了使等号成立,我们知道期望是常变量时将会带来高效率。即我们 要求: 对于不依赖于的常数,只要满足()x(0)0)如下条件即可。实际 上,由于∑(()=,那么我们有 ∑("0)() 因此,我们只是将设置为()的后验分布,(是的条件概率,且被O参数 化 现在,对于的选择,式(1)给出了我们试图最大化的对数似然的下界,这是 执行这两个步骤。上述就是EM算法的两个过程,具体流程如下所示。反复 E步骤。算法的M步骤中,最大化式(1)的参数θ,从而获得个新参数 ∑∑(" 我们怎么知道EM是否收敛?假设)和)连续两次迭代的参数。接下来 我们将证明()≤(0+),这也将解释EM为什么总是单调提高对数似函数。 这个结果的关键在于我们对的选择。具休米说,在EM算法的迭代过程中,参 数将从开始0),那么我们令(0)=(0)我们在前面看到,这个 选择确保了 Jensen不等式能够去取等。因此, 如需转载请注明CSDN博客网址:htp:/blog.csdn. net/qq30091945 ()≥∑∑( ) ( 那么,令0),B以)。为了得到式(2,我们令 ∑∑( 因此,在O)处,该公式必须等于或大于在()处的。 因此,EM是的似然函数单调收敛。在我们的EM算法的编写,我们说我们 运行它直到收敛。鉴于我们刚刚展示的结果,一个合理的收敛性测试检査是连续 迭代之问(⊙)之间的误差是否小于一些容差参数,如果(⊙)改进过慢,那么我 们说EM算法收敛。 那么如果我们定义如下函数: )=∑∑ 从之前推导可以得知((0)2)(0)。那么EM算法也可以看成通过不断迭代, (0)不断逼证()的过程,其中E步骤是最大化(自我检查,然后M步 骡就是最大化9。具体示意图如下所示 )固定e,调整Q(2使下界2 上升至与L(θ)在此点0处相等, 然后固定Q(z),调整θ使下界J (zQ)达到最大值,此时为新的 再固定θ,调整Q(z)…直 倒到收敛到似然函数L()的最大 值处的9 416 如需转载请注明CSDN博客网址:htp:/ blog. csdn. net/qq_30091945 四再看高斯混合模型 根据我们对EM算法的一般定义,计我们回到我们在高斯混合中拟合参数, 4和∑的旧例子上 E步骤很简单。按照上面的算法推导,我们简单地令, 这里 ()=)表示在分布下(=的概率 接下来是M步骤,我们需要最大化参数p∑。首先我们化简似然函数。其 过程如下: (2)=>∑(0)()0 ∑∑(=) bb/sd (()x( ∑∑)() 那么首先最大化,(42)对求偏导有: ∑∑ =∑2(0)- 那么令上式等于0有 S((

...展开详情
2018-08-12 上传 大小:902KB
举报 收藏 (3)
分享