关于卷积的一些思考

前言

这里是对卷积的一些思考。

一、卷积是什么

我们从一个简单的问题开始，f(x) = an * x^n + …, g(x) = bn * x^m + …, 那么H(x) = f(x) * g(x)的各项系数是什么？ 有些基础的小伙伴可能就举手了，“FFT直接就秒掉” 是的，这正是我们的主题—卷积 的一个应用场景

初始卷积是在CNN中听到的，当时对convolution这个词感到非常新鲜 又对“卷积”这个翻译感到很疑惑

经过了一年的学习与认识，在CNN、高等数学、概率论、离散数学等领域的学习后， 对这个词语有了自己的见解 它的本质，可以概括为四个字：“加权叠加” 这四个字的份量很重， 加权意味着多元运算，叠加代表将结果存储在统一时空或代数系统下

附上知乎大佬的链接: 如何通俗易懂地解释卷积？

二、卷积可以干什么

有了卷积的定义，那我们总得来干些什么 在计算机科学领域，有着六大卷积变换： DFT 、FFT 、NTT 、MTT 、FWT 、FMT 初学者可能会对这六个变换有些疑惑并产生了segment error 那我就来谈谈自己对这六个算法的认识

首先，我们介绍一下它们的名字 它们分别叫做：离散傅里叶变换、快速傅里叶变换、快速数论变换、任意模NTT、快速沃尔什变换和快速莫比乌斯变换

在这六个变换里，具有基石地位的是DFT离散傅里叶变换，很好理解，离散本身是计算机科学的基石，最常用的是FFT快速傅里叶变换，它在电气工程等领域有着广泛的应用

附一个youtube上百万播放量的视频: FFT：最灵巧的算法？

那这几个算法具体有什么用呢，直接有什么关联嘛？

有的，我娓娓道来 作为基石，DFT为后续五个变换提供了方法基础---- 利用所在代数系统的单位元 再次膜拜一下傅里叶，这简直是人类的顶级智慧 DFT主要解决了离散多项式的卷积乘法，进而引出了离散多项式的单位元----一个叫单位根的东西，回顾一下欧拉公式 e i π + 1 = 0. e^{i \pi} + 1=0. eiπ+1=0. 当pi不再是pi 而是 pi/n时，它就呈现出了复数美妙的地方，这里不再过多冗解 给出结论，离散多项式可利用NFT表达为 e i θ e^{i \theta} eiθ的线性和，利用这个线性和 进而达到卷积的效果，使得可以在 O(n log n)时间内求出离散多项式相乘

实际问题中，更常见的是FFT快速傅里叶变换，与DFT的区别在于，DFT所处的代数系统在整数域，而FFT的代数系统在实数域，DFT为FFT提供思想方法

然后的两个算法是NTT和MTT，这两个算法分别建立在一个整数环和多个整数环上，方法仍然是DFT所提供的幺元思想，在整数环上具体体现为阶和原根，到了高斯秀全场的时候了 ，MTT相对与NTT来说，其区别在于多对一，解决这一差异的方法是大名鼎鼎的中国剩余定理

最后的两个算法是FWT和FMT，快速沃尔什变换和快速莫比乌斯变换，快速沃尔什变换的基础建立在布尔代数上，代数系统的层级是域（记不太清了），其幺元是0和1及其相关运算。 FMT建立在集合这个域上，同时，在数论和整数环整数域上也有相关用法。这个算法的幺元有点emmmm，很难理解，我再学学后来补充。也有人认为FWT是FMT的一部分，因为布尔代数可以理解为模2的整数环。 目前以个人浅薄的离散数学知识，FMT的幺元似乎是经过莫比乌斯反演后的函数的函数值，因此FMT常常与FMI快速莫比乌斯反演相联系。

说了许多，之后把代码模板给补上，尽量不鸽

三、卷积可以吃吗

卷积当然可以吃，CNN可以用来造脑子，疯狂的戴尔夫.jpg 卷积在我们的生活中用处真的太大太大了，它解决了许多运算跨域的代数问题 后续会补上可以吃的卷积—CNN（尽量不鸽