Youmi Tech Blog.

I dream of painting and then I paint my dream.

卷积神经网络的数学推导

idiomer Posted at Jul 01, 2016 . - 神经网络 -

卷积神经网络(Convolutional Neural Network, CNN)是一种前馈神经网络,每个神经元都只影响邻层的一部分神经元,具有局部感受野,因此,网络具有极强的捕捉局部特征的能力;另一方面,通过权值共享和池化,显著地降低了网络的计算复杂度,使得CNN得到广泛应用。CNN是图像分类和语音识别领域的杰出算法,也是目前大部分计算机视觉系统的核心技术,从facebook的图像自动标签到自动驾驶汽车,乃至AlphaGo都在使用。与此同时,近两年CNN逐渐被应用于NLP任务,在sentence classification中,基于CNN的模型取得了非常显著的效果。

本文假设读者比较熟悉神经网络的相关知识,特别是反向传播算法的过程,从数学推导的角度来理解CNN的内部原理。

1 神经网络

神经网络是由多个感知器(神经元)构成的全连接的网络,本质上来说,这样的连接只是简单的线性加权和而已,所以每个神经元加上同一个非线性函数(如sigmoid,tanh等),使得网络能拟合非线性。通常,称这个非线性函数为激活函数。一个典型的全连接神经网络如下所示: nn

1.1 前向传导

上图中,每个圆圈代表一个神经元(标上“+1”的是偏置节点,不算入神经元),从神经元引出的连接是参数矩阵w,从偏置节点引出的是参数向量b。w和b是整个网络最重要的参数。

1.1.1 输入层

假设输入$x=[x_1, x_2, x_3]$,令第一层的输入$z^{(1)}$和激活输出$a^{(1)}$相等,即$z^{(1)} = a^{(1)} = x$。

1.1.2 隐藏层

第二层的输入为: $$z^{(2)}_1 = a^{(1)}_1 w^{(2)}_{11} + a^{(1)}_2 w^{(2)}_{12} + a^{(1)}_3 w^{(2)}_{13} + b^{(2)}_1\\ z^{(2)}_2 = a^{(1)}_1 w^{(2)}_{21} + a^{(1)}_2 w^{(2)}_{22} + a^{(1)}_3 w^{(2)}_{23} + b^{(2)}_2\\ z^{(2)}_3 = a^{(1)}_1 w^{(2)}_{31} + a^{(1)}_2 w^{(2)}_{32} + a^{(1)}_3 w^{(2)}_{33} + b^{(2)}_3$$ 用向量简洁表达为: $$ z^{(2)} = w^{(2)}a^{(1)} + b^{(2)} $$ 其中,$ z^{(2)} \in R^{3\times 1}, w^{(2)} \in R^{3\times 3}, a^{(1)} \in R^{3\times 1}, b^{(2)} \in R^{3\times 1}$

第二层的激活输出为: $$ a^{(2)} = f(z^{(2)}) $$ 其中,$f$为激活函数,$a^{(2)} \in R^{3 \times 1}$。

1.1.3 输出层

第三层输入: $$ z^{(3)} = w^{(3)}a^{(2)} + b^{(3)} $$ 其中,$ z^{(3)} \in R^{1\times 1}, w^{(3)} \in R^{1\times 3}, a^{(2)} \in R^{3\times 1}, b^{(3)} \in R^{1\times 1}$

第三层激活输出: $$ a^{(3)} = f(z^{(3)}) $$ 其中,$f$为激活函数,$a^{(3)} \in R^{1 \times 1}$。特别地,记$a^{(3)}$为$h_{w,b}(x)$

1.1.4 前向传导

因此,前向传导可以表示为: $$z^{(l+1)} = w^{(l+1)}a^{(l)}+b^{(l+1)}\\ a^{(l+1)} = f(z^{(l+1)})$$ 其中,$l=1,2,...,L-1$,$L$为神经网络的层数。

1.2 反向传播

假设神经网络的代价函数为: $$J(w,b)=\frac{1}{m} \sum_{i=1}^{m}J(w,b;x^{(i)},y^{(i)}) \\ 其中: J(w,b;x^{(i)},y^{(i)})=\frac{1}{2}(y^{(i)}-h_{w,b}(x^{(i)}))^2$$ 即,网络的整体代价为所有训练样例的平均代价。

此处我们是要找到最佳的w,b使得$J(w,b)$即代价函数的值最小,因此$J$是关于$w,b$的函数,其中$w,b$也不是标量,是很多$w_{ij},b_i$的集合。代价函数中没有显式的看到$w,b$的表达式,那是因为用简洁的$h_{w,b}(x^{(i)})$替换了。因此要强调的是:$J$的展开表达式(假设能展开)中只有$w,b$才是变量,其他都是已知的。

因此,根据梯度下降法的思想,对于每个$w_{ij}^{(l)},b_{ij}^{(l)}$,我们只要往负梯度方向更新就可以了,即:$$w_{ij}^{(l)}:=w_{ij}^{(l)}-\alpha \frac{\partial J}{\partial w_{ij}^{(l)}} \\ b_{ij}^{(l)}:=b_{ij}^{(l)}-\alpha \frac{\partial J}{\partial b_{ij}^{(l)}}$$ 向量化表达即为:$$w^{(l)}:=w^{(l)}-\alpha \frac{\partial J}{\partial w^{(l)}} \\ b^{(l)}:=b^{(l)}-\alpha \frac{\partial J}{\partial b^{(l)}}$$ 其中,$\alpha$是学习率。

因此,只要能求出$w,b$的偏导数就能迭代更新,从而完成整个算法。看似简单,但却困难。因为$J(w,b)$是很难写出显式表达式的,从而很难对每个$w_{ij},b_{ij}$都求出偏导,主要原因是网络是分层的进而$w,b$也是分层,这才导致了偏导的难求,从而才有了反向传播。

既然$w,b$是分层的,那么很自然地也可以分层地求$w,b$的偏导。那么很自然的,需要找到一个递推的结构来表达偏导。观察到前向传导中的结构$ z^{(l+1)} = w^{(l+1)}a^{(l)}+b^{(l+1)} $,只要求出$ z^{(l+1)}$的偏导,自然就可以求出$ w^{(l+1)},b^{(l+1)}$的偏导(矩阵、向量的求导形式类似标量,$a^{(l)}$视为常量)。

考虑单个样例的情形,当$l$为输出层时(l=3),有: $$ \delta^{(3)} = \frac{\partial J}{\partial z^{(3)}}=\frac{\partial}{\partial z^{(3)}}\frac{1}{2}(y-h(x))^2 = \frac{\partial}{\partial z^{(3)}}\frac{1}{2}(y-a^{(3)})^2\ =\frac{\partial}{\partial z^{(3)}}\frac{1}{2}(y-f(z^{(3)}))^2=(y-h(x))\circ f'(z^{(3)}) $$ 其中,$\circ$是按元素(element-wise)相乘。

当$l$为非输出层(隐藏层)时(l=2),有: $$\delta^{(2)} = \frac{\partial J}{\partial z^{(2)}}=\frac{\partial J}{\partial z^{(3)}}\cdot \frac{\partial z^{(3)}}{\partial z^{(2)}}=\delta^{(3)}\cdot \frac{\partial z^{(3)}}{\partial z^{(2)}}\ =\delta^{(3)}\cdot\frac{\partial}{\partial z^{(2)}}[w^{(2)} f(z^{(2)})+b^{(2)}] = w^{(2)} f'(z^{(2)}) \circ \delta^{(3)}$$

因此: $$\delta^{(L)} = (y-h(x))\cdot a^{(L)} \\ \delta^{(l)} = w^{(l)}a^{(l)} \cdot\ \delta^{(l+1)}, (l=2,...,L-1) $$ 所以: $$ \frac{\partial J}{\partial w^{(l)}}= \frac{\partial J}{\partial z^{(l)}}\cdot \frac{\partial z^{(l)}}{\partial w^{(l)}}=\delta^{(l)}\cdot (a^{(l-1)})^T \\ \frac{\partial J}{\partial b^{(l)}}= \frac{\partial J}{\partial z^{(l)}}\cdot \frac{\partial z^{(l)}}{\partial b^{(l)}}=\delta^{(l)} , (l=2,...,L)$$

2 卷积神经网络

2.1 卷积

假设有矩阵$A_{3\times 3}$和$B_{2\times2}$: \begin{equation*} A=\left[\begin{array}{ccc} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{array}\right]\quad B=\begin{bmatrix} 1 & 2\\ 3 & 4 \end{bmatrix} \end{equation*} 那么B卷积A的结果就是让 B 在矩阵 A 上滑动,换言之,就是 B 与 A 的所有2 × 2连续子矩阵做“对应元素积之和”运算,所以,此时的结果 C 应该为: \begin{equation*} C=\begin{bmatrix} 37 & 47\\ 67 & 77 \end{bmatrix} \end{equation*} 因此,假设 A 的大小为$h_a\times w_a$,B的大小为$h_b\times w_b$(其中$h_a\geq h_b, w_a\geq w_b$),则C的大小为$(h_a-h_b+1)\times(w_a-w_b+1)$,矩阵B称为卷积核或滤波器(filter),矩阵C称为特征图(feature map)。上述运算称为窄卷积,若矩阵A预先上下各添加$h_b-1$行零向量,左右各添加$w_b-1$列零向量,再与B卷积,则称为宽卷积。窄卷积和宽卷积分别用conv2(A, B, 'valid')和conv2(A, B, 'full')表示。

2.2 池化

假设矩阵C为$6\times4$的矩阵,池化窗口为$2\times2$,则按照池化窗口大小将矩阵C分割成6块不相交的$2\times2$小矩阵,对对每个块中的所有元素做求和平均操作,称为平均池化,取最大 值则称为最大池化。得到的矩阵S称为pool map。如: \begin{equation*} C=\begin{bmatrix} 1 & 2 & 3 & 4\\ 1 & 2 & 3 & 4\\ 5 & 6 & 7 & 8\\ 5 & 6 & 7 & 8\\ 9 & 0 & 1 & 2\\ 9 & 0 & 1 & 2 \end{bmatrix} \end{equation*} 若平均池化,则: \begin{equation*} S=\begin{bmatrix} 1.5 & 3.5\\ 5.5 & 7.5\\ 4.5 & 1.5 \end{bmatrix} \end{equation*} 若最大池化,则: \begin{equation*} S=\begin{bmatrix} 2 & 4\\ 6 & 8\\ 9 & 2 \end{bmatrix} \end{equation*} 由于池化也称为下采样,用$S=down(C)$表示,为了使得池化层具有可学习性,一般令: $$S = \beta down(C) + b$$ 其中,$\beta$和$b$为标量参数。

2.3 卷积神经网络

卷积神经网络是权值共享,非全连接的神经网络。以2个卷积层和2个池化层的卷积神经网络为例,其结构图如下: cnn

2.3.1 前向传导

C1层:卷积神经网络的输入是$28\times28$的矩阵A,经过$F_1$个$5\times5$的卷积核$K_i^1(i=1,2,...,F_1)$的卷积生成$F_1$个$24\times24$大小的feature maps: $$C_i^1 = conv2(A, K_i^1, 'valid') + b_i^1 \\ u_i^1 = C_i^1 \\ a_i^1 = f(u_i^1) $$

S2层:接着池化,池化窗口为$2\times2$,一个$24\times24$的feature map池化成一个$12\times12$大小的 pool map,共生成$F_1$个pool maps: $$S_i^2 = \beta_i^2 down(a_i^1) + b_i^2 \\ u_i^2 = S_i^2 \\ a_i^2 = f(u_i^2) $$

C3层:接着再次卷积,C3层中每个$8\times8$的feature map $C_i^3$都由S2中的所有$F_1$个 pool maps 经过$F_1$个$5\times5$的卷积核$K_{ij}^3(j=1,2,...,F_1)$,共生成$F_3$个feature maps: $$C_i^3 = \sum_{j=1}^{F_1}conv2(a_j^2, k_{ij}^3, 'valid') + b_{ij}^3\\ u_i^3 = C_i^3 \\ a_i^3 = f(u_i^3) $$

S4层:接着再次池化,池化窗口为$2\times2$,一个$8\times8$的feature map池化成一个$4\times4$大小的pool map,共生成$F_3$个pool maps: $$S_i^4 = \beta_i^4 down(a_i^3) + b_i^4 \\ u_i^4 = S_i^4 \\ a_i^4 = f(u_i^4) $$

全连接层:最后,将$a_i^4(i=1,2,...,F_3)$顺序展开成向量,并有序连接成一个长向量,作为全连接层网络的输入。

2.3.2 反向传播

$\quad$卷积神经网络的反向传播本质上是和BP神经网络是一致的,区别在于全连接和非全连接:在反向求导时,卷积神经网络要明确参数连接了哪些神经元;而全连接的普通神经网络中的相邻两层的神经元都是与另一层的所有神经元相连的,因此反向求导时非常简单。

全连接层 $\quad$全连接层的反向求导是与普通神经网络的反向求导是一致的: $$\frac{\partial J}{\partial w^{(l)}} = \delta^{(l)}(a^{(l-1)})^T \\ \frac{\partial J}{\partial b^{(l)}} = \delta^{(l)} $$

卷积层 $\quad$假设当前卷积层为$l$,下一层为池化层$l+1$,上一层也为池化层$l-1$。那么从$l-1$层到$l$层有: $$a_i^{(l)} = f(u_i^{(l)}) = f(\sum_{j=1}^{N_{l-1}}conv2(a_j^{(l-1)}, K_{ij}^{(l)})+b_{ij}^{(l)})$$ 其中,$N_{l-1}$为$l-1$层pool maps的个数。如,当$l=1$时,$N_{l-1}=1$;当$l=3$时,$N_{l-1}=F_1$。

$\quad$为了求得卷积层$l$的各个神经元的$\delta$,关键是要必须弄清楚该神经元与$l+1$层中的哪些神经元连接,因为求该神经元的$\delta$时,只与这些神经元相关。递推的方式与全连接的神经网络的不同之处在于:

  1. 卷积层$l$的各个神经元的$\delta$只和$l+1$层的相关神经元有关
  2. 卷积层 $l$ 到池化层 $l+1$ 做了下采样运算,使得矩阵维度减小,因此,$\delta_i^{(l+1)}$需要上采样up成卷积层的矩阵维度。定义 up 运算为(若上采样窗口为$2\times2$): $$up(\begin{bmatrix}1&2\\3&4\end{bmatrix}) = \begin{bmatrix}1&1&2&2\\1&1&2&2\\3&3&4&4\\3&3&4&4\end{bmatrix}$$

因此,有: $$\delta_i^{(l)} = \beta_i^{(l+1)} (a(u_i^{(l)}) \circ up(\delta_i^{l+1})) \\ \frac{\partial J}{\partial b_i^{(l)}} = \sum_{s,t}(\delta_i)_{st} \\ \frac{\partial J}{\partial K_{ij}^{(l)}} = \sum_{st}(\delta_i^{(l)})_{st}(P_j^{(l-1)})_{st} $$ 其中,$(*)_{st}$遍历$*$的所有元素,$(P_j^{(l-1)})_{st}$是$(\delta_i^{(l)})$所连接的 $l-1$ 层中$a_j^{l-1}$中相关的元素构成的矩阵。

池化层 假设当前池化层为 $l$,下一层为全连接层,那么当前池化层就是全连接层的输入,可以根据全连接层的 BP 求导公式递推算出。因此只需讨论下一层 $l+1$ 为卷积层的情形,上一层 $l-1$也为卷积层,该情形下有: $$a_i^{(l)} = f( \beta_i^{(l)} down(a_i^{(l-1)}) + b_i^{(l)} )$$

同样地,为了求得池化层 $l$ 的各个神经元的$\delta$,关键是要必须弄清楚该神经元与 $l+1$层中的哪些神经元连接,因为求该神经元的$\delta$时,只与这些神经元相关。递推的方式与全 连接的神经网络的不同之处在于:

  1. 池化层 $l$ 的各个神经元的$\delta$只和 $l+1$ 层的相关神经元有关
  2. 池化层 $l$ 到卷积层 $l+1$ 做了窄卷积运算,使得矩阵维度减小,因此,$\delta_i^{l+1}$ 需要与相应的卷积核做宽卷积运算使得矩阵维度扩展回去。 因此,有: $$\delta_i^{(l)} = \sum_{j=1}^{N_l}a_i^{(l)} \circ conv2(\delta_{j}^{(l+1)}, K_{ji}^{(l+1)}, 'full') \\ \frac{\partial J}{\partial b_i^{(l)}} = \sum_{s,t}(\delta_i^{(l)})_{st} \\ \frac{\partial J}{\partial \beta_i^{(l)}} = \sum_{s,t}( \delta_i^{(l)} \circ d_i^{(l-1)} )_{st} $$ 其中,$(*)_{st}$遍历$*$的所有元素,$d_i^{(l-1)} = down(a_i^{(l-1)})$。

参考资料

  1. UFLDL Tutorial
  2. GradientBased Learning Applied to Document Recognition
  3. Notes on Convolutional Neural Networks