数学证明、反例、归纳与渐近记号

层级：B｜按需

1. 机器学习读者为什么需要证明素养

不必成为纯数学家，但必须能区分：定义、假设、结论、直觉、经验观察和严格保证。论文中的“算法收敛”“估计量无偏”“概率至少为 $1-\delta$ ”都有明确条件。证明素养的价值不是自己证明一切，而是知道一个结论究竟保证了什么、没有保证什么。

2. 定义、命题、定理与推论

定义规定术语含义，通常无所谓真假。例如“若 $f(tx+(1-t)y)\le tf(x)+(1-t)f(y)$ ，称 $f$ 为凸函数”。
命题/定理是在给定条件下可以证明真假的陈述。
引理是为证明主要定理准备的辅助结论。
推论是从已有定理较直接得到的结论。
公理/假设是当前体系或模型中接受的出发点。

阅读定理时先做三栏笔记：已知条件、要证结论、关键连接。不要从公式第一行开始逐字符追踪。

3. 直接证明

直接证明从假设出发，通过定义和已知结论推到目标。

例：证明两个偶数之和仍是偶数。

若 $a=2m$ 、 $b=2n$ ，其中 $m,n\in\mathbb Z$ ，则

a+b=2(m+n).

因为 $m+n$ 是整数，所以 $a+b$ 是偶数。

关键在于展开“偶数”的定义，而不是枚举几个例子。

4. 逆否证明与反证法

证明 $P\Rightarrow Q$ 可以改证等价的逆否命题 $\neg Q\Rightarrow\neg P$ 。当结论的否定更容易使用时很有效。

反证法先假设待证结论为假，再推出矛盾。例如证明 $\sqrt2$ 不是有理数，会假设它能写成最简分数并推出分子分母同时为偶数。

使用反证法时要明确矛盾来自哪里，不能只写“显然矛盾”。

5. 反例

一个全称命题“对所有 $x$ ， $P(x)$ 成立”只要找到一个 $P(x)$ 不成立的对象就被推翻。

命题“协方差为零的随机变量一定独立”是错的。取对称随机变量 $X$ ，令 $Y=X^2$ ，在合适分布下可有 $\operatorname{Cov}(X,Y)=0$ ，但 $Y$ 完全由 $X$ 决定，显然不独立。

数值实验能帮助寻找反例，却不能证明无限范围内的全称命题。

6. 数学归纳法

要证明对所有正整数 $n$ 的命题 $P(n)$ ：

基础步：证明 $P(1)$ ；
归纳假设：假设 $P(k)$ 成立；
归纳步：据此证明 $P(k+1)$ 成立。

例如证明

1+2+\cdots+n=\frac{n(n+1)}2.

基础步 $n=1$ 成立。假设前 $k$ 项之和为 $k(k+1)/2$ ，则

1+\cdots+k+(k+1) =\frac{k(k+1)}2+(k+1) =\frac{(k+1)(k+2)}2.

这正是 $n=k+1$ 的形式。

归纳法常用于递归算法、迭代公式和树结构的正确性。

7. 必要条件、充分条件与“当且仅当”

若 $P\Rightarrow Q$ ：

$P$ 是 $Q$ 的充分条件；
$Q$ 是 $P$ 的必要条件。

“可微”是“连续”的充分条件；连续是可微的必要条件，但不是充分条件，因为 $|x|$ 在 0 连续却不可微。

证明 $P\Leftrightarrow Q$ 必须证明两个方向。论文里把单向结论当成双向结论，是常见的理解错误。

8. 近似、等价与正比

$a=b$ ：严格相等；
$a\approx b$ ：在特定精度或条件下近似相等；
$a\propto b$ ： $a=cb$ ，其中比例常数 $c$ 与当前关注变量无关；
$f(x)\sim g(x)$ （当 $x\to a$ ）： $f(x)/g(x)\to1$ 。

贝叶斯公式常写

p(\theta\mid D)\propto p(D\mid\theta)p(\theta),

省略的是不依赖 $\theta$ 的证据 $p(D)$ 。若比较不同 $\theta$ 的相对大小可以省略；要得到归一化概率就必须恢复常数。

9. 渐近记号

渐近记号描述输入规模增大时的增长级别，而不是某个固定规模的精确运行时间。

大 O：渐近上界

f(n)=O(g(n))

表示存在常数 $c>0,n_0$ ，使所有 $n\ge n_0$ 都有 $|f(n)|\le c|g(n)|$ 。

大 Omega：渐近下界

f(n)=\Omega(g(n))

表示最终至少按 $g(n)$ 的量级增长。

大 Theta：同阶

f(n)=\Theta(g(n))

表示同时是 $O(g(n))$ 与 $\Omega(g(n))$ 。

小 o

f(n)=o(g(n))

表示 $f(n)/g(n)\to0$ ，即 $f$ 严格低阶。

例如 $3n^2+5n+7=\Theta(n^2)$ ，也是 $O(n^3)$ ，但说 $\Theta(n^2)$ 更精确。

10. 机器学习中的规模变量

复杂度表达式必须说明变量：

$n$ ：样本数；
$d$ ：特征维度；
$K$ ：类别数；
$T$ ：迭代次数或树的数量；
$m$ ：隐藏单元数。

例如计算稠密矩阵 $\boldsymbol X\boldsymbol w$ ， $\boldsymbol X\in\mathbb R^{n\times d}$ ，时间为 $\Theta(nd)$ 。若只写“线性时间”，必须问是对 $n$ 还是对 $d$ 线性。

空间复杂度同样重要。保存完整 $n\times n$ 核矩阵需要 $\Theta(n^2)$ 内存，可能比训练时间更早成为瓶颈。

11. 概率性结论怎么读

学习理论常写：以至少 $1-\delta$ 的概率，

R(h)\le\hat R(h)+\epsilon(n,\delta,\mathcal H).

这不是说单个样本被正确分类的概率是 $1-\delta$ 。随机性通常来自训练集抽样；结论说在反复抽取训练集的世界里，大多数数据集会使这个界成立。必须识别“概率对什么随机对象而言”。

12. 证明与实验的边界

证明能覆盖满足条件的所有对象，但条件可能理想化；
实验反映特定数据、实现和随机种子，能揭示现实行为但不能自动推广；
理论与实验应相互校验，而不是互相替代。

例如凸优化的收敛定理可能要求学习率、光滑性与精确梯度；实际深度网络不完全满足，但实验仍可能表现良好。正确结论是“该定理不能直接提供保证”，不是“算法必然不收敛”。

易错点

举很多例子不能证明全称命题，一个反例却能推翻它。
大 O 是上界，不自动表示精确同阶。
忽略定理条件，会把局部结论误当全局结论。
$\propto$ 省略的常数必须与当前变量无关。
“以高概率成立”与“期望上成立”是不同保证。

常见问答

Q1：读西瓜书需要自己补完所有证明吗？

不需要。A 级内容应能补关键代数步骤；B/C 级理论先掌握条件、结论和证明主线。对你要实现或继续研究的主题，再深入严谨细节。

Q2：复杂度为什么忽略常数？

渐近分析关心规模增长的主导项，便于跨机器比较。但工程决策不能完全忽略常数、缓存、并行与稀疏结构。

Q3：`O(1)` 是否一定很快？

不一定。它只表示耗时不随所讨论的输入规模增长，常数可能很大，还可能依赖未计入的其他变量。

练习

给出反例推翻“若 $x^2>1$ ，则 $x>1$ ”。
写出命题“可逆矩阵的零空间只有零向量”的逆否形式。
用归纳法证明 $1+3+\cdots+(2n-1)=n^2$ 。
判断： $n^2=O(n^3)$ 是否正确？ $n^2=\Theta(n^3)$ 呢？
稠密数据矩阵为 $n\times d$ ，保存它需要什么空间复杂度？
解释 $p(\theta\mid D)\propto p(D\mid\theta)p(\theta)$ 省略了什么，以及什么时候不能省略。

答案与提示

$x=-2$ 。
若存在非零 $\boldsymbol x$ 使 $A\boldsymbol x=0$ ，则 $A$ 不可逆。
归纳步把下一项 $2(k+1)-1=2k+1$ 加到 $k^2$ ，得 $(k+1)^2$ 。
前者正确，后者错误。
$\Theta(nd)$ 。
省略证据 $p(D)$ ；需要归一化的后验数值或比较不同数据集时不能随意省略。