坐标下降法(Coordinate descent)
坐标下降法属于一种非梯度优化的方法,它在每步迭代中沿一个坐标的方向进行搜索,通过循环使用不同的坐标方法来达到目标函数的局部极小值。
相当于每次迭代都只是更新x的一个维度,即把该维度当做变量,剩下的n-1个维度当作常量,通过最小化f(x)来找到该维度对应的新的值。坐标下降法就是通过迭代地构造序列x0,x1,x2,…
来求解问题,即最终点收敛到期望的局部极小值点。通过上述操作,显然有:
f(x0)≥f(x1)≥f(x2)≥…
相比梯度下降法而言,坐标下降法不需要计算目标函数的梯度,在每步迭代中仅需求解一维搜索问题,所以对于某些复杂的问题计算较为简便。但如果目标函数不光滑的话,坐标下降法可能会陷入非驻点。
注意事项
关于坐标下降法,有几点需要注意的:
1.坐标下降的顺序是任意的,不一定非得按照从x1…xn的顺序来,可以是从1到n的任意排列。
2.坐标下降的关键在于一次一个地更新,所有的一起更新有可能会导致不收敛。
3.坐标上升法和坐标下降法的本质一样,只不过目标函数成为求f(x)的极大值了,每次迭代过程min变成max了。
首先介绍一个算法:coordinate-wise minimization
问题的描述:给定一个可微的凸函数,如果在某一点x,使得f(x)在每一个坐标轴上都是最小值,那么f(x)是不是一个全局的最小值。
形式化的描述为:是不是对于所有的d,i都有
这里的代表第i个标准基向量。
答案为成立。
这是因为:
但是问题来了,如果对于凸函数f,若不可微该会怎样呢?
答案为不成立,上面的图片就给出了一个反例。
那么同样的问题,现在,其中g是可微的凸函数,每一个hi都是凸的?
答案为成立。
证明如下,对每一个y
坐标下降(Coordinate descent):
这就意味着,对所有的,其中g是可微的凸函数,每一个hi都是凸的,我们可以使用坐标下降寻求一个最小值,我们从一个最初的猜想开始,对k进行循环:
每一次我们解决了,我们都会使用新的值。
Tseng (2001)的开创性工作证明:对这种f(f在紧集上连续,且f到达了其最小值),的极限值,k=1,2,3….是f的一个最小元(minimizer)。
在实分析领域:
随后收敛与x*( Bolzano-Weierstrass)
收敛于f*( monotoneconvergence)
其中:
坐标下降的顺序是任意的,可以是从1到n的任意排列。
可以在任何地方将单个的坐标替代成坐标块
关键在于一次一个地更新,所有的一起更新有可能会导致不收敛
我们现在讨论一下坐标下降的应用:
线性回归:
令,其中,A有p列:
最小化xi,对所有的xj,j不等于i:
解得:
坐标下降重复这个更新对所有的
对比坐标下降与梯度下降在线性回归中的表现(100个实例,n=100,p=20)
将坐标下降的一圈与梯度下降的一次迭代对比是不是公平呢?是的。
其中r=y-Ax。每一次的坐标更新需要O(n)个操作,其中O(n)去更新r,O(n)去计算,所以一圈就需要O(np),跟梯度下降是一样的。
我们用相同的例子,用梯度下降进行比较,似乎是与计算梯度下降的最优性相违背。
那么坐标下降是一个一阶的方法吗?事实上不是,它使用了比一阶更多的信息。
现在我们再关注一下支持向量机:
SVM对偶中的坐标下降策略:
SMO(Sequentialminimal optimization)算法是两块的坐标下降,使用贪心法选择下一块,而不是用循环。
回调互补松弛条件(complementaryslackness conditions):
v,d,s是原始的系数,截距和松弛,其中,使用任何的(1)中i使得来计算d,利用(1)(2)来计算2.
v,d,s是原始的系数,截距和松弛,其中,使用任何的(1)中i使得来计算d,利用(1)(2)来计算2.
SMO重复下面两步:
选出不满足互补松弛的αi,αj
最小化αi,αj使所有的变量满足条件
第一步使用启发式的方法贪心得寻找αi,αj,第二步使用等式约束。
---------------------
作者:花折泪
来源:****
原文:https://blog.****.net/u013802188/article/details/40476989
版权声明:本文为博主原创文章,转载请附上博文链接!