机器学习和数据挖掘（7）：VC维

本文主要是介绍机器学习和数据挖掘（7）：VC维，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

VC维

回顾与说明

如果一个假设空间存在突破点，则一定存在成长函数$m_{\mathcal H}(N)$被某个上限函数$B(N,k)$所约束，而上限函数等于一个组合的求和形式$\sum_{i=0}^{k-1}C_N^i$，易知该形式的最高次项是$N^{k-1}$。图左和右分别是以上限函数为上限的情况和以为$N_{k-1}$上限的情况。

可以看得出来：

$\begin{align} m_{\mathcal H}(N)\leq B(N,k)=\sum_{i=0}^{k-1}C_N^i\leq N^{k-1} \end{align}$

再结合之前的霍夫丁不等式可得：

$$P[|E_{in}(g)-E_{out}(g)|>\epsilon]\leq 4m_{\mathcal H}(2N)exp(-{1\over 8}\epsilon^2N)\leq^{if\ k\ exists} 4N^{k-1}exp(-{1\over 8}\epsilon^2N)$$

该公式的意义是在输入样本N很大时，VC限制一定成立，同时等式的左边也一定会在$k\geq 3$的情况下被$N^{k-1}$所约束（注意这里的条件没有了，原因很简单，VC限制是样本N很大的情况下产生的，因此一定满足的条件），而在$k<3$的情况下有其他的限制可以满足（比如前几章提到的如正射线之类的分类不需要多项式形式的限制也可以约束住成长函数）。

至此得知，满足以下几个条件，机器便可以学习：

1. 假设空间的成长函数有一个突破点k；
2. 输入数据样本N足够的大；

同时也通过VC限制得出了结论

1. $E_{in}\approx E_{out}$
2. 通过算法可以找到一个假设使得$E_{in}\approx 0$

VC维的定义

VC维（VC dimension）的定义是：最大的一个不是突破点的数，或者说，最大的一个数使得存在小于等于这些数的采样可以找到完全二分类的。

VC维是假设空间的一个性质，数据样本可以被完全二分的最大值。用$d_{vc}$作为VC维的数学符号，假如突破点存在的话，即最小的突破点减去1就是V维；如果不存在突破点的话，则VC维为无限大。

若输入数据量$N$小于VC维，则有可能输入数据D会被完全的二分类（这里不是一定，VC维只能保证存在）。

如果输入数据量N（或者用k表示）大于VC维，则有k一定是假设空间$\mathcal H$的突破点。

使用VC维$d_{vc}$对公式(1)进行重写，在$N\geq 2，d_{vc}\geq 2$时，可得：

$$m_{\mathcal H}(N)\leq \sum_{i=0}^{d_{vc}}C_N^i \leq N^{d_{vc}}$$

对第五章中提到的几种分类，使用VC维取代突破点，表示VC维与成长函数的关系，如下表所示。

正射线
一维空间的感知器
间隔为正的分类
凸图形分类
二维平面的感知器		在 时

对上述可学习条件1中假设空间可以重新定义，即，假设空间需要具备有限的VC维。

一个有限的VC维总是能够保证寻找到的近似假设

这篇关于机器学习和数据挖掘（7）：VC维的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---