科学网 › 标签 › 定义域

标签: 定义域

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

[转载]（EM算法）The EM Algorithm: xuehuazhao 2012-5-19 16:23; EM是我一直想深入学习的算法之一，第一次听说是在NLP课中的HMM那一节，为了解决HMM的参数估计问题，使用了EM算法。在之后的MT中的词对齐中也用到了。在Mitchell的书中也提到EM可以用于贝叶斯网络中。下面主要介绍EM的整个推导过程。 1. Jensen不等式回顾优化理论中的一些概念。设f是定义域为实数的函数，如果对于所有的实数x，，那么f是凸函数。当x是向量时，如果其hessian矩阵H是半正定的（），那么f是凸函数。如果或者，那么称f是严格凸函数。 Jensen不等式表述如下：如果f是凸函数，X是随机变量，那么特别地，如果f是严格凸函数，那么当且仅当，也就是说X是常量。这里我们将简写为。如果用图表示会很清晰：图中，实线f是凸函数，X是随机变量，有0.5的概率是a，有0.5的概率是b。（就像掷硬币一样）。X的期望值就是a和b的中值了，图中可以看到成立。当f是（严格）凹函数当且仅当-f是（严格）凸函数。 Jensen不等式应用于凹函数时，不等号方向反向，也就是。 2. EM算法给定的训练样本是，样例间独立，我们想找到每个样例隐含的类别z，能使得p(x,z)最大。p(x,z)的最大似然估计如下：第一步是对极大似然取对数，第二步是对每个样例的每个可能类别z求联合分布概率和。但是直接求一般比较困难，因为有隐藏变量z存在，但是一般确定了z后，求解就容易了。 EM是一种解决存在隐含变量优化问题的有效方法。虽然不能直接最大化，我们可以不断地建立的下界（E步），然后优化下界（M步）。这句话比较抽象，看下面的。对于每一个样例i，让表示该样例隐含变量z的某种分布，满足的条件是。（如果z是连续性的，那么是概率密度函数，需要将求和符号换做积分符号）。比如要将班上学生聚类，假设隐藏变量z是身高，那么就是连续的高斯分布。如果按照隐藏变量是男女，那么就是伯努利分布了。可以由前面阐述的内容得到下面的公式：（1）到（2）比较直接，就是分子分母同乘以一个相等的函数。（2）到（3）利用了Jensen不等式，考虑到是凹函数（二阶导数小于0），而且就是的期望（回想期望公式中的Lazy Statistician规则）设Y是随机变量X的函数（g是连续函数），那么（1） X是离散型随机变量，它的分布律为，k=1,2,…。若绝对收敛，则有（2） X是连续型随机变量，它的概率密度为，若绝对收敛，则有对应于上述问题，Y是，X是，是，g是到的映射。这样解释了式子（2）中的期望，再根据凹函数时的Jensen不等式：可以得到（3）。这个过程可以看作是对求了下界。对于的选择，有多种可能，那种更好的？假设已经给定，那么的值就决定于和了。我们可以通过调整这两个概率使下界不断上升，以逼近的真实值，那么什么时候算是调整好了呢？当不等式变成等式时，说明我们调整后的概率能够等价于了。按照这个思路，我们要找到等式成立的条件。根据Jensen不等式，要想让等式成立，需要让随机变量变成常数值，这里得到： c为常数，不依赖于。对此式子做进一步推导，我们知道，那么也就有，（多个等式分子分母相加不变，这个认为每个样例的两个概率比值都是c），那么有下式：至此，我们推出了在固定其他参数后，的计算公式就是后验概率，解决了如何选择的问题。这一步就是E步，建立的下界。接下来的M步，就是在给定后，调整，去极大化的下界（在固定后，下界还可以调整的更大）。那么一般的EM算法的步骤如下：循环重复直到收敛 { （E步）对于每一个i，计算（M步）计算那么究竟怎么确保EM收敛？假定和是EM第t次和t+1次迭代后的结果。如果我们证明了，也就是说极大似然估计单调增加，那么最终我们会到达最大似然估计的最大值。下面来证明，选定后，我们得到E步这一步保证了在给定时，Jensen不等式中的等式成立，也就是然后进行M步，固定，并将视作变量，对上面的求导后，得到，这样经过一些推导会有以下式子成立：解释第（4）步，得到时，只是最大化，也就是的下界，而没有使等式成立，等式成立只有是在固定，并按E步得到时才能成立。况且根据我们前面得到的下式，对于所有的和都成立第（5）步利用了M步的定义，M步就是将调整到，使得下界最大化。因此（5）成立，（6）是之前的等式结果。这样就证明了会单调增加。一种收敛方法是不再变化，还有一种就是变化幅度很小。再次解释一下（4）、（5）、（6）。首先（4）对所有的参数都满足，而其等式成立条件只是在固定，并调整好Q时成立，而第（4）步只是固定Q，调整，不能保证等式一定成立。（4）到（5）就是M步的定义，（5）到（6）是前面E步所保证等式成立条件。也就是说E步会将下界拉到与一个特定值（这里）一样的高度，而此时发现下界仍然可以上升，因此经过M步后，下界又被拉升，但达不到与另外一个特定值一样的高度，之后E步又将下界拉到与这个特定值一样的高度，重复下去，直到最大值。如果我们定义从前面的推导中我们知道，EM可以看作是J的坐标上升法，E步固定，优化，M步固定优化。 3. 重新审视混合高斯模型我们已经知道了EM的精髓和推导过程，再次审视一下混合高斯模型。之前提到的混合高斯模型的参数和计算公式都是根据很多假定得出的，有些没有说明来由。为了简单，这里在M步只给出和的推导方法。 E步很简单，按照一般EM公式得到：简单解释就是每个样例i的隐含类别为j的概率可以通过后验概率计算得到。在M步中，我们需要在固定后最大化最大似然估计，也就是这是将的k种情况展开后的样子，未知参数和。固定和，对求导得等于0时，得到这就是我们之前模型中的的更新公式。然后推导的更新公式。看之前得到的在和确定后，分子上面的一串都是常数了，实际上需要优化的公式是：需要知道的是，还需要满足一定的约束条件就是。这个优化问题我们很熟悉了，直接构造拉格朗日乘子。还有一点就是，但这一点会在得到的公式里自动满足。求导得，等于0，得到也就是说再次使用，得到这样就神奇地得到了。那么就顺势得到M步中的更新公式：的推导也类似，不过稍微复杂一些，毕竟是矩阵。结果在之前的混合高斯模型中已经给出。 4. 总结如果将样本看作观察值，潜在类别看作是隐藏变量，那么聚类问题也就是参数估计问题，只不过聚类问题中参数分为隐含类别变量和其他参数，这犹如在x-y坐标系中找一个曲线的极值，然而曲线函数不能直接求导，因此什么梯度下降方法就不适用了。但固定一个变量后，另外一个可以通过求导得到，因此可以使用坐标上升法，一次固定一个变量，对另外的求极值，最后逐步逼近极值。对应到EM上，E步估计隐含变量，M步估计其他参数，交替将极值推向最大。EM中还有“硬”指定和“软”指定的概念，“软”指定看似更为合理，但计算量要大，“硬”指定在某些场合如K-means中更为实用（要是保持一个样本点到其他所有中心的概率，就会很麻烦）。另外，EM的收敛性证明方法确实很牛，能够利用log的凹函数性质，还能够想到利用创造下界，拉平函数下界，优化下界的方法来逐步逼近极大值。而且每一步迭代都能保证是单调的。最重要的是证明的数学公式非常精妙，硬是分子分母都乘以z的概率变成期望来套上Jensen不等式，前人都是怎么想到的。在Mitchell的Machine Learning书中也举了一个EM应用的例子，明白地说就是将班上学生的身高都放在一起，要求聚成两个类。这些身高可以看作是男生身高的高斯分布和女生身高的高斯分布组成。因此变成了如何估计每个样例是男生还是女生，然后在确定男女生情况下，如何估计均值和方差，里面也给出了公式，有兴趣可以参考。; 2835 次阅读|0 个评论

说课（4）--（泛函分析）: 热度 15 gfcao 2011-10-23 16:17; 距离空间中的点集是研究空间上算子（或变换）的基础，我们在微积分中研究函数的性质时首先需要搞清楚函数的定义域。在单变量情形，函数的定义域常常是开区间、闭区间，而在实分析中，函数的定义域可以是任意的开集、闭集甚至可测集。对于函数的连续性研究来说，开集、闭集是两个最基本的概念，这两个概念是建立在集合的内点、极限点（聚点）概念之上的。在一般的线性距离空间中，我们可以类似有限维空间定义“内点”、“极限点”、“开邻域”、“开集”、“闭集”、“稠密集”、“疏朗集”、“离散点集”、“孤立点集”等概念，他们的定义与有限维空间如出一辙，没有本质的差异，讲授者完全可以简略带过。然而无限维空间中出现了一些新的现象，空间中的有界闭集不再具有有限维空间中有界闭集的美好特征，而这些特征是这些集合上函数或变换的许多重要性质得以成立的基础。如所周知，闭区间上的连续函数具有很好的性质，“介质定理”、“最大最小值原理”为保证方程解的存在性甚至数值求解发挥了举足轻重的作用。这些定理的证明强烈依赖于闭区间的重要特征，这就是区间套定理、聚点原理或有限覆盖原理。在有限维空间中，这些定理是相互等价的。在无限维空间中这些定理是否依然成立呢？这是决定相应的算子是否具有某种性质或方程是否有解的关键。可以证明，闭球套定理在完备线性距离空间上是成立的，事实上空间的完备性与闭球套定理是等价的。但令人遗憾的是，我们可以轻而易举地找到无限维空间中的有界闭集，在这个集合上，有限覆盖原理、聚点原理等不再成立。例如在 l 2 ={x={x n } n=1 ∞ | ∑ n |x n | 2 ∞ } 中定义距离为 : d(x,y)= 1/2 l 2 中的单位闭球指的是： B(0,1)= {x={x n } n=1 ∞ | ∑ n |x n | 2 ≤ 1} 显然它是一个有界闭集，取 B(0,1) 中特殊的点列 x (k) ={x n (k) } 为： X k (k) =1, x n (k) =0,(n ≠ k) ，不难验证 d(x (k) ,x (j) ) ≡ 2 1/2 (k ≠ j) 。显然 {x (k) } 没有聚点（或极限点）。如果以 B(0,1) 中每个点为球心， 1/3 为半径作开球，则可以得到 B(0,1) 的一个开覆盖，显而易见，从这个开覆盖中不可能找到 B(0,1) 的有限子覆盖。有限覆盖原理与聚点原理是如此重要，以至于许多方程解的存在性强烈依赖于他们，而在无限维空间中的有界闭集上，这些定理是不成立的，我们考察有界闭集上的算子或方程就未见得有意义了。这就是说，我们需要定义一种新的集合，使得在这些集合上有限覆盖原理或聚点原理能够成立，于是紧集、列紧集、完全有界集的概念应运而生。所谓紧集即使得有限覆盖原理成立的集合，所谓列紧集即聚点原理成立的集合。这里需要注意的是，在距离空间中，极限点与聚点是等价的概念，所以一般教科书中以序列的收敛性来定义列紧性，即：如果集合 M 中任何序列都有收敛的子列，则称 M 为列紧集，这也是这类集合之所以叫列紧集（序列紧）的原因。在开覆盖中，有一类特殊的覆盖，即用半径为ε的球覆盖某个集合，实际上在构造具体的开覆盖时常采用这种覆盖，假如对任意正数ε，存在有限个半径为ε的开球将某个集合覆盖住，则称该集合为完全有界集。列紧集、完全有界集、紧集是什么关系？弄清楚它们的关系需要费一番功夫，由自列紧性证明紧性是其中最困难的一步，但证明的思想不仅不怪异，而且很值得借鉴，在很多重要定理的证明中都可以发现类似的思想，老师最好帮助学生对这个证明作详细的剖析。证明的第一步是如何根据列紧集的可分性从开覆盖中寻找可数的子覆盖，这是比较体现智慧的一步，但也是可分集合中常规的一步。第二步是证明可数开覆盖必有有限的子覆盖，证明这个结论的最好方法是反证法，限于篇幅，这里不对细节作详细分析。; 个人分类: 教育点滴|13186 次阅读|28 个评论

10.5 PM 基础: lvlisuccess 2011-10-6 15:19; 函数：f（x）是变量x的实函数，即在其定义域内，任一x值都有一个实数f（x）与之对应。泛函：传统上，泛函通常是指一种定义域为函数，而值域为实数的函数。换句话说，就是从函数组成的一个向量空间到实数的一个映射。也就是说他的输入为函数，而输出为实数。泛函的应用可以追溯到变分法，那里通常需要寻找一个函数来最小化某个特定泛函。在物理学上，寻找某个能量泛函的最小系统状态是泛函的一个重要应用。泛函：N（y）是函数y（x）的泛函，即在其定义域内，任一函数y（x）都有一个实数N（y）与之对应。变分命题：寻找y（x）使得N（y）取极值。变分命题的实质是求泛函的极值问题。变分方法：设使泛函取得极值的函数y（x）存在，通过变分法求得这个极值函数y（x）所需满足的微分方程。对函数而言，一阶导数为零的极值条件给出的是相对极大或相对极小，而不是绝对极大或绝对极小。在变分法中，泛函的极值条件给出的也只是相对极大或相对极小。导数为零只是必要条件。泛函变分问题的一般求解步骤：1）从物理上建立泛函及其条件；2）通过泛函变分，利用变分法基本预备定理求得欧拉方程；3）在边界条件下求解欧拉方程，即微分方程求解。变分法与欧拉方程：1、变分法与欧拉方程代表同一物理问题；2、欧拉方程求解和从变分法求数值近似解效果一样。3、并不是所有的微分方程都能找到相对应的泛函问题。利用变分原理，是的包括预报场和所有的观测资料进行全局调整，从而也使得分析场达到统计意义上的最优。在变分方法中，观测算子可以是非线性的，从而使得直接同化非常规资料变为可能。同时，它可以全局调整，克服了最优插值在实际应用中的“资料选择”问题。变分方法90年代开始在少数国家实现了业务化，并且成为了目前客观分析方法的一个发展主流——assimilation。拉普拉斯说过“知道了绝对准确的方程和绝对准确的初值，就知道了未来的全部演化”。无独有偶，近代气象学的鼻祖——皮叶克尼斯也说“根据某一时刻实测大气状态和运动，通过描述大气运动规律的微分方程，来计算将来某一时刻的相应大气状态和运动。从原则上说，大气的未来的状态完全由大气的初始状态和边界条件决定 ”。人们在这些思想下，拼命地去寻找并企图建立一个“绝对准确的方程”（模式）和“ 绝对准确的初值”。随机性在自然界扮演着和决定性同样重要的角色，人们不但要去认识具有必然性的规律，还要去认识具有偶然性的规律。为了对现实中的现象描述，科学家们都会根据相应的物理规律，建立起相应的数学模型。然后进行相应的输入（输入可以是实际观测的，也可以是人为的“控制”资料），通过模型运算后，然后对输出分析，从而对其物理现象进一步研究。这是现今最常见的科学研究方法之一。那么有一个输入，通过模式的运算，就有一个相应得输出，似乎是属于牛顿力学的决定论的范畴。但是，在实际的工作中，我们会发现，这种方法其实是充满着不确定性的，因为：1）对于实测资料的输入而言，也是有很多不确定性的。这个也就是我们同化中经常提到的仪器误差和代表性误差。 2）从计算数学的角度来看，模式在运算求解的过程中，会引入计算上的不确定性。也就是我们常说的计算误差和截断误差。 3）我们所建立的模型是不完美的。我们所建立的模型只能说是对现实情况的一个近似。虽然有时候，我们的模式是一个很好的近似，比如牛顿第二定律对低速运动的描述。但是，很多时候我们模式所不能很好地描述部分却对我们所关心现象有着很大的影响，比如在气候模式中的非绝热项。所以，企图从决定论方面来描述我们的现实生活中的现象是行不通的。我们需要根据一种新的理论来建立模型。这种理论不但可以考虑物理规律，而且要考虑其不确定性，从某种最优的意义上最大地除去其噪音（即不确定性或者误差）提取信号。不但要对输出值进行分析，还要对输出值的质量进行分析，这种理论就是估计理论。这种估计理论首先承认了系统本身的决定性，承认物理规律，认为系统是由一定的物理规律来决定其基本的时空状态，而引入这个决定性的规律就是我们的模式。同时，估计理论还以前所未有的高度来对待系统的随机性，认为不可能具有完全决定性的系统，在一定范围内又呈现随机性。就像吸引子一样，所有的解最终会跑到吸引子里，但是吸引子内又表现为完全随机的。理论要满足人们的需要，必须通过一定具体形式来表现。气象上，有两颗新星正闪耀着估计理论的光芒——集合预报和资料同化。集合预报就是从在一定误差范围内的一组初值出发，这组初值代表了初始时刻的大气状态的概率分布，然后用模式去预报，得到一个预报值的集合，即未来某时刻的大气状态的概论分布。而同化就是利用一切有用信息，尽可能准确地估计出某一时刻的大气出现的概论分布。应该说，集合预报和资料同化其实是一个问题的两个方面。它们都是在给定观测和预报模式的情况下，去描述大气状态的概论分布及其发展。它们都有一个共同的理论基础—— 估计理论。气象里的同化是借客观分析和初始化的躯体诞生的。所以，它最初被认为一种插值方法，后来有被认为是对大气状态的一个最优估计。其实，人们从最优估计的理论上来理解同化时，同化的灵魂已经开始唤醒，但是，还没有完全醒来。因为，从估计理论上来讲，最优不过是概率分布中概率密度最大的地方。但是，现在人们知道，小概率事件不一定是不发生。何况，如果概率分布是一个双峰状态时，假如另一峰仅仅比主峰低一点，我们的仅仅去求“最优”时，其实漏了一个很重要的可能出现的状态。那么，要完全体现估计理论，使得同化的灵魂完全复苏，同化需要一个新的躯体——基于集合的同化。; 3223 次阅读|0 个评论

留数定理与情感: 热度 1 positron 2011-5-22 22:49; 爱上物理的标志是会把所有看到的物体看成方程式；爱上某人的标志是会把所有看到的异性看成那个人。推论一：爱上物理的标志是能把遇到的所有问题当做物理问题处理；推论二：爱上数学的标志是能把遇到的所有问题当做数学问题处理。中午吃饭的路上大脑里突然冒出那两句话，之后又得到后面的两个推论，下午复习留数时突然发现可以用留数定理“证明”之。简述如下：假设全体异性构成一个函数，且此函数可以展开成洛朗级数，每一项代表一个人，而自己钟情的那个是其中的-1次幂项。函数定义域内存在一个单极点，极点必须是唯一的单极点，原因不必说，而且对应着自己钟情的人，因为此处感情指数会变为无穷大。看人，然后在大脑中形成图像，可以视为对函数做包含单极点的围道积分，根据留数定理，除了-1次幂项，其他项对积分无贡献，所以大脑中只会形成一个人的图像。由上，第二句得证。而此证明过程本身证明了推论二，进而，所有命题成立。证毕！; 个人分类: 娱乐一下|4063 次阅读|1 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 定义域

相关帖子

相关日志

关闭安全验证