基于方差的梯度下降算法

梯度下降算法简介

梯度下降算法是寻找函数极小值点的迭代优化算法. 必须基于当前点的梯度(或近似梯度)方向的反方向进行规定步长距离进行迭代搜索, 以达到接近极小值的算法. 假如按梯度相同方向迭代搜索, 就会接近极大值, 称为梯度上升法.

该简介译自: Gradient descent from wikipedia

(可以证明, 沿着梯度方向或反方向, 可以获得最大、最快的进度. 对于梯度的详细了解,可参照高数课本导数部分关于梯度的介绍).

梯度下降算法步骤

1. 通用步骤

1. 计算当前误差
2. 查看当前误差是否符合要求, 或是否已达到迭代上限, 若是,结束
3. 计算当前点的梯度
4. 反方向根据梯度更新当前点, 计算误差,走2

2. 例子

用梯度下降算法求$y=x^2$的极小值点, 初始点为x=2, 精确度为0.01

计算梯度的函数为: $y^{'} = 2x$, 学习率(步长更新系数)为0.1, 迭代次数为20

我们发现, 当迭代次数达到15时, 误差值已经满足条件, 此时便可以停止迭代的, 所以16-20次时没有必要的, 此处仅为了展示清楚.

而此时, x = 0.087960也就是我们要找的值.

3. 代码(以python为例)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

target = 0
x = 2
rate = 0.1
precision = 0.01
previous_step_size = 1 
max_iters = 20 # maximum number of iterations
iters = 0 #iteration counter

def fun(x):
    return x * x

def derivative_fun(x):
    return 2 * x

while (abs(fun(x) - target) > precision) and (iters < max_iters):
    dx = -rate * derivative_fun(x)
    x += dx
    iters+=1

print("The local minimum occurs at", str(x)[:8])
#The output for the above will be: ('The local minimum occurs at 0.087960')

基于方差的梯度下降

1. 选择使用方差的原因

神经网络或其他机器学习内容里面, 经常需要用到梯度下降算法来解决问题. 这常常需要, 计算值与目标值的差距越小越好.

若使用原始的 $f(x)-y_0$ 则无法通过比大小的方式判断当前差距是否更小, 若是加个绝对值, 使用 $|f(x)-y_0|$ 又增加了复杂性, 在计算梯度的方面更不好处理.

所以,使用方差, 采用 $(f(x)-y_0)^2$来评估差距大小, 既排除了正负号带来的影响, 又能直接通过比大小来判断是否更好.

2. 推导(以神经网络中迭代更新weights为例)

在神经网络中, 我们分出许多层的概念.

输入层、隐藏层和输出层.

单论其中某一层(隐藏层为例)的某一节点, 处理过程是这样的:

为了讨论方便, 我们把神经网络简化为输入层和输出层, 也就是说,整个神经网络就是上图的流程.

于是,我们的误差就是 $$ E=y-\check y $$

但由于这样不好比较,所以我们取方差作为误差

$$ E=(y - \check y)^2 $$ 这里, 我们的目的是选取适当的 $w_i$ , 使得E最小, 也就是求E的极小值点, E关于 $w_i$ 的函数为:

$$ E = (y - \check y)^2 =(y - f(h))^2
=(y - f(\sum_i^n{w_ix_i}))^2 $$ 为简单起见,我们令:

$$ E = \frac{1}{2}*(y - \check y)^2 $$

我们要求E关于 $w_i$ 的梯度,数学推导过程为:

$$ \frac{\partial E}{\partial w_i} = \frac{1}{2}*\frac{\partial (y - f(h))^2}{\partial w_i} \newline = (y-f(h)) * \frac{\partial(y-f(h))}{\partial w_i}\newline = -(y-f(h)) * \frac{\partial f(h)}{\partial w_i}\newline = -(y-f(h)) * f^{'}(h) * \frac{\partial h}{\partial w_i}\newline = -(y-f(h)) * f^{'}(h) * \frac{\partial \sum_i^n{w_ix_i}}{\partial w_i}\newline = -(y-f(h)) * f^{'}(h) * \frac{\partial (w_1x_1 +w_2x_2 + ... + w_ix_i + ...+ w_nx_n)}{\partial w_i}\newline = -(y-f(h)) * f^{'}(h) * (\frac{\partial w_1x_1}{\partial w_i}+\frac{\partial w_2x_2}{\partial w_i} + ... + \frac{\partial w_ix_i}{\partial w_i} + ...+ \frac{\partial w_nx_n}{\partial w_i})\newline = -(y-f(h)) * f^{'}(h) * (0+0 + ... + x_i + ...+ 0)\newline = -(y-f(h)) * f^{'}(h) * x_i\newline = -\delta * x_i $$

记住, $w_i$ 的步长按梯度的反向进行

所以 $\Delta w_i = \eta * \delta * x_i$ , 其中 $\eta$ 为学习率.

经过多次的迭代, 最终 $w_i$ 会收敛为最优的 $w_i$ .