• 设H表示Rn中与坐标轴平行的矩形集合。每个矩形定义了一个二元分类器，将矩形内的点标记为+1，矩形外的点标记为-1。每个矩形由每个维度1≤i≤n上的区间[ai,bi]定义。一个点x=(x1,…,xn)∈Rn在矩形内当且仅当对于所有1≤i≤n，ai ≤xi ≤bi。H的VC维度是多少？请证明你的答案。

这是使用LaTex输入的，这是原文。

据我所知，VC维度是假设集H可以粉碎的样本大小d的最大整数，但在这种情况下，如果H是矩形，我们如何计算这个值呢？

回答：

对于Rn中的与坐标轴对齐的矩形，VC维度至少为2*n。

首先考虑R1中的矩形，这实际上只是x1轴上的一对最小/最大值(a1, b1)（不是真正的矩形）。这对值的VC维度为2，因为对于R1中的任意两个点，你可以设置(a1, b1)，使得这两个点中的一个、两个或都不在它们之间。但当你沿该轴添加第三个点时，你无法在不包括中间点的同时将两个外点包含在(a1, b1)范围内。

为了更容易可视化，假设这两个点分别位于x1 = -2和x1 = 2。你可以通过定义矩形边界(a1, b1)来粉碎这个集合：

(-3, 3) -> 两个点都被包含(-3, 1) -> 仅第一个点被包含(-1, 3) -> 仅第二个点被包含(-1, 1) -> 两个点都不被包含

现在假设你增加一个维度，使你的空间位于R2（即，现在是一个真正的矩形区域）。再添加两个点，并将新点的x1坐标设为0，这样它们在第一个维度上（对于上述定义的矩形）总是被包含，并将新点的x2坐标分别设为-2和2。同时，将前两个点的x2坐标设为0。

当你将(a1, b1, a2, b2)设为(-3, 3, -3, 3)时，你将包含所有4个点。你可以通过简单地将4个边界之一的绝对值从3减到1来排除任何点。由于你可以通过更改R2矩形的相应边界来包含4个点的任何子集，因此R2矩形的VC维度至少为4。

显然，你可以对任意数量的维度重复此过程。每次你添加一个新的维度xi时，将所有点的xi坐标设为0，除了你为该维度添加的两个新点（它们将分别位于xi = -2和xi = 2）。

由于你可以为每个维度粉碎2个额外的点，因此对于Rn中的与坐标轴对齐的矩形，VC维度将至少为2*n。