本文主要向大家介绍了VC编程之Foundataions of Machine Learning: Rademacher complexity and VC-Dimension，通过具体的内容向大家展示，希望对大家学习VC编程有所帮助。

（一） 增长函数（Growth function）

    在引入增长函数之前，我们先介绍一个例子，这个例子会有助于理解增长函数这个东西。

在input space为RR，假设空间为阈值函数，即当输入的点x>vx>v时，将该点标为正。如 图1 为其中的6个假设。

图1 阈值函数示例

很显然，这个假设集合的大小为无限多个。但实际，我们很容易发现，对一个样本大小为m的样本，这些假设集可以分成m+1m+1个大类，而每个大类里的假设对该样本产生的经验错都是一致的。故我们很容易的想到可以直接用每个大类的一个假设作为代表，也就是说无限个假设实际上有效的假设只有m+1m+1个。所以第一，第二篇文章中的|H||H|可以用m+1m+1来代替。

    但很不幸，这是一个特定的例子，并且有效函数依赖与样本，所以我们并不容易将其推广开来。但换个思维，我们是否可以找到某种方法将无限多的假设集分成有限个大类，即用有限个有效的假设集来等价这个无限个假设集。这就是增长函数要干的事。

    首先，定义一个二分的集合：

ΠH(S)={(h(x1),...,h(xm)):h∈H}ΠH(S)={(h(x1),...,h(xm)):h∈H}

每一个hh对样本进行二分类，都会得到一个结果，所有的结果形成的集合即ΠH(S)ΠH(S)，显然|ΠH(S)|≤2m|ΠH(S)|≤2m。

定义 2.3 增长函数 对一个假设集合H的增长函数ΠH:N→NΠH:N→N 定义为：

∀m∈N,ΠH(m)=maxs∈Xm∣ΠH(S)∣∀m∈N,ΠH(m)=maxs∈Xm∣ΠH(S)∣

ΠH(m)ΠH(m)表示使用hypothesis H 对任意m个点进行分类所能够产生的最大数量的不同方法。增长函数提供了另外一种衡量hypothesis set H 复杂性的方法，并且这种方法与 Rademacher complexity 不一样，它不依赖于产生样本的分布。

    首先，我们先介绍一下Hoeffding引理。

Hoeffding Lemma: 令a≤X≤ba≤X≤b为期望E[X]=0E[X]=0的随机变量。那么，对于所有t>0t>0，以下不等式成立：

E[exp(tX)]≤exp(t2(b−a)28)E[exp(tX)]≤exp(t2(b−a)28)

定理 2.3 Massart's lemma:  令A∈RmA∈Rm为一个有限的集合，记r=maxX∈A∥X∥2r=maxX∈A∥X∥2，那么以下不等式成立：

Eδ[1msupx∈A∑i=1mσixi]≤r2log∣A∣−−−−−−−√m.Eδ⁡[1msupx∈A∑i=1mσixi]≤r2log∣A∣m.

这里的σiσi为取值为{+1,−1}{+1,−1}的独立均匀随机变量，x1,...,xmx1,...,xm 为向量xx的各个成分。

证明： 对任意t>0t>0，使用Jensen's 不等式可得：

exp(tEσ[supx∈A∑i=1mσixi])≤Eσ[exp(tsupx∈A∑i=1mσixi)]=Eσ[supx∈Aexp(∑i=1mtσixi)]≤∑x∈AEσ[exp(∑i=1mtσixi)]exp⁡(tEσ⁡[supx∈A∑i=1mσixi])≤Eσ⁡[exp⁡(tsupx∈A∑i=1mσixi)]=Eσ⁡[supx∈Aexp⁡(∑i=1mtσixi)]≤∑x∈AEσ⁡[exp⁡(∑i=1mtσixi)]

再根据σiσi的独立性，应用Hoeffding's lemma可得：

exp(tEσ[supx∈A∑i=1mσixi])≤∑x∈A∏i=1mEσi[exp(tσixi)]≤∑x∈A∏i=1mexp[t2(2xi)28]=∑x∈Aexp[t22∑i=1mx2i]≤∑x∈Aexp[t2r22]=|A|et2r22exp⁡(tEσ⁡[supx∈A∑i=1mσixi])≤∑x∈A∏i=1mEσi⁡[exp⁡(tσixi)]≤∑x∈A∏i=1mexp⁡[t2(2xi)28]=∑x∈Aexp[t22∑i=1mxi2]≤∑x∈Aexp[t2r22]=|A|et2r22

两边取loglog，再同时除以t，可得：

Eσ[supx∈A∑i=1mσixi]≤log|A|t+tr22Eσ⁡[supx∈A∑i=1mσixi]≤log⁡|A|t+tr22

对所有t>0t>0均成立，令t=2log|A|√rt=2log⁡|A|r,使右边的式子最小，

Eδ[supx∈A∑i=1mσixi]≤r2log|A|−−−−−−√Eδ⁡[supx∈A⁡∑i=1mσixi]≤r2log⁡|A|

再同时除以m即得到定理中的式子。证毕！

    应用Massart's lemma，就可以用增长函数界定Rademacher complexity.

推论 2.1 令G为取值为{+1,−1}{+1,−1}的函数族，那么以下不等式成立：

Rm(G)≤2logΠG(m)m−−−−−−−−−−√.Rm(G)≤2logΠG(m)m.

证明： 对一个固定的样本S=(x1,...,xm)S=(x1,...,xm),定义G|SG|S为

G|S={(g(x1),...,g(xm)))T:g∈G}G|S={(g(x1),...,g(xm)))T:g∈G}

由于g(x)g(x)的取值为{−1,1}{−1,1}，所以对∀u∈G|S∀u∈G|S,有∥u∥2≤m−−√‖u‖2≤m。并且根据G|SG|S定义可知G|S=ΠG(S)G|S=ΠG(S),故|G|S|≤ΠG(m)|G|S|≤ΠG(m)。

     所以，应用Massart's lemma有：

Rm(G)=ES[Eσ[supu∈G|S1m∑i=1mσiui]]≤ES[m−−√2log|G|S|−−−−−−−−√m]≤ES[m−−√2logΠG(m)−−−−−−−−−−√m]≤2logΠG(m)m−−−−−−−−−−√Rm(G)=ES⁡[Eσ⁡[supu∈G|S1m∑i=1mσiui]]≤ES⁡[m2log⁡|G|S|m]≤ES⁡[m2log⁡ΠG(m)m]≤2log⁡ΠG(m)m

证毕！

    再将它与 定理2.2 结合起来，就得到增长函数表示的泛化边界：

推论 2.2 增长函数泛化界 令H为取值为{−1,+1}{−1,+1}的函数族。那么，对任意δ>0δ>0，以概率1−δ1−δ，对所有h∈Hh∈H，以下不等式成立：

R(h)≤Rˆ(h)+2logΠH(m)m−−−−−−−−−−√+log1δ2m−−−−−√(1)(1)R(h)≤R^(h)+2logΠH(m)m+log1δ2m

另外，增长函数也可以不用首先通过Rademacher Complexity来界定，即：

Pr[∣R(h)−Rˆ(h)∣>ϵ]≤4ΠH(2m)exp(−mϵ28)Pr⁡[∣R(h)−R^(h)∣>ϵ]≤4ΠH(2m)exp(−mϵ28)

这个不等式与式子11只差一个常数。

（二）VC维（VC-Dimension）

    在介绍VC维时，我们得先来了解二个概念，一个是前面在介绍增长函数时已经讲过的“二分”(dichotomy)，还有一个是打散（shattering）。

    所谓“二分”指的是给定一个样本S，和一个假设hh，用hh对S进行分类的结果称为二分。因此对一个假设集合H，可以产生多种不同的“二分”，而这些二分构成了假设集H对样本S的二分集合ΠH(S)ΠH(S)。
    “打散”的概念同样也是针对假设集和样本。我们说“一个样本S可以被假设集H打散”当且仅当用这个假设集中的假设可以实现样本S的所有可能的“二分”，即∣ΠH(S)∣=2m∣ΠH(S)∣=2m。

    现在来定义VC维，假设集H的VC维指的就是能够被H打散的最大的样本个数。更严格定义如下：

定义 2.4 VC-Dimension 假设集H的VC维是能够被H打散的最大样本集的大小：

VCdim(H)=maxm:ΠH(m)=2m.VCdim⁡(H)=maxm:ΠH(m)=2m.

这里必须注意两点：如果我们说假设集H的VC维d，那么意思就是说

存在着一个样本大小为d的样本能够被H打散（并不是说所有样本大小为d的样本都能够被打散）；

不存在一个样本大小为d+1d+1的样本能够被H打散（即所有样本大小为d+1d+1的样本都不能被H打散）

一些例子（这些例子的证明可见本人以前的文章：//www.cnblogs.com/boostable/p/iage_VC_dimension.html）：

当S为平面，H为矩形框，VCdim(H)=4VCdim(H)=4.

当S为x轴，H为区间，VCdim(H)=2VCdim(H)=2.

当S为圆周，H为凸集，VCdim(H)=∞VCdim(H)=∞.

当S为k维空间，H为半空间，VCdim(H)=k+1VCdim(H)=k+1.

接下来我们来证明一个定理，它将增长函数与VC维联系起来。

定理 2.4 Sauer's lemma 令H称为VCdim(H)=dVCdim⁡(H)=d的假设集。那么，对所有m∈Nm∈N，以下不等式成立：

ΠH(m)≤∑i=0d(mi).ΠH(m)≤∑i=0d(mi).

证明：首先，确定m可取的值为1,2,...1,2,...，d可取的值为0,1,2,...0,1,2,...，

当m=dm=d时，ΠH(m)=2dΠH(m)=2d,而

∑i=0d(mi)=∑i=0d(di)=2d∑i=0d(mi)=∑i=0d(di)=2d

故上式成立。

当m<dm<d时，ΠH(m)=2mΠH(m)=2m,而

∑i=0d(mi)=∑i=0m(mi)+∑i=m+1d(mi)=2m∑i=0d(mi)=∑i=0m(mi)+∑i=m+1d(mi)=2m

故上式成立。

当m>dm>d时，用归纳法证明。

当d=0d=0时，对所有m都成立。这是因为d=0d=0时ΠH(m)=20ΠH(m)=20,而∑di=0(mi)=1∑i=0d(mi)=1,故成立。

假设(m,d−1)(m,d−1)时成立，即ΠH(m)≤∑d−1i=0(mi)ΠH(m)≤∑i=0d−1(mi)，则

∑i=0d−1(mi)≤∑i=0d−1(mi)+(md)=∑i=0d(mi)∑i=0d−1(mi)≤∑i=0d−1(mi)+(md)=∑i=0d(mi)

(m,d)(m,d)也成立。

 如 图2 所示。证毕！

图2 Sauer's lemma 示例

推论 2.3 令H为VCdim(H)=dVCdim⁡(H)=d的假设集。那么，对所有的m≥dm≥d:

ΠH(m)≤emdd=O(md)ΠH(m)≤emdd=O(md)

证明：

ΠH(m)≤∑i=0d(mi)≤∑i=0d(mi)(md)d−i≤∑i=0m(mi)(md)d−i=(md)d∑i=0m(mi)(md)i=(md)d(1+dm)m≤(md)dedΠH(m)≤∑i=0d(mi)≤∑i=0d(mi)(md)d−i≤∑i=0m(mi)(md)d−i=(md)d∑i=0m(mi)(md)i=(md)d(1+dm)m≤(md)ded

最后一个不等式是因为(1−x)≤e−x(1−x)≤e−x。证毕！

    于是我们可以把推论2.2 中的ΠH(m)ΠH(m)用它的上界(emd)d(emd)d来替代，得到如下推论：

推论 2.4 VC-维泛化界 令H为取值为{+1,−1}{+1,−1}且VC维为d的假设集。那么，对任意的δ>0δ>0，至少以概率1−δ1−δ，以下不等式对所有h∈Hh∈H都成立：

R(h)≤Rˆ(h)+2dlogemdm−−−−−−−−√+log1δ2m−−−−−√R(h)≤R^(h)+2dlog⁡emdm+log⁡1δ2m

我们可以将上式简写成

R(h)≤Rˆ(h)+O(log(m/d)m/d−−−−−−−−√)R(h)≤R^(h)+O(log(m/d)m/d)

也就是说上界由m/dm/d决定，m越大上界越小，d越大H越复杂，上界也越大。

本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标编程语言VC/MFC频道！