设计个人网站,新品上市的营销方案,境外网站做网站涉黄,12333公共招聘网I. 牛顿迭代法给定一个复杂的非线性函数f(x)#xff0c;希望求它的最小值#xff0c;我们一般可以这样做#xff0c;假定它足够光滑#xff0c;那么它的最小值也就是它的极小值点#xff0c;满足f′(x0)0#xff0c;然后可以转化为求方程f′(x)0的根了。非线性方程的根我…I. 牛顿迭代法给定一个复杂的非线性函数f(x)希望求它的最小值我们一般可以这样做假定它足够光滑那么它的最小值也就是它的极小值点满足f′(x0)0然后可以转化为求方程f′(x)0的根了。非线性方程的根我们有个牛顿法所以 然而这种做法脱离了几何意义不能让我们窥探到更多的秘密。我们宁可使用如下的思路在yf(x)的xxn这一点处我们可以用一条近似的曲线来逼近原函数如果近似的曲线容易求最小值那么我们就可以用这个近似的曲线求得的最小值来近似代替原来曲线的最小值 显然对近似曲线的要求是1、跟真实曲线在某种程度上近似一般而言要求至少具有一阶的近似度2、要有极小值点并且极小值点容易求解。 这样我们很自然可以选择“切抛物线”来近似用二阶泰勒展开近似原曲线 该抛物线具有二阶的精度。对于这条抛物线来说极值点是(-b/(2*a)) 所以我们重新得到了牛顿法的迭代公式 如果f(x)足够光滑并且在全局只有一个极值点那么牛顿法将会是快速收敛的速度指数增长然而真实的函数并没有这么理想因此它的缺点就暴露出来了 1、需要求二阶导数有些函数求二阶导数之后就相当复杂了2、因为f″(xn)的大小不定所以g(x)开口方向不定我们无法确定最后得到的结果究竟是极大值还是极小值。 II. 梯度下降 这两个缺点在很多问题上都是致命性的因此为了解决这两个问题我们放弃二阶精度即去掉f″(xn)改为一个固定的正数1/h 这条近似曲线只有一阶精度但是同时也去掉了二阶导数的计算并且保证了这是一条开口向上的抛物线因此通过它来迭代至少可以保证最后会收敛到一个极小值至少是局部最小值。上述g(x)的最小值点为 所以我们得到迭代公式 对于高维空间就是 这就是著名的梯度下降法了。当然它本身存在很多问题但很多改进的算法都是围绕着它来展开如随机梯度下降等等。 这里我们将梯度下降法理解为近似抛物线来逼近得到的结果既然这样子看读者应该也会想到凭啥我一定要用抛物线来逼近用其他曲线来逼近不可以吗当然可以对于很多问题来说梯度下降法还有可能把问题复杂化也就是说抛物线失效了这时候我们就要考虑其他形式的逼近了。事实上其他逼近方案基本都被称为EM算法恰好就只排除掉了系出同源的梯度下降法实在让人不解。 根据一阶泰勒展开对于一个可微函数对于任意的x有 $ f(x\alpha p)f(x)\alpha * g(x)*po(\alpha *\left| p \right|) $ 其中$ g(x)*p \left| g(x) \right| *\left| p \right| *cos\theta $ ,$\theta$是两向量之间的夹角,p是搜索方向 当 $\theta $ 为180度得时候$g(x)*p$ 可取到最小值即为下降最快的方向。所以负梯度方向为函数f(x)下降最快的方向x为未知参数对X进行迭代更新 如果f(x)是凸函数则局部最优解就是全局最优解。 V. K-Means K-Means聚类很容易理解就是已知N个点的坐标xi,i1,…,N然后想办法将这堆点分为K类每个类有一个聚类中心cj,j1,…,K很自然地一个点所属的类别就是跟它最近的那个聚类中心cj所代表的类别这里的距离定义为欧式距离。所以K-Means聚类的主要任务就是求聚类中心cj。我们当然希望每个聚类中心正好就在类别的“中心”了用函数来表示出来就是希望下述函数L最小(kmeans目标函数是平方损失函数) 其中min操作保证了每个点只属于离它最近的那一类。如果直接用梯度下降法优化L那么将会遇到很大困难不过这倒不是因为min操作难以求导而是因为这是一个NP的问题理论收敛时间随着N成指数增长。这时我们也是用EM算法的这时候EM算法表现为1、随机选K个点作为初始聚类中心2、已知K个聚类中心的前提下算出各个点分别属于哪一类然后用同一类的所有点的平均坐标来作为新的聚类中心。 这种方法迭代几次基本就能够收敛了那么这样做的理由又在哪儿呢 聚类问题给定数据点给定分类数目求出个类中心使得所有点到距离该点最近的类中心的距离的平方和最小。 含隐变量的最大似然问题给定数据点给定分类数目考虑如下生成模型 模型中为隐变量表示簇的类别。 这个式子的直观意义是这样的对于某个将要生成的点和类别号如果不满足“到中心的距离小于等于到其他中心的距离”的话则不生成这个点。如果满足的话则取值就是这个“最近的”类中心的编号如果有多个则均等概率随机取一个以高斯的概率密度在这个类中心周围生成点。 用EM算法解这个含隐变量的最大似然问题就等价于用K-means算法解原聚类问题。 Q函数是完全数据的对数似然函数关于在给定X和参数$\mu$的情况下对隐变量Z的条件概率的期望em算法通过求解对数似然函数的下界的极大值逼近求解对数似然函数的极大值。 这和K-means算法中根据当前分配的样本点求新的聚类中心的操作是一样的。 k-means是GMM的简化而不是特例。 共同点都是使用交替优化算法要优化的参数分为两组固定一组优化另一组。 GMM是先固定模型参数优化 然后固定优化。k-means是先固定(聚类中心)优化聚类赋值然后固定聚类赋值优化。 k-means对GMM的简化有 模型中混合权重相等各个成分的协方差相等且固定为单位矩阵的倍数分配给各个component的方式由基于概率变为winner-take-all方式的 hard 赋值。kmeans中某样本点和模型中某个子成分如果该样本点与子成分的中心距离最小则以高斯的概率密度在中心点周围生成这个点否则就不生成这个点。而GMM中每个子成分都有可能生成该样本点概率值为子成分的系数所以说GMM是更为flexible的model由于大量的简化使得k-means算法收敛速度快于GMM并且通常使用k-means对GMM进行初始化。 转自 http://spaces.ac.cn/archives/4277/ https://www.zhihu.com/question/49972233转载于:https://www.cnblogs.com/ljygoodgoodstudydaydayup/p/7274943.html
