2
$\begingroup$

I'm reading van der Vaart's "Asymptotic statistics" and on page 275 the author introduces the concepts of Vapnik-Červonenkis (VC) classes of sets and functions and states a proposition which I can't prove. I'll write the definitions:

A collection $\mathcal{C}$ of subsets of the set $\mathcal{X}$ is said to pick out a certain subset $A$ of the finite set $\{x_1,\ldots,x_n\}\subset\mathcal{X}$ if it can be written as $A=\{x_1,\ldots,x_n\}\cap C$ for some $C\in\mathcal{C}$.

The collection $\mathcal{C}$ is said to shatter $\{x_1,\ldots,x_n\}$ if $\mathcal{C}$ picks out each of its $2^n$ subsets.

The VC index $V(\mathcal{C})$ of $\mathcal{C}$ is the smallest $n$ for which no set of size $n$ is shattered by $\mathcal{C}$. A collection of sets is called a VC class if its VC index is finite.

A collection of functions $\mathcal{F}:=\{f:\mathcal{X}\to\mathbb{R}\}$ is said to be a VC class of functions if the collection of all subgraphs $\{(x,t):f(x)<t\}$, if $f$ ranges over $\mathcal{F}$, forms a VC class of sets in $\mathcal{X}\times\mathbb{R}$.

Then goes a proposition: A collection of sets $C$ is a VC class of sets if and only if the collection of corresponding indicator functions $1_C$ is a VC class of functions.

It is said to be not difficult to see but I got stuck trying to prove it. Say $V(\mathcal{C})=n$. For $C\in\mathcal{C}$ denote $I_C:=\{(x,t)\subset\mathcal{X}\times\mathbb{R}:1_C(x)<t\}$ and $\mathcal{C}':=\{I_C:C\in\mathcal{C}\}$. My guess is that $V(\mathcal{C}')$ should also be $n$.

$\endgroup$

1 Answer 1

0
$\begingroup$

I think I figured it out. Indeed, $V(\mathcal{C}')\leq n$. To see this let $$\widetilde{V}:=\{(x_1,t_1),\ldots,(x_n,t_n)\}\subset X\times\mathbb{R}.$$ Suppose there exists an $i\in\{1,\ldots,n\}$ such that $t_i>1$. Then $(x_i,t_i)\notin I_C$ for all $C\in\mathcal{C}$, thus $\mathcal{C}'$ doesn't pick out $\{(x_i,t_i)\}$ and therefore does not shatter $\widetilde{V}$. If there exists an $i\in\{1,\ldots,n\}$ such that $t_i\leq 0$ then $(x_i,t_i)\in I_C$ for all $C\in\mathcal{C}$. But in this case setting $j=\{1,\ldots,n\}\backslash\{i\}$ results in $\{(x_j,t_j)\}\neq \widetilde{V}\cap I_C$ for all $C\in\mathcal{C}$. Therefore, $\mathcal{C}'$ doesn't pick out $\{(x_j,t_j)\}$ and consequently doesn't shatter $\widetilde{V}$. We will further assume that $t_i\in(0,1]$ for all $i\in\{1,\ldots,n\}$.

Since $V(\mathcal{C})=n$ there exists a subset $A$ of $V:=\{x_1,\ldots,x_n\}$, $A:=\{x_i:i\in T\subset\{1,\ldots,n\}\}$ such that $\mathcal{C}$ doesn't pick out $A$, i.e. $A\neq V\cap C$ for all $C\in\mathcal{C}$. Denote $\widetilde{A}:=\{(x_i,t_i):i\in T\subset\{1,\ldots,n\}\}$. Let $C\in\mathcal{C}$. Then $A\neq V\cap C$ and this means that:

  1. there exists $i\in\{1,\ldots,n\}$ such that $x_i\in A\backslash C$, or
  2. there exists $i\in\{1,\ldots,n\}$ such that $x_i\in C\backslash A$.

In the first case, from $t_i>0$ it follows that $(x_i,t_i)\notin I_C$, therefore $\widetilde{A}\neq \widetilde{V}\cap I_C$. In the second case $(x_i,t_i)\in I_C$, thus again $\widetilde{A}\neq \widetilde{V}\cap I_C$. Since $C$ is arbitrary $\widetilde{A}\neq \widetilde{V}\cap I_C$ for all $C\in\mathcal{C}$, i.e. $\mathcal{C}'$ doesn't pick out $\widetilde{A}$ and consequently doesn't shatter $\widetilde{V}$.

Suppose $V(\mathcal{C}')=n$. We will show that $V(\mathcal{C})\leq n$. Let $\{x_1,\ldots,x_n\}\subset X$. Denote $a:=1/2$. By $V(\mathcal{C}')=n$, the set $\{(x_1,a),\ldots,(x_n,a)\}$ has a subset $\{(x_i,a):i\in T\}$, $T\subset\{1,\ldots,n\}$, such that \begin{align*} \{(x_i,a):i\in T\}\neq \{(x_1,a),\ldots,(x_n,a)\}\cap I_C,\ \forall C\in\mathcal{C}. \end{align*} Let $C\in\mathcal{C}$. Then

  1. there exists $i\in T$ such that $(x_i,a)\in \{(x_i,a):i\in T\}\backslash I_C$, or
  2. there exists $i\in\{1,\ldots,n\}\backslash T$ such that $(x_i,a)\in I_C$.

In the first case $(x_i,a)\notin I_C$, which can only be true when $x_i\notin C$, therefore $\{x_i:i\in T\}\neq \{x_1,\ldots,x_n\}\cap C$. In the second case, from $(x_i,a)\in I_C$ it follows that $x_i\in C$, however, by the choice of $i$, $x_i\notin\{x_i:i\in T\}$, therefore $\{x_i:i\in T\}\neq \{x_1,\ldots,x_n\}\cap C$. Since $C$ is arbitrary, $\{x_i:i\in T\}\neq \{x_1,\ldots,x_n\}\cap C$ for all $C\in\mathcal{C}$, i.e. $\mathcal{C}$ doesn't pick out $\{x_i:i\in T\}$ and consequently doesn't shatter $\{x_1,\ldots,x_n\}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .