示例 3.12 超平面 一般的d

更一般地，在 ${\mathbb{R}}^d$ 中，

• 我们通过从一个 $d+1$ 点的集合开始来推导下界，其中
  • ${\mathbf{x}}_0$ 设为原点，
  • 并定义 ${\mathbf{x}}_i$（对于 $i\in \{1,\dots ,d\}$）为
    • 第 $i$ 个坐标为 1
    • 而所有其他坐标为 0 的点。
• 设 $y_0,y_1,\dots ,y_d\in \{-1,+1\}$ 是 ${\mathbf{x}}_0,{\mathbf{x}}_1,\dots ,{\mathbf{x}}_d$ 的任意标签集合。
• 设 $\mathbf{w}$ 是一个向量，其第 $i$ 个坐标为 $y_i$。
• 那么，由超平面方程 $\mathbf{w}\cdot \mathbf{x}+\frac{y_0}{2}=0$ 定义的分类器打碎了 ${\mathbf{x}}_0,{\mathbf{x}}_1,\dots ,{\mathbf{x}}_d$，
• 因为对于任何 $i\in \{0,\dots ,d\}$， \operatorname{sgn}\left( {\mathbf{w} \cdot {\mathbf{x}}_{i} + \frac{{y}_{0}}{2}}\right) = \operatorname{sgn}\left( {{y}_{i} + \frac{{y}_{0}}{2}}\right) = {y}_{i}. \tag{3.25}

为了得到一个上界，

• 只需证明没有 $d+2$ 个点的集合可以被半空间打碎。
• 现在，设 $\mathcal{X}$ 是一个包含 $d+2$ 个点的集合。
• 根据 定理 3.13 Radon 定理，
  • 它可以被划分为两个集合 ${\mathcal{X}}_1$ 和 ${\mathcal{X}}_2$，
    • 使得它们的凸包相交。
• 观察到，当两个点集 ${\mathcal{X}}_1$ 和 ${\mathcal{X}}_2$ 被超平面分开时，
  • 它们的凸包也被该超平面分开。
• 因此，${\mathcal{X}}_1$ 和 ${\mathcal{X}}_2$ 不能被超平面分开，
  • 因此 $x$ 不被打碎。
• 结合我们的下界和上界，我们已经证明了 $\mathrm{VCdim}\left(\text{超平面在}{\mathbb{R}}^d\right)=d+1$