Foundations of Machine Learning: Rademacher complexity and VC-Dimension(2)
（一） 增长函数（Growth function）
在引入增长函数之前，我们先介绍一个例子，这个例子会有助于理解增长函数这个东西。
在input space为$mathbb{R}$，假设空间为阈值函数，即当输入的点$x>v$时，将该点标为正。如 图1 为其中的6个假设。
图1 阈值函数示例
很显然，这个假设集合的大小为无限多个。但实际，我们很容易发现，对一个样本大小为m的样本，这些假设集可以分成$m+1$个大类，而每个大类里的假设对该样本产生的经验错都是一致的。故我们很容易的想到可以直接用每个大类的一个假设作为代表，也就是说无限个假设实际上有效的假设只有$m+1$个。所以第一，第二篇文章中的$|H|$可以用$m+1$来代替。
但很不幸，这是一个特定的例子，并且有效函数依赖与样本，所以我们并不容易将其推广开来。但换个思维，我们是否可以找到某种方法将无限多的假设集分成有限个大类，即用有限个有效的假设集来等价这个无限个假设集。这就是增长函数要干的事。
首先，定义一个二分的集合：
$$Pi_H(S)={(h(x_1),...,h(x_m)):hin H}$$
每一个$h$对样本进行二分类，都会得到一个结果，所有的结果形成的集合即$Pi_H(S)$，显然$|Pi_H(S)|leq 2^m$。
定义 2.3 增长函数 对一个假设集合H的增长函数$Pi_H:N ightarrow N$ 定义为：
$$forall min N,Pi_H(m)=max _{sin mathcal{X}^m}mid Pi_H(S)mid$$
$Pi_H(m)$表示使用hypothesis H 对任意m个点进行分类所能够产生的最大数量的不同方法。增长函数提供了另外一种衡量hypothesis set H 复杂性的方法，并且这种方法与 Rademacher complexity 不一样，它不依赖于产生样本的分布。
首先，我们先介绍一下Hoeffding引理。
Hoeffding Lemma: 令$aleq Xleq b$为期望$E[X]=0$的随机变量。那么，对于所有$t>0$，以下不等式成立：
$$E[exp(tX)] leq exp(frac{t^2(b-a)^2}{8})$$
定理 2.3 Massart's lemma: 令$Ain mathbb{R}^m$为一个有限的集合，记$r=max_{Xin A}parallel Xparallel_2$，那么以下不等式成立：
$$mathop{E} _{delta}[frac{1}{m} sup _{xin A}sum_{i=1}^m sigma_ix_i]leqfrac{rsqrt{2logmid Amid}}{m}.$$
这里的$sigma_i$为取值为${+1,-1}$的独立均匀随机变量，$x_1,...,x_m$ 为向量$x$的各个成分。
证明： 对任意$t>0$，使用Jensen's 不等式可得：
egin{align*}exp(tmathop{E} _sigma[sup _{xin A}sum _{i=1} ^msigma_ix_i])&leq mathop{E} _sigma[exp(tsup _{xin A}sum _{i=1} ^msigma_ix_i)] \&= mathop{E} _sigma[sup _{xin A}exp(sum _{i=1} ^mtsigma_ix_i)] \&leq sum _{xin A}mathop{E} _sigma[exp(sum _{i=1} ^mtsigma_ix_i)] end{align*}
再根据$sigma_i$的独立性，应用Hoeffding's lemma可得：
egin{align*}exp(tmathop{E} _sigma[sup _{xin A}sum _{i=1} ^msigma_ix_i])&leq sum _{xin A}prod _{i=1} ^mmathop{E} _{sigma_i}[exp(tsigma_ix_i)] \&leq sum _{xin A}prod _{i=1} ^m exp[frac{t^2(2x_i)^2}{8}] \&=sum _{xin A}exp[frac{t^2}{2}sum _{i=1} ^mx_i^2] \&leq sum _{xin A}exp[frac{t^2r^2}{2}]=|A|e^{frac{t^2r^2}{2}}end{align*}
两边取$log$，再同时除以t，可得：
$$mathop{E} _{sigma}[sup _{xin A}sum_{i=1}^m sigma_i x_i] leq frac{log|A|}{t}+frac{tr^2}{2}$$
对所有$t>0$均成立，令$t=frac{sqrt{2log|A|}}{r}$,使右边的式子最小，
$$mathop{E} _{delta}[mathop{sup} _{xin A}sum_{i=1}^m sigma_i x_i] leq rsqrt{2log|A|}$$
再同时除以m即得到定理中的式子。证毕！
应用Massart's lemma，就可以用增长函数界定Rademacher complexity.
推论 2.1 令G为取值为${+1,-1}$的函数族，那么以下不等式成立：
$$mathfrak{R}_m(G)leqsqrt{frac{2logPi_G(m)}{m}}.$$
证明： 对一个固定的样本$S=(x_1,...,x_m)$,定义$G_{|S}$为
$$G_{|S}={ (g(x_1),...,g(x_m)))^T:gin G }$$
由于$g(x)$的取值为${-1,1}$，所以对$forall uin G_{|S}$,有$| u|_2leq sqrt{m}$。并且根据$G_{|S}$定义可知$G_{|S}=Pi_G(S)$,故$|G_{|S}|leq Pi_G(m)$。
所以，应用Massart's lemma有：
egin{align*}mathfrak{R}_m(G) &= mathop{E} _S[mathop{E} _sigma[sup _{uin G_{|S}}frac{1}{m}sum _{i=1} ^msigma_iu_i]] \&leq mathop{E} _S[frac{sqrt{m}sqrt{2log|G_{|S}|}}{m}] \&leq mathop{E} _S[frac{sqrt{m}sqrt{2logPi_G(m)}}{m}] leq sqrt{frac{2logPi_G(m)}{m}}end{align*}
证毕！
再将它与 定理2.2 结合起来，就得到增长函数表示的泛化边界：
推论 2.2 增长函数泛化界 令H为取值为${-1,+1}$的函数族。那么，对任意$delta>0$，以概率$1-delta$，对所有$hin H$，以下不等式成立：
egin{align}label{equ:9}R(h)leqwidehat{R}(h)+sqrt{frac{2logPi_H(m)}{m}}+sqrt{frac{logfrac{1}{delta}}{2m}}end{align}
另外，增长函数也可以不用首先通过Rademacher Complexity来界定，即：
$$mathop{Pr}[mid R(h)-widehat{R}(h)mid>epsilon]leq 4Pi_H(2m)exp(-frac{mepsilon^2}{8})$$
这个不等式与式子 ef{equ:9}只差一个常数。
（二）VC维（VC-Dimension）
在介绍VC维时，我们得先来了解二个概念，一个是前面在介绍增长函数时已经讲过的“二分”(dichotomy)，还有一个是打散（shattering）。
所谓“二分”指的是给定一个样本S，和一个假设$h$，用$h$对S进行分类的结果称为二分。因此对一个假设集合H，可以产生多种不同的“二分”，而这些二分构成了假设集H对样本S的二分集合$Pi_H(S)$。
“打散”的概念同样也是针对假设集和样本。我们说“一个样本S可以被假设集H打散”当且仅当用这个假设集中的假设可以实现样本S的所有可能的“二分”，即$mid Pi_H(S)mid=2^m$。
现在来定义VC维，假设集H的VC维指的就是能够被H打散的最大的样本个数。更严格定义如下：
定义 2.4 VC-Dimension 假设集H的VC维是能够被H打散的最大样本集的大小：
$$mathop{VCdim}(H)=max{m:Pi_H(m)=2^m}.$$
这里必须注意两点：如果我们说假设集H的VC维d，那么意思就是说
- 存在着一个样本大小为d的样本能够被H打散（并不是说所有样本大小为d的样本都能够被打散）；
- 不存在一个样本大小为$d+1$的样本能够被H打散（即所有样本大小为$d+1$的样本都不能被H打散）
一些例子（这些例子的证明可见本人以前的文章：http://www.cnblogs.com/boostable/p/iage_VC_dimension.html）：
- 当S为平面，H为矩形框，$VCdim(H)=4$.
- 当S为x轴，H为区间，$VCdim(H)=2$.
- 当S为圆周，H为凸集，$VCdim(H)=infty$.
- 当S为k维空间，H为半空间，$VCdim(H)=k+1$.
接下来我们来证明一个定理，它将增长函数与VC维联系起来。
定理 2.4 Sauer's lemma 令H称为$mathop{VCdim}(H)=d$的假设集。那么，对所有$min N$，以下不等式成立：
$$Pi_H(m)leqsum_{i=0}^d{m choose i}.$$
证明：首先，确定m可取的值为$1,2,...$，d可取的值为$0,1,2,...$，
- 当$m=d$时，$Pi_H(m)=2^d$,而
$$sum _{i=0} ^d {m choose i}=sum _{i=0} ^d{d choose i}=2^d$$
故上式成立。 - 当$m<d$时，$Pi_H(m)=2^m$,而
$$sum _{i=0} ^d {m choose i}=sum _{i=0} ^m{m choose i}+sum _{i=m+1} ^d{m choose i}=2^m $$
故上式成立。 - 当$m>d$时，用归纳法证明。
- 当$d=0$时，对所有m都成立。这是因为$d=0$时$Pi_H(m)=2^0$,而$sum _{i=0} ^d{m choose i}=1$,故成立。
- 假设$(m,d-1)$时成立，即$Pi_H(m)leqsum _{i=0} ^{d-1}{m choose i}$，则
$$sum _{i=0} ^{d-1}{m choose i} leq sum _{i=0} ^{d-1}{m choose i}+{m choose d}=sum _{i=0} ^{d}{m choose i}$$
$(m,d)$也成立。
如 图2 所示。证毕！
图2 Sauer's lemma 示例
推论 2.3 令H为$mathop{VCdim}(H)=d$的假设集。那么，对所有的$mgeq d$:
$$Pi_H(m)leq{frac{em}{d}}^d=O(m^d)$$
证明：
egin{align*}Pi_H(m) &leq sum _{i=0} ^d {m choose i} \&leq sum _{i=0} ^d {m choose i}(frac{m}{d})^{d-i} \&leq sum _{i=0} ^m {m choose i}(frac{m}{d})^{d-i} \&=(frac{m}{d})^dsum _{i=0} ^m{m choose i}(frac{m}{d})^i \&=(frac{m}{d})^d(1+frac{d}{m})^m leq (frac{m}{d})^de^dend{align*}
最后一个不等式是因为$(1-x)leq e^{-x}$。证毕！
于是我们可以把推论2.2 中的$Pi_H(m)$用它的上界$(frac{em}{d})^d$来替代，得到如下推论：
推论 2.4 VC-维泛化界 令H为取值为${+1,-1}$且VC维为d的假设集。那么，对任意的$delta>0$，至少以概率$1-delta$，以下不等式对所有$hin H$都成立：
$$mathcal{R}(h)leqwidehat{mathcal{R}}(h)+sqrt{frac{2dlogfrac{em}{d}}{m}}+sqrt{frac{logfrac{1}{delta}}{2m}}$$
我们可以将上式简写成
$$R(h)leqwidehat{R}(h)+O(sqrt{frac{log(m/d)}{m/d}})$$
也就是说上界由$m/d$决定，m越大上界越小，d越大H越复杂，上界也越大。