# 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)的变换矩阵

0. 确定插值点: 插值点是构建变换矩阵的核心数学坐标 决定了变换矩阵 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](https://github.com/andravin/wincnn)
#### 推导
首先我们把卷积写为多项式的乘法

- 输入为 $d = [d_0,d_1,d_2,d_3]$
- 卷积核为 $g = [g_0,g_1,g_2]$

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

$$
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
$$

所以卷积等价为

$$
d * g = D(x)G(x)
$$

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

假设是F(2,3)

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

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


3. 选择插值点

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

[WINOGRAD CONVOLUTION FOR DEEP NEURAL NETWORKS:EFFICIENT POINT SELECTION](https://arxiv.org/pdf/2201.10369)

然后计算在这些点的值

$$
D(x_1) , D(x_2), .. , D(x_{m+n-1})

G(x_1) , G(x_2), .. , G(x_{m+n-1})
$$

4. 计算哈达玛乘积

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


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

L为拉格朗日插值多项式

则

$$
y_0 = M_1 L_1(1) + ... + M_{m+n-1} L_{m+n-1} (m+n-1)
...
$$
## 结合型