集中不等式(1)

发表于

这篇文章里介绍一些在随机模型中非常常见的集中不等式. 是之前在各类paper上看的类似不等式的一个总结, 我们会经常用它们来给概率的界进行估计. 所谓的集中是说某个随机变量\(X\) 在反复多次选取之后能够集中到某一点（例如数学期望）附近. 集中性质的一个典型例子就是大数定律了. （自行复习）. 下面我们来看主要要说的几个不等式.

马尔可夫不等式

严格意义上来说Markov不等式不是集中不等式，它的原表述可以写成 \[\mathbb{P}(|X|\geq a)\leq \frac{\mathbb{E}X}{a}\] 它的证明是简单的: 我们设\(X\)有分布函数\(F(x)\) \[ \begin{align} P(|X|\geq a)&=1-F(x)=\int_a^{\infty}dF(x)+\int_{-\infty}^{-a}dF(x) \\ &\leq \frac{1}{a}\int_{-a}^a|x|dF(x)+\frac{1}{a}\int_a^{\infty}|x|dF(x)+\int_{-\infty}^{-a}|x|dF(x)\\ &=\frac{\mathbb{E}|X|}{a} \end{align} \] 对所有的单调严格递增函数\(\Phi(x)\),Markov不等式可以有如下推广 \[ \mathbb{P}(X\geq a)=\mathbb{P}(\Phi(X)\geq \Phi(a))\leq\frac{\mathbb{E}\Phi(X)}{\Phi(a)} \] 灵活运用markov不等式可以帮助我们得到chebshev不等式. 只需要对随机变量\(Y=(X-\mathbb{E}X)^2\)应用Markov不等式即可得到 \[ \mathbb{P}(|X-\mathbb{E}(X)|\geq a)\leq \frac{\text{Var}(X)}{a^2} \] 而马尔科夫(chebshev)不等式的应用是非常广泛的，一个非常典型的例子是，我们可以用马尔科夫不等式给出大数定律(独立同分布,二阶中心矩存在,依概率收敛版本)的证明 设\(X_1,X_2,\cdots,\)为独立同分布的随机变量列,\(\mathbb{E}X_i=\mu,\text{Var}X_i=\sigma^2\)，那么\(\overline{X}=\frac{1}{n}\sum_{i=1}^nX_i\)会依概率收敛到\(\mu\).为了证明这一点，我们只需要考虑对任意给定的正数\(\varepsilon\)，有 \[ \mathbb{P}\left(|\overline{X_n}-\mu|\varepsilon\right)\leq \frac{\mathbb{E}|\overline{X_n}-\mu|^2}{\varepsilon^2}=\frac{\sigma^2}{n\varepsilon^2}\longrightarrow 0 \] 这就完成了证明. 当然这个证明是非常弱的，从过程中我们也看到了很多可以减弱条件的可能，感兴趣的读者可以自己思考.

Hoeffding不等式

对于有界的随机变量，我们事实上有更强的界来控制样本均值的集中程度. 我们假设\(X_i\)是独立的随机变量列，并且满足\(\mathbb{P}(X_i\in[a_i,b_i])=1\),那么这\(n\)个随机变量的经验期望\(\overline{X}=\frac{1}{n}\sum_{i=1}^nX_i\)满足Hoeffding不等式 \[ \begin{align} \mathbb{P}(\overline{X}-\mathbb{E}(\overline{X})\geq t)\leq \exp\left(-\frac{2t^2n^2}{\sum_{i=1}^n(b_i-a_i)^2}\right) \\ \mathbb{P}(|\overline{X}-\mathbb{E}(\overline{X}|)\geq t)\leq 2\exp\left(-\frac{2t^2n^2}{\sum_{i=1}^n(b_i-a_i)^2}\right) \end{align} \] Hoeffding不等式的证明参见Wassily Hoeffding，Probability inequalities for sum of bounded random variables,1963年JASA上的一篇文章. 而这个界的指数函数事实上可以帮助我们做很多事情. 例如，周志华老师的《机器学习》这本书中就利用Hoeffding不等式简单解释了一下集成学习的原理.例如我们考虑而分类问题，标签为{-1,+1}和真实的函数\(f(x)\),假定基分类器的错误率为\(\epsilon\). 因此对每个基分类器，有 \[ P(h_i(x)\neq f(x))=\epsilon \] 我们假设集成是通过简单投票法结合T个集分类器来分类的，也就是说我们集成分类的结果是 \[ H(x)=\text{sign}\left(\sum_{i=1}^Th_i(x)\right) \] 假设基分类器的错误率相互独立. 集成结果错误是超过半数的基分类器的结果都错,而我们假设了每个基分类器错误概率相同. 我们把每个基分类器的结果是否正确看成是一个Bernoulli分布，其取值在\(\{0,1\}\)两点，故有界，其期望为\(1-\epsilon\). 设\(G(T)\)表示\(T\)个基分类器中投对的个数. 现在我们给定任意的\(\delta>0\),由Hoeffding不等式得到 \[ \mathbb{P}\left(G(T)-T(1-\epsilon)\leq -T\delta \right)\leq \exp\left(-\frac{2\delta^2T^2}{T}\right) \] 于是我们就知道集成结果错误的概率即\(T(1-\epsilon-\delta)\leq [\frac{T}{2}]\)的概率，再代入回原来的指数控制界，整理即可得到两点：

  • 首先注意到\(\delta = 1-\epsilon-[\frac{T}{2}]\frac{1}{T}\)应当大于零. 而为了保证这一点，我们需要\(\epsilon \leq \frac{1}{2}\).
  • 其次就是整体的分类错误概率可以控制用不等式取等号时的最大概率来控制（\(T(1-\epsilon-\delta)=[\frac{T}{2}]\)）此时上界可控制为 \[ \exp\left(-\frac{1}{2}T(1-2\epsilon)^2\right) \]

这就说明多个独立的基分类器的集成能够非常有效地降低分类错误率，这也从最简单地情况说明了集成学习的基本原理. 特别是集成学习的两个要求：基学习器的“好”（\(\epsilon<0.5\)）而不同（独立）.

其它不等式

在这一部分我们仅给出一些经典的基本结果

  • Bernstein不等式 它是对Hoeffding不等式的进一步改进. 假设\(X_i\)是独立的随机变量列\(X_i\in [a,b],\sigma^2=\frac{1}{n}\sum_{i=1}^n\text{Var}(X_i),\varepsilon>0\),则 \[ \mathbb{P}\left(|\frac{1}{n}\sum_{i=1}^nX_i-\mathbb{E}X_i|>\varepsilon\right)\leq 2\exp\left(-\frac{n\varepsilon^2}{2\sigma^2+\frac{2}{3}\varepsilon(b-a)}\right) \]
  • Benett不等式 仍然假设\(\sigma^2=\frac{1}{n}\sum_{i=1}^n\text{Var}(X_i),\varepsilon>0,\mathbb{E}(X_i)=0,|X_i|\leq a,u\geq 0\),则 \[ \mathbb{P}(\sum_{i=1}^nX_i>t)\leq\exp\left(-\frac{n\sigma^2}{a^2}h(\frac{at}{n\sigma^2})\right) \] 其中 \[ h(u)=(1+u)\log(1+u)-u \]
  • Efron-Stein不等式 这个不等式给出了随机变量方差的一个上限估计. 假设\(X_i\)和\(X_i'\)是两列独立的两两独立的随机变量列，并且对于所有的\(i\)，\(X_i\)和\(X_i'\)有着相同的分布. 那么令\(X=(X_1,\cdots,X_n),X^{(i)}=(X_1,\cdots,X_{i-1},X_i',X_{i+1},\cdots,X_n)\)，则有 \[ \text{Var}(f(X))\leq\frac{1}{2}\sum_{i=1}^n\mathbb{E}[(f(X)-f(X^{(i)}))^2] \]

References

  1. Wassily Hoeffding，Probability inequalities for sum of bounded random variables, JASA
  2. 机器学习，周志华，清华大学出版社
  3. http://www.cs.cmu.edu/~aarti/Class/10701_Spring14/slides/TailBounds.pdf
  4. https://zh.wikipedia.org/wiki/集中不等式