3-of-{red, not(small), soft, not(box)}
is true if any 3 of the 4 given literals are true for an example. Note: M and N are not parameters defining the space, the hypothesis space includes all possible rules with all possible meaningful values of M and N over the set of n features.
(a) Determine an upper-bound on the PAC sample complexity of any consistent learning algorithm using this hypothesis space.
(b)
Using this upper-bound, calculate a sufficient number of examples when
= =0.01, n = 50.
(a) Give an upper bound on the number of randomly drawn training instances sufficient to assure that for any concept in C, any consistent learner using H=C, will, with probability at least 1-, output a hypothesis with error at most .
(b) Calculate a specific number of sufficient examples when = = 0.01.
(c) Generalize your result to disjunctions of k real-valued intervals on a single real-valued feature.