最优化-梯度下降算法

梯度下降算法是最优化算法之一,在大量的机器学习算法和深度学习中都会被用到。优化是指当改变$x$以最小化或最大化某个函数$f(x)$,该函数一般为算法中的目标函数或损失函数,或者称为代价函数、误差函数等。在优化过程中需要通过导数$f’(x)$或$\frac{dy}{dx}$来描述缩放$x$对输出$f(x)$的变化:$f(x+\theta) \approx f(x)+\theta f’(x)$。对于任意小的$\eta$使得$f(x-\eta sign(f’(x))) \lt f(x)$,因此可以将$x$往导数的相反方向移动一小步来减小$f(x)$,这个过程就是梯度下降。

梯度下降

在最小化多维输入的函数:$f: R^n \rightarrow R^n$,为了使得$f$最小化,在一维情况下需要使用导数,如果是多维的情况下需要使用偏导数(partial derivative),偏导数$\frac {\partial} {\partial x} f(x)$衡量点$x$在$x_i$增加或减小是$f(x)$的变化。梯度是相对一个向量求导的导数:$f$的导数是包含所有偏导数的向量,可以记作${\nabla}_x f(x)$。梯度的第i个元素是$f$关于$x_i$的偏导数。在$u$(单位向量)方向上的方向导数是函数$f$在$u$方向的斜率。换句话说,方向导数是函数$f(x+\alpha u)$关于$\alpha$的导数。可以根据链式法则,当$\alpha=0$时,$\frac{\partial}{\partial_{\alpha}}f(x+\alpha u)=u^T \nabla_{x}f(x)$。为了最小化$f$希望找到下降最快的方向,计算方向导数

其中$\theta$是$u$与梯度的夹角。将$||u||_2 = 1$代入,并会略和$u$无关的项,能简化得到${min}_{u}cos{\theta}$。这在$u$ 与梯度方向相反时取得最小。换句话说,梯度向量指向上坡,
负梯度向量指向下坡。我们在负梯度方向上移动可以减小$f$。这被称为最速下降法(method of steepest descent) 或梯度下降(gradient descent)。快速下降并更新的公式为

其中$\epsilon$为学习率,描述更新的步长大小的量。当梯度的每个元素为0或者接近0的地方收敛。

借用维基百科上的说明:

梯度下降算法是基于观察:如果$f(x)$在$a$点处可导且有定义,那么函数$f(x)$在$a$沿着梯度的反向$-\nabla{f(a)}$,如果:

其中每次$\gamma$的步长更新,且可以改变。对于$\gamma>0$为一个任意小的数成立,那么$f(a) \gt f(b)$。因此可以通过最初的估计到后续过程中进行推断得到$x_{n+1}=x_{n}-\gamma_{n}\nabla{f(x_{n})}, n \ge 0$,因此可以得到$f(x_{0} \ge f(x_1) \ge f(x_2) \ge … \ge f(x_{n+1})$,可以得到下图的形式:

可以根据线性模型来使用梯度下降算法来求解。其中$h(x)$为拟合的函数,$J(\theta)$为误差函数或损失函数,用来衡量训练数据集用$h(x)$来拟合的效果程度,$\theta$为需要求得参数。假设:

下面是通过梯度下降来进行参数迭代:

  1. 计算$J(\theta)$关于$\theta$的偏导数,也就是计算向量中每一个$\theta$的梯度:
  1. 沿着梯度的方向更新参数
  1. 迭代直到收敛

上面的梯度下降是使用了所有的样本。因此在数据量很大的时候,每次迭代都会将训练集遍历一次,内存的开销会很大,因此后续对这种批量梯度下降的方式进行了优化,出现了随机梯度下降等算法。

通过示例实现批量梯度下降

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# coding:utf-8
import numpy as np

# 数据
x = np.array([[2.1, 1.5], [2.5, 2.3], [3.3, 3.9], [3.9, 5.1], [2.7, 2.7]])
y = np.array([2.5, 3.9, 6.7, 8.8, 4.6])

# 拟合的函数:f(x) = w1*x1 + w2*x2
# 损失函数:J(w) = (sum((f(x) - y)^2))/2m
# 初始化权重
w = np.random.rand(2)

# 初始化 阈值eps, 学习率(学习步长)
eps = 0.00001
alpha = 0.1
loss = 1
max_iter = 500
iter = 1
while loss > eps and iter < 500:
# 初始化 损失函数差值
loss = 0
sigma = np.array([0, 0])
# 更新权重
for i in range(x.shape[0]):
h = y[i] - sum(w * x[i, :])
sigma = sigma + h * x[i, :] / 5
w = w + alpha * sigma
for i in range(x.shape[0]):
loss += (sum(w * x[i, :]) - y[i]) ** 2
print loss, w
iter += 1