机器学习基础-BP(Error Back Propagation)算法的数学原理

本文就 coursera 上斯坦福大学吴恩达教授的《机器学习》课程中的误差反向传播算法（Error Back Propagation）进行推导证明

明确一些记法

简单将神经网络的示意如下，有助于推导过程中理解，读者也可自己画出示意图:

本文沿用公开课中的符号记法：

• 用字母 $z$ 和 $a$ 分别表示每个神经元上的输入和输出；其上标 $^{(l)}$ 表示该神经元所在的层数，$L$ 表示神经网络的总层数；其下标 $_i$ 表示该神经元在该层的标号，并用 $S_l$ 表示第 $l$ 层神经元的总个数。
• 特别地，习惯用 $_k$ 下标表示输出层的神经元标号，$K$ 表示输出层神经元的总数，即 $S_L = K$
• 用希腊字母 $\boldsymbol\Theta$ 表示系数矩阵，它应该是一个三维矩阵。$\boldsymbol\Theta^{(l)}$ 表示第 $l$ 层的系数矩阵，它应该是一个 $S^{l+1} \times (S^l + 1)$ 矩阵。
• 用 $g(x)$ 表示 S 型函数（Sigmoid function）: $$g(x) = \frac1{1+e^{-x}},\ x \in R \tag{1.1}$$
• 且容易得： $$g'(x) = g(x)\left[1-g(x)\right] \tag{1.2}$$
• $\{\boldsymbol{x}^{(i)}, y^{(i)}\}$ 表示训练样本，当有多个训练样本时，用上标进行标号。并字母 $m$ 表示训练样本的总数。

需要注意，除了输出层外，每一层都应加入一个偏置项:

$$a^{(l)}_0 = 1,\ \ l = 1,2,\cdots,L-1$$

根据以上记法，有：

$$z^{(l)}_i = \sum\limits_{j=0}^{S_{l-1}}\Theta^{(l)}_{ij} a^{(l-1)}_j ,\ \ i = 1,2,\cdots S_l \tag{1.3}$$ $$\begin{aligned} &a^{(l)}_0 = 1, \\ &a^{(l)}_i = g(z^{(l)}_i),\ \ i = 1,2,\cdots S_l \end{aligned} \tag{1.4}$$

* 另外，文中一般使用粗体字母表示矩阵（或向量），如 $\boldsymbol x$，表示输入特征向量；常规字母表示实数，如 $x_1$ 表示向量 $\boldsymbol x$ 中的第一个元素，它是一个实数。（即使不关注这个区别，也应能从上下文区分出一个字母代表的是向量或实数）

目的

我们已经走得太远，以至于忘记了为什么而出发 ——纪伯伦$^{注1}$

我们要时刻记得我们想要得到什么，以至于当我们在进行复杂的推导过程中仍能清楚的知道每一步的意义，和接下来的方向。

BP 算法是神经网络参数训练的重要算法，其关键在于得到代价函数 $J(\boldsymbol\Theta)$ 对于每一个参数 $\Theta^{(l)}_{ij}$ 的偏导数，所以我们期望通过该算法，最终得到如下的内容：

$$\begin{aligned} \frac{\partial J}{\partial\Theta^{(1)}_{1\ 0}} &= \cdots \\ \frac{\partial J}{\partial\Theta^{(1)}_{1\ 2}} &= \cdots \\ &\cdots \\ \end{aligned} \tag{1.5}$$

有了这些导数值我们就可以利用梯度下降或其他经典算法，很容易地（调用库）对代价函数 $J(\boldsymbol\Theta)$ 进行最小化，以训练出合适的参数。

总而言之，我们的目的是得到一系列形如 $1.5$ 式的偏导。

代价函数

如何选取合适的代价函数呢？当我们观察神经网络的最后一层时，可以把它看作输入为 $\boldsymbol a^{(L-1)}$ 的 $K$ 分类问题。

便得到了神经网络的代价函数:

$$\begin{array}{r} J(\boldsymbol\Theta) =-\frac1m\sum\limits_{j=1}^m\sum\limits_{k=1}^K \left\{ y^{(j)}_kln\left(h_{\boldsymbol\theta}(\boldsymbol x^{(j)})\right)_k + \left(1-y^{(j)}_k\right) ln\left[1-\left(h_{\boldsymbol\Theta}(\boldsymbol x^{(j)})\right)_k\right] \right\}, \tag{3.1} \\ y_k^{(j)} = \mathbf I_k(y^{(j)}) = \begin{cases} 1, & y^{(j)} = k \\ 0, & y^{(j)} \not={k} \end{cases} \end{array}$$

其中 $h_{\boldsymbol\theta}(\boldsymbol x)$ 是一个 $K$ 维向量，$\Big(h_{\boldsymbol\theta}(\boldsymbol x)\Big)_k$ 就是每个样本所对应的第 $k$ 个输出值，即对每个样本来说都有：

$$\Big(h_{\boldsymbol\theta}(\boldsymbol x)\Big)_k = a^{(L)}_k \tag{3.2}$$

* 代价函数在不同的算法中可能有细微差别，在西瓜书的BP算法一节中使用了均方误差作为代价函数，其值约等于上述代价函数，并且反向传播的推导过程基本一致。

最后一层参数的偏导

为简化记法，我们先在只有一个样本 $\{\boldsymbol x, \boldsymbol y\}$ 的情况下推导。

由 $3.1$、$3.2$ 式知，此时代价函数为：

$$J(\boldsymbol\Theta) = -\sum\limits_{k=1}^K \left[ y_klna^{(L)}_k + (1-y_k)ln\left(1-a^{(L)}_k\right) \right],\ y_k = \mathbf{I}_k(\boldsymbol{y}) \tag{4.1}$$

由 $1.3$、$1.4$ 式，及复合函数求导法则，可得代价函数 $J(\boldsymbol\Theta)$ 对最后一层参数 $\boldsymbol\Theta^{(L-1)}$ 的偏导：

$$\frac{\partial J}{\partial\Theta^{(L-1)}_{ij}} = \frac{\partial J}{\partial a_i^{(L)}} \cdot \frac{\mathrm{d}a^{(L)}_i}{\mathrm{d}z^{(L)}_i} \cdot \frac{\partial z^{(L)}_i}{\partial \boldsymbol{\Theta}^{(L-1)}_{ij}} \tag{4.2}$$ $$$$

分别计算上式中的 3 项：

$$\frac{\partial J}{\partial a_i^{(L)}} = -\Big(\frac{y_i}{a^{(L)}_i} + \frac{y_i-1}{1-a^{(L)}_i}\Big) \tag{4.3}$$

由 $1.4$、$1.2$ 式可得:

$$\frac{\mathrm{d}a^{(L)}_i}{\mathrm{d}z^{(L)}_i} = a^{(L)}_i\left(1-a^{(L)}_i\right) \tag{4.4}$$

由 $1.3$ 式可得：

$$\frac{\partial z^{(L)}_i}{\partial \boldsymbol{\Theta}^{(L-1)}_{ij}} =a^{(L-1)}_j \tag{4.5}$$

将上述三式带回 $4.2$ 式，并化简，立即得：

$$\frac{\partial J}{\partial\Theta^{(L-1)}_{ij}} = (a^{(L)}_i - y_i)a^{(L-1)}_j \tag{4.6}$$

并且有,

$$\frac{\partial J}{\partial z^{(L)}_i} = \frac{\partial J}{\partial a_i^{(L)}} \cdot \frac{\mathrm{d}a^{(L)}_i}{\mathrm{d}z^{(L)}_i} = a^{(L)}_i - y_i \tag{4.7}$$

记

$$\delta^{(L)}_i = a^{(L)}_i - y_i \tag{4.8}$$

称为第 $L$ 层（输出层）第 $i$ 个神经元的“误差项”。

至此，我们便得到代价函数对最后一层参数的偏导:

$$\frac{\partial J}{\partial\Theta^{(L-1)}_{ij}} = \delta^{(L)}_i a^{(L-1)}_j \tag{4.9}$$

且有：

$$\frac{\partial J}{\partial z^{(L)}_i} = \delta^{(L)}_i \tag{4.10}$$

向前传播

下面求代价函数 $J(\boldsymbol\Theta)$ 对第 $L-2$ 层参数 $\boldsymbol\Theta^{(L-2)}$ 的偏导：

$$\frac{\partial J}{\partial\Theta^{(L-2)}_{ij}} \tag{5.1}$$

由 $1.3$、$1.4$ 式可得：

$$z^{(L)}_k = \sum\limits_{i=0}^{S_{L-1}} \boldsymbol \Theta^{(L-1)}_{ki} a^{(L-1)}_i \tag{5.2}$$ $$a^{(L-1)}_i = g(z^{(L-1)}_i), \ i \not ={0} \tag{5.3}$$ $$z^{(L-1)}_i = \sum\limits_{j=0}^{S_{L-2}} \boldsymbol \Theta^{(L-2)}_{ij} a^{(L-2)}_j \tag{5.4}$$

因此由上述 3 式知对于任意一个 $z^{(L)}_k$ 都是 $\Theta^{(L-2)}_{ij}$ 的函数；而 $J(\boldsymbol\Theta)$ 又是每一个 $z^{(L)}_k$ 的函数，所以有（画出神经网络图中相关的部分，结合图示更容易理解）：

$$\begin{aligned} \frac{\partial J}{\partial\Theta^{(L-2)}_{ij}} &= \sum\limits_{k=1}^{K}\frac{\partial J}{\partial z^{(L)}_k} \cdot \frac{\partial z^{(L)}_k}{\partial a^{(L-1)}_i} \cdot \frac{\mathrm{d}a^{(L-1)}_i}{\mathrm{d}z^{(L-1)}_i} \cdot \frac{\partial z^{(L-1)}_i}{\partial \boldsymbol \Theta^{(L-2)}_{ij}} \\ &= \frac{\partial J}{\partial z^{(L-1)}_i} \cdot \frac{\partial z^{(L-1)}_i}{\partial \boldsymbol \Theta^{(L-2)}_{ij}} \\ \end{aligned} \tag{5.5}$$

分别计算上式各导数项，得：

$$\frac{\partial J}{\partial\Theta^{(L-2)}_{ij}} = \sum\limits_{k=1}^{K} \delta^{(L)}_k \cdot \Theta^{(L-1)}_{ki} \cdot g'(z^{(L-1)}_i) \cdot a^{(L-2)}_j \tag{5.6}$$

记

$$\delta^{(L-1)}_i = \sum\limits_{k=1}^K \delta^{(L)}_k \cdot \Theta^{(L-1)}_{ki} \cdot g'(z^{(L-1)}_i) \tag{5.7}$$

表示第 $L-1$ 层第 $i$ 个神经元的“误差项”

则有：

$$\frac{\partial J}{\partial\Theta^{(L-2)}_{ij}} = \delta^{(L-1)}_i a^{(L-2)}_j \tag{5.8}$$

结合 $5.5$、$5.8$，同样有：

$$\frac{\partial J}{\partial z^{(L-1)}_i} = \delta^{(L-1)}_i \tag{5.9}$$

找出通式

至此，我们求得了代价函数对 $\boldsymbol\Theta^{(L)}$ 和 $\boldsymbol\Theta^{(L-1)}$ 的偏导，在继续对 $\boldsymbol\Theta^{(L-2)}, \cdots, \boldsymbol\Theta^{(1)}$ 求导前，先看看我们得到了哪些有趣的结果。

我们对前面两步得到的结果稍作整理，得到：

$$\delta_k^{(L)} = a_k^{(L)} - y_k = \frac{\partial J}{\partial z^{(l)}_k} \tag{6.1}$$ $$\delta^{(L-1)}_i = \sum\limits_{k=1}^K \delta^{(L)}_k \cdot \Theta^{(L-1)}_{ki} \cdot g'(z^{(L-1)}_i) = \frac{\partial J}{\partial z^{(L-1)}_i} \tag{6.2}$$ $$\frac{\partial J}{\partial\Theta^{(L-1)}_{ij}} = a^{(L-1)}_j\delta^{(L)}_i \tag{6.3}$$ $$\frac{\partial J}{\partial\Theta^{(L-2)}_{ij}} = a^{(L-2)}_j \delta^{(L-1)}_i \tag{6.4}$$

自然地，我们倾向于作出以下猜想：（如果你觉得这个猜想不够“自然”，可以继续求出$\frac{\partial J}{\partial\Theta^{(L-3)}_{ij}}$，再将结果放在一起比较，会发现做出这个猜想非常合理和自然）

假设一：若记：

$$\delta_k^{(L)} = a_k^{(L)} - y_k \tag{6.5}$$ $$\delta^{(l)}_j = \sum\limits_{i=1}^{S_{l+1}} \delta^{(l+1)}_i \Theta^{(l)}_{ij} g'(z^{(l)}_j) ,\ \ l\not=K \tag{6.6}$$

_则对任意 $z^{(l)}_j$ 和 $\Theta^{(l)}_{ij}$，有:_

$$\text{(1).}\ \ \frac{\partial J}{\partial z^{(l)}_j} = \delta^{(l)}_j, \tag{6.7}$$ $$\text{(2).}\ \ \frac{\partial J}{\partial\Theta^{(l)}_{ij}} = a^{(l)}_j \delta^{(l+1)}_i. \tag{6.8}$$

若该假设正确，我们便得到了反向逐层求解代价函数对参数的偏导的方法。

接下来证明该假设是否正确。

归纳证明

显然，我们得到的 $6.1-6.4$ 式已经证明了 $l=K$ 和 $l=K-1$ 时，假设一 的正确性。采用数学归纳法，假设当 $l=n<L$ 时上述 假设一 仍成立，即有：

$$\frac{\partial J}{\partial z^{(n+1)}_i} = \delta^{(n+1)}_i \tag{7.1}$$ $$\frac{\partial J}{\partial\Theta^{(n)}_{ij}} = a^{(n)}_j \delta^{(n+1)}_i \tag{7.2}$$

时，考察 $l=n-1$ 时假设的正确性。

由 $7.1$、$7.2$ 式，同 $5.5$ 式推导过程，有：

$$\begin{aligned} \frac{\partial J}{\partial\Theta^{(n-1)}_{ij}} &= \sum\limits_{t=1}^{S_{n+1}} \frac{\partial J}{\partial z^{(n+1)}_t} \cdot \frac{\partial z^{(n+1)}_t}{\partial a^{(n)}_i} \cdot \frac{\mathrm{d}a_i^{(n)}}{\mathrm{d}z^{(n)}_i} \cdot \frac{\partial z^{(n)}_i}{\partial\Theta^{(n-1)}_{ij}} \\ &= \frac{\partial J}{\partial z^{(n)}_i} \cdot \frac{\partial z^{(n)}_i}{\partial\Theta^{(n-1)}_{ij}} \end{aligned} \tag{7.3}$$

将 $7.1$ 式带入上式，并对剩余项逐项求导，得：

$$\frac{\partial J}{\partial\Theta^{(n-1)}_{ij}} = \sum\limits_{t=1}^{S_{n}} \delta^{(n+1)}_t\cdot \Theta^{(n)}_{ti} \cdot g'(z^{(n)}_i)\cdot a^{(n-1)}_j \tag{7.4}$$

结合 $7.3$、$7.4$ 及 $6.6$ 式便有：

$$\begin{aligned} \frac{\partial J}{\partial z^{(n)}_i} &= \sum\limits_{t=1}^{S_{n}} \delta^{(n+1)}_t\cdot \Theta^{(n)}_{ti} \cdot g'(z^{(n)}_i)\\ &= \delta^{(n)}_i \end{aligned} \tag{7.5}$$ $$\frac{\partial J}{\partial\Theta^{(n-1)}_{ij}} = a^{(n-1)}_j \delta^{(n)}_i \tag{7.6}$$

所以 假设一 对 $l=n-1$ 时也成立，由数学归纳法， 假设一 成立得证！

矩阵表示法

以上 假设一 的内容就是 BP 算法的核心内容，在更多情况下还可以使用矩阵来表示：

若记：

$$\begin{aligned} &\delta^{(L)}_k = a^{(L)}_k - y_k \\ &\boldsymbol\delta^{(l)} = \left(\boldsymbol\Theta^{(l)}\right)^T \times \boldsymbol\delta^{(l+1)} .* g'(\boldsymbol z^{(l)}), \ \ l \not=L \end{aligned} \tag{8.1}$$

（$.*$ 表示对对应元素逐个执行乘法运算），则有：

$$\frac{\partial J(\boldsymbol\Theta)}{\partial\boldsymbol\Theta^{(l)}} = \boldsymbol\delta^{(l+1)} \times \left(\boldsymbol{a^{(l)}}\right)^T \tag{8.2}$$

多样本的情况

在矩阵表示法的基础下，容易写出在 $m$ 个训练样本下 BP 算法的结论：

根据多样本下的代价函数（$3.1$ 式），以及假设一的结论 $8.1$、$8.2$ 式，有：

$$\frac{\partial J(\boldsymbol\Theta)}{\partial\boldsymbol\Theta^{(l)}} = \frac1m \sum\limits_{i=1}^m \left[ \boldsymbol\delta^{(l+1)} \times \left(\boldsymbol{a^{(l)}}\right)^T \right]_i \tag{8.3}$$

正则化

为了一定程度地防止过拟合的情况地发生，选取合适的 $\lambda$ 将正则项加入代价函数（$3.1$ 式），便得到：

$$\begin{aligned} J(\boldsymbol\Theta) &= -\frac1m\sum\limits_{j=1}^m\sum\limits_{k=1}^K \left\{ y^{(j)}_kln\left(h_{\boldsymbol\theta}(\boldsymbol x^{(j)})\right)_k + \left(1-y^{(j)}_k\right)ln\left[1-\left(h_{\boldsymbol\theta}(\boldsymbol x^{(j)})\right)_k\right] \right\} \\ &+ \frac\lambda{2m} \sum\limits_{l=1}^{L-1}\sum\limits_{i=1}^{S_{l+1}} \sum\limits_{j=1}^{S_l} \Big(\Theta^{(l)}_{ij}\Big)^2,\\ &h_{\boldsymbol\theta}(\boldsymbol x) \in \mathbb R^K， \left(h_{\boldsymbol\theta}(\boldsymbol x)\right)_i = i^{(th)} \text{output} \end{aligned} \tag{9.1}$$

则：

$$\frac{\partial J(\boldsymbol\Theta)}{\partial\boldsymbol\Theta^{(l)}} = \frac1m \sum\limits_{i=1}^m \left[ \boldsymbol\delta^{(l+1)} \times \left(\boldsymbol{a^{(l)}}\right)^T \right]_i + \frac\lambda m\boldsymbol\Theta^{(l)} \tag{9.2}$$

*BP 算法的使用

至此，我们已经将 BP 算法的核心内容的数学原理推导并阐述完整了。

用伪代码表示使用 BP 算法来求解偏导的大致过程如下（其中 $\Delta^{(l)}_{ij}$ 表示第 $i$ 个样本中的 $\delta^{(L)}_j$，$D^{(l)}_{ij}$ 表示 $\frac{\partial J}{\partial\Theta^{(l)}_{ij}}$）：

$$\begin{aligned} &\text{Set }\Delta^{(l)}_{ij} = 0 \text{ (for all l, i, j)} \\ &\text{For } i = 1 \text{ to } m \\ &\ \ \ \text{ Set } \boldsymbol a^{(1)} = \boldsymbol x^{(i)} \\ &\ \ \ \text{ Perform forward propagation to compute } \boldsymbol a^{(l)} \text{ for } l = 2,3,\cdots,L \\ &\ \ \ \text{ Using } y^{(i)} \text{, compute }\boldsymbol\delta^{(L)} = \boldsymbol a^{(L)} - \boldsymbol y^{(i)}_* \\ &\ \ \ \text{ compute } \boldsymbol\delta^{(L-1)}, \boldsymbol\delta^{(L-2)}, \cdots, \boldsymbol\delta^{(2)} \\ &\ \ \ \ \ \Delta^{(l)}_{ij} := \Delta^{(l)}_{ij} + a^{(l)}_j\delta^{(l+1)}_i\\ &D^{(l)}_{ij} := \frac1m\Delta^{(l)}_{ij} + \frac\lambda m\Theta^{(l)}_{ij} \text{ if } j\not=0 \\ &D^{(l)}_{ij} := \frac1m\Delta^{(l)}_{ij} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{ if } j=0 \end{aligned}$$

需要注意的是，在实际使用中，上述过程很多步骤可以转换为矩阵运算以提升性能。

---

[注1] 这句话网传出自黎巴嫩诗人纪伯伦，但我在网络上并未查到确切证据或出处，甚至浏览了网上传言出处得作品，并未得到印证。如果你知道这句话的出处，请指正！