View Single Post
Old 09-23-2012, 08:23 PM
magdon's Avatar
magdon magdon is offline
Join Date: Aug 2009
Location: Troy, NY, USA.
Posts: 597
Default Re: Problem 2.15

The function h is +1 in some region and is -1 in the complement - i.e. it takes on two values. Any function can be monotonic, even one that takes on just 2 values.

In (b), you are asked to compute m(N). To compute m(N) you need to count the maximum number of implementable dichotomys on some N points. The problem suggest a set of N points which might be helpful. The fact that no point is larger than another is crucial [hint: because if a point were larger than another, there is a dichotomy that you cannot implement].

Originally Posted by mileschen View Post
In (a), it said that we should provide a monotonic classifier. Then, why there are +1 and -1 regions?

Also, as it said in (b) that generating the next point by increasing the first component and decreasing the second component. Then, how can we determine which point is larger? Because X1>=X2 if and only if the inequality is satisfied for every component. However, the next point is just with one component larger than that of the first one, while another component is less than that of the first one. So, it's a little confusing.
Have faith in probability
Reply With Quote