kernel - SVM：VC维度和内核维度数之间的关系

Question

我正在使用 Thorsten Joachims 的 SVM-light 探索 SVM 主题。

现在根据一些介绍文件：

^{“R n}中定向超平面集的 VC 维数为 n+1 [...]”

“当 C = inf 时，最佳超平面将是完全分离数据的超平面（假设存在）[...]”

我准备了一个二维线性可分数据集，并想看看我们从很多插图中知道的 2d 硬边距分类器。

所以我选择了以下参数：

我得到了 3 个支持向量，这很好，但估计的 VC 维数超过 10,000。

现在我想知道如果内核只是二维的，是否有可能有这么高的 VCdim？

score 3 · Accepted Answer

您似乎在这里混淆了几件事：

多项式核不是“二维核”，多项式核映射到大致 O(m ^d ) 维空间
经验 VC 维度不是真正的 VC 维度，真正的 VC 维度是分析对象，不能直接“从数据”计算，它需要严格的证明，其中一个（现有的几个）说对于 n 维空间，线性分类器的 VC 维数是 n+1，无论你如何“获得”这个空间，它都成立。
支持向量的数量与模型的泛化能力有关，VC 维度也是如此。不幸的是，支持向量的数量和数据的 VC 维度之间没有简单的“一对一”依赖关系。事实上，据我所知，SVM模型的VC维数没有已知的证明（我们知道，它是一个容差分类器，应该有更低的VC维数，但它远不是一个维数证明）。

score 1 · Accepted Answer

VC 维度不映射到给定解决方案的 SV 数量。

VC 维度是模型可以针对与这些点关联的标签的任何组合完美粉碎的数据集样本的最大数量。另一方面，支持向量是定义超平面的点。

编辑：

根据您的评论，我正在扩展我的答案。

首先，当你这样说时：

“当 C = inf 时，最佳超平面将是完全分离数据的超平面（假设存在）[...]”

这并不意味着 C 和 VC 维度之间存在直接关系（正如您在说 C=999 会产生 10000 的 VC 维度时所建议的那样）。这意味着使用 C = inf 您将强制执行所有约束并因此生成硬边距模型（一个完全分离数据的超平面）

“当应用映射到二维的多项式内核时，R^n 中定向超平面集的 VC 维是否为 n+1 的事实是否仍然成立”

这在特征空间中是正确的，但请记住，输入空间中的决策边界将不再是超平面，实际上将是非线性的。

“多项式内核 (a*b+c)^d 与 d = 2”...“如果内核只是二维的？”

该内核不是双向的，它会根据其他参数进行不同的映射。

2 回答 2