当前位置: 代码迷 >> 综合 >> Fundations of Machine Learning 2nd——第三章(二)growth fuction和 VC-Dimension
  详细解决方案

Fundations of Machine Learning 2nd——第三章(二)growth fuction和 VC-Dimension

热度:31   发布时间:2024-02-26 21:09:08.0

Fundations of Machine Learning 2nd——第三章(二)growth fuction和 VC-Dimension

  • 前言
  • Growth function
    • 引理1 Massart's Lemma
    • 推论1
    • 推理2 growth function的generalization bound
  • VC-dimension
  • 定义1 VC-dimension
    • Example 1 实线上的区间
    • Example 2 超平面
    • 定理1 Radon's Theorem
    • Example 3 平行坐标轴的矩形
    • 定理2 Sauer's Lemma
    • 推理1
    • 推理2 VC-dimension generalization bounds

前言

我们上篇文章讲了对于映射集HHH无限的情况,可以使用拉德马赫复杂度来表示其generalization error边界,然而拉德马赫复杂度的计算十分困难,因此本节引入VC维的概念来使得这个边界可以在现实中被计算出来,在介绍VC维之前我们先介绍growth function这个先验知识(VC维的generalization bound需要以growth function作为中间媒介)。

Growth function

growth function中文名翻译成生长函数…我总感觉像生物用语。。所以还是叫英文名字吧。。
先来看看他的定义:
对于映射集HHH的growth function: ΠH(m):N→N\Pi_{H}(m):N\rightarrow NΠH?(m):NN,定义如下:
?m∈N,ΠH(m)=max?{x1,...xm}?X∣{h(x1),...,h(xm):h∈H}∣\forall m\in N, \Pi_H(m) = \max\limits_{\{x_1,...x_m\}\subset X}|\{h(x_1),...,h(x_m):h\in H\}|?mN,ΠH?(m)={ x1?,...xm?}?Xmax?{ h(x1?),...,h(xm?):hH}

解释:我们先引入一个概念:dichotomydichotomydichotomy。它的定义如下:对于一个映射h∈Hh\in HhH,将hhh作用在样本集{x1,...,xm}\{x_1,...,x_m\}{ x1?,...,xm?}上会产生一个分类结果(我们假设是二分类),这个结果可能是{0,1,...,1}\{0,1,...,1\}{ 0,1,...,1}。我们把这样的一种分类结果称为dichotomydichotomydichotomy。那么,对于一个样本集来说,将HHH里所有的映射都作用在上面时,最多2m2^m2m种结果,因为也许有的结果在当前的问题里肯定不会出现(后面我们会举例子),所以dichotomydichotomydichotomy的个数也有可能小于2m2^m2m。那么HHH的growth function要找的就是能产生dichotomydichotomydichotomy数量最多的一个大小为mmm样本集,他的dichotomydichotomydichotomy数量即为ΠH(m)\Pi_H(m)ΠH?(m)

所以,growth function给我们提供了另一种计算映射集HHH的丰富度的方法。

那么如何用growth function替代拉德马赫复杂度在约束边界上的位置呢?
需要用到一个马萨特引理(Massart’s Lemma):

引理1 Massart’s Lemma

定义:令A?RmA\subset R^mA?Rm是一个有限集,设r=maxx∈A∥x∥2r=max_{x\in A}\|x\|_2r=maxxA?x2?,下式成立:
Eσ[1msup?x∈A∑i=1mσixi]≤r2log?∣A∣m\mathop{E}\limits_\sigma[\frac{1}{m}\sup\limits_{x\in A}\sum_{i=1}^m\sigma_ix_i]\leq\frac{r\sqrt{2\log|A|}}{m}σE?[m1?xAsup?i=1m?σi?xi?]mr2logA ??
σi\sigma_iσi?是独立同分布的随机变量,取值为{1,?1}\{1,-1\}{ 1,?1}xix_ixi?是向量xxx的第i项。

证明:

需要介绍一个最大不等式定理和推论:
最大不等式定理:
X1,...,XnX_1,...,X_nX1?,...,Xn?n≥1n\geq1n1的实值随机变量,对于所有的j∈[n]j\in[n]j[n]t>0t>0t>0,如果对于一些r>0r>0r>0满足:E[etXj]≤et2r2/2E[e^{tX_j}]\leq e^{t^2r^2/2}E[etXj?]et2r2/2,那么下列不等式成立:
E[max?j∈[n]Xj]≤r2log?nE[\max\limits_{j\in[n]}X_j]\leq r\sqrt{2\log n}E[j[n]max?Xj?]r2logn ?
证明:
对于任意的t>0t>0t>0,通过指数函数的凹性和杰森不等式,下式成立:
etE[maxj∈[n]Xj]≤E[etmax?j∈[n]Xj]=E[max?j∈[n]etXj]≤E[∑j∈[n]etXj]≤net2r22e^{tE[max_{j\in[n]}X_j]}\leq E[e^{t\max_{j\in[n]}X_j}]=E[\max\limits_{j\in[n]}e^{tX_j}]\leq E[\sum\limits_{j\in[n]}e^{tX_j}]\leq ne^{\frac{t^2r^2}{2}}etE[maxj[n]?Xj?]E[etmaxj[n]?Xj?]=E[j[n]max?etXj?]E[j[n]?etXj?]ne2t2r2?
第一步转换利用了指数函数的凹性+杰森不等式

补充杰森不等式:
f(x)f(x)f(x)是区间[a,b]上的下凹函数,对于人意的x1,x2...xn∈[a,b]x_1,x_2...x_n\in[a,b]x1?,x2?...xn?[a,b],有不等式:
∑i=1nf(xi)n≥f(∑i=1nxin)\frac{\sum_{i=1}^nf(x_i)}{n}\geq f(\frac{\sum_{i=1}^nx_i}{n})ni=1n?f(xi?)?f(ni=1n?xi??)
其加权形式为:
在原条件上,且a1+a2+...+an=1a_1+a2+...+a_n=1a1?+a2+...+an?=1,且aia_iai?都为正数,有:
f(∑i=1naixi)≤∑i=1naif(xi)f(\sum_{i=1}^na_ix_i)\leq\sum_{i=1}^na_if(x_i)f(i=1n?ai?xi?)i=1n?ai?f(xi?)

最大不等式推论:
X1,..,XnX_1,..,X_nX1?,..,Xn?n≥1n\geq1n1的实值随机变量,对于所有的j∈[n]j\in[n]j[n]Xj=∑i=1mYijX_j=\sum_{i=1}^mY_{ij}Xj?=i=1m?Yij?,对于每一个固定的j∈[n]j\in[n]j[n]YijY_{ij}Yij?都是独立的零均值变量,取值在[?ri,ri][-r_i,r_i][?ri?,ri?],对一些ri>0r_i>0ri?>0,下列不等式成立:
E[max?j∈[n]Xj]≤r2log?nE[\max\limits_{j\in[n]}X_j]\leq r\sqrt{2\log n}E[j[n]max?Xj?]r2logn ?
其中r=∑i=1mri2r=\sqrt{\sum_{i=1}^mr_i^2}r=i=1m?ri2? ?

证明:
由于E[etXj]=E[Πi=1metYij]=Πi=1mE[etYij]≤Πi=1met2rj22=et2r22E[e^{tX_j}]=E[\mathop{\Pi}\limits_{i=1}^me^{tY_{ij}}]=\mathop{\Pi}\limits_{i=1}^mE[e^{tY_{ij}}]\leq \mathop{\Pi}\limits_{i=1}^m e^{\frac{t^2r_j^2}{2}}=e^{\frac{t^2r^2}{2}}E[etXj?]=E[i=1Πm?etYij?]=i=1Πm?E[etYij?]i=1Πm?e2t2rj2??=e2t2r2?
倒第二个转换用了霍夫丁引理:

XXX表示E[X]=0E[X]=0E[X]=0的随机变量,且a≤X≥b,b>aa\leq X \geq b, b>aaXb,b>a,对于任意的t>0t>0t>0,都有:
E[etX]≤et2(b?a)28E[e^{tX}]\leq e^{\frac{t^2(b-a)^2}{8}}E[etX]e8t2(b?a)2?

所以能够利用最大不等式来得到该引理。

终于把最大不等式给说完了!现在目光切回到Massart’s Lemma!
如果把Massart’s Lemma中的σixi\sigma_ix_iσi?xi?看做一个新的变量yiy_iyi?的话,很容易发现yiy_iyi?取值在[?xi,xi][-x_i,x_i][?xi?,xi?]中,且∑i=1mxi2≤r\sqrt{\sum_{i=1}^mx_i^2}\leq ri=1m?xi2? ?r(注意,这里的r是Massart’s Lemma里定义的)。
∑i=1myi\sum_{i=1}^my_ii=1m?yi?看做新变量X,那么sup?x∈A∑i=1mσixi=max?x∈A∑i=1myi=max?j∈[n]Xj\sup\limits_{x\in A}\sum_{i=1}^m\sigma_ix_i=\max\limits_{x\in A}\sum_{i=1}^my_i=\max\limits_{j\in[n]}X_jxAsup?i=1m?σi?xi?=xAmax?i=1m?yi?=j[n]max?Xj?
根据最大不等式推论就能得到马萨特引理。
Eσ[1msup?x∈A∑i=1mσixi]≤r2log?∣A∣m\mathop{E}\limits_\sigma[\frac{1}{m}\sup\limits_{x\in A}\sum_{i=1}^m\sigma_ix_i]\leq\frac{r\sqrt{2\log|A|}}{m}σE?[m1?xAsup?i=1m?σi?xi?]mr2logA ??

OK 现在证明了马萨特引理了!该想想怎么用growth function替换拉德马赫复杂度了!

推论1

GGG表示一个函数族,输出取值为{?1,1}\{-1,1\}{ ?1,1},下式成立:
Rm(G)≤2log?ΠG(m)mR_m(G)\leq\sqrt{\frac{2\log\Pi_G(m)}{m}}Rm?(G)m2logΠG?(m)? ?

证明:
对于一个固定的样本集S={x1,..xm}S=\{x_1,..x_m\}S={ x1?,..xm?},定义G∣SG_{|S}GS?为函数结果向量集,对于g∈Gg\in GgG:其结果向量为{g(x1),..,g(xm)}T\{g(x_1),..,g(x_m)\}^T{ g(x1?),..,g(xm?)}T。因为输出在{?1,1}\{-1,1\}{ ?1,1},所以结果向量的模最大为m\sqrt{m}m ?。接下来就要用到Massart’s Lemma!!:
Rm(G)=ES[Eσ[sup?u∈G∣S1m∑i=1mσiui]]≤ES[m2log?∣G∣S∣m]R_m(G)=\mathop{E}\limits_S[\mathop{E}\limits_\sigma[\sup\limits_{u\in G_{|S}}\frac{1}{m}\sum_{i=1}^m\sigma_iu_i]]\leq\mathop{E}\limits_{S}[\frac{\sqrt{m}\sqrt{2\log|G_{|S}|}}{m}]Rm?(G)=SE?[σE?[uGS?sup?m1?i=1m?σi?ui?]]SE?[mm ?2logGS? ??]
由于∣G∣S∣≤ΠG(m)|G_{|S}|\leq \Pi_G(m)GS?ΠG?(m):
Rm(G)≤ES[m2log?∣G∣S∣m]=2log?ΠG(m)mR_m(G)\leq\mathop{E}\limits_S[\frac{\sqrt{m}\sqrt{2\log|G_{|S}|}}{m}]=\sqrt{\frac{2\log\Pi_G(m)}{m}}Rm?(G)SE?[mm ?2logGS? ??]=m2logΠG?(m)? ?

注意 这个不等式里就用growth function来表示了拉德马赫复杂度的上界。下一步终于到了这一小节的第一个高潮——把约束边界里的拉德马赫复杂度换成growth function!

推理2 growth function的generalization bound

HHH表示一个函数族,输出值为{?1,1}\{-1,1\}{ ?1,1}。对于任意的δ>0\delta>0δ>0,我们都有1?δ1-\delta1?δ的把握对于任意的h∈Hh\in HhH,下式成立:
R(h)≤R^S(h)+2log?ΠH(m)m+log?1δ2mR(h)\leq\hat{R}_S(h)+\sqrt{\frac{2\log\Pi_H(m)}{m}}+\sqrt{\frac{\log\frac{1}{\delta}}{2m}}R(h)R^S?(h)+m2logΠH?(m)? ?+2mlogδ1?? ?

不过我们的growth function只能算是一个中转站,因为计算growth function需要对所有的m≥1m\geq1m1的样本集计算,下面介绍的VC维也是一种计算映射集HHH复杂度的方法,不过更简单实用。

VC-dimension

VC-dimension(Vapnik-Chervonenkis dimension)。
介绍VC维之前先介绍一个概念:“shattering”
shattering表示:如果一个映射集HHH,对一个样本集SSSm≥1m\geq1m1),能够产生该样本集的所有可能的dichotomies,即ΠH(m)=2m\Pi_H(m)=2^mΠH?(m)=2m,就称HHH shattering SSS

定义1 VC-dimension

一个映射集HHH的VC-dimension是HHH可以shattering的最大到的样本集的大小。
VCdim(H)=maxm:ΠH(m)=2mVCdim(H)=max{m:\Pi_H(m)=2^m}VCdim(H)=maxm:ΠH?(m)=2m
所以,如果VCdim(H)=dVCdim(H)=dVCdim(H)=d,说明存在一个大小为ddd的样本集,能够被HHHshatter,但是不代表所有大小为ddd的样本集都能被HHHshatter。

下面举几个例子来更深入的理解VC-dimension的含义。

Example 1 实线上的区间

这个问题里的映射集就是实线上的各个区间。很明显他的VC-dimension至少是2。因为对于两个样本,他们的所有可能的dichotomy为(+,+),(+,?),(?,+),(?,?)(+,+),(+,-),(-,+),(-,-)(+,+),(+,?),(?,+),(?,?),都可以被产生。下图是可视化表示:
在这里插入图片描述
然鹅,没有一个大小为3的样本集能够被HHHshatter。(大家自己画画图就知道了~)

Example 2 超平面

首先考虑二维空间的超平面(其实就是一条直线),那么,任何三个非线性的点都可以被shatter。
前方高能——
在这里插入图片描述上面这个图就是三个点时可能的分类结果,虽然只画了四条线,不过每一条线分割出来的两部分都可以交换他们的正负性,因此3个点有8个dichotomy,所以可以被shatter。
而四个点的时候呢?
在这里插入图片描述当他们的正负性为上图所示的时候,就没有直线可以实现。因此不能被shattered。

更一般的,在RdR^dRd中,我们考虑一个大小为d+1d+1d+1的样本集。令x0=(0,0...,0)x_0=(0,0...,0)x0?=(0,0...,0)是原点。对于i∈{1,...,d}i\in\{1,...,d\}i{ 1,...,d}xix_ixi?的第iii个位置为1,其余为0。他们的标签y0,y1,y2,..,yd∈{?1,1}y_0,y_1,y_2,..,y_d\in\{-1,1\}y0?,y1?,y2?,..,yd?{ ?1,1},同时定义一个向量www,他的第iii项是yiy_iyi?。于是,超平面定义为:w?x+y02=0w·x+\frac{y_0}{2}=0w?x+2y0??=0,能够shatter所有的d+1d+1d+1个样本。
sgn(w?x+y02)=sgn(yi+y02)=yisgn(w·x+\frac{y_0}{2})=sgn(y_i+\frac{y_0}{2})=y_isgn(w?x+2y0??)=sgn(yi?+2y0??)=yi?

注意,这个公式对于size>d+1size>d+1size>d+1的样本集不适用,因为xxx的维数为ddd

也就是说对于样本在RdR^dRd的空间中,超平面分类至少能够shatter 大小为d+1d+1d+1的样本。下面我们来考虑size>d+1size>d+1size>d+1的情况,要先用到一个定理:

定理1 Radon’s Theorem

任何一个有d+2d+2d+2个在RdR^dRd的点的样本集XXX,都可以被分成两个子集X1,X2X_1,X_2X1?,X2?,且这两个子集凸包相交。

证明:
X={x1,...xd+2}?RdX=\{x_1,...x_{d+2}\}\subset R^dX={ x1?,...xd+2?}?Rd,下面的等式组成了一个d+1个线性方程组。
∑i=1d+2αixi=0∑i=1d+2αi=0==>α1x1,1+α2x21+...αd+2xd+2,1=0...α1x1,i+α2x2i+...αd+2xd+2,i=0...α1+...+αd+2=0\sum_{i=1}^{d+2}\alpha_ix_i=0\quad \sum_{i=1}^{d+2}\alpha_i=0\\==>\\ \alpha_1x_{1,1}+\alpha_2x_{21}+...\alpha_{d+2}x_{d+2,1} = 0\\...\\ \alpha_1x_{1,i}+\alpha_2x_{2i}+...\alpha_{d+2}x_{d+2,i} = 0\\...\\ \alpha_1+...+\alpha_{d+2} = 0i=1d+2?αi?xi?=0i=1d+2?αi?=0==>α1?x1,1?+α2?x21?+...αd+2?xd+2,1?=0...α1?x1,i?+α2?x2i?+...αd+2?xd+2,i?=0...α1?+...+αd+2?=0
未知数(αi\alpha_iαi?)有d+2d+2d+2个,方程有d+1d+1d+1个,因此必有非零解β1,...βd+2\beta_1,...\beta_{d+2}β1?,...βd+2?
又因为β1+...+βd+2=0\beta_1+...+\beta_{d+2} = 0β1?+...+βd+2?=0,因此J1={i∈[d+2]:βi>0},J2={i∈[d+2]:βi≤0}J_1=\{i\in[d+2]:\beta_i>0\},J_2=\{i\in[d+2]:\beta_i\leq0\}J1?={ i[d+2]:βi?>0},J2?={ i[d+2]:βi?0}都是非空集合。我们可以把样本集划分为X1={xi,i∈J1}X2={xi,i∈J2}X_1=\{x_i,i\in J_1\}\quad X_2=\{x_i,i\in J_2\}X1?={ xi?,iJ1?}X2?={ xi?,iJ2?}。因为∑i∈J1βi=?∑i∈J2βi\sum\limits_{i\in J_1}\beta_i=-\sum\limits_{i\in J_2}\beta_iiJ1??βi?=?iJ2??βi?,设β=∑i∈J1βi\beta=\sum\limits_{i\in J_1}\beta_iβ=iJ1??βi?,根据上面的两个公式可得:
∑i∈J1βiβxi=∑i∈J2?βiβxi\sum\limits_{i\in J_1}\frac{\beta_i}{\beta}x_i=\sum\limits_{i\in J_2}-\frac{\beta_i}{\beta}x_iiJ1??ββi??xi?=iJ2???ββi??xi?
因为∑i∈J1βiβ=∑i∈J2?βiβ=1\sum\limits_{i\in J_1}\frac{\beta_i}{\beta}=\sum\limits_{i\in J_2}-\frac{\beta_i}{\beta}=1iJ1??ββi??=iJ2???ββi??=1,且i∈J1时βiβ>0i\in J_1 时 \frac{\beta_i}{\beta}>0iJ1?ββi??>0i∈J2时?βiβ>0i\in J_2 时 -\frac{\beta_i}{\beta}>0iJ2??ββi??>0,所以∑i∈J1βiβxi\sum_{i\in J_1}\frac{\beta_i}{\beta}x_iiJ1??ββi??xi?同时属于X1,X2X_1,X_2X1?,X2?的凸包。
所以不存在超平面能够区分X1X_1X1?X2X_2X2?。而任意大小为d+2d+2d+2的,样本点在RdR^dRd的样本集,都可以分出来一组这样的两个子集(凸包相交),所超平面HHH不能shatter大小为d+2d+2d+2的样本集。所以VCdim(hyperplane in R^d)=d+1d+1d+1

Example 3 平行坐标轴的矩形

四个样本点的很容易被证明可以被shatter。下图(a)展示了部分情况,其余的自己画画就能找出来~下图(b)说明了五个样本点的时候肯定不能被shatter。
在这里插入图片描述

还有很多,就不一一列举了~

定理2 Sauer’s Lemma

HHH表示一个VCdim(H)=dVCdim(H)=dVCdim(H)=d的映射集。对于所有的m∈Nm\in NmN,下列不等式成立:
ΠH(m)≤∑i=0dCmd\Pi_H(m)\leq \sum_{i=0}^dC_m^dΠH?(m)i=0d?Cmd?

证明:
首先说明,这个推理用了归纳演绎的方法。显然,m=1m=1m=1时,d=0或者d=1d=0 或者d=1d=0d=1都是符合定理的。假设对于(m?1,d?1)和(m?1,d)(m-1,d-1)和(m-1,d)(m?1,d?1)(m?1,d)都成立。
固定一个样本集S={x1,..,xm}S=\{x_1,..,x_m\}S={ x1?,..,xm?},有ΠH(m)\Pi_H(m)ΠH?(m)个dichotomy,令G=H∣SG=H_{|S}G=HS?表示被SSS约束的一个映射集合。
考虑S′={x1,...xm?1}S^{'}=\{x_1,...x_{m-1}\}S={ x1?,...xm?1?},定义G1=G∣S′G_1=G_{|S^{'}}G1?=GS?表示被S′S^{'}S约束的一个映射集合。如果我们把每一个映射当成是一个非零点集(第iii个点表示x_i为0/1),可以定义G2G_2G2?如下:
G2={g′?S′:(g′∈G)∧(g′∪{xm}∈G)}G_2=\{g^{'}\subset S^{'}:(g^{'}\in G)\land (g^{'}\cup\{x_m\}\in G)\}G2?={ g?S:(gG)(g{ xm?}G)}
G1,G2G_1,G_2G1?,G2?的可视化如下:

在这里插入图片描述
(这个G1,G2G_1,G_2G1?,G2?解释的太抽象了,这图咱也没咋看懂,我个人理解是:G1G_1G1?表示的就是不考虑xmx_mxm?的所有dichotomy,G2G_2G2?表示的是对于SSS来说的所有dichotomy里,xm=0、xm=1x_m=0、x_m=1xm?=0xm?=1两种情况都有的前m?1m-1m?1个样本对应的dichotomy。。比如上图里第一行和第二行,除了xmx_mxm?取值不同,其余的取值都相同,G1G_1G1?表示的dichotomies里满足这种要求的dichotomies构成G2G_2G2?

所以∣G1∣+∣G2∣=∣G∣|G_1|+|G_2|=|G|G1?+G2?=G

由于VCdim(G1)≤VCdim(G)≤dVCdim(G_1)\leq VCdim(G)\leq dVCdim(G1?)VCdim(G)d,根据我们前面的假设可以得到:
∣G1∣≤ΠG1(m?1)≤∑i=0dCm?1i|G_1|\leq \Pi_{G_1}(m-1)\leq\sum_{i=0}^dC_{m-1}^iG1?ΠG1??(m?1)i=0d?Cm?1i?

根据G2G_2G2?的定义,如果Z?S′Z\subset S^{'}Z?S可以被G2G_2G2?shatter,那么Z∪xmZ\cup{x_m}Zxm?一定可以被GGGshatter。所以:
VCdim(G2)≤VCdim(G)?1≤d?1VCdim(G_2)\leq VCdim(G)-1\leq d-1VCdim(G2?)VCdim(G)?1d?1
所以
∣G2∣≤ΠG2(m?1)≤∑i=0d?1Cm?1i|G_2|\leq\Pi_{G_2}(m-1)\leq\sum_{i=0}^{d-1}C_{m-1}^{i}G2?ΠG2??(m?1)i=0d?1?Cm?1i?
所以
∣G∣=∣G1∣+∣G2∣≤∑i=0dCm?1i+∑i=0d?1Cm=1i=∑i=0dCm?1i+Cm?1i?1=∑i=0dCmi|G| = |G_1|+|G_2| \leq \sum_{i=0}^dC_{m-1}^i+\sum_{i=0}^{d-1}C_{m=1}^i=\sum_{i=0}^dC_{m-1}^i+C_{m-1}^{i-1}=\sum_{i=0}^dC_m^iG=G1?+G2?i=0d?Cm?1i?+i=0d?1?Cm=1i?=i=0d?Cm?1i?+Cm?1i?1?=i=0d?Cmi?
(最后一步自己把Cm?1i?1+Cm?1iC_{m-1}^{i-1}+C_{m-1}^iCm?1i?1?+Cm?1i?展开一下就能得到~)

至此,定理得证。

这个定理有啥用呢,看接下来的一个推论

推理1

HHH表示一个映射集,VCdim(H)=dVCdim(H)=dVCdim(H)=d,对于所有的m≥dm\geq dmd
ΠH(m)≤(emd)d=O(md)\Pi_H(m)\leq(\frac{em}{d})^d=O(m^d)ΠH?(m)(dem?)d=O(md)

证明:(用到了上一个推理)
ΠH(m)≤∑i=0dCmi≤∑i=0dCmi(md)d?i≤∑i=0mCmi(md)d?i=(md)d∑i=0mCmi(dm)i=(md)d(1+dm)m≤(md)ded\Pi_H(m)\leq\sum_{i=0}^dC_m^i\leq\sum_{i=0}^dC_m^i(\frac{m}{d})^{d-i}\leq\sum_{i=0}^mC_m^i(\frac{m}{d})^{d-i}=(\frac{m}{d})^d\sum_{i=0}^mC_m^i(\frac{d}{m})^i=(\frac{m}{d})^d(1+\frac{d}{m})^m\leq(\frac{m}{d})^de^dΠH?(m)i=0d?Cmi?i=0d?Cmi?(dm?)d?ii=0m?Cmi?(dm?)d?i=(dm?)di=0m?Cmi?(md?)i=(dm?)d(1+md?)m(dm?)ded

本小节的第二个高潮要来了~在generalization bound中用VCdim替换growth function!!

推理2 VC-dimension generalization bounds

HHH表示一个映射族,取值在{?1,1}\{-1,1\}{ ?1,1}VCdim=dVCdim=dVCdim=d。对于任一δ>0\delta > 0δ>0,都有1?δ1-\delta1?δ的把握,令下式对于所有的h∈Hh\in HhH成立:
R(h)≤R^S(h)+2dlog?emdm+log?1δ2mR(h)\leq\hat{R}_S(h)+\sqrt{\frac{2d\log\frac{em}{d}}{m}}+\sqrt{\frac{\log\frac{1}{\delta}}{2m}}R(h)R^S?(h)+m2dlogdem?? ?+2mlogδ1?? ?
注意,这里右边的第二项把growth function generalization bounds里面的log?ΠG(m)\log\Pi_G(m)logΠG?(m)利用上面的推理1换成了 dlog?emdd\log\frac{em}{d}dlogdem?

一般化的写法就是:
R(h)≤R^S(h)+O(log?(m/d)m/d)R(h)\leq\hat{R}_S(h)+O(\sqrt{\frac{\log(m/d)}{m/d}})R(h)R^S?(h)+O(m/dlog(m/d)? ?)
这个边界可以用在实际估计中了~(只需要知道ddd就行)

  相关解决方案