收敛率概述 (Overview of Rates of Convergence).pdfVIP

12/9/2016 收敛率概述 (Overview of Rates of Convergence) 收敛率概述 (Overview of Rates of Convergence) 2016-12-09 史春奇， 王雅清 AI2ML人工智能to机器学习 在算法优化过程中经常会遇到收敛(Convergence)问题， 尤其目前的深度学习盛行，  如何设计更高效的收敛算法， 是个极大的挑战。 而如何评价收敛的快慢呢？ 这就是收敛率的计算， 在这里我们主要概述一下什么是收 敛率。 因为这个概念用的不是很广泛， 大家都知道是什么含义， 但是如何计算，却不 很清楚。 一， 常见的收敛方法 1.1 Bisection方法 每次数列的限制到收敛点的上一次距离的一般距离之内。   /s?__biz MzIzMjU1NTg3Ng tempkey bNYtZPo2q2uo1ngJLOLo71AA3aCvWsCFMVElu2UO3UoGOaLvolku%2FsX7L2QF… 1/16 12/9/2016 收敛率概述 (Overview of Rates of Convergence) 这样如果把这种与收敛点的距离记为误差， 那么误差是2的负的幂次方运算。 如果对边界值取对数后， 我们发现这个误差的对数是k的线性函数。 /s?__biz MzIzMjU1NTg3Ng tempkey bNYtZPo2q2uo1ngJLOLo71AA3aCvWsCFMVElu2UO3UoGOaLvolku%2FsX7L2QF… 2/16 12/9/2016 收敛率概述 (Overview of Rates of Convergence) 1.2 Fix Point 方法 另外一种常见情况是Fix Point的方式。 其实我们常见的牛顿法和这个固定点方法是类 似的。对于这种情况我们认为两个点之间是有个函数关系式的。 或者说， 存在一个函 数g(x)的曲线， 上一个点的值就是下个点的输入。 等价于这个曲线与y=x的正斜线之 间有个关系。 如下图所示。 那么会有两种情况的收敛到两个线的交点。 /s?__biz MzIzMjU1NTg3Ng tempkey bNYtZPo2q2uo1ngJLOLo71AA3aCvWsCFMVElu2UO3UoGOaLvolku%2FsX7L2QF… 3/16 12/9/2016 收敛率概述 (Overview of Rates of Convergence) 在这种情况下， 我们会有这个线的斜率的绝对值必须小于1。 为什么会有这个结论 呢？ 因为如果斜率绝对值大于1后， 就不会收敛了。 如下图所示， 当斜率大于1后， 越来越发散， 就不会收敛了。 因此对于斜率的结论是 成立。   那么， 我们连续缩放到k=1的时候， 就有一个幂指数出现了。 并且它的底是 一个小于1的值。 这时候，我们对这个表达式取对数。 /s?__biz MzIzMjU1NTg3Ng tempkey bNYtZPo2q2uo1ngJLOLo71AA3aCvWsCFMVElu2UO3UoGOaLvolku%2FsX7L2QF… 4/16 12/9/2016 收敛率概述 (Overview of Rates of Convergence) 也有类似结论就是， 这个误差的对数是K的线性函数。 1.3 Newton方法 牛顿法就是通过切线与横轴的交点找到第二个点。然后就能反复找到曲线与横轴的交 点。 根据牛顿法可以得到它的迭代公式如下， 如果我们把这个迭代公式改写一下， 可以看 出牛顿法其实是Fixed Point点法的一个特例。  我们知道固定点法最后是要求g(x)=x，  就是g(x)曲线和y=x斜线的交点。  而在这种要求下， 同样可以得到， 牛顿法最后的点 /s?__biz MzIzMjU1NTg3Ng tempkey bNYtZPo2q2uo1ngJLOLo71AA3aCvWsCFMVElu2UO3UoGOaLvolku%2FsX7L2QF… 5/16 12/9/2016 收敛率概述 (Overview of Rates of Convergence) 是f(x)曲线与横轴的交点。