Consider the hypothesis class of all conjunctions of literals over d vari- ables. The empty conjunction...

Transcribed Image Text:

Consider the hypothesis class of all conjunctions of literals over d vari- ables. The empty conjunction ho is interpreted as the all-positive hy- pothesis (ho(x) = 1 for all x). Any conjunction which contains a vari- able and its negation (like ,, etc.) is interpreted as the all-negative hypothesis. We assume realizability, which in this context, means that there exists a Boolean conjunction that generates the labels. Thus, each example (x, y) = x x y consists of an assignment to the d Boolean variables and its truth value. For example, for d = 3 and the true hypothesis f(x) = ₁72, the training set S may contain ((1, 1, 1), 0), ((1, 0, 1), 1), ((0, 1, 0), 0), ((1, 0, 0), 1). (a) Prove that [H] = 3ª + 1. (b) Prove that the hypothesis class of all conjunctions over d variable is PAC learnable and bound its sample complexity m(e, 6). (c) Design an algorithm (using pseudocode) that implements the ERM rule and whose time is polynomial in dm. Consider the hypothesis class of all conjunctions of literals over d vari- ables. The empty conjunction ho is interpreted as the all-positive hy- pothesis (ho(x) = 1 for all x). Any conjunction which contains a vari- able and its negation (like ,, etc.) is interpreted as the all-negative hypothesis. We assume realizability, which in this context, means that there exists a Boolean conjunction that generates the labels. Thus, each example (x, y) = x x y consists of an assignment to the d Boolean variables and its truth value. For example, for d = 3 and the true hypothesis f(x) = ₁72, the training set S may contain ((1, 1, 1), 0), ((1, 0, 1), 1), ((0, 1, 0), 0), ((1, 0, 0), 1). (a) Prove that [H] = 3ª + 1. (b) Prove that the hypothesis class of all conjunctions over d variable is PAC learnable and bound its sample complexity m(e, 6). (c) Design an algorithm (using pseudocode) that implements the ERM rule and whose time is polynomial in dm.

Answer rating: 100% (QA)

Solution is interpreted hx 1 X Given that the empty conjun... View the full answer