如何通俗的理解机器学习中的VC维、shatter和break point？

理由

举报取消

2017年7月9日 3 条回复 3636 次浏览

互联网,学习,数学,数据挖掘,机器,编程

回复 ( 3 )

王留行管理大师
0
举报回复
理由

举报取消

学习VC维要先知道的概念有：增长函数（growth function）、对分（dichotomy）、打散（shattering）和断点（break point）

1.增长函数

增长函数表示假设空间H对m个示例所能赋予标记的最大可能结果数。

比如说现在数据集有两个数据点，考虑一种二分类的情况，可以将其分类成A或者B，则可能的值有：AA、AB、BA和BB，所以这里增长函数的值为4.

增长函数值越大则假设空间H的表示能力越强，复杂度也越高，学习任务的适应能力越强。不过尽管H中可以有无穷多的假设h，但是增长函数却不是无穷大的：对于m个示例的数据集，最多只能有个标记结果，而且很多情况下也达不到的情况。

2.对分

对于二分类问题来说，H中的假设对D中m个示例赋予标记的每种可能结果称为对D的一种对分（dichotomy）。对分也是增长函数的一种上限。

3.打散

打散指的是假设空间H能实现数据集D上全部示例的对分，即增长函数=。但是认识到不打散是什么则更加重要——

有些情况下H的增长函数不可以达到对应的值，比如说在二维实平面上的线性划分情况中，以下的情况就不可以线性可分（也就是说不能算作赋予标记的结果）：

或者下图这个

虽然图画的非常直击灵魂，但是你应该可以体会到这种情况下二维平面的线性分类器是不可以给上面的情况分类的（事实上对于任何集合，其=16种对分中至少有一种不能被线性划分实现）

4.Vapink-Chervonenkis Dimension

现在可以引出VC维的定义了——

假设空间H的VC维是能被H打散的最大的示例集（数据集）的大小，即有：
$VC(H)=max\{m:\prod(m)=2^m\}$
其中 $\prod(m)$ 为假设空间在数据集大小为m时的增长函数。

或者有这种更平实的定义——

对于一个假设空间H，如果存在m个数据样本能够被假设空间H中的函数按所有可能的种形式分开，则称假设空间H能够把m个数据样本打散（shatter）。假设空间H的VC维就是能打散的最大数据样本数目m。若对任意数目的数据样本都有函数能将它们shatter，则假设空间H的VC维为无穷大。

在上面那个4个点的图中，因为4个点的情况下以及不能做到对分，所以二维实平面上所有线性划分构成的假设空间H的VC维为3.

5.Break Point

在一些教课书中并没有提出Break Point的概念，这是林轩田《机器学习基石》公开课里的一种辅助概念。现在简单说一下break point的意义——我们希望假设空间H的增长函数越小越好（这样子假设空间比较简单），或者至少不要增长的太快——如果按照这种趋势增长那简直是没天理了。上面说道了，随着m的增大，一定会出现一个m使假设空间无法shatter。这种不满足的情况说明增长函数从这个点开始变缓了，是一个可喜可贺的重大突破，所以我们把第一个不满足shatter的m值称为break point（这里翻译成突破点）

给个不啰嗦的定义——

If no k inputs can be shattered by H , call k a break point for H .

从这个定义上看某个假设空间H的VC维数就是最大的非break point值，也就是break point-1.

参考资料

[1]周志华. 机器学习[M]. 清华大学出版社, 2016.

[2]沙伊・沙莱夫-施瓦茨, 沙伊・本-戴维. 深入理解机器学习:从原理到算法[M]. 机械工业出版社, 2016.

[3]Abumostafa Y S, Magdonismail M, Lin H T. Learning from Data: A Short Course[J]. Amlbook, 2012.

[4]白鹏. 支持向量机理论及工程应用实例[M]. 西安电子科技大学出版社, 2008.
偷泥王管理大师
0
举报回复
理由

举报取消

我来大致解释一下这三个概念吧。从逻辑和知识理解的先后顺序上来说，应该是先知道shatter，然后是break point，最后才是VC Dimension。

*为了便于理解，我们在binary target function的范畴内讨论

首先，假定我们的Hypothesis Set H是一个Binary function的集合，当我们将一个大小为N的sample data set(记作 $x_{1},x_{2},...,x_{N-1}$ )作为H中的一个hypothesis h的输入的时候，我们就会得到一个长度为N的tuple，形如 $(h(x_{1}),h(x_{2}),...,h(x_{N}))$ ，而这个tuple中的每个元素都是+1或者-1，我们把这样的一个tuple就称作为一个Dichotomy。

然后，我们定义，对于一个Hypothesis Set H来说， $H(x_{1},x_{2},...,x_{N})$ 是 H在sample（ $x_{1},x_{2},...,x_{N}$ ）上所有dichotomy的集合。

这样定义有啥好处呢？简单地解释一下。要知道，我们定义并发明这些概念的原因，在于我们以前是无法约束hypothesis的数量的。在Hoeffding’s Inequality中,

$P[\mid E_{in}-E_{out}\mid>\epsilon]$ $\leq2Me^{-2\epsilon^2N}$ ，

RHS中的M，也就是Hypothesis Set H的势，为无穷大。同样，在Generalization Bound中，

$E_{out}(g) \leq$ $E_{in}(g)+$ $(\frac{1}{2N}ln$ $\frac{2M}{\delta}$ $)^{\frac{1}{2}}$ ，

也出现了同样的问题，导致我们根本无法判断 $E_{in}$ 到底能不能够很好地估计 $E_{out}$ ，也就使得我们无法判断Learning的feasibility。而这里的一系列概念，就是要找到一个能够替代这个大M的有限的一个值，从而说明我们是可以做到Learning，不管能做到多好。

就差最后一个概念了，那就是Growth function。Growth function是什么呢，请不要执着于这个奇怪的名字，说白了对于一个Hypothesis Set H来说，它的Growth function就是它在任意N个点上所能产生的最多的dichotomy的数量，记作 $m_{H}(N)$ 。那么这个Growth function和前面所提的H在sample上所有的dichotomy的集合的势有什么区别呢？区别就在于这个Growth function是指针对任意N个点的最多的dichotomy数，而前面的集合是指对于特定的一个data set所能产生的dichotomy的集合。也就是说， $m_{H}(N)$ $max \mid$ $H(x_{1},x_{2},...,x_{N})$ $\mid$ 。

那么，我们可以知道一个显而易见的结论，那就是对于任何H， $m_{H}(N)$ $\leq 2^{N}$ （输入每一个 $x_{1},x_{2},...,x_{N}$ 都有两种可能的return值）。这样一来，我们首先就把原先的Hypothesis Set H的势，大M，给极大地缩小了范围（从无穷到有限），尽管 $2^{N}$ 仍旧是一个不现实的upper bound，但是最起码我们现在再讨论Generalization Bound，我们就可以说我们是可以约束RHS的。我觉得把Growth function看成是有效假设(Effective hypotheses)更加容易理解，也就是Growth function代表的是真正能得出不同结果的，有意义的Hypothesis的最大数量。

现在，铺垫了这么久，我们终于就可以来讲shatter了。如果H能在data set（ $x_{1},x_{2},...,x_{N}$ ）上产生所有的dichotomy，那么我们就说H可以shatter $x_{1},x_{2},...,x_{N}$ 。举两个例子。

Ex. input data set 为2D中的三个点，这三个点能够组成一个等边三角形；定义H为所有直线，若一个点在直线的一边，则return +1，否则return -1，请问H能够shatter这个吗？（并不规定直线的哪一边为+1，也就是说两种情况都可以）

可以。

Ex. input data set 为2D中的四个点，这四个点能够组成一个正方先；定义H为所有直线，若一个点在直线的一边，则return +1，否则return -1，请问H能够shatter这个吗？

不可以。多尝试几次便可以发现，无论如何，起码有以下这一种dichotomy是无法得到的：

将四个点从左上角开始顺时针命名为 $x_{1},x_{2},x_{3},x_{4}$ ，不难发现， $x_{1},x_{3}$ return +1， $x_{2},x_{4}$ return -1，是不会发生的。对于这个H， $m_{H}(4)=14$

显然，如果H能够shatter 一个大小为N的data set，那么可知 $m_{H}(N)=2^{N}$

换言之，H可以shatter $x_{1},x_{2},...,x_{N}$ $\Rightarrow$ $m_{H}(N)=2^{N}$

那么，另一个方向上，是不是 $m_{H}(N)$ $=2^{N}$ $\Rightarrow$ H能shatter任意 $x_{1},x_{2},...,x_{N}$ 呢？

我们来看一个例子。

Ex. input data set 为2D中的N个点；定义H为所有convex set，若一个点在一个convex set中，则return +1，否则return -1，请问H能够shatter这个吗？（convex set为一个这样的多边形：若一个多边形任意两个顶点之间的连线完全在这个多边形内，那么它就是一个convex set。总之理解起来只要知道这个形状总是凸出来，不是凹进去的就行了。）

这个例子中， $m_{H}(N)$ $=2^{N}$ 。为什么呢？假设这N个点都在某个圆的圆周上，那么是不是对于每一个dichotomy，我只要把我需要return +1的那些点作为顶点，连接起来，构成一个convex set，剩下的点就自然而然在这个convex set以外了，所以任何一个dichotomy我都可以从这个特定的圆上得到。然而，H能shatter任意 $x_{1},x_{2},...,x_{N}$ 吗？显然是不能的。如果我在这个平面上随机产生大量的点，现实中是几乎不可能出现能够产生所有dichotomy的情况的。而先前在求 $m_{H}(N)$ 时，我们考虑的是理想情况，求的是dichotomy数的最大值，所以即是我们知道一个H的Growth function已经等于其上限 $2^{N}$ ，我们无法判断对于某个特定的data set，这个H能不能够shatter。

那么，我们发现，尽管现在我们把一个无穷的范围缩小到了有限的 $2^{N}$ ，这个数字仍旧是大得可怕的。而且，让我们苦恼的是，如果我们观察Hoeffding’s Inequality，不难发现，RHS中，即使我们将大M替换成了 $2^{N}$ ，我们还是很难判断， $e^{-2\epsilon^2N}$ 到底能够有效地抵消 $2^{N}$ 增长地速度，从而使bound有效地收敛；换言之，我们仍旧无法判断Learning是不是feasible的。这时我们就需要break point来进一步帮助我们缩小范围了。

我们定义，如果任意一个大小为k的data set都不能被H shatter，我们就把k称作是H的break point。一般我们所指的都是最小的这样的k，因为显然如果任意大小为k的data set都不能被H shatter，那么任意大小为k+1的势必也不能被H shatter。

我们看先前的两个例子。

Ex. 定义H为一个平面中的所有直线，若一个点在直线的一边，则return +1，否则return -1。

先前的例子中我们已经看到，对于N=3时，Growth function的值为8， $m_{H}(N)=2^{N}$ ；N=4时，尝试一下便可知，Growth function的值为14， $m_{H}(N)$ $<2^{N}$ 。故对于这个H来说，break point k为4。

那么break point有什么用呢？其实，不难发现，对于一个H，break point如果存在（此处指break point是一个有限的数而不是无穷），那么 $m_{H}(N)$ $<2^{N}$ ；然后，经过一系列繁复的数学论证，我们可以得出一个结论，那就是如果break point存在， $m_{H}(N)$ 就是一个polynomial。此处省略数学论证的过程，如果有兴趣我可以再提供证明。那么我们费了半天功夫说明如果break point存在， $m_{H}(N)$ 就是一个polynomial有什么用呢？很简单，如果 $m_{H}(N)$ 是一个polynomial，那么我们就可以很肯定地把大M以某种方式替换成 $m_{H}(N)$ ，这样一来我们的Hoeffding’s Inequality和Generalizaiton Bound就明显可以很好地收敛只要N足够大，因为约束这个polynomial的是一个指数的函数，绝对上比polynomial要有效。换句话说，如果break point存在，我们就可以拍桌子说，Learning是可行的。

那么，VC Dimension是啥呢？我们定义，对于一个H，它的Vapnik-Chervonenkis Dimension为使得 $m_{H}(N)=2^{N}$ 的最大的N，记作 $d_{vc}(H)$ 。如果Growth function恒等于 $2^{N}$ ，那么 $d_{vc}(H)$ 为无穷。

其实，H的VC Dimension就是H的k-1，因为根据定义，对于 $N>d_{vc}$ ， $m_{H}(N)$ $<2^{N}$

更有用的是，VC Dimension就是我们先前所提到的那个polynomial的order，这一部分得需要略去的数学论证来得出，所以知道就行。

那么，实际上，通过数学论证，我们还可以把 $m_{H}(N)$ 进一步缩小，结论是：

$m_{H}(N)$ $\leq N^{d_{vc}}+1$ ，这可以通过induction来证明，也需要前面的数学论证为基础。

现在，再通过相当复杂的论证，我们就可以把先前的Generalization Bound在VC Dimension的基础上进一步约束，将大M替换为有限并有效的值。这里只讲一下结论，中间数学论证并不会影响逻辑上的理解。VC Generalization Bound:

$E_{out}(g) \leq E_{in}(g)$ $+(\frac{8}{N}ln$ $\frac{4m_{H}(2N)}{\delta}$ $)^{\frac{1}{2}}$

虽然是一个相当loose的bound，不信的话可以自己随意构想一个情况然后计算一下bound，但是起码现在我们就可以肯定，有理有据，证据确凿地说：Learning is feasible.

参考

Abu-Mostafa, Yaser S., Malik Magdon-Ismail, and Hsuan-Tien Lin. Learning from data: a short course. S. l.: AML, 2012. Print.

——————————————————————————————————————-

4/25

有位朋友对于以上提到的结论“如果break point存在， $m_{H}(N)$ 就是一个polynomial”的数学证明有所兴趣，在此特地补充一下证明过程。

要证明这个定理，我们主要用的是递归和归纳。

首先，我们定义： $B(N,k)$ 为在N个点上，使得这N个点的任意大小为k的子集都不能被shattered的最大的dichotomy的数量。

根据定义，我们可知，如果k是某一个的break point，那么 $m_{H}(N) \leq B(N,k)$ 。

那么我们求几个特殊情况下的 $B(N,k)$ 。

从k=1或者N=1开始，显然， , （k>1时）

现在我们观察 $N \geq2$ 以及 $k \geq 2$ 的情况。

对于这N个点，我们把它们记作( $x_{1},x_{2},...,x_{N-1}$ )。现在我们要把所有的dichotomy分类一下。其实，每一个dichotomy就是一个长度为N的tuple，其中每个元素都为+1或-1。那么，我们现在把这个tuple的位置用1到N来表示，然后把所有dichotomy分成三个组， $S_{1}$ , $S_{2}^{+}$ , $S_{2}^{-}$ 。怎么分呢？对于每个dichotomy所形成的tuple，我们先不看N号位上的元素。然后我们看前面N-1个位置的元素，如果我们发现有两个tuple，它们从1到N-1号位上所有的元素都一样，那么我们就把这两个tuple中，N号位上为+1的放在 $S_{2}^{+}$ ，N号位上为-1的放在 $S_{2}^{-}$ 。其余剩下的，也就是那些1到N-1号位上元素互相都不重复的tuple，放在 $S_{1}$ 。我们把 $S_{1}$ 的大小设为 $\alpha$ ，把 $S_{2}^{+}$ 的大小设为 $\beta$ ，显然 $S_{2}^{-}$ 的大小也是 $\beta$ ，因为这两个集合中的元素都是互相成对的，否则它们就会出现在 $S_{1}$ 里。 $\alpha+\beta$ 就是所有dichotomy的数量。对于每一对N和k，我们都可以把所产生的dichotomy这样来分类，也都能找到这样的 $\alpha$ 和 $\beta$ 使得 $B(N,k)=\alpha+2\beta$ 。

那么，在 $x_{1},x_{2},...,x_{N-1}$ 上，所能产生的dichotomy的数量就是 $\alpha+\beta$ 。

然后，因为在 $S_{2}^{+}$ 中， $x_{1},x_{2},...,x_{N-1}$ 中任意k-1个点都无法被 $S_{2}^{+}$ 中的dichotomy shatter（否则的话 $S_{2}^{+}$ 和 $S_{2}^{-}$ 就可以shatter一个大小为k的子集了）

所以， $\beta \leq B(N-1,k-1)$

这样，我们把上面的这两个不等式一合并，就有

$B(N,k) \leq B(N-1,k)+B(N-1,k-1)$

这个不等式是相当关键的。

现在我们要用这个结论来证明一个 lemma

Sauer’s Lemma: $B(N,k) \leq \sum_{i=0}^{k-1}$ $\left(\begin{array}{c}N\\ i\end{array}\right)$

证明过程如下：

首先，通过观察可知k=1或者N=1时这个lemma是对的。

然后，假定这个定理对于小于 $N_{0}$ 的所有N以及所有k都是正确的。

我们需要证明这个定理对于 $N=N_{0}+1$ 以及所有k也是正确的。

因为我们已知当k=1时，定理对于所有N都是正确的，我们只要关注 $k \leq 2$ 的情况。

$B(N_{0}+1,k) \leq$ $B(N_{0},k)+B(N_{0},k-1)$ $=\sum_{i=0}^{k-1}$ $\left(\begin{array}{c}N_{0}\\ i\end{array}\right)$ $+\sum_{i=0}^{k-2}$ $\left(\begin{array}{c}N_{0}\\ i\end{array}\right)$ $=1+\sum_{i=1}^{k-1}$ $\left(\begin{array}{c}N_{0}\\ i\end{array}\right)$ $+\sum_{i=1}^{k-1}$ $\left(\begin{array}{c}N_{0}\\ i-1\end{array}\right)$ $=1+\sum_{i=1}^{k-1}$ $\left[\left(\begin{array}{c}N_{0}\\ i\end{array}\right)+\left(\begin{array}{c}N_{0}\\ i-1\end{array}\right))\right]$ $=1+\sum_{i=1}^{k-1}\left(\begin{array}{c}N_{0}+1\\ i\end{array}\right) = \sum_{i=0}^{k-1}\left(\begin{array}{c}N_{0}+1\\ i\end{array}\right)$

Q.E.D

所以，我们可知，如果 $m_{H}(k)<2^k$ ，那么 $m_{H}(N) \leq \sum_{i=0}^{k-1} \left(\begin{array}{c}N\\ i\end{array}\right)$ ，而且RHS的最高次项的次数为k-1。
赵印初入职场
0
举报回复
理由

举报取消

简单通俗的说。

VC维是模型的复杂程度，模型假设空间越大，VC维越高。

shatter和break point是VC维理论中的概念。shatter是指模型假设把数据打碎了，也就是区分开了。而break point是指当模型复杂度变的足够高了后，可以把数据打的足够散的一个数学临界点。

更重要的是，VC维的实践意义是给机器学习可学性提供了理论支撑。

1. 测试集合的loss是否和训练集合的loss接近？VC维越小，理论越接近。

2. 训练集合的loss是否足够小？VC维越大，loss理论越小。

一般工业实践中通过引入正则对模型复杂度(VC维)进行控制，平衡这两个问题的矛盾。

如果想深入理解，推荐看看腾讯广点通团队的这个技术博客：VC维的来龙去脉 | 火光摇曳。个人认为总结的很好。

找回密码

如何通俗的理解机器学习中的VC维、shatter和break point？

发起人：Robot 管理大师

回复 ( 3 )

我来回答

帐户注册

登录

找回密码

如何通俗的理解机器学习中的VC维、shatter和break point？

发起人：Robot 管理大师

回复 ( 3 )

我来回答