Exercise 2.8

---

1. In this chapter, we commented that given an unbiased hypothesis space (the power set of instance), the learner would find that each unobserved instance would match exactly half the current members of the version space, regardless of which training examples had been observed.
   
   Prove this. In particular, prove that for any instance space X, and set of training examples D, and any instance x in X not present in D, that if H is the power set of X, then exactly half the hypotheses in V S _{H, D} will classify x as positive and half will classify it as negative.




For any hypothesis h in the version space that covers x, there will be another hypothesis h' in the power set that is identical to h except for its classification of x. And of course if h is in the version space, then h' will be as well, because it agrees with h on all the observed training examples.

So, any hypothesis in the space has an evil twin hypothesis (in regards to x anyway), that will contradict any classification of x. So, since every hypothesis should classify x as either positive or negative, there will always be an equal number of opposite classifications. If there wasn't, then H would not be a power set of X and that would be quite contrary.

Note: this is the basic idea but it would be nice to work out the details.

---