神经网络

0x00 神经元

神经元和感知器本质上时一样的，只不过神经元内部用的激活函数不是阶跃函数而是sigmoid或者tanh这样的激活函数。sigmoid函数的定义如下：

$$\text{sigmoid}(x)=\frac{1}{1+e^{-x}}$$

这是一个非线性函数，其值域为(0, 1)，其导数为：

$$y'=y(1-y)$$

我们先来看一个神经网络：

左边红色的一层为输入层，用于接收输入的数据，最右边绿色的一层为输出层，外界从此获取预测值的输出。二者之间即为隐藏层，对外部而言是不可见的。在上图中，$w_{41}$表示从神经元1到神经元4的权值，$a_4$表示隐藏层神经元4的输出，其余的标号同理可得。由此我们可以有如下神经网络输出的形成过程：

$$a_4=\text{sigmoid}(w_{41}x_1+w_{42}x_2+w_{43}x_3+b_4)$$

在前文线性单元和梯度下降一节，我们已经提到可以将后面的偏差项b看做是一个输入值永远为1的特殊的w，由此我们把b改写成$w_{4b}$可以有：

$$a_4=\text{sigmoid}(w_{41}x_1+w_{42}x_2+w_{43}x_3+w_{4b})$$

由此将其转换成矩阵形式有：

$$a_4=\text{sigmoid}([w_{41},w_{42},w_{43},w_{4b}]\begin{bmatrix}x_1\\x_2\\x_3\\1\end{bmatrix}) \\ 令\vec{w_4}=[w_{41},w_{42},w_{43},w_{4b}], \vec{x}=\begin{bmatrix}x_1\\x_2\\x_3\\1\end{bmatrix}\\ 则有a_4=\text{sigmoid}(\vec{w_4}\cdot \vec{x})$$

将上图中我们隐藏层的4个神经元写成矩阵的形式，可有：

$$\vec{a}=\begin{bmatrix} a_4 \\ a_5 \\ a_6 \\a_7 \end{bmatrix}=\text{sigmoid}\left( \begin{bmatrix} w_{41}&w_{42}&w_{43}&w_{4b} \\ w_{51}&w_{52}&w_{53}&w_{5b} \\ w_{61}&w_{62}&w_{63}&w_{6b} \\ w_{71}&w_{72}&w_{73}&w_{7b} \end{bmatrix} \begin{bmatrix}x_1\\x_2\\x_3\\1\end{bmatrix} \right)$$

将前面一组满是w的矩阵记为$W_1$，由此，我们就可以得到：

$$\vec{a}=\text{sigmoid}(W_1\cdot \vec{x})$$

同理，继续向下一层，我们可以得到整个神经网络的输出y：

$$\begin{align*} \vec{y}=\begin{bmatrix} y_1 \\ y_2 \end{bmatrix} =& \text{sigmoid}\left( \begin{bmatrix} w_{84}a_4+w_{85}a_5+w_{86}a_6+w_{87}a_7+w_{8b} \\ w_{94}a_4+w_{95}a_5+w_{96}a_6+w_{97}a_7+w_{9b} \end{bmatrix} \right) \\ =& \text{sigmoid}\left( \begin{bmatrix} w_{84}&w_{85}&w_{86}&w_{87}&w_{8b} \\ w_{94}&w_{95}&w_{96}&w_{97}&w_{9b} \end{bmatrix} \begin{bmatrix} a_4 \\ a_5 \\ a_6 \\a_7 \\ 1 \end{bmatrix} \right) \\ =& \text{sigmoid}\left( W_2\cdot \vec{a} \right) \\ \end{align*}$$

每一层的算法都是一样的，上一层的输出就是下一层的输入，由此我们可以推广一个有更多层的神经网络的算法，如下：

上图中神经网络每一层的输出向量计算即为：

$$\begin{align*} \vec{a}_1&=f(W_1\cdot\vec{x})\\ \vec{a}_2&=f(W_2\cdot\vec{a_1})\\ \vec{a}_3&=f(W_3\cdot\vec{a_2})\\ \vec{y}&=f(W_4\cdot\vec{a_3})\\ \end{align*}$$

其中f(x)即为激活函数。

0x01 反向传播算法

反向传播算法主要用于训练神经网络。按照之前所说，我们取所有输出层结点的误差平方和作为误差函数：

$$E_d\equiv\frac{1}{2}\sum_{i\in \text{outputs}}(t_i-y_i)^2$$

依据随机梯度下降法，我们需要对误差函数进行优化：

$$w_{ji}\gets w_{ji}-\eta\frac{\partial{E_d}}{\partial{w_{ji}}}$$

由此我们需要求得$E_d$对每个权重值$w_{ji}$的偏导数。

$w_{ji}$表示从神经元$i$到下一层神经元$j$的连接的权重矩阵。由上图可以看出$w_{ji}$仅能通过影响结点$j$的输入来影响网络的其他部分。例如上图中$w_{41}$只能通过影响结点4的输入值（也就是结点1的输出值）来影响网络的其他部分。由此，我们记$\text{net}_j$为结点$j$的加权输入，由此可得：

$$\text{net}_j=\sum_i w_{ji}\cdot x_{ji}$$

由此，我们可以有：

$$\begin{align*} \frac{\partial{E_d}}{\partial{w_{ji}}}&=\frac{\partial{E_d}}{\partial{\text{net}_j}}\frac{\partial{\text{net}_j}}{\partial{w_{ji}}}\\ &=\frac{\partial{E_d}}{\partial{\text{net}_j}}\frac{\partial}{\partial{w_{ji}}}\left(\sum_{i}{w_{ji}}x_{ji}\right)\\ &=\frac{\partial{E_d}}{\partial{\text{net}_j}}x_{ji} \end{align*}$$

注意在上式中第二步到第三步的推算，对那个和式求偏导数的时候，不是$w_{ji}$的那一项，比如$w_{j(i-1)}$，对$w_{ji}$求偏导数就等于0了，就没有了，所以整个和式的最终求导结果为$x_{ji}$。

对于上式中$\frac{\partial{E_d}}{\partial{\text{net}_j}}$的推导，则需要分为2种情况，输出层和隐藏层。对于输出层来说，由误差值的计算方法可得，最终的误差$E_d$直接与输出层$\text{net}_j$的输出值$y_j$有关：

$$E_d\equiv\frac{1}{2}\sum_{i\in \text{outputs}}(t_i-y_i)^2$$

$E_d$是$y_i$的函数，而且$y_i$是$\text{net}_j$的函数，于是我们可以有：

$$\begin{align*} \frac{\partial{E_d}}{\partial{\text{net}_j}}&=\frac{\partial{E_d}}{\partial{y_j}}\frac{\partial{y_j}}{\partial{\text{net}_j}}\\ \end{align*}$$

对于第一项：

$$\begin{align*} \frac{\partial{E_d}}{\partial{y_j}}&=\frac{\partial}{\partial{y_j}}\left(\frac{1}{2}\sum_{i\in \text{outputs}}(t_i-y_i)^2\right)\\ &=\frac{\partial}{\partial{y_j}}\left(\frac{1}{2}(t_j-y_j)^2\right)\\ &=-(t_j-y_j) \end{align*}$$

对于第二项：

$$\begin{align*} \frac{\partial{y_j}}{\partial{\text{net}_j}}&=\frac{\partial \text{sigmoid}(\text{net}_j)}{\partial{\text{net}_j}}=y_j(1-y_j) \end{align*}$$

由此：

$$\frac{\partial{E_d}}{\partial{\text{net}_j}}=-y_j(t_j-y_j)(1-y_j)$$

此后我们将上面2式代入$\frac{\partial{E_d}}{\partial{w_{ji}}}$，解得：

$$\begin{align*} \frac{\partial{E_d}}{\partial{w_{ji}}}&=\frac{\partial{E_d}}{\partial{\text{net}_j}}x_{ji}=-y_j(t_j-y_j)(1-y_j)x_{ji} \end{align*}$$

令$\delta_j=-\frac{\partial{E_d}}{\partial{\text{net}_j}}$，也就是一个结点的误差项$\delta$是整个网络的误差$E_d$对这个结点输入$\text{net}_j$的偏导数的相反数。则有：

$$\delta_j=y_j(t_j-y_j)(1-y_j)$$

将上述推导带入随机梯度下降公式，可有：

$$\begin{align*} w_{ji}&\gets w_{ji}-\eta\frac{\partial{E_d}}{\partial{w_{ji}}}\\ &=w_{ji}+\eta(t_j-y_j)y_j(1-y_j)x_{ji}\\ &=w_{ji}+\eta\delta_jx_{ji} \end{align*}$$

对于隐藏层节点来说，首先我们来明确一个概念——下游节点（Downstream）。节点$j$的下游节点就是下一层与节点$j$直接相连的节点。在上图中，对于节点4来说，它的直接下游节点是节点8和节点9。由此我们可以发现，隐藏层的节点4的输出只能影响到节点8和9，然后再间接影响到$E_d$。由此我们定义节点$j$的所有直接下游节点集合$\text{Downstream}(j)$，设$\text{net}_k$为节点j下游节点的输入，要注意的是这个输入不光节点j的输出哦，还有与j同层的其他节点的输出。由此我们可以说$\text{net}_k$是$\text{net}_j$的函数，而$E_d$又是$\text{net}_k$的函数，由此我们可以有：

$$\begin{align*} \frac{\partial{E_d}}{\partial{\text{net}_j}}&=\sum_{k\in \text{Downstream}(j)}\frac{\partial{E_d}}{\partial{\text{net}_k}}\frac{\partial{\text{net}_k}}{\partial{\text{net}_j}}\\ &=\sum_{k\in \text{Downstream}(j)}-\delta_k\frac{\partial{\text{net}_k}}{\partial{\text{net}_j}}\\ &=\sum_{k\in \text{Downstream}(j)}-\delta_k\frac{\partial{\text{net}_k}}{\partial{a_j}}\frac{\partial{a_j}}{\partial{\text{net}_j}}\\ &=\sum_{k\in \text{Downstream}(j)}-\delta_kw_{kj}\frac{\partial{a_j}}{\partial{\text{net}_j}}\\ &=\sum_{k\in \text{Downstream}(j)}-\delta_kw_{kj}a_j(1-a_j)\\ &=-a_j(1-a_j)\sum_{k\in \text{Downstream}(j)}\delta_kw_{kj} \end{align*}$$

注：由0x00 神经元一节所述，$a_j$表示隐藏层神经元$j$的输出：

$$a_j= \text{sigmoid}(Wx)$$

上式中的x为上一个隐藏层的输出，也是当前神经元的输入。所以实则：

$$a_j=\text{sigmoid}(\text{net}_j)$$

对于隐藏层的下一层来说，下一层的输入就是上一层的输出，所以下一层的输入$\text{net}_{k}$则有：

$$\text{net}_{k}=w_{kj}\cdot a_j$$

依据sigmoid函数的导数公式，有了上述第3个等号到第4个等号的推算。

将$\delta_j=-\frac{\partial{E_d}}{\partial{\text{net}_j}}$代入上式可有：

$$\delta_j=a_j(1-a_j)\sum_{k\in \text{Downstream}(j)}\delta_kw_{kj}$$

由此我们可以总结出对于某个节点的误差计算公式：

\delta_j=\left\{ \begin{array}{ccl} y_j(t_j-y_j)(1-y_j) & \mbox{for} & j \in \text{output layer} \\ a_j(1-a_j)\sum_{k\in \text{Downstream}(j)}\delta_kw_{kj} & \mbox{for} & j \in \text{hidden layer} \end{array} \right.

我们再回过头来看这幅图：

对于输出层节点8来说，其误差值$\delta_8$即为：

$$\begin{align*} \delta_8=& y_1(t_1-y_1)(1-y_1) \end{align*}$$

对于隐藏层节点4来说，其误差值$\delta_4$即为：

$$\delta_4=a_4(1-a_4)(\delta_8w_{84}+\delta_9w_{94})$$

最后依据下式更新w的值：

$$w_{ji}\gets w_{ji}+\eta\delta_jx_{ji}$$

0x02 检查神经网络是否出错

对于梯度下降算法：

$$w_{ji}\gets w_{ji}-\eta\frac{\partial{E_d}}{\partial{w_{ji}}}$$

我们真正要保证的是这个偏导数$\frac{\partial{E_d}}{\partial{w_{ji}}}$的正确性，依据导数的定义：

$$f'(x)=\lim_{\epsilon \to 0}\frac{f(x+\epsilon)-f(x-\epsilon)}{2\epsilon}$$

对于任意的导数值我们都可以用右边的等式来进行计算，我们没法求解极限，但是我们只要把$\epsilon$取得足够小就行了，让其大致地在这个区间范围内，我们就可以认为其值是正确的：

$$\begin{align*} \frac{\partial{E_d}}{\partial{w_{ji}}}&=\lim_{\epsilon \to 0}\frac{f(w_{ji}+\epsilon)-f(w_{ji}-\epsilon)}{2\epsilon} \\ &\approx \frac{f(w_{ji}+\epsilon)-f(w_{ji}-\epsilon)}{2\epsilon} \end{align*}$$

0x03 训练MNIST

代码过长，参见我的GitHub Gist：

Implement a neron network from very beginning

0x04 为什么没有TensorFlow跑得快

• 全部使用python编写，语言本身效率低，而TensorFlow底层计算全部基于C++编写的动态链接库，TensorFlow python端仅是一个用于与底层库交互的接口，实际的计算工作全部都是在底层库中完成的。
• 全部基于CPU计算，TensorFlow GPU版可以完成基于GPU的计算，众所周知，GPU的浮点计算速度远高于CPU。
• 没有使用向量化编程，没必要定义太多复杂的对象，直接把数学计算实现了就可以了。
• 没有使用SGD（随机梯度下降算法）