机器学习从入门到放弃：卷积神经网络CNN（一）

从数学角度来理解卷积，可以将其视为两个函数之间的运算，Δ值趋于无穷小的时候，通常表示：

四、傅里叶变换

在这里我们先从信号系统入手，通过卷积来理解接下来所要介绍的傅里叶变换。首先，我们需要记住卷积其中的最重要的一个性质：
时域的卷积等于频域相乘，频域的卷积等于时域相乘。

假设我们这里有两种信号，x(t) 和 y(t) 如果都是复杂函数的话，理论上都可以如下的多项式结构来进行表达，其实就是泰勒展开：

根据卷积的性质， x(t) 和 y(t) 两者的乘积可以表达为，x(t) 的多项式 a(n) 和 y(t) 的多项式 b(n) 的卷积，所以我们只要对多项式进行操作就必定能知道，x(t)乘以y(t)的新函数的表达式。比如上面的系数可以用如下方法进行求解：

上面的结论是不是很完美，但是有个问题，对于所有的函数确实可以泰勒展开来表示，但是我们在现实中操作确实非常困难的，因为我们很难恰当的找到对应的N阶多项式系数，换句话说时域名上很难算，所以我们需要把上面的多项式转变一下，变成如下的形式，这里转换指的是线性时不变系统，都可以看做是若干个 sin 和 cos 进行叠加，具体可以参考这个视频：
传送门

可能咋一看，你会发出疑惑：这是啥？？ 如果我告诉你这其实就是欧拉公式，你会不会想起来什么？我刚开始看的时候，完全有种死去的高数正在袭击我的感觉，为了快速的理解欧拉公式，我找到了这个视频，看完你会有种豁然开朗的感觉：
传送门

接下来我让 x(t) 和 x(t) 自身相乘：

发现没有，当求 x(t) 的 2 次方的时候，非常容易表示，就只需要在实部中参数乘以2，和虚部中参数乘以2。同理可得：

因此，我们只要将上诉的多项式变成 e 的虚部次方的形式，那不就可以完美解决多项式相乘的求解系数的问题了吗？假设我们有两个信号 g(t) 和 f(t)，表示为：

则两个函数的乘积为：

上诉的过程会计算一系列的三角函数，非常复杂，但是如果我们能够通过欧拉公式将 cos 和 sin 转变成 e 的虚部次方的形式，即：

我们把上面的函数写成如下的形式：

我们可以得到这两个函数的 f(t) 和 g(t) 的乘积如下：

这样我们就可以很快的利用卷积获取到此函数的多项式系数，然后再把 e 的虚部次方带入：

如上我们就完成了一次在时域信号复杂，难以相乘的情况下，通过将时域信号分解成频域信号进行卷积，就能得到我们想要的结果。

五、FFT快速傅里叶在CNN图像卷积上的使用

CNN中的卷积核使用里，就是通过“采样”过滤的方式，来通过频域上的“滤波”操作，然后反映成时域上的“特征”，所以卷积核也叫滤波器 Filter 之类的。

所以在 CNN 实现中，首先需要解决的是，我们如何快速的让原图片和卷积核进行“卷积”操作。如果单纯的像我们求解多项式系数一样，去求卷积的结果，那么起码需要 O(n^2) 的时间复杂度，就等于下图一样。每张图我们都需要让卷积核走动遍历去计算，但是如果是一张大图片，在比较庞大的训练数据量的时候，这计算量是非常恐怖的，那么这时 FFT 快速傅里叶就登场了，我们用这个算法来进行优化加速。

首先，我们需要确定的是，怎么把一张图片给变成一个频域上的函数？我们都知道图像每个像素都有可以用RBG值来进行表示，并且一张彩色的图片可以变成一个三维的矩阵，现在用一张灰色的图片来举例，也就是说它只有一维，那么这一张图片可以想象成如下的这样一个表达形式。

然后我们再分别以图像的x轴、y轴（或者说矩阵的第一维和第二维）为横轴，以灰度值为纵轴，这样就可以得到两个函数，分别表示灰度值在x轴和y轴的变化情况，如下图

根据傅里叶变换，时域上的信号可以变成频域上的若干个信号的叠加，那么图片在 y-z 面和 x-z 面上就可以分解成两个不同的频域信号了。如果你能在脑海中形成如下的图，且频域分别是 y-z 和 x-z 平面上，那么你应该很容易理解

比如我们使用一张图片，利用代码把它的傅里叶变换成频域上的表示就是这样：

图像的频谱图显示了图像在不同空间频率上的分布情况。这对于理解图像的纹理、边缘、模式等特征是很有帮助的，看频谱图可以从以下几个方面来看：

• 低频成分
  ： 位于频谱图中心的区域通常表示图像的低频成分。低频成分包含图像中较大且变化缓慢的部分，比如背景信息。
• 高频成分
  ： 位于频谱图边缘的区域表示图像的高频成分。高频成分对应图像中边缘、纹理等变化较快的部分。
• 水平和垂直方向
  ： 在频谱图中，水平方向表示图像的水平频率，垂直方向表示图像的垂直频率。这可以帮助分析图像中的水平和垂直特征。
• 对角线
  ： 对角线方向上的成分表示图像中具有斜向特征的部分。

比如如果图像在不同位置出现，他们的频谱图是不变的，如果旋转一定角度，在频谱上也能直观的发现：

所以，说了这么多，你大概能了解到傅里叶变换在图像处理中是非常重要的，也直观的清楚看到了一个图片进行傅里叶变换之后变成了什么样子。但是我们怎么获取到对应的频域函数的各个系数呢？也就是说我们怎么让上图中的图片，变成一个多项式相加的形式。然后让原图和卷积核的频域表达进行点值相乘。

假设我们取 n 个互不相同的值，x=(x0, x1, x2,...., xn-1) ，用这些点加上系数就能单独的代表某个图像的函数，比如我们称之为 A(x)，我们可以通过一组点来唯一确定此函数，如果我们知道结果 A(x) ，并且找到 n 个不同的点我们就能倒推出这个函数的表达式了：

A(x) = { (x0, A(x0)), (x1, A(x1)), (x2, A(x2)), ... (xn-1, A(xn-1)) }

也就是，问题变成了求解 n 阶线性方程的问题：

如果是二维的图片那就是这样的形式，只是为了方便后续的推到，现在我们只讨论一维的情况：

使用 FFT 和 IFFT 就能快速的找到一组不相同的点，对应上方左边的矩阵，首先登场的是 n
次单位根

（这叫做“旋转因子”， k 是旋转因子的指数），其实这个值就是上面一节我们介绍的 e 的虚部次方，这样的数有 n 个：

k = 1,2,3....n，

也就是说带入旋转因子之后，我们上面的函数就可以写成如下的表达式：

表达式(1)

这里注意的是，利用旋转因子的两个性质：

1.

2. 如果 n 是偶数，那么：

我们把表达式(1)变成这样，分为奇数和偶数两个部分：

带入旋转因子：

表达式(2)

我们让 k 值变成 k+n/2 时：

根据旋转因子的性质一和性质二：

所以对于奇数和偶数项，我们就可以得出以下的表达式：

所以只要我们就得到了“前一半”的结果；只要将等式右边中间的符号改成减号，就可以得到“后一半”的结果。所以只要分治的对半处理，就能快速的获得这个函数的表达式了。下面我们再将旋转因子的 n 个点带入到点值矩阵里面去：

表达式(3)

那么已知这个图片的单单灰度值的输出，也就是一个二维的y矩阵，我们就能求出这个图片函数的系数对吧，如下图：

现在我告诉你这个矩阵的-1次方，非常容易获得，那就是乘以 1/n：

表达式(4)

发现了吗？表达式(3)和(4)，使用的是几乎是同一个旋转因子矩阵，只需要在旋转因子上进行-1次方的变换，所以所以我们只要构造一个这样的矩阵，就能快速的完成 FFT 和 IFFT 的计算。

我发现当我看公式到这里，脑子已经完全变成浆糊了，我下面尝试一下将CNN中如果使用了FFT的话应该是怎么加速卷积计算的，水平有限，如果里面有错误，麻烦读者给予指正~

六、尝试手工推导CNN中使用FFT

现在有一张 1024x1024 的原图，并且使用 3x3 的一个卷积核，对其进行卷积操作。那么令 F(x) 为原图的函数表达，因为有 1024x1024 个像素点，所以我们是一个 1048576-1 阶的函数，令 G(x) 为卷积核的函数表达，因为是 3x3，所以这是个 9-1 阶的函数，如下：

F(X) = a0 + a1·X + a2·X^2 ..... + a1048576·X^1048575

G(X) = b0  + b1·X + b2·X^2.....+ b8·X^8

第二步，对输入的两个多项式 A(x) 和 B(x) 进行零填充： 将两个多项式的次数扩展到 2n-1，n 是足够大的整数，使得  n 大于等于 A 和 B 的次数之和。这可以通过在系数数组的末尾添加零来实现。比如这里 G(x) 就扩充变成：

G(X) = b0  + b1·X + b2·X^2.....+ b8·X^8 + 0·X^9 + .....0·X^1048575

第三步，把 F(x) 和 G(x) 变成点值表示，用复数旋转因子带入，然后使用 FFT，递归分治带入每一个输入值，然后就能得到 F(X)·G(X) 的值了。选择 2n-1 的单位复数根

，其中

，通常选择是

，其中 i 是虚数单位，这个选择是为了保证 2n-1 个根是不一样的。

F(X) = a0 + a1·Wn + a2·Wn ..... + a1048576·Wn

G(X) = b0  + b1·Wn + b2·Wn.....+ b8·Wn + 0·Wn + .....0·Wn

在伪代码中是这样子递归来求FFT的：

def fft_recursive(a, w_n):

    n=len(a)if n == 1:returna

    

    # 分割为奇次和偶次部分

    a_even= a[0::2]

    a_odd= a[1::2]

    

    # 递归计算

    y_even= fft_recursive(a_even, w_n**2)

    y_odd= fft_recursive(a_odd, w_n**2)

    

    # 合并结果

    y= [0] *n

    w= 1
    for k in range(n//2):
        t = w *y_odd[k]

        y[k]= y_even[k] +t

        y[k+ n//2] = y_even[k] - t
        w *=w_nreturn y

将 2n-1 个复数根 Wn 逐个带入函数，你会发现上面的式子用矩阵来表示就是上一节 表达式(3) 里面的表示，对于 F(x) 和 G(x)

上面的 y0 到 yn-1 实际上就是我们的图片也就是 1024*1024 个像素点，利用 表达式(4) 是可以反推出 a0 到 an-1 的系数的，然后我们这里需要计算 F(X)·G(X) 的值，也就是，当求出系数 a0~an-1 和 b0~bn-1 之后，我们带入到函数 F(X) 和 G(X) 就能针对每个点值进行单独的乘积了，比如对于第一个复数根：

Feature(W1) = F(W1) · G(W1)

一共选了 2n-1 个复数根，逐个带入就可以获得特征图的傅里叶变换函数，然后获取到 2n-1 个结果之后，实际上我们就获取到了这个图片的傅里叶输出了，然后再经过一次 IFFT 那就是 表达式(4)，我们就能获取到对应的 Featrue 特征图函数的表达式了。详细的过程你可在脑子里过一遍第四节中的第一张图。

得到特征图的函数表达，也就意味着我们可以根据 LOSS 不断修正它的系数，从而筛选出最能符合我们分类要求的函数，这样整个CNN的逻辑就完全可以串联起来了。

七、总结

本篇花了非常多的时间，也查阅了很多的资料才大概把卷积的整个底层原理，用图文的方式展示出来，因为水平有限，如果里面有任何不对的地方，麻烦读者指正。另外非常感谢下面的各位up主的贡献，我只是小小的知识搬运工。

Reference

[1] 请问为什么fft可以加速卷积运算？ - JieShi的回答 - 知乎
https://www.zhihu.com/question/394657296/answer/2329522108

[2] https://zhuanlan.zhihu.com/p/454090354

[3] https://blog.csdn.net/qq_37149421/article/details/103137332

[4] https://zhuanlan.zhihu.com/p/526705694

[5] 【【官方双语】那么……什么是卷积？】 https://www.bilibili.com/video/BV1Vd4y1e7pj/?share_source=copy_web&vd_source=4d1e9766ee0260272093180a125d35ee

[6] https://zhuanlan.zhihu.com/p/454090354