LFD Book Forum - View Single Post

OlivierB · #6 04-28-2013, 03:20 PM

@marek, Thanks for your contribution.
Let me try and rephrase, not adding much.

For a hypothesis set H with VD dimension d, we have
$m_{H}(N)\le B(N, d+1)=\sum_{i=0}^d \left(\begin{array}{c}N\\ i\end{array}\right)$

The second equality is the result of 2 inequalities in opposite direction. In class, we saw '≤' and '≥' is the subject of problem 2.4 in the book.

Let 2 hypothesis sets $H_{1}$ and $H_{2}$ with VC dimensions respectively $d_{1}$ and $d_{2}$ .

We can construct two disjoint $H'_{1}$ and $H'_{2}$ putting the intersection of both with one of them only.
$H'_{1}=H_{1}$
$H'_{2}=H_{2}-\bigcap(H_{1}, H_{2})$

The VC dimension of $H'_{1}$ is $d_{1}$
The VC dimension of $H'_{2}$ is $d'_{2}\le d_{2}$

Let H be the union of these hypothesis sets:
$H=\bigcup(H_{1}, H_{2})=\bigcup(H'_{1}, H'_{2})$
Let $N=d_{1}+d_{2}+1$

Now in order to try and determine the VC dimension of H, let us compute a higher bound of $m_{H}(N)$ :

$m_{H}(N)=m_{H'_1}(N)+m_{H'_2}(N)\le\sum_{i=0}^{d_1}\left(\begin{array}{c}N\\ i\end{array}\right)+\sum_{i=0}^{d'_2}\left(\begin{array}{c}N\\ i\end{array}\right)\le\sum_{i=0}^{d_1}\left(\begin{array}{c}N\\ i\end{array}\right)+\sum_{i=0}^{d_2}\left(\begin{array}{c}N\\ i\end{array}\right)$

which we can simplify:

$\sum_{i=0}^{d_1}\left(\begin{array}{c}N\\ i\end{array}\right)+\sum_{i=0}^{d_2}\left(\begin{array}{c}N\\ i\end{array}\right)=\sum_{i=0}^{d_1}\left(\begin{array}{c}N\\ i\end{array}\right)+\sum_{i=N-d_2}^{N}\left(\begin{array}{c}N\\ i\end{array}\right)=\sum_{i=0}^{d_1}\left(\begin{array}{c}N\\ i\end{array}\right)+\sum_{i=d_1+1}^{N}\left(\begin{array}{c}N\\ i\end{array}\right)$

For $m_{H}(N)=2^N$ to be true i.e. for H to shatter N, all inequalities must be equalities.
In other words, we must have:
1/ The growth functions of $H_{1}$ and $H_{2}$ must be exactly

and

2/ Removing the intersection of $H_{1}$ and $H_{2}$ from $H_{2}$ does not decrease the VC dimension of $H_{2}$ . If the intersection is empty then this condition holds.

If these 2 requirements are not contradictory (which seems plausible but I cannot prove - neither can I visualize with an example), then the VC dimension of

is at least

.

Now unless there is a mistake in the reasoning, the question is: Can these requirements be met ? Ideally via an example, because beyond the abstract equations, I would really like to 'visualize' a case where these inequalities are 'saturated'.