Q10 higher bound - Page 2

MindExodus · #11 04-29-2013, 04:06 AM

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

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.

nkatz · #12 04-29-2013, 08:50 AM

Here is another example for the upper bound:

* H1 takes any 1 point and sets it to + or -, with the other points--if any--getting the opposite sign
* H2 sets all to + or all to -

H1 can only shatter 1 point, and H2 can only shatter 1 point
Their union however can shatter 3 points

MindExodus · #13 04-29-2013, 05:44 PM

And this method can be generalizes!!

for

with VC dimension

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

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

points to -1 and other points to +1
so there is at least

+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

point

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

Quote:

Originally Posted by MindExodus

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$

Elroch · #14 04-29-2013, 06:04 PM

Simpler?

$H_1=\{\}, H_2=\{a\}$

jforbes · #15 04-29-2013, 08:19 PM

Quote:

Originally Posted by MindExodus

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$

MindExodus - very nice; I'm thoroughly convinced.

Quote:

Originally Posted by nkatz

Here is another example for the upper bound:

* H1 takes any 1 point and sets it to + or -, with the other points--if any--getting the opposite sign
* H2 sets all to + or all to -

H1 can only shatter 1 point, and H2 can only shatter 1 point
Their union however can shatter 3 points

nkatz, your example has me slightly puzzled. The only way H1 can fail to shatter 2 points is if there are exactly two points:
H1 contains +- and -+, but not -- or ++
Whereas if you give it three points, it contains
+--,
-+-,
--+,
++-,
+-+, and
-++.
Just looking at the first two points, now H1 contains all 4 combinations. How can this be if its VC dimension is only 1? I think it must be the case that $d_{VC}(H_1) > 1$ , but I'd be unsurprised if I were missing something.

Elroch · #16 04-30-2013, 04:13 AM

A useful little construction is this.

If you have two underlying disjoint sets of points

and

, and hypothesis sets $\mathcal H_A \subset 2^A$ and $\mathcal H_B \subset 2^B$ (where

is the set of subsets of

), then you can can form a new hypothesis set $\mathcal H_{ A X B} \subset 2^{A \cup B}$ with one hypothesis for each pair of hypotheses in $\mathcal H_A$ and $\mathcal H_B$ (in the obvious way). There is a simple relationship between the VC-dimensions of these three hypothesis sets, which can be used in examples.

Elroch · #17 04-30-2013, 04:20 AM

Quote:

Originally Posted by jforbes

MindExodus - very nice; I'm thoroughly convinced.

nkatz, your example has me slightly puzzled. The only way H1 can fail to shatter 2 points is if there are exactly two points:
H1 contains +- and -+, but not -- or ++
Whereas if you give it three points, it contains
+--,
-+-,
--+,
++-,
+-+, and
-++.
Just looking at the first two points, now H1 contains all 4 combinations. How can this be if its VC dimension is only 1? I think it must be the case that $d_{VC}(H_1) > 1$ , but I'd be unsurprised if I were missing something.

I presume he meant it was only one specific point that was being referred to, so $\mathcal H_1$ is +-- and -++, nothing more

Michael Reach · #18 04-30-2013, 07:14 AM

Good work on this problem by several of you guys!

jforbes · #19 04-30-2013, 01:05 PM

Quote:

Originally Posted by Elroch

I presume he meant it was only one specific point that was being referred to, so $\mathcal H_1$ is +-- and -++, nothing more

Wouldn't it then be the case that the union of the hypothesis sets could only shatter two points?

I'm still curious about what went wrong if H1 does in fact include --+, -+-, ... Is this sort of hypothesis set disallowed for some reason?

TTHotShot · #20 04-30-2013, 02:10 PM

Quote:

Originally Posted by OlivierB

$m_{H}(N)=m_{H'_1}(N)+m_{H'_2}(N)$

Great work everyone - this question had me scratching my head until I found this post. The one thing I don't understand is the above statment. Am I missing something? It seems like it should be an inequality.

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode