View Single Post
  #13  
Old 04-29-2013, 05:44 PM
MindExodus MindExodus is offline
Junior Member
 
Join Date: Apr 2013
Posts: 3
Default Re: Q10 higher bound

And this method can be generalizes!!

for H_1, H_2 with VC dimension d_1, d_2

H1: hypothesis over \{x_1, x_2, ... , x_{d1+d2-1}\}
mapping these point to cases that at most d_1 points to +1 and other points to -1

H2: hypothesis over \{x_1, x_2, ... , x_{d1+d2-1}\}
mapping these point to cases that at most d_2 points to -1 and other points to +1
so there is at least d_1 + 1 +1 and other points to -1


easy to prove that H_1 \cap H_2 = \{\}
since card(H_1) + card(H_2) = 2^{d_1+d_2+1}
so \{H_1 \cup H_2\} can shatter all d_1 + d_2 + 1 point

By proper extension with same idea, it can reach higher bound in k points cases

Quote:
Originally Posted by MindExodus View Post
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
Reply With Quote