key_technologies_in_AI
AI中的关键技术——自动微分和误差反向传播算法
1. 自动微分
自动微分(Automatic Differentiation,AD)是一种可以对一个函数进行计算导数的方法。符号微分的处理对象是数学表达式,数值微分处理的对象是数值,而自动微分的处理对象是一个函数或一段程序,它介于数值微分和符号微分之间的方法,采用类似有向图的计算来求解微分值。
所有的数值计算可以分解为一些基本操作,包含+,-,×,÷和一些初等函数exp, log, sin, cos等,然后利用链式法则来自动计算一个复合函数的梯度。
自动微分的基本流程:首先对基本算子(函数)应用符号微分方法,将复杂函数分解为一些基本算子(函数),包含+,-,×,÷和一些初等函数exp,log,sin,cos等;其次带入数值进行计算,保留中间结果;最后通过链式法则将中间结果应用于整个函数来自动计算一个复合函数的梯度,这样可以做到完全向用户隐藏微分求解过程,也可以灵活于编程语言的循环结构、条件结构等结合起来。
以如下的抽象函数为例:
$$y=f(g(h(x)))=f(g(h(v_{0})))=f(g(v_{1}))=f(v_{2})=v_{3}$$
其中:
$$v_{0}=x \ v_{1}=h(v_{0}) \ v_{2}=g(v_{1}) \ v_{3}=f(v_{2})$$
然后把这些新变量作为节点,依据运算逻辑把公式整理出一张计算图(Computational Graph),一般是有向无环图(DAG),数据正向传播,计算出中间节点,并记录计算图中的节点依赖关系。因此,自动微分可以被认为是将一个复杂的数学运算过程分解为一系列简单的基本运算,其中每一项基本运算都可以通过查表得出来。
当前比较流行的自动微分实现方式有三种,分别为基本表达式、操作符重载和源代码变换:
- 基本表达式
基本表达式或称元素库(Elemental Libraries),基于元素库中封装一系列基本的表达式(如:加减乘除等)及其对应的微分结果表达式,作为库函数。
用户通过调用库函数构建需要被微分的程序。而封装后的库函数在运行时会记录所有的基本表达式和相应的组合关系,最后使用链式法则对上述基本表达式的微分结果进行组合完成自动微分。
- 操作符重载
操作符重载或称运算重载(Operator Overloading,OO),利用现代语言的多态特性(例如C++/JAVA/Python等高级语言),使用操作符重载对语言中基本运算表达式的微分规则进行封装。
同样,重载后的操作符在运行时会记录所有的操作符和相应的组合关系,最后使用链式法则对上述基本表达式的微分结果进行组合完成自动微分。
- 源代码变换
源代码变换或称源码转换(Source Code Transformation,SCT)则是通过对语言预处理器、编译器或解释器的扩展,将其中程序表达(如:源码、AST抽象语法树 或 编译过程中的中间表达 IR)的基本表达式微分规则进行预定义,再对程序表达进行分析得到基本表达式的组合关系。
最后使用链式法则对上述基本表达式的微分结果进行组合生成对应微分结果的新程序表达,完成自动微分。
这里以一个神经网络中常见的复合函数为例,采用基本表达式的实现方法,说明自动微分过程:
$$f(x,w,b)=\frac{1}{e^{-(wx+b)}+1}$$
$x,w,b$均为标量
$$v_{0}=x \ v_{1}=w \ast v_{0} \ v_{2}=v_{1}+b \ v_{3}= -1 \ast v_{2} \ v_{4} = e^{v_{3}} \ v_{5} = v_{4}+1 \ v_{6}=\frac{1}{v_{5}}$$
构建计算图如下:
导数表:
自动微分计算模式:按照计算导数的顺序,自动微分可以分为两种模式:前向模式和反向模式
计算过程:
-
先进行前向传播,计算出所有中间变量$v_{0} \sim v_{6}$,并保存起来;
-
选择自动微分计算模式(前向\后向),根据计算图和导数表计算每个节点的导数;
-
将计算图中变量相关路径上的所有导数连乘起来,即:
$$\frac{\partial f(x;w,b)}{\partial x}=\frac{\partial f(x;w,b)}{\partial v_{6}}\frac{\partial v_{6}}{\partial v_{5}}\frac{\partial v_{5}}{\partial v_{4}}\frac{\partial v_{4}}{\partial v_{3}}\frac{\partial v_{3}}{\partial v_{2}}\frac{\partial v_{2}}{\partial v_{1}}\frac{\partial v_{1}}{\partial v_{0}}\frac{\partial v_{0}}{\partial v_{x}}$$
$$\frac{\partial f(x;w,b)}{\partial w}=\frac{\partial f(x;w,b)}{\partial v_{6}}\frac{\partial v_{6}}{\partial v_{5}}\frac{\partial v_{5}}{\partial v_{4}}\frac{\partial v_{4}}{\partial v_{3}}\frac{\partial v_{3}}{\partial v_{2}}\frac{\partial v_{2}}{\partial v_{1}}\frac{\partial v_{1}}{\partial w}$$
$$\frac{\partial f(x;w,b)}{\partial b}=\frac{\partial f(x;w,b)}{\partial v_{6}}\frac{\partial v_{6}}{\partial v_{5}}\frac{\partial v_{5}}{\partial v_{4}}\frac{\partial v_{4}}{\partial v_{3}}\frac{\partial v_{3}}{\partial v_{2}}\frac{\partial v_{2}}{\partial b}$$
如果参数有多个相关路径,那么将多个路径相乘的结果再相加即最终的导数。
计算图类型:
2. 误差反向传播算法
误差反向传播(error BackPropagation,BP)是1986年由Rumelhart和McClelland为首的科学家提出的概念,是一种按照误差逆向传播算法训练的多层前馈神经网络,误差反向传播算法系统的解决了多层神经网络隐含层连接权学习问题,它是迄今最成功的神经网络学习算法。现实任务中使用神经网络时,一般会使用梯度下降法进行参数学习,常使用误差反向传播来高效地计算梯度。下面就以前馈神经网络为例,介绍误差反向传播算法。
介绍反向传播之前就要下说明一下正向传播:
回顾一下单个神经元模型的结构:
单个神经元符号表:
输入$\boldsymbol{x}=\begin{bmatrix} x_{1}&x_{2}&...&x_{i}\end{bmatrix}$,权重$\boldsymbol{w}=\begin{bmatrix} w_{1}&w_{2}&...&w_{i}\end{bmatrix}$,偏置为$b$设激活函数$\sigma$为sigmoid函数,输出为$\hat{y}$正向传播计算过程有:
$$z=\sum w_{i}x_{i} +b=\boldsymbol{w} \boldsymbol{x}^{T}+b \ a = \sigma (z) = sigmoid(z)$$
假设标签值为$y$,设损失为L2-loss:$\mathcal{L}(\hat{y})=(y-\hat{y})^{2}$,相应的反向传播求梯度过程如下:
$$\frac{\partial \mathcal{L}(\hat{y})}{\partial a}=2 \ast (y-\hat{y})$$
$$\frac{\partial a}{\partial z}= \sigma^{'}(z)=sigmoid^{'}(z)=z \ast (1-z)$$
$$\delta = \frac{\partial \mathcal{L}(\hat{y})}{\partial z}=\frac{\partial \mathcal{L}(\hat{y})}{\partial a}\frac{\partial a}{\partial z}$$
$$\frac{\partial z}{\partial \boldsymbol{x}}=\boldsymbol{w}$$
$$\frac{\partial z}{\partial \boldsymbol{w}}=\boldsymbol{x}$$
$$\frac{\partial z}{\partial \boldsymbol{b}}=1$$
$$\Delta \boldsymbol{x} = \frac{\partial \mathcal{L}(\hat{y})}{\partial \boldsymbol{x}}=\frac{\partial \mathcal{L}(\hat{y})}{\partial a} \frac{\partial a}{\partial z} \frac{\partial z}{\partial \boldsymbol{x}}=2 \ast (y- \hat{y}) \ast z \ast (1-z) \ast \boldsymbol{w}$$
$$\Delta \boldsymbol{w} = \frac{\partial \mathcal{L}(\hat{y})}{\partial \boldsymbol{w}}=\frac{\partial \mathcal{L}(\hat{y})}{\partial a} \frac{\partial a}{\partial z} \frac{\partial z}{\partial \boldsymbol{w}}=2 \ast (y-\hat{y}) \ast z \ast (1-z) \ast \boldsymbol{x}$$
$$\Delta b = \frac{\partial \mathcal{L}(\hat{y})}{\partial b} = \frac{\partial \mathcal{L}(\hat{y})}{\partial a} \frac{\partial a}{\partial z} \frac{\partial z}{\partial b}=2 \ast (y-\hat{y}) \ast z \ast (1-z)$$
其中$\delta = \frac{\partial \mathcal{L}(\hat{y})}{\partial z}$称为误差项,表示该层神经元对最终损失的影响,换言之,也反映了最终损失对这一层神经元的敏感程度,因此称为误差项。
如果要进行参数更新的话那么就可以用下面的公式:
$$\boldsymbol{w} \leftarrow \boldsymbol{w} -\eta \Delta \boldsymbol{w} \ b \leftarrow b - \eta \Delta b$$
通过上面一个简单神经元的例子,我们对前向传播和反向传播有了一个直观的印象,可以发现链式法则是反向传播的主要数学工具,误差项是另外一个重要的概念,用$\delta$表示,下面将通过多隐含层前馈神经网络来详细介绍误差反向传播算法。
前馈神经网络结构图如下:
前馈神经网络符号表:
假设使用梯度下降法进行参数学习,给定一个样本$(\boldsymbol{x},\boldsymbol{y})$,网络得到的输出为$\boldsymbol{\hat{y}}$,设损失函数为$\boldsymbol{\mathcal{L}}(\hat{\boldsymbol{y}})$,为了不失一般性,设第$l$层的权重矩阵$\boldsymbol{W}^{(l)}$和偏置向量$\boldsymbol{b}^{(l)}$以及激活函数$\sigma_{l}$。
其中:
$$\boldsymbol{x} = \begin{bmatrix}x_{1} & \dots &x_{i} & \dots & x_{N_{0}} \end{bmatrix}$$
$$\boldsymbol{y} = \begin{bmatrix}y_{1} & \dots &y_{i} & \dots & y_{N_{L}} \end{bmatrix}$$
$$\boldsymbol{\hat{y}} = \begin{bmatrix} \hat{y}{1} & \dots & \hat{y}{i} & \dots & \hat{y}{N{L}} \end{bmatrix}$$
$$\boldsymbol{W^{(l)}} = \begin{bmatrix}w_{11} & w_{12} & \dots & w_{1N_{l-1}} \ w_{21} & w_{22} & \dots & w_{2N_{l-1}} \ \vdots & \vdots & \vdots & \vdots \ w_{N_{l}1} & w_{N_{l}2} & \dots & w_{N_{l}N_{l-1}} \end{bmatrix}$$
$$\boldsymbol{b}^{(l)} = \begin{bmatrix}b_{1}^{(l)} & \dots & b_{i}^{(l)} & \dots & b_{N_{l}}^{(l)} \end{bmatrix}$$
$$i \in \mathbb{R}^{N_{l}}$$
$$j \in \mathbb{R}^{N_{l-1}}$$
参数学习需要计算每个参数对最终损失地梯度,假设要更新第$l$层参数,那么我们需要求出每个参数地偏导数,即:$\frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial w_{ij}^{(l)}}$和$\frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial b_{i}^{(l)}}$。
通过单个神经元中反向传播过程介绍,根据链式法则我们可以得到:
$$\frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial w_{ij}^{(l)}} = \frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial \boldsymbol{z}^{(l)}}\frac{\partial \boldsymbol{z}^{(l)}}{\partial w_{ij}^{(l)}} = \delta^{(l)} \ast \frac{\partial \boldsymbol{z}^{(l)}}{\partial w_{ij}^{(l)}}$$
$$\frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial b_{i}^{(l)}} = \frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial \boldsymbol{z}^{(l)}}\frac{\partial \boldsymbol{z}^{(l)}}{\partial b_{i}^{(l)}} = \delta^{(l)} \ast \frac{\partial \boldsymbol{z}^{(l)}}{\partial b_{i}^{(l)}}$$
观察上面式子我们可以发现,只需要计算$\frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial \boldsymbol{z}^{(l)}}$、$\frac{\partial \boldsymbol{z}^{(l)}}{\partial w_{ij}^{(l)}}$和$\frac{\partial \boldsymbol{z}^{(l)}}{\partial b_{i}^{(l)}}$即可。
- 计算$\frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial \boldsymbol{z}^{(l)}}$,即$\delta^{(l)} \in \mathbb{R}^{N_{l}}$。
根据第$l$层与第$l+1$层之间的关系,有$\boldsymbol{z}^{(l+1)} = \boldsymbol{{W}^{(l+1)}}\boldsymbol{{a}^{(l)}}+ \boldsymbol{{b}^{(l+1)}}$,故有:
$$\frac{\partial \boldsymbol{z}^{(l+1)}}{\partial \boldsymbol{a}^{(l)}} = (\boldsymbol{W}^{(l+1)})^{T} \in \mathbb{R}^{N_{l} \ast N_{l+1}}$$
又因为$\boldsymbol{a}^{(l)} = \boldsymbol{\sigma}_{l}(\boldsymbol{z}^{(l)})$,故有:
$$\frac{\partial \boldsymbol{a}^{(l)}}{\partial \boldsymbol{z}^{(l)}} = \frac{\partial \boldsymbol{\sigma}{l}(\boldsymbol{z}^{(l)})}{\partial \boldsymbol{a}^{(l)}} = diag(\boldsymbol{\sigma}{l}^{'}(\boldsymbol{z}^{(l)})) \in \mathbb{R}^{N_{l} \ast N_{l}}$$
由链式求导法则有:
$$\delta^{(l)} = \frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial \boldsymbol{z}^{(l)}} = \frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial \boldsymbol{z}^{(l+1)}} \frac{\partial \boldsymbol{z}^{(l+1)}}{\partial \boldsymbol{a}^{(l)}} \frac{\partial \boldsymbol{a}^{(l)}}{\partial \boldsymbol{z}^{(l)}} = \delta^{(l+1)} \ast (\boldsymbol{W}^{(l+1)})^{T} \ast diag(\boldsymbol{\sigma}{l}^{'}(\boldsymbol{z}^{(l)})) \in \mathbb{R}^{N{l}}$$
> 上面的式子就体现了误差反向传播的思想,第$l+1$层的误差项可以反向传播给第$l$层。
- 计算$\frac{\partial \boldsymbol{z}^{(l)}}{\partial w_{ij}^{(l)}}$。
根据第$l$层与第$l-1$层之间的关系,有$\boldsymbol{z}^{(l)} = \boldsymbol{{W}^{(l)}}\boldsymbol{{a}^{(l-1)}}+ \boldsymbol{{b}^{(l)}}$,且${w}{ij}^{(l)}$是${z}{i}^{(l)}$的函数,即${z}{i}^{(l)} = \boldsymbol{w}{i:}^{(l)} \boldsymbol{a}^{(l-1)} + b_{i}^{(l)})$,故有:
$$\begin{aligned} \frac{\partial \boldsymbol{z}^{(l)}}{\partial {w}{ij}^{(l)}} &= \begin{bmatrix} \frac{\partial z{1}^{(l)}}{\partial {w}{ij}^{(l)}} & \dots & \frac{\partial z{i}^{(l)}}{\partial {w}{ij}^{(l)}} & \dots & \frac{\partial z{N_{l}}^{(l)}}{\partial {w}{ij}^{(l)}} \end{bmatrix} \ &= \begin{bmatrix} 0 & \dots & \frac{\partial (\boldsymbol{w}{i:}^{(l)} \boldsymbol{a}^{(l-1)} + b_{i}^{(l)})}{\partial {w}{ij}^{(l)}} & \dots & 0 \end{bmatrix} \ &= \begin{bmatrix} 0 & \dots & {a}{j}^{(l-1)} & \dots & 0 \end{bmatrix} \in \mathbb{R}^{1 \ast N_{l}} \end{aligned}$$
其中$\boldsymbol{w}_{i:}^{(l)}$为$\boldsymbol{W}^{(l)}$的第$i$行。
- 计算$\frac{\partial \boldsymbol{z}^{(l)}}{\partial b_{i}^{(l)}}$。
第$l$层有$\boldsymbol{z}^{(l)} = \boldsymbol{{W}^{(l)}}\boldsymbol{{a}^{(l-1)}}+ \boldsymbol{{b}^{(l)}}$,且$b_{i}^{(l)}$是${z}{i}^{(l)}$的函数,即${z}{i}^{(l)} = \boldsymbol{w}{i:}^{(l)} \boldsymbol{a}^{(l-1)} + b{i}^{(l)})$,故有:
$$\frac{\partial \boldsymbol{z}^{(l)}}{\partial b_{i}^{(l)}} = \begin{bmatrix} \frac{\partial z_{1}^{(l)}}{\partial b_{i}^{(l)}} & \dots & \frac{\partial z_{i}^{(l)}}{\partial b_{i}^{(l)}} & \dots & \frac{\partial z_{N_{l}}^{(l)}}{\partial b_{i}^{(l)}} \end{bmatrix} = \begin{bmatrix} 0 & \dots & 1 & \dots & 0 \end{bmatrix} \in \mathbb{R}^{1 \ast N_{l}}$$
由上面的式子很自然的可以得到:
$$\frac{\partial \boldsymbol{z}^{(l)}}{\partial \boldsymbol{b}^{(l)}} = \boldsymbol{E}{N{l}} \in \mathbb{R}^{N_{l} \ast N_{l}}$$
其中$\boldsymbol{E}{N{l}}$是$N_{l} \ast N_{l}$的单位矩阵。
经过上面的计算结果,根据链式求导法则,可以计算$\frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial w_{ij}^{(l)}}$:
$$\begin{aligned} \frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial w_{ij}^{(l)}} &= \frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial \boldsymbol{z}^{(l)}}\frac{\partial \boldsymbol{z}^{(l)}}{\partial w_{ij}^{(l)}} \ &= \delta^{(l)} \ast \frac{\partial \boldsymbol{z}^{(l)}}{\partial w_{ij}^{(l)}} \ &= \begin{bmatrix} \delta_{1}^{(l)} & \dots & \delta_{i}^{(l)} & \dots & \delta_{N-{l}}^{(l)} \end{bmatrix}\begin{bmatrix} 0 & \dots & {a}{j}^{(l-1)} & \dots & 0 \end{bmatrix}^{T} \ &= \delta{i}^{(l)}{a}_{j}^{(l-1)} \in \mathbb{R}^{1} \end{aligned}$$
根据向量的外积(用$\otimes$表示)定义,那么$\boldsymbol{W}^{(l)}$的导数就可以直接计算了:
$$\frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial \boldsymbol{W}^{(l)}} = \delta^{(l)} \otimes \boldsymbol{a}^{(l-1)}= \begin{bmatrix} \delta_{1}^{(l)} \ \vdots \ \delta_{i}^{(l)} \ \vdots \ \delta_{N-{l}}^{(l)} \end{bmatrix}\begin{bmatrix} 0 & \dots & {a}{j}^{(l-1)} & \dots & 0 \end{bmatrix} = \begin{bmatrix} \delta{i}^{(l)}{a}{j}^{(l-1)} \end{bmatrix} \in \mathbb{R}^{N{l} \ast N_{l-1}}$$
同理,计算$\frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial \boldsymbol{b}^{(l)}}$结果如下:
$$\frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial \boldsymbol{b}^{(l)}} = \frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial \boldsymbol{z}^{(l)}}\frac{\partial \boldsymbol{z}^{(l)}}{\partial \boldsymbol{b}^{(l)}} = \delta^{(l)}\boldsymbol{E}{N{l}} = \delta^{(l)} \in \mathbb{R}^{N_{l}}$$
求得梯度后就可以进行参数更新了,令:
$$\Delta \boldsymbol{W}^{(l)} = \frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial \boldsymbol{W}^{(l)}}$$
$$\Delta \boldsymbol{b}^{(l)} = \frac{\partial \boldsymbol{\mathcal{L}}(\boldsymbol{\hat{y})}}{\partial \boldsymbol{b}^{(l)}}$$
那么就可以用下面的公式更新参数:
$$\boldsymbol{W}^{(l)} \leftarrow \boldsymbol{W}^{(l)} - \eta \Delta \boldsymbol{W}^{(l)} \ \boldsymbol{b}^{(l)} \leftarrow \boldsymbol{b}^{(l)} - \eta \Delta \boldsymbol{b}^{(l)}$$
总结一下误差反向传播算法,在实际训练中可以用下面的流程图表示:
在实际训练中可以用下面的伪代码表示: