2
$\begingroup$

I would answer that it is $\infty$, but I have a gut feeling this may not be the correct answer...

May I present my proof attempt that it is indeed $\infty$, so that you can clear any misconceptions I have (if there are any)?

To my understanding, let $H$ be the family of all 1-NN classifiers. $VCdim(H)\geq m$ if there exists a set $X$ of $m$ points that is shattered by $H$ - that is, if for every possible classification of elements in $X$, there is a classifier $h\in H$ which yields this classification.

We will show that for each finite $m$ every set of $m$ points is shattered by $H$.

Let $X$ be a set of $m$ points. Let $d$ be the minimum distance between any two points in $X$. ($d>0$, because otherwise the distance between some two points would be $0$, so this would be only one distinct point, so $X$ would be a set of at most $m-1$ points and not of $m$ points).

Let $C(X)\in\lbrace0,1\rbrace^m$ be an arbitrary classification of elements of $X$. We will construct a classifier $h\in H$ that yields this classification. This will be the classifier trained on $X$. For every point $x\in X$, a 1-NN classifier trained on $X$ will yield the classification $C(x)$, since the fact that $d>0$ guarantees us there will be no ties in voting.

Since for each finite $m$ we have $VCdim(H)\geq m$ we know that $VCdim(H)=\infty$.

Is the above proof correct? Is the VC dimension of 1-nearest-neighbours really $\infty$?

$\endgroup$
1
  • $\begingroup$ Yes you are right. VC dimension of kNN with k=1 is infinite. See this : quora.com/… $\endgroup$ Jun 23 '19 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.