ML创新点

通用型

基本上都是即插即用的万金油

Winograd卷积

通过数学变换大幅减少卷积计算量

在传统的卷积优化中 可以使用FFT, 但是FFT在针对于大的卷积核时才有明显优势,而且限制比较多.

对于现在的小卷积核 Winograd算法的优势便很明显

Winograd算法基于国剩余定理 将空间域的卷积变换到Winograd域计算

Winograd的符号是 \(F(m,n)\) 代表每次计算输出m个点 卷积核大小n. m根据输入规模选定 或者经验选定

Winograd乘法计算次数为: m + n - 1

普通卷积乘法计算次数为: m * n

注意: Winograd在FP32下表现很好 在其他量化下可能导致量化精度降低很多很多

注意: 插值点的选用非常重要

流程

计算F(m,r)的变换矩阵

  1. 确定插值点: 插值点是构建变换矩阵的核心数学坐标 决定了变换矩阵 A B G的系数

由中国剩余定理 想确定一个n次多项式需要n+1个点

根据选定的插值点集合 构造一个 n*n的Vandermonde矩阵

  1. 卷积核变换(G): 将原始卷积核转化为变换域的矩阵

  2. 输入变换(B): 将输入矩阵转换为变换域的阵

  3. 哈达玛积(\(\circ\)): 在变换域中 两个矩阵左哈达玛乘积

  4. 输出变换(A): 将点乘结果逆变换回空间域

\[ Output = A^T [(G g G^T) \circ (B^T dB)]A \]

其中

  • B: 多项式在插值点的取值

  • g: 卷积核

  • d: 输入块

  • G: 卷积核在插值点的取值

  • A: 拉格朗日/Hermite 插值回系数

插值点选择

Github

推导

首先我们把卷积写为多项式的乘法

  • 输入为 \(d = [d_0,d_1,d_2,d_3]\)

  • 卷积核为 \(g = [g_0,g_1,g_2]\)

  1. 我们对它们进行 生成函数 定义多项式

\[ \begin{align}\begin{aligned} D(x) = d_0 + d_1 x + d_2 x^2 + d_3 x^3 \\G(x) = g_0 + g_1 x + g_2 x^2 \end{aligned}\end{align} \]

所以卷积等价为

\[ d * g = D(x)G(x) \]

  1. 接下来我们按照F(m,r)中 m的值进行分批次计算.

假设是F(2,3)

则先关注前两个输出 ([]符号代表取系数算子)

\[ y_0 = [x^0]D(x)G(x) , y_1 = [x^1]D(x)G(x) \]

  1. 选择插值点

选择 m + n - 1个插值点 尽量选择形式对称的插值点 \([x_1,x_2,...,x_{m+n-1}]\)

WINOGRAD CONVOLUTION FOR DEEP NEURAL NETWORKS:EFFICIENT POINT SELECTION

然后计算在这些点的值

\[ \begin{align}\begin{aligned} D(x_1) , D(x_2), .. , D(x_{m+n-1})\\G(x_1) , G(x_2), .. , G(x_{m+n-1}) \end{aligned}\end{align} \]

  1. 计算哈达玛乘积

\(M_0 = D(x_1) \odot G(x_1)\) ... \(M_{m+n-1} = D(x_{m+n-1}) \odot G(x_{m+n-1})\)

  1. 拉格朗日插值恢复系数

L为拉格朗日插值多项式

则

\[ y_0 = M_1 L_1(1) + ... + M_{m+n-1} L_{m+n-1} (m+n-1) ... \]

结合型