集合、命题、逻辑与量词

层级：A｜必学

1. 这不是形式主义

机器学习处处在描述“哪些对象属于哪里”“某个条件对哪些对象成立”：训练集是样本的集合，类别是标签的集合，假设空间是候选模型的集合，概率事件是样本空间的子集，定理用量词限定结论。若忽略集合和逻辑，最容易出现的不是算错，而是误读问题本身。

2. 集合与元素

集合是一组确定对象的汇集。可以枚举：

也可以用条件描述：

$x\in A$ 表示 $x$ 是 $A$ 的元素。空集 $\varnothing$ 不含任何元素。集合本身也能成为另一个集合的元素，因此要区分 $x\in A$ 与 $X\subseteq A$。

若 $A$ 的所有元素也属于 $B$，记作 $A\subseteq B$。若还知道 $A\ne B$，可写 $A\subsetneq B$。幂集 $2^A$ 或 $\mathcal P(A)$ 是 $A$ 所有子集构成的集合；若有限集合 $A$ 有 $n$ 个元素，幂集有 $2^n$ 个元素。

3. 集合运算

设 $A,B$ 是两个集合：

• 并集 $A\cup B$：属于 $A$ 或属于 $B$ 的元素；这里的“或”包含两者都属于的情况。
• 交集 $A\cap B$：同时属于 $A$ 和 $B$。
• 差集 $A\setminus B$：属于 $A$ 但不属于 $B$。
• 补集 $A^c$：相对于给定全集，不属于 $A$ 的元素。
• 笛卡尔积 $A\times B=\{(a,b):a\in A,b\in B\}$：所有有序对。

De Morgan 律：

直观地，“并非至少一个发生”等价于“两个都不发生”；“并非同时发生”等价于“至少一个不发生”。

4. 命题与真值

命题是可以判断真假的陈述。例如“$3>2$”是真命题，“$x>2$”在没有给定 $x$ 或量词时只是含变量的谓词。

常用逻辑连接词：

$P\Rightarrow Q$ 中，$P$ 是充分条件，$Q$ 是必要条件。不要把它自动倒过来。比如“矩阵可逆 $\Rightarrow$ 行列式非零”成立，反过来也成立需要另一个定理；不能仅凭原命题得出。

原命题 $P\Rightarrow Q$ 与逆否命题 $\neg Q\Rightarrow\neg P$ 等价，但与逆命题 $Q\Rightarrow P$ 不一定等价。

5. 全称量词与存在量词

• $\forall$：对所有。例如 $\forall x\in\mathbb R, x^2\ge0$。
• $\exists$：至少存在一个。例如 $\exists x\in\mathbb R, x^2=4$。
• $\exists!$：存在唯一一个。

量词的顺序非常重要：

表示对每个 $x$ 都能找一个更大的 $y$，这是真的；而

表示存在一个实数比所有实数都大，这是假的。

量词取否定时：

所以要否定“所有模型都泛化良好”，只需找到一个反例；要证明“没有模型满足条件”，则必须排除所有模型。

6. 集合大小与索引

有限集合 $A$ 的元素个数记为 $|A|$。注意它与绝对值共用竖线，含义由对象决定。例如训练集 $D=\{(\boldsymbol x_i,y_i)\}_{i=1}^n$ 满足 $|D|=n$。

索引集合常写作 $[n]=\{1,2,\ldots,n\}$。这不是所有教材的统一约定，作者通常会先定义。

7. 在机器学习中的位置

数据集与类别集合

$D$ 是有 $n$ 个样本的数据集，$\mathcal Y$ 是标签空间。二分类常取 $\mathcal Y=\{0,1\}$ 或 $\{-1,+1\}$。

严格说，数据集有时需要保留重复样本与顺序，因此更像序列或多重集；教材常为简洁仍使用集合记号。

事件是样本空间的子集

掷骰子的样本空间 $\Omega=\{1,2,3,4,5,6\}$。“偶数”事件 $A=\{2,4,6\}\subseteq\Omega$。$A\cap B$ 对应两个事件同时发生。

假设空间

模型训练常写为从假设集合 $\mathcal H$ 中选择函数：

这句话的逻辑对象是：候选函数集合、经验风险函数，以及返回最小风险函数的选择操作。

分类指标

设真实正例集合为 $P$，预测正例集合为 $\hat P$：

• 真正例：$P\cap\hat P$；
• 假正例：$P^c\cap\hat P$；
• 假负例：$P\cap\hat P^c$。

集合图能直接解释准确率、精确率与召回率的分子分母。

8. 易错点

1. $\{1,2\}$ 与 $(1,2)$ 不同：前者常是集合，后者常是有序对或开区间。
2. $1\in\{1,2\}$，但 $\{1\}\subseteq\{1,2\}$；不要混用 $\in$ 与 $\subseteq$。
3. 数学中的“或”通常是包含式或，不排除两者同时成立。
4. “若”只表达一个方向；“当且仅当”才表达双向。
5. 否定全称命题只需反例，不能把“多数时候成立”当作全称证明。

常见问答

Q1：训练数据有重复行，为什么还能写成集合？

这是常见的符号简化。真正实现中用数组或序列保留重复项与索引。若重复次数影响概率，就不能在推理时把它当普通集合去重。

Q2：$P(A\cup B)$ 为什么一般不等于 $P(A)+P(B)$？

$A\cap B$ 中的结果被两次计算，应减去一次：$P(A\cup B)=P(A)+P(B)-P(A\cap B)$。只有互斥时交集概率为零。

Q3：模型输出“必要不充分条件”有什么实际影响？

满足必要条件不保证目标成立。例如梯度为零是可微函数取得内部局部最优的必要条件，却不是充分条件；它也可能是最大值或鞍点。

练习

1. 设 $A=\{1,2,3\}$，$B=\{3,4\}$，求 $A\cup B$、$A\cap B$、$A\setminus B$。
2. 写出“并非所有样本都分类正确”的量词形式。
3. 否定命题“存在参数 $\theta$ 使损失为零”。
4. 判断 $P\Rightarrow Q$ 与 $Q\Rightarrow P$ 是否逻辑等价。
5. 标签集合有 4 个元素，它的幂集有多少元素？
6. 设真实正例 40 个，预测正例 30 个，交集 24 个。求假正例与假负例个数。

答案与提示

1. $\{1,2,3,4\}$，$\{3\}$，$\{1,2\}$。
2. $\exists i$，第 $i$ 个样本分类错误。
3. 对所有 $\theta$，损失都不为零。
4. 一般不等价。
5. $2^4=16$。
6. 假正例 $30-24=6$，假负例 $40-24=16$。