Q4 and Q5

tathagata · #1 01-23-2013, 04:18 AM

Regarding Q4, which asks us to determine the break point of a 3D Perceptron, just a clarification: I am thinking that the 2D case will also be a pathological case in 3D, as it is just a special case for the 3D plane, but if there exists any setting of 4 points in 3D that can be shattered by the 3D Perceptron then break point is greater than four, since we take the maximum? (like the 2D case with collinear points for N = 3)

Regarding Q5, as I understand it, any monotonically increasing function <= 2^N for all N, can be a possible growth function, is that correct or are there more restrictions?
Also we have a N choose 2 term in one of the options that is not defined for N = 1, but that can be logically regarded as zero, right?

yaser · #2 01-23-2013, 10:27 AM

Quote:

Originally Posted by tathagata

Regarding Q4, which asks us to determine the break point of a 3D Perceptron, just a clarification: I am thinking that the 2D case will also be a pathological case in 3D, as it is just a special case for the 3D plane, but if there exists any setting of 4 points in 3D that can be shattered by the 3D Perceptron then break point is greater than four, since we take the maximum? (like the 2D case with collinear points for N = 3)

You are right.

Quote:

Regarding Q5, as I understand it, any monotonically increasing function <= 2^N for all N, can be a possible growth function, is that correct or are there more restrictions?

There are more restrictions that were discovered in Lecture 6.

Quote:

Also we have a N choose 2 term in one of the options that is not defined for N = 1, but that can be logically regarded as zero, right?

Correct. For

, we have ${N \choose k}=0$ .

tathagata · #3 01-24-2013, 05:08 AM

Quote:

Originally Posted by yaser

There are more restrictions that were discovered in Lecture 6.

But doesn't lecture 6 discuss a more strict bound only if we have a break point? Whereas Q5 asks for any possible growth function, so being less than 2^N is sufficient I would have thought. What am i missing?

geekoftheweek · #4 01-24-2013, 11:30 AM

Quote:

Originally Posted by yaser

You are right.

I don't follow. In 2D, all four points must be coplanar so no line can shatter the points. In 3D the two x's and two o's can be separated along the third axis and this can easily be shattered by a plane. You need k > 4 as a breakpoint. Am I missing something? Perhaps I did not understand the OP's question.

yaser · #5 01-24-2013, 01:11 PM

Quote:

Originally Posted by tathagata

But doesn't lecture 6 discuss a more strict bound only if we have a break point? Whereas Q5 asks for any possible growth function, so being less than 2^N is sufficient I would have thought. What am i missing?

We either have a break point, or else we don't. In the latter case, the growth function is identically

. In the former case, the growth function is constrained such that many formulas cannot possibly be valid growth functions.

yaser · #6 01-24-2013, 01:13 PM

Quote:

Originally Posted by geekoftheweek

I don't follow. In 2D, all four points must be coplanar so no line can shatter the points. In 3D the two x's and two o's can be separated along the third axis and this can easily be shattered by a plane. You need k > 4 as a breakpoint. Am I missing something? Perhaps I did not understand the OP's question.

You are not missing anything. You have just articulated why a break point in 2D may not be a break point in 3D.

Anne Paulson · #7 01-24-2013, 01:29 PM

The terminology can be a bit confusing, because a break point exists if there is no pathological case that can be shattered. If you can shatter, you don't break.