关于坐标下降法(Coordinate Descent)你没理解的事情

灰太狼 2022-10-16 02:58 211阅读 0赞

### 目录 ###

*  概念
 *  原理
 *  坐标下降法与全局最小值
 *  特点

# 概念 #

*  见下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70]
 *  其实就是先固定其他相关变量的值，只对某个未知变量进行优化。

# 原理 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][20210526161755246.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 6]

# 坐标下降法与全局最小值 #

*  那么问题来了，假如我们寻找到了一个点x使得在所有单个坐标轴上f(x)都最小，是否证明我们找到了全局最小值点？
 *  这个问题要分情况来看：
 *  a. 若f(x)是可微的凸函数，答案是Yes，因为f(x)在任何坐标方向上求偏导都是0，并且对于凸函数来说，局部极小值就是全局最小值：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 7]
 *  b. 若f(x)是不可微的凸函数，答案是No，我们可以很容易举出反例，比如下图中算法会在不可微点（右图中红色虚线交叉点）停止迭代，因为在任意坐标方向上f(x)都找不到的更小值了。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 8]  
    知道为什么嘛？红点处对应的就是三维图这里的位置：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 9]  
    这个红色的凹槽处任何一点都会导致坐标下降法停止，然而真正的最低点只有一处，不用我说了吧。  
    为什么导致坐标下降法停止呢？因为在这条凹槽上的任何一点，你尝试沿着 x 1 x\_1 x1， x 2 x\_2 x2方向移动，你发现每个方向都会导致函数值 f ( x ) f(x) f(x)增加，所以坐标下降法认为到达底部了，其实没有。
 *  c.见下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 10]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 11]  
    因为是凸函数，所以有上式中的第一个 > = >= >=符号，你可以随机取两点想象一下。然后又由于 x x x是咱们用坐标下降法得到的最终结果，所以在每个维度求和的时候，第一项应当为0 ，即 ▽ g ( x ) ( y i − x i ) ▽g(x)(y\_i-x\_i) ▽g(x)(yi−xi)中的梯度为0，所以该项=0，而后面一项你要这么理解。首先，每一个 h i h\_i hi都是凸函数是什么意思？就是在每个维度上，都增加了一个凹槽，该凹槽是凸函数状的，如图：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 12]  
    上图中的两个红色凹槽分别是平行于两个坐标轴的，他们就是 h 1 h\_1 h1， h 2 h\_2 h2，两个凸函数。其实通过b你也能看出来，凹槽存在不可怕，可怕的是存在像b中那样的凹槽，对于两个坐标的增益都是负的，而这里的两个凹槽你可以试一试，不可能出现b中的情况，因为它们的平行于坐标轴的。所以当你真正达到坐标下降法的最低点后，公式中的 h i ( y i ) − h i ( x i ) h\_i(y\_i)-h\_i(x\_i) hi(yi)−hi(xi)必然是正的。

# 特点 #

*  坐标轴的顺序可以是任意的，可以使用\{1,2,…,n\}的任何排列
 *  之前我们介绍的是严格的坐标下降法，即每次仅沿着单个坐标轴的方向寻找函数极小值。与之相对应的是块坐标下降法，即每次沿着多个坐标轴的方向（超平面）取极值。
 *  将新的  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 13]
 *  见下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 14]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70]: /images/20221014/4352807ef62b46e0b0778cd5079e9bb2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 1]: /images/20221014/f905a84e31dc416a9162f5978e27f434.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 2]: /images/20221014/cee2f7c0e1be436080c807485e4b62fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 3]: /images/20221014/f5a3f6b6090c424abb9d9393b956d4b9.png
[20210526161755246.png]: /images/20221014/817f52acc4374e1a9ce27cd0445a48de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 4]: /images/20221014/16dc87d034d7488a80eca2453dfdd75a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 5]: /images/20221014/a518d521332745369eea78e0a3b8cd7e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 6]: /images/20221014/2145acdad3894a55931f91dce831407e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 7]: /images/20221014/5b1af3ebc9e7458a98f7f7a7c6b798a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 8]: /images/20221014/ba80ee078bf54da79a5dc460fe718921.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 9]: /images/20221014/48b7a19e10d6405892da0804966682da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 10]: /images/20221014/47af4fdbfd4141a0a7560633226fd702.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 11]: /images/20221014/60aeede5b6bd49b3945787893c2be9a3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 12]: /images/20221014/4e1e103b17d4451185f27f0e050ef240.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 13]: /images/20221014/0205a4d482274edaa794785898a18423.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDc2Nzk3_size_16_color_FFFFFF_t_70 14]: /images/20221014/9966fd3e98394126be65fb3b8ef0cb85.png