 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/computational-learning-theory/1/a/i/solution

H

S

when it realizes every binary labelling of

S

: for every function

g : S \to {0, 1}

there is an

h \in H

with

h ∣_{S} = g

. Identifying each classifier with its positive set, this says

{S \cap h : h \in H} = P (S),

where

P (S)

is the power set. Different labellings may require different members of the hypothesis class.

 New to topics? Read the docs here!