机器学习数学基础 120 章

Markov、Chebyshev、Hoeffding 等概率界

层级：C｜深入

1. 概率界在没有完整分布时控制坏事件

我们常不知道精确尾概率，只知道非负性、均值、方差或变量有界。集中不等式把有限信息转成“偏离均值超过某阈值的概率上界”，是泛化界、随机算法和样本复杂度的基础。

2. Markov 不等式

若 X≥0X\ge0 且 E[X]<∞E[X]<\infty，对 a>0a>0：

P(X≥a)≤E[X]a.P(X\ge a)\le\frac{E[X]}a.

证明：

X≥a1{X≥a},X\ge a\mathbf1\{X\ge a\},

两边取期望：

E[X]≥aP(X≥a).E[X]\ge aP(X\ge a).

它只用均值，普适但常很松。非负条件不能漏。

3. Chebyshev 不等式

对均值 μ\mu、有限方差 σ2\sigma^2：

P(∣X−μ∣≥t)≤σ2t2.P(|X-\mu|\ge t) \le\frac{\sigma^2}{t^2}.

把 Markov 用到非负变量 (X−μ)2(X-\mu)^2 即得。

标准差形式：

P(∣X−μ∣≥kσ)≤1/k2.P(|X-\mu|\ge k\sigma)\le1/k^2.

任何有限方差分布至少有 1−1/k21-1/k^2 的概率落在 kk 个标准差内，远比高斯 68–95–99.7 弱但不需分布形状。

4. 用 Chebyshev 证明弱大数

iid 方差 σ2\sigma^2：

Var(Xˉ)=σ2/n.Var(\bar X)=\sigma^2/n.

所以

P(∣Xˉ−μ∣≥ϵ)≤σ2nϵ2→0.P(|\bar X-\mu|\ge\epsilon) \le\frac{\sigma^2}{n\epsilon^2}\to0.

它给 O(1/n)O(1/n) 概率上界，但对有界变量可用指数级更强界。

5. Hoeffding 不等式

独立变量 Xi∈[ai,bi]X_i\in[a_i,b_i]，样本和偏离期望：

P(∑i(Xi−E[Xi])≥t)≤exp⁡(−2t2∑i(bi−ai)2).P\left(\sum_i(X_i-E[X_i])\ge t\right) \le\exp\left( -\frac{2t^2}{\sum_i(b_i-a_i)^2} \right).

若 iid Xi∈[a,b]X_i\in[a,b]：

P(∣Xˉ−EXˉ∣≥ϵ)≤2exp⁡(−2nϵ2(b−a)2).P(|\bar X-E\bar X|\ge\epsilon) \le2\exp\left(-\frac{2n\epsilon^2}{(b-a)^2}\right).

尾概率随 nϵ2n\epsilon^2 指数下降。

6. Bernoulli 风险界

固定分类器的 0-1 损失 Xi∈[0,1]X_i\in[0,1]：

P(∣R^−R∣≥ϵ)≤2e−2nϵ2.P(|\hat R-R|\ge\epsilon) \le2e^{-2n\epsilon^2}.

要使失败概率不超过 δ\delta，解得

n≥12ϵ2log⁡2δ.n\ge\frac1{2\epsilon^2} \log\frac2\delta.

这只对预先固定分类器。若从许多模型中选择，需要 union bound 或复杂度控制。

7. Union bound

无论事件是否独立：

P(⋃i=1MAi)≤∑i=1MP(Ai).P\left(\bigcup_{i=1}^{M}A_i\right) \le\sum_{i=1}^{M}P(A_i).

对有限假设集 ∣H∣=M|\mathcal H|=M，若每个模型坏事件概率至多 δ/M\delta/M，则任一模型出现坏事件概率至多 δ\delta。结合 Hoeffding 得复杂度项 log⁡M\log M。

Union bound 简单但事件高度重叠时会很松。

8. Chernoff 方法

对任意 s>0s>0：

P(X≥t)=P(esX≥est)≤e−stE[esX].P(X\ge t)=P(e^{sX}\ge e^{st}) \le e^{-st}E[e^{sX}].

再对 ss 优化。这是把 Markov 用到指数变量，利用矩生成函数得到指数尾界。Bernoulli 和的 Chernoff bounds 常比 Hoeffding 更依赖均值、在稀有事件时更紧。

9. Bernstein 不等式

在独立、有界并知道方差时，Bernstein 界大致形如

P(∣Xˉ−EX∣≥ϵ)≤2exp⁡(−nϵ22σ2+Cϵ).P(|\bar X-E X|\ge\epsilon) \le2\exp\left( -\frac{n\epsilon^2}{2\sigma^2+C\epsilon} \right).

小偏差区域利用实际方差，可能比只看范围的 Hoeffding 紧；大偏差仍受有界范围控制。具体常数随版本不同，使用时需引用准确条件。

10. Sub-Gaussian 随机变量

中心随机变量 XX 若

E[etX]≤eσ2t2/2E[e^{tX}]\le e^{\sigma^2t^2/2}

对所有 tt 成立，称 σ\sigma-sub-Gaussian。它具有高斯型尾：

P(∣X∣≥u)≤2e−u2/(2σ2).P(|X|\ge u)\le2e^{-u^2/(2\sigma^2)}.

有界中心变量、Gaussian 都是典型例子。sub-exponential 允许更重的指数尾。

11. 高概率记号

“以至少 1−δ1-\delta 的概率”：

∣hatR−R∣lelog⁡(2/δ)2n.|hat R-R|le \sqrt{\frac{\log(2/\delta)}{2n}}.

概率通常对训练样本随机抽取而言。δ\delta 是失败概率，不是分类错误率。界同时对所有模型成立还是只对固定模型，必须明确。

12. 界的价值与局限

理论界可能数值很松，但仍揭示：

  • 误差随 1/n1/\sqrt n 缩小；
  • 置信度仅对数依赖 1/δ1/\delta；
  • 模型数量/复杂度增加会付出代价；
  • 更强分布条件带来更紧界。

不能用一个最坏情形上界精确预测实践测试误差。

易错点

  1. Markov 要求随机变量非负。
  2. Chebyshev 要求有限方差。
  3. Hoeffding 要求独立与有界（对应版本）。
  4. 固定模型界不能直接用于数据选择后的模型。
  5. 1−δ1-\delta 是界成立概率，不是模型准确率。

常见问答

Q1：为什么 Hoeffding 不使用方差？

它只依变量范围，分布自由但可能松；Bernstein/empirical Bernstein 利用方差获得自适应界。

Q2：多重检验 Bonferroni 与 union bound 有何关系？

Bonferroni 通过把每项显著性设为 α/M\alpha/M，用 union bound 控制任一假阳性的家族错误率。

Q3：深度网络的经典界为何常很松？

参数/假设空间巨大，最坏情况复杂度高，而实际优化、数据结构、隐式正则与 margin 远比粗界利用的信息丰富。

练习

  1. X≥0,E[X]=2X\ge0,E[X]=2，界定 P(X≥10)P(X\ge10)。
  2. 均值 0、方差 4，界定 P(∣X∣≥6)P(|X|\ge6)。
  3. nn 个 [0,1][0,1] 独立变量，写 Hoeffding 双尾界。
  4. 100 个事件各概率至多 0.001，并集概率上界？
  5. 解释固定分类器与训练选择分类器为何需要不同界。

答案与提示

  1. 至多 0.2。
  2. 至多 4/36=1/94/36=1/9。
  3. 2e−2nϵ22e^{-2n\epsilon^2}。
  4. 0.1。
  5. 选择过程会偏向经验误差偶然偏低者，需要同时控制整个候选类。