机器学习(高数)：最优化算法之梯度下降法

作者: 星光下的胖子 | 来源:发表于2020-05-19 11:50 被阅读0次

一、梯度

导数

设函数 $y=f(x)$ 在点 $x_0$ 的某领域 $U(x_0)$ 内有定义，当自变量 $x$ 在 $x_0$ 处有增量 $\Delta{x}$ ，相应函数增量 $Δy=f(x_0+Δx)-f(x_0)$ ；如果 $Δy/Δx$ 当 $Δx \to 0$ 时极限存在，则称函数 $y=f(x)$ 在点 $x_0$ 处可导，并称此极限为函数 $y=f(x)$ 在点 $x_0$ 处的导数，记作 $f'(x_0)$ ，即
$f'(x_0) = \lim_{\Delta{x} \to {0}}\frac{\Delta{y}}{\Delta{x}} = \lim_{\Delta{x} \to {0}}\frac{f(x_0+\Delta{x})-f(x_0)}{\Delta{x}} \Leftrightarrow f'(x_0) = \lim_{x \to x_0}\frac{f(x)-f(x_0)}{x-x_0}$

函数导数 $f'(x_0)$ 的几何意义：函数曲线在点 $P_0(x_0, f(x_0))$ 处的切线斜率。

在一元函数 $f(x)$ 中，导数就是函数的变化率。那么对于二元函数、多元函数，我们应该如何描述函数的变化率？
下面引入两个概念：偏导数和方向导数。

偏导数是反映函数沿坐标轴方向的变化率。
方向导数是反映函数在其他特定方向(任意方向)上的变化率。

偏导数

设二元函数 $z=f(x, y)$ 在点 $(x_0,y_0)$ 的某领域内有定义，把 $y$ 固定在 $y_0$ 而让 $x$ 在 $x_0$ 有增量 $\Delta x$ ，相应函数有增量(对 $x$ 的偏增量) $\Delta z=f(x_0+\Delta x, y_0)-f(x_0,y_0)$ 。如果 $\Delta z/\Delta x$ 当 $Δx \to 0$ 时极限存在，则称这个极限为函数 $z=f(x,y)$ 在点 $(x_0,y_0)$ 处对 $x$ 的偏导数，记作 $f_x(x_0,y_0)$ ，即
$f_x(x_0,y_0)=\lim_{\Delta{x} \to {0}}\frac{\Delta{z}}{\Delta{x}}=\lim_{\Delta x \to 0}\frac{f(x_0+{\Delta x},y_0)-f(x_0,y_0)}{\Delta x}$

同样，把 $x$ 固定在 $x_0$ ，让 $y$ 有增量 $\Delta y$ ，如果极限存在则称此极限为函数 $f(x,y)$ 在点 $(x_0,y_0)$ 处对 $y$ 的偏导数，记作 $f_y(x_0,y_0)$ ，有
$f_y(x_0,y_0) = \lim_{\Delta{y} \to {0}}\frac{\Delta{z}}{\Delta{y}} = \lim_{\Delta y \to 0}\frac{f(x_0,y_0+{\Delta y})-f(x_0,y_0)}{\Delta y}$

偏导数是反映函数沿坐标轴方向的变化率。

方向导数

设多元函数 $f$ 在点 $P_0({x_1}^0,{x_2}^0,{x_3}^0,...,{x_n}^0)$ 的某领域 $U(P_0)$ 内有定义， $l$ 为从 $P_0$ 出发的射线， $P({x_1},{x_2},{x_3},...,{x_n})$ 为 $l$ 上且含于 $U(P_0)$ 内的任一点，以表示 $P$ 与 $P_0$ 两点间的距离。若极限
$\lim_{\rho \to 0^+}\frac{f(P)-f(P_0)}{\rho}=\lim_{\rho \to 0^+}\frac{\Delta_lf}{\rho}$
存在，称此极限为函数 $f$ 在点 $P_0$ 沿方向 $l$ 的方向导数，记作 $f_l(P_0)$ 或 $f_l(x_1^0,x_2^0,...,x_n^0)$ 。

方向导数是反映函数在其他特定方向(任意方向)上的变化率。

梯度

若多元函数 $f$ 在点 $P_0(x_1^0,x_2^0,...,x_n^0)$ 存在对所有自变量的偏导数，则称向量 $(f_{x_1}(P_0),f_{x_2}(P_0),...,f_{x_n}(P_0))$ 为函数 $f$ 在点 $P_0$ 处的梯度，记作
$gradf=(f_{x_1}(P_0),f_{x_2}(P_0),...,f_{x_n}(P_0))$
向量 $gradf$ 的长度(模)为
$|gradf|=\sqrt{[f_{x_1}(P_0)]^2 + [f_{x_2}(P_0)]^2 + ... + [f_{x_n}(P_0)]^2}$

函数在变量空间的某一点处，沿哪个方向有最大的变化率？答案：梯度/最大方向导数。
梯度概念的提出，就是为了寻找极值(极大值)，因此梯度总是指向函数增长最快的方向。梯度是一个向量，有大小和方向。

方向导数本质上研究的是函数在某点处沿某特定方向上的变化率问题，梯度反映的是空间变量变化趋势的最大值和方向。梯度与方向导数的关系：

梯度的方向是最大方向导数的方向，梯度的反方向是最小方向导数的方向。
梯度的值是最大方向导数的值。

方向导数为正，在该方向上是递增变化的；方向导数为负，在该方向上是递减变化的。以“开口向上的抛物线，对称轴左侧的点”为例：

在切线方向上，沿左上的方向导数最大(值为正，递增)，为梯度的方向。
在切线方向上，沿右下的方向导数最小(值为负，递减)，为梯度的反方向。

二、梯度下降法

所谓的梯度下降，就是取梯度的反方向，即函数下降最快的方向。
梯度下降法的计算过程就是沿梯度下降的方向求解极小值。

梯度下降法的迭代公式：
$\theta=\theta_{0}+\eta·(- \nabla f(\theta_{0}))$
其中， $\nabla f(\theta_{0}) = \lim_{\Delta \theta \to 0}\frac{f(\theta_0+\Delta \theta)-f(\theta_0)}{\Delta \theta}$ ， $\eta$ 为步长/学习率。
步长 $\eta$ 的取值要足够小，以保证每次迭代都在减小。
注意： $\eta$ 不能太小，否则收敛太慢； $\eta$ 不能太大，否则不能保证每一次迭代都在减少，也不能保证收敛。

梯度下降法是一个最优化算法，常用于机器学习中用来递归性地逼近最小偏差。在求解损失函数的最小值时，可以通过梯度下降法来一步步的迭代求解，得到最小的损失函数和模型参数值。

梯度下降法的简单理解

假设我们位于某个山腰处，正准备下山，但我们不知道下山的路。于是决定走一步算一步，我们沿着当前位置最陡峭最易下山的路前进一小步，然后在下一步位置重复这个过程，如此反复，知道走到山脚。这就是梯度下降法的一个简单示例，下山最陡的方向就是梯度的反方向，我们每次沿着梯度的反方向(极小值)前进一小步。

迭代公式的合理性证明

首先给出一阶泰勒展开式：
$\Delta \theta \to 0 \Rightarrow f(\theta) \approx f(\theta_0) + (\theta - \theta_0) \nabla f(\theta_0)$
要使每次更新 $\theta$ 都能使 $f(\theta)$ 变小，即 $f(\theta) \leqq f(\theta_0)$ ，于是：
$f(\theta) - f(\theta_0) \leqq 0 \Rightarrow (\theta - \theta_0) \nabla f(\theta_0) \leqq 0$
其中 $\theta - \theta_0$ 和 $\nabla f(\theta_0)$ 都是向量，设它们的夹角为 $\alpha$ ，有：
$(\theta - \theta_0) \nabla f(\theta_0) = \lVert \theta - \theta_0 \rVert \cdot \lVert \nabla f(\theta_0) \rVert \cdot \cos\alpha \leqq 0$
$\alpha$ 为钝角方可满足条件。且当 $\alpha = 180^\circ$ 时， $\cos\alpha = -1$ ，式子取得最小值，此时下降速度最快(即沿着梯度的反方向前进)。 $\alpha = 180^\circ$ 即向量反向，得到迭代公式：
$\theta - \theta_0 = - \eta \nabla f(\theta_0) \Rightarrow \theta=\theta_{0}+\eta·(- \nabla f(\theta_{0}))$

三、简单示例

回归问题：自动求解一元线性 $y=wx+b$ 回归中的 $w$ 和 $b$

# 梯度下降法
# 回归问题：解决y=3x+4线性回归
import random
import matplotlib.pyplot as plt

# 1）构造数据(x，y)：包含数据x和标签y
# _x存放数据x，_y存放标签y。
# 标签y使用random随机函数，使其值有一个上下波动(模型真实数据)。
_x = [i for i in range(-50, 50)]
_y = [(3 * x + 4 + (random.random() - 0.5)) for x in _x]

# 2）随机分配权重w和偏置b
# 一开始我们并不知道w和b的真实值，所以随机产生一个数。
w, b = random.random(), random.random()
print("初始w=%f, 初始b=%f" % (w, b))

# 3）计算损失loss，并用梯度下降法循环更新w和b的值
# 遍历数据集(x, y)，对于每个输入x，得到一个输出结果h。比较标签y，得到损失loss=(h-y)^2。
# 为了使损失loss变小，根据梯度下降法，修改w和b的值：
#       1.分别求loss关于w和b的偏导数；
#       2.step为步长，这里取0.001；
#       3.带入梯度下降求解公式，分别得到一个新的w和b值。
# 如此往复，不断地更新修正权值w和偏置b，直到loss达到我们设定的阈值范围。
for i in range(5000):
    for x, y in zip(_x, _y):
        # 获取损失loss
        h = w * x + b
        loss = (y - h) ** 2  # loss=(wx+b-y)**2

        # 使用梯度下降法，更新w和b的值
        d_loss_w = 2 * (w * x + b - y) * x  # loss对w求偏导
        d_loss_b = 2 * (w * x + b - y) * 1  # loss对b求偏导
        step = 0.0001  # step为步长
        w = w + (-1) * d_loss_w * step  # 更新后的权重w
        b = b + (-1) * d_loss_b * step  # 更新后的偏置

        # 打印结果
        print("w=%f, b=%f, loss=%f" % (w, b, loss))

print("训练结束w=%f, 训练结束b=%f" % (w, b))
# 最后，将最终得到的y=wx+b绘制成可视化曲线
plt.plot(_x, _y, ".")  # 描点
plt.plot(_x, [w * x + b for x in _x])  # 绘制y=wx+b
plt.show()

运行代码，最终训练结果： $w=2.999384,b=3.980978$ 。

一元线性回归

分类问题：分类两堆数据点

# 梯度下降法
# 分类问题：分类两堆数据点
import matplotlib.pyplot as plt
import random

# 1、构造数据，形如((3,6), 1)、((8,3), 0)
# 1）生成(3, 6)附近随机点，(8, 3)附近随点
_x1 = [3 + 3 * (random.random() - 0.5) for i in range(1000)]
_y1 = [6 + 3 * (random.random() - 0.5) for i in range(1000)]
_x2 = [7 + 5 * (random.random() - 0.5) for i in range(1000)]
_y2 = [3 + 3 * (random.random() - 0.5) for i in range(1000)]
# 2）添加标签
data = []
for x, y in zip(_x1, _y1): # 正样本
    data.append(((x, y), 1))
for x, y in zip(_x2, _y2): # 负样本
    data.append(((x, y), 0))
# 3）打乱数据集顺序(差异性学习)
random.shuffle(data)
random.shuffle(data)
random.shuffle(data)

# 2.随机分配权重w1、w2和偏置b(h=x1*w1+x2*w2+b)
w1, w2, b = random.random(), random.random(), random.random()
print("初始w1=%f, 初始w2=%f, 初始b=%f" % (w1, w2, b))

# 3.计算损失loss，使用梯度下降法循环更新权重w1、w2和偏置b
plt.ion()
for i in range(100):
    for e in data:
        features = e[0]
        y = e[1]
        # 计算损失loss
        h = features[0] * w1 + features[1] * w2 + b
        loss = (h - y) ** 2  # loss = (x1*w1+x2*w2+b-y)**2

        # 使用梯度下降法，更新w1、w2和b
        d_loss_w1 = 2 * (h - y) * features[0]
        d_loss_w2 = 2 * (h - y) * features[1]
        d_loss_b = 2 * (h - y) * 1
        step_size = 0.001  # 步长
        w1 += (-1) * d_loss_w1 * step_size
        w2 += (-1) * d_loss_w2 * step_size
        b += (-1) * d_loss_b * step_size

        print("后w1=%f, w2=%f, b=%f, loss=%f" % (w1, w2, b, loss))

    # 使用plt绘图工具查看整个学习过程
    # plt.cla()
    plt.plot(_x1, _y1, ".")
    plt.plot(_x2, _y2, ".")
    _x = [i / 10 for i in range(0, 100, 1)]
    _y = [(-w1 / w2) * x + ((0.5 - b) / w2) for x in _x]
    plt.plot(_x, _y)
    plt.pause(0.01)  # 睡眠0.01秒

print("训练结束w1=%f, 训练结束w2=%f, 训练结束b=%f" % (w1, w2, b))
plt.ioff()
plt.show()

运行代码，最终训练结果：

学习过程

最终结果

机器学习(高数)：最优化算法之梯度下降法