View Single Post
Old 05-01-2013, 05:01 PM
OlivierB OlivierB is offline
Join Date: Apr 2013
Location: Paris
Posts: 16
Default Re: Q10 higher bound

Originally Posted by marek View Post
I am still confused on how to piece everything together. I like your much cleaner version, but I do have one comment. Having disjoint hypothesis sets does not necessarily mean that the set of dichotomies they create will also be disjoint.

For example, let H1 and H2 be the positive and negative 1d rays, respectively. These two hypothesis sets are disjoint. However, given any data set they can both create the dichotomies of all +1 or all -1. They won't have much overlap beyond that (and maybe THAT is the point), but they won't be entirely disjoint as far as our inequalities are concerned.
Originally Posted by TTHotShot View Post
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.
@ marek, TTHotShot: Well, I agree with your remark, I was too quick: I have not explored the link between a hypothesis set and the dichotomies it generates on a set of points well enough. As a consequence the assertion that m_{H}(N)=m_{H'_1}(N)+m_{H'_2}(N) in general is wrong in general. Instead, it should be an inequality (≤), and probably quite a loose one, since there can be an overlap in the dichotomies generated by H_1 and H_2. Additionally, the definition of m_{H}(N) involves the determination of a maximum, and the independent search of 2 max on the RHS is a lot less constraining than one max on the LHS.
Reply With Quote