Mas 557 기계학습 이론 및 응용

Homework #5

due date: 5/10/05

1. Consider the class  of concepts of the form , where , ,  and  are integers in the interval (0, 99).  Give an upper bound on the number of randomly drawn training examples sufficient to assure that for any target concept , any consistent learner using  will, with probability of 95%, output a hypothesis with error at most 0.15.

2. A learner that makes no assumption that the target concept is representable by  and that simply finds the hypothesis with minimum training error, is called an agnostic learner.  In this agnostic learning, how many samples are required for  with the accuracy  and the confidence ?  Here, we assume that [eqn: LEFT | H` RIGHT |] is finite.

Hint: Apply the following Hoeffding bound: assuming the empirical error  is an unbiased estimator of the true error , the following inequality holds:

where  represents the number of samples.

3. Consider the space of instances  corresponding to all points in the ,  plane.  Give the VC dimension of the following hypothesis spaces:

(a)  = the set of all rectangles in the ,  plane.

That is,

(b)  = triangles in the ,  plane.  Points inside the triangle are classifies as

positive samples.

Justify your answer.

4. Prove the following theorem:

If [eqn: d=VCD(H)], the growth function is determined by

[eqn: PI _{H} (m) <= phi _{d} (m) <= LEFT ( {em} over {d} RIGHT ) ^{d} .]

Hint: Prove the theorem by induction.  Use the Sauer's lemma.