示例 3.14 轴对齐矩形

我们首先展示

• VC 维度至少为 4，
  • 通过考虑四个点形成的菱形模式。
• 显然，所有 16 种二分法都可以被实现，
  • 其中一些如图 3.3(a) 所示。

Figure 3.3 轴对齐矩形的 VC 维度。

1. 四个点形成的菱形模式的可实现二分法示例。
2. 如果内部点和其余点的标签相反，则没有五个点的样本可以被实现。

相反，对于任意五个不同的点，

• 如果我们构造包含这些点的最小轴对齐矩形，
  • 那么其中一个点会位于该矩形的内部。
• 假设我们
  • 给这个内部点分配一个负标签，
  • 给其余四个点分配正标签，
  • 如图 3.3(b) 所示。
• 没有任何轴对齐的矩形可以实现这种标记。
• 因此，任何五个不同的点集都无法被打散，故 $\mathrm{VCdim}\left(\text{轴对齐矩形}\right)=4$