核心思想：大数定律与集中不等式

所有这些不等式的核心思想都与大数定律 (Law of Large Numbers) 有关。大数定律告诉我们，当我们对一个随机变量进行大量独立重复的抽样时，这些样本的平均值会收敛到该随机变量的期望值。

而集中不等式 (Concentration Inequalities)，如马尔可夫、切比雪夫、霍夫丁不等式，则更进一步：它们不仅告诉我们样本均值会收敛，还量化了样本均值偏离其期望值的概率。它们给出了一个上界，说明“样本均值与真实期望值相差甚远”这种“坏事”发生的概率有多小。

推导阶梯

第一步：马尔可夫不等式 (Markov's Inequality)

这是最基础的集中不等式，适用于任何非负的随机变量 X。

定理: 如果 X 是一个非负随机变量，那么对于任何 a > 0，有：

• 直观理解：一个非负随机变量的值远大于其平均值的概率是有限的。如果一个班级的平均身高是1.7米，那么身高超过3.4米（平均值的两倍）的人数比例，不可能超过总人数的1/2。

• 推导：
  $E[X]={\int }_0^{\mathrm{\infty }}x\cdot p(x)dx$ (期望的定义)
  $E[X]={\int }_0^{a}x\cdot p(x)dx+{\int }_a^{\mathrm{\infty }}x\cdot p(x)dx$ (拆分积分)
  $E[X]\ge {\int }_a^{\mathrm{\infty }}x\cdot p(x)dx$ (因为第一项非负)
  $E[X]\ge {\int }_a^{\mathrm{\infty }}a\cdot p(x)dx=a{\int }_a^{\mathrm{\infty }}p(x)dx$ (因为在积分区间内 $x\ge a$)
  $E[X]\ge a\cdot P(X\ge a)$ (积分项就是概率的定义)
  整理后即得 $P(X\ge a)\le \frac{E[X]}{a}$。

• 局限：这个界限非常宽松，通常不够精确。

第二步：切比雪夫不等式 (Chebyshev's Inequality)

切比雪夫不等式利用了方差的信息，提供了一个更紧的界。它适用于任何有期望 $\mu$ 和方差 ${\sigma }^2$ 的随机变量 X。

定理: 对于任何 k > 0，有：

• 推导: 巧妙地应用马尔可夫不等式。
  令一个新的随机变量 $Y=(X-\mu {)}^2$。显然 $Y\ge 0$。
  应用马尔可夫不等式于 $Y$: $P(Y\ge a)\le \frac{E[Y]}{a}$。
  我们知道 $E[Y]=E[(X-\mu {)}^2]={\sigma }^2$ (方差的定义)。
  所以 $P((X-\mu {)}^2\ge a)\le \frac{{\sigma }^2}{a}$。
  令 $a=k^2$，则 $P((X-\mu {)}^2\ge k^2)\le \frac{{\sigma }^2}{k^2}$。
  因为 $(X-\mu {)}^2\ge k^2$ 等价于 $|X-\mu |\ge k$，所以我们得到切比雪夫不等式。

• 局限: 界限仍然不够紧，它随 $1/k^2$ 衰减，而不是指数衰减。

第三步：霍夫丁引理 (Hoeffding's Lemma) & 指数矩方法

为了得到指数衰减的界，我们需要一个更强大的工具。这里的关键技巧叫做指数矩方法 (Exponential Moment Method)，也叫 Chernoff Bound 方法。

1. 应用马尔可夫不等式于指数函数:
   对于任何 $s>0$，我们有：
   $P(X\ge a)=P(e^{sX}\ge e^{sa})$
   因为 $e^{sX}$ 是非负随机变量，应用马尔可夫不等式：
   $P(e^{sX}\ge e^{sa})\le \frac{E[e^{sX}]}{e^{sa}}$
   所以 $P(X\ge a)\le e^{-sa}E[e^{sX}]$。
   这个 $E[e^{sX}]$ 叫做矩生成函数。

2. 霍夫丁引理 (Hoeffding's Lemma):
   这是推导霍夫丁不等式的基石。它为有界随机变量的矩生成函数提供了一个上界。
   引理: 如果 X 是一个期望为 0 的随机变量，且其取值范围在 [a, b] 区间内，那么对于任何 $s>0$，有：

   $$E[e^{sX}]\le \exp \left(\frac{s^2(b-a{)}^2}{8}\right)$$

   这个引理的证明比较复杂，涉及到利用 X 的凸性和泰勒展开。

第四步：霍夫丁不等式 (Hoeffding's Inequality)

现在我们有了所有工具。让我们来证明机器学习中的霍夫丁不等式。

目标: 证明 $P(|L(h,{\mathcal{D}}_{train})-L(h,{\mathcal{D}}_{all})|>ϵ)\le 2\exp (-2{ϵ}^{2}N)$

1. 定义随机变量:

   • $L(h,{\mathcal{D}}_{all})$ 是期望损失（真实损失），记为 $\mu$。
   • $L(h,{\mathcal{D}}_{train})=\frac{1}{N}\sum _{n=1}^{N}l(h,x^n,{\hat{y}}^n)$ 是样本平均损失。
   • 令 $Z_n=l(h,x^n,{\hat{y}}^n)$ 为单个样本的损失。这是一个随机变量，其期望 $E[Z_n]=\mu$。
   • 我们想求的是 $P(|\frac{1}{N}\sum Z_n-\mu |>ϵ)$。

2. 只考虑单边情况: 先证明 $P(\frac{1}{N}\sum Z_n-\mu >ϵ)\le \exp (-2{ϵ}^{2}N)$。

   • 令 $S_N=\sum _{n=1}^N(Z_n-\mu )$。这是一个零均值的随机变量之和。
   • $P(\frac{1}{N}\sum Z_n-\mu >ϵ)=P(S_N>Nϵ)$。

3. 应用指数矩方法:
   对于任何 $s>0$：
   $P(S_N>Nϵ)\le e^{-sNϵ}E[e^{s{S}_N}]$
   $E[e^{s{S}_N}]=E[e^{s\sum (Z_n-\mu )}]=E[\prod e^{s(Z_n-\mu )}]$
   因为每个样本是独立同分布抽取的，所以期望的乘积等于乘积的期望：
   $E[e^{s{S}_N}]=\prod E[e^{s(Z_n-\mu )}]$

4. 应用霍夫丁引理:

   • 假设单个损失 $l(\cdot )$ 的取值范围是有界的，比如在 [0, 1] 之间（这在分类问题中通常成立，0/1损失或交叉熵损失的输出在一定范围内）。那么 $Z_n-\mu$ 的范围是 [-μ, 1-μ]，长度为 1。
   • 对 $E[e^{s(Z_n-\mu )}]$ 应用霍夫丁引理（其中 $b-a=1$）：
     $E[e^{s(Z_n-\mu )}]\le \exp (\frac{s^2\cdot 1^2}{8})=\exp (\frac{s^2}{8})$
   • 代回到上一步：
     $E[e^{s{S}_N}]\le \prod _{n=1}^N\exp (\frac{s^2}{8})=(\exp (\frac{s^2}{8}){)}^N=\exp (\frac{N{s}^2}{8})$

5. 找到最优上界:
   我们得到 $P(S_N>Nϵ)\le e^{-sNϵ}\exp (\frac{N{s}^2}{8})=\exp (\frac{N{s}^2}{8}-sNϵ)$。
   这个不等式对所有 $s>0$ 都成立。为了得到最紧的界，我们要找到一个 $s$ 来最小化右边的指数部分。对 $\frac{N{s}^2}{8}-sNϵ$ 关于 $s$求导并令其为0，可解得 $s=4ϵ$。
   将 $s=4ϵ$ 代回：
   $P(S_N>Nϵ)\le \exp (\frac{N(4ϵ{)}^2}{8}-(4ϵ)Nϵ)=\exp (2N{ϵ}^2-4N{ϵ}^2)=\exp (-2N{ϵ}^2)$。
   至此，我们证明了单边不等式。

6. 合并双边情况:
   $P(|L_{train}-L_{all}|>ϵ)=P(L_{train}-L_{all}>ϵ)+P(L_{train}-L_{all}<-ϵ)$
   对于 $P(L_{train}-L_{all}<-ϵ)$，可以用完全对称的方法证明其上界也是 $\exp (-2N{ϵ}^2)$。
   因此，总概率的上界是两者相加，即 $2\exp (-2N{ϵ}^2)$。

总结:
霍夫丁不等式的推导依赖于一系列越来越强大的概率工具，其核心是指数矩方法和霍夫丁引理，它将单个有界随机变量的性质推广到了它们的平均值上，并给出了一个随样本数量 N 指数衰减的概率上界。这个强大的结论是许多机器学习泛化理论的基石。