无约束最优化问题的求解算法

使用梯度下降法目的和原因

目的

梯度下降法(Gradient Descent)是一个算法，但不是像多元线性回归那样是一个具体做回归任务的算法，而是一个非常通用的优化算法来帮助一些机器学习算法求解出最优解的，所谓的通用就是很多机器学习算法都是用它，甚至深度学习也是用它来求解最优解。所有优化算法的目的都是期望以最快的速度把模型参数θ求解出来，梯度下降法就是一种经典常用的优化算法。

原因

前面利用θ的解析解公式求解出来的解我们就直接说是最优解的一个原因是MSE这个损失函数是凸函数，但是如果模型对应的损失函数是非凸函数的话，设置梯度为 0会得到很多个极值，甚至是极大值都有可能。

之前利用θ的解析解公式求解的另一个原因是特征维度并不多，但是细致分析一下公式里面 XT X 对称阵是 N 维乘以 N 维的，复杂度是是 O(N)的三次方，换句话说，就是如果你的特征数量翻倍，你的计算时间大致上要 2 的三次方，8 倍的慢。比如，4 个特征 1 秒，8 个特征就是 8 秒，16 个特征就是 64 秒，当维度更多的时候则运算的复杂度会指数级增长，耗费大量时间和硬件资源。

所以其实之前一步求出最优解并不是机器学习甚至深度学习常用的手段，如下图，之前我们是设置梯度为 0，反过来求解最低点的时候θ是多少，而梯度下降法是一点点去逼近最优解，通过设置一个学习率来定义每次移动的幅度，可以把学习率理解为步长，梯度下降法随机初始化一个值（选择损失函数上的一个点）作为‘开始的地方’，然后一直尝试去逼近损失函数的极小值（沿着损失函数负梯度的方向去走）。

梯度下降法的思想

比如你问一个刚认识的人年龄是多少，对方让你猜，还说你每猜完一次会告诉你是猜高了还是猜低了，这样你就可以奔着对的方向一直猜下去，最后总有一下你能猜对。梯度下降法就是这样的，你得去试很多次，而且是不是我们在试的过程中还得想办法知道是不是在猜对的路上，说白了就是得到正确的反馈再调整然后继续猜才有意义。

在进行这样的猜测时，一开始第一下都是随机瞎猜一个，那对于计算机来说就是随机取值，也就是说你有q =W1...Wn，这里θ强调一下不是一个值，而是一个向量就是一组 W，一开始的时候我们通过随机，把每个值都给它随机出来。有了θ我们可以去根据算法就是公式去计算出来y'，eg y'=Xθ，接下来计算y'与真实值和真实 y 之间的损失，比如均方误差MSE，然后调整θ再去计算MSE，直到求出的MSE最小视为收敛。

这个调整正如咱们前面说的肯定不是瞎调整，当然这个调整的方式很多，你可以整体θ

每个值调大一点，也可以整体θ每个值调小一点，也可以一部分调大一部分调小。第一次q 0我们可以得到第一次的 MSE 就是 Loss0，调整后第二次q1对应可以得到第二次的 MSE就是 Loss1，如果 loss 变小是不是调对了，就应该继续调，如果 loss 反而变大是不是调反了，就应该反过来调。直到 MSE 我们找到最小值时计算出来的q'就是我们的最优解。这个就好比道士下山，我们把 loss 看出是曲线就是山谷，如果走过来就再往回调，所以是一个迭代的过程。

梯度下降法公式

这里梯度下降法的公式就是一个式子指导计算机迭代过程中如何去调整θ，不需要推导

和证明，就是总结出来的

Wj t+1 =Wj t-h ×gradientj

这里的 Wj 就是θ中的某一个 j=0…n，这里的η就是图里的 learning step，很多时候也叫学习率 learning rate，很多时候也用α表示，这个学习率我们可以看作是下山迈的步子的大小，步子迈的大下山就快。

学习率一般都是正数，那么在山左侧梯度是负的，那么这个负号就会把 W 往大了调，如果在山右侧梯度就是正的，那么负号就会把 W 往小了调。每次 Wj 调整的幅度就是η*gradient，就是横轴上移动的距离。

如果特征或维度越多，那么这个公式用的次数就越多，也就是每次迭代要应用的这个式子 n+1 次，所以其实上面的图不是特别准，因为θ对应的是很多维度，应该每一个维度都可以画一个这样的图，或者是一个多维空间的图。

负梯度的含义就是沿着函数下降最快的方式去调整。

每个θ对应一个特征维度。

由此也反映出并不是某个θ得到最优解就是我们所要求的结果，而是特征空间里的每一个θ都求到一个最优解（随着问题复杂程度的增加，特征空间的维度越来越多，这往往很困难）或者是都在可接受范围内的合适解才是我们要的结果。

学习率

学习率的设置

根据我们上面讲的梯度下降法公式，我们知道η是学习率，设置大的学习率 Wj 每次调整的幅度就大，设置小的学习率 Wj 每次调整的幅度就小，然而如果步子迈的太大也会有问题其实，俗话说步子大了容易扯着蛋，可能一下子迈到山另一头去了，然后一步又迈回来了，使得来来回回震荡。步子太小呢就一步步往前挪，也会使得整体迭代次数增加。

合理的设置学习率才能进一步促进模型的收敛。

学习率的设置是门学问，一般我们会把它设置成一个比较小的正整数，0.1、0.01、0.001、0.0001，都是常见的设定数值，一般情况下学习率在整体迭代过程中是一直不变的数，但是也可以设置成随着迭代次数增多学习率逐渐变小，因为越靠近山谷我们就可以步子迈小点，省得走过，还有一些深度学习的优化算法会自己控制调整学习率这个值。

全局最优解

如果损失函数是非凸函数，梯度下降法是有可能落到局部最小值的，所以其实步长不能设置的太小太稳健，那样就很容易落入局部最优解，虽说局部最小值也没大问题，因为模型只要是堪用的就好，但是我们肯定还是尽量要奔着全局最优解去。

梯度下降法流程

梯度下降法几步流程就是猜正确答案的过程：

1. 随机猜，Random 随机θ，随机一组数值 W0…Wn

2. 求梯度，为什么是梯度？因为梯度代表曲线某点上的切线的斜率，沿着切线往下下降就相当于沿着坡度最陡峭的方向下降

3. if g<0, theta 变大，if g>0, theta 变小

4. 判断是否收敛 convergence，如果收敛跳出迭代，如果没有达到收敛，回第 2 步继续

1. 如何随机？

2. 怎么求梯度？

3. 如何调整θ或 W？

4. 怎么判断收敛？

1. np.random.rand()或者 np.random.randn()

4. 判断收敛这里使用 g=0 其实并不合理，因为当损失函数是非凸函数的话 g=0 有可

能是极大值，所以其实我们判断 loss 的下降收益更合理，当随着迭代 loss 减

小的幅度即收益不再变化就可以认为停止在最低点，那么就认为模型收敛了。

损失函数的导函数

下面公式推导 J(θ)是损失函数，q j 是某个特征维度 Xj 对应的权值系数，也可以写成 Wj。这里我们还是在接着之前的多元线性回归往下聊，所以损失函数是 MSE，所以下面公式表达的是因为我们的 MSE 中 X、y 是已知的，θ是未知的，而θ不是一个变量而是一堆变量，所以我们只能对含有一推变量的函数 MSE 中的一个变量求导，即偏导，下面就是对θj 求偏导。