快速卷积算法winograd原理推导

最近看到文章中说采用winograd快速卷积算法可以减少神经网络中图像卷积的乘法次数，因为之前做过cnn，当时卷积用的最简单的滑动窗口方式计算卷积，因此对这个快速卷积比较有兴趣，文章中先以一维的为例阐述了winigrad的如下思想：

其中下面的m1、m2、m3、m4的表达式是winograd的一个关键内容，通过这种转换将原本需要6次乘法减少到了4次（当然加法增加了），但是文中没有给出如何推导出的m1、m2、m3、m4的表达式，原论文中也没有，由于原论文中给出的是特殊形式，如果结果有变化类似的表达式需要自己推导，因此本人尝试了下m1、m2、m3、m4的表达式的推导的过程，大概如下：

    首先要做的是将上图中由d0\d1\d2\d3\g0\g1\g2的矩阵乘法转换为只用4个变量m1、m2、m3、m4表达的形式，因为输出是两个值，表达式需要有两个。m1、m2、m3、m4四个变量之间只用加减法实现，观察d0\d1\d2\d3\g0\g1\g2的矩阵乘法的形式，假设第一个表达式包含m1、m2、m3,第二个表达式包含m2、m3、m4，按照上图中的假设第一个表达式为m1+m2+m3,第二个表达式为m2-m3-m4,其中m2和m3的符号对推导有很大作用，下面以第一个表达式为m1+m2+m3、第二个表达式为m2-m3-m4的前提推导m1、m2、m3、m4的表达形式：

将上图展开后为：

d0g0+d1g1+d2g2=m1+m2+m3

d1g0+d2g1+d3g2=m2-m3-m4

从上式直观看，m1应该包含d0g0,m4应该包含d3g2,因此先假设m1=d0g0,m4=-d3g2,在次假设下代入上式，则可以约掉m1、m4，则可以计算出m2、m3的表达形式：

m1=d0g0

m2=0.5(g1d1+g2d2+g0d1+g1d2)

m3=0.5(g1d1+g2d2-g0d1-g1d2)

m4=-d3g2

观察m2的表达形式中包含d1、d2、g0、g1、g2，可以转化为两个多项式乘积的形式，多项式一部分包含 d1、d2，另一部分包含g0、g1、g2，且符号都为正，则m2可以转化为下列的形式：

m2=0.5(d1+d2)(g0+g1+g2)-0.5d2g0-0.5d1g2

同理观察m3 的形式，也可以类似转化为下列的形式：

m3=0.5(d2-d1)(g0-g1+g2)+0.5d1g2-0.5d2g0

目前为止m1、m2、m3、m4的表达形式如下：

m1=d0g0

m2=0.5*(d1+d2)(g0+g1+g2)-0.5d2g0-0.5d1g2

m3=0.5(d2-d1)(g0-g1+g2)+0.5d1g2-0.5d2g0

m4=-d3g2

为了进一步简化，考虑他们满足的条件：

d0g0+d1g1+d2g2=m1+m2+m3         --A

d1g0+d2g1+d3g2=m2-m3-m4            --B

观察上式A和B发现，在m2和m3各自加上一个值X的时候，式子B不变，式子A应该在m1中减去2X，观察目前m1、m2、m3、m4的表达形式，发现当X=0.5d2g0时，可以进一步简化m1、m2、m3、m4的表达形式如下：

m1=g0(d0-d2)

m2=0.5*(d1+d2)(g0+g1+g2)-0.5d1g2

m3=0.5(d2-d1)(g0-g1+g2)+0.5d1g2

m4=-d3g2

再由A、B发现，m2加上一个Y，m3减去一个Y的情况下，A式不变，B式需要减去2Y，由当前m2、m3的形式看出，Y=0.5d1g2时，m1、m2、m3、m4可以进一步化简，化简后就是最终的形式：

m1=g0(d0-d2)

m2=0.5*(d1+d2)(g0+g1+g2)

m3=0.5(d2-d1)(g0-g1+g2)

m4=g2(d1-d3)