A.1 离散数学速成 集合、逻辑、图论与组合

1.为什么深度学习也要管离散数学

说起来，深度学习听起来全是微积分和线性代数，怎么到这一篇我们忽然要聊离散数学呢？其实你稍微留意一下就会发现，模型里到处都是离散的影子。一个batch里有几个样本、词表有多大、神经网络一共有几层，这些数都是一段一段跳的整数，和连续滑动的实数不太一样。微积分研究的是连续变化的对象，而离散数学研究的，正是这种一段段、一个个分开来的对象，包括集合、图、逻辑命题和计数问题。

计算机科学的底子，恰恰就是离散数学。你看，CPU一拍一拍地执行指令，内存一格一格地存数据，就连我们写代码常用的那些数据结构，像数组、链表、哈希表，本质上也都是离散的。说穿了，深度学习模型最后总要落到代码上跑，而代码的世界天生就是离散的。所以这一篇，我们不妨把这层底子稍微补一补，重点讲集合和逻辑、图论、组合计数这三块，后面很多章节其实都悄悄用着它们。

我记得小张第一次去大厂面试的时候，被问到注意力机制到底在数学上是个什么东西，他支支吾吾了半天，最后才明白面试官想听的就是那么一句，每个token和其它所有token之间都连一条带权重的边，这其实就是一张完全图。这么一想，离散数学离我们并没有那么远。

2.集合与逻辑：表达条件的基本工具

我们先从最朴素的集合讲起。集合（set）就是一堆互不相同的对象凑在一起的整体，这些对象叫做集合的元素。我们把元素 $x$ 属于集合 $A$ 这件事写成 $x \in A$，这里的 $\in$ 就是表示属于这个关系的符号。一个集合要怎么描述清楚呢，常见的有两种法子。一种是把里面的元素一个一个列出来，比方说 $A=\{1,2,3\}$。另一种是写一条规则，比方说 $B=\{x \mid x \text{ 是偶数}\}$，这里的竖线 $\mid$ 读作满足，整条式子的意思就是 $B$ 是所有满足（是偶数）这个条件的 $x$ 凑起来的集合。

集合之间最常见的几种运算，无非是并、交、补这老三样。把集合 $A$ 和集合 $B$ 里的元素全部凑在一起，去掉重复的，得到的就是并集，记作 $A \cup B$，这里的 $\cup$ 是并运算的符号。两个集合里共同存在的元素凑在一起，得到的就是交集，记作 $A \cap B$，$\cap$ 是交运算的符号。要是我们在一个更大的范围里看，这个更大的范围叫全集，记作 $U$，那么全集里那些不属于 $A$ 的元素，构成的就是补集，记作 $A^c$。这三样运算凑在一起，就足够我们描述相当多的条件组合了。

说起来，集合和逻辑其实是一体两面。一条命题（proposition）就是一句能判断真假的话，比方说今天下雨了这句话，要么确实在下雨，要么没下，只有真和假两种情况，没有第三种。我们用小写字母 $p$、$q$ 来代指命题，用 $\land$ 表示并且（逻辑与），用 $\lor$ 表示或者（逻辑或），用 $\lnot$ 表示非（逻辑否定），用 $\rightarrow$ 表示蕴含，也就是如果那么这种结构。比方说 $p \land q$ 就是说 $p$ 和 $q$ 同时为真，整条式子才为真。小明在写训练循环的时候，常常要判断损失下降并且还没到最大轮数这件事，化成符号就是 $p \land q$，机器只认这种符号化的表达。

不过命题逻辑有个不够用的地方，它没法谈所有的和存在一个这种意思。于是我们要请出谓词逻辑（predicate logic），它在命题之外再加两个量词。一个是全称量词 $\forall$，读作对所有的，比方说 $\forall x \in A,\ p(x)$ 的意思就是对集合 $A$ 里的每一个元素 $x$，条件 $p(x)$ 都成立。另一个是存在量词 $\exists$，读作存在一个，$\exists x \in A,\ p(x)$ 的意思是集合 $A$ 里至少有一个 $x$ 让 $p(x)$ 成立。这里的 $p(x)$ 是一个谓词，也就是带有一个变量 $x$ 的条件，给 $x$ 代入具体的值之后就能判断真假。这两把量词加上去，就能表达相当精细的条件了，论文里那种对任意输入 $x$ 模型输出都满足某种约束的话，写出来用的就是它。

3.图论：关系结构的通用语言

集合讲完了，我们再来看图论，这一块是离散数学里和深度学习关系最紧密的部分。

图（graph）这件事说起来很朴素，由两部分组成，一部分叫节点（vertex），一部分叫边（edge）。我们把一张图记作 $G=(V,E)$，其中 $G$ 是这张图，$V$ 是所有节点组成的集合，$E$ 是所有边组成的集合。一条边就是连接两个节点的一条线，比方说节点 $u$ 和节点 $v$ 之间有一条边，就写成 $(u,v) \in E$。节点的度数（degree）就是连在它身上的边的条数，度数大的节点关系多，度数小的节点关系少。

边要是带方向，从 $u$ 指向 $v$，那张图就叫有向图（directed graph）。边要是不带方向，能来回走，就叫无向图（undirected graph）。路径（path）说的是一串节点，相邻两个之间都有边连着，能从一头走到另一头。要是任意两个节点之间都能找到一条路径走通，整张图就是连通的，叫连通图。

树（tree）是一种特别整齐的图，它是无向的、连通的、并且没有环的。说穿了，树就是一张不会绕圈子的连通图。我们前面在3.2 节讲过的计算图，本质上就是一张有向无环图（Directed Acyclic Graph，缩写成DAG），有向是说每条边都有方向，从前一层指向后一层，无环是说顺着方向走不会绕回原点。你看，反向传播能一路算下去不出岔子，靠的就是无环这个性质，要是有环，梯度就不知道该在哪几个节点之间来回打转了。A.3 节和A.4 节讲的那些搜索算法，像宽度优先和深度优先，说到底都是在图上找路，背后用到的就是图的遍历。A.5 节里那种用蒙特卡洛树搜索（Monte Carlo Tree Search，缩写MCTS）来做决策的过程，背后站着的也还是一棵不断往外展开的树。

图论里有个特别经典的问题，叫拓扑排序（topological sort），专门用来处理有先后依赖关系的任务。比方说小张开了一家奶茶店，做一杯奶茶要先煮茶、再加奶、再加糖、最后封口，这几步是有先后顺序的，糖加早了化不开，封口加早了后面什么都进不去。把这件事看作一张DAG，每个步骤是一个节点，（必须在某步之前完成）这种关系画成有向边，拓扑排序给出的就是一条合法的执行顺序。深度学习框架里做算子调度，也就是决定哪些算子先算、哪些后算，骨子里也是同一个问题。

4.组合计数：把可能数清楚

最后我们来聊组合计数，这一块看似朴素，其实是分析算法复杂度和算概率的看家本领。

计数最基本的一条原理叫加法原理：如果一件事有 $m$ 种做法，另一件和它互斥的事（也就是两件事不能同时发生）有 $n$ 种做法，那么这两件事合起来一共有 $m+n$ 种做法。紧挨着的是乘法原理：如果一件事分两步完成，第一步有 $m$ 种选择，第二步无论第一步怎么选都有 $n$ 种选择，那么整件事一共有 $m \times n$ 种做法，这里的 $\times$ 是乘号。这两条原理听起来像是废话，可真要排起东西来，全是它们的功劳。

从 $n$ 个不同的元素里挑出 $k$ 个，挑出来之后还要排成一队，顺序不一样就算两种，这种叫排列（permutation），总数记作 $P(n,k)$，公式是：

$$P(n,k) = \frac{n!}{(n-k)!}$$

这里的 $n!$ 读作 $n$ 的阶乘，意思是从 $1$ 一直乘到 $n$，也就是 $n! = n \times (n-1) \times \cdots \times 1$，式子里的 $\cdots$ 表示中间省略的部分按同样规律一直乘下去。分母里的 $(n-k)!$ 之所以出现，是因为 $n!$ 把全部 $n$ 个元素都排了，可我们只在乎前 $k$ 个位置上站的是谁，剩下那 $n-k$ 个元素怎么排都算同一种，所以要把那 $(n-k)!$ 种多余排法除掉。

要是挑出来之后不在乎顺序，只要凑成一堆就行，这种叫组合（combination），总数记作 $\binom{n}{k}$，读作从 $n$ 中选 $k$，公式是：

$$\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$$

和排列的公式一比，组合的分母多了一个 $k!$，这是因为挑出来的那 $k$ 个元素内部的 $k!$ 种排法我们都不在乎了，要一起除掉。

这些计数工具在深度学习里常常悄悄出现。比方说分析某个搜索算法最坏情况下要走多少步，本质上就是在数图里路径的条数。再比方说算从一批样本里随机抽几个组成一个小批量（mini-batch）有多少种抽法，用的就是 $\binom{n}{k}$。还记得3.6 节讲过的dropout吧，每个神经元独立地以概率 $r$ 被丢弃，一层有 $n$ 个神经元的话，所有可能的丢弃组合加起来一共有 $2^n$ 种（每个神经元要么丢要么不丢，是两种选择，$n$ 个连乘就得到 $2^n$），这里的 $2^n$ 表示 $2$ 自乘 $n$ 次。这个数随 $n$ 涨得飞快，也是dropout能制造出足够多扰动的一个数学原因。

5.回到深度学习：离散结构无处不在

讲了这么多，我们最后把话收一收，看看这些东西在深度学习里到底藏在哪儿。

注意力机制，说穿了就是把输入里的每一个token看成图上的一个节点，任意两个节点之间都连一条带权重的边，整张图就是一张完全图（complete graph，意思是每两个节点之间都有边的图）。权重就是注意力分数，模型学的也就是这张图上每条边该有多重。这么一看，自注意力其实就是图上的一种消息传递。

我们一直挂在嘴边的计算图，就是3.2 节里那张DAG，节点是运算，边是数据流向。训练里反复用的反向传播，就是在这张DAG上从输出端一路倒着把梯度传回去，每经过一个节点就按链式法则乘一次。A.5 节里那种用蒙特卡洛树搜的决策过程，背后是一棵在搜索中不断展开的树。混合专家（MoE）里的路由器把token分给不同的专家，可以看成给一张二部图（bipartite graph，节点分成两拨、边只在两拨之间连的图）做匹配，一拨是token，一拨是专家。就连我们平时调参、设随机种子、做数据划分，背后也都站着组合和概率的身影。

我之前看过一本讲算法竞赛的小说，里头的主人公把一张复杂的关系图画在草稿纸上，盯着看了半天忽然理清了思路，这种情节其实挺写实。图这种东西的好处就在于一画出来，关系一目了然，谁连着谁、谁依赖谁，比文字描述清楚得多。我们平时画的那些网络结构图、计算流图、注意力连线图，本质上都是在用图论的眼睛看模型。

说起来，离散数学这门课在大学里常常被大家当成应付考试的硬骨头，背一堆定理、刷一堆证明题，考完就忘。可一旦你真的开始写模型、读论文、做工程，就会发现它一直在那儿安安静静地起着作用。今天这一篇只是把几块最常用的石头搬出来认认脸，真要往深里走，集合论、图论、组合数学各自都是厚厚一摞书。不过对日常看深度学习来说，先把这些基本概念和它们之间的联系理顺，也就够用得很了。

今天就到这儿，下一章见。

练习

Q1. 命题逻辑里的 $\land$（与）、$\lor$（或）、$\lnot$（非）分别对应深度学习训练里常见的哪种条件判断？

$\land$（与）对应"两个条件同时成立"，比如训练循环里"损失下降 并且 还没到最大轮数"才继续练，写成 $p\land q$；$\lor$（或）对应"至少一个成立"，比如"早停触发 或者 显存不足"就停训；$\lnot$（非）对应取反，比如"没有NaN"才继续。机器只认这种符号化的真假表达，写代码时它们就是 &&、||、! 这些运算符。

Q2. 全称量词 $\forall$ 和存在量词 $\exists$ 各表示什么意思？请把"对任意输入 $x$，模型输出都满足约束 $C$"用符号写出来。

$\forall$ 读作"对所有的"，表示某个条件对集合里每一个元素都成立；$\exists$ 读作"存在一个"，表示集合里至少有一个元素让条件成立。"对任意输入 $x$，模型输出都满足约束 $C$"写成 $\forall x,\ C(f(x))$，其中 $f(x)$ 是模型输出、$C(\cdot)$ 是约束条件。论文里那种"对任意输入都满足某种约束"的话，用的就是它。

Q3. 易错点：树和"有向无环图（DAG）"是一回事吗？为什么反向传播要求计算图是无环的？

不完全是一回事。树是一种特别整齐的无向、连通、无环图（每个节点只有一个父节点）；DAG是有向（每条边有方向）、无环（顺着方向走不会绕回原点）的图，树可以看作DAG的特例，但DAG允许多个父节点（比如一个节点由几个前置节点共同汇出）。深度学习框架里的计算图是DAG（节点是运算、边是数据流向），反向传播靠链式法则沿DAG从输出端倒着把梯度传回去——要求无环是因为如果有环，梯度会在那几个节点之间来回打转、不知道该停在哪，反向传播就算不下去了。所以"无环"是反向传播能正确执行的前提。