证明最近邻分类器的假设空间VC维为无穷大.

Explaining 1-NN VC Dimension

The user is asking about proving the VC dimension of a 1-nearest neighbor classifier. The known theoretical result says that it can shatter any finite set of points in R^d given a small enough tolerance region and appropriate labels. To prove this, we assign labels arbitrarily to any n points. By using the 1-NN classifier with a training set that matches these labels, it will perfectly classify them, showing that the VC dimension is infinite.

Proving Infinite VC Dimension for 1-NN

To prove the 1-NN classifier has an infinite VC dimension, we show that for any size m, we can find m points that can be shattered. Consider a set of points S where each point is at least 2γ apart. We can create a classifier where the decision boundary depends only on the nearest neighbor. The classifier’s predictions are perfect because each point can be its own nearest neighbor, defined by its label. Thus, for every possible labeling, the classifier performs correctly, which demonstrates an infinite VC dimension.

Thought for 19 seconds

要点回顾

VC 维（Vapnik-Chervonenkis dimension） 是指：存在大小为 m 的样本集能被假设空间 H 完全打散（shatter），且不存在大小为 m+1 的样本集能被打散，则 VC(H)=m。
若对每一个正整数 m 都能找到可被打散的 m 个点，那么 VC(H)=∞。

1. 定义最近邻假设空间 H

给定一个度量空间 $(\mathcal{X},d)$ （下面可取 $\mathbb{R}^d$ 与欧氏距离），
对任何有限标注训练集

S=\{(x_1,y_1),\dots,(x_n,y_n)\},\qquad x_i\in\mathcal X,\;y_i\in\{0,1\},

定义1-NN 分类器

h_S(x)= y_{i^*},\quad i^*=\arg\!\min_{1\le i\le n} d(x,x_i),

若有平局，可规定任一确定的破局规则（对我们的证明无影响）。
把所有这样的 $h_S$ 收集起来，就得到假设空间 H。

2. 构造可被打散的任意大小样本集

给定任意正整数 $m$ ，构造互不相同且彼此间距大于 0 的点

\mathcal{C}_m=\{x_1,\dots,x_m\}\subset\mathcal{X}.

最直观的做法：令 $x_i=(i,0,\dots,0)$ ，点与点的距离等于 $|i-j|$ >0；
也可以在单位圆内取任意互不相邻的小球中心，只要保证 每个点到自身的距离 0 与 到其它点的距离 >0 即可。

3. 任意标注均可实现

取这 $m$ 个点的任意标签向量 $(y_1,\dots,y_m)\in\{0,1\}^m$ 。
构造训练集 $S=\{(x_i,y_i)\}_{i=1}^m$ 。
考察诱导出的 1-NN 分类器 $h_S$ 。

因为

d(x_i,x_i)=0 < d(x_i,x_j)\quad (j\neq i),

对每个 $x_i$ 来说 它自身就是唯一最近邻，于是

h_S(x_i)=y_i,\quad i=1,\dots,m.

换言之，不论怎样给 $\mathcal{C}_m$ 标签，都存在 H 中的某个假设恰好实现这些标签。

4. 推论：VC 维为无穷大

上述步骤对任何正整数 $m$ 都成立 ⇒ 对每个 $m$ 都能找到大小为 $m$ 的集合被 H 打散；
因此 VC(H) 不受上界约束，记为 $\operatorname{VC}(H)=\infty$ 。

备注与扩展

k-NN（固定有限 k） 的假设空间同样 VC 维无限，只需把每个点复制 k - 1 个靠得足够近的同标签伪点，使得目标点的 k 个最近邻仍由其自身阵营构成。
证明并不依赖于欧氏空间的维数，只要求度量满足 $d(x,x)=0<d(x,y)\;(x\neq y)$ 。
该结论说明最近邻方法的“表面”模型复杂度极高；其实际泛化能力更多依赖于平滑的度量结构、样本量以及留出集验证等技巧，而非传统 VC 理论能充分解释。

这样就完成了“最近邻分类器假设空间 VC 维为无穷大”的证明。

证明最近邻分类器的假设空间VC维为无穷大.

Pregunta

Pensamiento