机器学习代写: COMS 4771 HW4

1 [PAC learning and VC dimension]

(a) Consider a domain with n binary features and binary class labels. Let Fd be the hypoth- esis class that contains all decision trees over these features that have depth at most d. Give the tightest possible VC-dimension estimate of Fd.

(b) [asharperlearningrateforfindingperfectpredictors!]Considerafinitesizehypoth- esisclassFthatcontainstheperfectpredictor,thatis,∃f∗ ∈F,s.t.∀(x,y)∼D(X×Y), y = f∗(x). We will show that for such a hypothesis class F, we can derive a sharper sample complexity rate than what was shown in class (i.e., Occam’s Razor bound).

1. (i)  Forafixedǫ>0,wesaythataclassifierf isǫ-badif P(x,y)∼D[f(x) = y] < 1 − ǫ.

   What is the chance that output of a given ǫ-bad f matches the true label for all m samples drawn i.i.d. from D? That is, for a given ǫ-bad f, calculate

   P(xi,yi)mi=1∼D􏰗∀i f(xi) = yi | f is ǫ-bad􏰘.

2. (ii)  What is the chance that event in part (i) occurs for some f ∈ F ? That is, calculate

   P(xi,yi)mi=1∼D􏰗∃ ǫ-bad f ∈ F, such that ∀i f(xi) = yi􏰘.

3. (iii)  Observe that event is part (ii) is a “bad” event: an ERM-algorithm can pick a ǫ-bad classifier if it happens to perfectly classify on the m i.i.d. samples. We want to limit the probability of this bad event by at most δ > 0 amount. So how many i.i.d. samples suffice to ensure that with probability at least 1 − δ, an ERM-algorithm does not return an ǫ-bad classifier?

   1

(c) Given a collection of models F, suppose you were able to develop an algorithm A : (xi , yi )ni=1 􏰔→ fnA (that is, given n labeled training samples, A returns a model fnA ∈ F ) that has the following property: for all ǫ > 0, with probability 0.55 (over the draw of n = O( 1 ) samples,

ǫ2

err(fnA) − inf err(f) ≤ ǫ, f∈F

where err(f) := P(x,y)[f(x) ̸= y].
Show that one can construct an algorithm B : (xi , yi )i=1 􏰔→ fn′ with the property: for

n′ B allǫ>0andallδ>0,withprobabilityatleast1−δoveradrawofn′ samples:

B

(Hint: Algorithm B can make multiple calls to the algorithm A.)

err(fn′)− inf err(f)≤ǫ. f∈F

Moreover show that n′ = poly( 1 , 1 ) samples are enough for the algorithm B to return

ǫδ
such a model fn′ . Hence, the model class F is efficiently PAC-learnable.

B

3 [different learning rates for different strategies] Here will explore how the rate by which an algorithm learns a concept can change based on how labeled examples are obtained. For that we look at three settings: (i) an active learning setting where the algorithm has the luxury of specifying a data point and querying its label, (ii) a passive learning setting where labeled examples are drawn at random and (iii) an adversarial setting where training examples are given by an adversary that tries to make your life hard.

Consider a binary classification problem where each data point consists of d binary features. Let F be the hypothesis class of conjunctions of subsets of the d features and their negations. So for example one hypothesis could be f1(x) = x1 ∧ x2 ∧ ¬xd (where ∧ denotes the logical “and” and ¬ denotes the logical “not”). Another hypothesis could be f2(x) = ¬x3 ∧ x5. A conjunction in F cannot contain both xi and ¬xi. We assume a consistent learning scenario where there exists a hypothesis f ∗ ∈ F that is consistent with the true label for all data points.

1. (i)  In the active learning setting, the learning algorithm can query the label of an unlabeled example. Assume that you can query any possible example. Show that, starting with a single positive example, you can exactly learn the true hypothesis f∗ using d queries.
2. (ii)  In the passive learning setting, where the examples are drawn i.i.d. from an underlying fixed distribution D. How many examples are sufficient to guarantee a generalization error less than ǫ with probability ≥ 1 − δ?

   3

(iii) Show that if the training data is not representative of the underlying distribution, a con- sistent hypothesis f∗ can perform poorly. Specifically, assume that the true hypothesis f∗ is a conjunction of k out of the d features for some k > 0 and that all possible data points are equally likely. Show that there exists a training set of 2(d−k) unique examples and a hypothesis f that is consistent with this training set but achieves a classification error ≥ 50% when tested on all possible data points.