数据挖掘 - 反驳或证明声称如果 VCdim 为“n”，那么一组较小的尺寸可能不会被粉碎 - 吾爱随笔录

反驳或证明声称如果 VCdim 为“n”，那么一组较小的尺寸可能不会被粉碎

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

2022-02-20 09:28:16

今天在讲座中，讲师说了一些我觉得很奇怪的话，我听了觉得很不方便：他声称，如果某个假设类的最大 VCdim 是 $n\in\mathbb N$ , 那么可能有一些 $i<n$ 这样对于每个大小为 i 的子集 C，子集 C 都不会破碎。他的说法是真的吗？我认为我们可以采取一些大小的子集 $i,\forall i\in [n]$ 集合 C* 满足以下情况的条件 $|C|=n$ ，它们也会破碎。我错过了什么吗？

1个回答

我同意，书面声明是不正确的。如果 $C^*$ 被粉碎 $\mathcal{H}$ ，和 $C\subseteq C^*$ ，然后 $C$ 也被粉碎 $\mathcal{H}$ ; 可能过于迂腐：

对于每个 $B\subseteq C$ , 因为那时也 $B\subseteq C^*$ , 我们有一个 $H\in\mathcal{H}$ 这样 $C^*\cap H=B$ . 请注意，这意味着 $B\subseteq H$ . 现在， $C\subseteq C^*$ 暗示 $C\cap H\subseteq C^*\cap H$ ，所以我们有 $C\cap H\subseteq B$ . 并拥有两者 $B\subseteq C$ 和 $B\subseteq H$ 暗示 $B\subseteq C\cap H$ . 所以 $B=C\cap H$ .

其它你可能感兴趣的问题

上一篇为什么 Pytorch 中的 batchnorm1d 使用以下示例（2 行代码）计算 0？下一篇如何对“名称”进行编码，以便相似的名称由靠近 n 维平面的向量表示？