The Chernoff Bound

本文主要介绍一下chernoff bound的证明，以及一些在统计学习理论中的涉及到的一些不等式,首先来几个简单的。

Jensen 不等X为随机变量， $f:X\rightarrow\mathbb{R}$ 为凸函数,则下面的不等式成立

$\begin{equation}f(\mathbb{E}[X])\leq \mathbb{E}[f(x)] \end{equation}$

这个就是凸函数的性质，这里并不给出证明了，想知道为什么的看一下《凸优化》的前几章就行了。

接下来是Markov不等式，这里终于牵涉到概率了。假设X为非负的随机变量，且 $t>0$ ，则下式成立。

$\begin{equation}P(X>t)\leq\frac{\mathbb{E}[X]}{t} \end{equation}$

这里的证明也很简单

$\begin{equation}\begin{array}{rl} \mathbb{E}[X]&=\int_{0}^{+\infty}xp(x)dx=\int_{0}^{t}xp(x)dx+\int_{t}^{+\infty}xp(x)dx\\ &\geq \int_{t}^{+\infty}xp(x)dx \geq t\int_{t}^{+\infty}p(x)dx=tP(X>t) \end{array} \end{equation}$

现在重点来了，我们隆重介绍一下chernoff bound。首先来看一下最简单形式的chernoff bound。

假设 $X$ 为随机变量，则下面的不等式成立

$\begin{equation}P(X>\epsilon)\leq\underset{t\geq 0}{\inf}\exp(-t\epsilon)\mathbb{E}[\exp(tX)] \end{equation}$

这个不等式的证明也比较简单，直接利用之前的markov不等式即可。

$\begin{equation}\begin{array}{rl}P(X>\epsilon)&=P\left(\exp(X)>\exp(\epsilon)\right)\\ &=\underbrace{P\left(\exp(tX)>\exp(t\epsilon)\right)\leq\exp(-t\epsilon)\mathbb{E}[\exp(tX)]}_{Markov's \; inequality}\end{array} \end{equation}$

粗略一看，这个式子好像没有什么用。的确，在任何情况下都成立基本没啥用，我们需要在不同的情况下推广他的扩展形式

在期望已知的情况下Chernoff Bound的变体¶

假设随机变量 $X\in[a,b]$ , $\mathbb{E}[X]=0$ ，则下面的不等式成立。

$\begin{equation}\mathbb{E}[\exp(tX)]\leq\exp\left(\frac{t^2(b-a)^2}{8}\right) \end{equation}$

这个不等式，粗看起来与之前提到的Chernoff Bound有点相似，但是只是在左边相似而已。事实上不等式左边的基本毫无意义，怎么得到右边的公式才是最重要的。在得到右边的过程中，我们需要利用 $f(x)=\exp(tx)$ 为凸函数的性质。

证明如下：在 $a\neq 0 ,b\neq 0$ 时，我们可以把 $X$ 表示为 $a,b$ 的线性组合

$\begin{equation}X=\alpha b+(1-\alpha)a\end{equation}$

其中 $\alpha=(X-a)/(b-a)\in[0,1]$ 。接下来我们利用凸函数的性质，即Jensen不等式

$\begin{equation}f(X)=f(\alpha x+(1-\alpha)b)\leq\alpha f(x)+(1-\alpha)f(b) \end{equation}$

将 $X=\alpha b+(1-\alpha)a$ 带入到上面的不等式中，我们得到

$\begin{equation}\exp(tX)\leq\frac{X-a}{b-a}\exp(tb)+\frac{b-X}{b-a}\exp(ta)\end{equation}$

对该不等式求期望，并考虑到我们之前的大前提 $\mathbb{E}[X]=0$ ，我们得到下面的不等式

$\begin{equation}\mathbb{E}[\exp(tX)]\leq-\frac{a}{b-a}\exp(tb)+\frac{b}{b-a}\exp(ta)=\exp(g(u)) \end{equation}$

其中 $u=t(b-a),g(u)=-\theta u+\log (1-\theta+\theta \exp(u)),\theta=-a/(b-a)\in(0,1)$ 。看上去我们把东西弄得越来越复杂，接下来是见证奇迹的时刻。根据Taylor展开公式，存在 $v\in (0,u)$ 使得下面的等式成立：

$\begin{equation}g(u)=g(0)+ug'(0)+\frac{u^2}{2}g''(v) \end{equation}$

下面来对 $g(u)$ 求一阶导数和二阶导数

$\begin{equation}g'(0)=-\theta+\frac{\theta\exp(u)}{1-\theta+\theta\exp(u)}\vert_{u=0}=0\end{equation}$

$\begin{equation}\end{equation}$ 二阶导数的放缩利用了 $ab\leq (a+b)^2/4$ 这个最简单的不等式。接下来我们将上面得到的结果都带入原来的taylor展开式中

$\begin{equation}g(u)=\frac{u^2}{2}g''(v)\leq\frac{u^2}{8}=\frac{t^2(b-a)^2}{8} \end{equation}$

由此，经历了千辛万苦，我们终于证明了

$\begin{equation}\mathbb{E}[\exp(tX)]\leq\exp\left(\frac{t^2(b-a)^2}{8}\right) \end{equation}$

在bernoulli分布中的Chernoff Bound¶

之前得到的Chernoff界是绝对差形式，这里的Chernoff界则是相对差形式。假设 $X_1,X_2,\cdots,X_n$ 为符合bernoulli分布的各自独立的随机变量， $X=\sum {X_i}$ ，且 $\mu \geq E[X]$ 。则对于任意的 $\delta >0$ ，下面的不等式都成立

$\begin{equation}Pr[X>(1+\delta)\mu]<\left[ \frac{e^{\delta}}{{(1+\delta)}^{(1+\delta)}}\right]^{\mu}\end{equation}$

这个不等式跟之前的不等式相比，简直丑爆了，而且右边更加复杂。但是证明的第一步还是相同的，还是markov不等式。

$\begin{equation}Pr[X>(1+\delta)\mu]=Pr\left[e^{tX}>e^{t(1+\delta)\mu}\right]\leq e^{-t(1+\delta)\mu}\mathbb{E}[e^{tX}]\end{equation}$

又由于 $X=\sum {X_i}$ ，所以

$\begin{equation}\mathbb{E}[e^{tX}]=\mathbb{E}\left[e^{t\sum {X_i}}\right]=\mathbb{E}\left[\prod{e^{tX_i}}\right]\end{equation}$

这里利用了 $\mathbb{E}[YZ]=\mathbb{E}[Y]*\mathbb{E}[Z]$ 这个独立变量的积的期望公式。又由于 $X_i$ 是符合伯努利分布的随机变量，假设其参数为 $Pr[X_i=1]=p_i$ ，则我们有

$\begin{equation}\mathbb{E}\left[e^{tX_i}\right]=p_ie^t+(1-p_i)=1+p_i(e^t-1)\leq e^{p_i(e^t-1)}\end{equation}$

这里的放缩又利用了 $1+\alpha \leq e^{\alpha}$ 。最终，我们将每一个分量都带入，得到

$\begin{equation}\begin{split}Pr[X>(1+\delta)\mu]&\leq e^{-t(1+\delta)\mu}\mathbb{E}[e^{tX}]=e^{-t(1+\delta)\mu}\prod {\mathbb{E}\left[e^{tX_i}\right]}\\&\leq e^{-t(1+\delta)\mu}\prod {e^{p_i(e^t-1)}}\leq e^{-t(1+\delta)\mu}e^{\mu(e^t-1))}\end{split}\end{equation}$

最后，我们令 $t=ln(1+\delta)$ ，化简得到

$\begin{equation}Pr[X>(1+\delta)\mu]\leq \left[ \frac{e^{\delta}}{{(1+\delta)}^{(1+\delta)}}\right]^{\mu}\end{equation}$

这个式子提供了一个上界。对称的来说，对于下界我们也有一个不等式。假设 $X_1,X_2,\cdots,X_n$ 为符合bernoulli分布的各自独立的随机变量， $X=\sum {X_i}$ ，且 $\mu \le \mathbb{E}[X]$ 。则对于任意的 $1>\delta >0$ ，下面的不等式都成立

$\begin{equation}Pr[X<(1-\delta)\mu]< \left[ \frac{e^{-\delta}}{{(1-\delta)}^{(1-\delta)}}\right]^{\mu}\end{equation}$

这个公式的证明类似于之前公式的证明，这里我们要借助一个 $t<0$ 。

$\begin{equation}\begin{split}Pr[X<(1-\delta)\mu]&=Pr[tX>t(1-\delta)\mu]\leq e^{(-t(1-\delta)\mu)}\mathbb{E}(e^{tX})\\&=e^ {(-t(1-\delta)\mu)}\prod {\mathbb{E}(e^{tX_i})}\end{split}\end{equation}$

这里我们再次遇到 $\mathbb{E}(tX)$ ，再次利用Bernoulli分布性质，假设 $X_i=1$ 的概率为 $p_i$ ，则有

$\begin{equation}\mathbb{E}(e^{tX_i})=p_ie^t+(1-p_i)\leq e^{p_i(e^t-1)}\end{equation}$

将这个不等式带入，得到

$\begin{equation}\begin{split}Pr[X<(1-\delta)\mu]&\leq e^{(-t(1-\delta)\mu)}\prod {\mathbb{E}(e^{tX_i})}\\&\leq e^ {(-t(1-\delta)\mu)}e^{\mathbb{E}(X)(e^t-1)}\\&\leq e^{(-t(1-\delta)\mu)}e^{\mu(e^t-1)}\end{split}\end{equation}$

在这里，我们让 $t=ln(1-\delta)$ ，代入得

$\begin{equation}Pr[X<(1-\delta)\mu]\le \left[ \frac{e^{-\delta}}{{(1-\delta)}^{(1-\delta)}}\right]^{\mu}\end{equation}$

这样，下界我们也证明了。上下界一起大概就是中心极限定理的内容了。实际上，这两个界并不怎么好用，光写起来就十分麻烦，我们要对这两个界进一步放缩。那么问题来了，放缩方法哪家强，当然是Taylor展开了。我们可以观察到

$\begin{equation}ln(1+\delta)=\sum (-1)^{i+1}\frac{{\delta}^i}{i}\end{equation}$

所以,当 $\delta<1$ 时

$\begin{equation}(1+\delta)ln(1+\delta)=\delta +\sum_{i\geq 2}{{(-\delta)}^i\{\frac{1}{i-1}-\frac{1}{i}\}}\geq \delta +{\delta}^2/2-{\delta}^3/6\geq \delta+{\delta}^2/3\end{equation}$

综上我们有

$\begin{equation}Pr[X>(1+\delta)\mu]\leq e^{\frac{-{\delta}^2\mu}{3}} \quad (0<\delta<1)\end{equation}$

对称的，我们也有

$\begin{equation}Pr[X<(1-\delta)\mu]\leq e^{\frac{-{\delta}^2\mu}{2}}\quad (0<\delta<1)\end{equation}$

Hoeffding不等式¶

假设 $X_1,\cdots ,X_n$ 是 $n$ 个相互独立的随机变量，且 $X_i\in[a_i,b_i]$ ，令 $X=\sum {X_i}/n$ ，则对任意的 $\epsilon >0$ 有

$\begin{equation}P\left(|X-\mathbb{E}[{X}]|>\epsilon\right)\leq 2\exp\left(\frac{2n^2\epsilon^2}{\sum_{i=1}^n(b_i-a_i)^2}\right) \end{equation}$

看到这个公式，是不是感觉自己选择了Hard模式啊。根据对称性，Chernoff界以及随机变量的独立性质，我们可以得到

$\begin{equation}\begin{array}{rl} &P\left(|{X}-\mathbb{E}[{X}]|>\epsilon\right)\\ =&2P\left({X}-\mathbb{E}[{X}]>\epsilon\right)\\ \leq& 2\underset{t\geq 0}{\inf}\exp(-t\epsilon)\mathbb{E}[\exp(t{X})]\\ =& 2\underset{t\geq 0}{\inf}\exp(-t\epsilon)\mathbb{E}[\exp(t\sum_{i=1}^nX_i/n)]\\ =& 2\underset{t\geq 0}{\inf}\exp(-t\epsilon)\mathbb{E}[\prod_{i=1}^n\exp(tX_i/n)]\\ =& 2\underset{t\geq 0}{\inf}\exp(-t\epsilon)\prod_{i=1}^n\mathbb{E}[\exp(tX_i/n)]\\ \leq & 2\underset{t\geq 0}{\inf}\exp(-t\epsilon)\prod_{i=1}^n\exp(t^2(b_i-a_i)^2/(8n^2))\\ =& 2\underset{t\geq 0}{\inf}\exp(-t\epsilon+\sum_{i=1}^nt^2(b_i-a_i)^2/(8n^2)) \end{array} \end{equation}$

为了进一步化简结果，我们需要对右边的求极值。右边指数项里面是一个一元二次函数，求极值很简单，求一阶导数就可以了。我们定义函数 $p:\mathbb{R}\rightarrow\mathbb{R}$ 为

$\begin{equation}p(t)=-t\epsilon+\sum_{i=1}^n\frac{t^2(b_i-a_i)^2}{8n^2} \end{equation}$

对其求一阶导数

$\begin{equation}p'(t)=-\epsilon+\frac{t\sum_{i=1}^n(b_i-a_i)^2}{4n^2}=0 \end{equation}$

可得到

$\begin{equation}t=\frac{4n^2\epsilon}{\sum_{i=1}^n(b_i-a_i)^2} \end{equation}$

最后将这个 $t$ 带入到 $p(t)$ 即可得到Hoeffding不等式

$\begin{equation}P\left(|\bar{X}-\mathbb{E}[\bar{X}]|>\epsilon\right)\leq 2\exp\left(-\frac{2n^2\epsilon^2}{\sum_{i=1}^n(b_i-a_i)^2}\right)\end{equation}$

联合界Union Bound¶

联合界理解起来很简单，对于有限个事件 $A_1,A_2,\cdots,A_n$ ，有

$\begin{equation}P\left(\bigcup_{i=1}^nA_i\right)\leq\sum_{i=1}^nP(A_i) \end{equation}$

这个不等式是通过数学归纳法来证明的，对于 $n=2$ 的时候就是

$\begin{equation}P(A\cup B)=P(A)+P(B)-P(A\cap B)\end{equation}$

进行归纳

$\begin{equation}\begin{array}{rl} P\left(\bigcup_{i=1}^{k+1}A_i\right)&=P\left(\bigcup_{i=1}^{k}A_i\right)+P(A_{k+1})-P\left(\bigcup_{i=1}^{k}A_i\cap A_{k+1}\right)\\ &\leq\sum_{i=1}^kP(A_i)+P(A_{k+1})=\sum_{i=1}^{k+1}P(A_i) \end{array} \end{equation}$

因此，这个联合界成立。

经验风险最小化¶

机器学习求解的假设函数不是单纯为了拟合已有的数据，其最终目标是准确预测未知数据的输出。经验风险最小化存在过拟合的风险，其目的在于找到一个可以很好与训练数据匹配的假设函数，而该假设函数不一定能预测未知数据的输出，即泛化误差很大。增加训练数据的规模有利于降低泛化误差。但也不是训练数据越多越好，因为当训练数据达到一定规模后，泛化误差的变化趋于平缓。而且很多时候我们并不能拿到这么多的数据，还有可能我们的资源无法对这么多的数据进行处理。在固定了数据量的情况下，我们只能从模型复杂度下手来减少泛化误差，模型复杂度太大或者太小都会导致泛化误差过大。选择模型，就是我们预先提供的一些分布函数的集合 $\mathcal{H}$ ，这个集合包括模型 $\mathcal{H}=\{h_1,h_2,\cdots,h_{|\mathcal{H}|}$ 。根据经验风险最小化原则，我们选择模型的准则就是训练误差最小

$\begin{equation}\hat{h}=arg\underset{h_i\in\mathcal{H}}{\min}\hat{R}(h_i) \end{equation}$

我们需要证明我们的选择是有道理的，即使训练误差较小的假设函数 $\hat{h}$ ，他的泛化误差也不至于太大。

首先，对任意假设函数 $h$ 而言， $\hat{R}(h)$ 都是 $R(h)$ 的一个可靠的近似值；其次，给出 $\hat{h}$ 的泛化误差 $R(\hat{h})$ 的上界。我们在样本空间内格局样本的概率分布 $\mathcal{D}$ 进行采样，得到训练集 $\mathcal{S}=\{(x^{(i)},y^{(i)})\}_{i=1}^m$ 。给定任意假设函数 $h_i\in \mathcal{H}$ ，定义服从Bernoulli分布的随机变量 $Z_j=I\{h_i(x^{(j)})\neq y^{(j)}\}\in\{0,1\}$ ，则 $Z_j$ 表示 $h_i$ 是否将样本 $(x^{(j)},y^{(j)})$ 误分类了， $h_i$ 的泛化误差 $R(h_i)=P(z_j=1)$ 。因为所有样本都是从同一个概率分布中独立采样的，所以 $\{Z_j\}_{j=1}^m$ 中的都是满足独立同分布的Bernoulli随机变量。 $h_i$ 的训练误差形式为

$\begin{equation}\hat{R}(h_i)=\frac{1}{m}\sum_{j=1}^mI\{h_i(x^{(j)})\neq y^{(j)}\}=\frac{1}{m}\sum_{j=1}^mz_j \end{equation}$

显然 $\hat{R}(h_i)$ 为 $m$ 个独立同分布的Bernoulli随机变量的均值，且这些随机变量的期望值都是 $R(h_i)$ 。根据Hoeffding不等式，得到如下不等式

$\begin{equation} P\left(|R(h_i)-\hat{R}(h_i)|>\gamma\right)\leq 2\exp(-2\gamma^2m) \end{equation}$

上述规律说明：对于特定假设函数 $h_i$ 而言，在样本数目 $m$ 足够大时，训练误差和泛化误差近似相等的概率可以非常大，这也证明了 $\hat{R}(h)$ 是 $R(h)$ 的一个可靠的近似值。但我们想要保证的不仅仅是这种近似的可靠性只对特定的假设函数成立，而是对假设集合 $\mathcal{H}$ 所有的假设函数都成立。现将时间 $A_i$ 定义为 $|R(h_i)-\hat{R}(h_i)|>\gamma$ ，则由上一个结论可得 $P(A_i)\leq 2\exp(-2\gamma^2m)$ 。由于

$\begin{equation}\begin{array}{rl} &P\left(\exists h\in\mathcal{H}.|R(h_i)-\hat{R}(h_i)|>\gamma\right)\\ =&P(\bigcup_{i=1}^{|\mathcal{H}|}A_i)\\ \leq & \sum_{i=1}^{|\mathcal{H}|}P(A_i)\\ \leq & 2\sum_{i=1}^{|\mathcal{H}|}\exp(-2\gamma^2m)\\ =& 2|\mathcal{H}|\exp(-2\gamma^2m) \end{array} \end{equation}$

因此

$\begin{equation}\begin{array}{rl} &P\left(\neg\exists h\in\mathcal{H}.|R(h_i)-\hat{R}(h_i)|>\gamma\right)\\ =&P\left(\forall h\in\mathcal{H}.|R(h_i)-\hat{R}(h_i)|\leq\gamma\right)\\ \geq & 1-2|\mathcal{H}|\exp(-2\gamma^2m) \end{array}\end{equation}$

上式被称为一致性收敛(uniform convergence)，因为这个界对于 $\mathcal{H}$ 都成立。由此可知， $\mathcal{H}$ 中所有假设函数的训练误差与泛化误差偏离范围在 $\gamma$ 内的概率至少为

$\begin{equation}1-2|\mathcal{H}|\exp(-2\gamma^2m)\end{equation}$

在给定其中两个值得情况下，我们可以推出第三个变量需要满足的条件。例如为了确保所有假设函数的训练误差和泛化误差间的偏差范围都在γ $\gamma$ 以内的概率至少为 $1-\delta$ ，至少需要多少个训练样本？这个问题对应的数学表述为：

$\begin{equation}P\left(\forall h\in\mathcal{H}.|R(h_j)-\hat{R}(h_j)|\leq\gamma\right)\geq 1-2|\mathcal{H}|\exp(-2\gamma^2m)\geq 1-\delta \end{equation}$

由此我们可以得到训练样本数目的下界为

$\begin{equation}m\geq\frac{1}{2\gamma^2}\log\frac{2|\mathcal{H}|}{\delta}=O\left(\frac{1}{\gamma^2}\log\frac{|\mathcal{H}|}{\delta}\right) \end{equation}$

这条规律对我们是非常有用的，由此我们可以推测算法性能要达到某种水平，至少需要多少个样本就足够了，这也称为算法的样本复杂度(sample complexity)。一般而言， $\log|\mathcal{H}|$ 增长很慢，据CMU的Andrew Moore所说， $\log|\mathcal{H}|\leq 30$ 。样本数目太少不能保证训练出来的模型有较优的性能，样本数目也没必要太多太多，尤其在样本的收集比较困难的情况下，只要能在模型性能达到期望的效果，样本越少越好。同样地，假设样本数目 $m$ 和 $\delta$ 都确定了，我们想知道假设集合 $\mathcal{H}$ 中所有假设函数的训练误差和泛化误差间偏离程度 $\gamma$

$\begin{equation}|R(h_j)-\hat{R}(h_j)|\leq\gamma\leq\sqrt{\frac{1}{2m}\log\frac{2|\mathcal{H}|}{\delta}} \end{equation}$

接下来，我们给出 $\hat{h}$ 的泛化误差上界。定义假设集合 $\mathcal{H}$ 的最优假设函数为

$\begin{equation}h^{\star}=arg\underset{h\in\mathcal{H}}{\min}\;R(h) \end{equation}$

由于 $h^{\star}$ 训练误差小于 $\hat{h}$ ，结合 $|R(h)-\hat{R}{h}|\leq\gamma$ ，可得到 $\hat{h}$ 的泛化误差上界：

$\begin{equation}R(\hat{h})\leq\hat{R}(\hat{h})+\gamma\leq\hat{R}(h^{\star})+\gamma\leq R(h^{\star})+2\gamma\end{equation}$

上式说明，训练误差最小的假设函数 $\hat{h}$ 的泛化误差顶多比假设集合中最优的假设函数 $h^{\star}$ 高 $2\gamma$ ，即：

$\begin{equation}R(\hat{h})\leq\left(\underset{h\in\mathcal{H}}{\min}\;R(h)\right)+2\sqrt{\frac{1}{2m}\log\frac{2|\mathcal{H}|}{\delta}} \end{equation}$

我们可以总结出如下规律：在 $|\mathcal{H}|$ 有限的情况下，只要样本数目 $m$ 足够大，就有 $R(\hat{h})\approx \hat{R}(h)$ ；此时若有 $\hat{R}(\hat{h } )\approx 0$ ，必然有 $R(\hat{h} )\approx 0$ ，即通过经验风险最小化得到的最优假设函数是可靠的。但实际情况并非如此简单：如果 $|\mathcal{H}|$ 有限，在大多数情况下我们无法保证从 $\mathcal{H}$ 中选择出来的假设函数的经验风险趋近于0(少数时候可以碰巧找到经验风险为0的假设函数)，此时 $\hat{h}$ 的泛化误差可能无法令人满意；如果| $\mathcal{H}$ 趋于无限，我们虽可以保证 $R(\hat{h} )\approx 0$ ，但根据上式又无法得到 $R(\hat{h})\approx \hat{R}(h)$ ，使得无法确保 $\hat{h}$ 的泛化误差足够小。

SVM的置信界¶

假设训练点都处于一个半径为 $R$ 的球体之中，且让 $G(x)=\text{sign}[f(x)]=\text{sign}[{\beta}^Tx+{\beta}_o]$ ,则由 ${G(x),\Vert\beta\Vert\leq A}$ 组成的函数集合的VC维 $h$ 满足

$\begin{equation}h\leq R^2A^2\end{equation}$

如果 $f(x)$ 是在 $\Vert \beta\Vert\leq A$ 下分离训练数据最优的函数。则在测试集上的误差 $E(test)$ 我们有如下界限

$\begin{equation}Pr(E(test)\leq 4\frac{h[\log (2B/h)+1]-\log (\eta /4)}{N})\geq 1-\eta\end{equation}$

在SVM中，规则化参数 $C$ 的作用是用来约束分类器VC维的上界。根据结构风险最小化原则，我们来选择使得测试误差上界最小的 $C$ 。但是利用正则化项 $C$ 与交叉验证相比哪个更好，目前还不清楚。