Understanding Machine Learning: From Theory to Algorithms

82 The VC-Dimension

where, forx= (x 1 ....,xn),hp(x) = (^1) [p(x)≥0](the degree of a multi-
variable polynomial is the maximal sum of variable exponents over all
of its terms. For example, the degree ofp(x) = 3x^31 x^22 + 4x 3 x^27 is 5).

1. Use the Dudley representation to figure out the VC-dimension of the
   classP 1 d– the class of alld-degree polynomials overR.


2. Prove that the class of all polynomial classifiers overRhas infinite
   VC-dimension.


3. Use the Dudley representation to figure out the VC-dimension of the
   classPnd(as a function ofdandn).