Terry Winograd

Winograd ^[1]于1980 年提出了有限脈沖響應(yīng)（finite impulse response，F(xiàn)IR）濾波的最小濾波算法最小濾波算法^[2] 。該算法指出，由r 拍的FIR濾波器生成m 個(gè)輸出，即，需要的最少乘法數(shù)量 。以F(2,3) 為例，最小濾波算法：

涉及到的乘法數(shù)量為 ，從6 次降低到了4 次。

2015 年，Winograd 最小濾波算法初次被應(yīng)用在CNN 中^[3]，利用減少的乘法次數(shù)提升卷積算子性能。如果用矩陣的形式表示一維Winograd 最小濾波算法，則可以得到：

其中，g 為濾波器向量，d 為輸入數(shù)據(jù)向量，Y 為輸出數(shù)據(jù)向量，G 表示濾波器變換矩陣， 表示數(shù)據(jù)變換矩陣，表示矩陣的對(duì)應(yīng)位相乘（Hadamard 積）， 表示輸出變換矩陣。

由此擴(kuò)展到二維Winograd最小濾波算法可以得到：

其中，g為濾波器矩陣，d為輸入輸入數(shù)據(jù)塊。通過(guò)嵌套一維最小濾波算法和 ，可以得到二維的最小濾波算法其中，為輸出大小，為濾波器大小。二維最小濾波算法所需乘法數(shù)為 ，而原始卷積算法需要乘法數(shù)為。對(duì)于而言，乘法計(jì)算次數(shù)從36降低到了16，減少了55.6%。

將應(yīng)用到卷積計(jì)算，對(duì)于二維卷積算子，需要先將卷積輸入劃分為相互重疊的大小為 的切片，切片之間有r-1的重疊部分。對(duì)于每個(gè)通道，可以分成個(gè)切片，然后通過(guò)對(duì)每個(gè)切片分別進(jìn)行計(jì)算。

將每個(gè)切片標(biāo)記為，對(duì)應(yīng)第i個(gè)輸入和第k個(gè)卷積核的卷積計(jì)算結(jié)果為：

其中：，。

Winograd卷積的偽代碼

Winograd 卷積的四個(gè)階段

根據(jù)二維最小濾波算法的矩陣形式，可以將Winograd卷積分為四個(gè)分離的階段：輸入變換（input transformation，ITrans）、卷積核變換（kernel transformation，KTrans）、對(duì)應(yīng)位相乘（element-wise matrix multiplication，EWMM）和輸出變換（output transformation，OTrans），如圖1所示。

1. Terry Winograd, Professor Emeritus of Computer Science, Stanford University https://hci.stanford.edu/winograd/ ?

2. WINOGRAD S. Arithmetic complexity of computations [M]. Philadelphia: SIAM, 1980. ?

3. LAVIN A, GRAY S. Fast algorithms for convolutional neural networks[C]//Proceedings of the 2016 IEEE Conferenceon Computer Vision and Pattern Recognition, Las Vegas, Jun 27-30, 2016. Washington: IEEE Computer Society, 2016:4013-4021. ?