0%

统计学习中的几个概率不等式

前言: 福特的实习总算快结束了, 忙里偷闲写博客. 本文的初衷用简明扼要的语言说一说统计学习理论中的常见的概率不等式, 证明过程略, 只为了方便快速回忆. 主要参考了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 InequalityChebyshev 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 InequalityBennett Inequality and Bernstein Inequality - Hoeffding InequalityMcDiarmid 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)\)为一映射(比方说取为均值函数, 就是Hoeffding’s Inequality), 且几乎处处有\(\sup_{z_1,...,z_i,z_i',...,z_m}|f(z_1,...,z_i,...,z_m)-f(x_1,...,x_i',...,x_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}\]

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}\]