Learning From Data – A Short Course: Exercise 5.1

Consider hypothesis sets H_{1} and H_{100} that contain Boolean functions on 10 Boolean variables, so X = {-1,+1}^{10}. H_{1} contains all Boolean functions which evaluate to +1 on exactly one input point, and to -1 elsewhere; H_{100} contains all Boolean functions which evaluate to +1 on exactly 100 input points, and to -1 elsewhere.
(a) How big (number of hypotheses) are H_{1} and H_{100}?
(b) How many bits are needed to specify one of the hypotheses in H_{1}?
(c) How many bits are needed to specify one of the hypotheses in H_{100}?

(a) Each input point has 10 Boolean features, so: | H_{1} | = 2^{10}| H_{100} | = \binom{2^{10}}{100}

(b) 10.

(c) \text{upper}(\log_{2}(| H_{100} |)) = 469.


Facebooktwitterredditpinterestlinkedinmail

2 comments on “Learning From Data – A Short Course: Exercise 5.1”

  1. Isn’t |H_100| = 2^10 choose 100? 2^1000 seems extremely high since there’s only 2^1024 possible functions.

Leave a Reply

Your email address will not be published. Required fields are marked *