卷积的直观指南 – BetterExplained

想让工科学生坐立不安？让他们解释卷积以及（如果你很残忍）卷积定理。他们会嘟囔着滑动窗口之类的东西，试图从窗户逃出去。

卷积通常是通过其正式定义引入的：

$\displaystyle{ (f * g )(t) = \int_{-\infty}^\infty f(\tau) g(t - \tau) d\tau }$

哎呀。让我们开始吧没有微积分： 卷积是花式乘法。

第1部分：医院类比

想象你管理一家医院，治疗患有单一疾病的病人。你有：

一个治疗方案： [3] 每个患者在第一天获得3单位药物。
一份患者名单： [1 2 3 4 5] 您本周的患者人数（周一1人，周二2人，等等）。

问题：你每天使用多少药物？嗯，那只是一个简单的乘法：

Plan  *  Patients       = Daily Usage
[3]   *  [1 2 3 4 5]    = [3 6 9 12 15]

将计划乘以病人列表，得到未来几天的用药量： [3 6 9 12 15]。日常乘法（3 x 4）意味着只使用一天病人的计划： [3] * [4] = [12].

卷积的直觉

假设疾病发生变异，需要多日治疗。你制定了一个新计划： Plan: [3 2 1]

这意味着第一天用3个单位的药物，第二天2个，第三天1个。好的。在相同的病人计划下 [1 2 3 4 5]，我们每天的用药量是多少？

呃……糟糕。这不是一个简单的乘法：

周一，1名患者进来。这是她的第一天，所以她获得3单位。
周二，周一的女孩获得2单位（她的第二天），但两名新患者到达，每人获得3单位（2 * 3 = 6）。总计为2 + (2 * 3) = 8单位。
周三，更复杂了：周一的女孩结束（1单位，她的最后一天），周二的人获得2单位（2 * 2），还有3名新的周三患者……唉。

病人相互重叠，很难追踪。我们如何组织这个计算？

一个想法：想象翻转病人列表，以便第一个病人在右边：

           Start of line
 5 4 3 2 1

接下来，想象我们有3个独立的房间，每个房间施加适当的剂量：

 Rooms     3 2 1

第一天，你走进第一个房间，得到3个单位的药物。第二天，你走进2号房间，得到2个单位。最后一天，你走进3号房间，得到1个单位。之后没有房间，你的治疗结束。

要计算总药物用量，让患者排成一队，依次走过这些房间：

 Monday
 ----------------------------
 Rooms                  3 2 1                                      
 Patients       5 4 3 2 1

 Usage                  3

周一（我们的第一天），第一个房间里只有一位患者。她得到3个单位，总用量为3。有道理，对吧？

周二，每个人都往前一步：

 Tuesday
 ----------------------------
 Rooms                  3 2 1              
 Patients ->      5 4 3 2 1

 Usage                  6 2      = 8

第一位患者现在在第二个房间，而第一个房间里有2位新患者。我们将每个房间的剂量乘以患者人数，然后相加。

每天我们都让列表向前滑动：

 Wednesday
 ----------------------------
 Rooms                  3 2 1              
 Patients ->        5 4 3 2 1

 Usage                  9 4 1    = 14


 Thursday
 -----------------------------
 Rooms                  3 2 1              
 Patients ->          5 4 3 2 1

 Usage                 12 6 2    = 20


 Friday
 -----------------------------
 Rooms                  3 2 1              
 Patients ->            5 4 3 2 1

 Usage                 15 8 3    = 26

哇！这很复杂，但我们搞清楚了，对吧？我们可以通过反转列表、将其滑动到所需日期并组合剂量来找到任何一天的用量。

逐日的总用量如下所示（别忘了周六和周日，因为有些患者是从周五开始的）：

Plan      *  Patient List   = Total Daily Usage

[3 2 1]   *  [1 2 3 4 5]    = [3 8 14 20 26 14 5]
              M T W T F        M T W  T  F  S  S

这个计算就是卷积计划和患者列表的卷积(Convolution)。这是输入数字列表与“程序”之间的一种花哨乘法。

交互式演示

这里有一个现场演示。尝试改变 F （计划）或 G （患者列表）。卷积 $c(t)$ 与我们上面的手工计算一致。

（我们定义函数 $f(x)$ 和 $g(x)$ 将每个列表用零填充，并调整列表索引从1开始。）

你可以用 Wolfram Alpha:

ListConvolve[{3, 2, 1}, {1, 2, 3, 4, 5}, {1, -1}, 0]
{3, 8, 14, 20, 26, 14, 5}

快速进行卷积。（额外的 {1, -1}, 0 对齐列表并用零填充。）

应用：COVID呼吸机使用

我5年前开始写这篇文章（直觉需要时间……），但不幸的是，这个类比在今天仍然适用。

让我们用卷积(Convolution)来估计新入院患者的呼吸机使用量。

设$f(x)$为需要呼吸机的患者百分比。例如， [.05 .03 .01] 表示第一周5%的患者需要呼吸机，第二周3%，第三周1%。
设 $g(x)$ 为每周新入院患者数（单位：千人）。
卷积 $c(t) = f * g$ 表示每周所需的呼吸机数量（单位：千台）。$c(5)$ 是从现在起5周后所需的呼吸机数量。

让我们试一试：

F = [.05, .03, .01] 是每周的呼吸机使用率
G = [10, 20, 30, 20, 10, 10, 10]，是新入院患者数量。最初为每周1万人，上升至3万人，然后衰减至1万人。

根据这些数字，我们预计在2周内最大呼吸机使用量为2.2千：

卷积在9周后降至0，因为患者名单已用完。在这个例子中，我们关心的是卷积达到的峰值，而不是长期总量。

其他需要进行卷积(Convolve)的场景可能包括药物剂量、疫苗接种预约（今天一剂，一个月后另一剂）、再感染以及其他复杂的相互作用。

医院类比是我在学习时所希望拥有的心智模型。既然我们已经用实际数字试过了，现在让我们加入数学要素，将这个类比转化为微积分。

第2部分：微积分定义

那么，在我们的例子中发生了什么？我们有一个患者列表和一个计划。如果计划很简单（单日 [3]），那么普通的乘法就可以了。但因为计划复杂，我们不得不对其进行“卷积”(Convolve)。

现在来一些趣味事实(Fun Facts™)：

卷积写作 $f * g$，使用星号。是的，星号通常表示乘法，但在高等微积分课程中，它表示卷积。普通乘法只是隐含的（$fg$）。
卷积的结果是一个新的函数它给出了任意一天的总使用量（“第 $t=3$ 天的总使用量是多少？”）。我们可以将卷积随时间绘制成图表，以查看逐日总量。

现在的大发现： 卷积反转了其中一个列表！ 原因如下。

让我们称我们的治疗方案为 $f(x)$。在我们的例子中，我们使用了 [3 2 1].

患者列表（输入）是 $g(x)$。然而，我们需要反转在滑动列表时反转它，这样最早的患者（周一）先入院（先进先出）。这意味着我们需要使用 $g(-x)$，即 $g(x)$ 的水平镜像。 [1 2 3 4 5] 变为 [5 4 3 2 1].

现在我们有了反转后的列表，选择一个日期进行计算（$t = 0, 1, 2...$）。要将患者列表滑动这么多天，我们使用：$g(-x + t)$。也就是说，我们反转列表（$-x$）并跳到正确的那一天（$+t$）。

我们得到了我们的场景：

$f(x)$ 是使用计划
$g(-x + t)$ 是输入列表（翻转并向右滑动到指定日期）。

要得到第 $t$ 天的总使用量，我们将每个患者与计划相乘，并将结果相加（一个积分）。为了考虑任何可能的长度，我们从负无穷到正无穷进行。

现在我们可以用微积分正式描述卷积：

（就像彩色数学？还有更多。）

呼！符号还真不少。一些注意点：

我们使用一个虚拟变量 $\tau$（tau）进行中间计算。想象 $\tau$ 像敲响每个房间（$\tau={0, 1, 2, 3...}$），找到剂量[$f(\tau)$]、患者数量[$g(t - \tau)$]，将它们相乘，并在积分中求和。哎呀。所谓的“虚拟”变量 $\tau$ 就像 i 在一个 for 循环：它是临时的，但完成了工作。（类比：$t$ 是一个全局变量，在循环期间具有固定值：它是我们计算使用量的那天，例如 t = Day 5).
在官方定义中，你会看到 $g(t - \tau)$ 而不是 $g(- \tau+ t)$。第二种形式显示了翻转（$-\tau$）和滑动（$+t$）。写成 $g(t - \tau)$ 会让人觉得我们关心变量之间的差异，这曾让我困惑。
治疗方案（要运行的程序）被称为核：你将一个核与输入进行卷积。

还好，对吧？这个等式是对该类比的形式化描述。

第3部分：卷积的数学性质

发现一个新的数学运算怎么能不试跑一下呢？让我们看看它的表现。

卷积是可交换的：f * g = g * f

在我们的计算中，我们翻转了患者列表而保持计划不变。我们是否可以翻转计划呢？

当然可以。想象患者是固定的，待在他们的房间里： [1 2 3 4 5]。为了输送药物，我们有3辆医疗推车，每辆车进入每个房间并发放剂量。每天，它们向前滑动一个位置。

  Carts ->
  1 2 3

      1 2 3 4 5
      Patients

和之前一样，虽然我们的计划写的是 [3 2 1] （第一天3个单位），我们将推车的顺序翻转为[1 2 3]。这样，患者在第一天就能得到3个单位，正如我们预期。用Wolfram Alpha验证，计算是相同的。

ListConvolve[{1, 2, 3, 4, 5}, {3, 2, 1}, {1, -1}, 0]
{3, 8, 14, 20, 26, 14, 5}

酷！看起来卷积是可交换的：

$\displaystyle{f * g = g * f}$

并且在计算积分时我们可以选择翻转 $f$ 或 $g$。令人惊讶，对吧？

卷积的积分

当所有治疗都完成后，总计总用药量是多少？这就是 卷积的积分。（几分钟前，那个短语还会让你想跳楼。）

但这其实是个简单的计算。我们的计划给每位患者 sum([3 2 1]) = 6 单位的药物。而我们共有 sum([1 2 3 4 5]) = 15 患者。总用量就是 6 x 15 = 90 单位。

哇，这很简单：对于整个卷积就是各个部分和的乘积！

$\displaystyle{\int (f * g) = \int f \cdot \int g }$

我希望这能直观理解。注意，这个技巧适用于卷积，但一般不适用于积分。例如：

$\displaystyle{ \int (x \cdot x) \ne \int x \cdot \int x }$

如果我们将$x \cdot x$拆分为两个积分，我们会得到：

$ \int (x \cdot x) = \int x^2 = \frac{1}{3} x^3 $
$\int x \cdot \int x = \frac{1}{2}x^2 \cdot \frac{1}{2}x^2 = \frac{1}{4}x^4$

而它们并不相同。（如果我们可以这样拆分积分，微积分会容易得多。）奇怪的是，$\int (f * g)$可能比$\int (fg)$更容易求解。

脉冲响应

如果我们只送一位患者通过医院会发生什么？卷积就只是那天的计划。

Plan    * Patients = Convolution
[3 2 1] * [1]      = [3 2 1]

换句话说，与……卷积 [1] 就得到原始计划。

在微积分术语中，一个尖峰 [1] （其余为零）就是狄拉克δ函数。就卷积而言，这个函数的作用类似于数字1，返回原函数：

$\displaystyle{f(t) * \delta(t) = f(t)}$

我们可以将德尔塔函数延迟T，这也延迟了最终的卷积函数。想象一下，我们的唯一患者晚到了一周（$\delta(t - T)$），因此我们的药物使用也延迟了一周：

$\displaystyle{f(t) * \delta(t - T) = f(t - T)}$

第4部分：卷积定理与傅里叶变换

这个傅里叶变换(Fourier Transform) （用花体$\mathscr{F}$表示）将函数$f(t)$转换为一组循环成分$F(s)$：

$\displaystyle{f(t) \xrightarrow{\mathscr{F}} F(s)}$

作为一个运算符，这可以写成$\mathscr{F}\lbrace f \rbrace = F$。

在我们的类比中，我们通过一种巧妙的乘法将计划和患者列表卷积。既然傅里叶变换给出了成分列表，我们能否通过混合来得到相同的结果？ 配料列表?

是的，可以： 常规世界中的花式乘法是常规花式世界中的乘法。

在数学术语中，“时域中的卷积就是频域（傅里叶）中的乘法。”

数学上，这写作：

$\displaystyle{f * g \xrightarrow{\mathscr{F}} FG}$

或者

$\displaystyle{\mathscr{F}\lbrace f * g \rbrace = FG}$

其中 $f(x)$ 和 $g(x)$ 是要卷积的函数，它们的变换分别为 $F(s)$ 和 $G(s)$。

我们可以证明此定理借助高等微积分，它使用了一些我不太理解的定理，但让我们思考一下其含义。

因为 $F(s)$ 是 $f(t)$ 的傅里叶变换，我们可以询问一个特定频率（$s = 2\text{Hz}$），并得到 组合交互 每个数据点与该频率的贡献。假设：

$\displaystyle{F(2) = 3 + i}$

这意味着在每个数据点都与2Hz周期相乘后，结果是 $3 + i$。但我们本可以保持每个交互独立：

$\displaystyle{F(2) = 3 + i = c_0 + c_1 + c_2 + c_3 ... + c_t}$

其中 $c_t$ 是数据点 $t$ 对2Hz频率的贡献。类似地，我们可以将 $G(s)$ 展开为与2Hz成分的交互列表。假设 $G(2) = 7 - i$：

$\displaystyle{G(2) = 7 - i = d_0 + d_1 + d_2 + d_3 ... + d_t}$

卷积定理实际上是在说：

$\displaystyle{f * g \xrightarrow{\mathscr{F}} FG = (c_0 + c_1 + c_2 + ...)(d_0 + d_1 + d_2 + ...)}$

我们在常规域中的卷积涉及大量的交叉乘法。在花哨的频率域中，我们仍然有一堆交互，但 $F(s)$ 和 $G(s)$ 已经合并了它们。我们只需相乘 $F(2)G(2) = (3 + i)(7-i)$ 即可找到卷积结果中的2Hz成分。

类比一下，假设你想要计算：

$\displaystyle{(1 + 2 + 3 + 4)(5 + 6 + 7 + 8) = ?}$

交叉相乘每一项会很麻烦：$(1 \cdot 5) + (1\cdot 6) + (1\cdot 7) + ...$

更好的做法是将各组分别合并为 $(1 + 2 + 3 + 4) = 10$ 和 $(5 + 6 + 7 + 8) = 26$，然后然后相乘得到 $10 \cdot 26 = 260$。

这个细微差别让我很困惑。看起来 $FG$ 是一个单一的乘法，而 $f * g$ 涉及一堆中间项。我忘了 $F$ 已经完成了将一堆条目合并为一个的工作。

现在，我们还没有相当完成。

$\displaystyle{f * g \xrightarrow{\mathscr{F}} FG \xrightarrow{\mathscr{F^{-1}}} \ ?}$

我们可以将时域中的 $f * g$ 转换为频域中的 $FG$，但可能我们需要将其转换回时域才能得到可用的结果：

$\displaystyle{f * g = \mathscr{F}^{-1} \lbrace FG \rbrace}$

你有一个英文谜语（$f * g$），将其翻译成法语（$FG$），让你聪明的法国朋友算出结果，然后再将其转换回英语（$\mathscr{F}^{-1}$）。

反之亦然...

卷积定理也是以这种方式工作的：

$\displaystyle{fg \xrightarrow{\mathscr{F}} F * G}$

常规世界中的常规乘法是花式世界中的花式乘法。

很酷，对吧？不用像穴居人那样把两个函数相乘，戴上单片眼镜，对傅里叶变换做卷积，然后转换到时域：

$\displaystyle{fg = \mathscr{F}^{-1} \lbrace F*G \rbrace}$

我不是说这很有趣，只是说这是可能的。如果你的法国朋友遇到棘手的计算问题，对你来说可能只是算术。

简证

还记得我们说卷积的积分就是各自积分的乘积吗？

$\displaystyle{\int (f * g) = \int f \cdot \int g }$

嗯，傅里叶变换只是一个非常特殊的积分，对吧？

$\displaystyle{\int \rightarrow \mathscr{F}}$

所以（粗略地），似乎我们可以把通用积分 $\int$ 换成 $\mathscr{F}$，得到

$\displaystyle{\mathscr{F} (f * g) = \mathscr{F} (f) \cdot \mathscr{F} (g) }$

这就是卷积定理。我对证明需要更深入的理解，但这有助于理解。

第5部分：应用

卷积的技巧在于找到一个有用的“程序”（核）来应用于你的输入。这里有几个例子。

移动平均

假设你想对列表中相邻元素做移动平均。即每个元素的一半相加：

$\displaystyle{\frac{a + b}{2} = \frac{a}{2} + \frac{b}{2}}$

这是一个“乘法程序”，用 [0.5 0.5] 与我们的列表进行卷积：

ListConvolve[{1, 4, 9, 16, 25}, {0.5, 0.5}, {1, -1}, 0] 
{0.5, 2.5, 6.5, 12.5, 20.5, 12.5}

我们可以用单个操作实现移动平均。不错！

一个3元素移动平均是 [.33 .33 .33]，加权平均可以是 [.5 .25 .25].

导数

导数计算相邻值的差。计划如下： [1 -1]

ListConvolve[{1, 2, 3, 4, 5}, {1, -1}, {1, -1}, 0] 
{1, 1, 1, 1, 1, -5}                         // -5 since we ran out of entries

ListConvolve[{1, 4, 9, 16, 25}, {1, -1}, {1, -1}, 0] 
{1, 3, 5, 7, 9, -25}                        // discrete derivative is 2x + 1

用简单的核，我们可以在离散列表上找到有用的数学性质。要得到二阶导数，只需将导数卷积应用两次：

F * [1 -1] * [1 -1]

作为捷径，我们可以预先计算最终的卷积（[1 -1] * [1 -1] ）得到：

ListConvolve[{1, -1}, {1,-1}, {1, -1}, 0] 
{1, -2, 1}

现在我们有了一个单个核 [1, -2, 1] ，可以获取列表的二阶导数：

ListConvolve[{1, 4, 9, 16, 25}, {1, -2, 1}, {1, -1}, 0] 
{1, 2, 2, 2, 2, -34, 25}

排除边界项，我们得到预期的二阶导数：

$\displaystyle{x^2 \xrightarrow{d/dx} 2x \xrightarrow{d/dx} 2}$

图像模糊/去模糊

图像模糊本质上就是你的图像与某个“模糊核”的卷积：

$\displaystyle{\text{blurred} = \text{image} * \text{blur}}$

我们2D图像的模糊需要一个二维平均:

我们能消除模糊吗？能！借助我们的朋友——卷积定理，我们可以：

$\displaystyle{\text{blurred} = \text{image} * \text{blur}}$

$\displaystyle{\mathscr{F} \lbrace \text{blurred} \rbrace = \mathscr{F} \lbrace \text{image} * \text{blur} \rbrace}$

$\displaystyle{\mathscr{F} \lbrace \text{blurred} \rbrace = \mathscr{F} \lbrace \text{image} \rbrace \mathscr{F} \lbrace \text{blur} \rbrace}$

$\displaystyle{\frac{ \mathscr{F} \lbrace \text{blurred} \rbrace }{\mathscr{F} \lbrace \text{blur} \rbrace} = \mathscr{F} \lbrace \text{image} \rbrace }$

$\displaystyle{\mathscr{F}^{-1} \lbrace \frac{ \mathscr{F} \lbrace \text{blurred} \rbrace }{\mathscr{F} \lbrace \text{blur} \rbrace} \rbrace = \text{image}}$

哇！我们可以通过除以模糊来恢复原始图像。卷积在频域中是简单的乘法，而 反卷积 在频域中是简单的除法。

不久前，“通过除法傅里叶变换去模糊”的概念对我来说还是天书。虽然它在数学上可能令人生畏，但概念上正在变得简单。

更多阅读：

维基百科关于反卷积, 去模糊.
图像复原讲座, 另一个和上述示例
盲反卷积是指当你不知道模糊核（进行猜测）时

算法技巧：乘法

数字是什么？一串数字：

1234 = 1000 + 200 + 30 + 4 = [1000 200 30 4]
5678 = 5000 + 600 + 70 + 8 = [5000 600 70 8]

那么常规的小学乘法是什么？逐位的卷积！我们用一个数字列表扫描另一个，一边乘一边加：

来源

我们可以通过卷积数字列表来执行计算（wolfram alpha):

ListConvolve[{1000, 200, 30, 4}, {8, 70, 600, 5000}, {1, -1}, 0]
{8000, 71600, 614240, 5122132, 1018280, 152400, 20000}

sum {8000, 71600, 614240, 5122132, 1018280, 152400, 20000}
7006652

注意我们预先翻转了其中一个列表（稍后在卷积中会被交换），中间计算有点不同。但是，组合小计得到预期结果。

更快的卷积

为什么要卷积而不是常规的逐位乘法？嗯，卷积定理让我们可以用傅里叶变换替换卷积：

$\displaystyle{f * g = \mathscr{F}^{-1} \lbrace FG \rbrace}$

卷积（$f * g$）的复杂度为 $O(n^2)$。我们有 $n$ 个位置需要处理，每个位置有 $n$ 个中间乘法。

右侧涉及：

两个傅里叶变换，通常是 $O(n^2)$ 的。但是，快速傅里叶变换（一种分治策略）使它们变为 $O(n\log(n))$。
变换最终结果的逐点乘法（$\sum a_n \cdot b_n$），复杂度为 $O(n)$
逆变换，复杂度为 $O(n\log(n))$

总复杂度为：$O(n\log(n)) + O(n\log(n)) + O(n) + O(n\log(n)) = O(n\log(n))$

在高级域中的常规乘法更快比常规域中的高级乘法更高效。我们的法国朋友可不简单。（更多)

卷积神经网络(CNN)

机器学习就是发现将输入数据转换为期望结果（如预测、分类等）的数学函数。

从输入信号开始，我们可以将其与一堆核进行卷积：

$\displaystyle{\text{input} * k_1 * k_2 * k_3 ... = \text{result}}$

Given that convolution can do complex math (moving averages, blurs, derivatives...), it seems 一些 combination of kernels should turn our input into something useful, right?

Convolutional Neural Nets (CNNs) process an input with layers of kernels, optimizing their weights (plans) to reach a goal. Imagine tweaking the treatment plan to keep medicine usage below some threshold.

CNNs are often used with image classifiers, but 1D data sets work just fine.

精彩文章： https://ujjwalkarn.me/2016/08/11/intuitive-explanation-convnets/
数字分类器演示： https://cs.stanford.edu/people/karpathy/convnetjs/demo/mnist.html

LTI系统行为

A linear, time-invariant system means:

线性：按比例缩放和组合输入，会按相同比例缩放和组合输出
时间不变性：输出依赖于相对时间，而非绝对时间。你在第一天得到3个单位，你的无论它是星期三还是星期四。

A fancy phrase is "A LTI system is characterized by its impulse response". Translation: If we send a 单个 patient through the hospital [1], we'll discover the treatment plan. Then we can predict the usage for 任意 sequence of patients by convolving it with the plan.

$\displaystyle{\text{system response} = \text{impulse response} * \text{inputs}}$

If the system isn't LTI, we can't extrapolate based on a 单个 person's experience. Scaling the inputs may not scale the outputs, and the actual calendar day, not relative day, may impact the result (imagine fewer rooms available on weekends).

工程类比

From David Greenspan: "Suppose you have a special laser pointer that makes a star shape on the wall. You tape together a bunch of these laser pointers in the shape of a square. The pattern on the wall now is the convolution of a star with a square."

Regular multiplication gives you a single scaled copy of an input. Convolution creates multiple overlapping copies that follow a pattern you've specified.

Real-world systems have squishy, not instantaneous, behavior: they ramp up, peak, and drop down. The convolution lets us model systems that echo, reverb and overlap.

Now it's time for the famous sliding window example. Think of a pulse of inputs (red) sliding through a system (blue), and having a combined effect (yellow): the convolution.

(来源)

总结

Convolution has an advanced technical definition, but the basics can be understood with the right analogy.

Quick rant: I study math for fun, yet it took years to find a satisfying intuition for:

为什么一个函数要反转？
为什么卷积是可交换的？
为什么卷积的积分等于积分的乘积？
为什么傅里叶变换是逐点相乘，而不是重叠？

Why'd it take so long? Imagine learning multiplication with $f \times g = z$ instead of $3 \times 5 = 15$. Without an example I can explore 在我的脑海中, I could only memorize results, not intuit them. Hopefully this analogy can save you years of struggle.

数学愉快。

卷积(Convolution)的直观指南