【机器学习】算法基础——几种最优化方法详解

忙了好久一阵子，年前终于有时间休整一下了，会把之前的坑填一填。
去年搞了个博客打算写学术文章，最终发现还是没有知乎编辑舒服，
所以就打算把博客留给生活，知乎留给工作。

大部分的机器学习算法的本质都是建立优化模型，通过最优化方法对目标函数（或损失函数）进行优化，从而训练出最好的模型。常见的最优化方法有梯度下降法、牛顿法和其它衍生算法等。

那么在开始讲解前，我们先回顾一下数学上的一些基本概念。

梯度下降法是最早最简单，也是最为常用的最优化方法。梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。最速下降法越接近目标值，步长越小，前进越慢。

导数

方向导数

梯度公式

比如我们在一座大山上的某处位置，由于我们不知道怎么下山，于是决定走一步算一步，也就是在每走到一个位置的时候，求解当前位置的梯度，沿着梯度的负方向，也就是当前最陡峭的位置向下走一步，然后继续求解当前位置梯度，向这一步所在位置沿着最陡峭最易下山的位置走一步。这样一步步的走下去，一直走到觉得我们已经到了山脚。当然这样走下去，有可能我们不能走到山脚，而是到了某一个局部的山峰低处（局部最小值）。

从上面的解释可以看出，梯度下降不一定能够找到全局的最优解，有可能是一个局部最优解。当然，如果损失函数是凸函数，梯度下降法得到的解就一定是全局最优解。

梯度下降法步骤

具体例子

在使用梯度下降时，需要进行调优。哪些地方需要调优呢？

1. 算法的步长选择 ：步长取值取决于数据样本，可以多取一些值，从大到小，分别运行算法，看看迭代效果，如果损失函数在变小，说明取值有效，否则要增大步长。步长太大，会导致迭代过快，甚至有可能错过最优解。步长太小，迭代速度太慢，很长时间算法都不能结束。所以算法的步长需要多次运行后才能得到一个较为优的值。

2. 算法参数的初始值选择 ：初始值不同，获得的最小值也有可能不同，因此梯度下降求得的只是局部最小（当然如果损失函数是凸函数则一定是最优解）。由于有局部最优解的风险，需要多次用不同初始值运行算法，关键损失函数的最小值，选择损失函数最小化的初值。

3. 归一化 ：由于样本不同特征的取值范围不一样，可能导致迭代很慢，为了减少特征取值的影响，可以对特征数据归一化。

1. 靠近极小值时收敛速度减慢，如下图所示；

2. 直线搜索时可能会产生一些问题；

3. 寻找的是局部最优，可能会“之字形”地下降。

批量梯度下降法（Batch Gradient Descent）

批量梯度下降法，是梯度下降法最常用的形式，具体做法也就是在更新参数时使用所有的样本来进行更新。 这样一来每迭代一步，都要用到训练集所有的数据，如果数据量很大，那么可想而知这种方法的迭代速度会很慢。所以，这就引入了另外一种方法，随机梯度下降。

随机梯度下降法（Stochastic Gradient Descent）

随机梯度下降（Stochastic Gradient Descent）每次迭代只用到了一个样本，在样本量很大的情况下，常见的情况是只用到了其中一部分样本数据即可迭代到最优解。因此随机梯度下降比批量梯度下降在计算量上会大大减少。SGD有一个缺点是，其噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。而且SGD因为每次都是使用一个样本进行迭代，因此最终求得的最优解往往不是全局最优解，而只是局部最优解。但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近。

小批量梯度下降法（Mini-batch Gradient Descent）

小批量梯度下降法是批量梯度下降法和随机梯度下降法的折衷，也就是对于m个样本，我们采用 x个样子来迭代，1<x<m 。

def train(X, y, W, B, alpha, max_iters):
    '''
    使用了所有的样本进行梯度下降
    X: 训练集,
    y: 标签,
    W: 权重向量,
    B: bias,
    alpha: 学习率,
    max_iters: 最大迭代次数.
    '''
    dW = 0 # 权重梯度收集器
    dB = 0 # Bias梯度的收集器
    m = X.shape[0] # 样本数
    
    for i in range(max_iters):
        dW = 0 # 每次迭代重置
        dB = 0
        for j in range(m):
            # 1. 迭代所有的样本
            # 2. 计算权重和bias的梯度保存在w_grad和b_grad,
            # 3. 通过增加w_grad和b_grad来更新dW和dB
            W = W - alpha * (dW / m) # 更新权重
            B = B - alpha * (dB / m) # 更新bias
    return W, B 

牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x)=0的根。牛顿法最大的特点就在于它的收敛速度很快。

牛顿法步骤

具体例子

总的来说，梯度法和牛顿法有如下区别：

• 梯度下降法和牛顿法相比，两者都是迭代求解，不过梯度下降法是梯度求解，而牛顿法是用二阶的海森矩阵的逆矩阵求解。相对而言，使用牛顿法收敛更快（迭代更少次数）。但是每次迭代的时间比梯度下降法长。（至于为什么牛顿法收敛更快，通俗来说梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。）
• 牛顿法对初始值有一定要求，在非凸优化问题中（如神经网络训练），牛顿法很容易陷入鞍点（牛顿法步长会越来越小），而梯度下降法则很容易逃离鞍点（因此在神经网络训练中一般使用梯度下降法，高维空间的神经网络中存在大量鞍点）
• 梯度下降法在靠近最优点时会震荡，因此步长调整在梯度下降法中是必要的，具体有adagrad, adadelta, rmsprop, adam等一系列自适应学习率的方法。

def newton(f, x, iters):
    """
    实现牛顿法
    :param f: 原函数
    :param x: 初始值
    :param iters: 遍历的最大epoch
    :return:
    """
    Hessian_T = np.linalg.inv(hessian(f, x))
    H_G = np.matmul(Hessian_T, jacobian(f, x))
    x_new = x - H_G
    print("第1次迭代后的结果为:", x_new)
    for i in range(1, iters):
        Hessian_T = np.linalg.inv(hessian(f, x_new))
        H_G = np.matmul(Hessian_T, jacobian(f, x_new))
        x_new = x_new - H_G
        print("第"+str(i+1)+"次迭代后的结果为:", x_new)
    return x_new

最基本的最优化方法就介绍到这里，其余的还有拟牛顿法、DFP(Davidon-Fletcher-Powell)算法、BFGS(Broyden-Fletcher-Goldfard-Shano)算法等，有需求的朋友自己查。

1. 梯度下降法、牛顿法和拟牛顿法：https://zhuanlan.zhihu.com/p/37524275
2. 梯度下降法https://blog.csdn.net/weixin_42278173/article/details/81511646
3. 泰勒公式https://baike.baidu.com/item/%E6%B3%B0%E5%8B%92%E5%85%AC%E5%BC%8F
4. 海塞矩阵https://baike.baidu.com/item/%E9%BB%91%E5%A1%9E%E7%9F%A9%E9%98%B5

本文为VoidOc^[1]博主原创文章，未经博主允许不得转载。原文地址：https://voidoc.blog/21627.html