View Single Post
  #11  
Old 04-29-2013, 04:06 AM
MindExodus MindExodus is offline
Junior Member
 
Join Date: Apr 2013
Posts: 3
Default Re: Q10 higher bound

sry about didn't notice that requirement
but the key to this problem is the same:

let me just put another example:

just think of H1 and H2 on \{x_1, x_2, x_3\}
H1:
\{x_1 = 1, x_2 = 1, x_3 = 1\}
\{x_1 = 1, x_2 = 1, x_3 = -1\}
\{x_1 = 1, x_2 = -1, x_3 = 1\}
\{x_1 = -1, x_2 = 1, x_3 = 1\}

H2:
\{x_1 = -1, x_2 = -1, x_3 = -1\}
\{x_1 = -1, x_2 = -1, x_3 = 1\}
\{x_1 = -1, x_2 = 1, x_3 = -1\}
\{x_1 = 1, x_2 = -1, x_3 = -1\}

thus:
d_{H1} = 1 , d_{H2} = 1
and \{H_1 \cup H_2\} can shatter all 3 point


d_{H_1 \cup H_2} = 3

Quote:
Originally Posted by jforbes View Post
Bad news: the problem requires that each hypothesis set has a finite positive VC dimension, so this particular example does not guarantee that the maximum is greater than the sum of the VC dimension for the case we're being asked about.

I'm still on the fence for this question - my first attempts at constructing an example similar to this where each hypothesis set had a VC dimension of 1 failed to shatter 3 points, but I'm not 100% sure yet that I can't get it to work.
Reply With Quote