Question: 3.26 Symmetric functions. A function h: f0; 1gn ! f0; 1g is symmetric if its value is uniquely determined by the number of 1's in

3.26 Symmetric functions. A function h: f0; 1gn ! f0; 1g is symmetric if its value is uniquely determined by the number of 1's in the input. Let C denote the set of all symmetric functions.

(a) Determine the VC-dimension of C.

(b) Give lower and upper bounds on the sample complexity of any consistent PAC learning algorithm for C.

(c) Note that any hypothesis h 2 C can be represented by a vector (y0; y1; : : : ; yn)

2 f0; 1gn+1, where yi is the value of h on examples having precisely i 1's.

Devise a consistent learning algorithm for C based on this representation.

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock blur-text-image

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Pattern Recognition And Machine Learning Questions!

Briefly describe ASCII and Unicode and draw attention to any relationship between them. [3 marks] (b) Briefly explain what a Reader is in the context of reading characters from data. [3 marks] A...

Portray in words what transforms you would have to make to your execution to some degree (a) to accomplish this and remark on the benefits and detriments of this thought.You are approached to compose...

A network based service manages persistent objects. The service must enforce an access control policy to protect the objects. (a) Discuss how this access control might best be implemented for the...

Suppose that R(A, B, C) is a relational schema with functional dependencies F = {A, B C, C B}. (i) Is this schema in 3NF? Explain. [2 marks] (ii) Is this schema in BCNF? Explain. [2 marks] (b)...

Prolog You are approached to compose a Prolog program to work with twofold trees. Your code shouldn't depend on any library predicates and you ought to expect that the mediator is running without...

QUIZ... Let D be a poset and let f : D D be a monotone function. (i) Give the definition of the least pre-fixed point, fix (f), of f. Show that fix (f) is a fixed point of f. [5 marks] (ii) Show that...

lup ] (d) Show how a generating (or "mother") wavelet (x) can spawn a family of "daughter" wavelets jk(x) by simple shifting and scaling operations, and explain the advantages of representing...

For monotone functions f, f0: P Q between posets (P, vP ) and (Q, vQ), let f v f(i) Prove that the binary relation v is a partial order. [3 marks] (ii) For monotone functions between posets p : P 0...

MATHEMATICS FOR MACHINE LEARNING Marc Peter Deisenroth A. Aldo Faisal Cheng Soon Ong Contents Foreword 1 Part I Mathematical Foundations 9 1 Introduction and Motivation 11 1.1 Finding Words for...

Let i and j be positive integers. (i) Prove that there exist natural numbers a and b such that ai = bj+gcd(i, j). You may use standard results provided that you state them clearly. [4 marks] (ii) Let...

How did the APB pave the way for the FASB?

Provide arguments both for and against the Federal Reserves adoption of a target growth rate for M2. What assumptions would be necessary to compute such a target rate?

5 (1 point) Fiber Inc. financial statements are presented in the table below. Based on the information in the table, calculate the firm's total assets turnover ratio. Round the answers to two decimal...