vc获取n卡编号_VC维及结构风险最小化

一、VC维

我们以二分类为例来说明此概念。在此之前，我们先来解释如下四个概念(都很简单，别怕)：增长函数/growth function、对分/dichotomy、打散/shattering和断点/break point。然后再来说明什么是VC维。

定义两个符号：

• 假设空间
  ，其中h代表一个具体的函数或者模型。
• 数据集

1、增长函数：假设空间H对D中m个元素能进行标记的最大可能结果数。例如m=2时，其增长函数值为4。增长函数代表假设空间的表达能力，值越大代表H复杂度越高。H中元素多少跟增长函数没有直接关系，如果D中有m个元素，则H(D)的增长函数值最大不超过

。

2、对分：一个对分表示对D中元素的一种标记结果。H(D) 表示假设空间对D上的所有对分。

3、打散：假设空间能实现对数据集D的所有对分，即增长函数=

。不能打散的情况常见的是：在二维平面上线性分类器并不总能对4个样本点进行标记。如下图：

4、断点：我们把第一个不能被打散的m值叫做断点。m是D中元数个数。

5、[VC维]：假设空间H的VC维是指能被H打散的最大数据集的模。也即

。如：二维平面上线性分类器的VC维=3。

二、损失函数、经验风险、期望风险、结构风险

1、损失函数：假设我们有一个样本

，f是一个决策函数用来进行预测。损失函数就是用来表达真实值与预测值之间的差距，形如：

。此值越小代表模型预测的越准确。

2、经验风险：是对训练集中所有样本损失的平均化，经验风险越小说明对训练集拟合的越好，但是对于测试集是未知的。具体形式为：

。

3、期望风险：是一个全局概念，用来衡量对全部数据(训练集+测试集)的预测能力。假设X和Y的联合分布为

，则期望风险的定义如下：

但是联合分布一般很难获取，因此这个全局最优问题会采用局部最优的思路去解决，从而引入了结构风险最小化。

4、结构风险最小化

首先说明一下，(针对指示函数集)经验风险和期望风险之间的关系为：

，此公式的简化版为：

。其中h是函数集的VC维，n代表样本数。前述公式说明：期望风险由两部分决定，即经验风险和置信范围(与函数集的VC维和样本数有关)。传统机器学习算法中普通采用的经验风险最小化原则在样本数目有限时是不合理的，可能会出现过拟合现象。因为函数集的VC维越高则说明模型越复杂，就会导致置信范围较大，从而导致期望风险与经验风险之间有较大gap。因此我们不仅要经验风险小，而且要VC维尽量小以减小置信范围，从而减小期望风险，这样才能对未见样本有较好的泛化能力。

结构风险最小化：把函数集构造成一个函数子集序列，使各个子集按照VC维的大小排列。在每个子集中寻找最小经验风险，然后在子集间折衷考虑经验风险和置信范围使期望风险最小，也称为SRM准则。

补充：经验风险与结构风险都是作用于训练集来评估loss的，但结构风险一定程度上反映了期望风险的上界。而我们平常在测试集上度量的指标表现是对泛化能力的一种具体计算。

[参考资料]

1、如何通俗的理解机器学习中的VC维、shatter和break point？:https://www.zhihu.com/question/38607822/answer/149407083。

2、结构风险最小化：https://www.iteye.com/blog/xiaoxia001-1163389。

3、统计机器学习，李航。

4、Structural Risk Minimization： https://www.sciencedirect.com/topics/mathematics/structural-risk-minimization。