coordinate descent是什么意思?

  统计/机器学习 最优化    浏览次数:2869        分享
0

machine learning优化里的coordinate descent是什么意思?

 

xxax   2018-09-26 06:12



   3个回答 
8

坐标轴下降法顾名思义,是沿着坐标轴的方向去下降,这和梯度下降不同。梯度下降是沿着梯度的负方向下降。不过梯度下降和坐标轴下降的共性就都是迭代法,通过启发式的方式一步步迭代求解函数的最小值。

    坐标轴下降法的数学依据主要是这个结论(此处不做证明):一个可微的凸目标函数$J(\theta)$, 其中$\theta$是$nx\times 1$的向量,即有$n$个维度。如果在某一点$\bar \theta$,使得$J(\theta)$在每一个坐标轴$\bar \theta_i$,($i = 1,2,\cdots,n$)上都是最小值,那么$J(\bar \theta_i)$就是一个全局的最小值。

    于是我们的优化目标就是在$\theta$的$n$个坐标轴上(或者说向量的方向上)对损失函数做迭代的下降,当所有的坐标轴上的$\theta_i$($i = 1,2,\cdots,n$)都达到收敛时,我们的损失函数最小,此时的$\theta$即为我们要求的结果。

    下面我们看看具体的算法过程:

    1. 首先,我们把$\theta$向量随机取一个初值。记为$\theta^{(0)}$ ,上面的括号里面的数字代表我们迭代的轮数,当前初始轮数为0.

    2. 对于第$k$轮的迭代。我们从$\theta^{(k)}_1$开始,到$\theta^{(k)}_n$为止,依次求$\theta^{(k)}_i$。$\theta^{(k)}_i$的表达式如下:

    $$\theta^{(k)}_i = \text{argmin}_{\theta_i} J(\theta^{(k)}_1,\theta^{(k)}_2,\cdots,\theta^{(k)}_{i−1},\theta_i,\theta^{(k−1)}_{i+1},\cdots,\theta^{(k−1)}_n)$$

也就是说$\theta^{(k)}_i$是使$J(\theta^{(k)}_1,\theta^{(k)}_2,\cdots,\theta^{(k)}_{i−1},\theta_i,\theta^{(k−1)}_{i+1},\cdots,\theta^{(k−1)}_n)$最小化时候的$\theta_i$的值。此时$J(\theta)$只有$\theta^{(k)}_i$是变量,其余均为常量,因此最小值容易通过求导求得。

如果上面这个式子不好理解,我们具体一点,在第$k$轮,$\theta$向量的$n$个维度的迭代式如下:

    $$\theta^{(k)}_1=\text{argmin}_{\theta_1} J(\theta_1,\theta^{(k−1)}_2,...,\theta^{(k−1)}n)$$

    $$\theta^{(k)}_2=\text{argmin}_{\theta_2} J(\theta^{(k)}_1,\theta_2,\theta^{(k−1)}_3...,\theta^{(k−1)}_n)$$

    $$\cdots$$

    $$\theta^{(k)}_n=\text{argmin}_{\theta_n} J(\theta^{(k)}_1,\theta^{(k)}_2,...,\theta^{(k)}_{n−1},\theta_n)$$

    3. 检查$\theta^{(k)}$向量和$\theta^{(k−1)}$向量在各个维度上的变化情况,如果在所有维度上变化都足够小,那么$\theta^{(k)}$即为最终结果,否则转入2,继续第$k+1$轮的迭代。



以上就是坐标轴下降法的求极值过程,可以和梯度下降做一个比较:


a) 坐标轴下降法在每次迭代中在当前点处沿一个坐标方向进行一维搜索 ,固定其他的坐标方向,找到一个函数的局部极小值。而梯度下降总是沿着梯度的负方向求函数的局部最小值。


b) 坐标轴下降优化方法是一种非梯度优化算法。在整个过程中依次循环使用不同的坐标方向进行迭代,一个周期的一维搜索迭代过程相当于一个梯度下降的迭代。


c) 梯度下降是利用目标函数的导数来确定搜索方向的,该梯度方向可能不与任何坐标轴平行。而坐标轴下降法法是利用当前坐标方向进行搜索,不需要求目标函数的导数,只按照某一坐标方向进行搜索最小值。


d) 两者都是迭代方法,且每一轮迭代,都需要$O(mn)$的计算量($m$为样本数,$n$为系数向量的维度)


转自这里

SofaSofa数据科学社区DS面试题库 DS面经

东布东   2018-09-29 04:30

4

另外两位说得很清楚了,我就插个图。简单地说就是按照坐标轴方向下降的。


SofaSofa数据科学社区DS面试题库 DS面经

GuoLinhui   2018-09-29 10:25

3

Gradient descent是Coordinate descent的特殊情况。每一个待求变量都是个坐标。n个变量就形成在n维空间找最优解的问题。CD每一步只计算一个或一部分待求变量上的gradient,其余变量保持不变。如果每步都改变全部变量,就是GD。

CD最大的优点是第k步计算都用了之前最新的值,而GD相当于每n步才更新一次数据。

至于CD和GD有同一最优解,是靠把问题“设计”成凸优化来实现的。

SofaSofa数据科学社区DS面试题库 DS面经

Zealing   2018-09-29 06:47



  相关主题

为什么SGD需要对特征先做归一化缩放处理?   2回答

神经网络里的batch size和sgd里的batch size是一回事嘛?   1回答

混合整数规划的混合是什么意思?   2回答

python里用来做数值优化的库?   2回答

线性回归有精确的解析解为什么还要用梯度下降得到数值解?   4回答

优化算法中的“带冲量”是什么意思?   1回答

对于小批量随机剃度下降法(mini-batch SGD),如何选择每批样本的数量?   2回答

随机梯度下降(sgd)的收敛问题   4回答

梯度上升算法是什么?   2回答

RMSProp的直白解释   1回答

nesterov’s momentum和momentum的区别?   1回答

Adam优化算法   1回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!