梯度下降算法

基于梯度的优化是优化一个函数的最终取值。输入参数 $\omega$ ，需要优化的函数是 $J(\omega)$ ，基于梯度的优化即通过改变 $\omega$ 使得最大化或最小化 $J(\omega)$ ，称 $J(\omega)$ 为目标函数。

对于一元函数 $l=J(\omega)$ ，它的导数记为 $J'(\omega)$ ，输入 $w$ 发生微小变化 $\sigma$ 时，输出也发生变化，可以近似为
$J(w+\sigma)\approx J(w) + \sigma J'(w)$
假设存在的 $\sigma$ 足够小，则有 $J(w-\sigma *sign(J'(w)))<J(w)$ ，其中 $sign$ 是符号函数。当 $J'(w)$ 小于0时，随着 $w$ 增加， $J(w)$ 减小，而当 $J'(w)$ 大于0时，随着 $w$ 减小， $J(w)$ 才能减小。 $w$ 的变化方向(+或者-)与导数 $J(w)$ 的方向(正负)相反。

多元函数：方向导数与梯度的理解，参考博客https://www.cnblogs.com/wangguchangqing/p/10521330.html#autoid-0-0-0

方向导数

方向导数是指 $z=f(x,y)$ 在某一点 $P$ 沿着某个方向 $l$ 的变化率，是一个==数值==。记为
$\frac {\partial f}{\partial l}={lim}_{\rho \to 0} \frac{f(x+\Delta x,y+\Delta y)-f(x,y)} {\rho}$
自点 $P$ 引射线 $l$ ，与 $X$ 正轴方向的夹角为 $\theta$ ，与函数 $z=f(x,y)$ 的交点 $P'(x+\Delta x,y+\Delta y)$ ，函数在 $P、P'$ 的增量为 $f(x+\Delta x,y+\Delta y)-f(x,y)$ ，两点之间的距离 $\rho = \sqrt {(\Delta x) ^2+ (\Delta y)^2}$ 。若 $P'$ 沿着 $l$ 趋近于 $P$ ，如果增量与距离比值的极限存在，称该值为函数在 $P$ 处的方向导数，即公式(2)。

同时，若函数在 $P$ 处可微，则有 $f(x+\Delta x,y+\Delta y)-f(x,y)= \frac {\partial f} {\partial x}\cdot \Delta x +\frac {\partial f} {\partial y} \cdot \Delta y+o(\rho)$ ，

两边同除以 $\rho$ ，可以得到
$\frac{f(x+\Delta x,y+\Delta y)-f(x,y)} {\rho}= \frac {\partial f} {\partial x}\cdot\cos \theta +\frac {\partial f} {\partial y}\cdot \sin \theta + \frac {o(\rho)} {\rho}$
取极限得到
$\frac {\partial f}{\partial l}={lim}_{\rho \to 0} \frac{f(x+\Delta x,y+\Delta y)-f(x,y)} {\rho} =f_x \cdot \cos \theta +f_y \cdot \sin \theta$

梯度

梯度是指是这样一个向量：每个元素为函数对一元变量的偏导数，它的大小即为最大方向导数。梯度记为
$\nabla f = gradf(x,y)= \frac {\partial f} {\partial x}\cdot i + \frac {\partial f} {\partial y}\cdot j$
梯度与方向导数的联系：

设向量 $e=\cos \theta *i +\sin \theta*j$ 与 $l$ 同方向，根据方向导数的计算公式，有
$\frac {\partial f}{\partial l} =\frac {\partial f} {\partial x}\cos \theta +\frac {\partial f} {\partial y}\sin \theta = \begin{bmatrix} \frac {\partial f} {\partial x} & \frac {\partial f} {\partial y}\end{bmatrix} \begin{bmatrix} \cos \theta \\ \sin \theta \end{bmatrix} = \nabla f \cdot e =||\nabla f|| \cos<\nabla f,e>$
其中 $\cos<\nabla f,e>$ 表示梯度 $\nabla f$ 与向量的夹角， $||\nabla f||$ 表示梯度的大小。可以看到，当方向向量与梯度同方向时，方向导数达到最大值，且最大值等于梯度的大小。

最大方向导数的等于梯度的模， $||\nabla f||=\sqrt{f_x^2+f_y^2}$ ，而梯度的方向由梯度向量与 $X$ 轴的角度给出， $\alpha(x,y)=\arctan \frac {f_y}{f_x}$

由上述可得，函数在某点沿着梯度的方向增长最快，逆梯度方向减小最快。因此，要想求得函数的极小值（或最小值），可以通过沿逆梯度方向变化，不断下降找到极小值。

$eg:$

函数 $J(\theta) = 2-3\theta_1+4\theta_2 -5\theta_3$ ，则梯度为
$\nabla J(\theta)=\begin{bmatrix} \frac {\partial J} {\partial \theta_1} & \frac {\partial J} {\partial \theta_2} & \frac {\partial J} {\partial \theta_3}\end{bmatrix} =\begin{bmatrix}-3 &4 & -5 \end{bmatrix}$

梯度下降算法步骤

算法步骤：

给定目标函数 $f(x)$ 和初始点位置 $x_0$

计算梯度，取反表示沿逆梯度方向。 $\Delta x_t=-\nabla f(x_t)$
计算下一处的值：每次参数移动的幅度是 $\sigma$ ，称为学习率。更新后的参数 $x_{t+1}=x_t+\sigma \cdot\Delta x_t$
重复1、2，直至 $|\Delta x_t| <\epsilon$ ，其中 $\epsilon$ 是预先设置一个很小的值，满足条件时结束。

$eg:$

函数 $J(w)=w^2$ ，它的梯度计算公式为 $\nabla = 2\cdot w$ 初始位置 $w=10$ ，使用梯度下降计算极小值。其中学习率0.2。

计算过程如下

轮数	当前参数值 $w$	梯度取反 $\Delta w_t=-2w$	更新后的参数值 $w_t+\sigma \cdot \Delta w_t$
1	10	-20	6.0
2	6.0	-12.0	3.6
3	3.6	-7.2	2.16
4	2.16	-4.32	1.296
5	1.296	-2.592	0.7776
6	0.7776	-1.5552	0.466560
7	0.466560	-0.933120	0.279936
8	0.279936	-0.559872	0.167962
9	0.167962	-0.335923	0.100777
10	0.100777	-0.201554	0.060466

几种梯度下降算法

批梯度下降 batch gradient descent (BGD)

在每次参数更新时使用全部的样本数据， $\theta_i = \theta_i - \alpha\sum\limits_{j=0}^{m}(h_\theta(x_0^{(j)}, x_1^{(j)}, ...x_n^{(j)}) - y_j)x_i^{(j)}$ ，优点是充分利用了全部数据，保证在足够多的的迭代后可以达到最优，缺点是数据量过大时迭代十分缓慢，收敛速度很慢。

随机梯度下降 stochastic gradient descent (SGD)

与BGD不同在于，每次使用一个样本用于更新参数。 $\theta_i = \theta_i - \alpha (h_\theta(x_0^{(j)}, x_1^{(j)}, ...x_n^{(j)}) - y_j)x_i^{(j)}$ 。优点是一次训练一个样本速度快，但一个样本决定梯度方向，可能导致解不是最优，而且每次样本方向变化大，不容易很快收敛到最优解或局部最优解。

小批量梯度算法 Mini-batch gradient descent

每次使用一部分样本用于更新参数，即batch_size。对一个总样本数据m的数据集，每次使用x个样本，更新公式为 $\theta_i = \theta_i - \alpha \sum\limits_{j=t}^{t+x-1}(h_\theta(x_0^{(j)}, x_1^{(j)}, ...x_n^{(j)}) - y_j)x_i^{(j)}$

batch_size=1时，即为SGD的情况，batch_size=m时，即为BGD的情况。

梯度下降的缺陷

图片出自《深度学习与计算机视觉、算法原理、框架与代码实现》

1562770424938.png

函数的特殊点。从梯度下降的步骤来看，根据梯度的方向判断参数移动的方向，但是当 $J'(w)=0$ 的时候，就无法判断往哪边移动。称 $J'(w)=0$ 的点为驻点或者临界点。

函数会出现存在梯度为0的临界点，但该点不是最小点也不是最大点，这种临界点称为鞍点（Saddle Point）。

函数在某一段区域，梯度很小，且范围很大，梯度值小于更新条件，此时算法可能会停止迭代，这种区域称为停滞区。

极小值的存在，也会使算法停止迭代，从而得到不准确的结果，陷入局部最优解的情况。

因此，梯度下降算法的缺陷在于鞍点、停滞区、极小值的存在。

梯度下降算法通常适用于凸函数的情况。

梯度下降算法的改进

冲量momentum

算法步骤：

给定目标函数 $f(x)$ 和初始点位置 $x_0$

计算梯度，取反表示沿逆梯度方向。 $\Delta x_t=-\nabla f(x_t)$
计算下一处的值：设置一个冲量项， $V_{t+1}=\gamma v_t + \eta \Delta x_t$ ，更新后的参数为 $x_{t+1}=x_t+v_{t+1}$
重复1、2。

与原始梯度下降算法不一样的是，更新参数时，考虑到一个冲量，且冲量每次迭代时要乘以衰减数。在冲量项的影响下，算法迭代就相当于带上了“惯性”，前次迭代位置前进的方向可以影响到下一次迭代。这样当算法经过鞍点或是停滞区时，就不至于停下来做过于缓慢的迭代，而经过并不是很“深”的极值时，就可以借助冲量项带来的“惯性”冲出极值所的“坑”

算法停止的的标准也不再是梯度小于一个阈值。停止算法的标准可以是冲量小于某个值，梯度小于某个值，或是用户给定一个次数就停止。

Nesterov Accelerated Gradient Descent (NAG方法)

与加入冲量的改进唯一不同是，计算梯度的位置，不是当前位置 $x_t$ ，而是沿当前冲量前进一步的位置。

给定目标函数 $f(x)$ 和初始点位置 $x_0$ ，以及初始动量 $v_0$

计算梯度，取反表示沿逆梯度方向。 $\Delta x_t=-\nabla f(x_t+\gamma v_t)$
计算下一处的值：设置一个冲量项， $V_{t+1}=\gamma v_t + \eta \Delta x_t$ ，更新后的参数为 $x_{t+1}=x_t+v_{t+1}$
重复1、2。

1562773584951.png

反向传播算法（ BackPropagation算法 BP)

此部分参考了一篇博客，https://www.cnblogs.com/charlotte77/p/5629865.html，写的超级详细，跟着走了一遍过程，很容易理解反向传播的计算过程。

此外，参考《机器学习》的BP算法步骤，总结很简练，但没有具体数据去实现，看着很抽象。

算法的主要思想：

数据集输入神经网络，经过隐藏层，最终达到输出层。该过程是前向传播过程。
计算输出结果与真实结果存在误差，因此计算出误差，并将该误差从输出层向隐藏层反向传播，直至传播到输入层。
在反向传播的过程中，根据误差调整各种参数的值；不断迭代上述过程，直至收敛

$eg:$ 以下图为例，使用BP算法更新各层参数。

1562835182331.png

输入 $(0.05，0.1)$ 计算各级的输出：

隐藏层输入 $h1_{in}=w_{11}^1*x_1 +w_{21}^1*x_2+b_{11}^1=0.15*0.05+0.2*0.1+0.35=0.3775$

输入 $h2_{in}=w_{12}^1*x_1 +w_{22}^1*x_2+b_{12}^1=0.25*0.05+0.3*0.1+0.35=0.3925$

隐藏层输出： $h1_{out}=sigmoid(h1_{in})=0.59326999211$ $h2_{out}=sigmoid(h2_{in})=0.596884378259767$

隐藏层到输出层：

神经元 $y_1$ 的输入输出是[1.10590596705977 0.7513650695523157]

神经元 $y_2$ 的输入输出是[1.2249214040964653 0.7729284653214625]

因此，前向传播的输出结果是 $\begin{bmatrix} 0.7513650695523157 & 0.7729284653214625 \end{bmatrix}$ 而真实值是 $\begin{bmatrix} 0.01 & 0.99 \end{bmatrix}$

计算前向传播的结果与真实值的误差，使用均方误差

$E_k = \frac 1 2 \sum_i (y_{predict}-y_{truth}) ^2$

根据公式，可以算出总误差值 $E_k = \frac 1 2 ((0.7513650695523157-0.01)^2+(0.7729284653214625-0.99)^2)=0.2983711087600027$

反向传播，更新参数。

1562838188147.png

误差的公式
$MSE = \frac 1 2 [(y1_{out}-y1_{truth})^2+(y2_{out}-y2_{truth})^2] 其中y1_{truth}、y2_{truth}都是常量$

误差公式中只有输出值是变量，每个输出值又是通过各个路径的参数“复合”而来，看成一个复合函数。以输出y1为例： $y1_{out} = sigmoid(y1_{in})=sigmoid(h1_{out}*w_5+h2_{out}*w_6+b21)$ ，而 $h1_{out}、h2_{out}$ 等又可以推向输出层。 $h1_{out}=sigmoid(h1_{in})=sigmoid(x_1*w1+x2*w2+b_{11})$

故
$y1_{out} = sigmoid(y1_{in})=sigmoid(h1_{out}*w_5+h2_{out}*w_6+b_{21})\\=sigmoid(sigmoid(h1_{in})*w5+sigmoid(h2_{in})*w_6+b_{21})\\ =sigmoid(sigmoid(x_1*w1+x2*w2+b_{11})*w_5+sigmoid(x_1*w_3+x_2*w_4+b_{12})+b_{21})$

计算误差与某个参数 $w$ 的偏导，使用链式法则求偏导。

从输出层到隐藏层的参数

例如计算 $w_5$ 对最终损失的影响，偏导公式如下。没有考虑 $y2_{out}$ ，因为 $y2$ 的传播路径与 $w5$ 无关。
$\frac {\partial} {\partial w_5}MSE=\frac {\partial MSE} {\partial y1_{out}}*\frac {\partial y1_{out}} {\partial y1_{in}}*\frac {\partial y1_{in}} {\partial w_5}$

依次计算该公式的各个部分的值。

$MSE$ 对 $y1_{out}$ 的偏导，
$\frac {\partial MSE} {\partial y1_{out}}=\frac {\partial\frac 1 2 [(y1_{out}-y1_{truth})^2+(y2_{out}-y2_{truth})^2] } {\partial y1_{out}}=y1_{out}-y1_{truth}=0.74136507$

$y1_{out}$ 对 $y1_{in}$ 的偏导，sigmoid函数的导数公式是 $f'(x)=f(x)*(1-f(x))$ 。

根据计算式 $y1_{out}=sigmoid(y1_{in})$ 可以算出
$\frac {\partial y1_{out}} {\partial y1_{in}}=y1_{out}*(1-y1_{out})=0.75136507*(1-0.75136507)=0.1868156016$
$y1_{in}$ 对 $w_5$ 的偏导，计算式 $y1_{in}=h1_{out}*w_5+h2_{out}*w_6+b_{21}$ ，可以算出
$\frac {\partial y1_{in}} {\partial w_5}=h1_{out}=0.59326999211$
最后将三者乘起来，得到
$\frac {\partial} {\partial w_5}MSE =0.74136507*0.1868156016*0.59326999211=0.08216704052233154$
更新 $w_5$ 的值， $w_5=w_5 - \sigma * \frac {\partial} {\partial w_5}MSE=0.4-0.5*0.08216704052233154=0.3589164797388342$

其中 $\sigma$ 是学习率，更新公式和梯度下降算法一样。

总误差对 $w_5$ 的偏导： $(y1_{out}-y1_{truth})*[y1_{out}*(1-y1_{out})]*h1_{out}$

同理可得对 $w_6、w_7、w_8$ 的偏导。
$\frac {\partial} {\partial w_6}MSE =(y1_{out}-y1_{truth})*[y1_{out}*(1-y1_{out})]*h2_{out}=0.0826676278049868\\ \frac {\partial} {\partial w_7}MSE =(y2_{out}-y2_{truth})*[y2_{out}*(1-y2_{out})]*h1_{out}=-0.02260254047747507\\ \frac {\partial} {\partial w_8}MSE =(y2_{out}-y2_{truth})*[y2_{out}*(1-y2_{out})]*h2_{out}=-0.022740242215978222$
更新后的参数
$w_6 = w_6 - \sigma * \frac {\partial} {\partial w_6}MSE=0.4086661860975066\\ w_7 = w_7 - \sigma * \frac {\partial} {\partial w_7}MSE=0.5113012702387375$

偏置更新： $y1_{out}=sigmoid(y1_{in})$ ， $y1_{in}$ 中的偏置项只有一项，偏导是1。因此复合后的结果是 $\frac {\partial} {\partial b_{21}}MSE =y1_{out}*(y1_{out}-y1_{out})$
$b_{21}=b_{21}- \sigma * [y1_{out}*(1-y1_{out})] = 0.6-0.5*0.1868156016=0.5065921992\\ b_{22}=b_{22}- \sigma * [y2_{out}*(1-y2_{out})] = 0.6-0.5*0.1755100528=0.5122449736$

从隐藏层到输入层的参数更新

以 $w_1$ 为例，但是与上面不同的是， $w_1$ 会影响到全部的输出，因为它通过 $h_1、w_5、w_7$ 传播到两个输出y，因此会有两个误差。(这段公式老是报错。。。只好贴图了)

image.png

1562858618013.png

如上图绿色箭头，每个神经元被分为两块，左边表示输入in，右边表示输出out，绿色表示反向传播的路径，截止到w1，可以看到，损失对w1的偏导，分为两条路径，但两条路径有部分是共用，即 $h1_{out}$ 反向传播到输入层的部分。

公式（19）的计算过程如下，可以发现部分运算值已经在上面的w5到w8部分更新过一次。
$\frac {\partial MSE} {\partial y1_{out}}*\frac {\partial y1_{out}} {\partial y1_{in}}= [\frac {\partial\frac 1 2 [(y1_{out}-y1_{truth})^2+(y2_{out}-y2_{truth})^2] } {\partial y1_{out}}] [y1_{out}*(1-y1_{out})]\\=0.74136507*[0.75136507*(1-0.75136507)] =0.13849856154533652$
而
$\frac {\partial y1_{in}} {\partial h1_{out}}=w_5=0.4，因为y1_{in}是线性叠加而来，与h1有关的边只有w_5$
同理可以算出
$\frac {\partial MSE} {\partial y2_{out}}*\frac {\partial y2_{out}} {\partial y2_{in}}= (y2_{out}-y2_{truth})*(y2_{out}*(1-y2_{out}))=-0.038098236516556236$
而
$\frac {\partial y2_{in}} {\partial h1_{out}}=w_7=0.5，因为y2_{in}是线性叠加而来，与h1有关的边只有w_7$
从而，公式（19）的括号里的值，计算结果是
$0.13849856154533652*0.4-0.038098236516556236*0.5=0.03635030635985649$
计算 $h1_{out}$ 到 $w_1$ 的偏导。从 $h1_{out}$ 到 $h1_{in}$ ，是一个sigmoid函数，而 $h1_{in}$ 到输入是线性叠加，与 $w_1$ 有关的项是 $w1*x1$ ，因此 $h1_{in}$ 对于 $w_1$ 的偏导是 $x_1$
$\frac {\partial h1_{out}} {\partial h1_{in}}*\frac {\partial h1_{in}} {\partial w_{1}}=h1_{out}*(1-h1_{out})*x_1=0.012065035428616262$
综上， $\frac {\partial} {\partial w_1}MSE=0.012065035428616262*0.03635030635985649=0.0004385677340727236$

更新 $w_1$ 的值， $w_1=w_1 - \sigma*\frac {\partial} {\partial w_1}MSE=0.14978071613296362$

同理，计算对 $w_2$ 的偏导。可以看到与计算 $w_1$ 不同的传播路径在于隐藏层到输入层是连接到 $x_2$ 这个神经元，因此

$\frac {\partial} {\partial w_2}MSE=h1_{out}*(1-h1_{out})*x_2*0.03635030635985649=0.0008771354681454472$

更新后w2的值是 $w_2=0.1995614322659273$

同理计算w3和w4
$\frac {\partial} {\partial w_3}MSE=(\frac {\partial MSE} {\partial y1_{out}}*\frac {\partial y1_{out}} {\partial y1_{in}}*\frac {\partial y1_{in}} {\partial h2_{out}}+ \frac {\partial MSE} {\partial y2_{out}}*\frac {\partial y2_{out}} {\partial y2_{in}}*\frac {\partial y2_{in}} {\partial h2_{out}})*\frac {\partial h2_{out}} {\partial h2_{in}}*\frac {\partial h2_{in}} {\partial w_3}\\ =[(y1_{out}-y1_{truth})*(y1_{out}*(1-y1_{out}))*w_6+(y2_{out}-y2_{truth})*(y2_{out}*(1-y2_{out}))*w8]*\\(h2_{out}*(1-h_2{out}))*x1=0.0004977127352608601$

更新后 $w_3=0.24975114363236958$

$w4与w3$ 也只有隐藏层反向到输出的位置不同，对 $w_4的偏导为0.0009954254705217202$ ，更新后 $w_4=0.29950228726473915$

$b_{11}= 0.34998903580664814\\ b_{12}=0.3450228726473914$

全部更新一轮后的输出结果为 $\begin{bmatrix} 0.7237123710461725 & 0.7595051820170899 \end{bmatrix}$ ，损失由0.29837110876000270变降低到0.2812566048506621

总结：

这部分内容，在书上都放在了神经网络的优化方法部分。神经网络的训练实际上就是通过不断的训练，通过某种算法更新网络各个层级的权重参数，从而使损失函数降低。
梯度下降是通过函数的梯度性质来求解函数最小值，当然优缺点也很明显。除了梯度下降，还有牛顿-拉普森法、Adam法等很多其他优化算法。
而反向传播算法，是针对神经网络逆向优化所有参数，达到一个全局最优的解。

笔记（二）梯度下降与反向传播算法