神经网络的计算复杂度

940 views

什么是计算复杂度? 计算复杂度是用来衡量问题难易程度的标准,告诉人们求解这个问题需要多少的资源。

根据计算复杂度的定义,如果我们要探讨神经网络的计算复杂度,那我们首先要解决我们的第一个问题:

  • 神经网络要解决的问题是什么?

神经网络要解决什么问题?

神经网络要解决的问题可以概括为:给定网络结构,基于训练集,我们要找到输入和输出之间的关系。那么这个问题的输入规模大小为什么?输入规模一般是我们自己定的,为了便于分析,我们通常将它设定为输入的形状,如输入一张256x256x3的图片。

已经知道神经网络要解决的问题是什么了?根据计算复杂度度的定义,我们应该对神经网络要解决的的难度进行度量。怎么度量?通常根据求解这个问题所需要的的时间和空间来决定。

怎么度量这个问题所需要的的时间和空间?通过时间复杂度和空间复杂度。时间复杂度是指求解这个问题的过程中基本操作一共进行了多少次。空间复杂度是指求解这个问题一共需要多少单元的存储空间。可以看出,这两个度量标准都是估计值。

对于时间复杂度和空间复杂度,我们已经很熟悉了,在算法分析里面经常会用到。
但是对于时间复杂度的分析,我们需要知道哪个是基本操作?对于空间复杂度的分析, 我们需要知道在求解过程中存储了什么?


神经网络的基本操作和中间存储

无论何种神经网络,计算基本上都可以表达为这种形式:y = w[0]*x[0] + w[1]*x[1] + w[2]*x[2] ~ + b,可见计算基本上是由乘法和加法组成的。
我们通常将乘法、加法、减法、除法称作为一次浮点运算。对神经网络计算的度量可以通过多少次浮点运算(FLOPS)进行衡量。
有些计算器可以将乘法和加法进行集成,只需要一次时钟周期就可以同时完成加法和乘法。因此,我们将乘法和加法组合起来,用MACC进行衡量。
因此,对于计算量大小的估计可以通过下面两个标准进行度量:

  • FLOPS
  • MACCS

对于空间复杂度,神经网络通常需要对模型的权重进行中间存储,因此我们对于空间复杂度的分析主要集中在于模型的权重数量上。

对时间复杂度和空间复杂度,我们确定完需要分析的目标之后,下面就可以分析了。

下面,我们将对以下几种神经网络进行分析:

  • 全连接神经网络
  • 卷积神经网络
  • 激活层

全连接神经网络时间复杂度和空间复杂度分析

对于全连接的网络结构如下所示,输入层的每个神经元和每个隐藏隐藏神经元相连。注意: 下图中的连线代表的是权重,而圆形的表示的神经元。

全连接网络的数学表达可以表示为:Y = matul(W, X) + b。 Y、W、X表示的是向量。根据这个数学原理,如输入X是n维的,我们假设中间隐藏神经元数量为J, 因为每一个输入都要与所有中间隐藏神经元相连,所以权重的维度为n*J+1。全连接的需要存储的参数大小为n*J + 1

那么全连接网络一共需要多少次浮点计算?根据数学表达Y = matul(W, X) + b,我们可以知道一共需要2n*J+1 FLOPS。

我们看到全连接神经网络的参数是比较多的,比如我们输入为4096维,隐藏神经元有4096个,那么中间的参数大小大约是16.8M,假设一个浮点数一个字节,那么参数就将占用16.8MB大小的内存,十分可怕。毕竟输入4096维可能算是比较小的了。


卷积神经网络时间复杂度和空间复杂度分析

由于全连接的参数太多了,而且对于一些组合特征无法学习。比如给一张图片,不同位置像素的组合表示一些比较典型的特征。如手写数字里面,9是由一个圈和一个曲线组成的,那么组成这个圈的像素就可以作为一个比较典型的特征。

然而全连接无法对位置组合构成的特征进行学习,因为我们在图片输入全连接的过程中需要将图片拍扁变成一维的。

如果是全连接神经网络,每个像素都要与所有中间神经元进行相连,这样参数多,而且还无法学习组合特征。因此,我们从生物学上借鉴一个感受野的概念。也是我们组合多个像素,这些组合的像素和同样大小的感受野相连,最后才和中间神经元相连。打个比方:全连接网络就是我们一个像素一个像素的看,看完所有的像素之后,我们判断得出这个图片表示的是1。而卷积的过程就是,我们知道1是肯定有条直直的线,那么我们就不断在这个图片的距型区域内寻找是不是有直直的线。不同于一个像素一个像素的找,卷积是一个矩形区域一个矩形区域的搜索,如果有直直的线,就给给它一个数值较大的输出。如果没有直直的线,就给它一个数值较小的输出。

怎么判断图片的矩形区域内有没有直直的线?我们将直直的线表示成矩阵,如果矩形区域内的像素和我们用直直的线表示成的矩阵像素是相似的,那么就可以判断这个区域内有直直的线了。

对于一张图片,一个特征显然是不够的,通常需要多个特征。那么我们就可以通过多个感受野同时进行一个矩形区域一个矩形区域的搜索。多个感受野之间,有相同的输入,所以不同感受野之间是可以并行的。因此,卷积很适合并行执行。

还需要补充一点的是,我们通常把感受野称作为过滤器或者卷积核。通过感受野生成的数据,称作为feature map




为了便于分析,假设卷积核是正方形的,大小为K*K, 输出的feature map 是M*M大小的,输入的像素是Cin层的,一共有Cout个卷积核,那么输出就是Cout层。

对于卷积所需要的参数,由于对于同一个feature map, 感受野使用的权重参数是共享的,所以每个卷积核一套参数。卷积核一共有多少个参数?卷积核中的每个数组都要与Cin个输入相连,我们说了连线表示的就是权重,忽略bias,那么一个卷积核就需要K*K*Cin个参数,Cout个卷积层就需要K*K*Cin*Cout个参数,可以看出这个大小相比与全连接的大小是比较小的。

对于卷积的计算大小,看上图所示的代码。每个feature map的数值都是由卷积核和padding之后的输入计算得到的,每个卷积核和输入计算需要多少次浮点计算?很简单,看权重就知道,一个权重对应一次乘法和一次加法,加上bias需要一次加法运算,因此每个卷积核和输入计算需要2*K*K*Cin+1FLOPS,由于卷积核需要在图片进行扫描,扫描的次数就等于feature map的大小,所以生成一个feature map就需要M*M*(2*K*K*Cin+1) 次浮点运算。Cout次浮点运算,就有Cout 个feature map,总的来说就有M*M*(2*K*K*Cin+1)*Cout FLOPS。忽略bias加法,我们说了乘法和加法在一些计算器里面可以集成到一次计算周期MACC,那么就需要M*M*K*K*Cin*Cout MACCS。

我们可以看出卷积所需要的计算量很大,假设输入图片大小是256256, 一共rgb三层,卷积核大小假设为55, 一共有8个卷积核,输出的feature map大小为256*256,那么大概需要10亿次浮点运算,妈呀,贼多。因此在平时训练的时候,卷积都是很费时间的。


激活层的计算复杂度和空间复杂度

对于激活函数的分析就比较简单了,每个输入都只会与一个激活神经元进行相连。不同的激活函数,可能需要的浮点计算数量不同。对于sigmod函数,需要3次浮点计算,对于relu函数的化,就需要1次浮点计算。输入为n的话,激活层一定会有n个神经元。对于sigmod函数,才会有3n次浮点计算,这个是比较少的。通常,对于激活层,我们对它的计算时忽略不计的。

全连接参数太多,卷积计算太大,那么我们应该如何进行优化我们的模型以减少我们的计算呢?下面介绍神经网络的优化的思路。


神经网络的计算优化思路

融合

融合这个想法很少有人听过。一个神经网络层的计算,要经历三次内存的读取:

  • 从内存中读取输入
  • 从内存中读取中间权重
  • 将输出写入内存当中

内存读取通常比计算耗时更多。因此,我们要尽量减少内存读取的次数。
如果我们将卷积层和输入层分开执行,就需要经历5次内存读取。而如果将两者结合起来,卷积输出不用写入内存当中,直接给激活层进行计算,那么就只需要3次内存读取就完成了。节省的时间是很可观的。


卷积神经网络的计算优化

对于卷积神经网络的优化,基本上一个思路,用加法代替乘法。卷积计算的时间复杂度为M*M*K*K*Cin*Cout MACCS。缩小卷积核的大小K, 然后使用多个卷积核代替大卷积核,这样可以乘法就变成加法了。比如6*6的卷积核用3个2*2的卷积核进行代替,感受到的东西是一样,但是计算从36倍减少到了12倍,减少了3倍,十分可观。同时我们可以采用更大的步长,这样就可以减少feature map的大小。

对于神经网络计算复杂度和空间复杂度的分析已经结束了,但是如果大家将模型放到现实中去跑,你会发现运行时间和预估的浮点计算时间对不上。为什么?因为内存读取,现实就是内存读取可能比计算所需要的时间更多。下面,就介绍如何解释时间复杂度预估和现实运行对不上的问题?


真实运行时间和理论时间复杂度的误差分析

如果我们优化一个网络,就像mobile net 2 比 mobile net 1的参数数量和时间复杂度都要低,但是正式运行时间却是反过来的,难道理论不对了?
不,时间复杂度和空间复杂度只是一个参考量。

我们这里采用roofline model进行分析,使用 pie 表示机器没秒钟最多运行多少次的浮点计算,使用beta表示每秒能进行多少次的内存读取。pi/beta表示计算强度,表示每一次内存读取,我们最多能进行多少次的浮点计算。

随着内存带宽beta的增加,机器真实每秒能够进行的浮点计算数量也能增加。但是对于相同的内存带宽,计算量增大,机器真实每秒能够进行的浮点计算数量不会增加,而是保持有一个值,这个值就是我们的内存限制。
当我们浮点计算达到我们的最大计算浮点速度,即使内存再增大,现实计算浮点数量就不会增加,此时称之为计算上限。

在真实运行环境下,我们就可以通过上述模型进行分析。


总结

对于神经网络的时间复杂度、空间复杂度和真实运行时间分析,我们都有一定的了解的。下面进行一个总结。

总的来说,对于神经网络的计算时间,我们不仅要关注计算复杂度还要空间复杂度,关注内存的读取,内存带宽,否则你会发现理论无法对现实的运行时间进行很好的估计。

Rating: 5.0/5. From 1 vote.
Please wait...