数据挖掘 - 为什么在各种假设示例的 VC 维度证明中需要下界？ - 吾爱随笔录

为什么在各种假设示例的 VC 维度证明中需要下界？

数据挖掘机器学习 pac学习 vc理论

2022-02-22 17:24:53

在“机器学习基础”一书中，有证明各种假设的 VC 维度的示例，例如轴对齐的矩形、凸多边形、正弦函数、超平面等。

所有证明首先得出一个下限，然后显示一个上限。但是，既然 VC 维的定义只关心可以被假设集粉碎的“最大”集，为什么不直接推导出上限呢？由于所有示例都以与上限匹配的下限结束，因此在尝试显示上限时下限是否有助于/有用设置目标？ $\mathcal{H}$

参考：来自本书pdf版本的第41页 https://pdfs.semanticscholar.org/e923/9469aba4bccf3e36d1c27894721e8dbefc44.pdf

1个回答

让我们使用书中的引语。

为了给出一个上限，我们需要证明没有任何基数为可以被 $S$ $d + 1$ $H$

通过这样做，我们证明了，但这并不一定意味着。例如，我们可能会寻找更容易证明的失败，例如具有个成员的集合，因此证明，尽管我们知道 . 所以： $\text{VCdim}(H) < d+1$ $\text{VCdim}(H) = d$ $2d+1$ $\text{VCdim}(H) < 2d+1$ $\text{VCdim}(H) = d$

为了给出的下界，足以证明基数可以被 $d$ $\text{VCdim}(H)$ $S$ $d$ $H$

我们还需要证明下界以证明，这意味着。最后一个等式意味着对于每个大小到，可以粉碎至少一个具有该大小的 $d \le \text{VCdim}(H) < d+1$ $\text{VCdim}(H) = d$ $1$ $d$ $H$ $S$

请注意，对于示例，我们将无法证明，因此，因此我们必须尝试证明更小的（可能更难证明）上限。 $2d+1$ $2d \le \text{VCdim}(H)$ $\text{VCdim}(H) \neq 2d$ $d+1$

其它你可能感兴趣的问题

上一篇如何从图中获取变量值？下一篇PNY NVIDIA Quadro RTX 4000 是用于 Linux 机器学习的优秀 GPU 吗？