前言: 福特的实习总算快结束了, 忙里偷闲写博客. 本文的初衷用简明扼要的语言说一说统计学习理论中的常见的概率不等式, 证明过程略, 只为了方便快速回忆. 主要参考了Shai Shalev-Shwartz的Understanding machine learning一书、这篇博客以及维基百科.
设\(Z_i, i=1,...,m\)是一列独立同分布的随机变量序列, 且在本文讨论的范围统计学习理论中, 这里的\(Z_i\)可以直接理解为每个样本分类的正确与否, 因此有如下几个事实:
- \(Z_i\)有界, 且\(0\le Z_i\le1\)
- \(\frac{1}{m}\sum_{i=1}^{m}Z_i\)即为大小为\(m\)的训练集的分类正确率, 且\(0\le \frac{1}{m}\sum_{i=1}^{m}Z_i\le1\)
- 假定优化过程中训练集的分类错误率不断减小, 因此\(1-\frac{1}{m}\sum_{i=1}^{m}Z_i\)为上鞅的假设视为合理.
上述假设均可直接带入下述不等式去理解.
Moment Based Bound
基于矩的界主要是Markov Inequality和Chebyshev Inequality.
Markov Inequality
设\(Z\)为非负随机变量, \(\forall a >0\) \[\mathbb{P}(Z\ge a)\le\frac{\mathbb{E}(Z)}{a}\]
Chebyshev Inequality
\(\forall a >0\) \[\mathbb{P}(\left|Z-\mathbb{E}(Z)\right|\ge a)\le\frac{Var(Z)}{a^2}\]
Chernoff Bound
Chernoff Bound一般指用指数函数的单调性及Markov Inequality得到的界. 笔者按自己的理解再细分成了两类:
- Chernoff Inequality、Bennett Inequality and Bernstein Inequality
- Hoeffding Inequality 、McDiarmid inequality and Azuma–Hoeffding inequality
Chernoff Inequality
设\(Z_i \sim B(1,p_i), i=1,...,m\)为独立的伯努利随机变量序列, 那么对于\(\forall a >0\) \[ \begin{aligned}\mathbb{P}\left(\frac{1}{m}\sum_{i=1}^{m} Z_i>(1+a)\frac{1}{m}\sum_{i=1}^m p_i\right) & \le \exp\left(- \frac{a^2}{2+2a/3}\sum_{i=1}^m p_i\right)\\\ \mathbb{P}\left(\frac{1}{m}\sum_{i=1}^{m} Z_i<(1-a)\frac{1}{m}\sum_{i=1}^m p_i\right) & \le \exp\left(- \frac{a^2}{2+2a/3}\sum_{i=1}^m p_i\right)\end{aligned} \]
Bennett Inequality
设\(Z_i , i=1,...,m\)为0均值独立随机变量序列, 且几乎处处有\(Z_i\le c\). 那么对于\(\forall a >0\),\(\forall \sigma^2\ge\frac{1}{m}\sum_{i=1}^{m}\mathbb{E}\left[Z_i^2\right]\) \[ \begin{aligned}\mathbb{P}\left(\frac{1}{m}\sum_{i=1}^{m} Z_i>a \right) & \le \exp\left(- \frac{m\sigma^2}{c^2}h\left(\frac{ac}{\sigma^2}\right)\right)\end{aligned} \]其中\(h(x)=(1+x)\log(1+x)-x\)
Bernstein Inequality
设\(Z_i , i=1,...,m\)为0均值独立随机变量序列, 且几乎处处有\(\left\vert Z_i\right\vert\le c\). 那么对于\(\forall a >0\) \[ \begin{aligned}\mathbb{P}\left(\frac{1}{m}\sum_{i=1}^{m} Z_i>a \right) & \le \exp\left(- \frac{m^2 a^2}{2\sum_{j=1}^m\mathbb{E}[Z_j^2]+2acm/3}\right)\end{aligned} \]
Hoeffding Inequality
设\(Z_i , i=1,...,m\)为独立随机变量序列, 且几乎处处有\(l_i\le Z_i\le u_i\). 那么对于\(\forall a >0\) \[ \begin{aligned}\mathbb{P}\left(\frac{1}{m}\sum_{i=1}^{m} Z_i - \mathbb{E}\left[\frac{1}{m}\sum_{i=1}^{m} Z_i \right] \ge a\right) & \le\exp\left(- \frac{2m^2a^2}{\sum_{i=1}^m(u_i-l_i)^2}\right)\\\ \mathbb{P}\left(\frac{1}{m}\sum_{i=1}^{m} Z_i - \mathbb{E}\left[\frac{1}{m}\sum_{i=1}^{m} Z_i \right] \le -a\right) & \le\exp\left(- \frac{2m^2a^2}{\sum_{i=1}^m(u_i-l_i)^2}\right)\end{aligned} \]
McDiarmid inequality
设\(Z_i , i=1,...,m\)为独立随机变量序列, \(f(Z_1,...,Z_m)\)为一映射, 且几乎处处有\[\sup_{z_1,...,z_i,z_i',...,z_m}|f(z_1,...,z_i,...,z_m)-f(z_1,...,z_i',...,z_m)|\le c_i\]成立. 那么对于\(\forall a>0\) \[\begin{aligned}\mathbb{P}\left(f(Z_1,...,Z_m)- \mathbb{E}\left[f(Z_1,...,Z_m) \right] \ge a\right) & \le\exp\left(- \frac{2a^2}{\sum_{i=1}^mc_i^2}\right) \\\ \mathbb{P}\left(f(Z_1,...,Z_m)- \mathbb{E}\left[f(Z_1,...,Z_m) \right] \le -a\right) & \le\exp\left(- \frac{2a^2}{\sum_{i=1}^mc_i^2}\right)\end{aligned}\]
p.s. 该不等式可视为Hoeffding’s Inequality的推广, \(f\)取为均值映射就是Hoeffding’s Inequality.
Azuma–Hoeffding inequality
设\(Z_i , i=0,1,...,m\)为一个鞅(上鞅), 且几乎处处有\(|Z_k-Z_{k-1}|\le c_k\)成立. 那么对于\(\forall a>0\) \[\begin{aligned}\mathbb{P}\left(Z_m-Z_0 \ge a\right) & \le\exp\left(- \frac{a^2}{2\sum_{i=1}^mc_i^2}\right) \\\ \mathbb{P}\left(Z_m-Z_0 \le -a\right) & \le\exp\left(- \frac{a^2}{2\sum_{i=1}^mc_i^2}\right)\end{aligned}\]