独家 | 由第一原理导出卷积

作者：Michael Bronstein

翻译：陈之炎

校对：郑滋

本文约3200字，建议阅读9分钟

本文介绍了第一原理中推导出卷积，并展示它的平移对称性。

标签：卷积

TLDR：你有没有想过卷积有什么特别之处？在这篇文章中，我从第一原理中推导出卷积，并展示它的平移对称性。

 

某些事物实质上是对其本质的一种支持。(Claude Adrien Helvetius)

在本科学习期间，我在以色列的Technion参与了电气工程，令人感到震惊的一个重要的概念是，突如其来的卷积[1]。就像一粒沙子落入眼睛里，它扰乱了信号处理世界原本美丽的画面。让卷积从第一原则中产生而不只是假定，将会多么美好！正如我将在这篇文章中所展示的，这里的第一原则即平移不变性或对称性。

首先，从基本信号处理课程中教授的公式开始，定义两个n维向量x和w的离散卷积[2]：

 

为了方便起见，假设所有的索引从零到n−1，并且是n模，自然而然地想到在圆上定义的向量，把上面的公式写成矩阵向量乘法，得到了一个非常特殊的矩阵，称之为循环（circulant）矩阵：

 

循环矩阵具有多对角结构，每个对角线上的元素具有相同的值。它可以通过将向量w的移位(模n)叠加在一起来生成[3]；因此，用C(W)来表示，指的是由向量w形成的循环矩阵。由于任何卷积x∗w都可以等价地表示为循环矩阵C(W)x的乘法，所以将交替使用这两个术语。

在线性代数中学习的第一件事是矩阵乘法不满足交换率，也就是说，一般情况下，AB≠BA。然而，循环矩阵是非常特殊的例外：

循环矩阵满足交换律，即：C(w)C(u)=C(u)C(w)。对于任何循环矩阵，或u和w的任何选择，这都是正确的。同样，可以说卷积是一个满足交换率的运算，x∗w=w∗x。

 

选择特定的w=[0,1,0…,0]生成一个特殊的循环矩阵，将向量向右移动一位。这个矩阵叫做（右）移位算子 [4]，用S表示。右移位算子的转置是左移位算子。显然，左移后右移（或反之）不起任何作用，这意味着S是正交矩阵：

 

循环矩阵满足交换率，它足以表明移位的交换性（在[5]中引理3.1）：

当且仅当矩阵对移位满足交换率时，称矩阵是循环的。

首先，“当且仅当”是指一种非常重要的性质，即平移或移位等差[6]：卷积与移位的交换性意味着无论我们是先移动向量，然后卷积向量，还是先卷积然后移位，结果都是相同的。

 

其次，可以将卷积定义为移位等变线性运算：为了使移位符合交换率，矩阵必须具有循环结构。这正是我们所期望的，从平移对称[7]的第一原理中导出卷积。而不是给出卷积的公式并证明其移位等差性质，这通常是在信号处理书籍中来推导的，我们可以从移位等差的要求开始，得出卷积的公式，作为满足它的唯一可能的线性运算。

 

 

信号处理课程中教授的另一个重要事实是卷积和傅里叶变换[8]之间的联系。在这里，傅里叶变换从天而降，之后是它对角化卷积操作，在频域中执行两个向量的卷积，作为它们的傅里叶变换的元素乘积。从来没有人解释过这些正弦和余弦来自哪里，以及它们有什么特别之处。

为了弄清真相，回想一下线性代数中的一个事实：

交换矩阵是可以联合对角化的。

换句话说，满足AB=BA的两个矩阵将具有相同的特征向量（但可能是不同的特征值）[9]。由于所有循环矩阵都满足交换率，可以选择其中一个并计算其特征向量-上述定理保证了这些矩阵的特征向量也将是所有循环矩阵的特征向量。

 

由于S是正交矩阵，所以我们期望它的特征向量也是正交的[10]。一个简单的计算(见[5]第4.1节)得出了这样的结论

移位算子通过傅里叶变换对角化。

在这一点上，可以有今天的第二个“啊哈”时刻：这便是sines和cosines的来源！它们是移位算子的特征向量；我将它们表示为矩阵Φ的列。注意特征向量是复杂的，所以在转置Φ时需要采取复共轭。和Φ*进行的乘法（从左）称为傅里叶变换，并通过Φ实现傅里叶逆变换。

 

由于所有循环矩阵都是对角的，所以它们也由傅里叶变换[11]对角化，只在特征值上有所不同。最后还要认识到这一点，其中C(w)的特征值为w的傅里叶变换。

现在可以从图中导出卷积定理：卷积x∗w可以通过计算原始坐标系统中x（有时称为“空间域”卷积）的循环矩阵C(W)来实现，也可以通过傅里叶（在频域）变换来实现：首先计算Φ*x的傅里叶变换，再将其和w [12]的傅里叶变换相乘之后，计算傅里叶逆变换。

 

由于Φ具有特殊的冗余结构，Φ*x和Φx的乘积可以用快速傅里叶变换(FFT)算法的复杂度

计算。

为什么要这样来定义卷积？在这里我将重复Helvetius的名言：“对某些原则的了解很容易弥补对某些事实的缺乏”。对于卷积而言，它从第一原则的推导更加容易推广到其他领域。在下一篇文章中，我将展示如何定义图形上的卷积，以便生成图形深度学习体系结构的关键架构块。

[1]Dominquez-Torres，卷积的历史和起源提供了一个迷人卷积操作发展历史。卷积首次出现在泰勒定理的推导中。J. B. D’Alembert进行了多方位的研究。优先次序常常被错误地归于P.-S. de Laplace, Mémoire sur l’inclinaison moyenne des orbites des comètes, sur la figure de la terre et sur les fonctions (1773)。虽然巴黎皇家科学院的备忘录里没有卷积的痕迹。但是，拉普拉斯在他后来写于1778年并于1781年出版的关于概率的回忆录中确实使用了卷积。早期卷积称为résultante（法语“resultant”，最初由查尔斯·凯勒于1899年使用）、Composizione（意大利语“composition”，由维托·沃尔特拉于1910年使用）和faltung(字面意思是德语中的“folding”，由GustavDoetsch于1923年使用)；后者在20世纪初主导了德国文学。英文名称卷积来自拉丁语con（“在一起”）和volvere（“卷起”），是德语Faltung的直译，俄罗斯变体свертка也是如此。英语术语的第一次使用可以追溯到1934年AurelFriedrichWintner的论文；它后来被Doetsch（1937年），Gardner和Barnes（1942年)的权威著作在文献中得到巩固）。1910年Volterra首次使用了星象符号，不过形式不同。珀西·约翰·丹尼尔用了点符号。卷积的第一个现代表示法为f∗g，这是两者的结合，由Doetsch定义（1923）。

[2] 从技术角度上讲，我这里定义的是循环卷积。

[3]注意，C(W)的行是向量w的转置，导致卷积公式中出现反射，应将其与相关概念区分开来。注意边界条件(C的元素在右上角和左下角)。

[4]我交替使用运算符和矩阵两个术语。

[5] B.Bamieh，发现变换：循环矩阵、圆形卷积和离散傅里叶变换教程（2018）。ar Xiv：1805.05533提供了我在这篇文章中讨论的派生的细节。

[6]有些人经常混淆不变性（在拉丁语中的意思是“不变”)和等变性(“以同样的方式改变”），许多信号处理书籍提到我在这里讨论的属性为“移位不变性”。如果f(S x)=SF(X)，则函数是移位等变量。换句话说，不管是先移位，然后f还是反之亦然。不同的是，移位不变性是不受移位影响的性质：函数f(S x)=f(X)是移位不变的。位移不变性是物理学中的一个基本概念（它通常以“平移对称性”的名义出现），它指出物理定律不取决于空间中的位置。在经典力学的变分公式中，动量守恒定律是根据诺瑟定理由位移不变性发展而来的。

[7]等差的概念更普遍，可以用群体理论来扩展。该框架在T.Cohen和M.Welling，Group等变量卷积网络（2016）中用到。Proc. ICML 将CNN的卷积层的移位等距扩展到更一般的操作，如旋转。假设f：X→Y，其中X和Y是一些不同的空间，分别在X和Y的元素上定义了相应的组

运算，组等差表示为

，其中

。请注意

不一定等于

，因为输出空间Y的结构和偶数维数可以不同于输入X。在这篇文章中讨论的标准卷积是一个特殊的情况，X=Y是n维向量的空间，

是平移组，

是移位算子。

[8] 由于处理的是有限维向量，这里的术语“傅里叶变换”指的是离散傅立叶变换(DFT)。

[9]更准确地说，联合对角化意味着两个交换矩阵具有相同的特征空间，就像在一般情况下，特征值可以具有非平凡的多重性一样。由于在这里讨论的所有的特征值都很简单，所以可以讨论一个共同的特征基。

[10]然而，由于S是不对称的，所以它没有实特征值（对称实矩阵有实特征值）。S的特征值恰好是一个复根。

[11]当称矩阵C被傅里叶变换“对角化”时，意思是矩阵Φ*CΦ是对角化的。由于傅里叶变换是一个正交矩阵(Φ*Φ=I)，它在几何上充当坐标系统的变化，相当于n维旋转。在这个坐标系统中，C的作用为元素乘积。

[12]在信号处理中，通常在频域设计滤波器，因此从未显式计算w的傅里叶变换。

 

原文标题：

Deriving convolution from first principles

原文链接：

https://towardsdatascience.com/deriving-convolution-from-first-principles-4ff124888028 

编辑：于腾凯

校对：林亦霖

译者简介

陈之炎，北京交通大学通信与控制工程专业毕业，获得工学硕士学位，历任长城计算机软件与系统公司工程师，大唐微电子公司工程师，现任北京吾译超群科技有限公司技术支持。目前从事智能化翻译教学系统的运营和维护，在人工智能深度学习和自然语言处理（NLP）方面积累有一定的经验。业余时间喜爱翻译创作，翻译作品主要有：IEC-ISO 7816、伊拉克石油工程项目、新财税主义宣言等等，其中中译英作品“新财税主义宣言”在GLOBAL TIMES正式发表。能够利用业余时间加入到THU 数据派平台的翻译志愿者小组，希望能和大家一起交流分享，共同进步。

翻译组招募信息

工作内容：需要一颗细致的心，将选取好的外文文章翻译成流畅的中文。如果你是数据科学/统计学/计算机类的留学生，或在海外从事相关工作，或对自己外语水平有信心的朋友欢迎加入翻译小组。

你能得到：定期的翻译培训提高志愿者的翻译水平，提高对于数据科学前沿的认知，海外的朋友可以和国内技术应用发展保持联系，THU数据派产学研的背景为志愿者带来好的发展机遇。

其他福利：来自于名企的数据科学工作者，北大清华以及海外等名校学生他们都将成为你在翻译小组的伙伴。