In class we saw that finite hypothesis classes are always PAC-learnable. Here, we will prove that...

 

Transcribed Image Text:

In class we saw that finite hypothesis classes are always PAC-learnable. Here, we will prove that there are also infinite hypothesis class that are PAC-learnable. Let's first start with an easier case, that is we consider a specific distribution, rather than proving it for any distribution. Let X = {x R2 ||x||2 1} and y = {0,1}. Consider the class of classifiers given by concentric circles in the plane that predict 1 inside the circle and 0 outside, that is F= {h h(x) = 1 |||x||2 r], r > 0}. Note the cardinality of this hypothesis class is infinite. Denote by hs the solution of the ERM problem. (a) Assume that the samples x are uniformly distributed in X and assume the realizability as- sumption. Prove that if the number of training samples is bigger than the sample complexity function m (e, 6) = log, then with probability at least 1-6 we have Lp(hs) In class we saw that finite hypothesis classes are always PAC-learnable. Here, we will prove that there are also infinite hypothesis class that are PAC-learnable. Let's first start with an easier case, that is we consider a specific distribution, rather than proving it for any distribution. Let X = {x R2 ||x||2 1} and y = {0,1}. Consider the class of classifiers given by concentric circles in the plane that predict 1 inside the circle and 0 outside, that is F= {h h(x) = 1 |||x||2 r], r > 0}. Note the cardinality of this hypothesis class is infinite. Denote by hs the solution of the ERM problem. (a) Assume that the samples x are uniformly distributed in X and assume the realizability as- sumption. Prove that if the number of training samples is bigger than the sample complexity function m (e, 6) = log, then with probability at least 1-6 we have Lp(hs)