chapter4-梯度下降算法(Gradient Descent)

Posted on | In | | Visitors: ℃
Words count in article: 2.4k | Reading time ≈ 9

chapter4-梯度下降算法(Gradient Descent)

求解机器学习算法的模型参数时，即无约束优化问题时，梯度下降（Gradient Descent）是最常采用的方法之一，另一种常用的方法是最小二乘法。这里就对梯度下降法做一个完整的总结。

1.梯度

在微积分里面，对多元函数的参数求∂偏导数，把求得的各个参数的偏导数以向量的形式写出来，就是梯度。比如函数$f(x,y)$,分别对$x,y$进行求导，求得梯度向量是$(\frac{\partial f}{\partial x},\frac{\partial f}{\partial y})^T$ 简称$grad f(x,y)$ | $\Delta f(x,y)$,对于点为$(x_0,y_0)$,他的梯度向量值为$(\frac{\partial f}{\partial x_0},\frac{\partial f}{\partial y_0})^T$ | $\Delta f(x_0,y_0)$,如果为三个变量，就为：$\Delta f(x,y,z)$,以此类推。

那为什么要找到函数$f(x,y)$的梯度呢？因为梯度向量是函数下降(增加)速度最快的地方。比如说，在初始点$(x_0,y_0)$ 沿着梯度向量$\Delta f(x_0,y_0)$ (-$\Delta f(x_0,y_0)$)，增加最快(下降最快)的方向 ，我们能够更快的找到函数的最小值(最大值)。

2.梯度上升与梯度下降

在机器学习背景当中，求损失函数的最小值，是非常常见的。对于梯度来说，求梯度向量给予不同的正负，就能够使得在函数上走向增加最快的方向(+)和下降最快的方向(-)。即为$f(\theta)$和$-f(\theta)$。

3.梯度下降算法详解
3.1梯度下降算法的直观解释

梯度下降算法如下图所示，从图中我们可以看出，从初始点出发，通过迭代不断的朝着下降速度最快的方向前进。但是在不同的step size (learning rate)下，他走向了不同的地方，因为函数可能有多个峰值和谷值，所以会找到不同谷底的最小值，使得最终的结果可能是局部最优。当然梯度下降算法分为：批量梯度下降算法(BGD),随机梯度下降算法(SGD)和小批量随机梯度算法(MBGD)(算法区别主要在于样本选择)。选择不同的算法，他们在运行时间和结果是否最优解上有较大的差异。(如果函数为凸函数，那么不管怎样都会有全局最优解，比如$x^2$)

3.2 梯度下降算法相关概念

由上述介绍，我们总结概念如下：

  1. 步长(learning rate)： 步长决定了你梯度下降时，一次迭代你往前进方向走的长度

  2. 特征(feature): 指样本输入部分。比如2个但特征样本$(x_0,y_0)(x_1,y_1)$，则第一个样本特征为$x_0$，输出为$y_0$.

  3. 假设函数(hypothesis fuction):在监督学习中，为了拟合输入样本，而使用的假设函数，记为$h_\theta(x)$,比如对于某个单个特征的m个样本$(x^{(i)},y^{(i)}) \quad (i=1,2,3,\cdots,m)$,可以采用拟合函数如下:$h_\theta=\theta_0 + \theta_1x$.

  4. 损失函数(loss function): 为了评估模型拟合的好坏，通常用损失函数来度量拟合程度。损失函数极小化，以为这拟合度最好，对应的模型参数即为最优函数。在线性回归中，损失函数，通常为样本输出与假设函数的差的平方，即为平方误差(mse).比如m个样本$(x^{(i)},y^{(i)}) \quad (i=1,2,3,\cdots,m)$,采用线性回归，损失函数为：
    $$
    J(\theta_0,\theta_1) = \sum_{i=1}^m(h_\theta{(x_i)}-y_i)^2
    $$
    其中$x_i$表示第$i$个样本特征,$y_i$表示第$i$个样本的输出，$h_\theta(x)$为假设函数。

3.3 梯度下降详细算法

类比于最小二乘法章节。梯度下降算法我们以线性回归来进行举例，它亦有代数式和矩阵式两种求解方式，下面我们将进行分别讨论。

3.3.1. 梯度下降代数式算法

  1. 确定假设函数和损失函数

    ​ 对于线性回归的假设函数为$h_\theta(x_1,x_2,…x_n)=\theta_0+\theta_1x_1+…+\theta_{n−1}x_{n−1}$,其中$x_i$为样本特征，$\theta_i$为 模型参数，同最小二乘法，我们可以令$x_0=1$,可以简化为$h_θ(x_1,x_2,…x_n)=\sum_{i=0}^{n}\theta_ix_i$,因此利用均方误差作为损失函数为

$$
J(\theta_0,\theta_1,\cdots,\theta_j) =\frac{1}{2m}\sum_{i=1}^m(h_θ(x_0^{(i)},x_1^{(i)},\cdots,x_j^{(i)}) - y^{(j)})^2=\frac{1}{2m}\sum_{i=1}^n(\sum_{j=1}^m\theta_jx_j^{(i)}-y^{(i)})^2
$$

  1. 算法参数的初始化

    ​ 主要初始化模型参数$\theta_i$、终止距离$\epsilon $、步长$\alpha$和最大迭代次数max_iters.在没有先知经验下，我喜欢把数$\theta_i$初始化为0，$\epsilon $初始化为0.0001和$\alpha$初始化为0.38,max_iters初始化为1000.

    3.算法过程

    1）对损失函数$\theta_i$求偏导，得到梯度向量，即线性回归梯度为:

    $$
    \frac{\partial }{\partial \theta_i}J(\theta_0,\theta_1,\cdots,\theta_j) =\frac{1}{m}\sum_{i=1}^n(\sum_{j=1}^m\theta_jx_j^{(i)}-y^{(i)})x_j^{(i)}
    $$
    ​ 2）利用步长乘以损失函数梯度，得到当前位置下降的距离。

​ 3）确定当前所有$\theta_i$下降距离是否都小于$\epsilon$,如果小于或者达到最大迭代次数结束max_iters就终止训练，即 最佳参数为当前$\theta_i$,如果没有就进行步骤4。

​ 4） 更新每个参数$\theta_i$,更新后进入步骤1，知道满足步骤3或者达到最大迭代次数结束max_iters
$$
\theta_i=\theta_i-\alpha\frac{1}{m}\sum_{i=1}^n(\sum_{j=1}^m\theta_jx_j^{(i)}-y^{(i)})x_j^{(i)}
$$
3.3.2. 梯度下降矩阵式算法

​ 基本思想和线性代数解法一致，只是由矩阵进行表示

​ 1. 确定假设函数和损失函数

​ 对于简化后的$h_\theta$可知，能够得到矩阵表达式为:
$$
h_\theta(X) = \theta X
$$

​ 化简为矩阵损失函数 $J(θ)=\frac{1}{2}(θX−Y)^T(θX−Y)$，其中， 假设函数$h_{\theta}(X)$为mx1的向量,$\theta$为nx1的 向量，里面有n个代数法的模型参数。$X$为mxn维的矩阵。m代表样本的个数，n代表样本的特征数.

  1. 算法参数的初始化

    除$\theta_i$变为矩阵向量表示，其余和上述一致

  2. 算法过程

    1) 对损失函数$\theta_i$求偏导，得到梯度向量，即线性回归梯度为~

$$
\frac{\partial }{\partial \theta}J(\theta)=X^T(\theta X-Y)
$$

​ 2) 利用步长乘以损失函数梯度，得到当前位置下降的距离。

​ 3）确定当前所有$\theta_i$下降距离是否都小于$\epsilon$,如果小于或者达到最大迭代次数结束max_iters就终止训练，即最佳参数为当前$\theta_i$,如果没有就进行步骤4，

​ 4） 更新每个参数$\theta_i$,更新后进入步骤1，直到满足步骤3。
$$
\theta = \theta-\alpha X^T(\theta X-Y)
$$

3.3.3. 梯度下降算法代码实践

​ 现在我们举一个实际的栗子。对于函数$f(x)=x^4-3x^3+2$,求导可以得到$f^\prime(x)=4x^3-9x^2$.我们令$f^\prime(x)=0$可以解出$x=\frac{9}{4}=2.25 \quad and\quad x=0$,我们需要全局最小值，所以取得$x=2.25$.下面我们通过梯度下降算法去解出$x$的值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
next_x = 6  #初始化值x
learning_rate = 0.01  # 学习率
epsilon = 0.00001  # 迭代值相差阈值 如果相差太小就停止模型。
max_iters = 10000  #最大迭代数

#导函数
def df(x):
    return 4 * x**3 - 9 * x**2

for _i in range(max_iters):
    current_x = next_x
    next_x = current_x - learning_rate * df(current_x)

    step = next_x - current_x
    if abs(step) <= epsilon:
        break

print("Minimum at ", next_x)

# 最终输出求最小近似值x: "2.2499646074278457"
3.4 梯度下降算法调参

​ 1.learning_rate(步长)的选择，在不同阶数函数当中，峰值与谷值高低不一，造成步长的长度一定决定是否会错过全局最优峰值，或者会在局部峰值停滞不前。所以呢？根据我的经验来说：构建模型时，我们应该把步长设置得较大一点比如0.5，这样模型会更快的收敛，这样会更快的找到模型构建是否正确。当模型完全没问题时，应该逐渐减小步长，免得错过更好的峰值。

  1. 初始值设定。站在不同的高度，领略不同的风景。所以需要细心调整初始值。当然在深度学习当中对初始值的设定要求会更高。
  2. 归一化。在线性模型当中，归一化可以使模型更快的收敛。不会各种低峰饶很久，才回收敛。最常见归一化就是特征值$(x-avg(x))/std(x)$，就是减去平均值，然后除以方差。
3.5梯度下降算法的区别

1.批量梯度下降算法(BGD)

​ 批量梯度下降算法，直观而言。就是对全部样本的数据进行参数更新
$$
\theta_i=\theta_i-\alpha\frac{1}{m}\sum_{i=1}^n(\sum_{j=1}^m\theta_jx_j^{(i)}-y^{(i)})x_j^{(i)}
$$
2.随机梯度下降算法(SGD)

​ 同理，随机梯度下降算法，就是随机在样本中选择一个样本进行更新参数$\theta_i$ .

3.小批量随机梯度算法(MBGD)

​ 小批量随机梯度算法,是对前两种算法的综合。即为随机选择小批量的样本进行更新参数$\theta_i$ .

参考文献

梯度下降算法原理

gradient descent theory

为什么要归一化|标准化