View Single Post
Old 04-24-2013, 01:57 AM
Elroch Elroch is offline
Invited Guest
Join Date: Mar 2013
Posts: 143
Default *ANSWER* question 9

I imagine that most people attacked question 9 in the way I did first of all, by guessing that points in a regular polygon configuration would be critical, and then seeing what is possible to achieve with a triangle.

I was wondering how many were a little unhappy with this and found the alternative route that I eventually chanced on. This involves embedding the 2 dimensional space in a 6-dimensional one, (by the map (x_1,x_2)\mapsto(x_1,x_2,x_1,x_2,x_1,x_2) and map each triangle hypothesis to a single perceptron hypothesis on the 6-dimensional space, by considering it as a combination of 3 perceptron hypotheses. This idea seems to have quite a lot of mileage for similar higher dimensional problems that would be intractable using ad hoc methods.

[EDIT: the amusing thing is that although this idea did give me more confidence in my answer, I can now see my mental reasoning was invalid, and this does not really justify the *ANSWER* label. However, I am now fairly happy with simple geometric reasoning based on visualisation that n-sided polygons in 2 dimensions have VC dimension 2n+1, and it seems rather a big co-incidence that this is the same as the VC dimension of perceptrons in \mathbb{R}^{2n} that my erroneous argument would give]
Reply With Quote