date: 2019/09/18


早前《Winograd卷积原理 | Hey~YaHei!)》一文已经介绍过Winograd的卷积原理,但有些细节似乎尚不明确——



本文将借鉴《源于《孙子算经》的Cudnn | 知乎, Silicon Valley》和《wincnn/2464-supp.pdf | github, andravin》,深入剖析Winograd背后的数学原理。


中国同余定理

Winograd的基础来源于《孙子算经》中的中国同余定理(Chinese Remainder Theorem),同余定理是数论的重要内容(没学过数论的我,要读懂这个数学原理真的有些头疼QAQ)。


《孙子算经》

《孙子算经》有一章:

今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?

答曰:二十三。

术曰:三三数之剩二,置一百四十;五五数之剩三,置六十三,七七数之剩二,置三十,并之。得二百三十三,以二百一十减之,即得。凡三三数之剩一,则置七十;五五数之剩一,则置二十一;七七数之剩一,则置十五;一百六以上以一百五减之即得。


改用数学语言描述一下:

问题:已知同余方程组

求x?


其中,称为x与a模m同余,当时,可以认为x模m余a;


解答:


看到这,没读过数论的我感到十分震惊——为啥拿着余数乘几个数,最后加起来模一模怎么就可以推出被模的数呢??


定理内容

这里不加证明地直接引出中国同余定理的内容:

假设整数两两互素,则对于任意的整数,同余方程组

都存在整数解,且若$X, Y$都满足方程组,则必有,其中

其中是一个整数,使得


对《孙子算经》中的例子来说,就是


原始的定理只针对整数,事实上,该定理同样适用于多项式。

接下来我们关注一下定理里的两个细节:


如何证明互素?

互素,又称互质。若两个整数的公约数只有1,那么称它们为互素(质)整数。

当然这个定义可以引申到多项式上,比如就是典型的互素多项式。


证明互素的核心是证明它们的公约数只有1,问题可以转化成最大公约数为1,说起最大公约数的计算,那就不得不说欧几里得算法啦!

欧几里得算法俗称辗转相除法,用大数除以小数得到余数(这里商是无意义的),然后迭代计算,用上一轮的除数、余数分别作为新一轮的被除数和除数,直到最后能够整除,最后一轮的除数即为原始的两个数的最大公约数。

以1997和615为例:

故1997与615的最大公约数为1,记为gcd(1997, 615) = 1


至于,多项式之间如何做除法,可以直接用小学的长除法,除到最后余数的最高次幂小于除数的最高次幂即可。


除以为例:

(latex没法书写长除公式,这里我只能用分数的形式来表述)

那么这里除以,商为,余数为


如何求解系数?

根据定理,系数满足,我们假设      

 

那么有      

同时注意到,必定互素,则有      

构成了一个形如的贝祖公式,按照贝祖定理,可用扩展欧几里得算法求解出,也即(当然y没啥意义,我们要的是那个系数!)。    


扩展欧几里得算法除了能和欧几里得算法一样求得最大公约数之外,还能得到模逆元;

其实非常简单,与递归实现的欧几里得算法相比,无非是每次递归都逐步恢复出逆元x跟y

以python实现为例:

# def euclid(a, b):
#     while b != 0:
#         a, b = b, a % b
#     return a

def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a % b)

def ext_euclid(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, q = ext_euclid(b, a % b)
        x, y = y, (x - (a // b) * y)
        return x, y, q


Winograd算法

前边中国同余定理已经解释明白了,接下来我们试着理解一下Winograd的数学原理(以为例)。

假设两个离散序列,

经过Z变换变成多项式形式(为了方便起见,这里写作而非),

此时,(时域卷积 => Z域的乘法),记

于是两个序列的卷积变成了多项式的乘法(当然,乘积也是个多项式),我们继续往多项式版本的中国同余定理上套。

选取K个互素的一次多项式,使得的阶数等于,那就可以构造出同余方程

其中,除以的余数。

在这个例子中,至少需要3个互素一次多项式,不妨取

那么有

除此之外,我们再记一个特殊的,没有具体的意义,该多项式是为了凑足m的阶数,使得阶数高于,从而可以构造出同余方程

,则有

依次抽取的系数组成行向量并堆叠构造出变换矩阵

注意


接下来考虑一个重要的同余方程性质:

其中表示的最小公倍数


利用该性质(因为两两互素,所以就是它们的最小公倍数),又根据同余方程的乘法规则



原同余方程可以转化为同余方程组

的求解。原方程组又可以展开成

噢?好像变成了g(x)和d(x),橘势似乎明朗了起来=。=

依次抽取的系数组成列向量并堆叠构造出变换矩阵

那么回过头看看中国同余定理,

在这个例子里表示为

显然我们还差一个,根据贝祖公式用扩展欧几里得算法依次求得:

注意:此处《wincnn/2464-supp.pdf | github, andravin》给出的贝祖公式有误!!

抽取的系数组成列向量并堆叠构造出矩阵


我们代回去验证一下,

代入求得

阶数为4,大于3,则有


同样的由于阶数较高,原同余方程可以推出

改写成矩阵形式并做Z反变换变成

也即

……


啊!卡住了,我已经推导不下去……

  1. 上述Winograd的推导针对的是离散序列的卷积,我该如何推广到深度学习的卷积(即互相关函数)上去?
  2. 为何m输入r参数的离散序列卷积推导出来的变换矩阵G、A、B可以应用在m输出r参数的互相关函数上,最后变成的?